Parallel Multi-Block ADMM with o(1 / k) Convergence
Tóm tắt
This paper introduces a parallel and distributed algorithm for solving the following minimization problem with linear constraints: $$\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}$$ where $$N \ge 2$$ , $$f_i$$ are convex functions, $$A_i$$ are matrices, and $${\mathcal {X}}_i$$ are feasible sets for variable $$\mathbf{x}_i$$ . 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 $$A_i$$ 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 $$A_i$$ ). In the latter case, certain proximal terms can let the subproblem be solved in more flexible and efficient ways. We show that $$\Vert {\mathbf {x}}^{k+1} - {\mathbf {x}}^k\Vert _M^2$$ 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.
Tài liệu tham khảo
citation_title=The multivariate spline method for numerical solution of partial differential equations and scattered data interpolation; citation_inbook_title=Wavelets and Splines; citation_publication_date=2006; citation_pages=24-74; citation_id=CR1; citation_author=G Awanou; citation_author=MJ Lai; citation_author=P Wenston; citation_publisher=Nashboro Press
citation_title=Parallel and Distributed Computation: Numerical Methods; citation_publication_date=1997; citation_id=CR2; citation_author=D Bertsekas; citation_author=J Tsitsiklis; citation_publisher=Athena Scientific
citation_journal_title=Found. Trends Mach. Learn.; citation_title=Distributed optimization and statistical learning via the alternating direction method of multipliers; citation_author=S Boyd, N Parikh, E Chu, B Peleato, J Eckstein; citation_volume=3; citation_issue=1; citation_publication_date=2011; citation_pages=1-122; citation_doi=10.1561/2200000016; citation_id=CR3
citation_journal_title=Ann. Stat.; citation_title=Latent variable graphical model selection via convex optimization; citation_author=V Chandrasekaran, PA Parrilo, AS Willsky; citation_volume=40; citation_issue=4; citation_publication_date=2012; citation_pages=1935-1967; citation_doi=10.1214/11-AOS949; citation_id=CR4
citation_journal_title=Math. Program.; citation_title=The direct extension of admm for multi-block convex minimization problems is not necessarily convergent; citation_author=C Chen, BS He, YY Ye, XM Yuan; citation_volume=155; citation_issue=1; citation_publication_date=2016; citation_pages=57-79; citation_doi=10.1007/s10107-014-0826-5; citation_id=CR5
citation_journal_title=Abstr. Appl. Anal.; citation_title=On the convergence analysis of the alternating direction method of multipliers with three blocks; citation_author=C Chen, Y Shen, Y You; citation_volume=2013; citation_publication_date=2013; citation_pages=183961; citation_id=CR6
citation_journal_title=Math. Program.; citation_title=A proximal-based decomposition method for convex minimization problems; citation_author=G Chen, M Teboulle; citation_volume=64; citation_issue=1; citation_publication_date=1994; citation_pages=81-101; citation_doi=10.1007/BF01582566; citation_id=CR7
citation_journal_title=SIAM J. Optim.; citation_title=A generalized proximal point algorithm and its convergence rate; citation_author=E Corman, XM Yuan; citation_volume=24; citation_issue=4; citation_publication_date=2014; citation_pages=1614-1638; citation_doi=10.1137/130940402; citation_id=CR8
Davis, D., Yin, W.: Convergence rate analysis of several splitting schemes. UCLA CAM Report, pp. 14–51 (2014)
Davis, D., Yin, W.: Convergence rates of relaxed peaceman–rachford and admm under regularity assumptions. UCLA CAM Report, pp. 14–58 (2014)
Davis, D., Yin, W.: A three-operator splitting scheme and its optimization applications. UCLA CAM Report, pp. 15–13 (2015)
citation_journal_title=J. Sci. Comput.; citation_title=On the global and linear convergence of the generalized alternating direction method of multipliers; citation_author=W Deng, W Yin; citation_volume=66; citation_issue=3; citation_publication_date=2016; citation_pages=889-916; citation_doi=10.1007/s10915-015-0048-x; citation_id=CR12
citation_journal_title=Oper. Res.; citation_title=Generalized lagrange multiplier method for solving problems of optimum allocation of resources; citation_author=H Everett; citation_volume=11; citation_issue=3; citation_publication_date=1963; citation_pages=399-417; citation_doi=10.1287/opre.11.3.399; citation_id=CR13
citation_journal_title=Comput. Math. Appl.; citation_title=A dual algorithm for the solution of nonlinear variational problems via finite element approximation; citation_author=D Gabay, B Mercier; citation_volume=2; citation_issue=1; citation_publication_date=1976; citation_pages=17-40; citation_doi=10.1016/0898-1221(76)90003-1; citation_id=CR14
Glowinski, R.: Numerical methods for nonlinear variational problems. Springer Series in Computational Physics. Springer, Berlin (1984)
Glowinski, R., Marrocco, A.: Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité, d’une classe de problèmes de Dirichlet non linéaires. Laboria (1975)
citation_journal_title=SIAM J. Imaging Sci.; citation_title=Fast alternating direction optimization methods; citation_author=T Goldstein, B O’Donoghue, S Setzer, R Baraniuk; citation_volume=7; citation_issue=3; citation_publication_date=2014; citation_pages=1588-1623; citation_doi=10.1137/120896219; citation_id=CR17
citation_journal_title=J. Optim. Theory Appl.; citation_title=A note on the alternating direction method of multipliers; citation_author=D Han, X Yuan; citation_volume=155; citation_issue=1; citation_publication_date=2012; citation_pages=227-238; citation_doi=10.1007/s10957-012-0003-z; citation_id=CR18
citation_journal_title=Appl. Math. Optim.; citation_title=A class of projection and contraction methods for monotone variational inequalities; citation_author=BS He; citation_volume=35; citation_issue=1; citation_publication_date=1997; citation_pages=69-76; citation_doi=10.1007/BF02683320; citation_id=CR19
citation_journal_title=Comput. Optim. Appl.; citation_title=Parallel splitting augmented lagrangian methods for monotone structured variational inequalities; citation_author=BS He; citation_volume=42; citation_issue=2; citation_publication_date=2009; citation_pages=195-212; citation_doi=10.1007/s10589-007-9109-x; citation_id=CR20
citation_journal_title=SIAM J. Optim.; citation_title=On full Jacobian decomposition of the augmented lagrangian method for separable convex programming; citation_author=BS He, LS Hou, XM Yuan; citation_volume=25; citation_publication_date=2015; citation_pages=2274-2312; citation_doi=10.1137/130922793; citation_id=CR21
citation_journal_title=SIAM J. Optim.; citation_title=Alternating direction method with gaussian back substitution for separable convex programming; citation_author=BS He, M Tao, XM Yuan; citation_volume=22; citation_issue=2; citation_publication_date=2012; citation_pages=313-340; citation_doi=10.1137/110822347; citation_id=CR22
citation_journal_title=SIAM J. Numer. Anal.; citation_title=On the
convergence rate of the Douglas-Rachford alternating direction method; citation_author=BS He, XM Yuan; citation_volume=50; citation_issue=2; citation_publication_date=2012; citation_pages=700-709; citation_doi=10.1137/110836936; citation_id=CR23
citation_journal_title=Numer. Math.; citation_title=On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers; citation_author=BS He, XM Yuan; citation_volume=130; citation_issue=3; citation_publication_date=2015; citation_pages=567-577; citation_doi=10.1007/s00211-014-0673-6; citation_id=CR24
Hong, M., Luo, Z.Q.: On the Linear Convergence of the Alternating Direction Method of Multipliers.
arXiv:1208.3922
(2012)
Li, M., Sun, D., Toh, K.C.: A Convergent 3-Block Semi-Proximal ADMM for Convex Minimization Problems with One Strongly Convex Block.
arXiv:1410.7933
[math] (2014)
Lin, T., Ma, S., Zhang, S.: On the Convergence Rate of Multi-Block ADMM.
arXiv:1408.4265
[math] (2014)
citation_journal_title=SIAM J. Numer. Anal.; citation_title=Splitting algorithms for the sum of two nonlinear operators; citation_author=PL Lions, B Mercier; citation_volume=16; citation_issue=6; citation_publication_date=1979; citation_pages=964-979; citation_doi=10.1137/0716071; citation_id=CR28
citation_journal_title=IEEE Trans. Signal Process.; citation_title=D-admm: a communication-efficient distributed algorithm for separable optimization; citation_author=JF Mota, JM Xavier, PM Aguiar, M Puschel; citation_volume=61; citation_publication_date=2013; citation_pages=2718-2723; citation_doi=10.1109/TSP.2013.2254478; citation_id=CR29
citation_journal_title=Math. Program.; citation_title=Smooth minimization of non-smooth functions; citation_author=Y Nesterov; citation_volume=103; citation_issue=1; citation_publication_date=2005; citation_pages=127-152; citation_doi=10.1007/s10107-004-0552-5; citation_id=CR30
citation_journal_title=IEEE Trans. Pattern Anal. Mach. Intell.; citation_title=RASL: robust alignment by sparse and low-rank decomposition for linearly correlated images; citation_author=Y Peng, A Ganesh, J Wright, W Xu, Y Ma; citation_volume=34; citation_publication_date=2012; citation_pages=2233-2246; citation_doi=10.1109/TPAMI.2011.282; citation_id=CR31
Peng, Z., Yan, M., Yin, W.: Parallel and distributed sparse optimization. In: IEEE Asilomar Conference on Signals Systems and Computers (2013)
citation_title=Convex Analysis; citation_publication_date=1997; citation_id=CR33; citation_author=RT Rockafellar; citation_publisher=Princeton University Press
citation_title=Minimization Methods for Non-differentiable Functions; citation_publication_date=1985; citation_id=CR34; citation_author=NZ Shor; citation_author=KC Kiwiel; citation_author=A Ruszcayski; citation_publisher=Springer
citation_journal_title=SIAM J. Optim.; citation_title=Recovering low-rank and sparse components of matrices from incomplete and noisy observations; citation_author=M Tao, XM Yuan; citation_volume=21; citation_issue=1; citation_publication_date=2011; citation_pages=57-81; citation_doi=10.1137/100781894; citation_id=CR35
citation_journal_title=Pac. J. Optim.; citation_title=Solving multiple-block separable convex minimization problems using two-block alternating direction method of multipliers; citation_author=XF Wang, MY Hong, SQ Ma, ZQ Luo; citation_volume=11; citation_issue=4; citation_publication_date=2015; citation_pages=57-81; citation_id=CR36
citation_journal_title=SIAM J. Sci. Comput.; citation_title=Alternating direction algorithms for
-problems in compressive sensing; citation_author=JF Yang, Y Zhang; citation_volume=33; citation_issue=1; citation_publication_date=2011; citation_pages=250-278; citation_doi=10.1137/090777761; citation_id=CR37
citation_journal_title=J. Sci. Comput.; citation_title=A unified primal-dual algorithm framework based on Bregman iteration; citation_author=X Zhang, M Burger, S Osher; citation_volume=46; citation_issue=1; citation_publication_date=2011; citation_pages=20-46; citation_doi=10.1007/s10915-010-9408-8; citation_id=CR38