Compute Efficiency and Serial Runtime Tradeoffs for Stochastic Momentum Methods
Not on the map. Why?
Abstract (arXiv)
Stochastic momentum methods such as heavy ball (HB), Nesterov momentum, and variants of Accelerated SGD (ASGD) [Kidambi et al., 2018] are widely used in modern training, but their stochastic benefits depend on two distinct quantities: serial runtime, the number of iterations needed to reach a target accuracy, and compute efficiency (CE), the inverse total gradient-query or FLOP cost. Larger batches reduce serial runtime without hurting CE only when the contraction gap grows linearly with batch size. We study stochastic HB and ASGD for consistent linear regression with Gaussian covariates and prove finite-dimensional, discrete-time lower bounds on their batch-size tradeoffs. Our first result shows that HB does not improve the CE frontier over SGD for arbitrary spectra; rather, it preserves SGD-level CE over a larger batch-size window, allowing larger batches to reduce serial runtime until HB reaches its deterministic accelerated scale. This window can be a factor √kappa larger than the SGD critical batch size. For ASGD, the picture is more spectrum-dependent: for rapidly decaying power-law spectra, ASGD improves small-batch CE over HB/SGD, but as batch size grows it trades this CE advantage for improved serial runtime. Synthetic linear-regression experiments verify these qualitative regimes, including near-overlap of ASGD and HB for slowly decaying spectra and the predicted CE--serial tradeoff for rapidly decaying spectra.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 34 of its 44 references that are in the map. First posted on arXiv 17 Jun 2026.
Builds on
34 of 44 references.
References · 34
- 2024The Llama 3 Herd of Modelscited by 14,715
- 2025Qwen3 Technical Reportcited by 8,820
- 2015Optimizing Neural Networks with Kronecker-factored Approximate Curvaturecited by 796
- 2026Kimi K2.5: Visual Agentic Intelligencecited by 501
- 2023Symbolic Discovery of Optimization Algorithmscited by 434
- 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
- 2018Shampoo: Preconditioned Stochastic Tensor Optimizationcited by 426
- 2018Measuring the Effects of Data Parallelism on Neural Network Trainingcited by 193
- 2024SOAP: Improving and Stabilizing Shampoo using Adamcited by 192
- 2024The Road Less Scheduledcited by 163
- 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
- 2019Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Modelcited by 117
22 more
- 2023Noise Is Not the Main Factor Behind the Gap Between SGD and Adam on Transformers, but Sign Descent Might Becited by 114
- 2022Adaptive Gradient Methods at the Edge of Stabilitycited by 101
- 2024How Does Critical Batch Size Scale in Pre-training?cited by 73
- 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
- 2024The AdEMAMix Optimizer: Better, Faster, Oldercited by 54
- 2018On the insufficiency of existing momentum schemes for Stochastic Optimizationcited by 49
- 2018Quasi-hyperbolic momentum and Adam for deep learningcited by 48
- 2025Small Batch Size Training for Language Models: When Vanilla SGD Works, and Why Gradient Accumulation Is Wastefulcited by 41
- 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 38
- 2018Aggregated Momentum: Stability Through Passive Dampingcited by 36
- 2022The Power and Limitation of Pretraining-Finetuning for Linear Regression under Covariate Shiftcited by 26
- 2025Critical Batch Size Revisited: A Simple Empirical Approach to Large-Batch Language Model Trainingcited by 23
- 2022Trajectory of Mini-Batch Momentum: Batch Size Saturation and Convergence in High Dimensionscited by 19
- 2023When and Why Momentum Accelerates SGD:An Empirical Studycited by 19
- 2023The Marginal Value of Momentum for Small Learning Rate SGDcited by 18
- 2025Dimension-adapted Momentum Outscales SGDcited by 12
- 2025Connections between Schedule-Free Optimizers, AdEMAMix, and Accelerated SGD Variantscited by 10
- 2026Momentum Further Constrains Sharpness at the Edge of Stochastic Stabilitycited by 10
- 2023Nesterov acceleration despite very noisy gradientscited by 7
- 2026Theory of Optimal Learning Rate Schedules and Scaling Laws for a Random Feature Modelcited by 7
- 2025Seesaw: Accelerating Training by Balancing Learning Rate and Batch Size Schedulingcited by 6
- 2025A Simplified Analysis of SGD for Linear Regression with Weight Averagingcited by 4
Built on by
Citing papers per year: 2026: 2.
2 papers.