Provable Acceleration of Wide Neural Net Training via Polyak's Momentum

Jun-Kun Wang, Jacob Abernethy

Abstract

Incorporating momentum into gradient descent is a cornerstone of modern neural network training, yet theoretical justifications for its success in non-convex settings are scarce. This paper provides a formal proof that Polyak’s momentum, when applied to over-parameterized one-layer ReLU networks, achieves a significant acceleration in convergence. We demonstrate that the training error decreases at a rate of $(1-\sqrt{\kappa_n})^t$, a square-root improvement over the $(1-\kappa_n)^t$ rate of vanilla gradient descent. This result bridges the gap between empirical success and theoretical understanding in the Neural Tangent Kernel (NTK) regime.

Introduction

Momentum-based optimizers, such as Stochastic Gradient Descent (SGD) with momentum and Adam, are the industry standard for training deep learning models. While their benefits are well-documented for convex quadratic problems, their behavior in the non-convex landscapes of neural networks has been less understood. Previous research into "wide" neural networks established that vanilla Gradient Descent (GD) can achieve zero training error, but failed to prove that momentum provides the expected acceleration. This work addresses this gap by proving that Polyak's momentum (the "Heavy Ball" method) indeed speeds up training in the over-parameterized regime.

Methodology: The NTK Regime and Polyak's Momentum

The study focuses on a one-hidden-layer ReLU network trained using a squared loss function. The analysis is conducted within the Neural Tangent Kernel (NTK) regime, where the network width $m$ is sufficiently large such that weights remain close to their initial random values throughout training.

The optimization follows Polyak’s Momentum update rule: $$w_{t+1} = w_t - \eta \nabla L(w_t) + \beta(w_t - w_{t-1})$$ where $\eta$ represents the learning rate and $\beta$ is the momentum coefficient. By analyzing the discrete-time dynamical system of the residual error, the authors show that the optimization landscape of a wide neural network behaves locally like a quadratic function.

Theoretical Insights

The $\sqrt{\kappa}$ Speedup

The primary contribution is the proof of a square-root speedup. In optimization theory, the condition number $\kappa$ determines the convergence rate. While vanilla GD requires $O(\kappa \log(1/\epsilon))$ iterations to reach an error $\epsilon$, Polyak’s momentum reduces this complexity to $O(\sqrt{\kappa} \log(1/\epsilon))$. Specifically, the error decays at a rate of $(1 - \sqrt{\eta\lambda/2})^t$, where $\lambda$ is the smallest eigenvalue of the Gram matrix.

Stability of Activation Patterns

A critical requirement for this acceleration is that the network's activation patterns (which ReLU neurons are active) remain stable. If too many neurons flip their activation states, the resulting "noise" would disrupt the momentum dynamics. The authors prove that in the over-parameterized regime, only a negligible fraction of neurons change state.

Figure 1: The relationship between the distance from initialization $\alpha$ and the fraction of neurons $\theta(\alpha)$ that change their activation state.

As shown in Figure 1, the probability $\theta(\alpha)$ of a neuron changing its activation status is extremely low when the weight displacement $\alpha$ is small. This stability allows the network to maintain a nearly quadratic landscape, enabling the momentum to function effectively.

Key Results and Empirical Validation

The theoretical findings show that momentum converges to a small, controllable error neighborhood. The size of this neighborhood is inversely proportional to the number of neurons $m$, meaning that as the network becomes wider, the final training error can be made arbitrarily small.

To validate these claims, the authors performed experiments on synthetic data (5 points, $d=10$, $m=1000$). The results confirmed that the momentum-enhanced training curve drops significantly faster than that of vanilla GD, aligning with the predicted $O(\sqrt{\kappa})$ improvement.

Conclusion and Future Work

This work provides the first theoretical guarantee of momentum-driven acceleration in over-parameterized neural networks. However, several avenues for future research remain:

  • Deep Architectures: Extending these proofs to multi-layer networks.
  • Beyond NTK: Investigating acceleration in the "feature learning" regime where weights move significantly from initialization.
  • Optimizer Comparisons: Theoretically comparing Polyak’s momentum with Nesterov’s Accelerated Gradient (NAG) and adaptive methods like Adam.

Despite these limitations, the paper establishes a foundational theoretical basis for why momentum is so effective in modern deep learning.

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. In this paper we show that Polyak's momentum, in combination with over-parameterization of the model, helps achieve faster convergence in training a one-layer ReLU network on n examples. We show specifically that gradient descent with Polyak's momentum decreases the initial training error at a rate much faster than that of vanilla gradient descent. We provide a bound for a fixed sample size n, and we show that gradient descent with Polyak's momentum converges at an accelerated rate to a small error that is controllable by the number of neurons m. Prior work (Du et al. 2019) showed that using vanilla gradient descent, and with a similar method of over-parameterization, the error decays as (1−κn)t after t iterations, where κn is a problem-specific parameter. Our result shows that with the appropriate choice of momentum parameter one has a rate of (1−κn)t. This work establishes that momentum does indeed speed up neural net training.
BibTeX
@misc{wang2021provable,
  author = {Jun-Kun Wang and Jacob Abernethy},
  title = {{Provable Acceleration of Wide Neural Net Training via Polyak's Momentum}},
  year = {2021},
}
Figure