# Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2017.

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

- [A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip](https://mlsanity.com/paper/2106.07644/) (2021)
- [Maximum diffusion reinforcement learning](https://mlsanity.com/paper/2309.15293/) (2023)
- [Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization](https://mlsanity.com/paper/2101.12101/) (2021)
- [Inertial Newton Algorithms Avoiding Strict Saddle Points](https://mlsanity.com/paper/2111.04596/) (2021)
- [Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima](https://mlsanity.com/paper/2307.07030/) (2023)
- [Fast symplectic integrator for Nesterov-type acceleration method](https://mlsanity.com/paper/2106.07620/) (2021)
- [On Underdamped Nesterov's Acceleration](https://mlsanity.com/paper/2304.14642/) (2023)
- [Near-optimal Closed-loop Method via Lyapunov Damping for Convex Optimization](https://mlsanity.com/paper/2311.10053/) (2023)
- [A second-order-like optimizer with adaptive gradient scaling for deep learning](https://mlsanity.com/paper/2410.05871/) (2024)

## Abstract (arXiv)

In a Hilbert space setting mathcal H, given Phi: mathcal H → mathbb R a convex continuously differentiable function, and α a positive parameter, we consider the inertial system with Asymptotic Vanishing Damping beginequation* mbox(AVD)α quad quad ddotx(t) + fracαt dotx(t) + nabla Phi (x(t)) =0. endequation* Depending on the value of  α  with respect to 3, we give a complete picture of the convergence properties as t → + ∞ of the trajectories generated by mbox(AVD)α, as well as iterations of the corresponding algorithms. Our main result concerns the subcritical case α ≤ 3, where we show that Phi (x(t))-min Phi = mathcal O (t^-frac23α). Then we examine the convergence of trajectories to optimal solutions. As a new result, in the one-dimensional framework, for the critical value α = 3 , we prove the convergence of the trajectories without any restrictive hypothesis on the convex function Phi . In the second part of this paper, we study the convergence properties of the associated forward-backward inertial algorithms. They aim to solve structured convex minimization problems of the form min leftlbrace Theta:= Phi + Psi rightrbrace, with Phi smooth and Psi nonsmooth. The continuous dynamics serves as a guideline for this study. We obtain a similar rate of convergence for the sequence of iterates (xk): for α ≤ 3 we have Theta (xk)-min Theta = mathcal O (k-p) for all p <frac2α3 , and for α > 3  Theta (xk)-min Theta = o (k-2) . We conclude this study by showing that the results are robust with respect to external perturbations.