Source-linked AI summary
Gradient Descent Converges to Minimizers
Jason D. Lee, Max Simchowitz, Michael I. Jordan, Benjamin Recht
TL;DR
The paper addresses whether gradient descent can avoid saddle points in nonconvex optimization. It applies stable-manifold and invariant-manifold tools to the gradient map, showing that under strict-saddle assumptions, random initialization and a sufficiently small constant step size lead almost surely to local minimizers or negative infinity.
Problem
Worst-case analyses show that gradient descent can converge to saddle points, while finding local minimizers of nonconvex functions is NP-hard in the worst case.
Method
The paper applies the Stable-Center Manifold theorem to the gradient map and uses inversion of the gradient map to characterize stable sets.
Results
With random initialization and sufficiently small constant step size, gradient descent converges almost surely to a local minimizer or negative infinity under the strict saddle property.
Takeaways & Limitations
Short-step gradient descent avoids saddle points without the noise augmentation or complex initialization procedures used by some alternatives.
Takeaways & Limitations
It remains unclear whether the step-size restriction α < 1/L is necessary, including for greedy line-search or backtracking methods.
Abstract
from arXiv · showhide
We show that gradient descent converges to a local minimizer, almost surely with random initialization. This is proved by applying the Stable Manifold Theorem from dynamical systems theory.
1 Introduction
The paper argues that saddle points are usually not a practical obstacle for gradient descent: under mild regularity conditions, random initialization and a sufficiently small constant step size lead almost surely to local minimizers or negative infinity. The analysis uses dynamical-systems tools to avoid curvature-based methods and their higher per-iteration cost.
- 1 Introduction: Saddle points are little concern for gradient descent under mild regularity conditions, despite worst-case examples and nonconvex hardness results.The paper contrasts worst-case behavior with the high-quality solutions practitioners obtain from simple continuous-optimization algorithms.
- 1 Introduction: The strict saddle property requires every critical point to be either a local minimizer or a strict saddle with a strictly negative Hessian eigenvalue.This assumption excludes critical points whose Hessians are highly degenerate in the worst case.
- 1 Introduction: Under the strict saddle property, random initialization and a sufficiently small constant step size yield convergence to a local minimizer or negative infinity almost surely.The step size is less than the inverse Lipschitz constant of the gradient.
- 1 Introduction: The result avoids the need for unbiased noise with sufficiently large variance in every direction, a condition not always satisfied by random initialization.Prior work established convergence using noise-added stochastic methods under strict-saddle assumptions.
- 1 Introduction: Gradient descent has linear per-iteration complexity in dimension, unlike curvature-based algorithms whose complexity can scale quadratically or cubically.The paper also notes that its approach avoids complex and computationally prohibitive initialization procedures used in some global-convergence results.
- 1 Introduction: The paper uses the local stable manifold theorem and gradient-map inversion to establish convergence guarantees and rates depending on the minimizer’s local geometry.These tools are introduced as the main route to formalizing why saddle points are avoided.
2 Preliminaries
The preliminaries recast gradient descent as iteration of a gradient map and define the critical-point and stable-set concepts used in the analysis. They impose twice-continuous differentiability and a Lipschitz-gradient regularity condition, with random initialization absolutely continuous relative to Lebesgue measure.
- 2 Preliminaries: The paper studies a twice-continuously differentiable function f and its gradient map with step size α.The gradient map generates the gradient-descent iterates.
- 2 Preliminaries: The k-fold gradient-map composition represents k gradient-descent steps, and initialization is drawn from a distribution absolutely continuous with respect to Lebesgue measure.All probability statements concern the random initial point x0.
- 2 Preliminaries: A fixed point of the gradient map is equivalent to a critical point of f, allowing critical points to be analyzed through dynamical-systems theory.Critical points may be saddles, local minima, or local maxima.
- 2 Preliminaries: The paper defines isolated critical points, local minima, local maxima, and saddle points through neighborhood-based conditions on f.These definitions distinguish the local geometry of critical points before the strict-saddle analysis.
- 2 Preliminaries: A strict saddle is a critical point whose Hessian has at least one strictly negative eigenvalue.The paper focuses on saddle points with directions of strictly negative curvature.
- 2 Preliminaries: The global stable set consists of gradient-descent initial conditions that converge to a given critical point, while the local stable set describes its local attraction region.These stable sets are central to measuring how likely random initialization is to reach a critical point.
3 Intuition
The intuition is that a strict saddle attracts only from a lower-dimensional stable set, while points with any component in a negative-curvature direction move away. Gradient descent’s global stable-set argument extends this measure-zero picture beyond simple quadratics.
- 3 Intuition: For a quadratic with positive and negative Hessian eigenvalues, gradient descent behaves like power iteration with matrix I − αH.The step-size condition α < 1/L makes positive-curvature components contract and negative-curvature components expand.
- 3 Intuition: For the quadratic example, the saddle’s global stable set is the subspace spanned by positive-eigenvalue directions, and random initialization hits it with probability zero.Any initial component outside that subspace causes divergence to infinity.
- 3 Intuition: In the non-quadratic example, the saddle’s stable set is the x-axis, a zero-measure subset of R2; all other initial points diverge or converge to a local minimum.The Hessian’s positive eigenvector spans the same x-axis, matching the stable-set characterization.
- 3 Intuition: Locally, the stable set is approximated by the span of eigenvectors corresponding to positive Hessian eigenvalues, so negative curvature makes random local initialization leave the neighborhood.Taylor’s theorem supports this local picture when initialization is uniform in a small neighborhood.
- 3 Intuition: The general argument obtains the global stable set by inverting the gradient map and relating global convergence to eventual entry into the local stable set.If the local stable set has measure zero, its inverse images also yield a measure-zero global stable set under the paper’s framework.
- 3 Intuition: The formal result extends the measure-zero conclusion to degenerate critical points whenever at least one negative Hessian eigenvalue exists.In degenerate cases, the stable-set geometry is not characterized solely by the number of positive eigenvectors.
4 Main Results
The paper uses stable-center manifold theory to show that, under strict-saddle and sufficiently small-step assumptions, gradient descent almost surely avoids saddle points with random initialization. Additional conditions ensure convergence exists and, when it does, the limit is a local minimizer.
- Main theorem: Gradient descent never converges to saddle points from an absolutely continuous random initialization when the step size is sufficiently small.The global stable set is formed from countably many inverse images of local stable sets, preserving measure zero under diffeomorphisms.
- Stable-manifold argument: The stable-center manifold theorem characterizes the local stable set of a strict saddle for the gradient map.The proof first establishes that the gradient map is a diffeomorphism for step size α < 1/L, then applies invariant-manifold theory.
- Stable-manifold argument: Because a strict saddle has a negative Hessian eigenvalue, its local stable manifold has positive codimension and measure zero.The Jacobian is Dg(x) = I − α∇²f(x), so the stable-center manifold dimension is smaller than the ambient dimension.
- Further consequences: If the iterates converge, their limit is almost surely a local minimizer rather than a saddle point.This conclusion combines zero probability of saddle convergence with existence of the limit.
- Further consequences: Compact sublevel sets or the Łojasiewicz gradient inequality provide sufficient conditions for the iterates to converge and can support convergence-rate bounds.Compact sublevel sets prevent escape to infinity, while the Łojasiewicz inequality ensures finite traveled length and enables rates.
5 Conclusion
The paper shows that randomly initialized gradient descent with an appropriate constant step size avoids saddle points, and extends the geometric argument beyond gradient descent. It also identifies open questions about step sizes, symmetry, strict-saddle assumptions, and difficult degenerate critical points.
- Main result: Gradient descent with random initialization and an appropriate constant step size does not converge to a saddle point.The analysis uses a characterization of the local stable set from invariant-manifold theory.
- Extensions: The same diffeomorphism-based argument applies to the proximal point algorithm, which therefore does not converge to saddles.The paper expects similar arguments for ADMM, mirror descent, and coordinate descent under appropriate step sizes.
- Open questions: It remains unclear whether the restriction α < 1/L is necessary to avoid saddle points, including for greedy step-size methods.The paper leaves Wolfe line search and backtracking with random initialization for future investigation.
- Open questions: Future work should relax assumptions concerning isolated saddle points, especially for highly symmetric machine-learning problems.The paper suggests quotienting by symmetry groups and applying dynamical-systems techniques on manifolds.
- Scope and limitations: The strict saddle assumption may be stringent: although random functions can satisfy it under broad conditions, difficult unconstrained problems exist where it fails.Quartic-polynomial optimization can have a zero Hessian at a critical point and is linked to co-positive matrix testing and slow-manifold dynamics.