mlsanityData to 7 Oct 2026

Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation

arXiv 2404.02378 ↗First posted 3 Apr 2024math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We prove new convergence rates for a generalized version of stochastic Nesterov acceleration under interpolation conditions. Unlike previous analyses, our approach accelerates any stochastic gradient method which makes sufficient progress in expectation. The proof, which proceeds using the estimating sequences framework, applies to both convex and strongly convex functions and is easily specialized to accelerated SGD under the strong growth condition. In this special case, our analysis reduces the dependence on the strong growth constant from ρ to √ρ as compared to prior work. This improvement is comparable to a square-root of the condition number in the worst case and address criticism that guarantees for stochastic acceleration could be worse than those for SGD.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 29 of its 48 references that are in the map. First posted on arXiv 3 Apr 2024.

Builds on

29 of 48 references.

References · 29

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  2. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  3. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  4. 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
  5. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
  6. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  7. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  8. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  9. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 130
  10. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  11. 2018Does data interpolation contradict statistical optimality?cited by 95
  12. 2018Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?cited by 87
17 more
  1. 2018Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivitycited by 61
  2. 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
  3. 2018On the Ineffectiveness of Variance Reduced Optimization for Deep Learningcited by 48
  4. 2019Training Neural Networks for and by Interpolationcited by 45
  5. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 41
  6. 2018On exponential convergence of SGD in non-convex over-parametrized learningcited by 33
  7. 2020On the Convergence of Nesterov's Accelerated Gradient Method in Stochastic Settingscited by 27
  8. 2021Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsizecited by 22
  9. 2013Gradient methods for convex minimization: better rates under weaker conditionscited by 21
  10. 2018On Acceleration with Noise-Corrupted Gradientscited by 20
  11. 2019Fast and Furious Convergence: Stochastic Second Order Methods under Interpolationcited by 18
  12. 2021Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descentcited by 16
  13. 2020Adaptive Gradient Methods Converge Faster with Over-Parameterization (but you should do a line-search)cited by 15
  14. 2021A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossipcited by 15
  15. 2020Convergence Analysis of Accelerated Stochastic Gradient Descent under the Growth Conditioncited by 7
  16. 2020Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditionscited by 2
  17. 2022Accelerated Convex Optimization with Stochastic Gradients: Generalizing the Strong-Growth Conditioncited by 1

Built on by

Not cited yet.