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 101–200 of 1,315
Distributed Coordination for Nonsmooth Convex Optimization via Saddle-Point Dynamics
Cortés, J., & Niederländer, S. K. (2018) · Journal of Nonlinear Science · doi:10.1007/s00332-018-9516-4 · Cited by 84
“The availability of such characterizations is of critical importance to assess the speed of convergence of discrete-time implementations of the dynamics, see for instance [17, 51].”
BackgroundA Nesterov-Like Gradient Tracking Algorithm for Distributed Optimization Over Directed Networks
Lü, Q., Liao, X., Li, H., & Huang, T. (2020) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2019.2960770 · Cited by 79
“To overcome these difficulties effectively, quite a few approaches have been proposed, which achieve linear convergence for smooth and strongly convex cost functions [31]–[38].”
BackgroundMethodAsySPA: An Exact Asynchronous Algorithm for Convex Optimization Over Digraphs
Zhang, J., & You, K. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2930234 · Cited by 94
Decentralized multi-agent reinforcement learning with networked agents: recent advances
Zhang, K., Yang, Z., & Başar, T. (2021) · Frontiers of Information Technology & Electronic Engineering · doi:10.1631/fitee.1900661 · Cited by 125
Hybrid Voltage Control in Distribution Networks Under Limited Communication Rates
Liu, H. J., Shi, W., & Zhu, H. (2018) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2018.2797692 · Cited by 75
Self-citationRobust and communication-efficient collaborative learning
Reisizadeh, A., Taheri, H., Mokhtari, A., Hassani, H., & Pedarsani, R. (2019) · arXiv · doi:10.48550/arxiv.1907.10595 · Cited by 73
“…descent-type methods (Nedic and Ozdaglar, 2009; Jakovetic et al., 2014; Yuan et al., 2016; Qu and Li, 2017), augmented Lagrangian algorithms (Shi et al., 2015a,b; Mokhtari and Ribeiro, 2016), distributed variants of the alternating direction method of multipliers (ADMM) (Schizas et al.,…”
Harnessing smoothness to accelerate distributed optimization
Qu, G., & Li, N. (2016) · 2016 IEEE 55th Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798263 · Cited by 72
Distributed Online Aggregative Optimization for Dynamic Multirobot Coordination
Carnevale, G., Camisa, A., & Notarstefano, G. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3196627 · Cited by 83
Distributed Learning in the Nonconvex World: From batch data to streaming and beyond
Chang, T., Hong, M., Wai, H.-T., Zhang, X., & Lu, S. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2970170 · Cited by 114
Shi, C., & Yang, G. (2018) · Automatica · doi:10.1016/j.automatica.2018.04.010 · Cited by 70
Distributed Nesterov Gradient Methods Over Arbitrary Graphs
Xin, R., Jakovetić, D., & Khan, U. A. (2019) · IEEE Signal Processing Letters · doi:10.1109/lsp.2019.2925537 · Cited by 86
Exponential convergence of a distributed algorithm for solving linear algebraic equations
Liu, J., Morse, A. S., Nedić, A., & Başar, T. (2017) · Automatica · doi:10.1016/j.automatica.2017.05.004 · Cited by 67
Distributed least squares solver for network linear equations
Yang, T., George, J., Qin, J., Yi, X., & Wu, J. (2020) · Automatica · doi:10.1016/j.automatica.2019.108798 · Cited by 76
Sun, H., & Hong, M. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2943230 · Cited by 85
“The problem (1) and (2) have been studied extensively in the literature when f i ’s are all convex; see for example [5]–[7].”
BackgroundMethodDistributed Proximal Algorithms for Multiagent Optimization With Coupled Inequality Constraints
Li, X., Feng, G., & Xie, L. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2989282 · Cited by 75
“On the other hand, the dual-decomposition-based algorithms aim at handling the alignment of all local decision variables by equality constraints, through introducing corresponding dual variables, and typical algorithms include alternating direction method of multipliers (ADMM) [11], augmented Lagrangian method [12], d…”
Perturbed proximal primal–dual algorithm for nonconvex nonsmooth optimization
Hajinezhad, D., & Hong, M. (2019) · Mathematical Programming · doi:10.1007/s10107-019-01365-4 · Cited by 62
On the Influence of Bias-Correction on Distributed Stochastic Optimization
Yuan, K., Alghunaim, S. A., Ying, B., & Sayed, A. H. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3008605 · Cited by 89
DAdam: A Consensus-Based Distributed Adaptive Gradient Method for Online Optimization
Nazari, P., Tarzanagh, D. A., & Michailidis, G. C. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3223214 · Cited by 118
“In this section, we evaluate the effectiveness of the proposed D ADAM -type algorithms such as DA DAGRAD , D ADADELTA , D RMSPROP , and D ADAM by comparing them with S GD [48], D SGD [13, 20, 26, 6] and corrected D SGD (C-D SGD ) [17, 19].”
InfluentialAsynchronous Decentralized Parallel Stochastic Gradient DescentPreprint
Lian, X., Zhang, W., Zhang, C., & Liu, J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.06952 · Cited by 444
Distributed Newton Method for Large-Scale Consensus Optimization
Tutunov, R., Ammar, H. B., & Jadbabaie, A. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2907711 · Cited by 60
Distributed Learning in Non-Convex Environments—Part I: Agreement at a Linear Rate
Vlaski, S., & Sayed, A. H. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3050858 · Cited by 85
ExtraPush for convex smooth decentralized optimization over directed networks
Zeng, J., & Yin, W. (2015) · arXiv · doi:10.48550/arxiv.1511.02942 · Cited by 65
Self-citationLi, Q., Liao, Y., Wu, K., Zhang, L., Lin, J., Chen, M., Guerrero, J. M., & Abbott, D. (2021) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2021.3097047 · Cited by 65
Initialization-free privacy-guaranteed distributed algorithm for economic dispatch problem
Yun, H., Shim, H., & Ahn, H. (2019) · Automatica · doi:10.1016/j.automatica.2018.12.033 · Cited by 61
Yuan, D., Ho, D. W. C., & Hong, Y. (2016) · SIAM Journal on Control and Optimization · doi:10.1137/15m1048896 · Cited by 58
GNSD: a Gradient-Tracking Based Nonconvex Stochastic Algorithm for Decentralized Optimization
Lu, S., Zhang, X., Sun, H., & Hong, M. (2019) · IEEE Data Science Workshop (DSW) · doi:10.1109/dsw.2019.8755807 · Cited by 97
Differentially Private Consensus With Quantized Communication
Gao, L., Deng, S., Ren, W., & Hu, C. (2019) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2018.2890645 · Cited by 64
Graph balancing for distributed subgradient methods over directed graphs
Makhdoumi, A., & Ozdaglar, A. (2015) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402401 · Cited by 64
“The recent paper [40], proposes a gradient-based distributed algorithm for convex objecti v function with Lipschitz continuous gradients and shows its convergence with rateO( 1 T ).”
BackgroundA Bregman Splitting Scheme for Distributed Optimization Over Networks
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2805260 · Cited by 62
A federated data-driven evolutionary algorithm
Xu, J., Jin, Y., Du, W., & Gu, S. (2021) · Knowledge-Based Systems · doi:10.1007/s40747-021-00506-7 · Cited by 79
A Two-Tier Distributed Market Clearing Scheme for Peer-to-Peer Energy Sharing in Smart Grid
Ullah, M. H., & Park, J.-D. (2021) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2021.3058511 · Cited by 62
Yi, X., Zhang, S., Yang, T., Chai, T., & Johansson, K. H. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3108501 · Cited by 83
A clustering WSN routing protocol based on node energy and multipath
Wang, Z., Zhang, M., Gao, X., et al. (2017) · Cluster Computing · doi:10.1007/s10586-017-1550-8 · Cited by 56
A Compressed Gradient Tracking Method for Decentralized Optimization With Linear Convergence
Liao, Y., Li, Z., Huang, K., & Pu, S. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3180695 · Cited by 90
“Under a constant step-size, EXTRA [5] first achieved linear convergence rate for strongly convex and smooth cost functions by introducing an extra correction term to DGD. Distributed gradient tracking-based methods were later developed in [6]–[9], where the local gradient descent direction in DGD…”
Differential Privacy in Distributed Optimization With Gradient Tracking
Huang, L., Wu, J., Shi, D., Dey, S., & Shi, L. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3352328 · Cited by 78
A Dual Splitting Approach for Distributed Resource Allocation With Regularization
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2018) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2018.2834310 · Cited by 52
Liu, H., Yu, W., & Chen, G. (2020) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.3022240 · Cited by 55
Newton-like Method with Diagonal Correction for Distributed Optimization
Bajović, D., Jakovetić, D., Krejić, N., & Jerinkić, N. K. (2017) · SIAM Journal on Optimization · doi:10.1137/15m1038049 · Cited by 69
Primal–Dual Methods for Large-Scale and Distributed Convex Optimization and Data Analytics
Jakovetić, D., Bajović, D., Xavier, J., & Moura, J. M. F. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2020.3007395 · Cited by 67
“To illustrate, we consider EXTRA proposed in [30], a method developed from the standpoint of correcting the fixed point equation of the standard distributed gradient method [23] x (1) where W = I − L is the weight matrix and α > 0 is a step size.”
BackgroundMethodInfluentialDistributed Nesterov Gradient and Heavy-Ball Double Accelerated Asynchronous Optimization
Li, H., Cheng, H., Wang, Z., & Wu, G. (2020) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.3027381 · Cited by 62
Self-citationDecomposition of Nonconvex Optimization via Bi-Level Distributed ALADIN
Engelmann, A., Jiang, Y., Houska, B., & Faulwasser, T. (2020) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2020.3005079 · Cited by 73
Dong, Z., Mao, S., Perc, M., Du, W., & Tang, Y. S. (2022) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2022.3216572 · Cited by 55
“As to EDP, counterparts of [18], [19] are proposed in [21], [22], lacking theoretical analysis for the linear convergence rates.”
InfluentialLinear convergence of primal–dual gradient methods and their performance in distributed optimization
Alghunaim, S. A., & Sayed, A. H. (2020) · Automatica · doi:10.1016/j.automatica.2020.109003 · Cited by 72
“Although, EXTRA and DIGing are traditional AL primal-dual methods, the analysis in this work does not cover these cases.”
BackgroundMethodInfluentialWalkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization
Mao, X., Yuan, K., Hu, Y., Gu, Y., Sayed, A. H., & Yin, W. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2983167 · Cited by 90
“This approach includes well-known algorithms such as diffusion [5], [6] and consensus [11], [12], distributed ADMM (D-ADMM) [13]–[15], EXTRA [16], PG-EXTRA [17], DIGing [18], exact diffusion [19], NIDS [20], and beyond.”
BackgroundMethodSelf-citationConsensus Control of a Class of Uncertain Nonlinear Multiagent Systems via Gradient-Based Algorithms
Li, R., & Yang, G. (2018) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2018.2819361 · Cited by 50
Lei, J., Chen, H.-F., & Fang, H. (2018) · SIAM Journal on Control and Optimization · doi:10.1137/16m1086133 · Cited by 51
Distributed Learning in Non-Convex Environments— Part II: Polynomial Escape From Saddle-Points
Vlaski, S., & Sayed, A. H. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3050840 · Cited by 54
A Fast Distributed Asynchronous Newton-Based Optimization Algorithm
Mansoori, F., & Wei, E. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2933607 · Cited by 60
Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
Li, H., Fang, C., Yin, W., & Lin, Z. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3018317 · Cited by 88
“EXTRA also uses the gradient tracking.”
BackgroundMethodInfluentialSelf-citationA new Zeno-free event-triggered scheme for robust distributed optimal coordination
Yu, H., & Chen, T. (2021) · Automatica · doi:10.1016/j.automatica.2021.109639 · Cited by 51
Supervised Learning Under Distributed Features
Ying, B., Yuan, K., & Sayed, A. H. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2881661 · Cited by 50
A Primal-Dual SGD Algorithm for Distributed Nonconvex Optimization
Yi, X., Zhang, S., Yang, T., Chai, T., & Johansson, K. H. (2022) · IEEE/CAA Journal of Automatica Sinica · doi:10.1109/jas.2022.105554 · Cited by 57
“These are two advantages since in existing studies obtaining linear convergence for distributed smooth optimization, e.g., [47]–[49], it is standard to assume (restricted) strong convexity, which is stronger than the P–Ł condition, and to use the convexity parameter.”
A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
Alghunaim, S. A., & Yuan, K. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3184770 · Cited by 67
A Linearly Convergent Distributed Nash Equilibrium Seeking Algorithm for Aggregative Games
Huang, S., Lei, J., & Hong, Y. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3154356 · Cited by 51
Rashid, M., & Nanzer, J. A. (2022) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2022.3213788 · Cited by 50
Li, H., Jin, B., & Yan, W. (2020) · Automatica · doi:10.1016/j.automatica.2020.109422 · Cited by 50
Li, W., Zeng, X., Liang, S., & Hong, Y. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3075666 · Cited by 56
Zeroth-order algorithms for stochastic distributed nonconvex optimization
Yi, X., Zhang, S., Yang, T., & Johansson, K. H. (2022) · Automatica · doi:10.1016/j.automatica.2022.110353 · Cited by 70
Edge-Based Stochastic Gradient Algorithm for Distributed Optimization
Wang, Z., & Li, H. (2019) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2019.2933177 · Cited by 49
“It reveals the superiority of the proposed algorithm in flexible edge weight selections compared with gradient tracking methods [19], [20], [24], [25] and saddle-point methods [34], [44].”
BackgroundMethodInfluentialA Comprehensive Survey on Training Acceleration for Large Machine Learning Models in IoT
Wang, H., Qu, Z., Zhou, Q., Zhang, H., Luo, B., Xu, W., Guo, S., & Li, R. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2021.3111624 · Cited by 65
A Linearly Convergent Proximal Gradient Algorithm for Decentralized OptimizationPreprint
Alghunaim, S. A., Yuan, K., & Sayed, A. H. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.07996 · Cited by 76
“(cid:50) Next we show that when R ( w ) = 0 , we can have a better upper bound for the dual step-size, which covers the EXTRA algorithm [1]. and the step-sizes satisfy Proof .”
BackgroundMethodInfluentialAn Event-Triggered Approach for Gradient Tracking in Consensus-Based Distributed Optimization
Gao, L., Deng, S., Li, H., & Li, C. (2021) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2021.3122927 · Cited by 51
Social Learning in Multi Agent Multi Armed Bandits
Sankararaman, A., Ganesh, A. J., & Shakkottai, S. (2019) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/3366701 · Cited by 108
Kajiyama, Y., Hayashi, N., & Takai, S. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2989281 · Cited by 47
“Shi et al. proposed a consensus-based first-order algorithm with a fixed stepsize and showed linear convergence for continuous and strongly convex functions [12].”
BackgroundA Primal-Dual Quasi-Newton Method for Exact Consensus Optimization
Eisen, M., Mokhtari, A., & Ribeiro, A. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2951216 · Cited by 52
Wang, D., Chen, M., & Wang, W. (2019) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2018.2890115 · Cited by 49
A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks
Pu, S. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9303917 · Cited by 60
Throughput-Optimal Topology Design for Cross-Silo Federated LearningPreprint
Marfoq, O., Xu, C., Neglia, G., & Vidal, R. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.12229 · Cited by 118
Chen, W., Wang, Z., Dong, H., Mao, J., & Liu, G. P. (2023) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2023.3321027 · Cited by 51
“In this article, the selection of κ ∈ ( 0 , ¯ κ ) follows from the work [15], [16], [42].”
MethodInfluentialAnalysis and Design of First-Order Distributed Optimization Algorithms Over Time-Varying Graphs
Sundararajan, A., Scoy, B. V., & Lessard, L. (2020) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2020.2988009 · Cited by 67
Learning-Driven Decentralized Machine Learning in Resource-Constrained Wireless Edge Computing
Meng, Z., Xu, H., Chen, M., Xu, Y., Zhao, Y., & Qiao, C. (2021) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom42981.2021.9488817 · Cited by 46
“For any given graph with a weight matrix P ( t ) , there exists a spectral norm ρ = (cid:13)(cid:13)(cid:13) E ( P T ( t ) P ( t )) , where 1 is the identity matrix. ρ < 1 guarantees the convergence of the model to a stationary point [11] [19].”
BackgroundDistributed Gradient Tracking for Unbalanced Optimization With Different Constraint Sets
Cheng, S., Liang, S., Fan, Y. C., & Hong, Y. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3192316 · Cited by 46
“As pointed out in [19], the row stochastic matrix brings the consensus of the decision variables and the column stochastic matrix brings an “optimal average value,” In [5], [20], and [21],theauthorshaveintroducedadditionaldynamicstolearnthegradi-ents of global objective functions.”
BackgroundMethodWang, D., Wang, Z., Wu, Z., & Wang, W. (2022) · Science China Information Sciences · doi:10.1007/s11432-020-3111-4 · Cited by 46
Liu, Y., Guo, L., Lu, C., Chai, Y., Gao, S., & Xu, B. (2019) · IEEE Access · doi:10.1109/access.2019.2912004 · Cited by 47
Decentralized Consensus Algorithm with Delayed and Stochastic Gradients
Sirb, B., & Ye, X. (2018) · SIAM Journal on Optimization · doi:10.1137/16m1081257 · Cited by 52
“A correction technique is developed for decentralized gradient descent with convergence rate as O (1 /T ) with constant step size in [34], which results in a saddle-point algorithm as pointed out in [24].”
Fenchel Dual Gradient Methods for Distributed Convex Optimization Over Time-Varying Networks
Wu, X., & Lu, J. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2901829 · Cited by 47
A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
Pu, S., Olshevsky, A., & Paschalidis, I. C. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3126253 · Cited by 72
“1) has been studied extensively in the literature under various distributed algorithms [50, 31, 32, 23, 17, 18, 45, 13, 41, 29, 52, 40], among which the distributed gradient descent (DGD) method proposed in [31] has drawn the greatest attention.”
BackgroundDecentralized Stochastic Optimization With Inherent Privacy Protection
Wang, Y., & Poor, H. V. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3174187 · Cited by 59
Differentially Private Distributed Algorithms for Aggregative Games With Guaranteed Convergence
Wang, Y., & Nedić, A. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3351068 · Cited by 49
Distributed Optimization Methods for Multi-Robot Systems: Part 1—A Tutorial [Tutorial]
Shorinwa, O., Halsted, T., Yu, J., & Schwager, M. (2024) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2024.3358718 · Cited by 90
Distributed Signal Processing and Optimization Based on In-Network Subspace Projections
Lorenzo, P. D., Barbarossa, S., & Sardellitti, S. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2981204 · Cited by 48
“In the sequel, proceeding as in [21], we will modify the DiSPO method in order to guarantee exact convergence also when using a constant step-size.”
MethodDecentralized Decision Making for the Restoration of Interdependent Networks
Talebiyan, H., & Dueñas‐Osorio, L. (2020) · ASCE-ASME Journal of Risk and Uncertainty in Engineering Systems Part A Civil Engineering · doi:10.1061/ajrua6.0001035 · Cited by 45
Differentially Private Distributed Resource Allocation via Deviation Tracking
Ding, T., Zhu, S., Chen, C., Xu, J., & Guan, X. (2021) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2021.3062985 · Cited by 41
Wang, Y., & Başar, T. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3212006 · Cited by 53
Kamath, G., Agnihotri, P., Valero, M., Sarker, K., & Song, W.-Z. (2016) · 2016 IEEE Global Communications Conference (GLOBECOM) · doi:10.1109/glocom.2016.7842181 · Cited by 42
Robust convergence analysis of distributed optimization algorithms
Sundararajan, A., Hu, B., & Lessard, L. (2017) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2017.8262874 · Cited by 39
Jin, B., Li, H., Yan, W., & Cao, M. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3021528 · Cited by 47
Accelerated $AB$/Push–Pull Methods for Distributed Optimization Over Time-Varying Directed Networks
Nguyen, D. T. A., Nguyen, D. T., & Nedić, A. (2023) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2023.3338236 · Cited by 63
Wang, P., Ren, W., & Duan, Z. (2018) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2018.2797805 · Cited by 39
Distributed Subgradient-Based Multiagent Optimization With More General Step Sizes
Wang, P., Lin, P., Ren, W., & Song, Y. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2763782 · Cited by 42
Revisiting EXTRA for Smooth Distributed Optimization
Li, H., & Lin, Z. (2020) · SIAM Journal on Optimization · doi:10.1137/18m122902x · Cited by 56
DiNNO: Distributed Neural Network Optimization for Multi-Robot Collaborative Learning
Yu, J., Vincent, J. A., & Schwager, M. (2022) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2022.3142402 · Cited by 58
“The problem of training neural networks in a distributed way using data aggregated from individual robots can be viewed as a specific instantiation of a distributed optimization problem.”
Fast Decentralized Nonconvex Finite-Sum Optimization with Recursive Variance Reduction
Xin, R., Khan, U. A., & Kar, S. (2022) · SIAM Journal on Optimization · doi:10.1137/20m1361158 · Cited by 68
“For example, a stochastic variant of EXTRA [36], Exact Diffusion [54], and NIDS [19], called D2 [40], removes the bounded dissimilarity assumption in DSGD based on a bias-correction principle.”
Decentralized Machine Learning Through Experience-Driven Method in Edge Networks
Xu, H., Chen, M., Meng, Z., Xu, Y., Wang, L., & Qiao, C. (2021) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2021.3118424 · Cited by 43
Distributed Zero-Order Algorithms for Nonconvex Multi-Agent optimization
Tang, Y., & Li, N. (2019) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2019.8919690 · Cited by 46
Distributed Optimization Methods for Multi-Robot Systems: Part 2—A Survey
Shorinwa, O., Halsted, T., Yu, J., & Schwager, M. (2024) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2024.3352852 · Cited by 67
Random Gradient Extrapolation for Distributed and Stochastic Optimization
Lan, G., & Zhou, Y. (2018) · SIAM Journal on Optimization · doi:10.1137/17m1157891 · Cited by 40
Hashemi, A., Acharya, A., Das, R., Vikalo, H., Sanghavi, S., & Dhillon, I. S. (2021) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2021.3138977 · Cited by 73
“In the decentralized setting under strong convexity (SC), without using techniques such as gradient tracking [18], DGD based FL schemes use either η = O ( 1 t ) to have O (1 /(cid:15) ) rounds of communication (e.g. Choco-GD or DGD [2], [11]), or a fixed stepsize (independent of T ) to achieve…”
Multiagent Fully Decentralized Value Function Learning With Linear Convergence Rates
Cassano, L., Yuan, K., & Sayed, A. H. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2995814 · Cited by 43
Liu, C., Li, H., & Shi, Y. (2020) · Automatica · doi:10.1016/j.automatica.2020.108834 · Cited by 45
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.