Parallel Multi-Block ADMM with o(1 / k) Convergence

By Wei Deng, Ming-Jun Lai, Zhimin Peng, Wotao Yin. 2013

433 citations recorded by the source corpus.

This paper introduces a parallel and distributed algorithm for solving the following minimization problem with linear constraints: minimizef1(x1)+⋯+fN(xN)subject toA1x1+⋯+ANxN=c,x1∈X1,…,xN∈XN,\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \text {minimize} ~~&f_1(\mathbf{x}_1) + \cdots + f_N(\mathbf{x}_N)\\ \text {subject to}~~&A_1 \mathbf{x}_1 ~+ \cdots + A_N\mathbf{x}_N =c,\\&\mathbf{x}_1\in {\mathcal {X}}_1,~\ldots , ~\mathbf{x}_N\in {\mathcal {X}}_N, \end{aligned}$$\end{document}where N≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N \ge 2$$\end{document}, fi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_i$$\end{document} are convex functions, Ai\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A_i$$\end{document} are matrices, and Xi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {X}}_i$$\end{document} are feasible sets for variable xi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf{x}_i$$\end{document}. Our algorithm extends the alternating direction method of multipliers (ADMM) and decomposes the original problem into N smaller subproblems and solves them in parallel at each iteration. This paper shows that the classic ADMM can be extended to the N-block Jacobi fashion and preserve convergence in the following two cases: (i) matrices Ai\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A_i$$\end{document} are mutually near-orthogonal and have full column-rank, or (ii) proximal terms are added to the N subproblems (but without any assumption on matrices Ai\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A_i$$\end{document}). In the latter case, certain proximal terms can let the subproblem be solved in more flexible and efficient ways. We show that ‖xk+1-xk‖M2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Vert {\mathbf {x}}^{k+1} - {\mathbf {x}}^k\Vert _M^2$$\end{document} converges at a rate of o(1 / k) where M is a symmetric positive semi-definte matrix. Since the parameters used in the convergence analysis are conservative, we introduce a strategy for automatically tuning the parameters to substantially accelerate our algorithm in practice. We implemented our algorithm (for the case ii above) on Amazon EC2 and tested it on basis pursuit problems with >300 GB of distributed data. This is the first time that successfully solving a compressive sensing problem of such a large scale is reported.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

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

In Numerical Analysis

Citations in the corpus

Harnessing Wireless Channels for Scalable and Privacy-Preserving Federated Learning (2020, positive): “Compared to the existing analog FL algorithms [9–11] based on first-order methods such as GD and SGD, A-FADMM is a second-order method providing faster convergence [15, 16].”
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, positive): “Proof The proof of Lemma 3 follows the same lines of the proof in (Deng et al., 2017, Lemma 1.2).”
A Proximal Gradient Algorithm for Decentralized Composite Optimization (2015, neutral): “Parts of it appeared in recent works [30], [31].”
Energy-Efficient UAV-Assisted Mobile Edge Computing: Resource Allocation and Trajectory Optimization (2020, neutral): “τ 2 ||xi − xi ||2 is further combined in the primal problem of the current algorithm [35].”
Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges (2022, neutral): “Some examples are Decentralized Gradient Descent (DGD) [104], decentralized Alternating Direction Method of Multipliers (ADMM) [105], EXTRA [106], and ADMM based on Jacobi-Proximal [107].”
On non-ergodic convergence rate of Douglas–Rachford alternating direction method of multipliers (2015, positive): “2 in [2], we can immediately refine the worst-case convergence rate in Theorem 6.”
Parallel Direction Method of Multipliers (2014, positive): “Encouraged by the success of ADMM with two blocks, ADMM has also been extended to solve the problem with multiple blocks [15, 14, 10, 17, 13, 7].”
Exogenous Cost Allocation in Peer-to-Peer Electricity Markets (2019, positive): “Several extensions and convergence rate improvements have been proposed in [20]–[23].”
Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning (2019, positive): “On the other hand, primal-dual decomposition methods are shown to be effective in enabling distributed optimization [24], [34]–[38], among which ADMM is a compelling solution that often provides fast convergence rate with low complexity [34], [35], [38].”
ADMM Based Privacy-Preserving Decentralized Optimization (2017, positive): “Despite enabling new capabilities in privacy protection (with the assistance of partially homomorphic Paillier encryption), introducing time-varying penalty matrix also reduces convergence rate to O(1/t), in contrast to the o(1/t) rate in [44].”
QoE and power efficiency tradeoff for fog computing networks with fog node cooperation (2017, positive): “where ρ is the augmented Lagrangian parameter and Λ is the matrix of the dual variables [16].”
A distributed block coordinate descent method for training $l_1$ regularized linear classifiers (2014, neutral): “Several variants of global convergence and rate of convergence (e.g., O( 1k )) results exist under different weak/strong convexity assumptions on the two terms of the objective function (Deng and Yin, 2012; Deng et al., 2013).”