Behavior of accelerated gradient methods near critical points of nonconvex functions

DOI10.1007/S10107-018-1340-YzbMATH Open1415.90092arXiv1706.07993OpenAlexW2964265968WikidataQ129037120 ScholiaQ129037120MaRDI QIDQ2425178FDOQ2425178

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

zbMATH Keywords

nonconvex optimizationaccelerated gradient methods

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Introductory lectures on convex optimization. A basic course.
• 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 (11)

• Inertial Newton algorithms avoiding strict saddle points
• A Bregman Forward-Backward Linesearch Algorithm for Nonconvex Composite Optimization: Superlinear Convergence to Nonisolated Local Minima
• Second-Order Guarantees of Distributed Gradient Algorithms
• Approximating the nearest stable discrete-time system
• Analytical convergence regions of accelerated gradient descent in nonconvex optimization under regularity condition
• Generalized Momentum-Based Methods: A Hamiltonian Perspective
• Convergence of the Momentum Method for Semialgebraic Functions with Locally Lipschitz Gradients
• 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
• Finding the Nearest Positive-Real System
• 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)