mlsanityData to 14 Oct 2026

SGD with memory: fundamental properties and stochastic acceleration

arXiv 2410.04228 ↗First posted 5 Oct 2024cs.LG math.OCcited by 2

Not on the map. Why?

Abstract (arXiv)

An important open problem is the theoretically feasible acceleration of mini-batch SGD-type algorithms on quadratic problems with power-law spectrum. In the non-stochastic setting, the optimal exponent xi in the loss convergence Lt~ CLt-xi is double that in plain GD and is achievable using Heavy Ball (HB) with a suitable schedule; this no longer works in the presence of mini-batch noise. We address this challenge by considering first-order methods with an arbitrary fixed number M of auxiliary velocity vectors (*memory-M algorithms*). We first prove an equivalence between two forms of such algorithms and describe them in terms of suitable characteristic polynomials. Then we develop a general expansion of the loss in terms of signal and noise propagators. Using it, we show that losses of stationary stable memory-M algorithms always retain the exponent xi of plain GD, but can have different constants CL depending on their effective learning rate that generalizes that of HB. We prove that in memory-1 algorithms we can make CL arbitrarily small while maintaining stability. As a consequence, we propose a memory-1 algorithm with a time-dependent schedule that we show heuristically and experimentally to improve the exponent xi of plain SGD.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 33 of its 52 references that are in the map. First posted on arXiv 5 Oct 2024.

Builds on

33 of 52 references.

References · 33

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 738
  3. 2018On Lazy Training in Differentiable Programmingcited by 675
  4. 2021Explaining Neural Scaling Lawscited by 363
  5. 2020The large learning rate phase of deep learning: the catapult mechanismcited by 216
  6. 2020Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the Neural Tangent Kernelcited by 187
  7. 2020Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networkscited by 166
  8. 2020Finite Versus Infinite Neural Networks: an Empirical Studycited by 157
  9. 2020Frequency Bias in Neural Networks for Input of Non-Uniform Densitycited by 140
  10. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
  11. 2021Neural Networks as Kernel Learners: The Silent Alignment Effectcited by 106
  12. 2021Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regimecited by 96
21 more
  1. 2022More Than a Toy: Random Matrix Models Predict How Real-World Neural Representations Generalizecited by 91
  2. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  3. 2019A Fine-Grained Spectral Perspective on Neural Networkscited by 68
  4. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  5. 2021What can linearized neural networks actually say about generalization?cited by 49
  6. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 42
  7. 2020Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Modelcited by 39
  8. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 38
  9. 2021SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticalitycited by 35
  10. 2021Fast Adaptation with Linearized Neural Networkscited by 32
  11. 2021Approximation and Learning with Deep Convolutional Models: a Kernel Perspectivecited by 31
  12. 2022Homogenization of SGD in high-dimensions: Exact dynamics and generalization propertiescited by 27
  13. 2023Hitting the High-Dimensional Notes: An ODE for SGD learning dynamics on GLMs and multi-index modelscited by 26
  14. 2015From Averaging to Acceleration, There is Only a Step-sizecited by 24
  15. 2022Trajectory of Mini-Batch Momentum: Batch Size Saturation and Convergence in High Dimensionscited by 19
  16. 2021Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Modelscited by 16
  17. 2019Training Neural Networks as Learning Data-adaptive Kernels: Provable Representation and Approximation Benefitscited by 13
  18. 2022A view of mini-batch SGD via generating functions: conditions of convergence, phase transitions, benefit from negative momentacited by 11
  19. 2022Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditionscited by 9
  20. 2022Accelerated SGD for Non-Strongly-Convex Least Squarescited by 9
  21. 2017Stochastic Composite Least-Squares Regression with convergence rate O(1/n)cited by 7

Built on by

Cited by year

Citing papers per year: 2025: 2.

2 papers.

  1. 2025On the Effectiveness of the z-Transform Method in Quadratic Optimizationcited by 3
  2. 2025Corner Gradient Descentcited by 1