Optimization Online


Accelerated and Inexact forward-backward algorithms

Silvia Villa (villa***at***dima.unige.it)
Saverio Salzo (salzo***at***disi.unige.it)
Luca Baldassarre (l.baldassarre***at***cs.ucl.ac.uk)
Alessandro Verri (verri***at***disi.unige.it)

Abstract: We propose a convergence analysis of accelerated forward-backward splitting methods for minimizing composite functions, when the proximity operator is not available in closed form, and is thus 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. An experimental analysis aiming at validating the obtained rates is also presented.

Keywords: convex optimization, accelerated forward-backward splitting, inexact proximity operator, estimate sequences, total variation

Category 1: Convex and Nonsmooth Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Convex and Nonsmooth Optimization (Nonsmooth Optimization )


Download: [PDF]

Entry Submitted: 08/17/2011
Entry Accepted: 08/17/2011
Entry Last Modified: 09/19/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society