Source-linked AI summary
Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
Ioannis Panageas, Georgios Piliouras
TL;DR
The paper addresses whether gradient descent can avoid strict saddles when critical points are non-isolated and when global Lipschitz assumptions are unavailable. It generalizes the convergence analysis to forward-invariant convex domains and derives a step-size bound. The main result is that the initial conditions leading to strict saddles have Lebesgue measure zero under these extensions.
Problem
Prior guarantees require isolated critical points and globally Lipschitz gradients, leaving open whether convergence results extend to non-isolated equilibria and weaker smoothness settings.
Method
The paper combines dynamical-systems, topology, analysis, optimization, linear-algebra, and eigenvalue arguments to analyze the gradient-descent map on globally or forward-invariant domains.
Results
The set of initial conditions whose gradient-descent iterates converge to a strict saddle has Lebesgue measure zero even without isolated critical points, including on forward-invariant convex domains.
Takeaways & Limitations
Saddle points are of little concern for deterministic gradient descent under the paper’s weak assumptions, including settings with non-isolated critical points.
Takeaways & Limitations
The forward-invariant-domain result assumes an open convex domain S, bounded Hessian spectral norm, and g(S) ⊆ S.
Abstract
from arXiv · showhide
Given a non-convex twice differentiable cost function f, we prove that the set of initial conditions so that gradient descent converges to saddle points where \nabla^2 f has at least one strictly negative eigenvalue has (Lebesgue) measure zero, even for cost functions f with non-isolated critical points, answering an open question in [Lee, Simchowitz, Jordan, Recht, COLT2016]. Moreover, this result extends to forward-invariant convex subspaces, allowing for weak (non-globally Lipschitz) smoothness assumptions. Finally, we produce an upper bound on the allowable step-size.
1 Introduction
Gradient descent is practically useful in non-convex optimization despite limited understanding of saddle-point geometry, but prior guarantees require restrictive assumptions. This work addresses those restrictions by removing isolated-equilibrium assumptions, weakening smoothness requirements on invariant domains, and bounding the step size.
- Motivation: Gradient descent remains useful for non-convex problems with complicated saddle-point continua because it does not require global geometric knowledge.Examples include nonnegative matrix factorization and congestion or potential games with symmetry-induced saddle continua.
- Prior result: Prior theory showed almost-sure convergence to local minima or negative infinity under strict-saddle structure, random initialization, and sufficiently small constant step size.The strict-saddle property requires every critical point to be either a local minimizer or have a strictly negative Hessian eigenvalue.
- Limitations: That result assumes isolated critical points, globally L-Lipschitz gradients, and step size α < 1/L, limiting its applicability to symmetric objectives and non-globally-Lipschitz functions.The paper specifically notes that even cubic polynomials can violate global Lipschitz continuity of the gradient.
- Contributions: The paper removes the isolated-saddle assumption, allows forward-invariant convex domains under weaker smoothness conditions, and derives an upper bound on the allowable step size.Its proof combines dynamical systems, topology, analysis, optimization theory, linear algebra, and eigenvalue analysis.
- Broader context: The analysis connects gradient-like dynamics to broader applications, including game theory and mathematical biology, where dynamics decrease cost without necessarily following steepest descent.Related work studies analogous convergence claims for replicator dynamics and multiplicative-weights algorithms.
2 Preliminaries
The paper frames gradient descent as a discrete dynamical system whose fixed points are critical points, then extends measure-zero avoidance of strict saddles beyond isolated equilibria and global Lipschitz assumptions.
- Gradient descent updates x_k by x_{k+1}=x_k−α∇f(x_k), equivalently applying g(x)=x−α∇f(x).
- Fixed points of g are exactly critical points, while local minima form only a subset, so trajectories may converge to non-minimizing saddle points.
- A strict saddle is a critical point whose Hessian has a negative minimum eigenvalue; the paper studies whether initial conditions converging to such points have measure zero.
- Main results: The paper generalizes earlier measure-zero results from isolated to non-isolated critical points, including potentially uncountably many critical points.
- Main results: On an open convex forward-invariant domain S, the same conclusion holds without requiring globally Lipschitz gradients, provided g(S)⊆S and 0<α<1/L.
- Main results: Eigenvalue analysis of I−α∇²f(x) supplies upper bounds on the gradient-descent step-size.
3 Proving the theorems
The proofs extend saddle-avoidance results to non-isolated critical points and forward-invariant convex domains. They combine Lipschitz regularity, diffeomorphism properties, center-stable manifolds, and measure-zero arguments.
- Theorem 3: Theorem 3 generalizes Theorem 2 by working on a forward-invariant domain S instead of requiring global assumptions on R^N.The proof notes that setting S = R^N recovers Theorem 2.
- Regularity: Under the Hessian spectral-norm bound on a convex domain, ∇f is Lipschitz there, enabling the dynamical-systems argument.The paper establishes both directions between the Hessian bound and Lipschitzness of ∇f on S.
- Diffeomorphism: For sufficiently small α, the gradient-descent map g(x) = x − α∇f(x) is a diffeomorphism on S.Injectivity follows from αL < 1, while invertibility of I − α∇²f(x) yields local diffeomorphism properties.
- Proof strategy: The proof departs substantially from the earlier approach by introducing new tools and ideas beyond the cited prior work.The paper explicitly characterizes the approach as significantly different from Lee et al.
- Measure-zero argument: A strict saddle has an unstable direction, so its local center-stable manifold has lower dimension and Lebesgue measure zero.The proof then uses countable covers and null-set preservation under the locally Lipschitz inverse map.
- Consequences: Consequently, the set of initial conditions in S whose gradient-descent trajectories converge to strict saddles has measure zero.With an absolutely continuous prior and convergence for every initial condition, the probability of converging to a local minimizer is 1.
4 Examples
The examples illustrate saddle avoidance with non-isolated critical points and with a non-globally-Lipschitz function on a forward-invariant set. They also show that an overly large step-size can prevent convergence.
- Non-isolated critical points: The function f(x,y,z) = 2xy + 2xz − 2x − y − z has a line of critical points, all of which are strict saddles.Their common minimum Hessian eigenvalue is −2.
- Non-isolated critical points: For small enough step-sizes, practically all trajectories near that critical line diverge rather than converge to the strict saddles.The plotted red trajectories provide the example’s visual illustration.
- Step-size: Choosing α ≥ 2 makes the first coordinate alternate between x and −x, so gradient descent does not converge.This example demonstrates the need for an upper bound on the step-size.
5 Conclusion
The paper argues that gradient descent largely avoids strict saddles under weak assumptions, including non-isolated critical points. It also points toward studying how attraction-region size relates to minimizer quality.
- Main conclusion: Gradient descent can avoid strict saddles under weak assumptions that allow non-isolated critical points.The conclusion presents this as the paper’s central positive result.
- Open direction: The paper hypothesizes that the attraction region of each local minimizer may be proportional to its quality.This is stated as a natural hypothesis rather than an established theorem in the conclusion.
- Related directions: Related work on gradient-like systems in learning games reports minimal attraction regions for bad social states and near-optimal average behavior.The paper identifies extending comparable statements to gradient dynamics as a future question.