Provable Acceleration of Nesterov's Accelerated Gradient Method over Heavy Ball Method in Training Over-Parameterized Neural Networks

Xin Liu, Tao Wei, Jun Wang, Zhisong Pan, Wang, Jun, Pan, Zhisong

Abstract

Due to its simplicity and efficiency, the first-order gradient method has been extensively employed in training neural networks. Although the optimization problem of the neural network is non-convex, recent research has proved that the first-order method is capable of attaining a global minimum during training over-parameterized neural networks, where the number of parameters is significantly larger than that of training instances. Momentum methods, including the heavy ball (HB) method and Nesterov's accelerated gradient (NAG) method, are the workhorse of first-order gradient methods owning to their accelerated convergence. In practice, NAG often exhibits superior performance than HB. However, current theoretical works fail to distinguish their convergence difference in training neural networks. To fill this gap, we consider the training problem of the two-layer ReLU neural network under over-parameterization and random initialization. Leveraging high-resolution dynamical systems and neural tangent kernel (NTK) theory, our result not only establishes tighter upper bounds of the convergence rate for both HB and NAG, but also provides the first theoretical guarantee for the acceleration of NAG over HB in training neural networks. Finally, we validate our theoretical results on three benchmark datasets.

Introduction

In deep learning, momentum-based optimization is standard practice. Two primary variants dominate: Polyak’s Heavy Ball (HB) method and Nesterov’s Accelerated Gradient (NAG). While empirical evidence consistently favors NAG for its faster and more stable convergence, theoretical analysis has historically struggled to differentiate the two. This difficulty arises from the non-convex nature of neural network loss landscapes and the limitations of "low-resolution" Ordinary Differential Equation (ODE) models, which often yield identical equations for both methods. This paper addresses this gap by providing a rigorous mathematical guarantee for NAG's acceleration over HB in the context of over-parameterized, two-layer ReLU networks.

Methods

The analysis bridges the gap between theory and practice using two key frameworks:

  1. Neural Tangent Kernel (NTK) Theory: In the over-parameterized regime (large hidden layer width $m$), network weights remain close to their random initialization. This "lazy training" regime allows the non-convex loss landscape to be analyzed as if it were strongly convex.
  2. High-Resolution Dynamical Systems: Unlike standard ODEs, high-resolution models capture the "gradient correction term" in NAG—the mathematical representation of its "look-ahead" property.

By deriving residual dynamics and employing Lyapunov-based stability analysis, the authors established tighter upper bounds on convergence rates for both algorithms.

Key Insights and Ideas

The core theoretical contribution is identifying the role of the gradient correction term in the high-resolution ODE. In NAG, this term acts as a correction based on gradient changes, directly accelerating the decay of training loss.

Theoretical convergence rate coefficient for NAG as a function of the gradient correction term.

The analysis shows that while previous works suggested identical convergence rates of $O(e^{-\sqrt{\mu}t/4})$, this study provides tighter bounds. Specifically, HB converges at a rate of $O(e^{-(2-\sqrt{2})\sqrt{\mu}t})$, while NAG achieves a strictly faster rate $\rho_{NAG} > 0.585$.

Key Results

The theoretical findings were validated on MNIST, Fashion-MNIST (FMNIST), and CIFAR10 datasets. The experiments focused on binary classification tasks to align with the theoretical setup.

Empirical comparison of training loss for NAG (red) and HB (blue) across various network widths and learning rates.

As shown in the empirical results, NAG consistently achieves lower training loss faster than HB across various hidden layer widths ($m=1000$ to $8000$) and learning rates. Furthermore, weight stability experiments confirmed that weight displacement scales by $1/\sqrt{m}$, validating the NTK-based "lazy training" assumption.

Conclusion and Future Work

This work provides the first theoretical proof of NAG's superiority over HB in training over-parameterized neural networks. However, limitations remain: the proof is currently restricted to two-layer ReLU networks and the "lazy training" regime. Future research could extend these findings to deeper architectures, convolutional neural networks (CNNs), and adaptive optimizers like Adam or RMSProp.

Summary updated

Abstract

Due to its simplicity and efficiency, the first-order gradient method has been extensively employed in training neural networks. Although the optimization problem of the neural network is non-convex, recent research has proved that the first-order method is capable of attaining a global minimum during training over-parameterized neural networks, where the number of parameters is significantly larger than that of training instances. Momentum methods, including the heavy ball (HB) method and Nesterov's accelerated gradient (NAG) method, are the workhorse of first-order gradient methods owning to their accelerated convergence. In practice, NAG often exhibits superior performance than HB. However, current theoretical works fail to distinguish their convergence difference in training neural networks. To fill this gap, we consider the training problem of the two-layer ReLU neural network under over-parameterization and random initialization. Leveraging high-resolution dynamical systems and neural tangent kernel (NTK) theory, our result not only establishes tighter upper bounds of the convergence rate for both HB and NAG, but also provides the first theoretical guarantee for the acceleration of NAG over HB in training neural networks. Finally, we validate our theoretical results on three benchmark datasets.
BibTeX
@inproceedings{liu2024provable,
  author = {Xin Liu and Tao Wei and Jun Wang and Zhisong Pan and Wang, Jun and Pan, Zhisong},
  title = {{Provable Acceleration of Nesterov's Accelerated Gradient Method over Heavy Ball Method in Training Over-Parameterized Neural Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure