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
Items 301–400 of 1,315
Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk MinimizationPreprint
Zhang, J., & You, K. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.02712 · Cited by 54
Jiang, X., Zeng, X., Sun, J. Q., & Chen, J. (2022) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3170944 · Cited by 28
Nash equilibrium computation in two-network zero-sum games: An incremental algorithm
Shi, C., & Yang, G. (2019) · Neurocomputing · doi:10.1016/j.neucom.2019.05.076 · Cited by 23
Towards Accelerated Rates for Distributed Optimization over Time-Varying Networks
Rogozin, A., Lukoshkin, V., Gasnikov, A. V., Kovalev, D. A., & Shulgin, E. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-91059-4_19 · Cited by 23
Distributed decision-coupled constrained optimization via Proximal-Tracking
Falsone, A., & Prandini, M. (2021) · Automatica · doi:10.1016/j.automatica.2021.109938 · Cited by 29
Distributed Variable Sample-Size Stochastic Optimization With Fixed Step-Sizes
Lei, J., Yi, P., Chen, J., & Hong, Y. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3179216 · Cited by 28
Byzantine-Resilient Resource Allocation Over Decentralized Networks
Wang, R., Liu, Y., & Ling, Q. H. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3209010 · Cited by 30
Self-citationMeng, X., & Liu, Q. (2022) · Neurocomputing · doi:10.1016/j.neucom.2022.11.051 · Cited by 26
Distributed consensus-based multi-agent convex optimization via gradient tracking technique
Li, H., Zhang, H., Wang, Z., Zhu, Y., & Han, Q. (2019) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2019.01.050 · Cited by 23
Geometric convergence of distributed gradient play in games with unconstrained action sets
Tatarenko, T., & Nedić, A. (2020) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2020.12.1501 · Cited by 23
Asynchronous Optimization Over Graphs: Linear Convergence Under Error Bound Conditions
Cannelli, L., Facchinei, F., Scutari, G., & Kungurtsev, V. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3033490 · Cited by 27
Compressed Gradient Tracking Algorithm for Distributed Aggregative Optimization
Chen, L., Wen, G., Liu, H., Yu, W., & Cao, J. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3371876 · Cited by 26
Exact Convergence of Gradient-Free Distributed Optimization Method in a Multi-Agent System
Pang, Y., & Hu, G. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619028 · Cited by 18
Research status and prospects of distributed collaborative optimization
Chai, T., & Yang, T. (2020) · Scientia Sinica Technologica · doi:10.1360/sst-2020-0040 · Cited by 23
Primal–Dual Fixed Point Algorithms Based on Adapted Metric for Distributed Optimization
Li, H., Zheng, Z., Lü, Q., Wang, Z., Gao, L., Wu, G., Ji, L., & Wang, H. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3110295 · Cited by 23
“Similarly, Li et al. [38] proposed NIDS algorithm by combining EXTRA [31] and proximal operations, which achieved the same convergence as [37] and could employ a larger stepsize.”
Self-citationDecentralized Optimization Over the Stiefel Manifold by an Approximate Augmented Lagrangian Function
Wang, L., & Liu, X. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3182883 · Cited by 46
A Family of Distributed Momentum Methods Over Directed Graphs With Linear Convergence
Gao, J., Liu, X., Dai, Y., Huang, Y., & Yang, P. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3160684 · Cited by 24
“We also compare PDM with EXTRA [9] and the gradient tracking method [10]–[12] over an undirected graph with n = 500 agents.”
MethodGuo, L., Shi, X., Cao, J., & Wang, Z. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3250839 · Cited by 27
DISA: A Dual Inexact Splitting Algorithm for Distributed Convex Composite Optimization
Guo, L., Shi, X., Yang, S., & Cao, J. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3301289 · Cited by 31
“Furthermore, when the conic constraint sets are defined by nonlinear functions (covering COP (1)), DPDA and DPDA-TV have been developed in [7] for static and time-varying networks, respectively.”
Consensus optimization with delayed and stochastic gradients on decentralized networks
Sirb, B., & Ye, X. (2016) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata.2016.7840591 · Cited by 40
Maros, M., & Jaldén, J. (2019) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2019.2892055 · Cited by 26
Primal-dual stochastic distributed algorithm for constrained convex optimization
Niu, Y., Wang, H., Wang, Z., Xia, D., & Li, H. (2019) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2019.07.018 · Cited by 23
Yi, X., Zhang, S., Yang, T., Chai, T., & Johansson, K. H. (2020) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2020.12.383 · Cited by 30
Zhang, J., Liu, H., So, A. M., & Ling, Q. H. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3092347 · Cited by 27
“We also demonstrate the connection between PAD and several dual domain methods, including EXTRA [19], DLM [14], and PG-EXTRA [20].”
InfluentialSelf-citationA Sharp Convergence Rate Analysis for Distributed Accelerated Gradient MethodsPreprint
Li, H., Fang, C., Yin, W., & Lin, Z. (2018) · arXiv (Cornell University) · Cited by 25
Self-citationAchieving Linear Convergence in Distributed Aggregative Optimization Over Directed Graphs
Chen, L., Wen, G., Fang, X., Zhou, J., & Cao, J. (2024) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2024.3382173 · Cited by 25
Decentralized Sparse Multitask RLS Over Networks
Cao, X., & Liu, K. J. R. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2750110 · Cited by 21
Li, J., Zhu, X., Wu, Z., & Huang, T. (2021) · Information Sciences · doi:10.1016/j.ins.2021.10.003 · Cited by 21
Distributed adaptive Newton methods with global superlinear convergence
Zhang, J., You, K., & Başar, T. (2022) · Automatica · doi:10.1016/j.automatica.2021.110156 · Cited by 31
A Bi-Event-Triggered Multi-Agent System for Distributed Optimization
Huang, B., Liu, Y., Xia, Z., et al. (2022) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2022.3226763 · Cited by 21
Luan, M., Wen, G., Liu, H., Huang, T., Chen, G., & Yu, W. (2023) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2023.3270185 · Cited by 28
AB /Push-Pull method for distributed optimization in time-varying directed networks
Nedić, A., Nguyen, D. T. A., & Nguyen, D. T. (2023) · Optimization methods & software · doi:10.1080/10556788.2023.2261602 · Cited by 42
“Reference [25] uses a gradient difference structure in the algorithm to provide the first-order method that achieves a geometric convergence with the requirement of symmetric weights.”
A geometrically convergent method for distributed optimization over time-varying graphs
Nedić, A., Olshevsky, A., & Shi, W. (2016) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798402 · Cited by 25
Self-citationAccelerated Distributed Dual Averaging Over Evolving Networks of Growing Connectivity
Liu, S., Chen, P., & Hero, A. O. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2793878 · Cited by 21
Distributed Finite-Time Optimization
Yao, L., Yuan, Y., Sundaram, S., & Yang, T. (2018) · International Conference on Control and Automation · doi:10.1109/icca.2018.8444343 · Cited by 27
Walk Proximal Gradient: An Energy-Efficient Algorithm for Consensus Optimization
Mao, X., Gu, Y., & Yin, W. (2018) · IEEE Internet of Things Journal · doi:10.1109/jiot.2018.2875057 · Cited by 26
Self-citationShi, C., & Yang, G. (2020) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2020.3011837 · Cited by 21
“First, a distributed logistic regression problem (see e.g., [9] and [32]) is considered.”
BackgroundA Push-Pull Gradient Method for Distributed Optimization in NetworksPreprint
Pu, S., Shi, W., Xu, J., et al. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.07588 · Cited by 21
Self-citationLi, H., Lin, Z., & Fang, Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.04373 · Cited by 40
“In this paper, we extend two widely used decentralized algorithms of EXTRA (Shi et al., 2015) and DIGing (Nedić et al., 2017; Qu & Li, 2018), which have sparked a lot of interest in the distributed optimization community, to stochastic decentralized optimization by combining them with the powerful…”
BackgroundMethodInfluentialLinear Convergent Decentralized Optimization with CompressionPreprint
Liu, X., Li, Y., Wang, R., Tang, J., & Yan, M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2007.00232 · Cited by 47
Local Exact-Diffusion for Decentralized Optimization and Learning
Alghunaim, S. A. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3383271 · Cited by 52
“…have introduced bias-correction algorithms resistant to local function heterogeneity, such as the alternating-direction-method-of-multipliers-based methods [31], [32], EXTRA [33], ED [12], [13] (also known as NIDS [34] and D 2 [35]), and gradient-tracking ( GT ) methods [36], [37], [38], [39].”
ADMM-Tracking Gradient for Distributed Optimization Over Asynchronous and Unreliable Networks
Carnevale, G., Bastianello, N., Notarstefano, G., & Carli, R. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3539454 · Cited by 32
“GT algorithms were then introduced to guarantee exact convergence with fixed step-sizes, see [4], [5], [6], and have proved their versatility in different setups, see, e.g., [7], [8], [9], [10], [11], [12], [13].”
Distributed optimization model and algorithms for virtual energy storage systems using dynamic price
Kang, W., Chen, M., Li, Q., Lai, W., Luo, Y., & Tavner, P. (2020) · Journal of Cleaner Production · doi:10.1016/j.jclepro.2020.125440 · Cited by 21
Fast and Communication-efficient Distributed Pca
Gang, A., Raja, H., & Bajwa, W. U. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8683095 · Cited by 20
Achieving Acceleration in Distributed Optimization via Direct Discretization of the Heavy-Ball ODE
Zhang, J., Uribe, C. A., Mokhtari, A., & Jadbabaie, A. (2019) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2019.8814686 · Cited by 23
Convergence of Distributed Accelerated Algorithm Over Unbalanced Directed Networks
Li, H., Lü, Q., Chen, G., Huang, T., & Dong, Z. Y. (2019) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2019.2946287 · Cited by 19
“To accelerate convergence, Xi and Khan [33] proposed a novel fast distributed gradient method (DEXTRA) with constant step-size by incorporating push-sum technique into the protocol (EXTRA) of [14].”
BackgroundMethodPrivate Weighted Random Walk Stochastic Gradient Descent
Ayache, G., & Rouayheb, S. E. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3052975 · Cited by 33
Fast Attack-Resilient Distributed State Estimator for Cyber-Physical Systems
Yu, F., Dutta, R. G., Zhang, T., Hu, Y., & Jin, Y. (2020) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2020.3013072 · Cited by 21
“Shi et al. [24] proposed an algorithm called EXTRA which converged to the true solution, but the authors considered a fixed step size to obtain a higher convergence rate.”
MethodCoded Stochastic ADMM for Decentralized Consensus Optimization With Edge Computing
Chen, H., Ye, Y., Xiao, M., Skoglund, M., & Poor, H. V. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2021.3058116 · Cited by 20
A Primal-Dual Forward-Backward Splitting Algorithm for Distributed Convex Optimization
Li, H., Su, E., Wang, C., Liu, J., Zheng, Z., Wang, Z., & Xia, D. (2021) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2021.3098831 · Cited by 22
“A few notable distributed methods to solve this problem are gradient-based methods [29]–[32].”
MethodHong, M., Lee, J. D., & Razaviyayn, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.08941 · Cited by 24
Asynchronous Accelerated Proximal Stochastic Gradient for Strongly Convex Distributed Finite SumsPreprint
Hendrikx, H., Bach, F., & Massoulié, L. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.09865 · Cited by 23
Distributed Subgradient Algorithm for Multi-Agent Optimization With Dynamic Stepsize
Ren, X., Li, D., Xi, Y., & Shao, H. (2021) · IEEE/CAA Journal of Automatica Sinica · doi:10.1109/jas.2021.1003904 · Cited by 20
FlexPD: A Flexible Framework of First-Order Primal-Dual Algorithms for Distributed Optimization
Mansoori, F., & Wei, E. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3083981 · Cited by 24
Distributed Gradient Tracking Methods with Finite Data Rates
Ma, X., Yi, P., & Chen, J. (2021) · Journal of Systems Science and Complexity · doi:10.1007/s11424-021-1231-9 · Cited by 19
Distributed aggregative optimization with quantized communication
Chen, Z., & Liang, S. (2022) · Kybernetika · doi:10.14736/kyb-2022-1-0123 · Cited by 25
Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms
Salim, A., Condat, L., Mishchenko, K., & Richtárik, P. (2022) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-022-02061-8 · Cited by 53
FAST-PCA: A Fast and Exact Algorithm for Distributed Principal Component Analysis
Gang, A., & Bajwa, W. U. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3229635 · Cited by 23
Chen, T.-Y., Chen, W., Wei, F.-F., Hu, X.-M., & Zhang, J. (2024) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2024.3380436 · Cited by 30
“For discrete-time optimization, representative algorithms are EXTRA (an exact first-order algorithm) [11], distributed proportional-integral algorithms [13], DIGing (distributed inexact gradient method and the gradient tracking technique) [9], and distributed Newton-Raphson algorithm [10].”
Qiu, Z., Liu, S., & Xie, L. (2018) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.4040 · Cited by 18
Pang, Y., & Hu, G. (2017) · Asian Control Conference (ASCC) · doi:10.1109/ascc.2017.8287157 · Cited by 16
Linearized ADMM Converges to Second-Order Stationary Points for Non-Convex Problems
Lu, S., Lee, J. D., Razaviyayn, M., & Hong, M. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3100976 · Cited by 26
A variational approach to dual methods for constrained convex optimization
Fazlyab, M., Koppel, A., Preciado, V. M., et al. (2017) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2017.7963773 · Cited by 19
Decentralized online convex optimization with compressed communications
Cao, X., & Başar, T. (2023) · Automatica · doi:10.1016/j.automatica.2023.111186 · Cited by 18
Decentralized Consensus Optimization and Resource Allocation
Nedić, A., Olshevsky, A., & Shi, W. (2018) · Lecture notes in mathematics · doi:10.1007/978-3-319-97478-1_10 · Cited by 19
Self-citationA Computation-Efficient Decentralized Algorithm for Composite Constrained Optimization
Lü, Q., Liao, X., Li, H., & Huang, T. (2020) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2020.3037837 · Cited by 23
Wang, Y., Liu, S., Sun, B. N., & Li, X. (2022) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2022.3143157 · Cited by 20
“1) EXTRA [34]: EXTRA aims to solve differential problems, i.e., h = 0.”
BackgroundDistributed forward-backward methods for ring networks
Artacho, F. J. A., Malitsky, Y., Tam, M. K., et al. (2022) · Computational Optimization and Applications · doi:10.1007/s10589-022-00400-z · Cited by 18
Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning
Zhang, J., Liu, H., So, A. M., & Ling, Q. H. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3240652 · Cited by 24
“Since the gradient approximations g k +1 are noisy due to stochastic gradient noise and disagreement among the nodes, naively adopting centralized quasi-Newton methods may lead to almost-singular Hessian inverse approximations (i.e., either λ min ( H k +1 ) → 0 or λ max ( H k +1 ) → ∞ ) or even…”
Self-citationDecentralized multi-task stochastic optimization with compressed communications
Singh, N., Cao, X., Diggavi, S. N., & Başar, T. (2023) · Automatica · doi:10.1016/j.automatica.2023.111363 · Cited by 25
A Gradient Tracking Protocol for Optimization Over Nabla Fractional Multi-Agent Systems
Zhou, S., Wei, Y., Liang, S., & Cao, J. (2024) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2024.3402354 · Cited by 24
Yan, J., Shi, X., Guo, L., Wan, Y., & Wen, G. (2024) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2024.3407660 · Cited by 21
Distributed nonconvex optimization for sparse representation
Sun, Y., & Scutari, G. (2017) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2017.7952916 · Cited by 18
Convergence analysis of a distributed gradient algorithm for economic dispatch in smart grids
Zhang, H., Liang, S., Jing, L., & Han, Y. (2021) · International Journal of Electrical Power & Energy Systems · doi:10.1016/j.ijepes.2021.107373 · Cited by 19
Local Prediction for Enhanced Convergence of Distributed Optimization Algorithms
Mai, V. S., & Abed, E. H. (2017) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2017.2776084 · Cited by 19
A Geometrically Converging Dual Method for Distributed Optimization Over Time-Varying Graphs
Maros, M., & Jaldén, J. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3018743 · Cited by 21
Decentralized Multi-Agent Reinforcement Learning with Networked Agents: Recent AdvancesPreprint
Zhang, K., Yang, Z., & Başar, T. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.03821 · Cited by 18
Accelerated Distributed Aggregative Optimization
Liu, J., Chen, S., Cai, S., Xu, C., & Chu, J. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3546096 · Cited by 24
“In [14], an algorithm called EXTRA was proposed to achieve geometric convergence to the global optimal solution by introducing a cumulative correction term.”
A comprehensive experimental comparison between federated and centralized learning
Garst, S. J. F., Dekker, J., & Reinders, M. J. T. (2025) · Database · doi:10.1093/database/baaf016 · Cited by 24
Optimal gradient tracking for decentralized optimization
Song, Z., Shi, L., Pu, S., & Yan, M. (2023) · Mathematical Programming · doi:10.1007/s10107-023-01997-7 · Cited by 62
“EXTRA [51] is the first gradient-type method that achieves linear convergence for strongly convex and smooth objective functions by introducing an extra correction term to DGD. Subsequently, distributed ADMM methods [5, 29], NIDS [27], and exact diffusion method [68] were also shown to exhibit linear…”
Wang, Y., & Nedić, A. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3348158 · Cited by 28
On the Performance of Gradient Tracking with Local Updates
Nguyen, E. D. H., Alghunaim, S. A., Yuan, K., & Uribe, C. A. (2023) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc49753.2023.10383873 · Cited by 41
Privacy-Preserving Push-Pull Method for Decentralized Optimization via State Decomposition
Cheng, H., Liao, X., Li, H., Lü, Q., & Zhao, Y. (2024) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2024.3402430 · Cited by 25
Online Learning over a Decentralized Network Through ADMM
Xu, H.-F., Ling, Q. H., & Ribeiro, A. (2015) · Journal of the Operations Research Society of China · doi:10.1007/s40305-015-0104-0 · Cited by 16
“Indeed, decentralized batch optimization in a multi-agent network has received extensive research interests recently [2–6].”
BackgroundSelf-citationDoan, T. T., Beck, C. L., & Srikant, R. (2018) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/3219617.3219654 · Cited by 18
Scaling-Up Distributed Processing of Data Streams for Machine Learning
Nokleby, M., Raja, H., & Bajwa, W. U. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2020.3021381 · Cited by 27
“Several extensions to DGD have been proposed in the literature, including extensions to time-varying and directed graphs [90]–[92] and variations with stronger convergence guarantees [93]–[95].”
BackgroundA fast proximal gradient algorithm for decentralized composite optimization over directed networks
Zeng, J., He, T., & Wang, M. (2017) · Systems & Control Letters · doi:10.1016/j.sysconle.2017.07.005 · Cited by 17
Decentralized computation of effective resistances and acceleration of consensus algorithms
Aybat, N. S., & Gürbüzbalaban, M. (2017) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2017.8308701 · Cited by 19
Slavakis, K., & Yamada, I. (2018) · Optimization · doi:10.1080/02331934.2018.1505885 · Cited by 22
Distributed Nonconvex Multiagent Optimization Over Time-Varying NetworksPreprint
Sun, Y., Scutari, G., & Palomar, D. P. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1607.00249 · Cited by 17
Fully Asynchronous Distributed Optimization with Linear Convergence in Directed NetworksPreprint
Zhang, J., & You, K. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.08215 · Cited by 43
“It has also been widely studied in the control community, see e.g. [11] for a comprehensive review, and novel algorithms such as DGD [12], DDA [13] and EXTRA [14] have been developed.”
BackgroundSublinear and Linear Convergence of Modified ADMM for Distributed Nonconvex Optimization
Yi, X., Zhang, S., Yang, T., Chai, T., & Johansson, K. H. (2022) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2022.3186653 · Cited by 22
Convergence Rate of Incremental Gradient and Incremental Newton Methods
Gürbüzbalaban, M., Ozdaglar, A., & Parrilo, P. A. (2019) · SIAM Journal on Optimization · doi:10.1137/17m1147846 · Cited by 43
Decentralized and Privacy-Preserving Low-Rank Matrix Completion
Lin, A.-Y., & Ling, Q. H. (2015) · Journal of the Operations Research Society of China · doi:10.1007/s40305-015-0080-4 · Cited by 16
Self-citationAccelerated distributed Nesterov Gradient Descent for convex and smooth functions
Qu, G., & Li, N. (2017) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2017.8263979 · Cited by 19
A fully distributed method for distributed multiagent system in a microgrid
Ghaderyan, D., Перейра, Ф. Л., & Aguiar, A. P. (2021) · Energy Reports · doi:10.1016/j.egyr.2021.03.035 · Cited by 16
Achieving geometric convergence for distributed optimization with Barzilai-Borwein step sizes
Gao, J., Liu, X., Dai, Y., Huang, Y., & Yang, P. (2021) · Science China Information Sciences · doi:10.1007/s11432-020-3256-x · Cited by 27
Data-Dependent Convergence for Consensus Stochastic Optimization
Bijral, A. S., Sarwate, A. D., & Srebro, N. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2671377 · Cited by 34
Diffusion Learning in Non-convex Environments
Vlaski, S., & Sayed, A. H. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8683707 · Cited by 14
“Algorithms for the solution of (1) have been studied extensively over recent years both with inexact [1–3] and exact [4–6] gradients.”
BackgroundExact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm DevelopmentPreprint
Yuan, K., Ying, B., Zhao, X., et al. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1702.05122 · Cited by 16
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.