Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent

Abstract

Nesterov's accelerated gradient descent (AGD), an instance of the general family of "momentum methods", provably achieves faster convergence rate than gradient descent (GD) in the convex setting. However, whether these methods are superior to GD in the nonconvex setting remains open. This paper studies a simple variant of AGD, and shows that it escapes saddle points and finds a second-order stationary point in $\tilde{O}(1/{\epsilon }^{7/4})$ iterations, faster than the $\tilde{O}(1/{\epsilon }^2)$ iterations required by GD. To the best of our knowledge, this is the first Hessian-free algorithm to find a second-order stationary point faster than GD, and also the first single-loop algorithm with a faster rate than GD even in the setting of finding a first-order stationary point. Our analysis is based on two key ideas: (1) the use of a simple Hamiltonian function, inspired by a continuous-time perspective, which AGD monotonically decreases per step even for nonconvex functions, and (2) a novel framework called improve or localize, which is useful for tracking the long-term behavior of gradient-based optimization algorithms. We believe that these techniques may deepen our understanding of both acceleration algorithms and nonconvex optimization.

References in corpus (7)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Matrix Completion has No Spurious Local Minimum
• A geometric alternative to Nesterov's accelerated gradient descent
• Accelerated Methods for Non-Convex Optimization
• Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization

Cited by in corpus (61)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• A Framework for One-Bit and Constant-Envelope Precoding over Multiuser Massive MISO Channels
• On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov acceleration
• Escaping Saddles with Stochastic Gradients
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• ReduNet: A White-box Deep Network from the Principle of Maximizing Rate Reduction
• Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies
• Hamiltonian Descent Methods
• On Symplectic Optimization
• Efficiently escaping saddle points on manifolds
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• Exponential convergence rates for Batch Normalization: The power of length-direction decoupling in non-convex optimization
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Catalyst Acceleration for Gradient-Based Non-Convex Optimization
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression
• Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Dynamic Mini-batch SGD for Elastic Distributed Training: Learning in the Limbo of Resources
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Escaping from saddle points on Riemannian manifolds
• Finding Local Minima via Stochastic Nested Variance Reduction
• Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
• On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
• Cubic Regularization with Momentum for Nonconvex Optimization
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Stochastic Subspace Descent
• Replica Exchange for Non-Convex Optimization
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimization
• Generalized Proximal Methods for Pose Graph Optimization
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• Exit Time Analysis for Approximations of Gradient Descent Trajectories Around Saddle Points
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives
• Accelerated Gradient Methods with Memory
• On the Sublinear Convergence of Randomly Perturbed Alternating Gradient Descent to Second Order Stationary Solutions
• A Diffusion Approximation Theory of Momentum SGD in Nonconvex Optimization
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• Ill-Posedness and Optimization Geometry for Nonlinear Neural Network Training
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Cutting plane methods can be extended into nonconvex optimization
• On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization
• A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees
• Heavy-ball Algorithms Always Escape Saddle Points
• The loss landscape of deep linear neural networks: a second-order analysis
• Sample Efficient Stochastic Variance-Reduced Cubic Regularization Method
• On the global convergence of randomized coordinate gradient descent for non-convex optimization
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
• Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
• Adaptive Hamiltonian Variational Integrators and Symplectic Accelerated Optimization
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
• Stochastic Approximation for Online Tensorial Independent Component Analysis
• A Deterministic Gradient-Based Approach to Avoid Saddle Points
• Improved Oracle Complexity of Variance Reduced Methods for Nonsmooth Convex Stochastic Composition Optimization
• Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained SDPs