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
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.”
BackgroundMethod
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
Self-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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Exact Diffusion for Distributed Optimization and Learning—Part I: Algorithm Development. https://app.cochat.ai/papers/10.1109/tsp.2018.2875898
- The paper
- Yuan, K., Ying, B., Zhao, X., & Sayed, A. H. (2019). Exact Diffusion for Distributed Optimization and Learning—Part I: Algorithm Development. IEEE Transactions on Signal Processing. https://doi.org/10.1109/tsp.2018.2875898
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.