Repository logo
 

Convergence rates of Forward--Douglas--Rachford splitting method

Published version
Peer-reviewed

Type

Article

Change log

Authors

Molinari, Cesare 
Fadili, Jalal 

Abstract

Over the past years, operator splitting methods have become ubiquitous for non-smooth optimization owing to their simplicity and efficiency. In this paper, we consider the Forward--Douglas--Rachford splitting method (FDR) [10,40], and study both global and local convergence rates of this method. For the global rate, we establish an o(1/k) convergence rate in terms of a Bregman divergence suitably designed for the objective function. Moreover, when specializing to the case of Forward--Backward splitting method, we show that convergence rate of the objective function of the method is actually o(1/k) for a large choice of the descent step-size. Then locally, based on the assumption that the non-smooth part of the optimization problem is partly smooth, we establish local linear convergence of the method. More precisely, we show that the sequence generated by FDR method first (i) identifies a smooth manifold in a finite number of iteration, and then (ii) enters a local linear convergence regime, which is for instance characterized in terms of the structure of the underlying active smooth manifold. To exemplify the usefulness of the obtained result, we consider several concrete numerical experiments arising from applicative fields including, for instance, signal/image processing, inverse problems and machine learning.

Description

Keywords

Bregman distance, Finite identification, Forward–Backward, Forward–Douglas–Rachford, Local linear convergence, Partial smoothness

Journal Title

Journal of Optimization Theory and Applications

Conference Name

Journal ISSN

1573-2878
1573-2878

Volume Title

Publisher

Springer
Sponsorship
Engineering and Physical Sciences Research Council (EP/N014588/1)
Engineering and Physical Sciences Research Council (EP/M00483X/1)
CM was supported by CONICYT scholarship CONICYT-PCHA/Doctorado Nacional/2016. JL was supported by the European Research Council (ERC project SIGMA-Vision), and Leverhulme Trust project \Breaking the non-convexity barrier", the EPSRC grant \EP/M00483X/1", EPSRC centre \EP/N014588/1", Cantab Capital Institute for the Mathematics of Information, and Global Alliance project \Statistical and Mathematical Theory of Imaging". JF was partly supported by Institut Universitaire de France.