EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
Open accessThe DOI matches its Crossref record; 46 of the 46 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] K. Yuan, Q. Ling, and W. Yin, On the Convergence of Decentralized Gradient Descent , preprint, arXiv:1310.7063, 2013. 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] K. Yuan, Q. Ling, and W. Yin, On the Convergence of Decentralized Gradient Descent , preprint, arXiv:1310.7063, 2013. 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] D. Davis and W. Yin, Convergence Rate Analysis of Several Splitting Systems , preprint, arXiv:1406.4834, 2014. 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: 6
- I. Chen, Fast Distributed First-Order Methods , Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 2012.
- Forero P., 2010, J. Mach. Learn. Res., 59, 1663
- B. Johansson, On Distributed Optimization in Networked Systems , Ph.D. thesis, KTH, Stockholm, Sweden, 2008.
- Ling Q., 2012, NJ, 2925
- Nedic A., 2013, NJ, 6855
- J. Tsitsiklis, Problems in Decentralized Decision Making and Computation , Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1984.
Cited by
Items 401–500 of 1,315
Secure Distributed Optimization Under Gradient Attacks
Yu, S., & Kar, S. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3277211 · Cited by 26
Distributed Online Private Learning of Convex Nondecomposable Objectives
Cheng, H., Liao, X., & Li, H. (2023) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2023.3329832 · Cited by 18
Shi, X., Mu, C., Huang, D., et al. (2024) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2024.107002 · Cited by 15
Asynchronous Decentralized Framework for Unit Commitment in Power Systems
Ramanan, P., Yildirim, M., Chow, E., & Gebraeel, N. (2017) · Procedia Computer Science · doi:10.1016/j.procs.2017.05.038 · Cited by 18
FADE: Fast and Asymptotically Efficient Distributed Estimator for Dynamic Networks
Simões, A., & Xavier, J. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2901355 · Cited by 15
“The literature is too vast to discuss at length here, so we point the reader to references [2]–[14], a cross-section of representative work.”
A Distributed Stochastic Proximal-Gradient Algorithm for Composite Optimization
Niu, Y., Li, H., Wang, Z., Lü, Q., Xia, D., & Ji, L. (2021) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2021.3065653 · Cited by 17
“D ISTRIBUTED computing as a parallel processing framework has recently sparked increasing interest, largely thanks to the dramatic advances in promising communication [17], data storage [1], and computation technologies [7].”
InfluentialADACHI, T., Hayashi, N., & Takai, S. (2021) · IET Control Theory and Applications · doi:10.1049/cth2.12127 · Cited by 18
Improving the Transient Times for Distributed Stochastic Gradient Methods
Huang, K., & Pu, S. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3201141 · Cited by 28
“We study the following algorithm adapted from EXTRA [28], Exact Diffusion [37], NIDS [11] and D 2 [30], where the main characteristics of EDAS lie in the diminishing stepsize policy Algorithm 2.1 EDAS (Exact Diffusion with Adaptive Stepsizes) for some θ > 0 and m > 0.”
InfluentialA Robust Consensus-Based Economic Dispatch Strategy Under DoS Attack
Zhang, Z., Yue, D., Dou, C., et al. (2019) · IEEE International Conference on Industrial Cyber-Physical Systems (ICPS) · doi:10.1109/icphys.2019.8780286 · Cited by 15
Wang, D., Chen, Y., Gupta, V., & Lian, J. (2020) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2020.03.035 · Cited by 15
Privacy-Preserving Distributed Analytics in Fog-Enabled IoT Systems
Zhao, L. (2020) · Sensors · doi:10.3390/s20216153 · Cited by 17
Distributed Randomized Kaczmarz and Applications to Seismic Imaging in Sensor Network
Kamath, G., Ramanan, P., & Song, W. (2015) · International Conference on Distributed Computing in Smart Systems and the Internet of Things (DCOSS-IoT) · doi:10.1109/dcoss.2015.27 · Cited by 21
Asynchronous Decentralized Optimization in Directed NetworksPreprint
Zhang, J., & You, K. (2019) · arXiv (Cornell University) · Cited by 17
A Non-Asymptotic Analysis of Network Independence for Distributed Stochastic Gradient DescentPreprint
Olshevsky, A., Paschalidis, I. C., & Pu, S. (2019) · arXiv (Cornell University) · Cited by 13
Projected Gradient Method for Decentralized Optimization over Time-Varying NetworksPreprint
Rogozin, A., & Gasnikov, A. V. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.08527 · Cited by 21
Li, H., Lin, Z., & Fang, Y. (2020) · arXiv (Cornell University) · Cited by 14
Distributed Aggregative Optimization Algorithm for Solving Multirobot Formation Problem
Huang, J., Yang, C., Wu, S., & Liu, Q. (2025) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2025.3552468 · Cited by 20
“Consequently, directly applying establisheddistributedoptimizationmethods,suchasdistributed subgradientmethods[12]andEXTRA[14],tosolveproblem (1)becomeschallenging.”
Understanding Implicit Regularization in Over-Parameterized Single Index Model
Fan, J., Yang, Z., & Yu, M. (2022) · Journal of the American Statistical Association · doi:10.1080/01621459.2022.2044824 · Cited by 35
Nabla fractional distributed optimization algorithms over undirected/directed graphs
Hong, X., Wei, Y., Zhou, S., & Yue, D. (2024) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2024.01.013 · Cited by 18
Distributed Optimisation With Linear Equality and Inequality Constraints Using PDMM
Heusdens, R. R., & Zhang, G. (2024) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2024.3375597 · Cited by 20
Distributed Unbalanced Optimization Design Over Nonidentical Constraints
Huang, Q., Fan, Y. C., & Cheng, S. (2024) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2024.3374765 · Cited by 14
Chen, T.-Y., Chen, W., Guo, X.-Q., Gong, Y., & Zhang, J. (2024) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2024.3380389 · Cited by 16
Collaborative Resource Allocation over a Hybrid Cloud Center and Edge Server Network
Huang, H. H. H., Ling, Q. H., Shi, W., & Wang, J. W. J. (2017) · Journal of Computational Mathematics · doi:10.4208/jcm.1608-m2016-0561 · Cited by 15
Self-citationInferring Private Information in Wireless Sensor Networks
Burbano-L., D. A., George, J., Freeman, R. A., et al. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8683597 · Cited by 14
COLA: Communication-censored Linearized ADMM for Decentralized Consensus Optimization
Li, W., Liu, Y., Tian, Z., & Ling, Q. H. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8682575 · Cited by 11
Self-citationSubgradient averaging for multi-agent optimisation with different constraint sets
Romao, L. B. R. R., Margellos, K., Notarstefano, G., & Papachristodoulou, A. (2021) · Automatica · doi:10.1016/j.automatica.2021.109738 · Cited by 16
Hayashi, N., Sugiura, T., Kajiyama, Y., & Takai, S. (2019) · IET Control Theory and Applications · doi:10.1049/iet-cta.2019.0377 · Cited by 16
“Shi et al. proposed an exact first-order algorithm which achieves linear convergence for restricted strongly convex functions [12].”
BackgroundNested Distributed Gradient Methods with Adaptive Quantized Communication
Berahas, A. S., Iakovidou, C., & Wei, E. (2019) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc40024.2019.9029541 · Cited by 15
A General Framework of Exact Primal-Dual First-Order Algorithms for Distributed Optimization
Mansoori, F., & Wei, E. (2019) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc40024.2019.9029902 · Cited by 14
Gradient-free distributed optimization with exact convergence
Pang, Y., & Hu, G. (2022) · Automatica · doi:10.1016/j.automatica.2022.110474 · Cited by 15
Li, B., Li, Z., & Chi, Y. (2022) · SIAM Journal on Mathematics of Data Science · doi:10.1137/21m1450677 · Cited by 26
“2: initialization: set x Set the new parameter estimate x ( t ) = u ( t − 1) ,S .”
A Linear Algorithm for Quantized Event-Triggered Optimization Over Directed Networks
Yang, Y., Shi, L., & He, W. (2022) · IEEE/CAA Journal of Automatica Sinica · doi:10.1109/jas.2022.105614 · Cited by 14
Distributed hybrid optimization for multi-agent systems
Tan, X., Yang, Y., He, W., Cao, J., & Huang, T. (2022) · Science China Technological Sciences · doi:10.1007/s11431-022-2060-7 · Cited by 15
Decentralized double stochastic averaging gradient
Mokhtari, A., & Ribeiro, A. (2015) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2015.7421158 · Cited by 12
Computational Convergence Analysis of Distributed Optimization Algorithms for Directed Graphs
Zhang, S., Yi, X., George, J., & Yang, T. (2019) · International Conference on Control and Automation · doi:10.1109/icca.2019.8899565 · Cited by 14
Distributed fixed point method for solving systems of linear algebraic equations
Jakovetić, D., Krejić, N., Jerinkić, N. K., et al. (2021) · Automatica · doi:10.1016/j.automatica.2021.109924 · Cited by 14
Stochastic Proximal Gradient Consensus Over Random NetworksPreprint
Hong, M., & Chang, T. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.08905 · Cited by 14
Communication-Efficient Distributed Strongly Convex Stochastic Optimization: Non-Asymptotic RatesPreprint
Sahu, A. K., Jakovetić, D., Bajović, D., & Kar, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.02920 · Cited by 18
A Second-Order Proximal Algorithm for Consensus Optimization
Wu, X., Qu, Z., & Lu, J. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2996205 · Cited by 16
Decentralized Local Stochastic Extra-Gradient for Variational Inequalities
Beznosikov, A. N., Dvurechenskii, P., Koloskova, A., Samokhin, V., Stich, S. U., & Gasnikov, A. V. (2022) · neural information processing systems · doi:10.52202/068431-2762 · Cited by 53
“There have been tremendous advances recently in the development, design, and understanding of decentralized training schemes [71, 95, 86, 54, 84, 92, 90, 94, 23, 81, 50].”
Priority-Considered Load Shedding in Economic Dispatch: Distributed Optimization Approach
Fitri, I. R., & Kim, J. (2022) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2022.3231185 · Cited by 13
Distributed Banach-Picard Iteration: Application to Distributed Parameter Estimation and PCA
Andrade, F. L., Figueiredo, M. A. T., & Xavier, J. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3239806 · Cited by 14
A Distributed Nesterov-Like Gradient Tracking Algorithm for Composite Constrained Optimization
Zheng, L., Li, H., Li, J. Q., Wang, Z., Lü, Q., Shi, Y., Wang, H., Dong, T., Ji, L., & Xia, D. (2023) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2023.3239698 · Cited by 17
“PG-EXTRA [27], a proximal-gradient variant of EXTRA [28], uses a novel approach to diminish the state error resulting from distributed gradient descent.”
BackgroundOptimized Gradient Tracking for Decentralized Online Learning
Sharma, S. D., & Rajawat, K. (2024) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2024.3366437 · Cited by 17
Graph and Distributed Extensions of the Douglas–Rachford Method
Bredies, K., Chenchene, E., & Naldi, E. (2024) · SIAM Journal on Optimization · doi:10.1137/22m1535097 · Cited by 41
Distributed Optimization With Asynchronous Computation and Event-Triggered Communication
Dong, Z., Jin, Y., Mao, S., Ren, W., Du, W., & Tang, Y. S. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3449140 · Cited by 15
On the Performance of Exact Diffusion over Adaptive Networks
Yuan, K., Alghunaim, S. A., Ying, B., & Sayed, A. H. (2019) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc40024.2019.9029537 · Cited by 10
“In addition to exact diffusion, there exist other bias-correction methods such as EXTRA [12], ESOM [13], NIDS [14], and gradient-tracking methods such as Aug-DGM [15], NEXT/SONATA [16], [17], DIGing [18], [19], and push-pull methods [20], [21].”
MethodDistributed Optimization with Gradient Descent and Quantized Communication
Rikos, A. I., Jiang, W., Charalambous, T., & Johansson, K. H. (2023) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2023.10.100 · Cited by 14
Distributed Photometric Bundle Adjustment
Demmel, N., Gao, M., Laude, E., Wu, T. T., & Cremers, D. (2020) · International Conference on 3D Vision (3DV) · doi:10.1109/3dv50981.2020.00024 · Cited by 14
“The former could be addressed in the future by adaptive per-variable penalty weight schedules (similar to [33]) and the latter by exploring decentralized consensus optimization [32, 24, 23].”
BackgroundDistributed Stochastic Gradient Tracking MethodsPreprint
Pu, S., & Nedić, A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.11454 · Cited by 13
A Decentralized Proximal Point-type Method for Saddle Point ProblemsPreprint
Liu, W., Mokhtari, A., Ozdaglar, A., Pattathil, S., Shen, Z., & Zheng, N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.14380 · Cited by 32
Communication-efficient hierarchical distributed optimization for multi-agent policy evaluation
Ren, J., Haupt, J., & Guo, Z. (2020) · Journal of Computational Science · doi:10.1016/j.jocs.2020.101280 · Cited by 13
Convergence Analysis of Distributed Gradient Descent Algorithms With One and Two Momentum Terms
Liu, B., Chai, L., & Yi, J. (2022) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2022.3218663 · Cited by 16
Neurodynamic approaches for multi-agent distributed optimization
Guo, L., Korovin, I., Gorbachev, S. V., Shi, X., Gorbacheva, N., & Cao, J. (2023) · Neural Networks · doi:10.1016/j.neunet.2023.11.025 · Cited by 13
An enhanced gradient-tracking bound for distributed online stochastic convex optimization
Alghunaim, S. A., & Yuan, K. (2023) · Signal Processing · doi:10.1016/j.sigpro.2023.109345 · Cited by 15
Accelerated Distributed Optimization Algorithm With Malicious Nodes
Zhang, S., Liu, Z., Wen, G., & Wang, Y. (2023) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2023.3342165 · Cited by 15
“However, all the aforementioned distributed acceleration optimization algorithms [14], [15], [16] require the corresponding transition matrix to be symmetric and doubly stochastic.”
BackgroundMethodAEDFL: Efficient Asynchronous Decentralized Federated Learning with Heterogeneous Devices
Liu, J., Che, T., Zhou, Y., Jin, R., Dai, H., Dou, D., & Valduriez, P. (2024) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611978032.95 · Cited by 31
Liao, Z., Wang, S., Shi, J., et al. (2024) · ISA Transactions · doi:10.1016/j.isatra.2024.04.015 · Cited by 12
Xu, L., Yi, X., Deng, C., Shi, Y., Chai, T., & Yang, T. (2024) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2024.3384924 · Cited by 16
A proximal gradient algorithm for decentralized nondifferentiable optimization
Shi, W., Ling, Q. H., Wu, G., & Yin, W. (2015) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2015.7178514 · Cited by 10
Self-citationMokhtari, A., Ling, Q. H., & Ribeiro, A. (2014) · Cited by 12
Self-citationA decentralized quasi-Newton method for dual formulations of consensus optimization
Eisen, M., Mokhtari, A., & Ribeiro, A. (2016) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798550 · Cited by 16
Fenchel dual gradient methods for distributed convex optimization over time-varying networks
Wu, X., & Lu, J. (2017) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2017.8264079 · Cited by 12
Distributed Signal Recovery Based on In-network Subspace Projections
Lorenzo, P. D., Barbarossa, S., & Sardellitti, S. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8682719 · Cited by 11
Adaptive online distributed optimization in dynamic environments
Nazari, P., Khorram, E., & Tarzanagh, D. A. (2019) · Optimization methods & software · doi:10.1080/10556788.2019.1637433 · Cited by 14
Zeroth-order Feedback Optimization for Cooperative Multi-Agent Systems
Tang, Y., Ren, Z., & Li, N. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9304302 · Cited by 14
Liu, C., Zhou, Z., Pei, J., Zhang, Y., & Shi, Y. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3209951 · Cited by 15
Hu, J., Chen, G., Li, H., Shen, Z., & Zhang, W. (2022) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2022.3225229 · Cited by 13
Distributed Random Reshuffling Over Networks
Huang, K., Li, X., Milzarek, A., Pu, S., & Qiu, J. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3262181 · Cited by 16
Distributed Saddle Point Problems for Strongly Concave-Convex Functions
Qureshi, M. I., & Khan, U. A. (2023) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2023.3317807 · Cited by 17
Distributed Optimization Over Networks
Nedić, A. (2018) · Lecture notes in mathematics · doi:10.1007/978-3-319-97142-1_1 · Cited by 13
Distributed Proximal Splitting Algorithms with Rates and Acceleration
Condat, L., Malinovsky, G., & Richtárik, P. (2022) · Frontiers in Signal Processing · doi:10.3389/frsip.2021.776825 · Cited by 12
Asynchronous Decentralized Accelerated Stochastic Gradient Descent
Lan, G., & Zhou, Y. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3080256 · Cited by 19
Zhang, M., Zhou, Y., Ge, Q., Zheng, R., & Wu, Q. (2021) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2021.3112691 · Cited by 12
Implicit Tracking-Based Distributed Constraint-Coupled Optimization
Li, J., & Su, H. (2022) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2022.3203486 · Cited by 17
Mokhtari, A., Ling, Q. H., & Ribeiro, A. (2014) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2014.7094740 · Cited by 18
“The most popular alternatives are decentralized gradient descent (DGD) [6]–[9], distributed implementations of the alternating direction method of multipliers [3], [10]–[12], and decentralized dual averaging (DDA) [13].”
BackgroundSelf-citationOn Centralized and Distributed Mirror Descent: Convergence Analysis Using Quadratic Constraints
Sun, Y., Fazlyab, M., & Shahrampour, S. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3230767 · Cited by 12
“Of the two related works above, EXTRA [14] is of particular relevance to our algorithm.”
BackgroundMethodResultInfluentialChen, Z., & Li, N. (2022) · IEEE/CAA Journal of Automatica Sinica · doi:10.1109/jas.2022.105992 · Cited by 12
Private Learning on Networks: Part IIPreprint
Gade, S., & Vaidya, N. H. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1703.09185 · Cited by 13
Li, Z., & Yan, M. (2017) · arXiv (Cornell University) · Cited by 13
Sun, H., Lu, S., & Hong, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.05857 · Cited by 11
IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian MethodPreprint
Arjevani, Y., Bruna, J., Can, B., Gürbüzbalaban, M., Jegelka, S., & Lin, H. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.06733 · Cited by 22
A Second-Order Primal–Dual Dynamics for Set Constrained Distributed Optimization Problems
Tao, M., Guo, L., Cao, J., et al. (2023) · IEEE Transactions on Circuits & Systems II Express Briefs · doi:10.1109/tcsii.2023.3324187 · Cited by 11
A New Regularized Consensus Perspective for Distributed Optimization
Ye, M., Ding, L., Xu, S., et al. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3378170 · Cited by 11
An empirical comparison of multi-agent optimization algorithms
Assran, M., & Rabbat, M. (2017) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2017.8309024 · Cited by 10
On the Local Linear Rate of Consensus on the Stiefel Manifold
Chen, S., Garcia, A., Hong, M., & Shahrampour, S. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3330735 · Cited by 28
Gang, A., Xiang, B., & Bajwa, W. U. (2021) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2021.3122297 · Cited by 12
A Universal Decomposition for Distributed Optimization Algorithms
Scoy, B. V., & Lessard, L. (2022) · IEEE Control Systems Letters · doi:10.1109/lcsys.2022.3182640 · Cited by 15
Decentralized federated domain generalization with cluster alignment for fault diagnosis
Xu, D., Jia, M., Chen, T., Liu, Y., Chai, T., & Yang, T. (2024) · Control Engineering Practice · doi:10.1016/j.conengprac.2024.105951 · Cited by 13
Distributed Maximum Likelihood Using Dynamic Average Consensus
George, J. (2018) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2018.8461529 · Cited by 10
A Proximal ADMM for Decentralized Composite Optimization
Wang, B., Jiang, H., Fang, J., & Duan, H. (2018) · IEEE Signal Processing Letters · doi:10.1109/lsp.2018.2841648 · Cited by 13
On the Convergence of Distributed Subgradient Methods under Quantization
Doan, T. T., Maguluri, S. T., & Romberg, J. (2018) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2018.8636036 · Cited by 14
“Distributed algorithms for these problems have received much attention in recent years, mostly focusing on three widely-studied algorithms, namely, the alternating direction method of multipliers (ADMM) [1], [11], [22], [23], distributed dual methods (mirror descent/dual averaging) [6], [7], [25], and distributed (sub…”
MethodPan, T., Liu, J., & Wang, J. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i02.5523 · Cited by 19
A Unifying Approximate Method of Multipliers for Distributed Composite Optimization
Wu, X., & Lu, J. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3173171 · Cited by 21
“As [22] assumes W̃ W and Null(W̃ −W ) = span(1), Assumption 2.”
BackgroundMethodInfluentialGuo, L., Shi, X., Cao, J., & Wang, Z. (2022) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3208086 · Cited by 12
Distributed Smooth and Strongly Convex Optimization with Inexact Dual Methods
Fazlyab, M., Paternain, S., Ribeiro, A., & Preciado, V. M. (2018) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2018.8431049 · Cited by 11
Optimization over time-varying directed graphs with row and column-stochastic matricesPreprint
Saadatniaki, F., Xin, R., & Khan, U. A. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.07393 · Cited by 11
An introduction to decentralized stochastic optimization with gradient trackingPreprint
Xin, R., Kar, S., & Khan, U. A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.09648 · Cited by 9
Distributed Adaptive Newton Methods with Globally Superlinear ConvergencePreprint
Zhang, J., You, K., & Başar, T. (2020) · arXiv (Cornell University) · Cited by 11
Li, B., Cen, S., Chen, Y., & Chi, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.05844 · Cited by 134
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.