Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
Abstract
Many problems of recent interest in statistics and machine learning can be posed in the framework of convex optimization. Due to the explosion in size and complexity of modern datasets, it is increasingly important to be able to solve problems with a very large number of features or training examples. As a result, both the decentralized collection or storage of these datasets as well as accompanying distributed solution methods are either necessary or at least highly desirable. In this review, we argue that the alternating direction method of multipliers is well suited to distributed convex optimization, and in particular to large-scale problems arising in statistics, machine learning, and related areas. The method was developed in the 1970s, with roots in the 1950s, and is equivalent or closely related to many other algorithms, such as dual decomposition, the method of multipliers, Douglas–Rachford splitting, Spingarn's method of partial inverses, Dykstra's alternating projections, Bregman iterative algorithms for ℓ1 problems, proximal methods, and others. After briefly surveying the theory and history of the algorithm, we discuss applications to a wide variety of statistical and machine learning problems of recent interest, including the lasso, sparse logistic regression, basis pursuit, covariance selection, support vector machines, and many others. We also discuss general distributed optimization, extensions to the nonconvex setting, and efficient implementation, including some details on distributed MPI and Hadoop MapReduce implementations.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
With variable splitting techniques, denoiser prior can be plugged in as a modular part of model-based optimization methods to solve other inverse problems.
“Recent works have revealed that, with the aid of variable splitting techniques, denoiser prior can be plugged in as a modular part of model-based optimization methods to solve other inverse problems (e.g., deblurring).”
From Learning Deep CNN Denoiser Prior for Image Restoration (2017) · cites this paper as [5]
Cites
Regression shrinkage and selection via the lasso
Tibshirani, R. (1996) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1996.tb02080.x · Cited by 51,482 · see citing works
Distributed Subgradient Methods for Multi-Agent Optimization
Nedic, A., & Ozdaglar, A. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2008.2009515 · Cited by 3,719 · see citing works
Distributed asynchronous deterministic and stochastic gradient optimization algorithms
Tsitsiklis, J., Bertsekas, D., & Athans, M. (1986) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1986.1104412 · Cited by 1,967 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Machine learning: Trends, perspectives, and prospects
Jordan, M. I., & Mitchell, T. M. (2015) · Science · doi:10.1126/science.aaa8415 · Cited by 9,955 · see citing works
Deep Convolutional Neural Network for Inverse Problems in Imaging
Jin, K. H., McCann, M. T., Froustey, E., & Unser, M. (2017) · IEEE Transactions on Image Processing · doi:10.1109/tip.2017.2713099 · Cited by 2,529 · see citing works
Learning Deep CNN Denoiser Prior for Image Restoration
Zhang, K., Zuo, W., Gu, S., & Zhang, L. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.300 · Cited by 2,116 · see citing works
Chen, C. L. P., & Liu, Z. (2018) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2017.2716952 · Cited by 1,957 · see citing works
Challenges of Big Data analysis
Fan, J., Han, F., & Liu, H. (2014) · National Science Review · doi:10.1093/nsr/nwt032 · Cited by 1,482 · see citing works
Discriminative Correlation Filter with Channel and Spatial Reliability
Lukezic, A., Vojir, T., Zajc, L. C., Matas, J., & Kristan, M. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.515 · Cited by 1,153 · see citing works
Plug-and-Play priors for model based reconstruction
Venkatakrishnan, S. V., Bouman, C. A., & Wohlberg, B. (2013) · 2013 IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2013.6737048 · Cited by 1,178 · see citing works
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
Nedić, A., Olshevsky, A., & Shi, W. (2017) · SIAM Journal on Optimization · doi:10.1137/16m1084316 · Cited by 1,073 · see citing works
All you need to know about model predictive control for buildings
Drgoňa, J., Arroyo, J., Cupeiro Figueroa, I., Blum, D., Arendt, K., Kim, D., Ollé, E. P., Oravec, J., Wetter, M., Vrabie, D. L., et al. (2020) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2020.09.001 · Cited by 1,020 · see citing works
Plug-and-Play ADMM for Image Restoration: Fixed-Point Convergence and Applications
Chan, S. H., Wang, X., & Elgendy, O. A. (2017) · IEEE Transactions on Computational Imaging · doi:10.1109/tci.2016.2629286 · Cited by 904 · see citing works
Speeding Up Distributed Machine Learning Using Codes
Lee, K., Lam, M., Pedarsani, R., Papailiopoulos, D., & Ramchandran, K. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2736066 · Cited by 829 · see citing works
Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding
O’Donoghue, B., Chu, E., Parikh, N., & Boyd, S. (2016) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-016-0892-3 · Cited by 664 · see citing works
Self-citationImage super-resolution: the techniques, applications, and future
Yue, L., Shen, H., Li, J., Yuan, Q., Zhang, H., & Zhang, L. (2016) · Signal Processing · doi:10.1016/j.sigpro.2016.05.002 · Cited by 554 · see citing works
Cognitive internet of things: A new paradigm beyond connection
Wu, Q., Ding, G., Xu, Y., Feng, S., Du, Z., Wang, J., & Long, K. (2014) · IEEE Internet of Things Journal · doi:10.1109/jiot.2014.2311513 · Cited by 550 · see citing works
Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
Chen, Y., Su, L., & Xu, J. (2017) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3154503 · Cited by 390 · see citing works
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 · see citing works
A Crowdsourcing Framework for On-Device Federated Learning
Pandey, S. R., Tran, N. H., Bennis, M., Tun, Y. K., Manzoor, A., & Hong, C. S. (2020) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2020.2971981 · Cited by 318 · see citing works
Review of numerical optimization techniques for meta-device design [Invited]
Campbell, S. D., Sell, D., Jenkins, R. P., Whiting, E. B., Fan, J. A., & Werner, D. H. (2019) · Optical Materials Express · doi:10.1364/ome.9.001842 · Cited by 322 · see citing works
Graph and Total Variation Regularized Low-Rank Representation for Hyperspectral Anomaly Detection
Cheng, T., & Wang, B. (2020) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2019.2936609 · Cited by 266 · see citing works
Liu, M., Yu, F. R., Teng, Y., Leung, V. C. M., & Song, M. (2019) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2018.2885266 · Cited by 233 · see citing works
Yang, Q., Wang, H., Wang, T., Zhang, S., Wu, X., & Wang, H. (2021) · Applied Energy · doi:10.1016/j.apenergy.2021.117026 · Cited by 238 · see citing works
Bringing ai to edge: from deep learning’s perspective
Liu, D., Kong, H., Luo, X., Liu, W., & Subramaniam, R. (2022) · Neurocomputing · doi:10.1016/j.neucom.2021.04.141 · Cited by 171 · see citing works
Learning Based Content Caching and Sharing for Wireless Networks
Song, J., Sheng, M., Quek, T. Q. S., Xu, C., & Wang, X. (2017) · IEEE Transactions on Communications · doi:10.1109/tcomm.2017.2713384 · Cited by 144 · see citing works
Defect Detection in SEM Images of Nanofibrous Materials
Carrera, D., Manganini, F., Boracchi, G., & Lanzarone, E. (2017) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2016.2641472 · Cited by 133 · see citing works
Federated Tensor Factorization for Computational Phenotyping
Kim, Y., Sun, J., Yu, H., & Jiang, X. (2017) · Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/3097983.3098118 · Cited by 128 · see citing works
Modality-correlation-aware sparse representation for RGB-infrared object tracking
Lan, X., Ye, M., Zhang, S., Zhou, H., & Yuen, P. C. (2020) · Pattern Recognition Letters · doi:10.1016/j.patrec.2018.10.002 · Cited by 121 · see citing works
Partial Occlusion Handling for Visual Tracking via Robust Part Matching
Zhang, T., Jia, K., Xu, C., Ma, Y., & Ahuja, N. (2014) · 2014 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2014.164 · Cited by 117 · see citing works
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 · see citing works
Imaging neural activity in the ventral nerve cord of behaving adult Drosophila
Chen, C.-L., Hermans, L., Viswanathan, M. C., Fortun, D., Aymanns, F., Unser, M., Cammarato, A., Dickinson, M. H., & Ramdya, P. (2018) · Nature Communications · doi:10.1038/s41467-018-06857-z · Cited by 84 · see citing works
Hyperspectral Image Unmixing With Endmember Bundles and Group Sparsity Inducing Mixed Norms
Drumetz, L., Meyer, T. R., Chanussot, J., Bertozzi, A. L., & Jutten, C. (2019) · IEEE Transactions on Image Processing · doi:10.1109/tip.2019.2897254 · Cited by 104 · see citing works
Distributed Coordination of Charging Stations Considering Aggregate EV Power Flexibility
Yan, D., Ma, C., & Chen, Y. (2023) · IEEE Transactions on Sustainable Energy · doi:10.1109/tste.2022.3213173 · Cited by 96 · see citing works
Turning a denoiser into a super-resolver using plug and play priors
Brifman, A., Romano, Y., & Elad, M. (2016) · 2016 IEEE International Conference on Image Processing (ICIP) · doi:10.1109/icip.2016.7532589 · Cited by 91 · see citing works
Towards Data Poisoning Attacks in Crowd Sensing Systems
Miao, C., Li, Q., Xiao, H., Jiang, W., Huai, M., & Su, L. (2018) · Proceedings of the Eighteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing · doi:10.1145/3209582.3209594 · Cited by 77 · see citing works
GLMix: Generalized Linear Mixed Models For Large-Scale Response Prediction
Zhang, X., Zhou, Y., Ma, Y., Chen, B.-C., Zhang, L., & Agarwal, D. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939684 · Cited by 71 · see citing works
Protein design via deep learning
Ding, W., Nakai, K., & Gong, H. (2022) · Briefings in Bioinformatics · doi:10.1093/bib/bbac102 · Cited by 66 · see citing works
Rodosthenous, T., Shahrezaei, V., & Evangelou, M. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btaa530 · Cited by 67 · see citing works
Froelicher, D., Troncoso-Pastoriza, J. R., Sousa, J. S., & Hubaux, J.-P. (2020) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2020.2976612 · Cited by 59 · see citing works
EasiEdge: A Novel Global Deep Neural Networks Pruning Method for Efficient Edge Computing
Yu, F., Cui, L., Wang, P., Han, C., Huang, R., & Huang, X. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2020.3034925 · Cited by 58 · see citing works
Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
Gambella, C., & Simonetto, A. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3033139 · Cited by 60 · see citing works
Improving quality of data: IoT data aggregation using device-to-device communications
Sanyal, S., & Zhang, P. (2018) · IEEE Access · doi:10.1109/access.2018.2878640 · Cited by 51 · see citing works
A collective AI via lifelong learning and sharing at the edge
Soltoggio, A., Ben-Iwhiwhu, E., Braverman, V., Eaton, E., Epstein, B., Ge, Y., Halperin, L., How, J., Itti, L., Jacobs, M. A., et al. (2024) · Nature Machine Intelligence · doi:10.1038/s42256-024-00800-2 · Cited by 51 · see citing works
Degradation-Resistant Unfolding Network for Heterogeneous Image Fusion
He, C., Li, K., Xu, G., Zhang, Y., Hu, R., Guo, Z., & Li, X. (2023) · 2023 IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv51070.2023.01159 · Cited by 37 · see citing works
Fast 3D reconstruction method for differential phase contrast X-ray CT
McCann, M. T., Nilchian, M., Stampanoni, M., & Unser, M. (2016) · Optics Express · doi:10.1364/oe.24.014564 · Cited by 28 · see citing works
Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study
Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., & Leymann, F. (2024) · ACM Computing Surveys · doi:10.1145/3620668 · Cited by 22 · see citing works
Harnessing wireless channels for scalable and privacy-preserving federated learning
Elgabli, A., Park, J., Issaid, C. B., & Bennis, M. (2021) · IEEE Transactions on Communications · doi:10.1109/tcomm.2021.3078783 · Cited by 14 · see citing works
DJAM: Distributed Jacobi asynchronous method for learning personal models
Almeida, I., & Xavier, J. (2018) · IEEE Signal Processing Letters · doi:10.1109/lsp.2018.2859596 · Cited by 10 · see citing works
Fused graphical lasso recovers flowering time mutation genes in arabidopsis thaliana
Kapoor, R., Datta, A., & Thomson, M. (2021) · Inventions · doi:10.3390/inventions6030052 · Cited by 5 · see citing works
Understanding and Predicting Weight Loss with Mobile Social Networking Data
Wang, Z., Derr, T., Yin, D., & Tang, J. (2017) · Proceedings of the 2017 ACM on Conference on Information and Knowledge Management · doi:10.1145/3132847.3133019 · Cited by 9 · see citing works
Stochastic proximal gradient consensus over time-varying networks
Hong, M., & Chang, T.-H. (2016) · 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) · doi:10.1109/icassp.2016.7472584 · Cited by 6 · see citing works
A new multiple kernel-based regularization method for identification of delay linear dynamic systems
Chen, X., Mao, Z., & Jia, R. (2020) · Chemometrics and Intelligent Laboratory Systems · doi:10.1016/j.chemolab.2020.103971 · Cited by 5 · see citing works
- Authors
- Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J.
- Affiliations
- Stanford University (US)
- Rutgers, The State University of New Jersey (US)
- Corresponding author
- Boyd, Stephen
- Venue
- Foundations and Trends® in Machine Learning
- Publisher
- Emerald
- Published
- 2011-07-26
- Volume
- 3
- Issue
- 1
- Pages
- 1-122
- ISSN
- 1935-8237 (ISSN-L)
- 1935-8245
- OpenAlex
- W4292363360
- Cited by
- 17,075
- References
- 3
- Citations by year
- 2026: 928 · 2025: 1357 · 2024: 1490 · 2023: 1542 · 2022: 1478 · 2021: 1463 · 2020: 1675 · 2019: 1712 · 2018: 1464 · 2017: 1214 · 2016: 1014 · 2015: 761 · 2014: 543 · 2013: 286 · 2012: 124
- FWCI
- 285.67
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Foundations and Trends® in Machine Learning (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed Control Multi-Agent Systems
- Physical Sciences › Engineering › Computational Mechanics › Sparse and Compressive Sensing Techniques
- Keywords
- alternating direction method of multipliers, distributed convex optimization, statistical learning, large-scale optimization, dual decomposition, Douglas-Rachford splitting, LASSO, sparse logistic regression, basis pursuit, covariance selection, support vector machine, non-convex optimization, MPI, Hadoop MapReduce
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
