mlsanityData to 7 Oct 2026

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

arXiv 1906.07772 ↗First posted 18 Jun 2019math.OCcited by 35

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 13; 2022: 6; 2023: 4; 2024: 4; 2025: 5; 2026: 3.

35 papers.

Sort:

  1. 2022Multi-Task Learning as a Bargaining Gamecited by 209
  2. 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 169
  3. 2021An Unconstrained Layer-Peeled Perspective on Neural Collapsecited by 87
  4. 2021Convergence of gradient descent for learning linear neural networkscited by 22
  5. 2022Evaluating Model-free Reinforcement Learning toward Safety-critical Taskscited by 18
  6. 2021Smooth Bilevel Programming for Sparse Regularizationcited by 14
  7. 2021On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networkscited by 12
  8. 2021A 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 functionscited by 10
  9. 2021A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functionscited by 9
  10. 2021Convergence proof for stochastic gradient descent in the training of deep neural networks with ReLU activation for constant target functionscited by 9
  11. 2021Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascentcited by 8
  12. 2023Riemannian stochastic optimization methods avoid strict saddle pointscited by 8
23 more
  1. 2023No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Pathscited by 7
  2. 2023Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learningcited by 7
  3. 2024Fairness-Aware Meta-Learning via Nash Bargainingcited by 6
  4. 2022Gradient descent provably escapes saddle points in the training of shallow ReLU networkscited by 5
  5. 2022Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decompositioncited by 4
  6. 2021Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resiliencecited by 3
  7. 2025Towards Understanding Gradient Dynamics of the Sliced-Wasserstein Distance via Critical Point Analysiscited by 3
  8. 2025On exploration of an interior mirror descent flow for stochastic nonconvex constrained problemcited by 3
  9. 2021Inertial Newton Algorithms Avoiding Strict Saddle Pointscited by 2
  10. 2023Almost Sure Saddle Avoidance of Stochastic Gradient Methods without the Bounded Gradient Assumptioncited by 1
  11. 2024Avoiding strict saddle points of nonconvex regularized problemscited by 1
  12. 2021Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithmcited by 0
  13. 2021Asymptotic Escape of Spurious Critical Points on the Low-rank Matrix Manifoldcited by 0
  14. 2021Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamicscited by 0
  15. 2022Accelerated Multiplicative Weights Update Avoids Saddle Points almost alwayscited by 0
  16. 2024Efficient algorithms for regularized Poisson Non-negative Matrix Factorizationcited by 0
  17. 2024Disentangle Sample Size and Initialization Effect on Perfect Generalization for Single-Neuron Targetcited by 0
  18. 2025Langevin Multiplicative Weights Update with Applications in Polynomial Portfolio Managementcited by 0
  19. 2025A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyondcited by 0
  20. 2025Non-Singularity of the Gradient Descent map for Neural Networks with Piecewise Analytic Activationscited by 0
  21. 2026Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimizationcited by 0
  22. 2026Local-Minima-Preserving Continuous Relaxation of Ising Problemscited by 0
  23. 2026Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Frameworkcited by 0