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

arXiv: https://arxiv.org/abs/1906.07772 · HTML: https://mlsanity.com/paper/1906.07772/

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2019.

## Built on by (most cited first, 30 of 35)

- [Multi-Task Learning as a Bargaining Game](https://mlsanity.com/paper/2202.01017/) (2022)
- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [An Unconstrained Layer-Peeled Perspective on Neural Collapse](https://mlsanity.com/paper/2110.02796/) (2021)
- [Convergence of gradient descent for learning linear neural networks](https://mlsanity.com/paper/2108.02040/) (2021)
- [Evaluating Model-free Reinforcement Learning toward Safety-critical Tasks](https://mlsanity.com/paper/2212.05727/) (2022)
- [Smooth Bilevel Programming for Sparse Regularization](https://mlsanity.com/paper/2106.01429/) (2021)
- [On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks](https://mlsanity.com/paper/2112.09684/) (2021)
- [A proof of convergence for the gradient descent optimization method with random initializations in the training of neural networks with ReLU activation for piecewise linear target functions](https://mlsanity.com/paper/2108.04620/) (2021)
- [A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functions](https://mlsanity.com/paper/2104.00277/) (2021)
- [Convergence proof for stochastic gradient descent in the training of deep neural networks with ReLU activation for constant target functions](https://mlsanity.com/paper/2112.07369/) (2021)
- [Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent](https://mlsanity.com/paper/2101.05248/) (2021)
- [Riemannian stochastic optimization methods avoid strict saddle points](https://mlsanity.com/paper/2311.02374/) (2023)
- [No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Paths](https://mlsanity.com/paper/2306.11922/) (2023)
- [Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learning](https://mlsanity.com/paper/2306.14522/) (2023)
- [Fairness-Aware Meta-Learning via Nash Bargaining](https://mlsanity.com/paper/2406.07029/) (2024)
- [Gradient descent provably escapes saddle points in the training of shallow ReLU networks](https://mlsanity.com/paper/2208.02083/) (2022)
- [Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decomposition](https://mlsanity.com/paper/2210.00346/) (2022)
- [Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience](https://mlsanity.com/paper/2103.09424/) (2021)
- [Towards Understanding Gradient Dynamics of the Sliced-Wasserstein Distance via Critical Point Analysis](https://mlsanity.com/paper/2502.06525/) (2025)
- [On exploration of an interior mirror descent flow for stochastic nonconvex constrained problem](https://mlsanity.com/paper/2507.15264/) (2025)
- [Inertial Newton Algorithms Avoiding Strict Saddle Points](https://mlsanity.com/paper/2111.04596/) (2021)
- [Almost Sure Saddle Avoidance of Stochastic Gradient Methods without the Bounded Gradient Assumption](https://mlsanity.com/paper/2302.07862/) (2023)
- [Avoiding strict saddle points of nonconvex regularized problems](https://mlsanity.com/paper/2401.09274/) (2024)
- [Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm](https://mlsanity.com/paper/2101.02625/) (2021)
- [Asymptotic Escape of Spurious Critical Points on the Low-rank Matrix Manifold](https://mlsanity.com/paper/2107.09207/) (2021)
- [Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics](https://mlsanity.com/paper/2109.03974/) (2021)
- [Accelerated Multiplicative Weights Update Avoids Saddle Points almost always](https://mlsanity.com/paper/2204.11407/) (2022)
- [Efficient algorithms for regularized Poisson Non-negative Matrix Factorization](https://mlsanity.com/paper/2404.16505/) (2024)
- [Disentangle Sample Size and Initialization Effect on Perfect Generalization for Single-Neuron Target](https://mlsanity.com/paper/2405.13787/) (2024)
- [Langevin Multiplicative Weights Update with Applications in Polynomial Portfolio Management](https://mlsanity.com/paper/2502.19210/) (2025)

## Abstract (arXiv)

In a series of papers citeLSJR16, 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 C2 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 citeLPP for vanishing step-sizes.