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

In a Hilbert space setting ℋ , given Φ : ℋ → ℝ a convex continuously differentiable function, and α a positive parameter, we consider the inertial dynamic system with Asymptotic Vanishing Damping (AVD) α ẍ ( t ) + α/ tẋ ( t ) + ∇ Φ ( x ( t )) = 0. 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 (AVD) α , as well as iterations of the corresponding algorithms. Indeed, as shown by Su-Boyd-Candès, the case α = 3 corresponds to a continuous version of the accelerated gradient method of Nesterov, with the rate of convergence Φ ( x ( t )) − min Φ = O ( t −2 ) for α ≥ 3. Our main result concerns the subcritical case α ≤ 3, where we show that Φ ( x ( t )) − min Φ = O ( t −⅔ α ). This overall picture shows a continuous variation of the rate of convergence of the values Φ ( x ( t )) − min ℋ Φ = O ( t − p ( α ) ) with respect to α > 0: the coefficient p ( α ) increases linearly up to 2 when α goes from 0 to 3, then displays a plateau. 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. 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 { Θ := Φ + Ψ }, with Φ smooth and Ψ nonsmooth. The continuous dynamics serves as a guideline for this study. We obtain a similar rate of convergence for the sequence of iterates ( x k ): for α ≤ 3 we have Θ ( x k ) − min Θ = O ( k − p ) for all p < 2 α /3, and for α > 3 Θ ( x k ) − min Θ = o ( k −2 ). Finally, we show that the results are robust with respect to external perturbations.