mlsanityData to 14 Oct 2026

Nesterov acceleration in benignly non-convex landscapes

arXiv 2410.08395 ↗First posted 10 Oct 2024math.OC cs.LG stat.MLcited by 7

Not on the map. Why?

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.

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

32 of 55 references.

References · 32

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
  3. 2017Empirical Analysis of the Hessian of Over-Parametrized Neural Networkscited by 290
  4. 2015A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insightscited by 206
  5. 2016Eigenvalues of the Hessian in Deep Learning: Singularity and Beyondcited by 159
  6. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  7. 2021Label Noise SGD Provably Prefers Flat Global Minimizerscited by 121
  8. 2021What Happens after SGD Reaches Zero Loss? --A Mathematical Frameworkcited by 107
  9. 2014Analysis and Design of Optimization Algorithms via Integral Quadratic Constraintscited by 105
  10. 2020On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problemscited by 80
  11. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
  12. 2019A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamicscited by 49
20 more
  1. 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 39
  2. 2019Near-Optimal Methods for Minimizing Star-Convex Functions and Beyondcited by 36
  3. 2018On exponential convergence of SGD in non-convex over-parametrized learningcited by 33
  4. 2023Aiming towards the minimizers: fast convergence of SGD for overparametrized problemscited by 22
  5. 2019Negative eigenvalues of the Hessian in deep neural networkscited by 20
  6. 2021A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossipcited by 15
  7. 2019Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descentcited by 13
  8. 2023Provable non-accelerations of the heavy-ball methodcited by 12
  9. 2021Convergence rates for the Heavy-Ball continuous dynamics for non-convex optimization, under Polyak-L ojasiewicz conditioncited by 11
  10. 2018Accelerating SGD with momentum for over-parameterized learningcited by 8
  11. 2017Behavior of Accelerated Gradient Methods Near Critical Points of Nonconvex Functionscited by 7
  12. 2017Accelerated Methods for α-Weakly-Quasi-Convex Problemscited by 7
  13. 2021Provable Convergence of Nesterov's Accelerated Gradient Method for Over-Parameterized Neural Networkscited by 7
  14. 2023Nesterov acceleration despite very noisy gradientscited by 7
  15. 2023Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimizationcited by 6
  16. 2023Fast convergence to non-isolated minima: four equivalent conditions for C2 functionscited by 6
  17. 2023Accelerated Stochastic Optimization Methods under Quasar-convexitycited by 6
  18. 2023Convergence of the momentum method for semialgebraic functions with locally Lipschitz gradientscited by 3
  19. 2024Study of the behaviour of Nesterov Accelerated Gradient in a non convex setting: the strongly quasar convex casecited by 3
  20. 2024Heavy Ball Momentum for Non-Strongly Convex Optimizationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 1; 2026: 4.

7 papers.

  1. 2026TrasMuon: Trust-Region Adaptive Scaling for Orthogonalized Momentum Optimizerscited by 6
  2. 2024Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequalitycited by 3
  3. 2026EMA-Nesterov: Stabilizing Nesterov's Lookahead for Accelerated Deep Learning Optimizationcited by 1
  4. 2024Momentum-based minimization of the Ginzburg-Landau functional on Euclidean spaces and graphscited by 0
  5. 2025Robust Gradient Descent via Heavy-Ball Momentum with Predictive Extrapolationcited by 0
  6. 2026Optimal Asymptotic Rates for (Stochastic) Gradient Descent under the Local PL-Condition: A Geometric Approachcited by 0
  7. 2026Geometric Moment Contraction for Stochastic Nesterov Accelerationcited by 0