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 601–700 of 1,315
A Decentralized Primal-Dual Method for Constrained Minimization of a Strongly Convex Function
Hamedani, E. Y., & Aybat, N. S. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3130082 · Cited by 11
Vlaski, S., & Sayed, A. H. (2021) · IEEE Statistical Signal Processing Workshop (SSP) · doi:10.1109/ssp49050.2021.9513819 · Cited by 7
A decentralized adaptive momentum method for solving a class of min-max optimization problems
Barazandeh, B., Huang, T., & Michailidis, G. C. (2021) · Signal Processing · doi:10.1016/j.sigpro.2021.108245 · Cited by 15
Zhang, J., Bedi, A. S., Wang, M., & Koppel, A. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i8.20887 · Cited by 18
Quantized Distributed Nonconvex Optimization with Linear Convergence
Xu, L., Yi, X., Sun, J., Shi, Y., Johansson, K. H., & Yang, T. (2022) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc51059.2022.9992989 · Cited by 7
Yu, X., Fan, Y. C., & Cheng, S. (2023) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2023.11.017 · Cited by 7
A decentralized Second-Order Method for Dynamic Optimization
Mokhtari, A., Shi, W., Ling, Q. H., & Ribeiro, A. (2016) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7799196 · Cited by 6
Self-citationDecentralized exact coupled optimization
Alghunaim, S. A., Yuan, K., & Sayed, A. H. (2017) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2017.8262757 · Cited by 10
Asynchronous Decentralized Consensus ADMM for Distributed Machine Learning
Zhang, J. (2019) · International Conference on High Performance Big Data and Intelligent Systems (HPBD&IS) · doi:10.1109/hpbdis.2019.8735442 · Cited by 13
Distributed convex optimization based on ADMM and belief propagation methods
Ma, W., Zhang, H., & Fu, M. (2020) · Asian Journal of Control · doi:10.1002/asjc.2284 · Cited by 7
Decentralized Constrained Optimization: Double Averaging and Gradient Projection
Shahriari-Mehr, F., Bosch, D. D., & Panahi, A. (2021) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc45484.2021.9683355 · Cited by 8
Automatic Performance Estimation for Decentralized Optimization
Colla, S., & Hendrickx, J. M. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3251902 · Cited by 16
“Numerous other methods rely on the interplay of gradient and average consensus steps, such as EX-TRA [3], DIGing [4], and NIDS [5].”
BackgroundMethodInfluentialDecentralized constrained consensus optimization with primal dual splitting projection
Zhang, H., Shi, W., Mokhtari, A., Ribeiro, A., & Ling, Q. H. (2016) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2016.7905905 · Cited by 7
Self-citationZhu, J., Xie, P., Zhang, M., Zheng, R., Xing, L., & Wu, Q. (2019) · Complexity · doi:10.1155/2019/8030792 · Cited by 7
A Distributed Optimization Algorithm over Time-Varying Graphs with Efficient Gradient Evaluations
Scoy, B. V., & Lessard, L. (2019) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2019.12.181 · Cited by 7
Distributed Networked Real-Time Learning
Garcia, A., Wang, L., Huang, J., & Hong, L. (2020) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2020.3029992 · Cited by 8
Hu, J., Ran, L., Du, Z., & Li, H. (2020) · Signal Processing · doi:10.1016/j.sigpro.2020.107894 · Cited by 11
Impact of Communication Delays on the Convergence Rate of Distributed Optimization AlgorithmsPreprint
Doan, T. T., Beck, C. L., & Srikant, R. (2017) · arXiv (Cornell University) · Cited by 8
Balancing Communication and Computation in Distributed OptimizationPreprint
Berahas, A. S., Bollapragada, R., Keskar, N. S., et al. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1709.02999 · Cited by 7
Shen, Z., Mokhtari, A., Zhou, T., Zhao, P., & Qian, H. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.09969 · Cited by 54
Stochastic Primal-Dual Algorithm for Distributed Gradient Temporal Difference LearningPreprint
Lee, D., Yoon, H., & Hovakimyan, N. (2018) · arXiv (Cornell University) · Cited by 6
Xin, R., & Khan, U. A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1808.02942 · Cited by 7
Nested Distributed Gradient Methods with Adaptive Quantized CommunicationPreprint
Berahas, A. S., Iakovidou, C., & Wei, E. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1903.08149 · Cited by 7
Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up
Richards, D., & Rebeschini, P. (2019) · Oxford University Research Archive (ORA) (University of Oxford) · doi:10.48550/arxiv.1905.03135 · Cited by 14
Decentralized Markov Chain Gradient DescentPreprint
Sun, T., & Li, D. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.10238 · Cited by 10
Gradient tracking and variance reduction for decentralized optimization and machine learningPreprint
Xin, R., Kar, S., & Khan, U. A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.05373 · Cited by 6
Yi, X., Zhang, S., Yang, T., et al. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.12110 · Cited by 7
Primal-Dual Distributed Temporal Difference LearningPreprint
Lee, D., & Hu, J. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.07918 · Cited by 9
A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex OptimizationPreprint
Xin, R., Khan, U. A., & Kar, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.06752 · Cited by 38
Stochastic proximal gradient consensus over time-varying networks
Hong, M., & Chang, T.-H. (2016) · 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) · doi:10.1109/icassp.2016.7472584 · Cited by 6
Dual-Domain Defenses for Byzantine-Resilient Decentralized Resource Allocation
Wang, R., Ling, Q. H., & Tian, Z. (2024) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2024.3485508 · Cited by 7
Self-citationLiu, B., Xie, F., & Chai, L. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3546087 · Cited by 9
“The authors in [6], [7], [8], [9], [10], [11], and [12] focus on static undirected graphs and those in [13], [14], and [15] address the time-varying/stochastic undirected graphs.”
An accelerated distributed gradient method with local memory
Ren, X., Li, D., Xi, Y., et al. (2022) · Automatica · doi:10.1016/j.automatica.2022.110260 · Cited by 6
Zhang, S., Wu, W., Li, Z., Chen, J., & Georgiou, T. T. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3413854 · Cited by 8
Xie, A., Yi, X., Wang, X., Cao, M., & Ren, X. (2024) · International Conference on Control and Automation · doi:10.1109/icca62789.2024.10591815 · Cited by 8
Zhang, Z., Yin, X., & Hu, S. (2024) · ISA Transactions · doi:10.1016/j.isatra.2024.11.055 · Cited by 6
Distributed convex optimization with coupling constraints over time-varying directed graphs†
Zhang, B., Gu, C., & Li, J. (2020) · Journal of Industrial and Management Optimization · doi:10.3934/jimo.2020061 · Cited by 9
Distributed Adaptive Learning of Graph Processes via In-Network Subspace Projections
Lorenzo, P. D., Barbarossa, S., & Sardellitti, S. (2019) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/ieeeconf44664.2019.9048992 · Cited by 6
“Then, to speed up the convergence of the proposed method, hinging on the idea of exact first-order optimization [21], we extend A-DiSPO to A-EDiSPO (i.e., Adaptive Exact Distributed Subspace Projected Optimization), whose main steps are listed in Algorithm 2.”
MethodGraph-Homomorphic Perturbations for Private Decentralized Learning
Vlaski, S., & Sayed, A. H. (2021) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp39728.2021.9413811 · Cited by 7
Decentralized Approximate Newton Methods for Convex Optimization on Networked Systems
Wei, H., Qu, Z., Wu, X., Wang, H., & Lu, J. (2021) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2021.3070663 · Cited by 7
Low Sample and Communication Complexities in Decentralized Learning: A Triple Hybrid Approach
Zhang, X., Liu, J., Zhu, Z., & Bentley, E. S. (2021) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom42981.2021.9488686 · Cited by 6
Distributed Constrained Optimization With Asynchrony and Delays
Su, E., Li, H., Zheng, Z., Lü, Q., & Wang, Z. (2021) · IEEE Transactions on Circuits & Systems II Express Briefs · doi:10.1109/tcsii.2021.3132392 · Cited by 7
“Inrecent years, the synchronous distributed methods [5]–[8] to solve problems similar to (1) have been well developed.”
BackgroundA divide-and-conquer algorithm for distributed optimization on networks
Emirov, N., Song, G., & Sun, Q. (2024) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2023.101623 · Cited by 10
Zhu, J., Wang, X., Zhang, M., Liu, M., & Wu, Q. (2022) · Complex & Intelligent Systems · doi:10.1007/s40747-022-00785-8 · Cited by 7
“To demonstrate the performance advantage of our algo-rithm, we first compare the proposed algorithm with DeFW [31], EXTRA [39], and DGD [40] on different datasets with n = 64.”
MethodKomuro, K., Yukawa, M., & Cavalcante, R. L. G. (2022) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2022.3181729 · Cited by 8
Li, J., An, Q., & Su, H. (2023) · Applied Mathematics and Computation · doi:10.1016/j.amc.2022.127801 · Cited by 7
A Fast Finite-Time Consensus based Gradient Method for Distributed Optimization over Digraphs
Jiang, W., & Charalambous, T. (2022) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc51059.2022.9992389 · Cited by 14
Wang, L., & Liu, X. (2023) · Journal of Industrial and Management Optimization · doi:10.3934/jimo.2023018 · Cited by 11
“Interested readers are referred to [35, 30] for more details.”
Shen, J., Wang, L., & Zhu, L. (2023) · International Journal of Electrical Power & Energy Systems · doi:10.1016/j.ijepes.2023.109669 · Cited by 7
A Linearly Convergent Robust Compressed Push-Pull Method for Decentralized Optimization
Liao, Y., Li, Z., & Pu, S. (2023) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc49753.2023.10384180 · Cited by 6
Dynamic Average Diffusion With Randomized Coordinate Updates
Ying, B., Yuan, K., & Sayed, A. H. (2019) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2019.2942191 · Cited by 7
“There are several interesting properties associated with the dynamic diffusion strategy (16).”
BackgroundMulti-Agent System-based Distributed Energy Management in Smart Grid under Uncertainty
Ullah, M. H., Alseyat, A., & Park, J.-D. (2019) · IEEE Energy Conversion Congress and Exposition (ECCE) · doi:10.1109/ecce.2019.8912976 · Cited by 6
On the Divergence of Decentralized Nonconvex Optimization
Hong, M., Zeng, S., Zhang, J., & Sun, H. (2022) · SIAM Journal on Optimization · doi:10.1137/20m1353149 · Cited by 9
Distributed Multi-agent Video Fast-forwarding
Lan, S., Wang, Z., Roy–Chowdhury, A. K., Wei, E., & Zhu, Q. (2020) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/3394171.3413767 · Cited by 7
Blended dynamics approach to distributed optimization: Sum convexity and convergence rate
Lee, S., & Shim, H. (2022) · Automatica · doi:10.1016/j.automatica.2022.110290 · Cited by 9
Automated Worst-Case Performance Analysis of Decentralized Gradient Descent
Colla, S., & Hendrickx, J. M. (2021) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc45484.2021.9683505 · Cited by 8
Distributed convex optimization via proportional-integral-differential algorithm
Zhu, W. Q., & Tian, H. (2021) · Measurement and Control · doi:10.1177/00202940211029332 · Cited by 6
“Multiply (1N � In) on the both sides of the second equation in (8), one can derive that”
BackgroundRobust Consensus of Multiagent Dynamics With Transmission Constraints and Noises
Wang, X., & Su, H. (2022) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2022.3147451 · Cited by 6
Optimally Compressed Nonparametric Online Learning: Tradeoffs between memory and consistency
Koppel, A., Bedi, A. S., Rajawat, K., et al. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2973567 · Cited by 6
Communication-Efficient Algorithms for Decentralized and Stochastic OptimizationPreprint
Lan, G., Lee, S., & Zhou, Y. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1701.03961 · Cited by 6
Hybrid Voltage Control in Distribution Networks Under Limited Communication RatesPreprint
Liu, H. J., Shi, W., & Zhu, H. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1707.07094 · Cited by 6
Self-citationExact Diffusion for Distributed Optimization and Learning --- Part II: Convergence AnalysisPreprint
Yuan, K., Ying, B., Zhao, X., et al. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1702.05142 · Cited by 6
Distributed Zero-Order Algorithms for Nonconvex Multi-Agent OptimizationPreprint
Tang, Y., Zhang, J., & Li, N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.11444 · Cited by 5
Li, W., Zeng, X., Liang, S., et al. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2001.00509 · Cited by 6
Distributed Aggregative Optimization over Multi-Agent NetworksPreprint
Li, X., Xie, L., & Hong, Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.13436 · Cited by 6
Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized OptimizationPreprint
Kovalev, D. A., Salim, A., & Richtárik, P. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.11773 · Cited by 102
A Survey of Distributed Optimization Methods for Multi-Robot SystemsPreprint
Halsted, T., Shorinwa, O., Yu, J., & Schwager, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.12840 · Cited by 71
Xin, R., Das, S., Khan, U. A., & Kar, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.01594 · Cited by 30
“To address this issue, stochastic methods that are robust to heterogeneous data have been proposed, e.g., D2 [51] that is derived from primal-dual formulations [22,25,47,69] and GT-DSGD [29,63] that is based on gradient tracking [10,33,38,41,67].”
Vuković, M., Jakovetić, D., Bajović, D., et al. (2024) · SIAM Journal on Control and Optimization · doi:10.1137/22m1543197 · Cited by 5
Distributed Optimization on Matrix‐Weighted Networks
Cui, Q., Ji, Z., Liu, Y., et al. (2024) · Optimal Control Applications and Methods · doi:10.1002/oca.3212 · Cited by 5
A Stochastic Gradient Tracking Algorithm for Decentralized Optimization With Inexact Communication
Shah, S. M., & Bollapragada, R. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3548470 · Cited by 7
“In the deterministic setting, algorithms such as EX-TRA [6] achieve linear convergence for strongly convex, smooth functions.”
InfluentialA stochastic gradient tracking algorithm with adaptive momentum for distributed optimization
Li, Y., Hu, H., Zhang, K., Lü, Q., Deng, S., & Li, H. (2025) · Neurocomputing · doi:10.1016/j.neucom.2025.130095 · Cited by 5
Xu, L., Yi, X., Sun, J., Shi, Y., Johansson, K. H., & Yang, T. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3563431 · Cited by 11
Differentially private and communication-efficient distributed nonconvex optimization algorithms
Xie, A., Yi, X., Wang, X., Cao, M., & Ren, X. (2025) · Automatica · doi:10.1016/j.automatica.2025.112338 · Cited by 12
Delay-tolerant augmented-consensus-based distributed directed optimization
Doostmohammadian, M., Narahari, K. R., & Aghasi, A. (2025) · Systems & Control Letters · doi:10.1016/j.sysconle.2025.106260 · Cited by 9
“…reduced-complexity and flexible algorithms [10], primal-dual subgradient-based solutions [11], EXTRA algorithm for first-order consensus-based optimization [12], push-pull gradient-based methods [13], and the solutions based on alternating direction method of multipliers (ADMM) [14, 15, 16, 17].”
Distributed convex optimization as a tool for solving f -consensus problems
Huang, C., Anderson, B. D. O., Zhang, H., et al. (2023) · Automatica · doi:10.1016/j.automatica.2023.111087 · Cited by 5
Peng, J., Li, W., & Ling, Q. H. (2024) · Signal Processing · doi:10.1016/j.sigpro.2024.109419 · Cited by 5
Self-citationYuan, R., Zhao, Z., Chen, S., & Chai, T. (2024) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.7336 · Cited by 6
Distributed optimisation algorithm based on iterative learning control
Dong, X., Zhang, R., Chen, X., & Xue, L. (2024) · International Journal of Systems Science · doi:10.1080/00207721.2024.2388810 · Cited by 5
A forward-backward Bregman splitting scheme for regularized distributed optimization problems
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2016) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798413 · Cited by 5
A generalized algorithm for continuous-time distributed optimization
Yu, H., Dhullipalla, M. H., & Chen, T. (2021) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc50511.2021.9483292 · Cited by 5
Decentralized proximal splitting algorithms for composite constrained convex optimization
Zheng, L., Ran, L., Li, H., Feng, L., Wang, Z., Lü, Q., & Xia, D. (2022) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2022.07.053 · Cited by 5
Subgradient-Push Is of the Optimal Convergence Rate
Lin, Y., & Liu, J. (2022) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc51059.2022.9992842 · Cited by 8
Frugal and decentralised resolvent splittings defined by nonexpansive operators
Tam, M. K. (2023) · Optimization Letters · doi:10.1007/s11590-023-02064-y · Cited by 18
GradConsensus: Linearly Convergent Algorithm for Reducing Disagreement in Multi-Agent Optimization
Khatana, V., Saraswat, G., Patel, S., & Salapaka, M. V. (2023) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2023.3321757 · Cited by 7
Zeroth-order Gradient Tracking for Distributed Constrained Optimization
Cheng, S., Yu, X., Fan, Y. C., et al. (2023) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2023.10.115 · Cited by 5
Accelerated Distributed Nesterov Optimization Subject to Complex Constraints and Its Applications
Liu, B., Du, W., & Li, Z. (2023) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2023.3331334 · Cited by 5
Private and Robust Distributed Nonconvex Optimization via Polynomial Approximation
He, Z., He, J., Chen, C., & Guan, X. (2024) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2024.3354875 · Cited by 7
Provably Accelerated Decentralized Gradient Methods Over Unbalanced Directed Graphs
Song, Z., Shi, L., Pu, S., & Yan, M. (2024) · SIAM Journal on Optimization · doi:10.1137/22m148570x · Cited by 11
MUSIC: Accelerated Convergence for Distributed Optimization With Inexact and Exact Methods
Wu, M., Liao, H., Ding, Z., & Xiao, Y. (2024) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2024.3376421 · Cited by 8
“Without any increase in communication as the inex-act MUSIC method, the proposed method is communication efficient and exactly converges to the optimal solution.”
InfluentialDistributed Heavy-Ball Over Time-Varying Digraphs With Barzilai-Borwein Step Sizes
Yang, S., Shen, Y. ‐., Cao, J., & Huang, T. (2024) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2024.3382232 · Cited by 6
Zhou, Y., Guo, L., Shi, X., & Cao, J. (2024) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2024.3462519 · Cited by 12
“In fact, the proposed SDP-ADMM is closely related to the existing algorithms such as EXTRA [48], DLM [20], and PG-EXTRA [25].”
Adaptive Consensus: A Network Pruning Approach for Decentralized Optimization
Shah, S. M., Berahas, A. S., & Bollapragada, R. (2024) · SIAM Journal on Optimization · doi:10.1137/23m1599379 · Cited by 8
Asynchronous Distributed Optimization With Delay-free Parameters
Wu, X., Liu, C., Magnússon, S., & Johansson, M. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3590953 · Cited by 11
“In addition to being an averaging matrix, this section assumes W to be positive definite, which can be satisfied by letting W = W (cid:23) + I 2 for any averaging matrix W (cid:23) associated with G [33, Sect.”
Nesterov Accelerated Gradient Tracking With Adam for Distributed Online Optimization
Su, Y., Sheng, Q., Shi, X., et al. (2025) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2025.3604059 · Cited by 5
“Under di ff erent assumptions, gradient tracking has spawned numerous variants [26], [27], [28], e ff ectively addressing online optimization problems [17].”
Kajiyama, Y., Hayashi, N., & Takai, S. (2017) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2017.8264346 · Cited by 6
Distributed Deterministic Asynchronous Algorithms in Time-Varying Graphs Through Dykstra Splitting
Pang, C. H. J. (2019) · SIAM Journal on Optimization · doi:10.1137/18m1168297 · Cited by 5
Decentralized Optimization with Edge Sampling
Zhang, C., Li, Q., & Zhao, P. (2019) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2019/93 · Cited by 5
A Unified Contraction Analysis of a Class of Distributed Algorithms for Composite Optimization
Xu, J., Sun, Y., Tian, Y., & Scutari, G. (2019) · IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing · doi:10.1109/camsap45676.2019.9022451 · Cited by 7
Distributed Constrained Optimization with Linear Convergence Rate
Dong, Z., Mao, S., Du, W., & Tang, Y. S. (2020) · International Conference on Control and Automation · doi:10.1109/icca51439.2020.9264327 · Cited by 6
“The first algorithm proved to converge linearly is EXTRA (exact first-order algorithm) [13], which is suitable for fixed communication topology.”
Method
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.