First-order methods almost always avoid saddle points: The case of vanishing step-sizes

Ioannis Panageas, Georgios Piliouras, Xiao Wang

Abstract In non-convex optimization, saddle points pose a significant challenge. While previous research established that standard Gradient Descent with a constant step-size almost never converges to strict saddle points, practical applications typically employ vanishing step-sizes to ensure precise convergence to local minima. This paper bridges a critical theoretical gap by proving that common first-order optimization methods—including Gradient Descent, Mirror Descent, Proximal Point, and Manifold Descent—almost surely avoid strict saddle points even when using vanishing step-sizes of order $\Omega(1/k)$.

The Saddle Point Trap

In the non-convex landscapes characteristic of deep learning, saddle points are far more prevalent than local minima. A "strict" saddle point is defined as a critical point where the Hessian matrix possesses at least one negative eigenvalue. This indicates that there is a specific direction leading to lower function values, yet the gradient is zero, creating a plateau that can stall optimization.

A landmark 2016 paper demonstrated that standard Gradient Descent (GD) almost never gets trapped in these saddle points if a constant step-size is used. However, real-world optimization rarely relies on constant steps; instead, it utilizes "vanishing" step-sizes (e.g., decaying at a rate of $1/k$) to help the algorithm settle precisely into a minimum. This discrepancy left an open question: does the theoretical guarantee of saddle-point avoidance hold when the step-size shrinks toward zero?

The Theoretical Gap: Time Non-Homogeneous Systems

Previous proofs of saddle-point avoidance relied heavily on the Stable Manifold Theorem from dynamical systems. This theorem establishes that the set of initializations leading into an unstable fixed point (like a saddle) constitutes a set of measure zero—a vanishingly thin slice of the total parameter space.

Crucially, the classical Stable Manifold Theorem only applies to time-homogeneous systems, where the update rule remains constant across iterations. When a vanishing step-size ($\alpha_k \to 0$) is introduced, the update rule changes at every step $k$. The system becomes time non-homogeneous, rendering classical proofs invalid. The core question becomes whether an optimizer, whose "engine" weakens over time, can still generate sufficient momentum to escape a saddle point.

Methodology: A Generalized Stable Manifold Theorem

To address this, the authors reframe the optimization process through the lens of discrete-time dynamical systems.

  1. A New Stable Manifold Theorem: The paper's primary mathematical contribution is a generalization of the Stable Manifold Theorem for time-varying systems. The authors prove that provided the step-size does not vanish too rapidly, the "stable set" (the collection of initial points that converge to the saddle) remains a low-dimensional manifold.
  2. Lyapunov-Perron Method: To establish the existence of this manifold, the researchers employ the Lyapunov-Perron method. This involves defining an operator on the space of sequences and identifying its fixed point via the Banach Fixed Point Theorem.
  3. Measure Theory: Because this stable manifold has a lower dimension than the ambient space, its Lebesgue measure (volume) is zero. Consequently, under random initialization, the probability of an algorithm landing on a trajectory that converges to a strict saddle point is exactly zero.

Key Insights and Results

The theoretical framework yields several critical insights into the behavior of first-order methods:

  • The $1/k$ Threshold: The avoidance guarantees hold specifically for step-sizes of order $\Omega(1/k)$. If the step-size decays too quickly (e.g., $1/k^2$ or $1/k^4$), the algorithm may "run out of gas" and halt at a non-critical point before it can escape the saddle's vicinity. The authors demonstrate this mathematically using a toy function $f(x, y) = x^2 - y^2$, showing that $1/\sqrt{k}$ and $1/k$ rates successfully escape, while faster decays fail.
  • Universal Applicability: The generalized theorem extends beyond standard Gradient Descent. The authors prove it also applies to:
  • Mirror Descent: Utilized for constrained optimization and non-Euclidean geometries.
  • Proximal Point Method: An implicit method common in non-smooth optimization.
  • Manifold Descent: Optimization where variables are constrained to curved surfaces.
  • Handling Drifting Landscapes: The main technical hurdle was that the optimization "landscape" effectively stretches and changes as the step-size shrinks. By proving a stable manifold theorem for this specific type of "drifting" system, the authors provide a mathematical tool that could be useful in broader areas of control theory and physics.

Limitations and Future Directions

While the paper provides a robust theoretical foundation for vanishing step-sizes, it notes a few boundaries to its current scope:

  • Block Coordinate Descent: The behavior of Block Coordinate Descent—where only a subset of variables is updated at a time—remains an open question under this framework.
  • Strict vs. Non-Strict Saddles: The guarantees apply exclusively to strict saddle points. They do not cover "flat" saddle points (e.g., $f(x) = x^4$ at $x=0$), where second-order derivative information is zero.
  • Rates of Escape: The theorem proves that these algorithms eventually avoid saddle points but does not bound how long the escape takes. In practical deep learning, the speed of escape is often just as critical as the guarantee of escape itself.

Summary updated

Abstract

In a series of papers [Lee et al 2016], [Panageas and Piliouras 2017], [Lee et al 2019], it was established that some of the most commonly used first order methods almost surely (under random initializations) and with step-size being small enough, avoid strict saddle points, as long as the objective function $f$ is $C^2$ and has Lipschitz gradient. The key observation was that first order methods can be studied from a dynamical systems perspective, in which instantiations of Center-Stable manifold theorem allow for a global analysis. The results of the aforementioned papers were limited to the case where the step-size $\alpha$ is constant, i.e., does not depend on time (and typically bounded from the inverse of the Lipschitz constant of the gradient of $f$). It remains an open question whether or not the results still hold when the step-size is time dependent and vanishes with time. In this paper, we resolve this question on the affirmative for gradient descent, mirror descent, manifold descent and proximal point. The main technical challenge is that the induced (from each first order method) dynamical system is time non-homogeneous and the stable manifold theorem is not applicable in its classic form. By exploiting the dynamical systems structure of the aforementioned first order methods, we are able to prove a stable manifold theorem that is applicable to time non-homogeneous dynamical systems and generalize the results in [Lee et al 2019] for time dependent step-sizes.
BibTeX
@inproceedings{panageas2019first,
  author = {Ioannis Panageas and Georgios Piliouras and Xiao Wang},
  title = {{First-order methods almost always avoid saddle points: The case of vanishing step-sizes}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=X4KpnKt-lfv},
}
Figure