First-order Methods Almost Always Avoid Saddle Points

2017/10/20 by Jason D. Lee, Lee, Jason D., Ioannis Panageas +9 · 3 citations
Computer Science · Engineering · Physics and Astronomy · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Model Reduction and Neural Networks #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1710.07406

openalex publication_date 2017/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We establish that first-order methods avoid saddle points for almost all initializations. Our results apply to a wide variety of first-order methods, including gradient descent, block coordinate descent, mirror descent and variants thereof. The connecting thread is that such algorithms can be studied from a dynamical systems perspective in which appropriate instantiations of the Stable Manifold Theorem allow for a global stability analysis. Thus, neither access to second-order derivative information nor randomness beyond initialization is necessary to provably avoid saddle points.

Citations

• On the saddle point problem for non-convex optimization
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified\n Geometric Analysis
• When is a Convolutional Filter Easy To Learn?

Cited by

• Training Generative Adversarial Networks with Adaptive Composite Gradient
• Escaping spurious local minimum trajectories in online time-varying nonconvex optimization
• Deep Learning Theory Review: An Optimal Control and Dynamical Systems Perspective

Related

• First-order methods almost always avoid saddle points: the case of vanishing step-sizes
• Randomized coordinate gradient descent almost surely escapes strict saddle points
• Gradient Descent Converges to Minimizers
• Distributed Gradient Descent: Nonconvergence to Saddle Points and the\n Stable-Manifold Theorem
• Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity