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 (2)

• Accelerated Methods for Non-Convex Optimization
• Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality

Cited by in corpus (10)

• Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression
• Dynamic Mini-batch SGD for Elastic Distributed Training: Learning in the Limbo of Resources
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Escaping from saddle points on Riemannian manifolds
• Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
• Stochastic Subspace Descent
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Ill-Posedness and Optimization Geometry for Nonlinear Neural Network Training
• Heavy-ball Algorithms Always Escape Saddle Points