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 201–300 of 1,315
Privacy-Preserving Incremental ADMM for Decentralized Consensus Optimization
Ye, Y., Chen, H., Xiao, M., Skoglund, M., & Poor, H. V. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3027917 · Cited by 39
Accelerated First-Order Optimization Algorithms for Machine Learning
Li, H., Fang, C., & Lin, Z. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2020.3007634 · Cited by 52
“Classical distributed algorithms include the distributed GD (DGD) [86], EXTRA [87], the gradient-tracking-based methods Table 2 Gradient Complexity Comparisons Between SGD, SVRG, and”
MethodDistributed Stochastic Consensus Optimization With Momentum for Nonconvex Nonsmooth Problems
Wang, Z., Zhang, J., Chang, T., Li, J., & Luo, Z.-Q. T. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3097211 · Cited by 55
A Fast Randomized Incremental Gradient Method for Decentralized Nonconvex Optimization
Xin, R., Khan, U. A., & Kar, S. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3122586 · Cited by 50
Decentralized Joint-Sparse Signal Recovery: A Sparse Bayesian Learning Approach
Khanna, S., & Murthy, C. R. (2016) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2016.2612120 · Cited by 39
Distributed Optimization with Dynamic Event-Triggered Mechanisms
Du, W. J., Yi, X., George, J., Johansson, K. H., & Yang, T. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619311 · Cited by 44
S-DIGing: A Stochastic Gradient Tracking Algorithm for Distributed Optimization
Li, H., Zheng, L., Wang, Z., Yan, Y., Feng, L., & Guo, J. (2020) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2020.3017242 · Cited by 40
Song, Q., Meng, D., & Liu, F. (2021) · Automatica · doi:10.1016/j.automatica.2021.110096 · Cited by 37
GTAdam: Gradient Tracking With Adaptive Momentum for Distributed Online Optimization
Carnevale, G., Farina, F., Notarnicola, I., & Notarstefano, G. (2022) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2022.3232519 · Cited by 49
Zeroth Order Nonconvex Multi-Agent Optimization over NetworksPreprint
Hajinezhad, D., Hong, M., & García, A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.09997 · Cited by 35
Distributed discrete-time optimization over directed networks: A dynamic event-triggered algorithm
Yang, Y., He, W., Tian, Y., Du, W., & Qian, F. (2023) · Information Sciences · doi:10.1016/j.ins.2023.119168 · Cited by 35
Wai, H.-T., Chang, T., & Scaglione, A. (2015) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2015.7178631 · Cited by 40
Fast proximity-gradient algorithms for structured convex optimization problems
Qia, L., & Zhang, N. (2015) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2015.11.004 · Cited by 36
Private Optimization on Networks
Gade, S., & Vaidya, N. H. (2018) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2018.8430960 · Cited by 46
Accelerated Gradient Play Algorithm for Distributed Nash Equilibrium Seeking
Tatarenko, T., Shi, W., & Nedić, A. (2018) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc.2018.8619479 · Cited by 35
Self-citationLi, R., & Yang, G. (2019) · Information Sciences · doi:10.1016/j.ins.2019.08.010 · Cited by 33
Dynamics based privacy preservation in decentralized optimization
Gao, H. B., Wang, Y., & Nedić, A. (2023) · Automatica · doi:10.1016/j.automatica.2023.110878 · Cited by 44
Power Spectra Separation via Structured Matrix Factorization
Fu, X., Sidiropoulos, N. D., & Ma, W. (2016) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2560142 · Cited by 34
Expander graph and communication-efficient decentralized optimization
Chow, Y. T., Shi, W., Wu, T., & Yin, W. (2016) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2016.7869675 · Cited by 36
Self-citationSun, H., Lu, S., & Hong, M. (2020) · International Conference on Machine Learning · Cited by 44
Distributed Optimization With Coupling Constraints
Wu, X., Wang, H., & Lu, J. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3169955 · Cited by 49
Finite-Bit Quantization for Distributed Algorithms With Linear Convergence
Michelusi, N., Scutari, G., & Lee, C.-S. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3176253 · Cited by 39
Surplus-based accelerated algorithms for distributed optimization over directed networks
Wang, D., Wang, Z., Lian, J., & Wang, W. (2022) · Automatica · doi:10.1016/j.automatica.2022.110569 · Cited by 35
Confederated Learning: Federated Learning With Decentralized Edge Servers
Wang, B., Fang, J., Li, H., Yuan, X., & Ling, Q. H. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3241768 · Cited by 45
Self-citationPrivacy-Preserving Distributed Learning via Obfuscated Stochastic Gradients
Gade, S., & Vaidya, N. H. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619133 · Cited by 46
A Fast Row-Stochastic Decentralized Method for Distributed Optimization Over Directed Graphs
Ghaderyan, D., Aybat, N. S., Aguiar, A. P., & Перейра, Ф. Л. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3275927 · Cited by 45
DC-DistADMM: ADMM Algorithm for Constrained Optimization Over Directed Graphs
Khatana, V., & Salapaka, M. V. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3221856 · Cited by 44
Olshevsky, A., Paschalidis, I. C., & Spiridonoff, A. (2018) · arXiv (Cornell University) · Cited by 31
Value Propagation for Decentralized Networked Deep Multi-agent Reinforcement LearningPreprint
Qu, C., Mannor, S., Xu, H., Qi, Y., Song, L., & Xiong, J. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.09326 · Cited by 54
A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient DescentPreprint
Pu, S., Olshevsky, A., & Paschalidis, I. C. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.02702 · Cited by 33
“Problem (1.1) has been studied extensively in the literature under various distributed algorithms [48, 30, 31, 23, 19, 20, 44, 15, 40, 28, 50, 39], among which the distributed gradient descent (DGD) method proposed in [30] has drawn the greatest attention.”
InfluentialLoizou, N., & Richtárik, P. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3113285 · Cited by 48
Resilient consensus‐based distributed optimization under deception attacks
Fu, W., Ma, Q., Qin, J., & Kang, Y. (2020) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.5026 · Cited by 39
“To overcome the shortcoming of slow convergence due to the diminishing step-sizes in DGD, fixed step-sizes are utilized from different perspectives 21-25 to develop a great number of distributed optimization algorithms.”
MethodResource-Aware Exact Decentralized Optimization Using Event-Triggered Broadcasting
Liu, C., Li, H., & Shi, Y. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3014316 · Cited by 34
Communication-Censored Linearized ADMM for Decentralized Consensus Optimization
Li, W., Liu, Y., Tian, Z., & Ling, Q. H. (2019) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2019.2957719 · Cited by 35
Self-citationQuasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous DataPreprint
Lin, T., Karimireddy, S. P., Stich, S. U., & Jaggi, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.04761 · Cited by 120
Ouassal, H., Rocco, T., Yan, M., & Nanzer, J. A. (2020) · IEEE Transactions on Antennas and Propagation · doi:10.1109/tap.2020.2977751 · Cited by 30
FedHybrid: A Hybrid Federated Optimization Method for Heterogeneous Clients
Niu, X., & Wei, E. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3240083 · Cited by 44
“Primal iterative methods, including distributed (sub)-gradient descent (DGD) and related methods [20, 25], have updates in the form of some linear combinations of a gradient descent step with respect to its local objective function and a weighted average with local neighbors.”
Hong, M. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1604.00543 · Cited by 50
Maros, M., & Jaldén, J. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619626 · Cited by 34
A Canonical Form for First-Order Distributed Optimization Algorithms
Sundararajan, A., Scoy, B. V., & Lessard, L. (2019) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2019.8814838 · Cited by 40
“ζ0 ζ1 ζ2 ζ3 EXTRA [17] 12 1 0 0 NIDS [7] 12 1 0 1 2 Exact Diffusion [23] 12 1 0 1 2 DIGing [9, 15] 0 2 1 0 AsynDGM [22] 0 2 1 1 Jakovetić [4] (B = βI) αβ 2 1 0 Jakovetić [4] (B = βW ) αβ 2 1− αβ 0”
Accelerated Distributed Energy Management for Microgrids
Du, W. J., Yao, L., Wu, D. X., et al. (2018) · IEEE Power & Energy Society General Meeting (PESGM) · doi:10.1109/pesgm.2018.8586094 · Cited by 30
Distributed projection‐free algorithm for constrained aggregative optimization
Wang, T., & Yi, P. (2023) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.6640 · Cited by 35
Yu, X., & Wang, Y. (2023) · Automatica · doi:10.1016/j.automatica.2023.111150 · Cited by 35
Networked Signal and Information Processing: Learning by multiagent systems
Vlaski, S., Kar, S., Sayed, A. H., & Moura, J. M. F. (2023) · IEEE Signal Processing Magazine · doi:10.1109/msp.2023.3267896 · Cited by 47
Decentralized gradient tracking with local steps
Liu, Y., Lin, T., Koloskova, A., & Stich, S. U. (2024) · Optimization methods & software · doi:10.1080/10556788.2024.2322095 · Cited by 72
Multi-consensus Decentralized Accelerated Gradient DescentPreprint
Ye, H., Luo, L., Zhou, Z., & Zhang, T. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.00797 · Cited by 52
On the Linear Convergence of Distributed Optimization over Directed Graphs
Xi, C., & Khan, U. A. (2015) · arXiv · doi:10.48550/arxiv.1510.02149 · Cited by 29
An approximate Newton method for distributed optimization
Mokhtari, A., Ling, Q. H., & Ribeiro, A. (2015) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2015.7178513 · Cited by 28
Self-citationDistributed Algorithms with Finite Data Rates that Solve Linear Equations
Lei, J., Yi, P., Shi, G., & Anderson, B. D. O. (2020) · SIAM Journal on Optimization · doi:10.1137/19m1258864 · Cited by 30
Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
Song, Z., Shi, L., Pu, S., & Yan, M. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3160238 · Cited by 45
Decentralized Federated Learning for Industrial IoT With Deep Echo State Networks
Qiu, W., Ai, W., Chen, H., Feng, Q., & Tang, G. (2022) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2022.3194627 · Cited by 36
Sparsity-aware tight frame learning with adaptive subspace recognition for multiple fault diagnosis
Zhang, H., Chen, X., Du, Z., & Yang, B. (2017) · Mechanical Systems and Signal Processing · doi:10.1016/j.ymssp.2017.02.043 · Cited by 29
Ding, T., Zhu, S., He, J., Chen, C., & Guan, X. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619119 · Cited by 28
Can Primal Methods Outperform Primal-Dual Methods in Decentralized Dynamic Optimization?
Yuan, K., Xu, W., & Ling, Q. H. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3011640 · Cited by 36
Self-citationConcepts and Application of DNA Origami and DNA Self-Assembly: A Systematic Review
Liu, W., Duan, H., Zhang, D., Zhang, X., Luo, Q., Xie, T., Yan, H., Peng, L., Hu, Y., Li, L., et al. (2021) · Applied Bionics and Biomechanics · doi:10.1155/2021/9112407 · Cited by 38
Privacy-Preserving Distributed ADMM With Event-Triggered Communication
Zhang, Z., Yang, S., Xu, W., & Di, K. (2022) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3192346 · Cited by 32
Walk for Learning: A Random Walk Approach for Federated Learning From Heterogeneous Data
Ayache, G., Dasari, V. R., & Rouayheb, S. E. (2023) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2023.3244250 · Cited by 46
Improved Convergence Rates for Distributed Resource AllocationPreprint
Nedić, A., Olshevsky, A., & Shi, W. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.05441 · Cited by 28
“0. The preceding relation and (26) yield xk → x˜. To establish the rate of convergence, we use a convergence property of nonnegative monotonic scalar sequence, which has appeared in recent work [27], [28]. The result is stated in the following: Proposition 1. If a sequence {ak} ⊂ R is such that ak ≥ 0, P∞ t=1 at <…”
MethodSelf-citationMatcha: A Matching-Based Link Scheduling Strategy to Speed up Distributed Optimization
Wang, J., Sahu, A. K., Joshi, G., & Kar, S. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3212536 · Cited by 43
A Newton Tracking Algorithm With Exact Linear Convergence for Decentralized Consensus Optimization
Zhang, J., Ling, Q. H., & So, A. M. (2021) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2021.3083975 · Cited by 39
“We compare Newton tracking with several first-order algorithms, including gradient tracking [21], EXTRA [17], and DLM [16].”
MethodSelf-citationDeceFL: a principled fully decentralized federated learning framework
Yuan, Y., Liu, J., Jin, D., Yue, Z., Yang, T., Chen, R., Wang, M., Xu, L., Hua, F., Guo, Y., et al. (2023) · National Science Open · doi:10.1360/nso/20220043 · Cited by 34
Distributed Primal-Dual Method for Convex Optimization With Coupled Constraints
Su, Y., Wang, Q., & Sun, C. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3123888 · Cited by 38
Distributed Aggregative Optimization via Finite-time Dynamic Average Consensus
Chen, M., Wang, D., Wang, X., Wu, Z., & Wang, W. (2023) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2023.3253143 · Cited by 27
Wu, M., Xiong, N. N., Vasilakos, A. V., Leung, V. C. M., & Chen, C. L. P. (2020) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.3011819 · Cited by 28
Doan, T. T., Beck, C. L., & Srikant, R. (2017) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3154496 · Cited by 40
Accelerated Distributed Nesterov Gradient Descent for smooth and strongly convex functions
Qu, G., & Li, N. (2016) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2016.7852231 · Cited by 28
Distributed Design for Nuclear Norm Minimization of Linear Matrix Equations With Constraints
Li, W., Zeng, X., Hong, Y., & Ji, H. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2981930 · Cited by 27
Recent Theoretical Advances in Decentralized Distributed Convex Optimization
Gorbunov, E., Rogozin, A., Beznosikov, A. N., Dvinskikh, D., & Gasnikov, A. V. (2022) · Springer optimization and its applications · doi:10.1007/978-3-031-00832-0_8 · Cited by 48
“For non-accelerated dynamics [133, 111] complexity bounds include κ and χ .”
BackgroundMethodInfluentialDistributed Adaptive Subgradient Algorithms for Online Learning Over Time-Varying Networks
Zhang, M., Hao, B., Ge, Q., Zhu, J., Zheng, R., & Wu, Q. (2021) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2021.3097714 · Cited by 28
Pin, L., Xiao, F., Wei, B., & Wang, A. (2021) · Systems & Control Letters · doi:10.1016/j.sysconle.2021.105002 · Cited by 26
Zeroth-order feedback optimization for cooperative multi-agent systems
Tang, Y., Ren, Z., & Li, N. (2022) · Automatica · doi:10.1016/j.automatica.2022.110741 · Cited by 36
Innovation Compression for Communication-Efficient Distributed Optimization With Linear Convergence
Zhang, J., You, K., & Xie, L. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3241771 · Cited by 34
Broadcast-based distributed alternating direction method of multipliers
Makhdoumi, A., & Ozdaglar, A. (2014) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2014.7028466 · Cited by 30
Stochastic sub-gradient algorithm for distributed optimization with random sleep scheme
Yi, P., & Hong, Y. (2015) · Control Theory and Technology · doi:10.1007/s11768-015-5100-8 · Cited by 26
“To eliminate the disagreements between the agents’ estimates, which indeed constitute the main obstacle in the optimal solution seeking, consensus-type algorithms are usually incorporated into the distributed optimization algorithms, like [1–15].”
BackgroundMethodInfluentialDistributed Gradient Methods with Variable Number of Working Nodes
Jakovetić, D., Bajović, D., Krejić, N., & Jerinkić, N. K. (2016) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2560133 · Cited by 22
Decentralised seismic tomography computing in cyber-physical sensor systems
Zhao, L., Song, W., Shi, L., & Ye, X. (2015) · Cyber-Physical Systems · doi:10.1080/23335777.2015.1062049 · Cited by 24
Gradient-Consensus Method for Distributed Optimization in Directed Multi-Agent Networks
Khatana, V., Saraswat, G., Patel, S., & Salapaka, M. V. (2020) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc45564.2020.9147544 · Cited by 30
“Unlike the ergodic error estimates common in the existing literature [6, 10, 15, 16, 20], bound on the error between the objective function at the local estimate of the optimal solution, and the optimal value is provided at each iteration.”
BackgroundResultInfluentialLv, Y.-W., Yang, G., & Shi, C. (2020) · Information Sciences · doi:10.1016/j.ins.2020.05.119 · Cited by 27
Distributed continuous‐time constrained convex optimization with general time‐varying cost functions
Huang, B., Zou, Y., & Meng, Z. (2020) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.5383 · Cited by 25
“First, our algorithm can be seen as a generalization of the work in References 1,7-17 where the cost functions are time-invariant.”
MethodA linearly convergent algorithm for distributed principal component analysis
Gang, A., & Bajwa, W. U. (2021) · Signal Processing · doi:10.1016/j.sigpro.2021.108408 · Cited by 24
An Accelerated Method For Decentralized Distributed Stochastic Optimization Over Time-Varying Graphs
Rogozin, A., Bochko, M., Dvurechensky, P. E., Gasnikov, A. V., & Lukoshkin, V. (2021) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc45484.2021.9683110 · Cited by 34
Li, H., Hu, J., Ran, L., Wang, Z., Lü, Q., Du, Z., & Huang, T. (2021) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2021.3072373 · Cited by 28
Decentralized Consensus Optimization Based on Parallel Random Walk
Ye, Y., Chen, H., Ma, Z., & Xiao, M. (2019) · IEEE Communications Letters · doi:10.1109/lcomm.2019.2955442 · Cited by 26
An Accelerated Decentralized Stochastic Proximal Algorithm for Finite SumsPreprint
Hendrikx, H., Bach, F., & Massoulié, L. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.11394 · Cited by 25
Network Newton-Part II: Convergence Rate and ImplementationPreprint
Mokhtari, A., Ling, Q. H., & Ribeiro, A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1504.06020 · Cited by 27
Self-citationZhang, R., Guo, G., & Zhou, Z.-D. (2024) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2024.3498323 · Cited by 24
Fast decentralized gradient descent method and applications to in-situ seismic tomography
Zhao, L., Song, W., & Ye, X. (2015) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata.2015.7363839 · Cited by 24
Approximate Projection Methods for Decentralized Optimization With Functional Constraints
Lee, S., & Zavlanos, M. M. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2778696 · Cited by 25
Decentralized quadratically approximated alternating direction method of multipliers
Mokhtari, A., Shi, W., Ling, Q. H., & Ribeiro, A. (2015) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2015.7418306 · Cited by 26
Self-citationCao, X., & Başar, T. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2997394 · Cited by 32
Distributed constraint-coupled optimization via primal decomposition over random time-varying graphs
Camisa, A., Farina, F., Notarnicola, I., & Notarstefano, G. (2021) · Automatica · doi:10.1016/j.automatica.2021.109739 · Cited by 35
Improved distributed optimization algorithm and its application in energy saving of ethylene plant
Wang, T., Ye, Z., Wang, X., Li, Z., & Du, W. (2022) · Chemical Engineering Science · doi:10.1016/j.ces.2022.117449 · Cited by 24
Privacy-Preserved Distributed Optimization for Multi-Agent Systems With Antagonistic Interactions
Luo, Q., Liu, S., Wang, L., & Tian, E. (2022) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2022.3226578 · Cited by 28
“…distributed optimization algorithms that are commonly utilized, namely, the so-called first-order algorithm (i.e. only using the gradient information of the objective function) [24], [25] and the second-order algorithm (i.e. using the Hessian matrix information of the objective function) [26], [27].”
MethodDistributed Online Adaptive Gradient Descent With Event-Triggered Communication
Okamoto, K., Hayashi, N., & Takai, S. (2023) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2023.3294432 · Cited by 28
Distributed subgradient method for multi‐agent optimization with quantized communication
Li, J., Chen, G., Wu, Z., & He, X. (2016) · Mathematical Methods in the Applied Sciences · doi:10.1002/mma.4044 · Cited by 28
“When the gradients of local objectives are Lipschitz continuous, the recent algorithm EXTRA proposed in [16, 17] showed a better performance of convergence.”
Distributed Big-Data Optimization via Blockwise Gradient Tracking
Notarnicola, I., Sun, Y., Scutari, G., & Notarstefano, G. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3008713 · Cited by 26
Compressed Distributed Gradient Descent: Communication-Efficient Consensus over Networks
Zhang, X., Liu, J., Zhu, Z., & Bentley, E. S. (2019) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2019.8737489 · Cited by 27
An Optimal Algorithm for Decentralized Finite-Sum Optimization
Hendrikx, H., Bach, F., & Massoulié, L. (2021) · SIAM Journal on Optimization · doi:10.1137/20m134842x · Cited by 77
Optimal Algorithms for Distributed OptimizationPreprint
Uribe, C. A., Lee, S., Gasnikov, A. V., & Nedić, A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1712.00232 · Cited by 40
Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent NetworksPreprint
Fallah, A., Gürbüzbalaban, M., Ozdaglar, A., Şimşekli, U., & Zhu, L. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.08701 · Cited by 28
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.