TL;DR
This paper provides the first theoretical proof that Nesterov’s Accelerated Gradient (NAG) method converges faster than the Heavy Ball (HB) method when training over-parameterized neural networks. By employing "high-resolution" dynamical systems and Neural Tangent Kernel (NTK) theory, the authors bridge the long-standing gap between empirical observations of NAG's superiority and the mathematical guarantees that previously failed to distinguish the two.
What Problem Does This Paper Address?
In the world of deep learning, momentum-based optimization is the gold standard. Two of the most popular variants are the Heavy Ball (HB) method and Nesterov’s Accelerated Gradient (NAG). While practitioners have long observed that NAG typically converges faster and more reliably than HB, theoretical analysis has struggled to explain why.
The challenge lies in how we model these algorithms. Researchers often use "low-resolution" Ordinary Differential Equations (ODEs) to represent the continuous-time limit of these discrete algorithms. Unfortunately, at low resolution, the ODEs for HB and NAG look identical, making it impossible to prove that one is faster than the other. Furthermore, neural network training is inherently non-convex, which complicates traditional convergence proofs that rely on convex assumptions.
Methods
The authors tackle this by moving to a high-resolution dynamical system perspective. Unlike low-resolution models, high-resolution ODEs retain a "gradient correction" term that is unique to NAG. This term accounts for the fact that NAG calculates the gradient at a "looked-ahead" position rather than the current one.
To handle the non-convexity of neural networks, the researchers leverage Neural Tangent Kernel (NTK) theory. In the "over-parameterized" regime—where the network has far more parameters than training data points—the weights stay relatively close to their initial values. Under these conditions, the complex, non-convex training dynamics of the weights actually correspond to a strongly convex dynamics for the residual error.
Finally, they use a Lyapunov-based approach combined with a sharper version of Young’s inequality to derive tighter upper bounds on the convergence rates for both methods.
Datasets
The theoretical results were validated using three standard benchmark datasets:
- MNIST: Handwritten digits.
- FMNIST (Fashion-MNIST): Images of clothing articles.
- CIFAR10: A collection of images in 10 different classes.
For their experiments, the authors focused on binary classification tasks using the first two classes of each dataset, normalized to unit norm.
Key Insights and Ideas
- The Resolution Matters: The "aha moment" is that the acceleration of NAG over HB is hidden in higher-order terms. By using high-resolution ODEs, the authors could finally see the "gradient correction" term that drives NAG's superior performance.
- Provable Acceleration: The paper proves that while HB converges at a rate of $O(e^{-(2-\sqrt{2})\sqrt{\mu}t})$, NAG achieves a faster rate of $O(e^{-\rho_{NAG}\sqrt{\mu}t})$, where $\rho_{NAG}$ is strictly greater than $2-\sqrt{2}$.
- The Role of Over-parameterization: The study reinforces the idea that very wide neural networks are "nicer" to optimize. In this regime, the training process behaves predictably enough that we can apply tools from convex optimization to a non-convex problem.
Key Results
- Theoretical Gap: The authors established the first theoretical guarantee for the acceleration of NAG over HB in neural network training.
- Empirical Validation: Experiments on MNIST (and others) confirmed that NAG consistently reaches a lower training loss faster than HB across various network widths ($m$), learning rates ($\eta$), and momentum parameters ($\beta$).
- Weight Stability: The authors also tracked the maximum distance weights moved from their initialization. As predicted by Lemma 4 and 6, this distance decreases as the network width ($m$) increases, supporting the validity of the NTK-based analysis.

Limitations and Future Work
While this is a significant step forward, the authors acknowledge several limitations:
- Architecture: The proof is currently limited to two-layer ReLU networks. Extending this to deeper, more complex architectures (like Transformers or CNNs) remains a challenge.
- Continuous vs. Discrete: The analysis is performed in continuous time (ODEs). While the authors cite work showing that discrete iterates stay close to these ODE trajectories, a direct discrete-time proof would be even more robust.
- Stochasticity: This paper focuses on deterministic gradient methods. Real-world training uses Stochastic Gradient Descent (SGD); incorporating noise and mini-batching into this high-resolution framework is a promising future direction.
Summary updated