Accelerated And Inexact Forward-Backward Algorithms

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.


Published in:
Siam Journal On Optimization, 23, 3, 1607-1633
Year:
2013
Publisher:
Philadelphia, Siam Publications
ISSN:
1052-6234
Keywords:
Laboratories:




 Record created 2013-12-09, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)