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 1,201–1,300 of 1,315
Double Acceleration of Distributed Nesterov Gradient Descent Algorithms by Exploiting Momentum
Yi, X., Yi, J., & Chai, L. (2024) · 2022 IEEE 20th International Conference on Industrial Informatics (INDIN) · doi:10.1109/indin58382.2024.10774328
A Survey of Distributed Optimization
Yu, W., Zhu, Y., & Liu, H. (2024) · Elsevier eBooks · doi:10.1016/b978-0-443-14081-5.00077-5
A penalty-based method for communication-efficient decentralized bilevel programming
Nazari, P., Mousavi, A., Tarzanagh, D. A., & Michailidis, G. C. (2024) · Automatica · doi:10.1016/j.automatica.2024.112039 · Cited by 6
Wang, A., Li, Q., & Zhang, W. (2024) · Communications in computer and information science · doi:10.1007/978-981-96-0154-7_7
Stabilization and Performance Improvement of Control Systems under State Feedback
Yao, L. (2022) · University of North Texas Digital Library (University of North Texas) · doi:10.12794/metadc1944321
Parameter learning: a convex analytic path
Theodoridis, S. (2025) · Machine Learning · doi:10.1016/b978-0-44-329238-5.00014-7
An Extended Distributed Inexact Method with Multi-Update and Single-Combination Strategy
郝, 晓. (2025) · Advances in Applied Mathematics · doi:10.12677/aam.2025.141040
Distributed Stochastic Averaging Gradient Algorithm over Directed Graph
Zhao, J., & Gao, W. (2024) · China Automation Congress (CAC) · doi:10.1109/cac63892.2024.10865751
Distributed Constrained Optimization with Uncoordinated Step Sizes: A Case Study on Ethylene Plant
Liu, B., Li, Z., & Du, W. (2024) · China Automation Congress (CAC) · doi:10.1109/cac63892.2024.10865107
Accelerated online averaging over networks
Liu, W., Liu, X., Mao, X., & Wu, Z. (2025) · Scientia Sinica Mathematica · doi:10.1360/ssm-2024-0223
Distributed Consensus, Optimization and Computation in Networked Systems
Yao, L. (2018) · University of North Texas Digital Library (University of North Texas) · doi:10.12794/metadc1404555
Distributed Estimation for ℓ0-Constrained Quantile Regression Using Iterative Hard Thresholding
Zhao, Z., & Lian, H. (2025) · Mathematics · doi:10.3390/math13040669 · Cited by 1
On Linear Convergence of PI Consensus Algorithm under the Restricted Secant Inequality
Chakrabarti, K., & Baranwal, M. (2024) · Indian Control Conference · doi:10.1109/icc64753.2024.10883750 · Cited by 1
Achieving Local Consensus Over Compact Submanifolds
Hu, J., Zhang, J., & Deng, K. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3545711 · Cited by 8
“It should be noted that Assumption 2.1 implies that the second largest singular value σ 2 of W lies in the interval [0 , 1) [1].”
InfluentialEstimation Network Design framework for efficient distributed optimization
Bianchi, M., & Grammatico, S. (2024) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc56724.2024.10885996
A Zeroth-Order Proximal Algorithm for Consensus Optimization
Wang, C., Ou, Z., & Lu, J. (2024) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc56724.2024.10886308 · Cited by 1
Accelerating Gradient Tracking with Periodic Global Averaging
Feng, S., & Jiang, X. (2024) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc56724.2024.10886594
“Many decentralized methods have been proposed to solve the problem (1), including decentralized/distributed gradient descent (DGD) methods [6]–[8], EXTRA [9], Exact-Diffusion/D 2 /NIDS (ED) [10]–[13], and Gradient Tracking (GT) methods [14]–[17].”
Communication-efficient Exact Diffusion for Decentralized Learning
Fagundes, G. F., Vlaski, S., & Nassif, R. (2025) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp49660.2025.10888313
“Several approaches have been studied for bias-correction in the context of consensus [21]–[23], and more recently, multitask [24] optimization, by leveraging arguments based on Lagrangian duality.”
Deep-Relative-Trust-Based Diffusion for Decentralized Deep Learning
Li, M., Fainman, A., & Vlaski, S. (2025) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp49660.2025.10889869
Distributed algorithm design for multi-agent cooperative optimization over directed graph
Wang, J., & Li, T. (2025) · Engineering Optimization · doi:10.1080/0305215x.2025.2450691
Proximally Regularized Multitask Learning over Networks
Vlaski, S., & Nassif, R. (2024) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/ieeeconf60004.2024.10943086
Accelerated Nesterov Design for Distributed Optimization Over Directed Graphs
Zhang, Z., Yin, X., Fan, Y. C., & Cheng, S. (2025) · International Journal of Control Automation and Systems · doi:10.1007/s12555-024-0424-0 · Cited by 1
Xu, Q., & Luo, S. (2023) · International Conference on Networking Systems of AI (INSAI) · doi:10.1109/insai60116.2023.00045
Distributed Nonsmooth Constrained Optimization Algorithm under Weight-unbalanced Directed Graph
Feng, L., Guo, Z., Zeng, L., & Gao, R. (2025) · International Symposium on Autonomous Systems (ISAS) · doi:10.1109/icaisisas64483.2025.11051448
Distributed Nesterov-like accelerated non-convex composite optimization algorithm
Li, T., Zhang, K., Xu, L., Gao, C., Li, F., & Yang, T. (2025) · Scientia Sinica Informationis · doi:10.1360/ssi-2025-0112
Analysis of DGD for decentralized high-dimensional statistical models: beyond the least squares
Gao, J., & Lian, H. (2025) · Analysis and Applications · doi:10.1142/s0219530525500459
Variance-reduced decentralized projection algorithms for constrained optimization in networks
Lü, Q., Liao, X., Li, H., Deng, S., Li, Y., & Zhang, K. (2025) · Elsevier eBooks · doi:10.1016/b978-0-44-333337-8.00009-3
A decentralised strongly adaptive subgradient online learning algorithm over time-varying networks
Wang, G., Zhang, M., Wang, L., Zhao, X., & Zhang, Q. (2025) · International Journal of Systems Science · doi:10.1080/00207721.2025.2530672
Variance-Reduced Gradient Estimator for Nonconvex Zeroth-Order Distributed Optimization
Mu, H., Tang, Y., & Li, Z. (2025) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc63710.2025.11107900 · Cited by 1
“…with a decreasing step-size achieved a convergence rate of O ( log t √ t ) [4], while [5] and subsequent works proposed gradient tracking (GT) mechanisms with a fixed step-size, achieving a sublinear convergence rate of O ( 1 t ) , which is comparable to centralized gradient descent method.”
Warm-Up Gradient Tracking for Distributed Nonconvex Optimization with Data Heterogeneity
Zhang, Z., Huang, Y., & Xu, J. (2025) · International Conference on Control and Automation · doi:10.1109/icca65672.2025.11129713
Zhu, J., Wu, W., & Wang, Q. (2025) · Conference on Fully Actuated System Theory and Applications (FASTA) · doi:10.1109/fasta65681.2025.11138185
Distributed Newton Optimization with ADMM-Based Consensus
Carnevale, G., Bastianello, N., Notarstefano, G., et al. (2025) · Lecture notes in control and information sciences - proceedings · doi:10.1007/978-3-031-83191-1_20
Distributed Optimization Algorithm Over Directed Networks with Finite-Time Convergence
Zhang, P., Xie, J. H., Gao, W., et al. (2025) · Chinese Control Conference (CCC) · doi:10.23919/ccc64809.2025.11179427
“…optimization algorithms based on fixed step size to ensure the convergence of the problem, for example, the EXTRA algorithm proposed in the literature [8], which is suitable for the case of local objective function is smooth and strongly convex, and can achieve Q-linear convergence speed.”
Chen, S., & Ma, J. (2025) · Chinese Control Conference (CCC) · doi:10.23919/ccc64809.2025.11179429
“Based on the gradient-based method, [9] developed an exact first-order al-gorithm (EXTRA).”
A Unified Framework for Robust Distributed Optimization Under Bounded Disturbances
Liu, C., Huang, R., Chen, W.-H., Du, W., & Shi, Y. (2025) · Chinese Control Conference (CCC) · doi:10.23919/ccc64809.2025.11178647
“…First, we compare one instance of our RDO framework, i.e., Robust AugDGM (RAugDGM) in (16), with four widely known non-robust algorithms: EX-TRA [23], NIDS [7], DIGing [10], and AugDGM [21], to illustrate the performance gap between robust and non-robust designs under bounded communication…”
A distributed proximal splitting method with linesearch for locally Lipschitz gradients
Atenas, F., Dao, M. N., & Tam, M. K. (2025) · Journal of Global Optimization · doi:10.1007/s10898-025-01544-y
Asynchronous Distributed Composite Optimization via Publish-Subscribe Paradigm
Huang, R., Liu, C., Nanavati, R. V., Liu, C., & Chen, W.-H. (2025) · International Conference on Automation and Computing (ICAC) · doi:10.1109/icac65379.2025.11196425
Deng, S., Lu, H., Lü, Q., et al. (2025) · Digital Signal Processing · doi:10.1016/j.dsp.2025.105734
Distributed Algorithm for Constrained Optimization with Asynchrony and Delays
Li, H., Lü, Q., Xia, D., Wang, X., Wang, Z., Zheng, L., Li, J. Q., & Ran, L. (2025) · Computational intelligence methods and applications · doi:10.1007/978-981-95-0911-9_7
Distributed Proximal Splitting Algorithm for Composite Constrained Convex Optimization
Li, H., Lü, Q., Xia, D., Wang, X., Wang, Z., Zheng, L., Li, J. Q., & Ran, L. (2025) · Computational intelligence methods and applications · doi:10.1007/978-981-95-0911-9_10
Distributed Dual Proximal Gradient Algorithms for Nonsmooth Constrained Composite Optimization
Li, H., Lü, Q., Xia, D., Wang, X., Wang, Z., Zheng, L., Li, J. Q., & Ran, L. (2025) · Computational intelligence methods and applications · doi:10.1007/978-981-95-0911-9_9
Distributed Primal-Dual Forward-Backward Splitting Algorithm for Nonsmooth Composite Optimization
Li, H., Lü, Q., Xia, D., Wang, X., Wang, Z., Zheng, L., Li, J. Q., & Ran, L. (2025) · Computational intelligence methods and applications · doi:10.1007/978-981-95-0911-9_6
Distributed Dual Operator Splitting Algorithm for Nonsmooth Composite Optimization
Li, H., Lü, Q., Xia, D., Wang, X., Wang, Z., Zheng, L., Li, J. Q., & Ran, L. (2025) · Computational intelligence methods and applications · doi:10.1007/978-981-95-0911-9_5 · Cited by 1
Distributed Primal-Dual Fixed Point Algorithm for Multi-Block Separable Optimization
Li, H., Lü, Q., Xia, D., Wang, X., Wang, Z., Zheng, L., Li, J. Q., & Ran, L. (2025) · Computational intelligence methods and applications · doi:10.1007/978-981-95-0911-9_3
A Convergence-Motivated Learning-to-Optimize Framework for Decentralized Optimization
He, Y., Shang, Q., Huang, X., Liu, J., & Yuan, K. (2025) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2025.3644008 · Cited by 4
“…more challenging in decentralized optimization, where researchers are usually constrained to test their algorithms on simple target problems [7], [8], [9], [11], [12] within dozens of nodes [5], [11], [12], [35], [36], and decentralized L2O shall maintain much more memory during the training…”
Distributed Aggregative Optimization of High-Order Heterogeneous Integrator Systems
Xie, R., Xian, C., & Zhao, Y. (2025) · Youth Academic Annual Conference of Chinese Association of Automation (YAC) · doi:10.1109/yac66630.2025.11149839
Emirov, N., Song, G., & Sun, Q. (2025) · Expositiones Mathematicae · doi:10.1016/j.exmath.2025.125740
Achieving violation-free distributed optimization under coupling constraints
Liu, C., Tan, X., Wu, X., et al. (2025) · Automatica · doi:10.1016/j.automatica.2025.112774
A Unified Dual-Consensus Approach to Distributed Optimization With Globally Coupled Constraints
Liu, Z., Wu, X., Wang, D., & Lu, J. (2025) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2025.3649114
“This parameter setting corresponds to PGC [30], P-EXTRA [9], and DPGA [28], with specific choices of W and P D .”
InfluentialA Tutorial on Distributed Multi-Armed Bandits
Ji, L. (2025) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc57313.2025.11312351
Automated algorithm design for convex optimization problems with linear equality constraints
Ozaslan, I. K., Wu, W., Chen, J., et al. (2025) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc57313.2025.11312607
A novel distributed gradient algorithm for composite constrained optimization over directed network
Ou, M., Zhang, H., Yan, Z., Yang, Z., & Ran, H. (2026) · Scientific Reports · doi:10.1038/s41598-026-36058-4 · Cited by 1
Tang, R., Li, H., Xia, D., Ran, L., Li, J., & Zhu, W. (2026) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2026.102282
Garmpis, S., & Bechlioulis, C. P. (2025) · International Conference on Systems and Control (ICSC) · doi:10.1109/icsc67755.2025.11335077
“Fixed step-size algorithms such as EXTRA [4] and DIGing [5] achieve faster convergence by integrating gradient tracking mechanisms, which enable agents to estimate the global gradient through local consensus dynamics.”
Imagining a Democratic, Affordable Future of Foundation Models: A Decentralised Avenue
He, F., Nan, L., & Zhu, T. (2025) · Springer handbooks of computational statistics · doi:10.1007/978-3-031-95418-4_16 · Cited by 1
Distributed Optimization of Multi-Agent Systems via Intermittent Gradient Information
Zhang, J., Tan, X., & Wu, Y. (2025) · Asia-Pacific Conference on Intelligent Robot Systems (ACIRS) · doi:10.1109/acirs66343.2025.11360953
Distributed Optimal Control for Grid-Forming and Grid-Feeding Converters in DC Microgrid
Zhang, J., Mohiuddin, S. M., & Qi, J. (2026) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2026.3660614 · Cited by 2
“The optimal consensus problem is introduced in [28] and [29], where multiple agents cooperatively minimize the sum of their local objective functions while enforcing consensus among their decision variables to achieve a unified global decision.”
Decentralized Primal--Dual Optimization Without Global Lipschitz Continuity
Wang, L., Yang, S., & Zhang, M.-L. (2026) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2026.3656728
“When g i = 0 and f i is strongly convex, algorithms such as D-ADMM [12], DLM [13], EXTRA [14], DIGing [15], GT [16], and Exact Di ff usion [17] have been proposed, all of which are proved to exhibit linear convergence rates.”
An improved convergence guarantee for the gradient-push algorithm with a constant stepsize
Choi, H., Choi, W., & Kim, G. (2026) · Computational Optimization and Applications · doi:10.1007/s10589-025-00763-z · Cited by 1
On the Convergence of Decentralized Stochastic Gradient-Tracking With Finite-Time Consensus
Fainman, A., & Vlaski, S. (2026) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2026.3667215 · Cited by 1
“Decentralized strategies to solve problem (1) (see, for example, [2], [3], [4], [5], [6], [7], [8], [9], [10], [11]) rely only on exchanges of information between pairs of neighbors and avoid any centralized processing.”
Primal-Dual Strategy for Composite Optimization Over Directed Graphs
Zandi, S., Esfandiari, M., & Zhao, S. (2026) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2026.3667777
“Shi et al. [22] achieve geometric convergence with the help of symmetric weights.”
Fan, P. Z., Wu, M., Liao, H., Jin, J., & Xiong, N. N. (2026) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2026.3665573 · Cited by 2
“Another well-known method ensuring exact convergence is EXTRA [22], which leverages di ff erences between gradients at consecutive iterations.”
A first-order algorithm for decentralised min-max problems
Malitsky, Y., & Tam, M. K. (2026) · Numerische Mathematik · doi:10.1007/s00211-026-01530-w · Cited by 11
“Consider the (primal) monotone inclusion where A : H ⇒ H and C : H ′ ⇒ H ′ are maximally monotone, B : H → H is monotone and L - Lipschitz continuous, and K : H → H ′ is a linear operator with adjoint K ∗ .”
Chakrabarti, K., Mai, V. S., & Maity, D. (2026) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.70448
ϵ -Differentially Private Distributed Non-Convex Optimization
Gao, Y., li, R., & Yang, G. (2026) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2026.3671820
“Under Assumption 2, we can derive that By setting , it is evident that g i , k represents the stochastic gradient as defined in [44], [45], [46], [47], [48], [49], and [50].”
InfluentialVariance-Reduced Decentralized Stochastic Optimization Algorithms With Communication Skip
Xu, W., li, R., & Yang, G. (2026) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2026.3669596
“In [28], an algorithm named DSA was proposed that combines EXTRA [44] with SAGA.”
Differentially Private Accelerated Distributed Algorithm for Aggregative Optimization
Liu, B., Li, D., & Chai, L. (2026) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2026.3674758 · Cited by 2
“Numerous distributed optimization algorithms have been proposed and have demonstrated excellent results, such as gradient-based methods [4], [5], distributed alternating direction method of multipliers (ADMM) [6], [7], and decentralized exact first-order algorithms [8].”
Zhao, H. V., Yue, P., & Fang, C. (2026) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2026.3677732 · Cited by 3
“Further, EXTRA [66] first achieved a linear convergence rate for smooth and strongly convex cost functions with an extra correction term.”
Park, S., Vlaski, S., & Hanzo, L. (2025) · 2018 52nd Asilomar Conference on Signals, Systems, and Computers · doi:10.1109/ieeeconf67917.2025.11443796
Guo, L., Shi, X., Xu, W., & Cao, J. (2026) · Automatica · doi:10.1016/j.automatica.2026.112965 · Cited by 3
Optimization methods over networks for popular content delivery and distributed machine learning
Costantini, M. (2023) · theses.fr (ABES) · doi:10.70675/1f27d904z6f26z4a9ez8b79z78214cb50b08
Beyond gradients : zero-order approaches to optimization and learning in multi-agent environments
Mhanna, E. (2024) · theses.fr (ABES) · doi:10.70675/7eb7acfcz07cbz4f12z9e08z1b5ebe87ca4c
Decentralized Accelerated Nonconvex Minimax Optimization via Exact Diffusion
Cai, H., Alghunaim, S. A., & Sayed, A. H. (2026) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp55912.2026.11462899
Decentralized Learning with Dynamically Refined Edge Weights: A Data-Dependent Framework
Du, R., & Wai, H.-T. (2026) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp55912.2026.11463182
Luo, B., Lü, Q., Cheng, H., et al. (2026) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2026.3683196
“These methods [10], [11], [12] can achieve linear or asymptotic convergence to the exact solution.”
InfluentialDiffusion-LSVRG-UP: Distributed LSVRG-based diffusion algorithm with uncoordinated probabilities
Zhao, J., & Gao, W. (2026) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2026.108658
Improved Analysis of Push-DIGing for Distributed Convex Optimization over Digraphs
Mo, M., Wang, J., Liu, B., 盛子晗, & Yuan, K. (2026) · International Symposium on Big Data and Applied Statistics (ISBDAS) · doi:10.1109/isbdas69350.2026.11484962
A necessary and sufficient condition for discrete-time consensus on star boundaries
Sidorenko, G., & Thunberg, J. (2026) · Automatica · doi:10.1016/j.automatica.2026.113027
Event-Triggered Quantized Distributed Optimization With Feedback Delay
Yang, H., Wei, Z., Mao, S., et al. (2026) · Lecture notes in electrical engineering · doi:10.1007/978-981-95-8329-4_9
Distributed Continuous-Time Optimization via Unbiased Extremum Seeking
Yang, X., Li, X., Zhang, K., et al. (2026) · Lecture notes in electrical engineering · doi:10.1007/978-981-95-8329-4_29
A Fast Differentially Private Distributed Algorithm Over Unbalanced Directed Networks
Ran, M., Wang, Z. X., Lei, Y., & Li, H. (2026) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2026.3691978
“In addition, EXTRA [25] makes use of a fixed large step size, which offers an accelerated convergence rate O ( 1 k ) .”
Decentralized Inexact Cubic Newton Method With Consensus Procedure
Agafonov, A., Novitskii, A., Rogozin, A., et al. (2026) · IEEE Access · doi:10.1109/access.2026.3695635
Decentralized EM algorithm for Gaussian mixtures under data heterogeneity and partial labeling
Li, X., Wu, S., Du, B., & Wang, H. (2026) · Biometrics · doi:10.1093/biomtc/ujag092
Li, Z., Ran, L., Li, J., & Zheng, L. (2026) · Mathematical and Computational Applications · doi:10.3390/mca31030091
“Objective Functions Algorithm Iteration Step-Sizes [8,11] min [14,16,18] min ∑ mi = 1 f i ( x ) (Smooth only) Decentralized Synchronous Coordinated [25,27] min Here, f i denotes smooth function, while g i , h i and g denote potentially nonsmooth functions.”
Gradient tracking with distributed unified adaptive momentum for stochastic non-convex optimization
Cao, Z., He, S., Yan, D., Zhou, Y., Wang, X., & Li, C. (2026) · Communications in Nonlinear Science and Numerical Simulation · doi:10.1016/j.cnsns.2026.110279
Zhao, W., Liu, R., Shao, J., et al. (2026) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2026.108820
Privacy-preserving gradient tracking via state decomposition for directed multi-agent optimization
Li, Y., Wu, C., Zhang, K., Lü, Q., Deng, S., & Li, H. (2026) · Communications in Nonlinear Science and Numerical Simulation · doi:10.1016/j.cnsns.2026.110441 · Cited by 1
Predefined-time Distributed Convex Optimization Algorithms with Equality Constraints
Zheng, L., Guo, L., & He, J. (2026) · doi:10.1109/icaisisas68969.2026.11567682
“Shi et al. constructed a decentralized consensus-oriented optimization framework and developed a primal first-order iterative scheme that converges to the exact minimizer [3].”
Clipped Stochastic Gradient Tracking For Locally Smooth Functions
Mei, L., & Zhang, J. (2026) · Journal of Scientific Computing · doi:10.1007/s10915-026-03357-x
“…Efficient classic algorithms for this problem include the distributed gradient descent (DGD) [28, 26, 48, 49], gradient tracking (GT) [27, 33, 16], Push-Pull [28, 19, 36, 34], the primal-dual (PD) methods [31, 50], as well as their numerous variants [36, 10, 40, 23, 37, 46, 33, 39], to name a few.”
Garmpis, S., & Bechlioulis, C. P. (2026) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2026.3710316
“Among these, fixed step-size gradient-based approaches have emerged due to their simplicity and effectiveness [2].”
Poisson subsampling for large-scale functional data analysis
Yan, X., & He, S. (2026) · Computational Statistics · doi:10.1007/s00180-026-01776-w
Chaotic-AES Integration for Privacy-Preserving Distributed Personalized Optimization
Tang, Q., Zhou, X., Yuan, Y., Lü, Q., & Li, H. (2026) · IEEE Signal Processing Letters · doi:10.1109/lsp.2026.3711542
“…optimization, including subgradient and gradient descent methods [10], [11], [12], [13], as well as more advanced schemes such as EXTRA [14], [15], [16], DIGing [17], [18], [19], push–pull methods [20], [21], [22],…”
Retraction-Free Optimization Over the Stiefel Manifold for the LoRA Fine-Tuning
Zhang, Y., Hu, J. N., Lai, Z., Lin, L., & Wen, Z. (2026) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2026.3711595 · Cited by 3
“…remark that our penalty-parameter-free algorithm design and analysis are motivated by insights from multi-agent decentralized optimization [14], [15], [16], [17], [18]: the stepsize for the consensus (constraint violation) term—which directly measures and penalizes the discrepancy across…”
Proportional-Integral-Based Distributed Nesterov Gradient Methods for Distributed Optimization
Yang, Z., Li, K., Pourkabirian, A., et al. (2026) · International Conference on Communications · doi:10.1109/icc59461.2026.11588109
Distributed Affine Body Dynamics with Adaptive Consensus
Liu, J., Zhou, W., Pei, X., et al. (2026) · ACM SIGGRAPH Conference Papers (SIGGRAPH) · doi:10.1145/3799902.3811106
A Distributed Aggregative Optimization Algorithm for Unbalanced Directed Graphs
Chen, Y., & Yang, Q. (2026) · Journal of Scientific Computing · doi:10.1007/s10915-026-03401-w
“A key advancement, DEXTRA [17], achieves linear convergence by merging the push-sum protocol [18] with the EXTRA framework [14], though it confines step sizes to a specific, non-trivial interval.”
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.