Convergence rate analysis of several splitting schemes
From MaRDI portal
Abstract: Splitting schemes are a class of powerful algorithms that solve complicated monotone inclusions and convex optimization problems that are built from many simpler pieces. They give rise to algorithms in which the simple pieces of the decomposition are processed individually. This leads to easily implementable and highly parallelizable algorithms, which often obtain nearly state-of-the-art performance. In the first part of this paper, we analyze the convergence rates of several general splitting algorithms and provide examples to prove the tightness of our results. The most general rates are proved for the emph{fixed-point residual} (FPR) of the Krasnosel'skiu{i}-Mann (KM) iteration of nonexpansive operators, where we improve the known big- rate to little-. We show the tightness of this result and improve it in several special cases. In the second part of this paper, we use the convergence rates derived for the KM iteration to analyze the emph{objective error} convergence rates for the Douglas-Rachford (DRS), Peaceman-Rachford (PRS), and ADMM splitting algorithms under general convexity assumptions. We show, by way of example, that the rates obtained for these algorithms are tight in all cases and obtain the surprising statement: The DRS algorithm is nearly as fast as the proximal point algorithm (PPA) in the ergodic sense and nearly as slow as the subgradient method in the nonergodic sense. Finally, we provide several applications of our result to feasibility problems, model fitting, and distributed optimization. Our analysis is self-contained, and most results are deduced from a basic lemma that derives convergence rates for summable sequences, a simple diagram that decomposes each relaxed PRS iteration, and fundamental inequalities that relate the FPR to objective error.
Recommendations
- Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
- Convergence Rate Analysis of Primal-Dual Splitting Schemes
- Introduction
- Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
- Convergence rates of forward-Douglas-Rachford splitting method
Cited in
(only showing first 100 items - show all)- On the information-adaptive variants of the ADMM: an iteration complexity perspective
- A regularized semi-smooth Newton method with projection steps for composite convex programs
- Tight global linear convergence rate bounds for Douglas-Rachford splitting
- An operator splitting approach for distributed generalized Nash equilibria computation
- A new primal-dual algorithm for minimizing the sum of three functions with a linear operator
- The Glowinski-Le Tallec splitting method revisited: a general convergence and convergence rate analysis
- Local and global convergence of a general inertial proximal splitting scheme for minimizing composite functions
- On the linear convergence of forward-backward splitting method. I: Convergence analysis
- Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis
- Fast convergence of dynamical ADMM via time scaling of damped inertial dynamics
- Distributed computation of fast consensus weights using ADMM
- Applications of accelerated computational methods for quasi-nonexpansive operators to optimization problems
- Decentralized proximal splitting algorithms for composite constrained convex optimization
- Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property
- Accelerated proximal point method for maximally monotone operators
- Sparsity reconstruction using nonconvex TGpV-shearlet regularization and constrained projection
- Fast robust methods for singular state-space models
- Douglas-Rachford splitting and ADMM for pathological convex optimization
- Accelerated alternating direction method of multipliers: an optimal \(O(1 / K)\) nonergodic analysis
- Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence
- Accelerating convergence of a class of splitting algorithms with iterative foldings
- Local convergence properties of Douglas-Rachford and alternating direction method of multipliers
- On the global and linear convergence of the generalized alternating direction method of multipliers
- Asymmetric forward-backward-adjoint splitting for solving monotone inclusions involving three operators
- \(O(1/t)\) complexity analysis of the generalized alternating direction method of multipliers
- Quadratic growth conditions and uniqueness of optimal solution to Lasso
- Convergence rate analysis for fixed-point iterations of generalized averaged nonexpansive operators
- 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
- A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization
- ARock: an algorithmic framework for asynchronous parallel coordinate updates
- Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
- 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
- On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions
- Tight sublinear convergence rate of the proximal point algorithm for maximal monotone inclusion problems
- Low-rank matrix iteration using polynomial-filtered subspace extraction
- A unified splitting algorithm for composite monotone inclusions
- A general inertial proximal point algorithm for mixed variational inequality problem
- Inertial proximal ADMM for linearly constrained separable convex optimization
- scientific article; zbMATH DE number 2051075 (Why is no real title available?)
- Tight Global Linear Convergence Rate Bounds for Operator Splitting Methods
- Parameter selection and preconditioning for a graph form solver
- An alternating direction method of multipliers with a worst-case \(O(1/n^2)\) convergence rate
- Distributed model predictive control for continuous-time nonlinear systems based on suboptimal ADMM
- First- and second-order methods for online convolutional dictionary learning
- The augmented Lagrangian method with full Jacobian decomposition and logarithmic-quadratic proximal regularization for multiple-block separable convex programming
- On the complexity analysis of the primal solutions for the accelerated randomized dual coordinate ascent
- Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
- On the convergence rate of the Krasnosel'skiĭ-Mann iteration
- SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- Reflected three-operator splitting method for monotone inclusion problem
- An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming
- Thresholding gradient methods in Hilbert spaces: support identification and linear convergence
- Operator splitting performance estimation: tight contraction factors and optimal parameter selection
- Rate of convergence of modified Mann iteration for asymptotically nonexpansive mappings
- A dynamical system associated with the fixed points set of a nonexpansive operator
- Convergence Rates for Projective Splitting
- Relaxation algorithms for matrix completion, with applications to seismic travel-time data interpolation
- EXTRA: an exact first-order algorithm for decentralized consensus optimization
- Cyclic coordinate-update algorithms for fixed-point problems: analysis and applications
- Introduction
- The Variable Metric Forward-Backward Splitting Algorithm Under Mild Differentiability Assumptions
- On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces
- New inertial method for nonexpansive mappings
- Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists
- Some extensions of the operator splitting schemes based on Lagrangian and primal–dual: a unified proximal point analysis
- On convergence rates of proximal alternating direction method of multipliers
- [[: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)}\)]]
- Distributed safe resource allocation using barrier functions
- Inertial-relaxed splitting for composite monotone inclusions
- Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient
- The operator splitting schemes revisited: primal-dual gap and degeneracy reduction by a unified analysis
- Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming
- A randomized operator splitting scheme inspired by stochastic optimization methods
- Parameter-free accelerated gradient descent for nonconvex minimization
- Consistent learning by composite proximal thresholding
- A three-operator splitting scheme and its optimization applications
- A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
- An accelerated semi-proximal ADMM with applications to multi-block sparse optimization problems
- Proximal alternating direction method of multipliers with convex combination proximal centers
- Accelerating preconditioned ADMM via degenerate proximal point mappings
- On the analysis of semismooth Newton-type methods for composite optimization
- Doubly robust logistic regression for image classification
- Understanding the Douglas-Rachford splitting method through the lenses of Moreau-type envelopes
- Inertial reflected Krasnosel’ski-Mann iteration with applications to monotone inclusion problems
- An augmented Lagrangian primal-dual semismooth Newton method for multi-block composite optimization
- Complexity of the relaxed Peaceman-Rachford splitting method for the sum of two maximal strongly monotone operators
- The generalized proximal point algorithm with step size 2 is not necessarily convergent
- Using filter methods to guide convergence for ADMM, with applications to nonnegative matrix factorization problems
- Pointwise and ergodic convergence rates of a variable metric proximal alternating direction method of multipliers
- Tikhonov regularization of monotone operator flows not only ensures strong convergence of the trajectories but also speeds up the vanishing of the residuals
- Understanding the ADMM algorithm via high-resolution differential equations
- Convergence analysis of multi-block symmetric two-step inertial ADMM for nonconvex consensus problem
- Nonexpansive mappings in two-time-scale stochastic approximation: finite-time analysis
- Asymptotic linear convergence of ADMM for isotropic TV norm compressed sensing
- Fast forward-backward splitting for monotone inclusions with a convergence rate of the tangent residual of o(1/k)
- Continuous dynamics related to monotone inclusions and non-smooth optimization problems
This page was built for publication: Convergence rate analysis of several splitting schemes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5350476)
