Provable Acceleration of Neural Net Training via Polyak's Momentum

Jun-Kun Wang, Jacob D. AbernethyarXiv 2020 · arXiv · OpenReview

Abstract

Incorporating a "momentum" dynamic in gradient descent methods is widely used in neural net training as it often leads to significantly faster convergence. However, there are very few theoretical guarantees to explain this effect. This paper provides a non-asymptotic accelerated linear rate of Polyak's momentum for quadratic problems, one-layer wide ReLU networks, and deep linear networks. While prior work showed vanilla gradient descent has a convergence rate of $(1 - \Theta(1/\kappa))^t$, this work proves that Polyak's momentum achieves a rate of $(1 - \Theta(1/\sqrt{\kappa}))^t$. These results are obtained from a modular analysis framework that establishes momentum's ability to speed up neural net training.

Introduction

Polyak’s Momentum, often referred to as the "Heavy Ball" method, is a cornerstone of modern deep learning optimization. Despite being the default choice in major frameworks like PyTorch and TensorFlow, a rigorous theoretical understanding of its performance in neural networks has remained elusive. While its benefits for simple convex quadratic problems have been known since the 1960s, extending these guarantees to the non-convex, non-quadratic landscape of neural networks has proven difficult.

This research, presented at ICML 2021, bridges the gap between empirical observation and mathematical proof. It provides the first non-asymptotic framework to demonstrate that momentum achieves a "square-root" speedup over vanilla gradient descent for two critical architectures: wide ReLU networks and deep linear networks.

The Challenge of Acceleration

In optimization theory, "acceleration" typically refers to improving the convergence rate's dependency on the condition number $\kappa$ to its square root, $\sqrt{\kappa}$. For a poorly conditioned problem, this improvement is transformative—potentially reducing the number of iterations required by orders of magnitude.

Prior to this work, most momentum guarantees were either asymptotic (valid only as time approaches infinity) or restricted to highly simplified cases. For neural networks, previous benchmarks for vanilla gradient descent showed error decay rates of $(1 - \Theta(1/\kappa))^t$. Proving that momentum could achieve $(1 - \Theta(1/\sqrt{\kappa}))^t$ in these complex settings was a significant open challenge.

Methodology: A Modular Framework

The authors introduce a Modular Analysis framework designed to generalize acceleration proofs. Rather than deriving proofs for each architecture from scratch, they propose a "Meta Theorem" based on two components:

  1. The Residual Dynamic: Many optimization processes can be modeled as a recursive linear system with an added "perturbation" or error term ($\phi_t$).
  2. The Meta Theorem: If the error term $\phi_t$ remains sufficiently small throughout the training process, the Meta Theorem guarantees an accelerated convergence rate.

By applying this framework, the researchers demonstrated that strongly convex quadratics, one-layer wide ReLU networks (within the Neural Tangent Kernel regime), and deep linear networks all satisfy the conditions for acceleration.

Key Insights

  • The $\sqrt{\kappa}$ Speedup: The core contribution is the formal proof that momentum shifts the error decay from a linear dependency on $\kappa$ to a square-root dependency.
  • Over-parameterization as a Tool: In the case of ReLU networks, the proof relies on the "width" of the network. Sufficient width ensures that activation patterns remain stable during training, allowing the non-linear system to behave linearly enough for momentum to take effect.
  • Depth Independence: For deep linear networks, the analysis shows that the width required for acceleration does not need to scale with the depth of the network, suggesting that momentum is robust against depth-related issues.

Empirical Validation

To support their theoretical findings, the authors conducted proof-of-concept experiments using synthetic data. These experiments compared vanilla gradient descent against Polyak's momentum in training ReLU and deep linear networks.

Comparison of convergence rates between vanilla gradient descent and Polyak's momentum.

As shown in the figure above, the empirical risk for the momentum-based optimizer drops much more rapidly than that of vanilla gradient descent. While vanilla GD reaches an empirical risk of approximately $10^{-6}$ after 50 iterations, momentum reaches $10^{-12}$, confirming the theoretical prediction of accelerated convergence.

Limitations and Future Directions

While this work provides a major step forward, several areas remain for future exploration:

  • The NTK Regime: The ReLU network analysis assumes a "lazy training" regime where the network is extremely wide. Real-world networks may operate outside these bounds.
  • Loss Functions: The current proofs are tailored to squared loss; extending this to cross-entropy loss is a natural next step.
  • Stochastic Optimization: The focus here is on deterministic Gradient Descent. Providing a non-asymptotic acceleration proof for Stochastic Gradient Descent (SGD) in these settings remains a significant open problem.

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- \Theta(\frac{1}{ \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(\frac{1}{\sqrt{\kappa'}}))^t$. For the deep linear network, prior work Hu et al. 2020 showed that vanilla gradient descent has a rate of $(1-\Theta(\frac{1}{\kappa}))^t$, where $\kappa$ is the condition number of a data matrix. Our result shows an acceleration rate $(1- \Theta(\frac{1}{\sqrt{\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.
BibTeX
@misc{wang2020provable,
  author = {Jun-Kun Wang and Jacob D. Abernethy},
  title = {{Provable Acceleration of Neural Net Training via Polyak's Momentum}},
  year = {2020},
  eprint = {2010.01618},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.01618},
}
Figure