Push-Sum Distributed Dual Averaging for convex optimization
Abstract
Recently there has been a significant amount of research on developing consensus based algorithms for distributed optimization motivated by applications that vary from large scale machine learning to wireless sensor networks. This work describes and proves convergence of a new algorithm called Push-Sum Distributed Dual Averaging which combines a recent optimization algorithm [1] with a push-sum consensus protocol [2]. As we discuss, the use of push-sum has significant advantages. Restricting to doubly stochastic consensus protocols is not required and convergence to the true average consensus is guaranteed without knowing the stationary distribution of the update matrix in advance. Furthermore, the communication semantics of just summing the incoming information make this algorithm truly asynchronous and allow a clean analysis when varying intercommunication intervals and communication delays are modelled. We include experiments in simulation and on a small cluster to complement the theoretical analysis.
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?
All prior work in distributed optimization, except for [30], [31], [32], [29], requires time-varying communications with some form of balancedness, often reflected in a requirement of having a sequence of doubly stochastic matrices commensurate with the sequence of underlying communication graphs.
“All the prior work in distributed optimization, except for [30], [31], [32], [29], requires time-varying communications with some form of balancedness, often reflected in a requirement of having a sequence of doubly stochastic matrices that are commensurate with the sequence of underlying communication graphs.”
From Distributed Optimization Over Time-Varying Directed Graphs (2015) · cites this paper as [31]
Cites
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
Flagged first, then by citations
Cited by
Sorted by citations
Distributed Optimization Over Time-Varying Directed Graphs
Nedic, A., & Olshevsky, A. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2364096 · Cited by 1,187 · see citing works
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 · see citing works
NEXT: In-Network Nonconvex Optimization
Lorenzo, P. D., & Scutari, G. (2016) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2016.2524588 · Cited by 473 · see citing works
Distributed nonconvex multiagent optimization over time-varying networks
Sun, Y., Scutari, G., & Palomar, D. (2016) · 2016 50th Asilomar Conference on Signals, Systems and Computers · doi:10.1109/acssc.2016.7869154 · Cited by 86 · see citing works
Distributed optimization over time-varying directed graphs
Nedic, A., & Olshevsky, A. (2013) · 52nd IEEE Conference on Decision and Control · doi:10.1109/cdc.2013.6760975 · Cited by 72 · see citing works
ExtraPush for convex smooth decentralized optimization over directed networks
Zeng, J., & Yin, W. (2015) · arXiv · doi:10.48550/arxiv.1511.02942 · Cited by 65
Central Server Free Federated Learning over Single-sided Trust Social Networks
He, C., Tan, C., Tang, H., Qiu, S., & Liu, J. (2019) · arXiv · doi:10.48550/arxiv.1910.04956 · Cited by 60 · see citing works
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
Nedic, A., & Olshevsky, A. (2014) · arXiv · doi:10.48550/arxiv.1406.2075 · Cited by 38
On the Linear Convergence of Distributed Optimization over Directed Graphs
Xi, C., & Khan, U. A. (2015) · arXiv · doi:10.48550/arxiv.1510.02149 · Cited by 29 · see citing works
- Authors
- Tsianos, K. I., Lawlor, S., & Rabbat, M. G.
- Affiliations
- McGill University (CA)
- ORCID
- Rabbat, Michael G.
- Venue
- 2012 IEEE 51st IEEE Conference on Decision and Control (CDC)
- Publisher
- IEEE
- Published
- 2012-12
- Pages
- 5453-5458
- ISSN
- 0191-2216 (ISSN-L)
- OpenAlex
- W2063403497
- Cited by
- 304
- References
- 1
- Citations by year
- 2026: 9 · 2025: 18 · 2024: 23 · 2023: 25 · 2022: 24 · 2021: 22 · 2020: 33 · 2019: 32 · 2018: 33 · 2017: 29 · 2016: 18 · 2015: 20 · 2014: 12 · 2013: 3 · 2012: 3
- FWCI
- 10.20
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE Conference on Decision and Control (CDC) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Opinion Dynamics and Social Influence
- Keywords
- distributed optimization, convex optimization, consensus algorithms, asynchronous communication, communication delay, convergence analysis, wireless sensor networks, large-scale machine learning
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
