Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima

Rishabh Dixit; Mert Gurbuzbalaban; Waheed U. Bajwa

math.OCJul 13, 2023

Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima

Authors: Rishabh Dixit, Mert Gurbuzbalaban, Waheed U. Bajwa

Organizations: Department of Electrical and Computer Engineering, Rutgers University–New Brunswick, NJ 08854 USA · Departments of Electrical & Computer Engineering, Management Science and Information Systems, and Statistics, Rutgers University–New Brunswick, NJ 08854 USA · Departments of Electrical & Computer Engineering and Statistics, Rutgers University–New Brunswick, NJ 08854 USA

Abstract

This paper considers the problem of understanding the behavior of a general class of accelerated gradient methods on smooth nonconvex functions. Motivated by some recent works that have proposed effective algorithms, based on Polyak's heavy ball method and the Nesterov accelerated gradient method, to achieve convergence to a local minimum of nonconvex functions, this work proposes a broad class of Nesterov-type accelerated methods and puts forth a rigorous study of these methods encompassing the escape from saddle points and convergence to local minima through both an asymptotic and a non-asymptotic analysis. In the asymptotic regime, this paper answers an open question of whether Nesterov's accelerated gradient method (NAG) with variable momentum parameter avoids strict saddle points almost surely. This work also develops two metrics of asymptotic rates of convergence and divergence, and evaluates these two metrics for several popular standard accelerated methods such as the NAG and Nesterov's accelerated gradient with constant momentum (NCM) near strict saddle points. In the non-asymptotic regime, this work provides an analysis that leads to the "linear" exit time estimates from strict saddle neighborhoods for trajectories of these accelerated methods as well the necessary conditions for the existence of such trajectories. Finally, this work studies a sub-class of accelerated methods that can converge in convex neighborhoods of nonconvex functions with a near optimal rate to a local minimum and at the same time this sub-class offers superior saddle-escape behavior compared to that of NAG.

Figures & tables

Panel of Figure 1 — Figure 1: Heatmaps of (a) the lower bound on the asymptotic divergence metric $\mathcal{M}^{\star}(f)$ from Theorem 3.25 and (b) the upper bound on the exit time metric $K_{\text{exit}}(\sigma)$ from ( 85 ), shown as functions of the asymptotic momentum parameter $\beta$ and step size $h$ . While the scales differ across the two plots, the bounds exhibit an order-wise inverse relationship: as $\beta$ and $h$ increase, the lower bound on $\mathcal{M}^{\star}(f)$ increases, whereas the upper bound on $K_{\text{exit}}(\sigma)$ decreases.

Figure 2: Simulated trajectories of various accelerated gradient methods from the family ( G-AGM2 ) on the phase retrieval problem with

h=0.01/L

, under the same initial unstable projections for fixed values of

m

n

, and

\epsilon

. The parameter

r

controls the momentum via

\beta_{k}=\frac{k}{k+3-r}

;

r=0

corresponds to the Nesterov accelerated method ( NAG ).

Figure 3: Simulated trajectories of various accelerated gradient methods from the family ( G-AGM2 ) on the phase retrieval problem with

h=0.1/L

, under the same initial unstable projections for fixed values of

m

n

, and

\epsilon

. The parameter

r

controls the momentum via

\beta_{k}=\frac{k}{k+3-r}

;

r=0

corresponds to the Nesterov accelerated method ( NAG ).

Figure 4: Simulated trajectories of various accelerated gradient methods from ( G-AGM1 ) with

\beta_{k}=\frac{rk}{k+3-r}

on the phase retrieval problem with

h=0.01/L

, under the same initial unstable projections for fixed values of

m

n

, and

\epsilon

. Note that

r=0

corresponds to the gradient descent method.

Figure 5: Simulated trajectories of various accelerated gradient methods from ( G-AGM1 ) with

\beta_{k}=\frac{rk}{k+3-r}

on the phase retrieval problem with

h=0.01/L

, under different initial unstable projections for fixed values of

m

n

, and

\epsilon

. Note that

r=0

corresponds to the gradient descent method.

Figure 6: Simulated trajectories of various accelerated gradient methods from the family ( G-AGM2 ) on the low-rank matrix factorization problem with

h=0.01/L

, under the same initial unstable projections for fixed values of

n_{1}

n_{2}

d

, and

\epsilon

. The parameter

r

controls the momentum via

\beta_{k}=\frac{k}{k+3-r}

;

r=0

corresponds to the Nesterov accelerated method ( NAG ).

Figure 7: Simulated trajectories of various accelerated gradient methods from the family ( G-AGM2 ) on the low-rank matrix factorization problem with

h=0.01/L

, under the same initial unstable projections for fixed values of

n_{1}

n_{2}

d

, and

\epsilon

. The parameter

r

controls the momentum via

\beta_{k}=\frac{k}{k+3-r}

;

r=0

corresponds to the Nesterov accelerated method ( NAG ).

Figure 8: Simulated trajectories of various accelerated gradient methods from ( G-AGM1 ) with $\beta_{k}=\frac{rk}{k+3-r}$ on the low-rank matrix factorization problem with $h=0.01/L$ , under the same initial unstable projections for fixed values of $n_{1}$ , $n_{2}$ , $d$ , and $\epsilon$ . Note that $r=0$ corresponds to the gradient descent method.

Figure 9: Simulated trajectories of various accelerated gradient methods from the family ( G-AGM2 ) on a positive definite quadratic function, under the same initialization scheme

{\mathbf{x}}_{0}={\mathbf{x}}_{-1}

for fixed values of

n

and

h

. The parameter

r

controls the momentum via

\beta_{k}=\frac{k}{k+3-r}

;

r=0

corresponds to the Nesterov accelerated method ( NAG ).

Nonconvex Optimization

Nonconvex optimization develops methods for problems whose objectives or constraints can have multiple local optima, saddle points, or nonsmooth structure.

See all 145 papers

Understanding Schedule-Free Methods in Nonconvex Optimization: Rate Guarantees and Escaping Saddles
Jul 10, 2026Jiseok Chae, Donghwan KimLearning Rate Scheduling Optimization Convergence Analysis
Natural Science Research Institute KAIST Daejeon, Republic of Korea · Department of Mathematical Sciences KAIST Daejeon, Republic of Korea
A lower bound for stepsize-based acceleration of gradient descent
Aug 11, 2026Jianhao Ma, Yuxin ChenLearning Rate Scheduling Last-Iterate Convergence
Department of Industrial Engineering, Tsinghua University · Department of Statistics and Data Science, Wharton School, University of Pennsylvania
Primal Acceleration of Newton's Method
Aug 21, 2026Nikita DoikovSecond-Order Optimization
School of Operations Research and Information Engineering (ORIE), Cornell University, Ithaca, NY, USA.

Jul 10, 2026J/K move · Enter open · S save

Understanding Schedule-Free Methods in Nonconvex Optimization: Rate Guarantees and Escaping Saddles

Jiseok Chae, Donghwan Kim

Natural Science Research Institute KAIST Daejeon, Republic of Korea · Department of Mathematical Sciences KAIST Daejeon, Republic of Korea

Learning Rate Scheduling Optimization Convergence Analysis Nonconvex Optimization Gradient Descent Dynamics Stochastic Gradient Descent

Open paper AskPDF arXiv

Schedule-Free methods have attracted growing interest for alleviating the burden of designing and tuning a learning rate scheduler, while matching and sometimes even outperforming optimizers with tuned schedulers. Despite their strong empirical results, their convergence theory in nonconvex optimization, where modern machine learning objectives typically arise, has remained largely unexplored. In this paper, we provide worst-case analyses of Schedule-Free gradient descent and Schedule-Free stochastic gradient descent, in their standard form and without auxiliary modifications or restrictive conditions, for smooth but possibly nonconvex objectives. Based on a Lyapunov analysis derived from the continuous-time limiting ordinary differential equation associated with these methods, we show that Schedule-Free gradient descent and Schedule-Free stochastic gradient descent achieve the optimal worst-case convergence rates attainable among first-order methods. We further formulate Schedule-Free gradient descent as a nonautonomous dynamical system and prove strict-saddle avoidance under an arbitrarily small one-time perturbation. These theoretical results provide a better understanding of the strong performance that Schedule-Free methods demonstrate.

Abstract

Nonconvex Optimization

Explore similar work

Understanding Schedule-Free Methods in Nonconvex Optimization: Rate Guarantees and Escaping Saddles

A lower bound for stepsize-based acceleration of gradient descent

Primal Acceleration of Newton's Method