On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers
Open accessThe DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
Abstract
We consider a network of agents that are cooperatively solving a global optimization problem, where the objective function is the sum of privately known local objective functions of the agents and the decision variables are coupled via linear constraints. Recent literature focused on special cases of this formulation and studied their distributed solution through either subgradient based methods with O(1/√k) rate of convergence (where k is the iteration number) or Alternating Direction Method of Multipliers (ADMM) based methods, which require a synchronous implementation and a globally known order on the agents. In this paper, we present a novel asynchronous ADMM based distributed method for the general formulation and show that it converges at the rate O (1=k).
Overview
Integrity signals
Registry
Cites
Statistics
Verification
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?
In the citing paper
“For general convex functions and assuming closed and bounded feasible sets, the decentralized asynchronous ADMM [32] is proved to have a rate of O ( 1 k ) in terms of expected objective error and feasibility violation.”
From EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2015) · cites this paper as [32]
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
Coordination of groups of mobile autonomous agents using nearest neighbor rules
Jadbabaie, A., Lin, J., & Morse, A. S. (2003) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2003.812781 · Cited by 8,339
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
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 · cited 1×
“First, many of these algorithms are based on first-order subgradient methods [1], [12], [9], which for general convex problems have slow convergence rates (given by O(1/ √ k) where k is the iteration number),1 making them impractical in many large scale applications.”
BackgroundSelf-citationBoyd, S., Ghosh, A., Prabhakar, B., & Shah, D. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874516 · Cited by 2,439
PROBLEMS IN DECENTRALIZED DECISION MAKING AND COMPUTATION
Τσιτσικλής, Ι. (2014) · doi:10.12681/eadd/3778 · Cited by 1,278
On the $O(1/n)$ Convergence Rate of the Douglas–Rachford Alternating Direction Method
He, B., & Yuan, X. (2012) · SIAM Journal on Numerical Analysis · doi:10.1137/110836936 · Cited by 881
Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization
Sundhar Ram, S., Nedić, A., & Veeravalli, V. V. (2010) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-010-9737-7 · Cited by 814 · cited 1×
“sus step).3 Several follow-up papers considered variants of this method for problems with local and global constraints [26], [36] randomly varying networks [29], [30], [31] and random gradient errors [42], [34]. A different distributed algorithm that relies on Nesterov’s dual averaging algorithm [37] for static networ…”
MethodOn the linear convergence of the alternating direction method of multipliers
Hong, M., & Luo, Z.-Q. (2017) · Mathematical Programming · doi:10.1007/s10107-016-1034-2 · Cited by 690
Research works printed but not linked: 1
- eckstein, 2012, Augmented Lagrangian and Alternating Direction Methods for Convex Optimization A Tutorial and Some Illustrative Computational Results Augmented Lagrangian and Alternating Direction Methods for Convex Optimization A Tutorial and Some Il Rutcor Research Report
Cited by
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
Shi, W., Ling, Q., Wu, G., & Yin, W. (2015) · SIAM Journal on Optimization · doi:10.1137/14096668x · Cited by 1,261
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,069
“However, de-synchronization and extensions of these methods to time-varying undirected graphs are more involved [25, 69], while their extensions to directed graphs are non-existent in the current literature.”
BackgroundHong, M., Luo, Z.-Q., & Razaviyayn, M. (2016) · SIAM Journal on Optimization · doi:10.1137/140990309 · Cited by 841
Harnessing Smoothness to Accelerate Distributed Optimization
Qu, G., & Li, N. (2018) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2017.2698261 · Cited by 565
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization
Nedic, A., Olshevsky, A., & Rabbat, M. G. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2817461 · Cited by 534
Metadata
- Authors
- Wei, E., & Ozdaglar, A.
- Affiliations
- Massachusetts Institute of Technology (US)
- Venue
- 2013 IEEE Global Conference on Signal and Information Processing
- Publisher
- IEEE
- Published
- 2013-12
- Pages
- 551-554
- ISSN
- 2376-4066 (ISSN-L)
- OpenAlex
- W2152637881
- Cited by
- 342
- References
- 17
- Citations by year
- 2026: 5 · 2025: 8 · 2024: 10 · 2023: 16 · 2022: 14 · 2021: 26 · 2020: 24 · 2019: 41 · 2018: 56 · 2017: 41 · 2016: 44 · 2015: 35 · 2014: 19 · 2013: 3
- FWCI
- 25.80
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- IEEE Global Conference on Signal and Information Processing (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc-sa)
- arXiv (Cornell University)
- Funders
- National Science Foundation (0545910)
- Multidisciplinary University Research Initiative (FA9550-09-1-0538)
- Office of Naval Research (FA9550)
- Air Force Office of Scientific Research (FA9550-, FA9550-09-1-0538)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Keywords
- distributed optimization, alternating direction method of multipliers, cooperative optimization, multi-agent systems, sublinear convergence
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers. https://app.cochat.ai/papers/10.1109/globalsip.2013.6736937
- The paper
- Wei, E., & Ozdaglar, A. (2013). On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers. 2013 IEEE Global Conference on Signal and Information Processing. https://doi.org/10.1109/globalsip.2013.6736937
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.