On non-ergodic convergence rate of Douglas–Rachford alternating direction method of multipliers

By Bingsheng He, Xiaoming Yuan. 2015

337 citations recorded by the source corpus.

Subfields: Applied Mathematics, Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Mechanics

In Computer Vision and Pattern Recognition

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).”
Nuclear Norm Based Matrix Regression with Applications to Face Recognition with Occlusion and Illumination Changes (2014, methodology): “Without this strong convexity assumption, He and Yuan [47] presented the most general result to date of O 1=k ð Þ convergence rate for ADMM.”
Fast Alternating Direction Optimization Methods (2014, background): “In the case that the number of accelerated iterations is finite, then after the final accelerated iteration each pair of restart and unaccelerated iterations is equivalent to a single iteration of the original unaccelerated ADMM (Algorithm 1) for which convergence is known [25].”
Towards an optimal stochastic alternating direction method of multipliers (2014, background): “As in (He & Yuan, 2012), Ouyang et al. (2013) also use this variational characterization of optimality and seek to bound it in expectation.”
Stochastic Alternating Direction Method of Multipliers (2013, background): “By contrast, recent research (He & Yuan, 2012a;b; Wang & Banerjee, 2012) only show the convergence of ADMM indirectly in terms of the satisfaction of variational inequalities.”
An introduction to continuous optimization for imaging (2016, background): “…to be found in the literature, from the thesis of Eckstein (1989) to more recent 226 A. Chambolle and T. Pock convergence analyses (with rates) such as that of Nishihara et al. (2015) (Shefi and Teboulle 2014, He and Yuan 2015b, He and Yuan 2015c, Goldstein, O’Donoghue, Setzer and Baraniuk 2014).”
On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers (2016, background): “The work [24] shows that ‖uk − uk+1‖2, where uk := (xk, y,λ), of the ADM converges at O(1/k).”
Large Scale Distributed Sparse Precision Estimation (2013, methodology): “First, we propose an inexact ADMM [27, 12] algorithm targeted to CLIME, where each step is either elementwise parallel or involves suitable matrix multiplications.”
SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD (2018, background): “2] and to the following selected resources, which are by no means comprehensive: [44, 80, 83, 89, 99, 105, 106].”
Parallel Multi-Block ADMM with o(1 / k) Convergence (2013, positive): “Inspired by [18], we provide a much shorter proof for (5.9) than the one in [18].”
Training Neural Networks Without Gradients: A Scalable ADMM Approach (2016, background): “The convergence of ADMM is fairly well understood for convex problems involving only two separate variable blocks (He & Yuan, 2015).”
Convergence Rate Analysis of Several Splitting Schemes (2014, background): “literature, the majority are given in terms of somewhat awkward quantities, such as the fixed-point residual (FPR) (the squared distance between two consecutive iterates) and the violation to a Lagrangian-type optimality condition (variational inequalities/duality gaps) [12,7,19,32,26,17,30].”
Unwrapping ADMM: Efficient Distributed Computing via Transpose Reduction (2015, methodology): “A more recent result due to He and Yuan (He & Yuan, 2012), provides a global convergence rate for the method.”