How to Escape Saddle Points Efficiently

Abstract

This paper shows that a perturbed form of gradient descent converges to a second-order stationary point in a number iterations which depends only poly-logarithmically on dimension (i.e., it is almost "dimension-free"). The convergence rate of this procedure matches the well-known convergence rate of gradient descent to first-order stationary points, up to log factors. When all saddle points are non-degenerate, all second-order stationary points are local minima, and our result thus shows that perturbed gradient descent can escape saddle points almost for free. Our results can be directly applied to many machine learning applications, including deep learning. As a particular concrete example of such an application, we show that our results can be used directly to establish sharp global convergence rates for matrix factorization. Our results rely on a novel characterization of the geometry around saddle points, which may be of independent interest to the non-convex optimization community.

References in corpus (7)

• Guaranteed Matrix Completion via Non-convex Factorization
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Matrix Completion has No Spurious Local Minimum
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• The Power of Normalization: Faster Evasion of Saddle Points
• Accelerated Methods for Non-Convex Optimization

Cited by in corpus (81)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Non-convex Optimization for Machine Learning
• Neuroevolution in Deep Neural Networks: Current Trends and Future Challenges
• Adaptive Federated Optimization
• Learning One-hidden-layer Neural Networks with Landscape Design
• The Non-convex Geometry of Low-rank Matrix Optimization
• Escaping Saddles with Stochastic Gradients
• The Global Landscape of Neural Networks: An Overview
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• How to Start Training: The Effect of Initialization and Architecture
• Asynchronous and Parallel Distributed Pose Graph Optimization
• Enhancing Adjoint Optimization-based Photonics Inverse Design with Explainable Machine Learning
• Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• On the different regimes of Stochastic Gradient Descent
• Inexact Non-Convex Newton-Type Methods
• Mathematical Models of Overparameterized Neural Networks
• On the diffusion approximation of nonconvex stochastic gradient descent
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization
• Understanding Deep Learning via Decision Boundary
• A Hybrid Model-based and Data-driven Approach to Spectrum Sharing in mmWave Cellular Networks
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization
• Stein Neural Sampler
• Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
• Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• Non-Convex Matrix Completion Against a Semi-Random Adversary
• Finding Local Minima via Stochastic Nested Variance Reduction
• Inexact Newton Methods for Stochastic Nonconvex Optimization with Applications to Neural Network Training
• Adam${}^{+}$: A Stochastic Method with Adaptive Variance Reduction
• Personalized incentives as feedback design in generalized Nash equilibrium problems
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Deep Neural Networks with Multi-Branch Architectures Are Less Non-Convex
• Optimization Landscape of Gradient Descent for Discrete-time Static Output Feedback
• Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
• Perturbed Proximal Descent to Escape Saddle Points for Non-convex and Non-smooth Objective Functions
• Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Stochastic Second-order Methods for Non-convex Optimization with Inexact Hessian and Gradient
• On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation
• NoncovANM: Gridless DOA Estimation for LPDF System
• Escaping Saddle Points Faster with Stochastic Momentum
• The Impact of Local Geometry and Batch Size on Stochastic Gradient Descent for Nonconvex Problems
• Stochastic Iterative Hard Thresholding for Graph-structured Sparsity Optimization
• Matrix Completion and Related Problems via Strong Duality
• Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Efficient Dictionary Learning with Gradient Descent
• Theory III: Dynamics and Generalization in Deep Networks
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• Accelerated Gradient Methods with Memory
• Towards an Understanding of Residual Networks Using Neural Tangent Hierarchy (NTH)
• A Geometric Approach of Gradient Descent Algorithms in Linear Neural Networks
• Second-order Symmetric Non-negative Latent Factor Analysis
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Ill-Posedness and Optimization Geometry for Nonlinear Neural Network Training
• An equivalence between critical points for rank constraints versus low-rank factorizations
• The loss landscape of deep linear neural networks: a second-order analysis
• Critical Point Finding with Newton-MR by Analogy to Computing Square Roots
• Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
• Are Saddles Good Enough for Deep Learning?
• A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points
• Local saddle structure in relaxed averaged alternating reflections Algorithms on phase retrieval
• The Nonconvex Geometry of Linear Inverse Problems
• Stochastic Gradient Langevin Dynamics with Variance Reduction
• WGAN with an Infinitely Wide Generator Has No Spurious Stationary Points
• BAMSProd: A Step towards Generalizing the Adaptive Optimization Methods to Deep Binary Model
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• One-dimensional System Arising in Stochastic Gradient Descent
• Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points
• Deep Neural Networks Are Congestion Games: From Loss Landscape to Wardrop Equilibrium and Beyond
• Run-and-Inspect Method for Nonconvex Optimization and Global Optimality Bounds for R-Local Minimizers
• Convergence of a Human-in-the-Loop Policy-Gradient Algorithm With Eligibility Trace Under Reward, Policy, and Advantage Feedback