Source-linked AI summary
The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^{2}$
Hedy Attouch, Juan Peypouquet
TL;DR
The paper addresses whether Nesterov’s accelerated forward-backward method can provide convergent sequences while improving its known O(k^-2) function-value rate. It proves that the function-value error is actually o(k^-2), and that no uniform O(k^-p) rate exists for every problem when p > 2.
Problem
The paper studies the unresolved convergence behavior of sequences generated by Nesterov’s accelerated forward-backward method despite its O(k^-2) function-value rate.
Method
The paper analyzes Nesterov’s accelerated forward-backward iterations and establishes asymptotic convergence-rate properties for their generated sequences.
Results
(Ψ + Φ)(x_k) − min(Ψ + Φ) = o(k^-2), while ∥x_{k+1} − x_k∥ = o(k^-1).
Takeaways & Limitations
Theorem 1’s o(k^-2) rate is optimal because no p > 2 gives O(k^-p) convergence for every Φ and Ψ.
Takeaways & Limitations
No p > 2 provides an O(k^-p) convergence rate uniformly for every Φ and Ψ.
Abstract
from arXiv · showhide
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.
Introduction
The paper studies Nesterov’s accelerated forward-backward method for convex smooth+nonsmooth optimization and proves a strictly faster-than-O(k^-2) convergence rate for function values. It also establishes velocity decay, an optimality limitation, and preservation of convergence under inexact iterations.
- Problem setting: Forward-backward splitting exploits an additively separable smooth+nonsmooth structure, including ISTA when Ψ is the ℓ1 norm and Φ is quadratic.The method was developed to minimize sums of a proper lower-semicontinuous convex function and a convex differentiable function with Lipschitz gradient.
- Nesterov acceleration: O(k^-2) function-value convergence improves on the classical O(k^-1) rate while retaining the computational efficiency of forward-backward iterations.The accelerated method uses a parameter α > 0 and s > 0, with α = 3 described as common practice.
- Main result: o(k^-2) function-value error and o(k^-1) successive-iterate velocity hold when α > 3 and 0 < s < 1/L.Under the theorem’s convexity, smoothness, and existence-of-minimizers assumptions, the generated sequence satisfies (Ψ + Φ)(xk) − min(Ψ + Φ) = o(k^-2) and ∥xk+1 − xk∥ = o(k^-1).
- Optimality: No p > 2 yields O(k^-p) convergence for every Φ and Ψ, making the theorem’s faster-than-O(k^-2) rate optimal in this sense.This limitation is established through a result from [2, Example 2.13].
- Inexact computations: The paper establishes a tolerance estimate ensuring that the convergence order is preserved when the accelerated iterations are computed inexactly.This result is stated as Theorem 4, alongside related work on inexact FISTA-like algorithms.
1. Main results
For α > 3 and 0 < s < 1/L, the accelerated forward-backward method achieves o(k^-2) function-value convergence and o(k^-1) velocity decay, while its iterates converge weakly to a minimizer. The same asymptotic properties extend to an inexact variant under suitable error tolerances.
- Exact algorithm: The sequence (xk) converges weakly to a point in S when α > 3 and 0 < s < 1/L.Here S is the nonempty set of minimizers of Ψ + Φ.
- Inexact algorithm: Suitable tolerances for errors (gk) preserve all asymptotic properties of the exact method, including o(k^-2) convergence.The inexact algorithm also retains the velocity result and weak convergence to a point in S.