On the O(1/n) Convergence Rate of the Douglas-Rachford Alternating Direction Method

By Bingsheng He, Xiaoming Yuan. 2012

996 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Physics

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 Computer Vision and Pattern Recognition

In Mathematical Physics

Citations in the corpus

GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, background): “First, it worth mentioning that the convergence rate of Gauss-Seidel ADMM for sum of two separable convex functions has been studied in (Lions and Mercier, 1979; He and Yuan, 2012, 2015).”
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers (2013, methodology): “In this paper, we focus on the more general formulation (1) and propose an asynchronous decentralized algorithm based on the classical Alternating Direction Method of Multipliers (ADMM) (see [2], [3], [4], [5], [13] for convergence analysis of classical ADMM, and also [8], [11] for its applications ”
Proximal Algorithms (2013, methodology): “In the image processing literature, it is known as the split inexact Uzawa method [80, 205, 204, 104].”
Quantized consensus ADMM for multi-agent distributed optimization (2015, background): “Proofs can be found in [20], [21], [23].”
Tight global linear convergence rate bounds for Douglas–Rachford splitting (2015, background): “ng been known that Douglas-Rachford splitting converges under quite mild assumptions, see [13, 24, 12]. However, the rate of convergence in the general case has just recently been shown to be O(1/k), [19, 9, 7]. For general maximal monotone operator problems, where one of the operators is strongly m”
Parallel Multi-Block ADMM with o(1 / k) Convergence (2013, positive): “The analysis is based on bounding the error ‖uk − u∗‖2G and estimating its decrease, motivated by the works [12,21,23].”
On the linear convergence of the alternating direction method of multipliers (2012, background): “ethod [13–15] for ﬁnding a zero of the sum of two maximal monotone operators. It is known that in this case every limit point of the iterates is an optimal solution of the problem. The recent work of [21,22,26] have shown that, under some additional assumptions, the objective values generated by the”
Asynchronous Distributed ADMM for Consensus Optimization (2014, background): “…“the curse of the last reducer” (Suri & Vassilvitskii, 2011)) is also widely known in MapReduce, which requires a similar full synchronization in its reduce step. algorithm reduces to a synchronous one, its convergence rate also reduces to the standard O( 1T ) rate for ADMM (He & Yuan, 2012).”
Adaptive Consensus ADMM for Distributed Optimization (2017, methodology): “ADMM is known to have a O (1 /k ) convergence rate under mild conditions for convex problems (He & Yuan, 2012; 2015), while a O (1 /k 2 ) rate is possible when at least one of the functions is strongly convex or smooth (Goldfarb et al., 2013; Goldstein et al., 2014; Kadkhodaie et al., 2015; Tian &…”
Minimization of ℓ1-2 for Compressed Sensing (2015, background): “A recent result on the O(1/n) convergence rate of ADMM was established in [36].”
Convex Optimization for Big Data: Scalable, randomized, and parallel algorithms for big data analytics (2014, methodology): “For the former, we can update z k +1 inexactly by using a single step of the proximal gradient method, which leads to the method shown in Algorithm 4 which was motivated in [19] as a preconditioned variant of ADMM and then analyzed in [20] in a more general framework.”
On non-ergodic convergence rate of Douglas–Rachford alternating direction method of multipliers (2015, methodology): “A first-step work is [10] where we showed a worst-case O(1/k) convergence rate measured by the iteration complexity, where k denotes the iteration counter, for the ADMM scheme (1.”
Reweighted Infrared Patch-Tensor Model With Both Nonlocal and Local Priors for Single-Frame Small Target Detection (2017, methodology): “Algorithm Complexity and Computational Time The proposed model is solved via ADMM, which has been proved a O(1/k) convergence [51], [52].”
Global Convergence of ADMM in Nonconvex Nonsmooth Optimization (2015, background): “For convex problems, its convergence was established first in [14] and its convergence rates given in [18,11,10] in different settings.”
Randomized First-Order Methods for Saddle Point Optimization (2014, neutral): “, [3, 6, 13, 21, 35] for detailed reviews on the relationship between the primal-dual methods and other algorithms, as well as recent theoretical developments).”
On Full Jacobian Decomposition of the Augmented Lagrangian Method for Separable Convex Programming (2015, methodology): “The technique of analysis is motivated by our recent result in [21].”