Nesterov Momentum Escapes AI Training's Worst Traps Almost Every Time
A new analysis settles whether momentum-based optimizers can get stuck at saddle points, and designs a variant that escapes faster without hurting convergence.
- Paper proves Nesterov's accelerated gradient with variable momentum avoids strict saddle points almost surely in non-convex optimization.
- Introduces a general family of Nesterov-type methods covering NAG, constant-momentum Nesterov, and gradient descent as special cases.
- Defines asymptotic divergence and exit-time metrics quantifying how fast each method escapes saddle neighborhoods.
- Proves linear-rate escape, O(log 1/ε) iterations, from ε-neighborhoods of strict saddles.
- Tunable momentum schedule β_k = k/(k+3-r) beats classical NAG on phase retrieval and matrix factorization.
- Published in Foundations of Computational Mathematics; preprint on arXiv.
Nesterov Momentum Escapes Strict Saddles Almost Surely
Standard Nesterov accelerated gradient avoids convergence to strict saddle points from almost every initialization, according to a journal article by Rishabh Dixit, Mert Gürbüzbalaban, and Waheed U. Bajwa in Foundations of Computational Mathematics. The analysis also introduces a tunable momentum schedule that can leave saddle neighborhoods faster while preserving local convergence guarantees near strongly convex minima.
Why strict saddles cause long stalls
A strict saddle is a stationary point where the gradient is zero and the Hessian has at least one negative eigenvalue. That negative curvature identifies a descent direction, but a first-order optimizer close to the saddle sees only a small gradient. Its iterates can therefore move so slowly that the run appears to have converged.
Earlier work established that gradient descent avoids strict saddles from almost every random initialization, yet it can remain nearby for many iterations. Jin et al. later showed that a perturbed accelerated method could find an approximate second-order stationary point in roughly O(1/ε7/4) iterations, up to logarithmic factors, compared with O(1/ε2) for gradient descent. That algorithm injected perturbations, leaving the behavior of the classical time-varying Nesterov method unresolved.
What the proof settles
The new analysis covers Nesterov accelerated gradient with the classical coefficient βk = k/(k+3). Under the paper’s smoothness and step-size assumptions, the iterates converge to a strict saddle only from a measure-zero set of initial conditions. An initialization drawn from a continuous distribution therefore avoids such convergence with probability one.
This story is for Pro members
You've reached the end of the free preview. Upgrade to AlphaSignal Pro to read the full article - and everything else behind the paywall.
Comments
