The Rate of Convergence of Nesterov's Accelerated Forward-Backward Method is Actually Faster Than 1/k2

By Hédy Attouch, Juan Peypouquet. SIAM Journal on Optimization, 2015

320 citations recorded by the source corpus.

The {\it forward-backward algorithm} is a powerful tool for solving optimization problems with a {\it additively separable} and {\it smooth} + {\it nonsmooth} structure. In the convex setting, a simple but ingenious acceleration scheme developed by Nesterov has been proved useful to improve the theoretical rate of convergence for the function values from the standard $\mathcal O(k^{-1})$ down to $\mathcal O(k^{-2})$. In this short paper, we prove that the rate of convergence of a slight variant of Nesterov's accelerated forward-backward method, which produces {\it convergent} sequences, is actually $o(k^{-2})$, rather than $\mathcal O(k^{-2})$. Our arguments rely on the connection between this algorithm and a second-order differential inclusion with vanishing damping.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/9c26e573c0e83a98bd3bc94cdf17a955554d2edf

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Convergence of iterates for first-order optimization algorithms with inertia and Hessian driven damping (2021, background): “For such values of α, it was also proved in [20,21] that the asymptotic convergence rate of the values is actually o(1/t2).”
A strong convergence result involving an inertial forward–backward algorithm for monotone inclusions (2017, methodology): “method from the standard O(k−1) down to O(k−2) and the inertial extrapolation scheme of Nesterov’s accelerated forward–backward method is actually o(k−2) rather than O(k−2) (see [3]).”
Convergence of a Relaxed Inertial Forward–Backward Algorithm for Structured Monotone Inclusions (2019, methodology): “Other choices of the extrapolation factors αk have been made in a series of recent papers [7, 9, 11, 20, 43].”