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

By Hédy Attouch, Zaki Chbani, Hassan Riahi. E S A I M: Control, Optimisation and Calculus of Variations, 2017

144 citations recorded by the source corpus.

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 (xk): for α ≤ 3 we have Θ(xk) − min Θ = O(k−p) for all p < 2α/3, and for α > 3 Θ(xk) − min Θ = o(k−2). Finally, we show that the results are robust with respect to external perturbations.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/92cb9b838458e10b5a205addcd7f76cb19c860f9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Mathematical Physics

Citations in the corpus

Understanding the acceleration phenomenon via high-resolution differential equations (2018, background): “[ACR17] Hedy Attouch, Zaki Chbani, and Hassan Riahi.”