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

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.