EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
Open accessThe DOI matches its Crossref record; 47 of the 47 references it cites were found in a registry or an index; 7 of the 19 sources its claims cite were checked for support.
Abstract
Recently, there has been growing interest in solving consensus optimization problems in a multiagent network. In this paper, we develop a decentralized algorithm for the consensus optimization problem $\mathrm{minimize}_{x\in\mathbb{R}^p}~\bar{f}(x)=\frac{1}{n}\sum_{i=1}^n f_i(x),$ which is defined over a connected network of $n$ agents, where each function $f_i$ is held privately by agent $i$ and encodes the agent's data and objective. All the agents shall collaboratively find the minimizer while each agent can only communicate with its neighbors. Such a computation scheme avoids a data fusion center or long-distance communication and offers better load balance to the network. This paper proposes a novel decentralized exact first-order algorithm (abbreviated as EXTRA) to solve the consensus optimization problem. “Exact” means that it can converge to the exact solution. EXTRA uses a fixed, large step size, which can be determined independently of the network size or topology. The local variable of every agent $i$ converges uniformly and consensually to an exact minimizer of $\bar{f}$. In contrast, the well-known decentralized gradient descent (DGD) method must use diminishing step sizes in order to converge to an exact minimizer. EXTRA and DGD have the same choice of mixing matrices and similar per-iteration complexity. EXTRA, however, uses the gradients of the last two iterates, unlike DGD which uses just that of the last iterate. EXTRA has the best known convergence rates among the existing synchronized first-order decentralized algorithms for minimizing convex Lipschitz--differentiable functions. Specifically, if the $f_i$'s are convex and have Lipschitz continuous gradients, EXTRA has an ergodic convergence rate $O(\frac{1}{k})$ in terms of the first-order optimality residual. In addition, as long as $\bar{f}$ is (restricted) strongly convex (not all individual $f_i$'s need to be so), EXTRA converges to an optimal solution at a linear rate $O(C^{-k})$ for some constant $C>1$.
Overview
CoChat Summary
TL;DR
EXTRA is a synchronous decentralized exact first-order algorithm for consensus optimization that can use a fixed step size independent of network size and converges to an exact solution. It achieves an ergodic O(1/k) rate for convex Lipschitz-differentiable objectives and a linear rate under restricted strong convexity.
Key findings
- EXTRA uses a fixed large step size and converges exactly, unlike DGD with a fixed step size, which stalls in an O(α)-neighborhood and requires diminishing step sizes for exact convergence.
- Under Assumptions 1–3 and step size \(0<\alpha<2\lambda_{\min}(\tilde W)/L_f\), the sequence \(z_k\) converges to an optimal \(z^*\), with contraction factor \(\zeta=1-\alpha L_f/(2\lambda_{\min}(\tilde W))\); running-average progress is \(O(1/k)\), running-best progress is \(o(1/k)\), and running-average optimality residuals are \(O(1/k)\).
- If \(g(x)=f(x)+\frac{1}{4\alpha}\|x\|^2_{\tilde W-W}\) is restricted strongly convex with constant \(\mu_g>0\), then with proper step size \(\alpha<2\mu_g\lambda_{\min}(\tilde W)/L_f^2\), \(\|z_k-z^*\|_G^2\) converges Q-linearly at \(O((1+\delta)^{-k})\), and \(\|x_k-x^*\|_{\tilde W}^2\) converges R-linearly at the same rate.
- Numerical experiments: in decentralized least squares with \(n=10\), \(m_i=1\), \(p=5\), connectivity ratio \(r=0.5\), \(L_f=1\), and \(\|x^*-x_0\|=300\), DGD with fixed step size and EXTRA show similar linear convergence for the first 200 iterations, after which DGD slows and stalls while EXTRA continues. In decentralized logistic regression with \(n=200\), \(r=0.2\), \(m_i=10\), \(p=20\), and 2000 samples, EXTRA outperforms DGD and shows linear exact convergence.
Methods
- Design: a synchronous decentralized first-order algorithm where each agent holds a local copy \(x^{(i)}\) and communicates only with neighbors; EXTRA is derived by taking the difference of two DGD updates and uses gradients of the last two iterates.
- Data/sample: numerical tests on decentralized least squares, decentralized robust least squares with Huber loss, and decentralized logistic regression over randomly generated connected networks.
- Analysis: convergence is established under mixing-matrix assumptions, convex Lipschitz-differentiable objectives, and solution existence; rates are derived via a contraction recursion, ergodic averaging, and restricted strong convexity.
Limitations
- The paper states EXTRA is “far from perfect” and that more work is needed to adapt it to asynchronous and dynamic network settings; these are left as open questions.
- The paper notes it is open whether \(\|z_k-z_{k+1}\|_G^2\) is monotonic; if monotonicity could be shown, the rates would hold for the last point in the running sequence. It also states that proving linear convergence under the numerically observed larger step size \(O(1/L_f)\) remains open.
- The paper states that determining \(\mu_g\) or a lower bound is tricky except when each \(f_i\) is restricted strongly convex, and that deriving an optimal step size and explicit linear rate is “quite tricky and messy.” The numerical results are described as preliminary.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Figures

![Fig. 4.2 Plot of residuals ‖ x k -x ∗ ‖ F ‖ x 0 -x ∗ ‖ F . Constant α = 0 . 5276 is the theoretical critical step size given for DGD in [36]. For DGD with diminishing step sizes O (1 /k 1 / 3 ) and O (1 /k 1 / 2 ) , we have hand-optimized their initial step sizes as 10 α and 20 α , respectively. The initial large step sizes have helped them (the red and purple curves) realize faster convergence initially.](https://figures.cochat.ai/paper-figures/4f2c85fb730e4c6eaeaa955cda38aeac/extra-an-exact-first-order-algorithm-for-decentralized-consensus-optimization-figure-2.png)
![Fig. 4.3 Plot of residuals ‖ x k -x ∗ ‖ F ‖ x 0 -x ∗ ‖ F . Constant α = 0 . 0059 is the theoretical critical step size given for DGD in [36]. For DGD with diminishing step sizes O (1 /k 1 / 3 ) and O (1 /k 1 / 2 ) , we have hand-optimized their initial step sizes as 10 α and 20 α , respectively.](https://figures.cochat.ai/paper-figures/d5f55fab59f84fe6834d6cb2909bb298/extra-an-exact-first-order-algorithm-for-decentralized-consensus-optimization-figure-3.png)
Verification
Claims the paper makes
6 Valid · 1 Not valid · 9 Not checked · 58 Own results and interpretations
At least one cited source doesn’t support this claim or points to a different paper, and none confirmed it — see the verdicts below.
In the paper
“On the other hand, properly reducing α k enables exact convergence , namely, that each x k ( i ) converges to the same exact solution.”
What the sources say
- Misattributedcites [36] [36] K. Yuan, Q. Ling, and W. Yin , On the Convergence of Decentralized Gradient Descent , arXiv preprint arXiv:1310.7063, (2013). 1.1, 2.1, 2.4, 4.1, 4.1, 4.2, 4.3 - sourceExperimental — accuracy not yet measured
Our copy disclaims the diminishing-stepsize result for itself: §1.3 (Contribution and notation) states 'Since our analysis uses a fixed stepsize, the local solutions will not be asymptotically consensual. To adapt our analysis to diminishing stepsizes, significant changes will be needed,' and every rate in Theorems 2-3 and Remarks 1-3 lands in an O(alpha/(1-beta))-neighborhood rather than the exact solution. The only place the paper states the claim's point is §1.2 (Related methods): 'Convergence to x* can be achieved by using diminishing stepsizes in [8,11,29] at the price of slower rates of convergence' — i.e., it credits exact convergence under diminishing stepsizes to other works it cites, without reporting or relying on it. Reference [8] in our copy is Duchi, Agarwal and Wainwright, 'Dual averaging for distributed optimization: convergence analysis and network scaling,' IEEE TAC 57 (2012) (with [11] Jakovetic, Xavier, Moura and [29] also credited). (LLM, conf=0.82) It matches “Dual averaging for distributed optimization: convergence analysis and network scaling” (2012) instead.
Checked by a reasoning model — may be wrong.
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Misattributed
Every source the paper cites for this claim was checked and supports it.
In the paper
“In contrast, the well-known decentralized gradient descent (DGD) method must use diminishing step sizes in order to converge to an exact minimizer.”
- Also stated in: § EXTRA: AN EXACT FIRST-ORDER ALGORITHM FOR DECENTRALIZED CONSENSUS OPTIMIZATION ∗ · p. 4 · plain
“properly reducing α k enables exact convergence , namely, that each x k ( i ) converges to the same exact solution.”
What the sources say
- Supportedcites [36] [36] K. Yuan, Q. Ling, and W. Yin , On the Convergence of Decentralized Gradient Descent , arXiv preprint arXiv:1310.7063, (2013). 1.1, 2.1, 2.4, 4.1, 4.1, 4.2, 4.3 - source
Section 1.2 (Related methods) states that with a fixed stepsize the listed algorithms 'and iteration (4) in particular' converge to a neighborhood of x* rather than x* itself, and that convergence to x* can be achieved by using diminishing stepsizes (at the price of slower rates) — exactly the necessity the claim attributes. Section 1.3 reinforces this: 'Since our analysis uses a fixed stepsize, the local solutions will not be asymptotically consensual,' and the Abstract/Theorems 2-3 give only O(α/(1-β))-neighborhood landing levels for fixed α. The only mild caveat is that the diminishing-stepsize exact-convergence results are credited to references [8,11,29] rather than proved here for iteration (4), but the paper's own statement of the fixed-stepsize limitation for DGD covers the claim. (LLM, conf=0.85)
boostedstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Also stated in: § EXTRA: AN EXACT FIRST-ORDER ALGORITHM FOR DECENTRALIZED CONSENSUS OPTIMIZATION ∗ · p. 4 · plain
Every source the paper cites for this claim was checked and supports it.
In the paper
“(iii) min t ≤ k { a t } = o ( 1 k ) .”
What the sources say
- Supportedcites [6] [6] D. Davis and W. Yin , Convergence Rates of Splitting Algorithms for Optimization . arXiv preprint arXiv:1406.4834, 2014. 1 - source
Section 2 ('Summable sequence convergence lemma', Lemma 3, p. 8) states Part 4 'No monotonicity', defining the best-so-far sequence and asserting that '(a_j^best) is monotonically nonincreasing and the above bounds continue to hold when a_k is replaced with a_k^best', while the Part 1a proof on the same page gives a_k = o(1/(Λ_k − Λ_⌈k/2⌉)) = o(1/(k+1)) when (λ_j) is bounded away from 0 (i.e. unweighted summability). Together these yield exactly the claim: a nonnegative sequence with finite sum has running minimum o(1/k) (the source writes o(1/(k+1)), the same rate up to index shift). The remark on p. 9 confirms the setting — Part 1 generalizes the known result that a nonnegative, summable, monotonic sequence converges at o(1/(k+1)) — and p. 12 applies Lemma 3 to a running minimum, min_{i=0,…,k}{‖e_i‖}. (LLM, conf=0.85)
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“An EXTRA update is, therefore, a DGD update with a cumulative correction term.”
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A conclusion the paper draws from its own results — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“In this subsection we prove that EXTRA with a proper step size reaches linear convergence if the original objective ¯ f is restricted strongly convex.”
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
31 more claims
Create a free account to see all 74 claims and to verify the 7 references still open.
- Probably not a substantial claim. 21
- It may state two separate claims as one. 26
- The quote only partly states this claim. 1
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?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“EXTRA converges at an o (1 /k ) rate when the objective function in (1) is convex, and it has a Q-linear rate when the objective function is strongly convex.”
From Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2017) · cites this paper as [62]
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“Proposition 1 ( [62]). Assume null { I -W } = span { 1 } where W ∈ R n × n . If x ∗ satisfies conditions: (i) x ∗ = Wx ∗ (consensus), (ii) 1 ⊤ ∇ f ( x ∗ ) = 0 (optimality), then the rows of x ∗ are the same as each other and the transpose of each row is an optimal solution of the problem (1) .”
From Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2017) · cites this paper as [62]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
Each contradiction between two passages listed here was confirmed by an independent check.
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ Algorithm 1: EXTRA · p. 9
“null { U } = (span { 1 } ) ⊥”
§ Algorithm 1: EXTRA · p. 7
“null { W -˜ W } = span { 1 } , null { I -˜ W } ⊇ span { 1 } .”
Citations
Cites
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 1×
“1) include the (sub)gradient method [21, 25, 36], the (sub)gradient-push method [23, 24], the fast (sub)gradient method [5, 14], and the dual averaging method [8].”
MethodFast linear iterations for distributed averaging
Xiao, L., & Boyd, S. (2004) · Systems & Control Letters · doi:10.1016/j.sysconle.2004.02.022 · Cited by 2,706
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
Distributed average consensus with least-mean-square deviation
Xiao, L., Boyd, S., & Kim, S.-J. (2007) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2006.08.010 · Cited by 1,107
Optimal decentralized protocol for electric vehicle charging
Gan, L., Topcu, U., & Low, S. H. (2013) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2012.2210288 · Cited by 997
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
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-citationDistributed 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 1×
“1) has additional constraints that force x into a bounded set, which also leads to bounded (sub)gradients and a Hessian, projected first-order algorithms are applicable [27, 37].”
BackgroundOn Distributed Convex Optimization Under Inequality and Equality Constraints
Zhu, M., & Martinez, S. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2167817 · Cited by 759
Fastest Mixing Markov Chain on a Graph
Boyd, S., Diaconis, P., & Xiao, L. (2004) · SIAM Review · doi:10.1137/s0036144503423264 · Cited by 744
Research works printed but not linked: 3
- [5] I. Chen , Fast Distributed First-Order Methods , master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 2012. 1.1, 2.1, 2.4, 4.1 -
- [15] B. Johansson , On Distributed Optimization in Networked Systems , PhD thesis, KTH, 2008. 1 -
- [31] J. Tsitsiklis , Problems in Decentralized Decision Making and Computation , PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1984. 2.4 -
Cited by
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., & Suresh, A. T. (2019) · arXiv · doi:10.48550/arxiv.1910.06378 · Cited by 1,734
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
Self-citationA 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].”
Harnessing Smoothness to Accelerate Distributed Optimization
Qu, G., & Li, N. (2018) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2017.2698261 · Cited by 565
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization
Nedic, A., Olshevsky, A., & Rabbat, M. G. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2817461 · Cited by 534
“Moreover, without a good intuition for what it is doing, it is difficult to extend it to time-varying or directed graphs (the original proof in [32] only covered fixed graphs).”
InfluentialNEXT: 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
Push–Pull Gradient Methods for Distributed Optimization in Networks
Pu, S., Shi, W., Xu, J., & Nedic, A. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2972824 · Cited by 376
Self-citationDistributed Online Optimization in Dynamic Environments Using Mirror Descent
Shahrampour, S., & Jadbabaie, A. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2743462 · Cited by 331
Distributed Optimization for Control
Nedić, A., & Liu, J. (2018) · Annual Review of Control, Robotics, and Autonomous Systems · doi:10.1146/annurev-control-060117-105131 · Cited by 302
A Proximal Gradient Algorithm for Decentralized Composite Optimization
Shi, W., Ling, Q., Wu, G., & Yin, W. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2461520 · Cited by 307
“When the possibly-nondifferentiable term , we have in (2a) and (2b) and thus (4) In (3a) and (3b), we have and thus (5) The updates (4) and (5) are known as EXTRA, a recent algo-rithm for decentralized differentiable optimization [23].”
InfluentialSelf-citationCevher, V., Becker, S., & Schmidt, M. (2014) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2329397 · Cited by 300
“Surprisingly, we can also decentralize the communication requirements of gradient methods for decomposable objectives with only minor modifications [31].”
Distributed stochastic gradient tracking methods
Pu, S., & Nedić, A. (2021) · Mathematical Programming · doi:10.1007/s10107-020-01487-0 · Cited by 266
Li, Z., Shi, W., & Yan, M. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2926022 · Cited by 244
Self-citationA Linear Algorithm for Optimization Over Directed Graphs With Geometric Convergence
Xin, R., & Khan, U. A. (2018) · IEEE Control Systems Letters · doi:10.1109/lcsys.2018.2834316 · Cited by 243
“Another method, EXTRA [3], achieves geometric convergence to the global optimal solution with the requirement of symmetric weights.”
Convergence of Asynchronous Distributed Gradient Methods Over Stochastic Networks
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2730481 · Cited by 214
Linear Convergence in Optimization Over Directed Graphs With Row-Stochastic Matrices
Xi, C., Mai, V. S., Xin, R., Abed, E. H., & Khan, U. A. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2797164 · Cited by 215
“To accelerate the convergence, DEX-TRA, [33] combines push-sum consensus, [26, 27], and EX-TRA, [20], and converges linearly under the strong-convexity assumption with the step-size being chosen in some interval.”
BackgroundMethodInfluentialNedic, A. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2975210 · Cited by 211
Convergence Rate of Distributed ADMM over NetworksPreprint
Makhdoumi, A., & Ozdaglar, A. (2017) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 202
Xin, R., & Khan, U. A. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2942513 · Cited by 201
Exact Diffusion for Distributed Optimization and Learning—Part I: Algorithm Development
Yuan, K., Ying, B., Zhao, X., & Sayed, A. H. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2875898 · Cited by 200
Communication-efficient algorithms for decentralized and stochastic optimization
Lan, G., Lee, S., & Zhou, Y. (2020) · Mathematical Programming · doi:10.1007/s10107-018-1355-4 · Cited by 187
Network Newton Distributed Optimization Methods
Mokhtari, A., Ling, Q., & Ribeiro, A. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2617829 · Cited by 182
Self-citationDistributed Subgradient Projection Algorithm Over Directed Graphs
Xi, C., & Khan, U. A. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2615066 · Cited by 185
“A related algorithm, EXTRA, [13], uses a constant step-size and the gradients of the last two iterates.”
MethodDEXTRA: A Fast Algorithm for Optimization Over Directed Graphs
Xi, C., & Khan, U. A. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2672698 · Cited by 172
Accelerated Distributed Nesterov Gradient Descent
Qu, G., & Li, N. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2937496 · Cited by 187
“The weight matrix W is chosen using the Laplacian method [31].”
Liu, Q., Yang, S., & Hong, Y. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2681200 · Cited by 184
On Nonconvex Decentralized Gradient Descent
Zeng, J., & Yin, W. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2818081 · Cited by 184
“When fi’s are convex, the existing algorithms include the (sub)gradient methods [5], [6], [10], [13], [15], [23], [27], and the primaldual domain methods such as the decentralized alternating direction method of multipliers (DADMM) [19], [20] and EXTRA [21], [22].”
InfluentialSelf-citationADD-OPT: Accelerated Distributed Directed Optimization
Xi, C., Xin, R., & Khan, U. A. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2737582 · Cited by 181
D$^2$: Decentralized Training over Decentralized Data
Tang, H., Lian, X., Yan, M., Zhang, C., & Liu, J. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.07068 · Cited by 159
Distributed nonconvex constrained optimization over time-varying digraphs
Scutari, G., & Sun, Y. (2019) · Mathematical Programming · doi:10.1007/s10107-018-01357-w · Cited by 210
Aybat, N. S., Wang, Z., Lin, T., & Ma, S. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2713046 · Cited by 172
Optimal distributed stochastic mirror descent for strongly convex optimization
Yuan, D., Hong, Y., Ho, D. W. C., & Jiang, G. (2018) · Automatica · doi:10.1016/j.automatica.2017.12.053 · Cited by 154
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., & Stich, S. U. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.10422 · Cited by 151
Tracking-ADMM for distributed constraint-coupled optimization
Falsone, A., Notarnicola, I., Notarstefano, G., & Prandini, M. (2020) · Automatica · doi:10.1016/j.automatica.2020.108962 · Cited by 177
DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
Mokhtari, A., & Ribeiro, A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.04216 · Cited by 130
“…(Mokhtari et al. (2015a,b)), decentralized dual averaging (Duchi et al. (2012); Tsianos et al. (2012b)), the exact first order al-gorithm (EXTRA) (Shi et al. (2015)), as well as the alternating direction method of multipliers (ADMM) (Boyd et al. (2011); Shi et al. (2014); Iutzeler et al.…”
InfluentialGeometrically 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
Self-citationPrimal–dual algorithm for distributed constrained optimization
Lei, J., Chen, H.-F., & Fang, H. (2016) · Systems & Control Letters · doi:10.1016/j.sysconle.2016.07.009 · Cited by 148
Communication-efficient distributed learning: An overview
Cao, X., Başar, T., Diggavi, S., Eldar, Y. C., Letaief, K. B., Poor, H. V., & Zhang, J. (2023) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2023.3242710 · Cited by 139
A Novel Consensus-Based Economic Dispatch for Microgrids
Tang, Z., Hill, D. J., & Liu, T. (2018) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2018.2835657 · Cited by 137
Decentralized Optimization Over Time-Varying Directed Graphs With Row and Column-Stochastic Matrices
Saadatniaki, F., Xin, R., & Khan, U. A. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2969721 · Cited by 172
“Related work along these lines also include [31] over undirected graphs and [32] over directed graphs.”
BackgroundDing, T., Zhu, S., He, J., Chen, C., & Guan, X. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3059427 · Cited by 126
A Decentralized Second-Order Method with Exact Linear Convergence Rate for Consensus Optimization
Mokhtari, A., Shi, W., Ling, Q. H., & Ribeiro, A. (2016) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2016.2613678 · Cited by 132
“If we substitute the augmented Lagrangian by its first order approximation we can recover the update of EXTRA proposed in [31].”
InfluentialSelf-citationMagnússon, S., Weeraddana, P. C., Rabbat, M., & Fischione, C. (2015) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2015.2476198 · Cited by 149
Distributed optimization over directed graphs with row stochasticity and constraint regularity
Mai, V. S., & Abed, E. H. (2019) · Automatica · doi:10.1016/j.automatica.2018.07.020 · Cited by 136
“Though better convergence rates are attainable when certain assumptions on smoothness and strong convexity of fi are imposed [32, 40, 44, 46], fast convergence is not the main goal in this paper; instead, we focus on a distributed non-smooth optimization problem with row stochasticity and constraint regularity.”
BackgroundMethodConvergence rate analysis of distributed optimization with projected subgradient algorithm
Liu, S., Qiu, Z., & Xie, L. (2017) · Automatica · doi:10.1016/j.automatica.2017.06.011 · Cited by 122
“When the cost function assumes Lipschitz continuous gradients, a sublinear rate of O(1/k) can be achieved by adopting a constant step size (Qu & Li, 2016; Shi et al., 2015), and the fast distributed gradient method achieves a rate of O(1/k2−ε) with an arbitrarily small ε (Jakovetic et al.”
A Unification and Generalization of Exact Distributed First-Order Methods
Jakovetić, D. (2018) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2018.2846183 · Cited by 142
Decentralized Proximal Gradient Algorithms With Linear Convergence Rates
Alghunaim, S. A., Ryu, E. K., Yuan, K., & Sayed, A. H. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3009363 · Cited by 151
“…( w ) = 0 we present an adapt-then-combine (ATC) unifying primal-dual framework that covers many existing state-of-the-art algorithms [1], [2], [3], [4], [5], [6], [7], [8], [9], which to our knowledge, is the first primal-dual interpretation of the ATC gradient-tracking methods [1], [2], [3], [4].”
InfluentialA Dual Approach for Optimal Algorithms in Distributed Optimization over Networks
Uribe, C. A., Lee, S., Gasnikov, A. V., & Nedić, A. (2020) · Information Theory and Applications Workshop (ITA) · doi:10.1080/10556788.2020.1750013 · Cited by 151
Geometric Convergence of Gradient Play Algorithms for Distributed Nash Equilibrium Seeking
Tatarenko, T., Shi, W., & Nedić, A. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3046232 · Cited by 150
Self-citationMulti-Agent Reinforcement Learning via Double Averaging Primal-Dual OptimizationPreprint
Wai, H.-T., Yang, Z., Wang, Z., & Hong, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.00877 · Cited by 161
Xin, R., Kar, S., & Khan, U. A. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2974267 · Cited by 114
Hong, M., Hajinezhad, D., & Zhao, M. (2017) · doi:10.13140/rg.2.2.25204.14729 · Cited by 120
Balancing Communication and Computation in Distributed Optimization
Berahas, A. S., Bollapragada, R., Keskar, N. S., & Wei, E. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2880407 · Cited by 136
A General Framework for Decentralized Optimization With First-Order Methods
Xin, R., Pu, S., Nedić, A., & Khan, U. A. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2020.3024266 · Cited by 149
Distributed Aggregative Optimization Over Multi-Agent Networks
Li, X., Xie, L., & Hong, Y. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3095456 · Cited by 125
Wang, D., Wang, Z., & Wen, C. (2019) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2019.2933005 · Cited by 105
The Proximal Augmented Lagrangian Method for Nonsmooth Composite Optimization
Dhingra, N. K., Khong, S. Z., & Jovanovic, M. R. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2867589 · Cited by 149
“Remark 8: Forward Euler discretization of (18) is given by where α is the step-size, and the EXTRA algorithm [43, Equation (2.13)], which has received significant recent attention, can be clearly recovered from (19) by setting β = 1 / (2 αµ ) and taking W = I − ( α/µ ) L in (20).”
InfluentialLiang, S., Wang, L. Y., & Yin, G. (2019) · Automatica · doi:10.1016/j.automatica.2019.04.004 · Cited by 106
Variance-Reduced Decentralized Stochastic Optimization With Accelerated Convergence
Xin, R., Khan, U. A., & Kar, S. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3031071 · Cited by 128
Li, H., Lü, Q., Liao, X., & Huang, T. (2018) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2018.2823901 · Cited by 110
Distributed Optimization for Smart Cyber-Physical Networks
Notarstefano, G., Notarnicola, I., & Camisa, A. (2019) · Foundations and Trends® in Systems and Control · doi:10.1561/2600000020 · Cited by 122
Tailoring Gradient Methods for Differentially Private Distributed Optimization
Wang, Y., & Nedić, A. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3272968 · Cited by 138
Communication-Censored ADMM for Decentralized Consensus Optimization
Liu, Y., Xu, W., Wu, G., Tian, Z., & Ling, Q. H. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2907258 · Cited by 109
Self-citationDistributed Smooth Convex Optimization With Coupled Constraints
Liang, S., Wang, L. Y., & Yin, G. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2912494 · Cited by 116
An Improved Convergence Analysis for Decentralized Online Stochastic Non-Convex Optimization
Xin, R., Khan, U. A., & Kar, S. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3062553 · Cited by 147
A Decentralized Market Model for a Microgrid With Carbon Emission Rights
Mu, C., Ding, T., Zhu, S., Han, O., Du, P., Li, F. F., & Siano, P. (2022) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2022.3173520 · Cited by 102
A Push-Pull Gradient Method for Distributed Optimization in Networks
Pu, S., Shi, W., Xu, J., & Nedic, A. (2018) · 2018 IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619047 · Cited by 94
Self-citationDistributed Zero-Order Algorithms for Nonconvex Multiagent Optimization
Tang, Y., Zhang, J., & Li, N. (2020) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2020.3024321 · Cited by 95
“…consensus-based decentralized gradient descent (DGD) algorithms with O (log t/ √ t ) convergence for nonsmooth convex functions; papers [8], [11], and [12] employed the gradient tracking scheme and showed that the DGD with gradient tracking achieves O (1 /t ) convergence for smooth convex…”
BackgroundOptimization for Reinforcement Learning: From a single agent to cooperative agents
Lee, D., He, N., Kamalaruban, P., & Cevher, V. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2976000 · Cited by 113
Sun, Y., Scutari, G., & Daneshmand, A. (2022) · SIAM Journal on Optimization · doi:10.1137/19m1259973 · Cited by 155
Asynchronous Distributed Algorithms for Solving Linear Algebraic Equations
Liu, J., Mou, S., & Morse, A. S. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2714645 · Cited by 95
Bastianello, N., Carli, R., Schenato, L., & Todescato, M. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3011358 · Cited by 119
“Distributed gradient descent algorithms in general combine local gradient descent steps with consensus averaging, see for example [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14].”
BackgroundDecentralized Learning for Wireless Communications and Networking
Giannakis, G. B., Ling, Q. H., Mateos, G., Schizas, I. D., & Zhu, H. (2016) · Scientific computation · doi:10.1007/978-3-319-41589-5_14 · Cited by 107
Self-citationDistributed Online Convex Optimization With an Aggregative Variable
Li, X., Yi, X., & Xie, L. (2021) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2021.3107480 · Cited by 95
Yi, X., Yao, L., Yang, T., George, J., & Johansson, K. H. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8618989 · Cited by 112
“(Restricted strongly convex, see [31]) The global objective function P =1 f i ( x ) is restricted strongly convex with respect to its global minimizer x ∗ with convexity parameter m f > 0 , i.e., for all x ∈ R p , n X i =1 Remark 1.”
BackgroundInfluentialDistributed Event-Triggered Gradient Method for Constrained Convex Minimization
Liu, C., Li, H., Shi, Y., & Xu, D. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2916985 · Cited by 93
Solving a system of linear equations: From centralized to distributed algorithms
Wang, P., Mou, S., Lian, J. J., & Ren, W. (2019) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2019.04.008 · Cited by 95
Distributed nonconvex multiagent optimization over time-varying networks
Sun, Y., Scutari, G., & Palomar, D. (2016) · 2016 50th Asilomar Conference on Signals, Systems and Computers · doi:10.1109/acssc.2016.7869154 · Cited by 86
FROST—Fast row-stochastic optimization with uncoordinated step-sizes
Xin, R., Xi, C., & Khan, U. A. (2019) · EURASIP Journal on Advances in Signal Processing · doi:10.1186/s13634-018-0596-y · Cited by 122
ZONE: Zeroth-Order Nonconvex Multiagent Optimization Over Networks
Hajinezhad, D., Hong, M., & Garcia, A. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2896025 · Cited by 137
Asynchronous Distributed Optimization Via Randomized Dual Proximal Gradient
Notarnicola, I., & Notarstefano, G. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2607023 · Cited by 87
Parallel and Distributed Successive Convex Approximation Methods for Big-Data Optimization
Scutari, G., & Sun, Y. (2018) · Lecture notes in mathematics · doi:10.1007/978-3-319-97142-1_3 · Cited by 121
Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
Xu, J., Tian, Y., Sun, Y., & Scutari, G. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3086579 · Cited by 109
Variance Reduced Local SGD with Lower Communication Complexity
Liang, X., Shen, S., Liu, J., Pan, Z., Chen, E., & Cheng, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.12844 · Cited by 83
Exact Diffusion for Distributed Optimization and Learning—Part II: Convergence Analysis
Yuan, K., Ying, B., Zhao, X., & Sayed, A. H. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2875883 · Cited by 103
A review of distributed optimization: Problems, models and algorithms
Zheng, Y., & Liu, Q. (2021) · Neurocomputing · doi:10.1016/j.neucom.2021.06.097 · Cited by 98
Distributed Discrete-Time Optimization in Multiagent Networks Using Only Sign of Relative State
Zhang, J., You, K., & Başar, T. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2884998 · Cited by 86
“However, they all require each agent to access the exact relative state information with respect to its neighbors [6]–[9] or the quantized absolute state [10]–[12].”
Forward-Backward-Half Forward Algorithm for Solving Monotone Inclusions
Briceño-Arias, L. M., & Davis, D. (2018) · SIAM Journal on Optimization · doi:10.1137/17m1120099 · Cited by 104
Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization
Doan, T. T., Maguluri, S. T., & Romberg, J. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3014095 · Cited by 100
“1) have a long history, probably first studied in [5] and recently received a wide attention; see for example, [1, 6–11] and the recent survey paper [4].”
BackgroundOptimization and Learning With Information Streams: Time-varying algorithms and applications
Dall’Anese, E., Simonetto, A., Becker, S., & Madden, L. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2968813 · Cited by 86
Stochastic Proximal Gradient Consensus Over Random Networks
Hong, M., & Chang, T. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2673815 · Cited by 85
Improved Convergence Rates for Distributed Resource Allocation
Nedić, A., Olshevsky, A., & Shi, W. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619322 · Cited by 100
“0. The preceding relation and (26) yield xk → x˜. To establish the rate of convergence, we use a convergence property of nonnegative monotonic scalar sequence, which has appeared in recent work [27], [28]. The result is stated in the following: Proposition 1. If a sequence {ak} ⊂ R is such that ak ≥ 0, P∞ t=1 at <…”
MethodSelf-citationLi, L., Yu, Y., Li, X., & Xie, L. (2022) · Automatica · doi:10.1016/j.automatica.2022.110259 · Cited by 91
Distributed Energy Resource Coordination Over Time-Varying Directed Communication Networks
Yang, T., Wu, D. X., Fang, H., Ren, W., Wang, H., Hong, Y., & Johansson, K. H. (2019) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2019.2921284 · Cited by 80
Linear Time Average Consensus and Distributed Optimization on Fixed Graphs
Olshevsky, A. (2017) · SIAM Journal on Control and Optimization · doi:10.1137/16m1076629 · Cited by 87
A Distributed Stochastic Gradient Tracking Method
Pu, S., & Nedić, A. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8618708 · Cited by 70
Optimal Algorithms for Non-Smooth Distributed Optimization in NetworksPreprint
Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., & Massoulié, L. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.00291 · Cited by 172
Variance-Reduced Stochastic Learning by Networked Agents Under Random Reshuffling
Yuan, K., Ying, B., Liu, J., & Sayed, A. H. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2872003 · Cited by 67
ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks
Zeng, J., & Yin, W. (2017) · Journal of Computational Mathematics · doi:10.4208/jcm.1606-m2015-0452 · Cited by 82
Self-citation
Metadata
- Authors
- Shi, W., Ling, Q., Wu, G., & Yin, W.
- Venue
- SIAM Journal on Optimization
- Published
- 2015-01
- Volume
- 25
- Issue
- 2
- Pages
- 944-966
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W1571416372
- Cited by
- 1,261
- References
- 25
- Citations by year
- 2026: 75 · 2025: 116 · 2024: 131 · 2023: 131 · 2022: 145 · 2021: 138 · 2020: 158 · 2019: 140 · 2018: 97 · 2017: 62 · 2016: 43 · 2015: 21
- FWCI
- 85.01
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- SIAM Journal on Optimization (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (0748839, 1317602)
- National Natural Science Foundation of China (61004137)
- China Scholarship Council
- Ministry of Industry and Information Technology of the People's Republic of China
- 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 › Computer Networks and Communications › Distributed Sensor Networks and Detection Algorithms
- Keywords
- multi-agent systems, large step size, linear convergence, ergodic convergence rate, strongly convex functions, distributed optimization
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.
The claim verdicts this report counts are experimental: their accuracy is not yet measured.
A language model drew the claims from the paper on 2026-10-10, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-10-10 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Cited sources are checked with a language model’s help (qwen3.8-omni-flash).
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.