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
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 6×
“The rate of the mean solution is obtained by analyzing an inexact gradient descent iteration, somewhat similar to [8, 11, 20, 25].”
BackgroundMethodInfluentialInformation-driven dynamic sensor collaboration
Zhao, F., Shin, J., & Reich, J. (2002) · IEEE Signal Processing Magazine · doi:10.1109/79.985685 · Cited by 803
Fastest Mixing Markov Chain on a Graph
Boyd, S., Diaconis, P., & Xiao, L. (2004) · SIAM Review · doi:10.1137/s0036144503423264 · Cited by 744
Consensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic Signals
Schizas, I. D., Ribeiro, A., & Giannakis, G. B. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2007.906734 · Cited by 685
Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks
Chen, J., & Sayed, A. H. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2198470 · Cited by 680
Fast Distributed Gradient Methods
Jakovetic, D., Xavier, J., & Moura, J. M. F. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2298712 · Cited by 624
Distributed Robust Power System State Estimation
Kekatos, V., & Giannakis, G. B. (2013) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2012.2219629 · Cited by 521
Distributed Spectrum Sensing for Cognitive Radio Networks by Exploiting Sparsity
Bazerque, J. A., & Giannakis, G. B. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2038417 · Cited by 510
Distributed learning in wireless sensor networks
Predd, J. B., Kulkarni, S. B., & Poor, H. V. (2006) · IEEE Signal Processing Magazine · doi:10.1109/msp.2006.1657817 · Cited by 369
Distributed Learning in Wireless Sensor Networks
Predd, J. B., Kulkarni, S. R., & Poor, H. V. (2007) · Wireless Sensor Networks · doi:10.1002/9780470061794.ch8 · Cited by 264
Monitoring and Optimization for Power Grids: A Signal Processing Perspective
Giannakis, G. B., Kekatos, V., Gatsis, N., et al. (2012) · Cited by 264
Distributed Autonomous Online Learning: Regrets and Intrinsic Privacy-Preserving Properties
Yan, F., Sundaram, S., Vishwanathan, S. V. N., & Qi, Y. (2013) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2012.191 · Cited by 263
Monitoring and Optimization for Power Grids: A Signal Processing Perspective
Giannakis, G. B., Kekatos, V., Gatsis, N., Kim, S.-J., Zhu, H., & Wollenberg, B. F. (2013) · IEEE Signal Processing Magazine · doi:10.1109/msp.2013.2245726 · Cited by 235
Tsianos, K. I., Lawlor, S., & Rabbat, M. G. (2012) · 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2012.6483403 · Cited by 223
Multirobot Active Target Tracking With Combinations of Relative Observations
Zhou, K., & Roumeliotis, S. I. (2011) · IEEE Transactions on Robotics · doi:10.1109/tro.2011.2114734 · Cited by 219
Mota, J. F. C., Xavier, J. M. F., Aguiar, P. M. Q., & Puschel, M. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2011.2182347 · Cited by 210
Analysis and Generalizations of the Linearized Bregman Method
Yin, W. (2010) · SIAM Journal on Imaging Sciences · doi:10.1137/090760350 · Cited by 189
Self-citationDecentralized Sparse Signal Recovery for Compressive Sleeping Wireless Sensor Networks
Ling, Q., & Tian, Z. (2010) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2010.2047721 · Cited by 173
Self-citationGroup-Lasso on Splines for Spectrum Cartography
Bazerque, J. A., Mateos, G., & Giannakis, G. B. (2011) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2011.2160858 · Cited by 171
Decentralized Dynamic Optimization Through the Alternating Direction Method of Multipliers
Ling, Q. H., & Ribeiro, A. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2295055 · Cited by 150
Self-citationSparse event detection in wireless sensor networks using compressive sensing
Meng, J., Li, H., & Han, Z. (2009) · Conference on Information Sciences and Systems · doi:10.1109/ciss.2009.5054713 · Cited by 126
Exact Regularization of Convex Programs
Friedlander, M. P., & Tseng, P. (2007) · SIAM Journal on Optimization · doi:10.1137/060675320 · Cited by 105
Augmented $\ell_1$ and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm
Lai, M., & Yin, W. (2013) · SIAM Journal on Imaging Sciences · doi:10.1137/120863290 · Cited by 102
Self-citationGradient methods for convex minimization: better rates under weaker conditionsPreprint
Zhang, H., & Yin, W. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1303.4645 · Cited by 91
Self-citationDistributed strongly convex optimization
Tsianos, K. I., & Rabbat, M. (2012) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2012.6483272 · Cited by 88
D-MAP: Distributed Maximum a Posteriori Probability Estimation of Dynamic Systems
Jakubiec, F. Y., & Ribeiro, A. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2222398 · Cited by 76
Error Forgetting of Bregman Iteration
Yin, W., & Osher, S. (2012) · Journal of Scientific Computing · doi:10.1007/s10915-012-9616-5 · Cited by 66
Self-citationCavalcante, R. L. G., & Stańczak, S. (2013) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2013.2246766 · Cited by 54
Decentralized Jointly Sparse Optimization by Reweighted $\ell_{q}$ Minimization
Ling, Q. H., Wen, Z., & Yin, W. (2012) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2012.2236830 · Cited by 53
Self-citationDecentralized dynamic optimization through the alternating direction method of multipliers
Ling, Q. H., & Ribeiro, A. (2013) · IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC) · doi:10.1109/spawc.2013.6612034 · Cited by 22
Self-citation
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
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.