Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
From MaRDI portal
Abstract: Operator splitting schemes are a class of powerful algorithms that solve complicated monotone inclusion and convex optimization problems that are built from many simpler pieces. They give rise to algorithms in which all simple pieces of the decomposition are processed individually. This leads to easily implementable and highly parallelizable or distributed algorithms, which often obtain nearly state-of-the-art performance. In this paper, we analyze the convergence rate of the forward-Douglas-Rachford splitting (FDRS) algorithm, which is a generalization of the forward-backward splitting (FBS) and Douglas-Rachford splitting (DRS) algorithms. Under general convexity assumptions, we derive the ergodic and nonergodic convergence rates of the FDRS algorithm, and show that these rates are the best possible. Under Lipschitz differentiability assumptions, we show that the best iterate of FDRS converges as quickly as the last iterate of the FBS algorithm. Under strong convexity assumptions, we derive convergence rates for a sequence that strongly converges to a minimizer. Under strong convexity and Lipschitz differentiability assumptions, we show that FDRS converges linearly. We also provide examples where the objective is strongly convex, yet FDRS converges arbitrarily slowly. Finally, we relate the FDRS algorithm to a primal-dual forward-backward splitting scheme and clarify its place among existing splitting methods. Our results show that the FDRS algorithm automatically adapts to the regularity of the objective functions and achieves rates that improve upon the sharp worst case rates that hold in the absence of smoothness and strong convexity.
Recommendations
- Convergence rates of forward-Douglas-Rachford splitting method
- Convergence Rate Analysis of Primal-Dual Splitting Schemes
- Convergence rate analysis of several splitting schemes
- Tight global linear convergence rate bounds for Douglas-Rachford splitting
- Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
Cites work
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science
- A generalized forward-backward splitting
- A Modified Forward-Backward Splitting Method for Maximal Monotone Mappings
- A monotone+skew splitting model for composite monotone inclusions in duality
- A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
- A splitting algorithm for dual monotone inclusions involving cocoercive operators
- Compositions and convex combinations of averaged nonexpansive operators
- Convergence Rate Analysis of Primal-Dual Splitting Schemes
- Convergence rate analysis of several splitting schemes
- Convex analysis and monotone operator theory in Hilbert spaces
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
- Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
- Forward-Douglas–Rachford splitting and forward-partial inverse method for solving monotone inclusions
- scientific article; zbMATH DE number 3108780 (Why is no real title available?)
- Mean Value Methods in Iteration
- Proximal splitting methods in signal processing
- Quelques propriétés des opérateurs angle-bornes et n-cycliquement monotones
- Solving monotone inclusions via compositions of nonexpansive averaged operators
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Support-vector networks
- The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
Cited in
(33)- Tight global linear convergence rate bounds for Douglas-Rachford splitting
- Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
- Modified Fejér sequences and applications
- An adaptive primal-dual framework for nonsmooth convex minimization
- Douglas-Rachford splitting and ADMM for pathological convex optimization
- Convergence rates of forward-Douglas-Rachford splitting method
- An inertial parallel and asynchronous forward-backward iteration for distributed convex optimization
- Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence
- Iteration complexity of an inexact Douglas-Rachford method and of a Douglas-Rachford-Tseng's F-B four-operator splitting method for solving monotone inclusions
- Convergence rates for the relaxed Peaceman-Rachford splitting method on a monotone inclusion problem
- Convergence analysis of the generalized Douglas-Rachford splitting method under Hölder subregularity assumptions
- Convergence Rate Analysis of Primal-Dual Splitting Schemes
- Convergence rate analysis for averaged fixed point iterations in common fixed point problems
- A survey on operator splitting and decomposition of convex programs
- A unified splitting algorithm for composite monotone inclusions
- Convergence Rates in Forward--Backward Splitting
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
- On the convergence rate of a forward-backward type primal-dual splitting algorithm for convex optimization problems
- On the linear convergence rate of a relaxed forward–backward splitting method
- A new homotopy proximal variable-metric framework for composite convex minimization
- Convergence Analysis for Splitting of the Abstract Differential Riccati Equation
- Convergence analysis of Douglas-Rachford splitting method for ``strongly + weakly convex programming
- Convergence rate analysis of several splitting schemes
- A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates
- [[:Publication:6091103|Fast Krasnosel’skiĭ–Mann Algorithm with a Convergence Rate of the Fixed Point Iteration of \(\boldsymbol{{ o} \left(\frac{1}Template:K \right)}\)]]
- Tikhonov regularized iterative methods for nonlinear problems
- A three-operator splitting scheme and its optimization applications
- Understanding the Douglas-Rachford splitting method through the lenses of Moreau-type envelopes
- Complexity of the relaxed Peaceman-Rachford splitting method for the sum of two maximal strongly monotone operators
- Revisiting extragradient-type methods. I: Generalizations and sublinear convergence rates
- Over relaxed hybrid proximal extragradient algorithm and its application to several operator splitting methods
- On the convergence rate of Douglas-Rachford operator splitting method
This page was built for publication: Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947226)
