First-order Methods Almost Always Avoid Saddle Points

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.

References in corpus (4)

• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• When Are Nonconvex Problems Not Scary?
• On the saddle point problem for non-convex optimization
• On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization

Cited by in corpus (45)

• Denoising Prior Driven Deep Neural Network for Image Restoration
• The Mechanics of n-Player Differentiable Games
• The Non-convex Geometry of Low-rank Matrix Optimization
• DC3: A learning method for optimization with hard constraints
• Deep Learning Theory Review: An Optimal Control and Dynamical Systems Perspective
• Progress toward favorable landscapes in quantum combinatorial optimization
• ADMM and Accelerated ADMM as Continuous Dynamical Systems
• Beyond Convexity -- Contraction and Global Convergence of Gradient Descent
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
• Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems
• The Mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization
• Escaping from saddle points on Riemannian manifolds
• Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning
• A Cubic Regularized Newton's Method over Riemannian Manifolds
• A general system of differential equations to model first order adaptive algorithms
• Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
• Stable Opponent Shaping in Differentiable Games
• Distributed Deep Learning with Event-Triggered Communication
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• Learning from Sparse Demonstrations
• On the Sublinear Convergence of Randomly Perturbed Alternating Gradient Descent to Second Order Stationary Solutions
• Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points
• First-order methods almost always avoid saddle points: the case of vanishing step-sizes
• Distributed Non-convex Optimization of Multi-agent Systems Using Boosting Functions to Escape Local Optima: Theory and Applications
• Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization
• Escaping spurious local minimum trajectories in online time-varying nonconvex optimization
• Asymptotic study of stochastic adaptive algorithm in non-convex landscape
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework
• Robust Blind Deconvolution via Mirror Descent
• Training Generative Adversarial Networks with Adaptive Composite Gradient
• Global Optimality in Distributed Low-rank Matrix Factorization
• Multichannel Sparse Blind Deconvolution on the Sphere
• Multiplicative Weights Update as a Distributed Constrained Optimization Algorithm: Convergence to Second-order Stationary Points Almost Always
• Asymptotic Escape of Spurious Critical Points on the Low-rank Matrix Manifold
• Smooth Bilevel Programming for Sparse Regularization
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results
• Training few-shot classification via the perspective of minibatch and pretraining
• Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics
• On Assessing the Quantum Advantage for MaxCut Provided by Quantum Neural Network Ansätze
• Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience