Accelerated and Inexact Forward-Backward Algorithms

Silvia Villa, Saverio Salzo, Luca Baldassarre, Alessandro Verri

SIAM Journal on Optimization · 2013 · 198 citations · 63 references

DOIFull text

Open access

Concepts

Abstract

We propose a convergence analysis of accelerated forward-backward splitting methods for composite function minimization, when the proximity operator is not available in closed form, and can only be computed up to a certain precision. We prove that the $1/k^2$ convergence rate for the function values can be achieved if the admissible errors are of a certain type and satisfy a sufficiently fast decay condition. Our analysis is based on the machinery of estimate sequences first introduced by Nesterov for the study of accelerated gradient descent algorithms. Furthermore, we give a global complexity analysis, taking into account the cost of computing admissible approximations of the proximal point. An experimental analysis is also presented.

References

63