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

Jun-Kun Wang, Chi-Heng Lin, Jacob Abernethy

Abstract

Incorporating "momentum" dynamics in gradient descent is a cornerstone of neural network training, empirically observed to lead to significantly faster convergence. However, theoretical guarantees explaining this acceleration have remained elusive, particularly for non-convex landscapes. This paper provides a non-asymptotic accelerated linear rate for Polyak's momentum in quadratic problems and extends this to two canonical models: one-layer wide ReLU networks and deep linear networks. By employing a modular analysis, the authors demonstrate that momentum improves the convergence rate from $(1 - \Theta(1/\kappa))^t$ to $(1 - \Theta(1/\sqrt{\kappa}))^t$, where $\kappa$ is the condition number. This work establishes a rigorous theoretical foundation for the empirical success of momentum in deep learning.

Introduction

In modern deep learning, momentum is often treated as a "free lunch." Algorithms like Polyak’s momentum (the "Heavy Ball" method) are defaults in major frameworks because they consistently speed up training. Despite this ubiquity, theoretical understanding has lagged. While momentum's benefits for simple convex quadratic problems have been known since the 1960s, proving similar acceleration for neural networks is challenging due to their complex, non-convex loss landscapes.

Previous theoretical attempts were often asymptotic—valid only as time approaches infinity—or failed to show a clear quantifiable advantage over vanilla Gradient Descent (GD). This paper bridges that gap by providing concrete, finite-time guarantees for how much faster momentum performs in over-parameterized settings.

The Modular Analysis Framework

The authors introduce a Modular Analysis framework to simplify the study of complex optimization dynamics. Rather than treating every network architecture as a unique case, they identify a shared "residual dynamic."

  1. The Meta-Theorem: The researchers proposed a general theorem for systems where the error (residual) evolves according to a specific linear recurrence influenced by momentum. If a problem can be shown to fit this form, acceleration follows automatically.
  2. Non-Asymptotic Approach: Unlike prior work relying on Gelfand’s formula, which lacks quantifiable rates for finite iterations, this paper uses a new technical approach to bound matrix-vector products. This allows for the calculation of exact speedups at any iteration $t$.

Provable Acceleration in Canonical Models

The framework is applied to two of the most popular models in optimization literature:

  • One-layer Wide ReLU Networks: Operating in the Neural Tangent Kernel (NTK) regime, where the network is wide enough that weights remain near their initialization. Previous work showed vanilla GD converges at a rate of $(1 - \Theta(1/\kappa'))^t$; this paper proves momentum achieves $(1 - \Theta(1/\sqrt{\kappa'}))^t$.
  • Deep Linear Networks: These serve as a proxy for understanding how depth affects optimization. The analysis shows that momentum achieves a rate of $(1 - \Theta(1/\sqrt{\kappa}))^t$, and notably, the width required for this acceleration is independent of the number of layers ($L$).

Empirical Evidence

To validate the theoretical findings, the authors conducted experiments on synthetic datasets. These simulations track the decay of empirical risk over time, comparing vanilla GD against momentum.

Empirical risk vs. iterations for vanilla GD and momentum.

As shown in the figure above, momentum exhibits a characteristic oscillatory behavior but maintains a significantly steeper descent on a log scale compared to vanilla GD. This visual evidence confirms the transition from a $1/\kappa$ dependency to the much faster $1/\sqrt{\kappa}$ dependency. For a condition number of $\kappa = 100$, this theoretical result implies that momentum can reach a target error in roughly 10 steps, whereas vanilla GD would require 100.

Conclusion and Limitations

This work provides a major step forward in the theoretical justification of momentum in deep learning. By leveraging over-parameterization, the authors show that the optimization landscape locally behaves like the quadratic problems Polyak originally studied.

However, limitations remain. The results currently apply to one-layer ReLU and deep linear architectures. Extending these proofs to deep non-linear networks (like ResNets) where "feature learning" occurs—and neurons change activation patterns significantly—remains an open challenge. Additionally, the analysis assumes an appropriate choice of hyperparameters, leaving the theoretical guidance for real-world parameter tuning as a subject for future research.

Summary updated

Abstract

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- Θ(\frac{1}{ κ'}))^t$ after $t$ iterations, where $κ'$ 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-Θ(\frac{1}{\sqrt{κ'}}))^t$. For the deep linear network, prior work Hu et al. 2020 showed that vanilla gradient descent has a rate of $(1-Θ(\frac{1}κ))^t$, where $κ$ is the condition number of a data matrix. Our result shows an acceleration rate $(1- Θ(\frac{1}{\sqrtκ}))^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.
BibTeX
@inproceedings{wang2021modular,
  author = {Jun-Kun Wang and Chi-Heng Lin and Jacob Abernethy},
  title = {{A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=Ep6lzouWs9},
}
Figure