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