The DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.
On the Convergence of Decentralized Gradient Descent
Open accessAbstract
Consider the consensus problem of minimizing $f(x)=\sum_{i=1}^n f_i(x)$, where $x\in{\mathbb{R}}^p$ and each $f_i$ is only known to the individual agent $i$ in a connected network of $n$ agents. To solve this problem and obtain the solution, all the agents collaborate with their neighbors through information exchange. This type of decentralized computation does not need a fusion center, offers better network load balance, and improves data privacy. This paper studies the decentralized gradient descent method [A. Nedic and A. Ozdaglar, IEEE Trans. Automat. Control, 54 (2009), pp. 48--61], in which each agent $i$ updates its local variable $x_{(i)}\in{\mathbb{R}}^n$ by combining the average of its neighbors' with a local negative-gradient step $-\alpha \nabla f_i(x_{(i)})$. The method is described by the iteration $ x_{(i)}(k+1) \gets \sum_{j=1}^n w_{ij} x_{(j)}(k) - \alpha \nabla f_i(x_{(i)}(k)),\ \text{for each agent}~i, $ where $w_{ij}$ is nonzero only if $i$ and $j$ are neighbors or $i=j$ and the matrix $W=[w_{ij}] \in \mathbb{R}^{n \times n}$ is symmetric and doubly stochastic. This paper analyzes the convergence of this iteration and derives its rate of convergence under the assumption that each $f_i$ is proper closed convex and lower bounded, $\nabla f_i$ is Lipschitz continuous with constant $L_{f_i}>0$, and the stepsize $\alpha$ is fixed. Provided that $\alpha \le \min\{(1+\lambda_n(W))/L_h,1/L_{\bar{f}}\}$, where $L_h=\max_i\{L_{f_i}\}$ and $L_{\bar{f}}=\frac{1}{n}\sum_{i=1}^{n}L_{f_i}$, the objective errors of all the local solutions and the networkwide mean solution reduce at rates of $O(1/k)$ until they reach a level of $O(\alpha)$. If $f_i$ are strongly convex with modulus $\mu_{f_i}$ and $\alpha \le \min\{(1+\lambda_n(W))/L_h,1/(L_{\bar{f}}+\mu_{\bar{f}})\}$, where $\mu_{\bar{f}}=\frac{1}{n}\sum_{i=1}^{n}\mu_{f_i}$, then all the local solutions and the mean solution converge to the global minimizer $x^*$ at a linear rate until reaching an $O(\alpha)$-neighborhood of $x^*$. We also develop an iteration for decentralized basis pursuit and establish its linear convergence to an $O(\alpha)$-neighborhood of the true sparse signal. This analysis reveals how the convergence of $ x_{(i)}(k+1) \gets \sum_{j=1}^n w_{ij} x_{(j)}(k) - \alpha \nabla f_i(x_{(i)}(k)),\ \text{for each agent}~i, $ depends on the stepsize, function convexity, and network spectrum.
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
Consensus and Cooperation in Networked Multi-Agent Systems
Olfati-Saber, R., Fax, J. A., & Murray, R. M. (2007) · Proceedings of the IEEE · doi:10.1109/jproc.2006.887293 · Cited by 10,522 · cited 1×
“Compared to optimization with a fusion center that collects data and performs computation, decentralized optimization enjoys the advantages of scalability to network sizes, robustness to dynamic topologies, and privacy preservation in data-sensitive applications [7, 17, 22, 32].”
BackgroundDistributed 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
Information consensus in multivehicle cooperative control
(2007) · IEEE Control Systems · doi:10.1109/mcs.2007.338264 · Cited by 3,156
An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination
Cao, Y., Yu, W., Ren, W., & Chen, G. (2013) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2012.2219061 · Cited by 2,399
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
Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
Yin, W., Osher, S., Goldfarb, D., & Darbon, J. (2008) · SIAM Journal on Imaging Sciences · doi:10.1137/070703983 · Cited by 1,414
Self-citationPROBLEMS IN DECENTRALIZED DECISION MAKING AND COMPUTATION
Τσιτσικλής, Ι. (2014) · doi:10.12681/eadd/3778 · Cited by 1,278
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2161027 · Cited by 947
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2010) · Cited by 884
Gradient methods for minimizing composite objective function
Nesterov, Y. E. (2007) · Cited by 867
Cited by
A survey of distributed optimization
Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., Hong, Y., Wang, H., Lin, Z., & Johansson, K. H. (2019) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2019.05.006 · Cited by 913
Decentralized federated learning: Fundamentals, state of the art, frameworks, trends, and challenges
Martínez Beltrán, E. T., Pérez, M. Q., Sánchez, P. M. S., Bernal, S. L., Bovet, G., Pérez, M. G., Pérez, G. M., & Celdrán, A. H. (2023) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2023.3315746 · Cited by 625
“Some examples are Decentralized Gradient Descent (DGD) [104], decentralized Alternating Direction Method of Multipliers (ADMM) [105], EXTRA [106], and ADMM based on Jacobi-Proximal [107].”
MethodLian, X., Zhang, C., Zhang, H., Hsieh, C., Zhang, W., & Liu, J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.09056 · Cited by 395
Decentralized Federated Averaging
Sun, T., Li, D., & Wang, B. (2023) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2022.3196503 · Cited by 388
Decentralized Federated Learning With Unreliable Communications
Ye, H., Liang, L., & Li, G. Y. (2022) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2022.3152445 · Cited by 184
Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms
Jakovetic, D., Moura, J. M. F., & Xavier, J. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2363299 · Cited by 123
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
Wang, J., Sahu, A. K., Yang, Z., Joshi, G., & Kar, S. (2019) · 2019 Sixth Indian Control Conference (ICC) · doi:10.1109/icc47138.2019.9123209 · Cited by 149
Robust and communication-efficient collaborative learning
Reisizadeh, A., Taheri, H., Mokhtari, A., Hassani, H., & Pedarsani, R. (2019) · arXiv · doi:10.48550/arxiv.1907.10595 · Cited by 73
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
Self-citationA Generic Federated Recommendation Framework via Fake Marks and Secret Sharing
Lin, Z., Pan, W., Yang, Q., & Ming, Z. (2023) · ACM Transactions on Information Systems · doi:10.1145/3548456 · Cited by 44
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
Zhao, Y., Yu, C., Zhao, P., Tang, H., Qiu, S., & Liu, J. (2019) · arXiv · doi:10.48550/arxiv.1901.10593 · Cited by 16
Digest: Fast and communication efficient decentralized learning with local updates
Gholami, P., & Seferoglu, H. (2024) · IEEE Transactions on Machine Learning in Communications and Networking · doi:10.1109/tmlcn.2024.3354236 · Cited by 14
Zhang, L., Li, G., Yuan, L., Ding, X., & Rong, Q. (2024) · Information Processing & Management · doi:10.1016/j.ipm.2023.103580 · Cited by 9
Augmented distributed optimization for networked systems
Xu, J. (2019) · doi:10.32657/10356/68805 · Cited by 5
Metadata
- Authors
- Yuan, K., Ling, Q., & Yin, W.
- Venue
- SIAM Journal on Optimization
- Published
- 2016-01
- Volume
- 26
- Issue
- 3
- Pages
- 1835-1854
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W1616857247
- Cited by
- 633
- References
- 40
- FWCI
- 50.53
- 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.