Tight global linear convergence rate bounds for Douglas–Rachford splitting

By Pontus Giselsson. Journal of Fixed Point Theory and Applications, 2015

91 citations recorded by the source corpus.

Recently, several authors have shown local and global convergence rate results for Douglas–Rachford splitting under strong monotonicity, Lipschitz continuity, and cocoercivity assumptions. Most of these focus on the convex optimization setting. In the more general monotone inclusion setting, Lions and Mercier showed a linear convergence rate bound under the assumption that one of the two operators is strongly monotone and Lipschitz continuous. We show that this bound is not tight, meaning that no problem from the considered class converges exactly with that rate. In this paper, we present tight global linear convergence rate bounds for that class of problems. We also provide tight linear convergence rate bounds under the assumptions that one of the operators is strongly monotone and cocoercive, and that one of the operators is strongly monotone and the other is cocoercive. All our linear convergence results are obtained by proving the stronger property that the Douglas–Rachford operator is contractive.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Orthopedics and Sports Medicine

View Paper: https://www.semanticscholar.org/paper/4859da584d7af5e200bbb8cf7fec013dcb7dfce0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Orthopedics and Sports Medicine

Citations in the corpus

Plug-and-Play Methods Provably Converge with Properly Trained Denoisers (2019, background): “The proof of Theorem 2 relies on the notion of “negatively averaged” operators of (Giselsson, 2017).”
A Primer on Monotone Operator Methods (2015, background): “For example, if f is a strongly convex CCP function, g is a strongly smooth CCP function, A = ∂f , and B = ∂g, then 1/2I + 1/2CACB is a contraction, and Douglas-Rachford converges geometrically [39,57].”
SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD (2018, background): “Giselsson also provided tight global linear convergence rate bounds in the more general setting of monotone inclusions [96]: namely, when one of A or B is strongly monotone and the other cocoercive, when one of A or B is both strongly monotone and cocoercive, and when one of A or B is strongly monot”
FedSplit: An algorithmic framework for fast federated optimization (2020, background): “Recent works have studied such splitting schemes for convex minimization under strong convexity and smoothness assumptions [11, 10, 19].”