The DOI matches its DataCite record; 1 of the 1 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 each $f_i$ is only known to one individual agent $i$ out of a connected network of $n$ agents. All the agents shall collaboratively solve this problem and obtain the solution subject to data exchanges restricted to between neighboring agents. Such algorithms avoid the need of a fusion center, offer better network load balance, and improve data privacy. We study the decentralized gradient descent method in which each agent $i$ updates its variable $x_{(i)}$, which is a local approximate to the unknown variable $x$, by combining the average of its neighbors' with the negative gradient step $-α\nabla f_i(x_{(i)})$. The iteration is $$x_{(i)}(k+1) \gets \sum_{\text{neighbor} j \text{of} i} w_{ij} x_{(j)}(k) - α\nabla f_i(x_{(i)}(k)),\quad\text{for each agent} i,$$ where the averaging coefficients form a symmetric doubly stochastic matrix $W=[w_{ij}] \in \mathbb{R}^{n \times n}$. We analyze the convergence of this iteration and derive its converge rate, assuming that each $f_i$ is proper closed convex and lower bounded, $\nabla f_i$ is Lipschitz continuous with constant $L_{f_i}$, and stepsize $α$ is fixed. Provided that $α< O(1/L_h)$ where $L_h=\max_i\{L_{f_i}\}$, the objective error at the averaged solution, $f(\frac{1}{n}\sum_i x_{(i)}(k))-f^*$, reduces at a speed of $O(1/k)$ until it reaches $O(α)$. If $f_i$ are further (restricted) strongly convex, then both $\frac{1}{n}\sum_i x_{(i)}(k)$ and each $x_{(i)}(k)$ converge to the global minimizer $x^*$ at a linear rate until reaching an $O(α)$-neighborhood of $x^*$. We also develop an iteration for decentralized basis pursuit and establish its linear convergence to an $O(α)$-neighborhood of the true unknown sparse signal.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
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?
When using a fixed step size, these algorithms do not converge to a solution x* of problem (1.1) but to a point in its neighborhood, regardless of whether the f_i are differentiable.
“When using a fixed step size, these algorithms do not converge to a solution x ∗ of problem (1.1) but a point in its neighborhood no matter whether f i 's are differentiable or not [36].”
From EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2015) · cites this paper as [36]
Properly reducing α_k enables exact convergence, namely that each x_k(i) converges to the same exact solution.
“On the other hand, properly reducing α k enables exact convergence , namely, that each x k ( i ) converges to the same exact solution.”
From EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2015) · cites this paper as [36]
DGD must use diminishing step sizes in order to converge to an exact minimizer.
“In contrast, the well-known decentralized gradient descent (DGD) method must use diminishing step sizes in order to converge to an exact minimizer.”
From EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2015) · cites this paper as [36]
With a fixed step size α_k ≡ α, DGD has inexact convergence: for each agent i, x_k(i) converges to a point in the O(α)-neighborhood of a solution to (1.1), and these points for different agents can be different.
“With a fixed step size α k ≡ α , DGD has inexact convergence . For each agent i , x k ( i ) converges to a point in the O ( α )-neighborhood of a solution to (1.1), and these points for different agents can be different.”
From EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2015) · cites this paper as [36]
Paper [36] studies DGD with a constant α_k ≡ α; before the iterates reach the O(α)-neighborhood, the objective value reduces at the rate O(1/k), and this rate improves to linear if the f_i are also (restricted) strongly convex.
“Paper [36] assumes that ∇ f i 's are Lipschitz continuous, and studies DGD with a constant α k ≡ α . Before the iterates reach the O ( α )-neighborhood, the objective value reduces at the rate O ( 1 k ) , and this rate improves to linear if f i 's are also (restricted) strongly convex.”
From EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2015) · cites this paper as [36]
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].”
Background
Flagged first, then by citations
Cited by
Sorted by citations
EXTRA: 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
Self-citationAchieving 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
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
Metadata
- Authors
- Yuan, K., Ling, Q., & Yin, W.
- Affiliations
- University of Science and Technology of China (CN)
- University of California, Los Angeles (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2013
- Volume
- 26
- Issue
- 3
- Pages
- 1835-1854
- ISSN
- 1052-6234 (ISSN-L)
- arXiv
- 1310.7063
- OpenAlex
- W1616857247
- Cited by
- 635
- References
- 1
- Citations by year
- 2026: 33 · 2025: 55 · 2024: 62 · 2023: 73 · 2022: 64 · 2021: 80 · 2020: 80 · 2019: 66 · 2018: 45 · 2017: 22 · 2016: 28 · 2015: 20 · 2014: 7
- FWCI
- 50.63
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- SIAM Journal on Optimization (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- eScholarship (California Digital Library) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (0748839, 1317602)
- National Natural Science Foundation of China (61004137)
- Army Research Office (W911NF, W911NF-09-1-0383)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
- Keywords
- consensus, convergence rate, distributed optimization, doubly stochastic matrices, Lipschitz continuous gradient, strong convexity, step size selection, networked agents, convex optimization, data privacy, network load balancing, distributed estimation
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
