# On the insufficiency of existing momentum schemes for Stochastic Optimization

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Mar 2018.

## Built on by (most cited first, 30 of 49)

- [Temporal Efficient Training of Spiking Neural Network via Gradient Re-weighting](https://mlsanity.com/paper/2202.11946/) (2022)
- [The AdEMAMix Optimizer: Better, Faster, Older](https://mlsanity.com/paper/2409.03137/) (2024)
- [Small Batch Size Training for Language Models: When Vanilla SGD Works, and Why Gradient Accumulation Is Wasteful](https://mlsanity.com/paper/2507.07101/) (2025)
- [Towards understanding how momentum improves generalization in deep learning](https://mlsanity.com/paper/2207.05931/) (2022)
- [Does SGD really happen in tiny subspaces?](https://mlsanity.com/paper/2405.16002/) (2024)
- [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)
- [Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models](https://mlsanity.com/paper/2106.03696/) (2021)
- [On the Role of Server Momentum in Federated Learning](https://mlsanity.com/paper/2312.12670/) (2023)
- [First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities](https://mlsanity.com/paper/2305.15938/) (2023)
- [A Defense of the Quadratic Model](https://mlsanity.com/paper/2607.21716/) (2026)
- [On the fast convergence of minibatch heavy ball momentum](https://mlsanity.com/paper/2206.07553/) (2022)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [A view of mini-batch SGD via generating functions: conditions of convergence, phase transitions, benefit from negative momenta](https://mlsanity.com/paper/2206.11124/) (2022)
- [On the Last Iterate Convergence of Momentum Methods](https://mlsanity.com/paper/2102.07002/) (2021)
- [Momentum Further Constrains Sharpness at the Edge of Stochastic Stability](https://mlsanity.com/paper/2604.14108/) (2026)
- [Acceleration of stochastic gradient descent with momentum by averaging: finite-sample rates and asymptotic normality](https://mlsanity.com/paper/2305.17665/) (2023)
- [Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noise](https://mlsanity.com/paper/2312.14567/) (2023)
- [Leveraging Continuous Time to Understand Momentum When Training Diagonal Linear Networks](https://mlsanity.com/paper/2403.05293/) (2024)
- [Escaping Saddle Points Faster with Stochastic Momentum](https://mlsanity.com/paper/2106.02985/) (2021)
- [Handling Data Heterogeneity via Architectural Design for Federated Visual Recognition](https://mlsanity.com/paper/2310.15165/) (2023)
- [On the Performance Analysis of Momentum Method: A Frequency Domain Perspective](https://mlsanity.com/paper/2411.19671/) (2024)
- [Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum](https://mlsanity.com/paper/2111.06171/) (2021)
- [Analytical Study of Momentum-Based Acceleration Methods in Paradigmatic High-Dimensional Non-Convex Problems](https://mlsanity.com/paper/2102.11755/) (2021)
- [Feedback Gradient Descent: Efficient and Stable Optimization with Orthogonality for DNNs](https://mlsanity.com/paper/2205.08385/) (2022)
- [Flatter, faster: scaling momentum for optimal speedup of SGD](https://mlsanity.com/paper/2210.16400/) (2022)
- [Projected Forward Gradient-Guided Frank-Wolfe Algorithm via Variance Reduction](https://mlsanity.com/paper/2403.12511/) (2024)
- [StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models](https://mlsanity.com/paper/2604.15416/) (2026)
- [From Optimization to Control: Quasi Policy Iteration](https://mlsanity.com/paper/2311.11166/) (2023)

## Abstract (arXiv)

Momentum based stochastic gradient methods such as heavy ball (HB) and Nesterov's accelerated gradient descent (NAG) method are widely used in practice for training deep networks and other supervised learning models, as they often provide significant improvements over stochastic gradient descent (SGD). Rigorously speaking, "fast gradient" methods have provable improvements over gradient descent only for the deterministic case, where the gradients are exact. In the stochastic case, the popular explanations for their wide applicability is that when these fast gradient methods are applied in the stochastic case, they partially mimic their exact gradient counterparts, resulting in some practical gain. This work provides a counterpoint to this belief by proving that there exist simple problem instances where these methods cannot outperform SGD despite the best setting of its parameters. These negative problem instances are, in an informal sense, generic; they do not look like carefully constructed pathological instances. These results suggest (along with empirical evidence) that HB or NAG's practical performance gains are a by-product of mini-batching. Furthermore, this work provides a viable (and provable) alternative, which, on the same set of problem instances, significantly improves over HB, NAG, and SGD's performance. This algorithm, referred to as Accelerated Stochastic Gradient Descent (ASGD), is a simple to implement stochastic algorithm, based on a relatively less popular variant of Nesterov's Acceleration. Extensive empirical results in this paper show that ASGD has performance gains over HB, NAG, and SGD.