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

¹ Institut Montpelliérain A. Grothendieck, UMR CNRS 5149, Université Montpellier, 34095 Montpellier Cedex 5, France.
² Cadi Ayyad University, Faculty of Sciences Semlalia, Mathematics, 40000 Marrakech, Morroco.

^* Corresponding author: hedy.attouch@univ-montp2.fr

Received: 23 June 2017
Accepted: 17 December 2017

Abstract

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

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⁻²) 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⁻²). Finally, we show that the results are robust with respect to external perturbations.