# Nesterov acceleration in benignly non-convex landscapes

arXiv: https://arxiv.org/abs/2410.08395 · HTML: https://mlsanity.com/paper/2410.08395/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 55 references that are in the map.
- First posted on arXiv 10 Oct 2024.

## Builds on (most cited first, 30 of 32)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Empirical Analysis of the Hessian of Over-Parametrized Neural Networks](https://mlsanity.com/paper/1706.04454/) (2017)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond](https://mlsanity.com/paper/1611.07476/) (2016)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Label Noise SGD Provably Prefers Flat Global Minimizers](https://mlsanity.com/paper/2106.06530/) (2021)
- [What Happens after SGD Reaches Zero Loss? --A Mathematical Framework](https://mlsanity.com/paper/2110.06914/) (2021)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems](https://mlsanity.com/paper/2006.11144/) (2020)
- [Gradient Descent Can Take Exponential Time to Escape Saddle Points](https://mlsanity.com/paper/1705.10412/) (2017)
- [A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics](https://mlsanity.com/paper/1904.04326/) (2019)
- [Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis](https://mlsanity.com/paper/2105.01650/) (2021)
- [Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond](https://mlsanity.com/paper/1906.11985/) (2019)
- [On exponential convergence of SGD in non-convex over-parametrized learning](https://mlsanity.com/paper/1811.02564/) (2018)
- [Aiming towards the minimizers: fast convergence of SGD for overparametrized problems](https://mlsanity.com/paper/2306.02601/) (2023)
- [Negative eigenvalues of the Hessian in deep neural networks](https://mlsanity.com/paper/1902.02366/) (2019)
- [A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip](https://mlsanity.com/paper/2106.07644/) (2021)
- [Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent](https://mlsanity.com/paper/1908.07861/) (2019)
- [Provable non-accelerations of the heavy-ball method](https://mlsanity.com/paper/2307.11291/) (2023)
- [Convergence rates for the Heavy-Ball continuous dynamics for non-convex optimization, under Polyak-L ojasiewicz condition](https://mlsanity.com/paper/2107.10123/) (2021)
- [Accelerating SGD with momentum for over-parameterized learning](https://mlsanity.com/paper/1810.13395/) (2018)
- [Behavior of Accelerated Gradient Methods Near Critical Points of Nonconvex Functions](https://mlsanity.com/paper/1706.07993/) (2017)
- [Accelerated Methods for α-Weakly-Quasi-Convex Problems](https://mlsanity.com/paper/1710.00797/) (2017)
- [Provable Convergence of Nesterov's Accelerated Gradient Method for Over-Parameterized Neural Networks](https://mlsanity.com/paper/2107.01832/) (2021)
- [Nesterov acceleration despite very noisy gradients](https://mlsanity.com/paper/2302.05515/) (2023)
- [Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization](https://mlsanity.com/paper/2302.07851/) (2023)
- [Fast convergence to non-isolated minima: four equivalent conditions for C2 functions](https://mlsanity.com/paper/2303.00096/) (2023)
- [Accelerated Stochastic Optimization Methods under Quasar-convexity](https://mlsanity.com/paper/2305.04736/) (2023)
- [Convergence of the momentum method for semialgebraic functions with locally Lipschitz gradients](https://mlsanity.com/paper/2307.03331/) (2023)

## Built on by (most cited first, 7 of 7)

- [TrasMuon: Trust-Region Adaptive Scaling for Orthogonalized Momentum Optimizers](https://mlsanity.com/paper/2602.13498/) (2026)
- [Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequality](https://mlsanity.com/paper/2410.16849/) (2024)
- [EMA-Nesterov: Stabilizing Nesterov's Lookahead for Accelerated Deep Learning Optimization](https://mlsanity.com/paper/2605.25395/) (2026)
- [Momentum-based minimization of the Ginzburg-Landau functional on Euclidean spaces and graphs](https://mlsanity.com/paper/2501.00389/) (2024)
- [Robust Gradient Descent via Heavy-Ball Momentum with Predictive Extrapolation](https://mlsanity.com/paper/2512.10033/) (2025)
- [Optimal Asymptotic Rates for (Stochastic) Gradient Descent under the Local PL-Condition: A Geometric Approach](https://mlsanity.com/paper/2605.14663/) (2026)
- [Geometric Moment Contraction for Stochastic Nesterov Acceleration](https://mlsanity.com/paper/2609.31303/) (2026)

## Abstract (arXiv)

While momentum-based optimization algorithms are commonly used in the notoriously non-convex optimization problems of deep learning, their analysis has historically been restricted to the convex and strongly convex setting. In this article, we partially close this gap between theory and practice and demonstrate that virtually identical guarantees can be obtained in optimization problems with a `benign' non-convexity. We show that these weaker geometric assumptions are well justified in overparametrized deep learning, at least locally. Variations of this result are obtained for a continuous time model of Nesterov's accelerated gradient descent algorithm (NAG), the classical discrete time version of NAG, and versions of NAG with stochastic gradient estimates with purely additive noise and with noise that exhibits both additive and multiplicative scaling.