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 901–1,000 of 1,315
Fast Distributed Resource Allocation of Smart Grid: A Zeroth-Order Optimization Algorithm
Luan, M., Wen, G., & Zheng, W. X. (2023) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc49753.2023.10383947 · Cited by 2
Wang, L., & Liu, X. (2023) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc49753.2023.10383237 · Cited by 2
Exact Subspace Diffusion for Decentralized Multitask Learning
Wadehra, S., Nassif, R., & Vlaski, S. (2023) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc49753.2023.10384238 · Cited by 3
Parallel multi-splitting proximal method for star networks
Wei, E. (2017) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2017.7963623 · Cited by 1
Romao, L. B. R. R., Margellos, K., Notarstefano, G., & Papachristodoulou, A. (2019) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc40024.2019.9029252 · Cited by 2
Distributed empirical risk minimization over directed graphs
Xin, R., Sahu, A. K., Kar, S., & Khan, U. A. (2019) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/ieeeconf44664.2019.9049065 · Cited by 3
Distributed multi‐agent optimisation via coordination with second‐order nearest neighbours
Ren, X., Li, D., Xi, Y., et al. (2020) · IET Control Theory and Applications · doi:10.1049/iet-cta.2019.0708 · Cited by 2
A Distributed Adaptive Moment Estimation Method With Dynamic Bound For Online Optimization
Shen, X., Fang, R., Li, D., & Wu, X. (2020) · International Conference on Control and Automation · doi:10.1109/icca51439.2020.9264510 · Cited by 2
“For example, [14]– [16] use corrected update rules and momentum techniques to accelerate convergence.”
MethodZhang, J., Ling, Q. H., & So, A. M. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9303887 · Cited by 2
“We compare Newton tracking with the first-order algorithms, including gradient tracking [21], EXTRA [15] and DLM [17].”
MethodSelf-citationAn Acceleration of Decentralized SGD Under General Assumptions with Low Stochastic Noise
Trimbach, E., & Rogozin, A. (2021) · Communications in computer and information science · doi:10.1007/978-3-030-86433-0_8 · Cited by 3
On the Convergence of NEAR-DGD for Nonconvex Optimization with Second Order Guarantees
Iakovidou, C., & Wei, E. (2021) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc45484.2021.9683777 · Cited by 2
Linear Convergence of Distributed Mirror Descent with Integral Feedback for Strongly Convex Problems
Sun, Y., & Shahrampour, S. (2021) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc45484.2021.9682809 · Cited by 2
Zhan, W., Wu, G., & Gao, H. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i8.20884 · Cited by 4
Self-citationPrimal-Dual Algorithm for Distributed Constrained OptimizationPreprint
Lei, J., Chen, H.-F., & Fang, H. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1510.08580 · Cited by 2
A Bregman Splitting Algorithm for Distributed Optimization over NetworksPreprint
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1608.08031 · Cited by 2
Accelerated Consensus via Min-Sum SplittingPreprint
Rebeschini, P., & Tatikonda, S. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.03807 · Cited by 5
“…combined with some form of local optimization over a peer-to-peer network, as in the case of iterative subgradient methods Nedic and Ozdaglar (2009); Sundhar Ram et al. (2010); Johansson et al. (2010); Duchi et al. (2012); Chen and Sayed (2012); Jakoveti´c et al. (2014); Shi et al. (2015).”
MethodDistributed Convex Optimization With Coupling Constraints Over Time-Varying Directed GraphsPreprint
Gu, C., Wu, Z., Li, J., & Guo, Y. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.07916 · Cited by 4
Global Optimality in Distributed Low-rank Matrix FactorizationPreprint
Zhu, Z., Li, Q., Yang, X., Tang, G., & Wakin, M. B. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.03129 · Cited by 4
Han, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.00257 · Cited by 2
Online Federated Learning over decentralized networks
Zhang, C. (2018) · doi:10.32657/10220/47928 · Cited by 3
A Unification and Generalization of Exact Distributed First Order MethodsPreprint
Jakovetić, D. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1709.01317 · Cited by 2
Compressed Distributed Gradient Descent: Communication-Efficient Consensus over NetworksPreprint
Zhang, X., Liu, J., Zhu, Z., et al. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1812.04048 · Cited by 2
Contraction Analysis on Primal-Dual Gradient OptimizationPreprint
Su, Y., Shi, Y., & Sun, C. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.10171 · Cited by 3
Resource-aware Exact Decentralized Optimization Using Event-triggered BroadcastingPreprint
Liu, C., Li, H., & Shi, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.10179 · Cited by 2
Distributed Resource Allocation over Time-varying Balanced Digraphs with Discrete-time CommunicationPreprint
Su, L., Li, M., Gupta, V., et al. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.13003 · Cited by 2
Distributed Least Squares Solver for Network Linear EquationsPreprint
Yang, T., George, J., Qin, J., et al. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.00156 · Cited by 2
Optimally Compressed Nonparametric Online LearningPreprint
Koppel, A., Bedi, A. S., Rajawat, K., et al. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.11555 · Cited by 2
A Unified Contraction Analysis of a Class of Distributed Algorithms for Composite OptimizationPreprint
Xu, J., Sun, Y., Tian, Y., et al. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.09817 · Cited by 2
FlexPD: A Flexible Framework Of First-Order Primal-Dual Algorithms for Distributed OptimizationPreprint
Mansoori, F., & Wei, E. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.07526 · Cited by 2
Gradient-Consensus: Linearly Convergent Distributed Optimization Algorithm over Directed GraphsPreprint
Khatana, V., Saraswat, G., Patel, S., & Salapaka, M. V. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.10070 · Cited by 7
A general framework for decentralized optimization with first-order methodsPreprint
Xin, R., Pu, S., Nedić, A., et al. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.05837 · Cited by 2
Li, X., & Zhang, Z. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.01505 · Cited by 2
Decentralized Riemannian Gradient Descent on the Stiefel ManifoldPreprint
Chen, S., García, A., Hong, M., & Shahrampour, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.07091 · Cited by 13
GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex LearningPreprint
Zhang, X., Liu, J., Zhu, Z., & Bentley, E. S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2105.01231 · Cited by 3
Decentralized Optimization with Heterogeneous Delays: a Continuous-Time Approach.Preprint
Even, M., Hendrikx, H., & Massoulié, L. (2021) · arXiv (Cornell University) · Cited by 2
Towards Understanding Practical Randomness Beyond Noise: Differential Privacy and Mixup.Preprint
Xiao, H., & Devadas, S. (2021) · IACR Cryptology ePrint Archive · Cited by 3
Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed GraphsPreprint
Song, Z., Shi, L., Pu, S., & Yan, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.12065 · Cited by 1
Li, R. (2020) · Chinese Control Conference (CCC) · doi:10.23919/ccc50068.2020.9188585 · Cited by 1
Xiong, Y., You, K., & Wu, L. (2020) · International Conference on Control and Automation · doi:10.1109/icca51439.2020.9264323 · Cited by 3
“The EXTRA algorithm in [14] can achieve a linear convergence rate for strongly convex functions by using the difference of two consecutive gradient descent iterates.”
MethodDecentralized Machine Learning over the Internet
Zhu, D., & Peng, J. (2022) · Chinese Control Conference (CCC) · doi:10.23919/ccc55666.2022.9901831 · Cited by 1
“Then, node i updates x k +1 i as where γ > 0 is the step size and W = [ W ij ] ∈ R n × n is the locally constructed Metropolis constant edge weight matrix [32, 33].”
BackgroundFixed-Time Optimization of Perturbed Multi-Agent Systems under the Resource Constraints
Wang, B., Wang, F., Chen, Y., et al. (2023) · Applied Sciences · doi:10.3390/app13074527 · Cited by 1
Distributed Optimization with Noisy Information Sharing
Wang, Y. (2023) · Chinese Control Conference (CCC) · doi:10.23919/ccc58697.2023.10240327 · Cited by 1
Yuan, H., Alghunaim, S. A., & Yuan, K. (2023) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc49753.2023.10384058 · Cited by 1
Fully Stochastic Distributed Convex Optimization on Time-Varying Graph with Compression
Yau, C.-Y., & Wai, H.-T. (2023) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc49753.2023.10383992 · Cited by 1
A Smoothed Bregman Proximal Gradient Algorithm for Decentralized Nonconvex Optimization
Pu, W., Zhang, J., Zhou, R., Fu, X., & Hong, M. (2024) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp48485.2024.10448285 · Cited by 2
Decentralized Sum-of-Nonconvex Optimization
Liu, Z., & Low, B. K. H. (2024) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v38i13.29318 · Cited by 1
Distributed optimization via dynamic event-triggered scheme with metric subregularity condition
Yu, X., Chen, X., Fan, Y. C., et al. (2024) · Autonomous Intelligent Systems · doi:10.1007/s43684-024-00063-z · Cited by 1
“…the projection from a point z to the optimal solution set Z ∗ = X ∗ × Y ∗ , then Based on the optimization problem in (1) and the primal-dual event-triggered algorithm in (5), we take the following assumption, which is more general than the strongly convex and restrict strongly convex in [18, 38].”
Chen, B., Yang, J., Lu, W., et al. (2024) · International Journal of Network Management · doi:10.1002/nem.2276 · Cited by 1
A stochastic primal–dual algorithm for composite constrained optimization
Su, E., Hu, Z., Xie, W. C., Li, L., & Zhang, W. (2024) · Neurocomputing · doi:10.1016/j.neucom.2024.128285 · Cited by 2
Decentralized Conjugate Gradient Tracking for Sum-of-Nonconvex Optimization
Zhang, Z., & Ni, Y.-H. (2024) · Chinese Control Conference (CCC) · doi:10.23919/ccc63176.2024.10661557 · Cited by 1
Resilient Distributed Optimization Algorithm Based on Trusted Nodes against Malicious Attacks
Cao, L., & Gao, W. (2024) · Chinese Control Conference (CCC) · doi:10.23919/ccc63176.2024.10662289 · Cited by 1
A Distributed Accelerated Algorithm Based on a Unified Momentum Method
Chen, Y., & Yang, Q. (2024) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-024-02552-w · Cited by 1
“The subsequent work on distributed optimization over undirected graphs includes [7, 9, 17, 20], where the convergence is sublinear, and [16, 19, 29] with linear convergence.”
Decentralized Learning of Quantile Regression: A Smoothing Approach
Shi, J., Wang, Y., Zhu, Z., & Lian, H. (2024) · Journal of Computational and Graphical Statistics · doi:10.1080/10618600.2024.2431060 · Cited by 4
A Flexible Framework for Decentralized Composite Optimization with Compressed Communication
Chang, Z., Zhang, Z., Yang, S., & Cao, J. (2024) · Fractal and Fractional · doi:10.3390/fractalfract8120721 · Cited by 1
Distributed constrained optimization over unbalanced graphs and delayed gradient
Huang, Q., Fan, Y. C., & Cheng, S. (2024) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2024.107466 · Cited by 1
A Linearly Convergent Quantized Stochastic Gradient Tracking Method With Variance Reduction
Zhu, L., Shi, X., Gui, J., Cao, J., & Abdel‐Aty, M. (2025) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2025.3540175 · Cited by 3
“Different from the DGD algorithm, which only utilizes the gradient from the last iteration, EX-TRA [6] can achieve a linear convergence to the exact solution by using gradients from the previous two iterations under a fixed stepsize.”
Decentralized Nonstationary Fuzzy Neural Network with Meta-Learning-Net
Zhang, Z., Yu, M., & Jia, H. (2025) · Mathematics · doi:10.3390/math13040552 · Cited by 1
Fast Networked Data Selection via Distributed Smoothed Quantile Estimation
Zhang, X., & Vasconcelos, M. M. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3541117 · Cited by 1
“This approach is complemented by integrating it with one of the advanced distributed smooth optimization methods, namely, the EXTRA algorithm [17], [18].”
Decentralized Federated Learning with Auto-switchable Local Optimizers
Li, T., Chang, Z., Pan, Z., Yang, S., Xu, W., & Chen, Y. (2025) · International Conference on Intelligent Control and Information Processing · doi:10.1109/icicip64458.2025.10898094 · Cited by 1
Li, C., & Wang, Q. (2025) · Neurocomputing · doi:10.1016/j.neucom.2025.130000 · Cited by 1
Gradient Tracking for Sum‐of‐Nonconvex Decentralized Optimization
Zhang, Z., & Ni, Y. (2025) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.7978 · Cited by 1
Zhang, S., Pananjady, A., & Romberg, J. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3562997 · Cited by 6
“Pu and Nedi´c [53] combined DSG with gradient tracking, but the method converges only to a neighborhood of the optimal solution, and at a suboptimal rate.”
Asynchronous distributed algorithm for constrained optimization and its application
Wang, T., Li, Z., Nie, R., & Du, W. (2025) · Science China Technological Sciences · doi:10.1007/s11431-024-2852-1 · Cited by 3
Decentralized Optimization on Compact Submanifolds by Quantized Riemannian Gradient Tracking
Chen, J., Liu, L., Zhu, T., Liu, Y., Dai, G., Jiang, Y., & Tsang, I. W.-H. (2025) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2025.3568045 · Cited by 7
“[29] introduced a novel quantized distributed gradient decent algorithm (QDGD) for strongly convex and smooth objectives, in which each node transmits a quantized local decision variable to neighboring nodes under the assumption of unbiasedness.”
Kuruzov, I. A., Alkousa, M. S., Stonyakin, F. S., et al. (2025) · Optimization methods & software · doi:10.1080/10556788.2025.2475404 · Cited by 1
“In [33], for the least squares problem, it was compared the performance of DAccGD to EXTRA [36], DIGing [26], Mudag [42], and APM-C [21], as a result of the comparison, DAccGD outperformed all the mentioned algorithms.”
Friedkin-Johnsen Model is Distributed Gradient Descent
Akgün, O. E., Vèkássy, Á., Ballotta, L., et al. (2025) · IEEE Control Systems Letters · doi:10.1109/lcsys.2025.3581718 · Cited by 1
“It is well-known that the DGD with fixed stepsizes does not converge to a consensus in general [25].”
Decentralized Nonconvex Low-rank Matrix Recovery
Gao, J., & Lian, H. (2025) · IEEE Transactions on Image Processing · doi:10.1109/tip.2025.3588719 · Cited by 1
“The weight matrix A is chosen by the Laplacian method [34] with where I is the identity matrix, d i denotes the degree of node i and L is the Laplacian matrix defined as L ii = d i , L ij = − 1 if nodes i and j are connected, and L ij = 0 otherwise.”
PMGT-VR: A Decentralized Proximal-Gradient Algorithmic Framework With Variance Reduction
Ye, H., Xiong, W., & Zhang, T. (2025) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2025.3606874 · Cited by 17
“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.”
InfluentialPeng, Y., Zhang, S., Zhou, Z., Wen, P., & Huang, F. (2025) · Signal Processing · doi:10.1016/j.sigpro.2025.110289 · Cited by 1
Deng, K., & Hu, J. J. (2025) · Numerische Mathematik · doi:10.1007/s00211-025-01497-0 · Cited by 28
“When f i ’s are convex, to achieve the exact convergence, the local historic information is investigated in various papers, such as EXTRA [46], DLM [33], exact diffusion [60], NIDS [32], and the gradient tracking-type methods [42, 57].”
Survey and prospects of distributed optimization in multi-agent systems
Jiang, X., Xianlin, Z. E. N. G., Sun, J. Q., & Chen, J. (2025) · Scientia Sinica Informationis · doi:10.1360/ssi-2025-0337 · Cited by 1
Distributed Zeroth-Order Gradient Tracking for Weakly Convex Optimization Over Unbalanced Graphs
Wang, R., Cheng, S., Fan, Y. C., & Qiu, J. (2025) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2025.3636755 · Cited by 2
“[41], [42], [43] have introduced auxiliary dynamics for global gradient information, and [44] have proposed a feasible centralized gradient estimation scheme via orthogonal random directions.”
Decentralized Stochastic Optimization Over Unreliable Networks via Two-Timescales Updates
Liu, H., Yau, C.-Y., & Wai, H.-T. (2025) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2025.3639067 · Cited by 1
“This leads to primal-only schemes such as decentralized gradient (DGD) method [6], [7], [8], [9], [10] as well as the popular extensions such as gradient tracking, EXTRA [7], [8], [11].”
Robust Distributed Cooperative Classification With Learned Compressed-Feature Diffusion
Yao, X., Chen, J., & Chen, J. (2026) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2026.3652297 · Cited by 3
Privacy-Preserving Fully Distributed Market Clearing for Peer-to-Peer Energy Trading
He, W., Yang, Y., Mishra, Y., & Tian, Y. (2026) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2026.3652997 · Cited by 1
“1) For prosumers with access to p nm , i.e., i ∈ N n , we impose a relaxed constraint √ w in (ˆ p − p nm ) = 0; 2) To ensure consensus among all prosumers’ estimates, we require ˆ p 1 nm = · · · = ˆ p Nnm , which is equivalently written as V ˆ p nm = 0 with V = L 1 / 2 , following Lemma 3.1 in [26].”
InfluentialDubrovskiy, S., & Yassine, A. (2025) · Computing, Communications and IoT Applications (ComComAp) · doi:10.1109/comcomap68359.2025.11353170 · Cited by 1
Distributed Penalty Nesterov Gradient Algorithm For Extremely Large-Scale MIMO Systems
Chen, Q., Wang, Z., Zhang, C., Shu, F., Huang, Y., & Niyato, D. T. (2026) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2026.3660267 · Cited by 3
“Alternatively, diffusion strategies have emerged as a powerful method for solving optimization problems in a decentralized fashion [21], [22], [23], [24], [25], [26], [27], [28], [29], [30], [31].”
Riemannian Momentum Tracking: Distributed Optimization With Momentum on Compact Submanifolds
Chen, J., Zhu, T., Ye, H., Liu, L., Dai, G., Liu, Y., Jiang, Y., & Tsang, I. W.-H. (2026) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2026.3667761
Topology-Optimal Multiple Gossip Steps for Decentralized Federated Learning via Gossip Tensor
Zhong, Y., Ma, L., & Yan, X. (2026) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2026.3670013 · Cited by 1
“Therefore, Lemma 1(iii) plays a key role in proving the convergence of many existing DFL algorithms [11], [13], [22], and µ ( W ) can reflect the e ff ects of graph topology on the communication rounds, as shown in Table I. Additionally, when W is not doubly stochastic, [24] demonstrates that…”
Stochastic Push–Pull for Decentralized Nonconvex Optimization
You, R., & Pu, S. (2026) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2026.3675119 · Cited by 1
“Such a challenge has motivated the development of more advanced algorithms, such as EXTRA [28], Exact-Diffusion/D 2 [10], [29], [30], [31], and gradient tracking based methods [12], [32].”
Energy-Based Deep Learning Initialization Method Achieves Precise Evolution of Soliton Dynamics
Zhang, Z., Liu, M., Xing, X., Zhang, K., Huang, X., & Liu, W. (2026) · Chinese Physics Letters · doi:10.1088/0256-307x/43/7/070402 · Cited by 1
Sparsity-aware tight frame learning for rotary machine fault diagnosis
Zhang, H., Chen, X., Du, Z., Ma, M., & Zhang, X. (2016) · IEEE International Instrumentation and Measurement Technology Conference · doi:10.1109/i2mtc.2016.7520471 · Cited by 2
Nguyen, M. N. H., Pham, C., Tran, N. H. K., et al. (2017) · International Conference on Information Networking · doi:10.1109/icoin.2017.7899457 · Cited by 1
Distributed Optimization with Binary Relative Information over Deterministically Time-varying Graphs
Zhang, J., & You, K. (2018) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc.2018.8619132 · Cited by 1
A primal-dual Quasi-Newton method for consensus optimization
Eisen, M., Mokhtari, A., & Ribeiro, A. (2017) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2017.8335187 · Cited by 2
Consensus-Based Quantized Algorithm for Convex Optimization with Smooth Cost Functions
Hayashi, N., Kajiyama, Y., & Takai, S. (2020) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1587/transfun.2019map0008 · Cited by 1
Decentralized Expectation Maximization Algorithm
Jin, H., Sun, X., & Xu, L. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-60245-1_35 · Cited by 1
An Inexact Fenchel Dual Gradient Algorithm for Distributed Optimization
Wang, H., & Lu, J. (2020) · International Conference on Control and Automation · doi:10.1109/icca51439.2020.9264365 · Cited by 1
Distributed Dynamic Online Linear Regression Over Unbalanced Graphs
Cheng, S., & Hong, Y. (2020) · International Conference on Control and Automation · doi:10.1109/icca51439.2020.9264584 · Cited by 1
“Thanks to efforts of many scholars, lots of excellent outcomes on distributed optimization were developed to handle different circumstances, such as unconstrained optimization [7]–[9] and constrained optimization [10]–[12], or over undirected graphs [13]–[15] and directed graphs [16]–[18].”
BackgroundConvergence Results of a Nested Decentralized Gradient Method for Non-strongly Convex Problems
Choi, W., Kim, D., & Yun, S.-B. (2022) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-022-02069-0 · Cited by 1
Yun-shan, L., Xiong, H., Zhou, H. Y., & Guan, X. (2022) · Mathematics · doi:10.3390/math10030357 · Cited by 2
A Snapshot Gradient Tracking for Distributed Optimization over Digraphs
Che, K., & Yang, S. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-20503-3_28 · Cited by 1
Accelerated Distributed Composite Nesterov Gradient Descent Algorithm
Yue, X., & Ni, Y. (2022) · Chinese Control Conference (CCC) · doi:10.23919/ccc55666.2022.9901596 · Cited by 1
“Based on the EXTRA method[8], the distributed proximal gradient exact first-order algorithm (PG-EXTRA) [16] is proposed to solve the consistent optimization of the local objective function with a smooth+non-smooth composite form question.”
On the Role of Data Homogeneity in Multi-Agent Non-convex Stochastic Optimization
Li, Q., & Wai, H.-T. (2022) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc51059.2022.9992403 · Cited by 1
Computational Convergence Rate Analysis of Distributed Optimization Algorithm
Du, J., Liu, Y., Zhi, Y., & Gao, H. B. (2023) · Lecture notes in electrical engineering · doi:10.1007/978-981-19-6613-2_511 · Cited by 2
An Accelerated Asynchronous Distributed Method for Convex Constrained Optimization Problems
Abolfazli, N., Jalilzadeh, A., & Hamedani, E. Y. (2023) · Conference on Information Sciences and Systems · doi:10.1109/ciss56502.2023.10089633 · Cited by 1
Distributed Situation Awareness Consensus Optimization of Unmanned Group Systems
Qiu, H., Hai, X., Sun, C., et al. (2023) · Chinese Control Conference (CCC) · doi:10.23919/ccc58697.2023.10240099 · Cited by 1
A Tracking Augmented Lagrangian Method for ℓ0 Sparse Consensus Optimization
Olama, A., Carnevale, G., Notarstefano, G., & Camponogara, E. (2023) · International Conference on Control, Decision and Information Technologies (CoDIT) · doi:10.1109/codit58514.2023.10284260 · Cited by 1
An Extended Gradient Method for Smooth and Strongly Convex Functions
Zhang, X., Liu, S., & Zhao, N. (2023) · Mathematics · doi:10.3390/math11234771 · Cited by 1
Fractional order distributed optimization algorithm based on proportional-integral protocol
Zhou, S., Zeng, Y., Hong, X., et al. (2023) · Chinese Control and Decision Conference (CCDC) · doi:10.1109/ccdc58219.2023.10326847 · Cited by 1
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.