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 701–800 of 1,315
Linear Convergence for Distributed Optimization Without Strong Convexity
Yi, X., Zhang, S., Yang, T., Chai, T., & Johansson, K. H. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9304381 · Cited by 8
“In [12], the authors proposed the distributed exact first-order algorithm (EXTRA) to solve the smooth convex optimization problem and proved the linear convergence under the assumptions that the global cost function is restricted strongly convex and the optimal set is a singleton.”
InfluentialSelf-Healing First-Order Distributed Optimization
Ridgley, I. L. D., Freeman, R. A., & Lynch, K. (2021) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc45484.2021.9683487 · Cited by 5
Optimal Diffusion Learning Over Networks—Part II: Multitask Algorithms
Merched, R. (2022) · IEEE Open Journal of Signal Processing · doi:10.1109/ojsp.2022.3141965 · Cited by 5
Communication-Efficient Decentralized Subspace Estimation
Jiao, Y., & Gu, Y. (2022) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2022.3157437 · Cited by 5
A Decentralized Stochastic Algorithm for Coupled Composite Optimization With Linear Convergence
Lü, Q., Liao, X., Deng, S., & Li, H. (2022) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2022.3190743 · Cited by 8
A Modified Gradient Flow for Distributed Convex Optimization on Directed Networks
Jahvani, M., & Guay, M. (2022) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc53348.2022.9867634 · Cited by 5
CPCA: A Chebyshev Proxy and Consensus based Algorithm for General Distributed Optimization
He, Z., He, J., Chen, C., & Guan, X. (2020) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc45564.2020.9147791 · Cited by 4
On the Linear Convergence of Two Decentralized Algorithms
Li, Y., & Yan, M. (2021) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-021-01833-y · Cited by 9
Augmented distributed optimization for networked systems
Xu, J. (2019) · doi:10.32657/10356/68805 · Cited by 5
A Fast Distributed Asynchronous Newton-Based Optimization AlgorithmPreprint
Mansoori, F., & Wei, E. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.01872 · Cited by 5
Distributed Online Convex Optimization with Improved Dynamic RegretPreprint
Zhang, Y., Ravier, R., Tarokh, V., & Zavlanos, M. M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.05127 · Cited by 11
Primal-dual methods for large-scale and distributed convex optimization and data analyticsPreprint
Jakovetić, D., Bajović, D., Xavier, J., et al. (2021) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.4427250 · Cited by 5
Distributed Nonconvex Optimization: Gradient-free Iterations and Globally Optimal SolutionPreprint
He, Z., He, J., Chen, C., & Guan, X. (2020) · arXiv (Cornell University) · Cited by 5
Distributed Online Optimization via Gradient Tracking with Adaptive Momentum.Preprint
Carnevale, G., Farina, F., Notarnicola, I., & Notarstefano, G. (2020) · arXiv (Cornell University) · Cited by 5
On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized OptimizationPreprint
Hashemi, A., Acharya, A., Das, R., Vikalo, H., Sanghavi, S., & Dhillon, I. S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.10643 · Cited by 7
“In the decentralized setting under strong convexity (SC), without using techniques such as gradient tracking [45], DGD based schemes use either η = O(1t ) to have O(1/ ) rounds of communication (e.”
BackgroundMethodInfluentialPMGT-VR: A decentralized proximal-gradient algorithmic framework with variance reductionPreprint
Ye, H., Xiong, W., & Zhang, T. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.15010 · Cited by 5
“Competitors and plots: We compare the proposed PMGT-LSVRG and PMGT-SAGA with the PG-EXTRA [25] and NIDS [18] because the contributions of [26] mainly focus on the theoretical analysis and the authors show that NIDS achieves the state-of-the-art rate in the existing full-gradient-based algorithms.”
InfluentialCompressed Gradient Tracking for Decentralized Optimization with Linear Convergence.Preprint
Li, Z., Liao, Y., Huang, K., & Pu, S. (2021) · arXiv (Cornell University) · Cited by 3
Improving the Transient Times for Distributed Stochastic Gradient MethodsPreprint
Huang, K., & Pu, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2105.04851 · Cited by 5
“We study the following algorithm adapted from EXTRA [28], Exact Diffusion [37], NIDS [11] and D 2 [30], where the main characteristics of EDAS lie in the diminishing stepsize policy Algorithm 2.1 EDAS (Exact Diffusion with Adaptive Stepsizes) for some θ > 0 and m > 0.”
InfluentialInnovation Compression for Communication-efficient Distributed Optimization with Linear ConvergencePreprint
Zhang, J., You, K., & Xie, L. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2105.06697 · Cited by 5
MARL with General Utilities via Decentralized Shadow Reward Actor-CriticPreprint
Zhang, J., Bedi, A. S., Wang, M., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.00543 · Cited by 5
On the Convergence of Decentralized Adaptive Gradient MethodsPreprint
Chen, X., Karimi, B., Zhao, W., & Li, P. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2109.03194 · Cited by 16
Berahas, A. S., Bollapragada, R., & Wei, E. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3094906 · Cited by 17
Duan, M., Zhu, S., Yang, Z., et al. (2025) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2025.3574852 · Cited by 4
“Problem(7)isastandarddistributedoptimiza-tionproblem,andtherearelotsofdistributedalgorithmseither indiscrete-time[6],[7],[8],[9],[10],[11]orincontinuous-time[12],[13]thatcanbeusedtosolveit.”
Collaborative Multi-Agent Video Fast-Forwarding
Lan, S., Wang, Z., Wei, E., Roy–Chowdhury, A. K., & Zhu, Q. (2023) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2023.3275853 · Cited by 10
“Morerecently,EXTRA[56],whichtakesacarefulcombination ofgradientandconsensussteps,isproposedtoimprovecon-vergencespeedandisshowntoachievelinearconvergencewith constantstepsize.”
Distributed multi-timescale algorithm for nonconvex optimization problem: A control perspective
Shi, X., Liu, J., & Sun, C. (2025) · Neural Networks · doi:10.1016/j.neunet.2025.107257 · Cited by 6
On Graphs with Finite-Time Consensus and Their Use in Gradient Tracking
Nguyen, E. D. H., Jiang, X., Ying, B., & Uribe, C. A. (2025) · SIAM Journal on Optimization · doi:10.1137/24m1661455 · Cited by 14
An Analysis Tool for Push-Sum-Based Distributed Optimization
Lin, Y., Zhu, Z., & Liu, J. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3596669 · Cited by 5
“Althoughtheanalysisofthepush-sumalgorithmiselegant,the analysesofpush-sum-basedalgorithmsareoftenquitecomplicated, e.g.,subgradient-push[6],DEXTRA[12](apush-sum-basedvariant ofthewell-knownEXTRAalgorithm[13])andPush-DIGing[14].”
Distributed Consensus Optimization with Consensus ALADIN
Du, X., & Wang, J. (2025) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc63710.2025.11107815 · Cited by 8
An asynchronous Quasi-Newton method for consensus optimization
Eisen, M., Mokhtari, A., & Ribeiro, A. (2016) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2016.7905906 · Cited by 4
An accelerated algorithm for distributed optimization with Barzilai-Borwein step sizes
Zhang, X., Liu, S., & Zhao, N. (2022) · Signal Processing · doi:10.1016/j.sigpro.2022.108748 · Cited by 7
Distributed Stochastic Consensus Optimization Using Communication-Censoring Strategy
Li, R., Xu, W., & Yu, F. (2023) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2023.3281561 · Cited by 4
He, Z., He, J., Chen, C., & Guan, X. (2024) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2024.3395723 · Cited by 8
Accelerating Distributed Nash Equilibrium Seeking
Tatarenko, T., & Nedić, A. (2024) · European Control Conference (ECC) · doi:10.23919/ecc64448.2024.10590834 · Cited by 4
Distributed aggregative optimization over directed networks with column-stochasticity
Zhou, Q., Zhang, K., Zhou, H., Lü, Q., Liao, X., & Li, H. (2024) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2024.107492 · Cited by 5
Two-Group Distributed Optimization Under Cooperative-Collaborative Networks With Linear Convergence
Dong, Z., Mao, S., Du, W., Jin, Y., & Tang, Y. S. (2025) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2024.3524548 · Cited by 4
The Effectiveness of Local Updates for Decentralized Learning Under Data Heterogeneity
Wu, T., Li, Z., & Sun, Y. (2025) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2025.3533208 · Cited by 12
“Problem (1) has found applications in many areas, including machine learning, signal processing, telecommunications, finance, multi-agent control,etc. [1]–[4].”
A Unifying System Theory Framework for Distributed Optimization and Games
Carnevale, G., Mimmo, N., & Notarstefano, G. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3573800 · Cited by 4
“Indeed, as we will see also later, some popular consensus-oriented schemes (see [47]) widely adopted in distributed optimization (see, e.g., [48], [49], and [50]) require initialization in a subset S z .”
Decentralized Riemannian Natural Gradient Methods with Kronecker Product Approximations
Hu, J. J., Deng, K., & Li, Q.-Z. (2025) · Journal of the Operations Research Society of China · doi:10.1007/s40305-025-00583-2 · Cited by 11
Distributed Stochastic Mirror Descent Algorithm Over Time-varying Network
Wang, Y., Zhou, H., & Hong, Y. (2018) · International Conference on Control and Automation · doi:10.1109/icca.2018.8444276 · Cited by 6
Han, S. (2019) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2019.8815081 · Cited by 5
BFGS-ADMM for Large-Scale Distributed Optimization
Li, Y., Gong, Y., Freris, N. M., Voulgaris, P. G., & Stipanović, D. M. (2021) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc45484.2021.9683678 · Cited by 8
Hayashi, N., & Nagahara, M. (2022) · Advanced Robotics · doi:10.1080/01691864.2022.2099764 · Cited by 4
“proposed a distributed proximal gradient algorithm that converges to the solution for the first-order optimality criteria at the rate of O(1/k), where k is the number of iterations in the algorithm [53].”
DISH: A Distributed Hybrid Primal-Dual Optimization Framework to Utilize System Heterogeneity
Niu, X., & Wei, E. (2022) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc51059.2022.9993156 · Cited by 4
A stochastic averaging gradient algorithm with multi‐step communication for distributed optimization
Zheng, Z., Yan, Y., Feng, L., Du, Z., Li, H., Wang, Z., & Hu, J. (2023) · Optimal Control Applications and Methods · doi:10.1002/oca.2973 · Cited by 4
Compressed Differentially Private Distributed Optimization with Linear Convergence
Xie, A., Yi, X., Wang, X., Cao, M., & Ren, X. (2023) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2023.10.1029 · Cited by 3
Gossip-based distributed stochastic mirror descent for constrained optimization
Fang, X., Zhang, B., & Yuan, D. (2024) · Neural Networks · doi:10.1016/j.neunet.2024.106291 · Cited by 8
Berahas, A. S., Bollapragada, R., & Gupta, S. (2024) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-024-02554-8 · Cited by 18
“Our proposed algorithmic framework is iterative and works with inner and outer loops.”
InfluentialMultiagent Distributed Optimization
Rabbat, M., & Ribeiro, A. (2018) · Elsevier eBooks · doi:10.1016/b978-0-12-813677-5.00005-5 · Cited by 4
Berglund, E., Magnússon, S., & Johansson, M. (2021) · IEEE Signal Processing Letters · doi:10.1109/lsp.2021.3084510 · Cited by 4
A Graph Neural Network Based Decentralized Learning Scheme
Gao, H., Lee, M., Yu, G., & Zhou, Z. (2022) · Sensors · doi:10.3390/s22031030 · Cited by 6
A distributed algorithm for dictionary learning over networks
Zhao, M.-M., Shi, Q., & Hong, M. (2016) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2016.7905893 · Cited by 6
Multi-agent constrained optimization of a strongly convex function
Hamedani, E. Y., & Aybat, N. S. (2017) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2017.8309021 · Cited by 4
Capri: Consensus Accelerated Proximal Reweighted Iteration for A Class of Nonconvex Minimizations
Sun, T., & Li, D. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.2989393 · Cited by 4
Zhang, S., Pananjady, A., & Romberg, J. (2022) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc51059.2022.9993276 · Cited by 4
Distributed Subgradient Projection Algorithm over Directed GraphsPreprint
Xi, C., & Khan, U. A. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.00653 · Cited by 4
A Distributed Stochastic Gradient Tracking MethodPreprint
Pu, S., & Nedić, A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.07741 · Cited by 4
Geometric Convergence for Distributed Optimization with Barzilai-Borwein Step SizesPreprint
Gao, J., Liu, X., Dai, Y., Huang, Y., & Yang, P. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.07852 · Cited by 4
Yi, X., Zhang, S., Yang, T., Johansson, K. H., & Chai, T. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.03282 · Cited by 3
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and GossipPreprint
Loizou, N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.12176 · Cited by 4
Pan, T., Liu, J., & Wang, J. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.12665 · Cited by 4
A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!Preprint
Kovalev, D. A., Koloskova, A., Jaggi, M., Richtárik, P., & Stich, S. U. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.01697 · Cited by 75
A fast randomized incremental gradient method for decentralized non-convex optimizationPreprint
Xin, R., Khan, U. A., & Kar, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.03853 · Cited by 4
FedHybrid: A Hybrid Primal-Dual Algorithm Framework for Federated OptimizationPreprint
Niu, X., & Wei, E. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.01279 · Cited by 4
“Primal iterative methods, including distributed (sub)-gradient descent (DGD) and related methods [20, 25], have updates in the form of some linear combinations of a gradient descent step with respect to its local objective function and a weighted average with local neighbors.”
Decentralized Composite Optimization with CompressionPreprint
Li, Y., Liu, X., Tang, J., Yan, M., & Yuan, K. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.04448 · Cited by 13
“Decentralized algorithms such as PG-EXTRA (Shi et al., 2015b) and NIDS (Li et al., 2019) are proposed for composite optimization, and the sublinear rate is proved when the smooth component is strongly convex and smooth.”
Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learning
Zhao, X., Lei, J., Li, L., Buşoniu, L., & Xu, J. (2025) · Journal of Systems Science and Complexity · doi:10.1007/s11424-025-4426-7 · Cited by 8
“Decentralized double stochastic averaging gradient [42] was the first de-centralized variance reduction method, obtained by combining exact first order algorithm [43] and SAGA [33] , and linear convergence was shown under strong convexity of local functions and Lipschitz continuity of local gradients.”
Distributed Optimization Under Information Constraints: A Survey
Liu, S., Hua, Y., Han, Q., & Xie, L. (2026) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2025.3645932 · Cited by 7
“EXTRA was interpreted as a DGD method augmented with a cumulative correction term that removes the steady-state bias caused by a fixed stepsize [6].”
Lee, C.-P., Wang, P.-W., & Lin, C. (2022) · Mathematical Programming Computation · doi:10.1007/s12532-022-00219-z · Cited by 3
Wang, Z., Zong, X., & Gai, L.-J. (2023) · Control Theory and Technology · doi:10.1007/s11768-023-00173-8 · Cited by 3
A Distributed Optimization Approach for Collaborative Object Lifting Using Multiple Aerial Robots
Liu, J., Sun, C., Feng, Z. G., et al. (2023) · Unmanned Systems · doi:10.1142/s2301385024410127 · Cited by 3
Decentralized State-Dependent Markov Chain Synthesis With an Application to Swarm Guidance
Uzun, S., Üre, N. K., & Acikmese, B. A. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3353673 · Cited by 6
“…of multiagent networked systems research, including distributed coordination of mobile autonomous agents [27], [28], [29], [30], [31], [51], distributed optimization [52], [53], [54], [55], [56], distributed state estimation [57], [58], or dynamic load-balancing for parallel processors [59], [60].”
Linearly Convergent Second-Order Distributed Optimization Algorithms
Qu, Z., Li, X., Li, L., & Hong, Y. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3360287 · Cited by 4
Multi-consensus decentralized primal-dual fixed point algorithm for distributed learning
Tang, K., Liu, W., & Mao, X. (2024) · Machine Learning · doi:10.1007/s10994-024-06537-8 · Cited by 4
Distributed Conjugate Gradient Method via Conjugate Direction Tracking
Shorinwa, O., & Schwager, M. (2024) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc60939.2024.10644588 · Cited by 9
Su, Y., Wang, Q., & Sun, C. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3470841 · Cited by 3
“In the existing literature, many cele-brated results have been addressed to solve a special case of (1), i.e., f = 0 [22], [23], [24], [25].”
On the Optimal Communication Weights in Distributed Optimization Algorithms
Colla, S., & Hendrickx, J. M. (2024) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2024.10.107 · Cited by 3
Distributed Stochastic Learning for Composite Sharing Optimization in Consumer Electronics
Lü, Q., Dai, X., Zhang, W., & Ezilarasan, M. R. (2024) · IEEE Transactions on Consumer Electronics · doi:10.1109/tce.2024.3506915 · Cited by 3
“Related known approaches can be found in the relevant works [15], [16], [17], [18], [19], [20], [21], [22], [23], [24].”
Decentralized Upper Confidence Bound Algorithms for Homogeneous Multi-agent Multi-armed Bandits
Zhu, J., Mulle, E., Smith, C. S., et al. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3525417 · Cited by 3
Open Distributed Convex Optimization
Wu, X., Lin, J., Jiang, S., et al. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3608057 · Cited by 3
“To attain faster convergence, Shi et al. [7] modified the previous algorithm via a fixed step-sizes, resulting in an extra convergence.”
Distributed economic dispatch for microgrids with vehicle-to-grid under time-varying network
Lu, C.-F., Liu, G. P., Yan, R., & Cui, J. (2025) · Journal of Energy Storage · doi:10.1016/j.est.2025.120007 · Cited by 5
Gossip‐based distributed hierarchical algorithm for multi‐cluster constrained optimisation
Li, D., Shi, C., & Yang, G. (2019) · IET Control Theory and Applications · doi:10.1049/iet-cta.2018.6224 · Cited by 4
Improving the Convergence of Distributed Gradient Descent via Inexact Average Consensus
Du, B., Zhou, J., & Sun, D. (2020) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-020-01648-3 · Cited by 4
A Heavy-Ball Distributed Optimization Algorithm over Digraphs with Row-Stochastic Matrices
Shen, Y., & Yang, S. (2020) · Chinese Control Conference (CCC) · doi:10.23919/ccc50068.2020.9188385 · Cited by 4
Differentially Private Discrete-Time Second-Order Consensus under Directed Topologies
Ma, M., Zhao, C., & He, J. (2020) · International Conference on Control and Automation · doi:10.1109/icca51439.2020.9264473 · Cited by 3
“Early works on consensus with first-order dynamics can be found in [1], [2].”
BackgroundGT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning
Zhang, X., Liu, J., Zhu, Z., & Bentley, E. S. (2021) · ACM International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing (MobiHoc) · doi:10.1145/3466772.3467056 · Cited by 7
Distributed Sparse Optimization With Minimax Concave Regularization
Komuro, K., Yukawa, M., & Cavalcante, R. L. G. (2021) · IEEE Statistical Signal Processing Workshop (SSP) · doi:10.1109/ssp49050.2021.9513764 · Cited by 3
Shethia, S., Gupta, A., Thapliyal, O., & Hwang, I. (2021) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/smc52423.2021.9658615 · Cited by 4
Colla, S., & Hendrickx, J. M. (2022) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc51059.2022.9993346 · Cited by 3
Moothedath, S., & Vaswani, N. (2022) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc51059.2022.9992928 · Cited by 3
Adaptive Fuzzy Approximate Optimal Consensus of Lagrangian Agents: An EXTRA-Based Smoothing Approach
Psillakis, H. E., & Oikonomidis, K. A. (2023) · IEEE Transactions on Fuzzy Systems · doi:10.1109/tfuzz.2023.3276394 · Cited by 3
Zhou, Y., Ai, W., Tang, G., & Chen, H. (2023) · Applied Intelligence · doi:10.1007/s10489-023-04765-4 · Cited by 3
An accelerated exact distributed first-order algorithm for optimization over directed networks
Wang, Z., Wang, C., Wang, J., Hu, J., & Li, H. (2023) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2023.08.015 · Cited by 3
Distributed mirror descent algorithm over unbalanced digraphs based on gradient weighting technique
Shi, C., & Yang, G. (2023) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2023.08.009 · Cited by 4
Distributed Optimization for the DER-Rich Electric Power Grid
Adan, J., & Srivastava, A. K. (2023) · Foundations and Trends® in Electric Energy Systems · doi:10.1561/3100000036 · Cited by 3
NPGA: A Unified Algorithmic Framework for Decentralized Constraint-Coupled Optimization
Li, J., & Su, H. (2024) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2024.3354882 · Cited by 5
“1) Given the aforementioned three properties, we can easily verify that − I W ≤ I [25].”
InfluentialDelay-Agnostic Asynchronous Distributed Optimization
Wu, X., Liu, C., Magnússon, S., & Johansson, M. (2023) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc49753.2023.10383647 · Cited by 14
Ran, L., Li, H., Hu, J., Lü, Q., Wang, Z., Li, Z., & Chen, G. (2024) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2023.3285865 · Cited by 4
Data-Driven Distributed Spectrum Estimation for Linear Time-Invariant Systems
Liu, S., Cortés, J., & Martínez, S. (2024) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2024.3432816 · Cited by 3
“Our approach relies on the body of work that designs distributed algorithms to solve linear algebraic equations (LAEs) [25], [26], [27], [28], [29] and distributed optimization problems [30], [31], [32].”
Decentralized Rank-Adaptive Matrix Factorization—Part I: Algorithm Development
Jiao, Y., Gu, Y., Chang, T., & Luo, Z.-Q. T. (2024) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2024.3465009 · Cited by 3
A distributed algorithm with dynamic event-triggered mechanism for resource allocation problems
Chen, B., Yang, J., Lu, W., et al. (2024) · Cluster Computing · doi:10.1007/s10586-024-04693-z · Cited by 3
Ji, C., Heusdens, R. R., Maag, S., & Li, Q. (2025) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp49660.2025.10888257 · Cited by 8
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.