The DOI matches its Crossref record; 43 of the 43 references it cites were found in a registry or an index.
On the linear convergence of the alternating direction method of multipliers
Open accessAbstract
We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global R-linear convergence of the ADMM for minimizing the sum of any number of convex separable functions, assuming that a certain error bound condition holds true and the dual stepsize is sufficiently small. Such an error bound condition is satisfied for example when the feasible set is a compact polyhedron and the objective function consists of a smooth strictly convex function composed with a linear mapping, and a nonsmooth ℓ1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _1$$\end{document} regularizer. This result implies the linear convergence of the ADMM for contemporary applications such as LASSO without assuming strong convexity of the objective function.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000016 · Cited by 17,075
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
Model Selection and Estimation in Regression with Grouped Variables
Yuan, M., & Lin, Y. (2006) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2005.00532.x · Cited by 7,261
Iterative Solution of Nonlinear Equations in Several Variables
Ortega, J. M., & Rheinboldt, W. C. (2000) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719468 · Cited by 6,860
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
Iterative Solution of Nonlinear Equations in Several Variables
I., E., Ortega, J. M., & Rheinboldt, W. C. (1971) · Mathematics of Computation · doi:10.2307/2004942 · Cited by 4,408
Eckstein, J., & Bertsekas, D. P. (1992) · Mathematical Programming · doi:10.1007/bf01581204 · Cited by 2,791
Bregman, L. M. (1967) · USSR Computational Mathematics and Mathematical Physics · doi:10.1016/0041-5553(67)90040-7 · Cited by 2,618
Cited by
LIME: Low-Light Image Enhancement via Illumination Map Estimation
Guo, X., Li, Y., & Ling, H. (2017) · IEEE Transactions on Image Processing · doi:10.1109/tip.2016.2639450 · Cited by 2,998
On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
Shi, W., Ling, Q., Yuan, K., Wu, G., & Yin, W. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2304432 · Cited by 820
Fast Alternating Direction Optimization Methods
Goldstein, T., O'Donoghue, B., Setzer, S., & Baraniuk, R. (2014) · SIAM Journal on Imaging Sciences · doi:10.1137/120896219 · Cited by 785
Robust Multi-View Spectral Clustering via Low-Rank and Sparse Decomposition
Xia, R., Pan, Y., Du, L., & Yin, J. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.8950 · Cited by 713
On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers
Deng, W., & Yin, W. (2016) · Journal of Scientific Computing · doi:10.1007/s10915-015-0048-x · Cited by 650
Multi-view low-rank sparse subspace clustering
Brbić, M., & Kopriva, I. (2018) · Pattern Recognition · doi:10.1016/j.patcog.2017.08.024 · Cited by 483
Parallel Multi-Block ADMM with o(1 / k) Convergence
Deng, W., Lai, M.-J., Peng, Z., & Yin, W. (2017) · Journal of Scientific Computing · doi:10.1007/s10915-016-0318-2 · Cited by 455
Multi-Agent Distributed Optimization via Inexact Consensus ADMM
Chang, T.-H., Hong, M., & Wang, X. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2367458 · Cited by 444
Self-citationCommunication-Efficient Distributed Optimization using an Approximate Newton-type Method
Shamir, O., Srebro, N., & Zhang, T. (2013) · arXiv · doi:10.48550/arxiv.1312.7853 · Cited by 424
“A similar dependence occurs with other recently-proposed algorithms for distributed optimization (e.g. Yang, 2013; Mahajan et al., 2013; Dekel et al., 2012; Cotter et al., 2011; Duchi et al., 2012).”
BackgroundMethodKomodakis, N., & Pesquet, J.-C. (2015) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2377273 · Cited by 419
D-ADMM: A Communication-Efficient Distributed Algorithm for Separable Optimization
Mota, J. F. C., Xavier, J. M. F., Aguiar, P. M. Q., & Puschel, M. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2254478 · Cited by 363
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers
Wei, E., & Ozdaglar, A. (2013) · 2013 IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2013.6736937 · Cited by 342
Exogenous Cost Allocation in Peer-to-Peer Electricity Markets
Baroche, T., Pinson, P., Latimier, R. L. G., & Ahmed, H. B. (2019) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2019.2896654 · Cited by 314
An improved residual-based convolutional neural network for very short-term wind power forecasting
Yildiz, C., Acikgoz, H., Korkmaz, D., & Budak, U. (2021) · Energy Conversion and Management · doi:10.1016/j.enconman.2020.113731 · Cited by 258
Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms
Jakovetic, D., Moura, J. M. F., & Xavier, J. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2363299 · Cited by 123
Distributed stochastic optimization and learning
Shamir, O., & Srebro, N. (2014) · 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2014.7028543 · Cited by 120
Pang, G., Cao, L., Chen, L., Lian, D., & Liu, H. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11692 · Cited by 59
Iutzeler, F., Bianchi, P., Ciblat, P., & Hachem, W. (2014) · 53rd IEEE Conference on Decision and Control · doi:10.1109/cdc.2014.7040177 · Cited by 10
Metadata
- Authors
- Hong, M., & Luo, Z.-Q.
- Venue
- Mathematical Programming
- Published
- 2016-07-06
- Volume
- 162
- Issue
- 1-2
- Pages
- 165-199
- ISSN
- 0025-5610 (ISSN-L)
- 1436-4646
- OpenAlex
- W2105693192
- Cited by
- 690
- References
- 43
- FWCI
- 75.62
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.