Introduction
In deep learning, Polyak’s momentum (often referred to as the "Heavy Ball" method) is the bread and butter of optimization, serving as a default choice in frameworks like PyTorch and TensorFlow. Empirically, it is well-known to speed up training. Theoretically, however, the evidence has been surprisingly thin.
Most existing proofs for momentum only apply to simple convex quadratic problems and often only provide "asymptotic" results—describing what happens as iterations approach infinity rather than providing a clear guarantee for a finite number of steps. Furthermore, extending these proofs to the non-convex, non-differentiable landscapes of neural networks (like those using ReLU activations) has been a major mathematical hurdle.
This paper provides the first theoretical proof that Polyak’s momentum actually accelerates the training of neural networks in a quantifiable, finite-time way. By developing a novel "modular analysis" framework, the authors demonstrate that momentum achieves a non-asymptotic accelerated linear convergence rate for wide one-layer ReLU networks and deep linear networks, significantly outperforming vanilla gradient descent.
Methods: A Modular Analysis Framework
Instead of proving acceleration for each model from scratch, the authors introduce a Modular Analysis framework. They identify a common "residual dynamic"—a mathematical pattern in how the error evolves over time—that appears across different optimization problems.
- The Meta Theorem: The authors propose a "Meta Theorem of Acceleration." If an optimization process's error follows a specific recursive form, it is guaranteed to converge at an accelerated rate.
- Bounding Matrix Powers: A standard tool for analyzing these recursions is Gelfand’s formula, but it fails to provide non-asymptotic rates. The authors develop a new technical result to bound matrix-vector products more tightly, allowing for quantifiable bounds at every iteration $t$.
- Realization: They then show that four major problems—strongly convex quadratics, general smooth functions (locally), wide one-layer ReLU networks, and deep linear networks—all "realize" this specific dynamic under certain conditions, such as over-parameterization.
Experimental Setup
As a theoretical paper, the work does not rely on standard image or text datasets like ImageNet or GLUE. Instead, it utilizes:
- Synthetic Data Matrices: For the deep linear network analysis, the authors assume a data matrix $X$ and label matrix $Y$ where a perfect solution $W^*$ exists.
- Random Initialization: They utilize standard initialization schemes (Gaussian for ReLU, Orthogonal for deep linear) to satisfy the conditions required for the Neural Tangent Kernel (NTK) regime.
Key Insights
- The Power of the Square Root: The core breakthrough is proving the shift from a convergence rate of $(1 - \Theta(1/\kappa))$ in vanilla gradient descent to $(1 - \Theta(1/\sqrt{\kappa}))$ with momentum, where $\kappa$ is the condition number. For poorly conditioned problems (high $\kappa$), this square root represents a massive reduction in the required number of iterations.
- Over-parameterization as an Enabler: The paper highlights that network "width" isn't just beneficial for generalization; it allows the optimization landscape to stay close enough to the initial Gram matrix for momentum's acceleration to take effect.
- Decoupling Dynamics from Models: By creating a modular framework, the authors show that acceleration is a property of the momentum dynamic itself when applied to systems that behave linearly near the starting point.
Key Results
The theoretical findings are backed by both rigorous proofs and toy empirical verifications.
- Wide ReLU Networks: For a one-layer ReLU network with $m$ neurons, if $m$ is sufficiently large (over-parameterized), Polyak’s momentum achieves an accelerated rate of $(1 - \Theta(1/\sqrt{\hat{\kappa}}))^t$. This is the first such result for ReLU networks.
- Deep Linear Networks: The authors prove that for a network of depth $L$, momentum achieves acceleration $(1 - \Theta(1/\sqrt{\kappa}))^t$. Crucially, they show that the required width $m$ for this to hold is independent of the depth $L$, suggesting that depth does not inherently hinder momentum's ability to accelerate.
- Non-Asymptotic Quadratics: They provide a new, cleaner proof for the classical quadratic case that gives a concrete bound for any finite iteration $t$, improving upon the "eventual" guarantees of previous literature.
Limitations and Future Work
While a significant theoretical step forward, the paper notes several limitations:
- The "NTK" Regime: The analysis for ReLU networks relies on the "wide" regime where weights don't move very far from initialization. While standard in theory, it doesn't fully capture how smaller, practical networks learn features.
- One-Layer ReLU: The ReLU acceleration proof is limited to one-hidden-layer networks. Extending this to deep ReLU networks remains a significant challenge due to the increasing complexity of activation patterns.
- Local vs. Global: For general smooth functions, the acceleration is only proven to be "local" (when already somewhat close to the solution), rather than global.
- Stochastic Settings: This paper focuses on deterministic gradient descent. A natural next step is extending this modular analysis to Stochastic Gradient Descent (SGD) with momentum, which is the standard in practice.
Summary updated