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
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 3980052 (Why is no real title available?)
- 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
- 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
(15)- Analysis of asymptotic escape of strict saddle sets in manifold optimization
- Inertial Newton algorithms avoiding strict saddle points
- Global convergence of stochastic gradient Hamiltonian Monte Carlo for nonconvex stochastic optimization: nonasymptotic performance bounds and momentum-based acceleration
- Finding the nearest positive-real system
- Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
- A Newton-based method for nonconvex optimization with fast evasion of saddle points
- Approximating the nearest stable discrete-time system
- Analytical convergence regions of accelerated gradient descent in nonconvex optimization under regularity condition
- A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
- Convergence of the Momentum Method for Semialgebraic Functions with Locally Lipschitz Gradients
- Switched diffusion processes for non-convex optimization and saddle points search
- Second-order guarantees of distributed gradient algorithms
- Gradient descent provably escapes saddle points in the training of shallow ReLU networks
- Generalized momentum-based methods: a Hamiltonian perspective
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
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)
