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

Ioannis Panageas, Georgios Piliouras, Xiao Wang

Abstract

In a series of papers, 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. 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 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 these methods, we prove a stable manifold theorem applicable to time non-homogeneous systems and generalize previous results for vanishing step-sizes.

Introduction

In non-convex optimization, particularly in the training of deep neural networks, the landscape is often dominated by saddle points rather than local minima. These points, where the gradient vanishes but the Hessian has at least one negative eigenvalue, can significantly slow down or trap optimization algorithms. While previous research demonstrated that first-order methods with constant step-sizes almost never converge to these "strict" saddle points, a significant gap remained: in practice, practitioners almost always use vanishing step-sizes (learning rate decay) to ensure convergence to a local minimum.

The mathematical difficulty lies in the transition from time-homogeneous to time non-homogeneous dynamical systems. When the step-size $\alpha_k$ is constant, the update rule is stationary, allowing the application of the classical Stable Manifold Theorem. However, when $\alpha_k$ varies with time, the system's behavior changes at every iteration, rendering standard theorems inapplicable.

Theoretical Framework: A Non-Homogeneous Stable Manifold Theorem

The core contribution of this work is a significant extension of dynamical systems theory. The authors develop a new version of the Stable Manifold Theorem specifically designed for discrete-time, non-homogeneous dynamical systems.

To achieve this, they utilize the Lyapunov-Perron method to construct a "stable manifold"—a set of initial points that would eventually lead the algorithm into a saddle point. By applying measure theory, they prove that this stable set has a Lebesgue measure of zero. This implies that for any random initialization, the probability of the algorithm being trapped in the stable manifold of a strict saddle point is zero.

Algorithmic Mapping and Generality

The power of this new theorem lies in its broad applicability. The authors demonstrate that several fundamental first-order methods satisfy the necessary conditions:

  • Gradient Descent: The standard update $x_{k+1} = x_k - \alpha_k \nabla f(x_k)$.
  • Mirror Descent: Generalizing gradient descent to non-Euclidean geometries.
  • Proximal Point Method: An implicit update rule often used in non-smooth optimization.
  • Manifold Descent: Optimization constrained to a Riemannian manifold.

By proving a general theorem first, the authors provide a unified framework that covers these diverse algorithms under the same theoretical umbrella.

The $1/k$ Threshold and Step-Size Decay

A critical insight from the analysis is the requirement on the decay rate of the step-size. The authors identify that the step-size $\alpha_k$ must be of order $\Omega(1/k)$.

If the step-size decays too aggressively (e.g., $\alpha_k = 1/k^2$), the sum of the step-sizes $\sum \alpha_k$ converges to a finite value. In such cases, the algorithm may "run out of gas," stalling near a saddle point or even a non-critical point because it lacks the cumulative "push" needed to escape the unstable direction. However, as long as the cumulative step-size is infinite (as with $1/k$ or $1/\sqrt{k}$), the unstable directions—the paths leading "down" from the saddle—remain powerful enough to eventually steer the trajectory away.

Conclusion

This paper provides a rigorous mathematical foundation for the empirical success of learning rate decay in non-convex optimization. By extending the Stable Manifold Theorem to time-varying systems, it confirms that vanishing step-sizes do not increase the risk of getting trapped in saddle points compared to constant step-sizes, provided the decay is not overly rapid. This work bridges the gap between optimization theory and practical deep learning heuristics, ensuring that our most common tools are theoretically sound even in complex, non-convex landscapes.

Summary updated

Abstract

In a series of papers \cite{LSJR16, PP17, LPP}, 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 $α$ is constant, i.e., does not depend on time (and 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 \cite{LPP} for vanishing 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