Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
arXiv:1407.5210
Abstract
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 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 this paper, we provide a comprehensive convergence rate analysis of the Douglas-Rachford splitting (DRS), Peaceman-Rachford splitting (PRS), and alternating direction method of multipliers (ADMM) algorithms under various regularity assumptions including strong convexity, Lipschitz differentiability, and bounded linear regularity. The main consequence of this work is that relaxed PRS and ADMM automatically adapt to the regularity of the problem and achieve convergence rates that improve upon the (tight) worst-case rates that hold in the absence of such regularity. All of the results are obtained using simple techniques.
arXiv comment40 pages, 3 tables
References in corpus (2)
Cited by in corpus (18)
- A General Analysis of the Convergence of ADMM
- A Three-Operator Splitting Scheme and its Optimization Applications
- Adaptive Consensus ADMM for Distributed Optimization
- On the Sublinear Convergence Rate of Multi-Block ADMM
- Douglas-Rachford Splitting: Complexity Estimates and Accelerated Variants
- SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm
- Generalized Kalman Smoothing: Modeling and Algorithms
- Linear convergence of the generalized PPA and several splitting methods for the composite inclusion problem
- Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
- On the Duality Gap Convergence of ADMM Methods
- Alternating Direction Method of Multipliers for Linear Inverse Problems
- A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
- Tuning Over-Relaxed ADMM
- Local Convergence Properties of Douglas--Rachford and ADMM
- Parameter Insensitivity in ADMM-Preconditioned Solution of Saddle-Point Problems
- Activity Identification and Local Linear Convergence of Douglas--Rachford/ADMM under Partial Smoothness
- Acceleration of saddle-point methods in smooth cases
- Complexity of the relaxed Peaceman-Rachford splitting method for the sum of two maximal strongly monotone operators