Exact Diffusion for Distributed Optimization and Learning—Part I: Algorithm Development
Open accessThe DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index.
Abstract
This paper develops a distributed optimization strategy with guaranteed exact convergence for a broad class of left-stochastic combination policies. The resulting exact diffusion strategy is shown in Part II of this paper to have a wider stability range and superior convergence performance than the EXTRA strategy. The exact diffusion method is applicable to locally balanced left-stochastic combination matrices which, compared to the conventional doubly stochastic matrix, are more general and able to endow the algorithm with faster convergence rates, more flexible step-size choices, and improved privacy-preserving properties. The derivation of the exact diffusion strategy relies on reformulating the aggregate optimization problem as a penalized problem and resorting to a diagonally weighted incremental construction. Detailed stability and convergence analyses are pursued in Part II of this paper and are facilitated by examining the evolution of the error dynamics in a transformed domain. Numerical simulations illustrate the theoretical conclusions.
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
Monte Carlo sampling methods using Markov chains and their applications.
Hastings, W. K. (1970) · Biometrika · doi:10.1093/biomet/57.1.97 · Cited by 15,195
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 2×
“a calculation of the form: w k;i+1 = XN ‘=1 a ‘k ‘;i; where XN a ‘k = 1: (3) It should be emphasized that condition (2), which is repeated in (3), is different from all previous algorithms studied in [23], [32]–[34], [36], [38], [42], [43], which require Ato be symmetric and doubly stochastic (i.e., each of its column…”
BackgroundEXTRA: 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
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
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
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
Self-citationOn the Convergence of Decentralized Gradient Descent
Yuan, K., Ling, Q., & Yin, W. (2013) · arXiv · doi:10.48550/arxiv.1310.7063 · Cited by 635
Self-citationNEXT: 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
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 · cited 2×
“It should be emphasized that condition (2), which is repeated in (3), is different from all previous algorithms studied in [23], [32]–[34], [36], [38], [42], [43], which require A to be symmetric and doubly stochastic (i.”
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2015) · 2015 54th IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402509 · Cited by 332 · cited 3×
“It should be emphasized that condition (2), which is repeated in (3), is different from all previous algorithms studied in [23], [32]–[34], [36], [38], [42], [43], which require A to be symmetric and doubly stochastic (i.”
BackgroundMethodPush-Sum Distributed Dual Averaging for convex optimization
Tsianos, K. I., Lawlor, S., & Rabbat, M. G. (2012) · 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2012.6426375 · Cited by 304 · cited 3×
“employ the useful push-sum technique, which requires A to be right (rather than left) stochastic, i.e., Ais required to satisfy instead1A1 N = 1 N. For instance, the push-sum implementations in [40], [44]–[47] replace the rightmost condition in (3) by w k;i+1 = XN ‘=1 a ‘k ‘;i; where XN k=1 a ‘k = 1: (4) It will be il…”
BackgroundMethodInfluentialGeometrically convergent distributed optimization with uncoordinated step-sizes
Nedic, A., Olshevsky, A., Shi, W., & Uribe, C. A. (2017) · 2017 American Control Conference (ACC) · doi:10.23919/acc.2017.7963560 · Cited by 145
Harnessing smoothness to accelerate distributed optimization
Qu, G., & Li, N. (2016) · 2016 IEEE 55th Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798263 · Cited by 72
ExtraPush for convex smooth decentralized optimization over directed networks
Zeng, J., & Yin, W. (2015) · arXiv · doi:10.48550/arxiv.1511.02942 · Cited by 65
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
Cited by
Xin, R., Kar, S., & Khan, U. A. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2974267 · Cited by 114
“Of relevance here are EX-TRA [27] and exact diffusion [28], both of which eliminate the bias caused by b and are built different principle than gradient tracking.”
BackgroundSupervised Learning Under Distributed Features
Ying, B., Yuan, K., & Sayed, A. H. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2881661 · Cited by 50
“To this end, we can apply the exact diffusion algorithm developed in [18], [51] to solve (22).”
BackgroundMethodSelf-citation
Metadata
- Authors
- Yuan, K., Ying, B., Zhao, X., & Sayed, A. H.
- Venue
- IEEE Transactions on Signal Processing
- Published
- 2019-02-01
- Volume
- 67
- Issue
- 3
- Pages
- 708-723
- ISSN
- 1053-587X (ISSN-L)
- 1941-0476
- OpenAlex
- W2964165783
- Cited by
- 200
- References
- 15
- FWCI
- 15.09
- 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.