# Compute Efficiency and Serial Runtime Tradeoffs for Stochastic Momentum Methods

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

## 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 (most cited first, 30 of 34)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [Kimi K2.5: Visual Agentic Intelligence](https://mlsanity.com/paper/2602.02276/) (2026)
- [Symbolic Discovery of Optimization Algorithms](https://mlsanity.com/paper/2302.06675/) (2023)
- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [Shampoo: Preconditioned Stochastic Tensor Optimization](https://mlsanity.com/paper/1802.09568/) (2018)
- [Measuring the Effects of Data Parallelism on Neural Network Training](https://mlsanity.com/paper/1811.03600/) (2018)
- [SOAP: Improving and Stabilizing Shampoo using Adam](https://mlsanity.com/paper/2409.11321/) (2024)
- [The Road Less Scheduled](https://mlsanity.com/paper/2405.15682/) (2024)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model](https://mlsanity.com/paper/1907.04164/) (2019)
- [Noise Is Not the Main Factor Behind the Gap Between SGD and Adam on Transformers, but Sign Descent Might Be](https://mlsanity.com/paper/2304.13960/) (2023)
- [Adaptive Gradient Methods at the Edge of Stability](https://mlsanity.com/paper/2207.14484/) (2022)
- [How Does Critical Batch Size Scale in Pre-training?](https://mlsanity.com/paper/2410.21676/) (2024)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [The AdEMAMix Optimizer: Better, Faster, Older](https://mlsanity.com/paper/2409.03137/) (2024)
- [On the insufficiency of existing momentum schemes for Stochastic Optimization](https://mlsanity.com/paper/1803.05591/) (2018)
- [Quasi-hyperbolic momentum and Adam for deep learning](https://mlsanity.com/paper/1810.06801/) (2018)
- [Small Batch Size Training for Language Models: When Vanilla SGD Works, and Why Gradient Accumulation Is Wasteful](https://mlsanity.com/paper/2507.07101/) (2025)
- [Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression](https://mlsanity.com/paper/2110.06198/) (2021)
- [Aggregated Momentum: Stability Through Passive Damping](https://mlsanity.com/paper/1804.00325/) (2018)
- [The Power and Limitation of Pretraining-Finetuning for Linear Regression under Covariate Shift](https://mlsanity.com/paper/2208.01857/) (2022)
- [Critical Batch Size Revisited: A Simple Empirical Approach to Large-Batch Language Model Training](https://mlsanity.com/paper/2505.23971/) (2025)
- [Trajectory of Mini-Batch Momentum: Batch Size Saturation and Convergence in High Dimensions](https://mlsanity.com/paper/2206.01029/) (2022)
- [When and Why Momentum Accelerates SGD:An Empirical Study](https://mlsanity.com/paper/2306.09000/) (2023)
- [The Marginal Value of Momentum for Small Learning Rate SGD](https://mlsanity.com/paper/2307.15196/) (2023)
- [Dimension-adapted Momentum Outscales SGD](https://mlsanity.com/paper/2505.16098/) (2025)
- [Connections between Schedule-Free Optimizers, AdEMAMix, and Accelerated SGD Variants](https://mlsanity.com/paper/2502.02431/) (2025)
- [Momentum Further Constrains Sharpness at the Edge of Stochastic Stability](https://mlsanity.com/paper/2604.14108/) (2026)

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

- [A Defense of the Quadratic Model](https://mlsanity.com/paper/2607.21716/) (2026)
- [Momentum in large-batch training: Polyak enlarges the critical batch size, Nesterov improves data efficiency](https://mlsanity.com/paper/2609.02728/) (2026)

## 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.