# A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Oct 2020.

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

- [Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization](https://mlsanity.com/paper/2205.10217/) (2022)
- [Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Lojasiewicz Functions when the Non-Convexity is Averaged-Out](https://mlsanity.com/paper/2206.11872/) (2022)
- [Towards Understanding GD with Hard and Conjugate Pseudo-labels for Test-Time Adaptation](https://mlsanity.com/paper/2210.10019/) (2022)
- [Accelerated Convergence of Stochastic Heavy Ball Method under Anisotropic Gradient Noise](https://mlsanity.com/paper/2312.14567/) (2023)
- [Deep Linear Networks can Benignly Overfit when Shallow Ones Do](https://mlsanity.com/paper/2209.09315/) (2022)
- [Provable Convergence of Nesterov's Accelerated Gradient Method for Over-Parameterized Neural Networks](https://mlsanity.com/paper/2107.01832/) (2021)
- [Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time](https://mlsanity.com/paper/2207.02189/) (2022)
- [Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization](https://mlsanity.com/paper/2302.07851/) (2023)
- [A Convergence Analysis of Nesterov's Accelerated Gradient Method in Training Deep Linear Neural Networks](https://mlsanity.com/paper/2204.08306/) (2022)
- [A Nonstochastic Control Approach to Optimization](https://mlsanity.com/paper/2301.07902/) (2023)
- [Mean-field analysis for heavy ball methods: Dropout-stability, connectivity, and global convergence](https://mlsanity.com/paper/2210.06819/) (2022)
- [Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks](https://mlsanity.com/paper/2410.09640/) (2024)
- [Polyak's Heavy Ball Method Achieves Accelerated Local Rate of Convergence under Polyak-Lojasiewicz Inequality](https://mlsanity.com/paper/2410.16849/) (2024)
- [FedFOR: Stateless Heterogeneous Federated Learning with First-Order Regularization](https://mlsanity.com/paper/2209.10537/) (2022)
- [(Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentum](https://mlsanity.com/paper/2401.06738/) (2024)
- [AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learning](https://mlsanity.com/paper/2604.09437/) (2026)
- [Provable Acceleration of Nesterov's Accelerated Gradient Method over Heavy Ball Method in Training Over-Parameterized Neural Networks](https://mlsanity.com/paper/2208.03941/) (2022)
- [On the Convergence of Federated Averaging under Partial Participation for Over-parameterized Neural Networks](https://mlsanity.com/paper/2310.05495/) (2023)
- [Training-Loss Guarantees for Muon with Finite-Step Newton--Schulz Orthogonalization](https://mlsanity.com/paper/2610.03306/) (2026)

## Abstract (arXiv)

Incorporating a so-called "momentum" dynamic in gradient descent methods is widely used in neural net training as it has been broadly observed that, at least empirically, it often leads to significantly faster convergence. At the same time, there are very few theoretical guarantees in the literature to explain this apparent acceleration effect. Even for the classical strongly convex quadratic problems, several existing results only show Polyak's momentum has an accelerated linear rate asymptotically. In this paper, we first revisit the quadratic problems and show a non-asymptotic accelerated linear rate of Polyak's momentum. Then, we provably show that Polyak's momentum achieves acceleration for training a one-layer wide ReLU network and a deep linear network, which are perhaps the two most popular canonical models for studying optimization and deep learning in the literature. Prior work Du at al. 2019 and Wu et al. 2019 showed that using vanilla gradient descent, and with an use of over-parameterization, the error decays as (1- Theta(frac1 kappa'))t after t iterations, where kappa' is the condition number of a Gram Matrix. Our result shows that with the appropriate choice of parameters Polyak's momentum has a rate of (1-Theta(frac1√kappa'))t. For the deep linear network, prior work Hu et al. 2020 showed that vanilla gradient descent has a rate of (1-Theta(frac1kappa))t, where kappa is the condition number of a data matrix. Our result shows an acceleration rate (1- Theta(frac1√kappa))t is achievable by Polyak's momentum. All the results in this work are obtained from a modular analysis, which can be of independent interest. This work establishes that momentum does indeed speed up neural net training.