Theoretical analysis of accelerated gradient methods showing almost-sure escape from strict saddles and linear exit times, plus a subclass achieving near-optimal convergence to local minima in convex neighborhoods of nonconvex functions.
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
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.
citation-role summary
background 1
citation-polarity summary
verdicts
UNVERDICTED 3roles
background 1polarities
background 1representative citing papers
An approximate IPTR framework for linearly constrained optimization uses low-rank projector updates to cut per-iteration cost while preserving feasibility and convergence guarantees, with experiments showing 2.48x speedup.
Heavy-ball methods with random starts provably escape saddle points via a new state-space mapping that allows larger steps than plain gradient descent.
citing papers explorer
-
Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima
Theoretical analysis of accelerated gradient methods showing almost-sure escape from strict saddles and linear exit times, plus a subclass achieving near-optimal convergence to local minima in convex neighborhoods of nonconvex functions.
-
Scalable First-Order Interior Point Trust Region Algorithms for Linearly Constrained Optimization
An approximate IPTR framework for linearly constrained optimization uses low-rank projector updates to cut per-iteration cost while preserving feasibility and convergence guarantees, with experiments showing 2.48x speedup.
-
Heavy-ball Algorithms Always Escape Saddle Points
Heavy-ball methods with random starts provably escape saddle points via a new state-space mapping that allows larger steps than plain gradient descent.