# Gradient Norm Minimization of Nesterov Acceleration: o(1/k3)

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 27 references that are in the map.
- First posted on arXiv 19 Sep 2022.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [A Variational Perspective on Accelerated Methods in Optimization](https://mlsanity.com/paper/1603.04245/) (2016)
- [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013)
- [Understanding the Acceleration Phenomenon via High-Resolution Differential Equations](https://mlsanity.com/paper/1810.08907/) (2018)
- [Sharp convergence rates for Langevin dynamics in the nonconvex setting](https://mlsanity.com/paper/1805.01648/) (2018)
- [A Dynamical Systems Perspective on Nesterov Acceleration](https://mlsanity.com/paper/1905.07436/) (2019)
- [On Learning Rates and Schr"odinger Operators](https://mlsanity.com/paper/2004.06977/) (2020)
- [The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k2](https://mlsanity.com/paper/1510.08740/) (2015)
- [Fast convex optimization via inertial dynamics with Hessian driven damping](https://mlsanity.com/paper/1601.07113/) (2016)
- [On the Hyperparameters in Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2108.03947/) (2021)
- [An extension of the second order dynamical system that models Nesterov's convex gradient method](https://mlsanity.com/paper/1908.02574/) (2019)
- [On the Self-Penalization Phenomenon in Feature Selection](https://mlsanity.com/paper/2110.05852/) (2021)

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

- [Proximal Subgradient Norm Minimization of ISTA and FISTA](https://mlsanity.com/paper/2211.01610/) (2022)
- [Revisiting the acceleration phenomenon via high-resolution differential equations](https://mlsanity.com/paper/2212.05700/) (2022)
- [Linear Convergence of ISTA and FISTA](https://mlsanity.com/paper/2212.06319/) (2022)
- [A Variational Perspective on High-Resolution ODEs](https://mlsanity.com/paper/2311.02002/) (2023)
- [On Underdamped Nesterov's Acceleration](https://mlsanity.com/paper/2304.14642/) (2023)
- [Linear convergence of forward-backward accelerated algorithms without knowledge of the modulus of strong convexity](https://mlsanity.com/paper/2306.09694/) (2023)
- [Generalized Continuous-Time Models for Nesterov's Accelerated Gradient Methods](https://mlsanity.com/paper/2409.00913/) (2024)
- [Lyapunov Analysis For Monotonically Forward-Backward Accelerated Algorithms](https://mlsanity.com/paper/2412.13527/) (2024)

## Abstract (arXiv)

In the history of first-order algorithms, Nesterov's accelerated gradient descent (NAG) is one of the milestones. However, the cause of the acceleration has been a mystery for a long time. It has not been revealed with the existence of gradient correction until the high-resolution differential equation framework proposed in [Shi et al., 2021]. In this paper, we continue to investigate the acceleration phenomenon. First, we provide a significantly simplified proof based on precise observation and a tighter inequality for L-smooth functions. Then, a new implicit-velocity high-resolution differential equation framework, as well as the corresponding implicit-velocity version of phase-space representation and Lyapunov function, is proposed to investigate the convergence behavior of the iterative sequence xkk=0∞ of NAG. Furthermore, from two kinds of phase-space representations, we find that the role played by gradient correction is equivalent to that by velocity included implicitly in the gradient, where the only difference comes from the iterative sequence ykk=0∞ replaced by xkk=0∞. Finally, for the open question of whether the gradient norm minimization of NAG has a faster rate o(1/k3), we figure out a positive answer with its proof. Meanwhile, a faster rate of objective value minimization o(1/k2) is shown for the case r > 2.