# A Convergence Analysis of Nesterov's Accelerated Gradient Method in Training Deep Linear Neural Networks

arXiv: https://arxiv.org/abs/2204.08306 · HTML: https://mlsanity.com/paper/2204.08306/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 47 references that are in the map.
- First posted on arXiv 18 Apr 2022.

## Builds on (most cited first, 28 of 28)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Deep Learning without Poor Local Minima](https://mlsanity.com/paper/1605.07110/) (2016)
- [A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks](https://mlsanity.com/paper/1810.02281/) (2018)
- [Adaptive Gradient Methods with Dynamic Bound of Learning Rate](https://mlsanity.com/paper/1902.09843/) (2019)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [Convergence Analysis of Two-layer Neural Networks with ReLU Activation](https://mlsanity.com/paper/1705.09886/) (2017)
- [Descending through a Crowded Valley - Benchmarking Deep Learning Optimizers](https://mlsanity.com/paper/2007.01547/) (2020)
- [Identity Matters in Deep Learning](https://mlsanity.com/paper/1611.04231/) (2016)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Provable Benefit of Orthogonal Initialization in Optimizing Deep Linear Networks](https://mlsanity.com/paper/2001.05992/) (2020)
- [Deep linear neural networks with arbitrary loss: All local minima are global](https://mlsanity.com/paper/1712.01473/) (2017)
- [Width Provably Matters in Optimization for Deep Linear Neural Networks](https://mlsanity.com/paper/1901.08572/) (2019)
- ["Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions](https://mlsanity.com/paper/1705.02766/) (2017)
- [Depth Creates No Bad Local Minima](https://mlsanity.com/paper/1702.08580/) (2017)
- [On the Global Convergence of Training Deep Linear ResNets](https://mlsanity.com/paper/2003.01094/) (2020)
- [A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network](https://mlsanity.com/paper/2010.01618/) (2020)
- [A recurrent neural network without chaos](https://mlsanity.com/paper/1612.06212/) (2016)
- [A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks](https://mlsanity.com/paper/2010.13165/) (2020)
- [Provable Convergence of Nesterov's Accelerated Gradient Method for Over-Parameterized Neural Networks](https://mlsanity.com/paper/2107.01832/) (2021)
- [Effects of Depth, Width, and Initialization: A Convergence Analysis of Layer-wise Training for Deep Linear Neural Networks](https://mlsanity.com/paper/1910.05874/) (2019)

## Built on by (most cited first, 4 of 4)

- [Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks](https://mlsanity.com/paper/2410.09640/) (2024)
- [On the Convergence of Federated Averaging under Partial Participation for Over-parameterized Neural Networks](https://mlsanity.com/paper/2310.05495/) (2023)
- [Robust Gradient Descent via Heavy-Ball Momentum with Predictive Extrapolation](https://mlsanity.com/paper/2512.10033/) (2025)
- [Global Exponential Convergence of Two-Layer Linear Network Training](https://mlsanity.com/paper/2610.09356/) (2026)

## Abstract (arXiv)

Momentum methods, including heavy-ball~(HB) and Nesterov's accelerated gradient~(NAG), are widely used in training neural networks for their fast convergence. However, there is a lack of theoretical guarantees for their convergence and acceleration since the optimization landscape of the neural network is non-convex. Nowadays, some works make progress towards understanding the convergence of momentum methods in an over-parameterized regime, where the number of the parameters exceeds that of the training instances. Nonetheless, current results mainly focus on the two-layer neural network, which are far from explaining the remarkable success of the momentum methods in training deep neural networks. Motivated by this, we investigate the convergence of NAG with constant learning rate and momentum parameter in training two architectures of deep linear networks: deep fully-connected linear neural networks and deep linear ResNets. Based on the over-parameterization regime, we first analyze the residual dynamics induced by the training trajectory of NAG for a deep fully-connected linear neural network under the random Gaussian initialization. Our results show that NAG can converge to the global minimum at a (1 - O(1/√kappa))t rate, where t is the iteration number and kappa > 1 is a constant depending on the condition number of the feature matrix. Compared to the (1 - O(1/kappa))t rate of GD, NAG achieves an acceleration over GD. To the best of our knowledge, this is the first theoretical guarantee for the convergence of NAG to the global minimum in training deep neural networks. Furthermore, we extend our analysis to deep linear ResNets and derive a similar convergence result.