Behavior of accelerated gradient methods near critical points of nonconvex functions
From MaRDI portal
Publication:2425178
DOI10.1007/S10107-018-1340-YzbMATH Open1415.90092arXiv1706.07993OpenAlexW2964265968WikidataQ129037120 ScholiaQ129037120MaRDI QIDQ2425178FDOQ2425178
Authors: Yanyan Li 
Publication date: 26 June 2019
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1706.07993
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
- Introductory lectures on convex optimization. A basic course.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- 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
- Convex optimization: algorithms and complexity
- On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
- Heavy-ball method in nonconvex optimization problems
- The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than \(1/k^2\)
- Convergence rates of inertial forward-backward algorithms
Cited In (13)
- Inertial Newton algorithms avoiding strict saddle points
- Finding the nearest positive-real system
- 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
- Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Nonconvex Stochastic Optimization: Nonasymptotic Performance Bounds and Momentum-Based Acceleration
- 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)
