Convergence Rate Analysis of Several Splitting Schemes

By Damek Davis, Wotao Yin. 2014

289 citations recorded by the source corpus.

Operator-splitting schemes are iterative algorithms for solving many types of numerical problems. A lot is known about these methods: they converge, and in many cases we know how quickly they converge. But when they are applied to optimization problems, there is a gap in our understanding: The theoretical speed of operator-splitting schemes is nearly always measured in the ergodic sense, but ergodic operator-splitting schemes are rarely used in practice. In this chapter, we tackle the discrepancy between theory and practice and uncover fundamental limits of a class of operator-splitting schemes. Our surprising conclusion is that the relaxed Peaceman-Rachford splitting algorithm, a version of the Alternating Direction Method of Multipliers (ADMM), is nearly as fast as the proximal point algorithm in the ergodic sense and nearly as slow as the subgradient method in the nonergodic sense. A large class of operator-splitting schemes extend from the relaxed Peaceman-Rachford splitting algorithm. Our results show that this class of operator-splitting schemes is also nearly as slow as the subgradient method. The tools we create in this chapter can also be used to prove nonergodic convergence rates of more general splitting schemes, so they are interesting in their own right.

Subfields: Computational Mechanics, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/aa97d4e589190a107d63e50d611715fe8e7f0486

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

Citations in the corpus

LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning (2018, background): “(74) Using the implications of summable sequences in (Davis and Yin, 2016, Lemma 3), the theorem follows.”
An introduction to continuous optimization for imaging (2016, background): “Some of these studies (Shefi and Teboulle 2014, Davis and Yin 2014b) relate the algorithm, and linearized variants, to the primal–dual approach discussed in Section 5.1; we will see indeed that these methods belong to the same class.”
Self Equivalence of the Alternating Direction Method of Multipliers (2014, methodology): “The convergence analysis of ADM, such as conditions for sublinear or linear convergence, involves many different scenarios [4–6].”
Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems (2014, background): “Under the same conditions, several recent works [20, 21, 22] have shown that the ADMM converges with the sublinear rate of O((1)t ) or o(1t ), and it converges with a rate O( 1 t2 ) when properly accelerated [23, 24].”
Operator Splitting for a Homogeneous Embedding of the Linear Complementarity Problem (2020, background): “Moreover, approaches relying on DR splitting automatically beneﬁt from the guaranteed o (1 /k ) bound on the convergence rate [32, 16].”
A Dynamical System Associated with the Fixed Points Set of a Nonexpansive Operator (2014, background): “ done in terms of the ﬁxed point residual function t → kTx(t) − x(t)k and of t → kx˙(t)k. Notice that convergence rates for the discrete iteratively generated algorithm (10) have been investigated in [15,16,18]. 7 Theorem 10 Let T : H → H be a nonexpansive mapping such that FixT 6= ∅, λ : [0,+∞) → [”
ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates (2015, unknown): “Finer convergence rates follow from [17,18].”
A New Primal–Dual Algorithm for Minimizing the Sum of Three Functions with a Linear Operator (2016, background): “3) We have the following convergence rate and 22), and we have Thus, (cid:107) ( z k , s k ) − ( z ∗ , s ∗ ) 2 I , M is monotonically decreasing as long as 2) Summing up (29) from 0 to ∞ , we have and thus the sequence ( 3) The o (1 /k ) convergence rate follows from [14, Theorem 1].”
A Three-Operator Splitting Scheme and its Optimization Applications (2015, methodology): “The following averaging scheme is typically used in the literature for splitting schemes [24,22,4]:”
SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD (2018, background): “In 2015, Damek Davis and Wotao Yin showed that DR might converge arbitrarily slowly in the infinite dimensional setting [66].”
From Local SGD to Local Fixed Point Methods for Federated Learning (2020, background): “(iv) and (v) come from Theorem 1 in (Davis & Yin, 2016).”