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.
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