Behavior of accelerated gradient methods near critical points of nonconvex functions
From MaRDI portal
Publication:2425178
Abstract: We examine the behavior of accelerated gradient methods in smooth nonconvex unconstrained optimization, focusing in particular on their behavior near strict saddle points. Accelerated methods are iterative methods that typically step along a direction that is a linear combination of the previous step and the gradient of the function evaluated at a point at or near the current iterate. (The previous step encodes gradient information from earlier stages in the iterative process.) We show by means of the stable manifold theorem that the heavy-ball method method is unlikely to converge to strict saddle points, which are points at which the gradient of the objective is zero but the Hessian has at least one negative eigenvalue. We then examine the behavior of the heavy-ball method and other accelerated gradient methods in the vicinity of a strict saddle point of a nonconvex quadratic function, showing that both methods can diverge from this point more rapidly than the steepest-descent method.
Recommendations
- Accelerated methods for nonconvex optimization
- A Newton-based method for nonconvex optimization with fast evasion of saddle points
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- Extending the Step-Size Restriction for Gradient Descent to Avoid Strict Saddle Points
- Convergence guarantees for a class of non-convex and non-smooth optimization problems
Cites work
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- Convergence rates of inertial forward-backward algorithms
- Convex optimization: algorithms and complexity
- Heavy-ball method in nonconvex optimization problems
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 3980052 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
- THE HEAVY BALL WITH FRICTION METHOD, I. THE CONTINUOUS DYNAMICAL SYSTEM: GLOBAL EXPLORATION OF THE LOCAL MINIMA OF A REAL-VALUED FUNCTION BY ASYMPTOTIC ANALYSIS OF A DISSIPATIVE DYNAMICAL SYSTEM
- The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k^2
Cited in
(18)- Analytical convergence regions of accelerated gradient descent in nonconvex optimization under regularity condition
- Approximating the nearest stable discrete-time system
- A Newton-based method for nonconvex optimization with fast evasion of saddle points
- Finding the nearest positive-real system
- Analysis of asymptotic escape of strict saddle sets in manifold optimization
- Global convergence of stochastic gradient Hamiltonian Monte Carlo for nonconvex stochastic optimization: nonasymptotic performance bounds and momentum-based acceleration
- Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
- Second-order guarantees of distributed gradient algorithms
- A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
- Generalized momentum-based methods: a Hamiltonian perspective
- Convergence of the Momentum Method for Semialgebraic Functions with Locally Lipschitz Gradients
- Switched diffusion processes for non-convex optimization and saddle points search
- Inertial Newton algorithms avoiding strict saddle points
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- Gradient descent provably escapes saddle points in the training of shallow ReLU networks
- Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians
- Heavy-ball differential equation achieves \(O(\varepsilon^{-7/4})\) convergence for nonconvex functions
- Gradient descent in phase retrieval
This page was built for publication: Behavior of accelerated gradient methods near critical points of nonconvex functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2425178)
