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

2017/06/18 by Hédy Attouch, Attouch, Hedy, Zaki Chbani +3 · 5 citations
Computer Science · Engineering · Mathematics · #49M37 #65K05 #90C25 #FOS: Mathematics #Numerical methods in inverse problems #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1706.05671

openalex publication_date 2017/06/18 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28

Abstract

In a Hilbert space setting \mathcal H, given Φ: \mathcal H → \mathbb R a convex continuously differentiable function, and α a positive parameter, we consider the inertial system with Asymptotic Vanishing Damping (AVD)_α x(t) + \fracαt x(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. Our main result concerns the subcritical case α≤ 3, where we show that Φ(x(t))-min Φ= \mathcal O (t^-(2)/(3)α). 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 Φ. 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 \lbrace Θ:= Φ+ Ψ\rbrace, 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 Θ= \mathcal O (k^-p) for all p 3 Θ(x_k)-min Θ= o (k^-2) . We conclude this study by showing that the results are robust with respect to external perturbations.

Cited by

• The Iterates of Nesterov's Accelerated Algorithm Converge in The Critical Regimes
• Inexact and Stochastic Gradient Optimization Algorithms with Inertia and Hessian Driven Damping
• A √(2)-accelerated FISTA for composite strongly convex problems
• Fast convex optimization via inertial systems with asymptotically vanishing viscosity and Hessian-driven damping
• Fast convergence of dynamical systems with implicit Hessian damping and Tikhonov regularization

Related

• Combining fast inertial dynamics for convex optimization with Tikhonov regularization
• Nesterov's acceleration and Polyak's heavy ball method in continuous time: convergence rate analysis under geometric conditions and perturbations
• Accelerated Gradient Methods via Inertial Systems with Hessian-driven Damping
• Convergence rates for an inertial algorithm of gradient type associated to a smooth nonconvex minimization
• Accelerated gradient methods with strong convergence to the minimum norm minimizer: a dynamic approach combining time scaling, averaging, and Tikhonov regularization