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
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
Figure 1: Heatmaps of (a) the lower bound on the asymptotic divergence metric M⋆(f) from Theorem 3.25 and (b) the upper bound on the exit time metric Kexit(σ) from ( 85 ), shown as functions of the asymptotic momentum parameter β and step size h . While the scales differ across the two plots, the bounds exhibit an order-wise inverse relationship: as β and h increase, the lower bound on M⋆(f) increases, whereas the upper bound on Kexit(σ) 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 ϵ . The parameter r controls the momentum via βk=k+3−rk ; 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 ϵ . The parameter r controls the momentum via βk=k+3−rk ; r=0 corresponds to the Nesterov accelerated method ( NAG ).
Figure 4: Simulated trajectories of various accelerated gradient methods from ( G-AGM1 ) with βk=k+3−rrk on the phase retrieval problem with h=0.01/L , under the same initial unstable projections for fixed values of m , n , and ϵ . Note that r=0 corresponds to the gradient descent method.
Figure 5: Simulated trajectories of various accelerated gradient methods from ( G-AGM1 ) with βk=k+3−rrk on the phase retrieval problem with h=0.01/L , under different initial unstable projections for fixed values of m , n , and ϵ . 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 n1 , n2 , d , and ϵ . The parameter r controls the momentum via βk=k+3−rk ; 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 n1 , n2 , d , and ϵ . The parameter r controls the momentum via βk=k+3−rk ; r=0 corresponds to the Nesterov accelerated method ( NAG ).
Figure 8: Simulated trajectories of various accelerated gradient methods from ( G-AGM1 ) with βk=k+3−rrk on the low-rank matrix factorization problem with h=0.01/L , under the same initial unstable projections for fixed values of n1 , n2 , d , and ϵ . 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 x0=x−1 for fixed values of n and h . The parameter r controls the momentum via βk=k+3−rk ; r=0 corresponds to the Nesterov accelerated method ( NAG ).
Nonconvex optimization develops methods for problems whose objectives or constraints can have multiple local optima, saddle points, or nonsmooth structure.
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.
Jiseok Chae, Donghwan Kim
Natural Science Research Institute KAIST Daejeon, Republic of Korea · Department of Mathematical Sciences KAIST Daejeon, Republic of Korea
Recent work has shown that, for smooth convex optimization, plain gradient descent can be accelerated from its textbook convergence rate of O(T−1) (where T denotes the number of iterations) to O(T−log2(1+2)) using carefully designed stepsize schedules alone, without resorting to momentum or other algorithmic modifications. Despite this progress, however, little was known about lower bounds for such methods beyond the classical Ω(T−2) benchmark for general first-order methods. In this work, we present a new lower bound of Ω(T−1.9319) for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules. This result provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal O(T−2) convergence rate. The proof was developed by GPT-5.6 Sol Pro under the authors' guidance.
Jianhao Ma, Yuxin Chen
Department of Industrial Engineering, Tsinghua University · Department of Statistics and Data Science, Wharton School, University of Pennsylvania
We develop a new direct accelerated Newton method for minimizing convex functions with Lipschitz continuous Hessian. The algorithm uses only primal variables and performs just one linear solve per iteration. With a simple predetermined choice of parameters, it achieves the global convergence rate of O(1/k3) in terms of the functional residual. To the best of our knowledge, this is the first second-order method for this problem class attaining this rate while relying solely on one linear system solve per iteration (without solving auxiliary nonlinear regularized subproblems, such as cubic regularization, performing nonlinear parameter searches, or using dual extragradient corrections). Our method can be implemented in a Hessian-free way, using an inexact linear system solver, while preserving the fast global rate. We further extend our construction to arbitrary geometry through Bregman divergence, and to composite optimization problems.
Nikita Doikov
School of Operations Research and Information Engineering (ORIE), Cornell University, Ithaca, NY, USA.