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 1,101–1,200 of 1,315
Primal-dual optimization methods for large-scale and distributed data analytics.Preprint
Jakovetić, D., Bajović, D., Xavier, J., & Moura, J. M. F. (2019) · arXiv (Cornell University)
Convergence Rates of Distributed Two-Time-Scale Gradient Methods under Random Quantization
Doan, T. T., Maguluri, S. T., & Romberg, J. (2019) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2019.12.192
Schnelle, verteilte Optimierungsmethoden und spieltheoretische Ansätze in vernetzten Systemen
Tatarenko, T. (2020) · at - Automatisierungstechnik · doi:10.1515/auto-2019-0080
Accelerated Distributed Optimization over Directed Graphs with Row and Column-Stochastic Matrices
Hu, J., Zhu, Y., Li, H., & Wang, Z. (2019) · IEEE Symposium Series on Computational Intelligence (SSCI) · doi:10.1109/ssci44817.2019.9002658
Event-triggered Broadcasting for Distributed Smooth Optimization
Liu, C., Li, H., Shi, Y., & Xu, D. (2019) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc40024.2019.9029758 · Cited by 1
A Robust Gradient Tracking Method for Distributed Optimization over Directed NetworksPreprint
Pu, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.13980
A Penalty Alternating Direction Method of Multipliers for Decentralized Composite Optimization
Zhang, J., So, A. M., & Ling, Q. H. (2020) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp40776.2020.9053138 · Cited by 1
Self-citationOperator Sliding and Decentralized Optimization
Lan, G. (2020) · Springer series in the data sciences · doi:10.1007/978-3-030-39568-1_8
Accelerated Parallel Algorithms
Lin, Z., Li, H., & Fang, C. (2020) · Springer eBooks · doi:10.1007/978-981-15-2910-8_6
Malaspina, G., Jakovetić, D., & Krejić, N. (2020) · arXiv (Cornell University)
Distributed Multi-agent Video Fast-forwardingPreprint
Lan, S., Wang, Z., Roy–Chowdhury, A. K., et al. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.04437
Distributed Networked Real-time LearningPreprint
García, A., Wang, L., Huang, J., et al. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.04103
Online Supervised Learning with Distributed Features over Multiagent System
An, X., He, B., Hu, C., & Liu, B. (2020) · Complexity · doi:10.1155/2020/8830359
Linear Convergence of Distributed Mirror Descent with Integral Feedback for Strongly Convex ProblemsPreprint
Sun, Y., & Shahrampour, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.12233
Distributed Subgradient Algorithm for Multi-agent Optimization with Uncoordinated Dynamic Stepsizes
Ren, X., Li, D., Xi, Y., & Shao, H. (2020) · International Conference on Control and Automation · doi:10.1109/icca51439.2020.9264511
A distributed methodology for approximate uniform global minimum sharing
Bin, M., & Parisini, T. (2021) · Automatica · doi:10.1016/j.automatica.2021.109777
A Robust Decentralized Multi-Sources Joint Power Spectra Separation and DOA Estimation Algorithm
Li, L., Chen, X., Wang, J., et al. (2020) · International Conference on Wireless Communications and Signal Processing (WCSP) · doi:10.1109/wcsp49889.2020.9299812
“Note that based on some effective algorithms [9], (cid:6) Y (cid:17) (cid:18)(cid:18) (cid:18)(cid:18) n,f can be exchanged and obtained at each receiver, and the normalized data n can then be calculated without FC.”
MethodAccelerated Distributed Optimization over Digraphs with Stochastic Matrices
Wang, H., Li, H., & Zhou, B. (2021) · Springer eBooks · doi:10.1007/978-981-33-4528-7_4
Distributed Networked Learning with Correlated DataPreprint
Hong, L., García, A., & Eksin, C. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.12783
“Hence, our model and the algorithm relates to decentralized convex optimization [16–20] and the recent work on finding the best common linear model in convex machine learning problems [21].”
MethodLin, Y., Shames, I., & Nešić, D. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.07953
Newton Method over Networks is Fast up to the Statistical PrecisionPreprint
Daneshmand, A., Scutari, G., Dvurechensky, P. E., & Gasnikov, A. V. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.06780 · Cited by 9
Xiang, B., Gang, A., & Bajwa, W. U. (2021) · arXiv (Cornell University)
Combining ADMM and tracking over networks for distributed constraint-coupled optimization
Falsone, A., Notarnicola, I., Notarstefano, G., & Prandini, M. (2020) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2020.12.380
Gradient-free distributed optimization and nash equilibrium seeking
Pang, Y. (2020) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/143354
Distributed Alternating Direction Method of Multipliers for Linearly Constrained Optimization
Niu, K., Zhou, M., Abdallah, C. T., & Hayajneh, M. (2021) · International Multi-Conference on Systems, Signals & Devices (SSD) · doi:10.1109/ssd52085.2021.9429350
Liu, C., Zhou, Z., Pei, J., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.14075
Gradient-Consensus Method for Distributed Optimization in Directed NetworksPreprint
Khatana, V., Saraswat, G., Patel, S., & Salapaka, M. V. (2019) · arXiv (Cornell University) · Cited by 1
Distributed smooth optimisation with event-triggered proportional-integral algorithms
Yao, L., Wei, Y., & Fu, S. (2021) · International Journal of Control · doi:10.1080/00207179.2021.1970816
Ran, L., Hu, J., Liu, H., & Li, H. (2021) · Chinese Control Conference (CCC) · doi:10.23919/ccc52363.2021.9550251
“sumed to be a general case of existing consensus problems [1, 4, 11, 12, 13, 20, 21, 24, 25, 26].”
BackgroundMethodBFGS-ADMM for Large-Scale Distributed OptimizationPreprint
Li, Y., Gong, Y., Freris, N. M., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2109.14804
A Primal-Dual Algorithm for Distributed Stochastic Optimization with Equality Constraints
Du, K., & Chen, X. (2021) · Chinese Control Conference (CCC) · doi:10.23919/ccc52363.2021.9549801
Distributed Randomized Block Stochastic Gradient Tracking MethodPreprint
Yousefian, F., Yevale, J., & Kaushik, H. D. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.06575
Rao, A. A., & Wai, H.-T. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.04523
Distributed algorithm for non-convex stochastic optimization with variance reduction.Preprint
Jiang, X., Zeng, X., Sun, J. Q., & Chen, J. (2021) · arXiv (Cornell University)
Quantized Primal-Dual Algorithms for Network Optimization with Linear ConvergencePreprint
Chen, Z., Liang, S., Li, L., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.08180
Distributed Forward-Backward Methods without Central CoordinationPreprint
Artacho, F. J. A., Malitsky, Y., Tam, M. K., et al. (2021) · arXiv (Cornell University)
Ran, L., Wang, C., Zheng, L., Li, H., & Wang, Z. (2022) · Optimal Control Applications and Methods · doi:10.1002/oca.2886
Distributed optimization methods for N-cluster games
Tatarenko, T., & Zimmermann, J. (2022) · at - Automatisierungstechnik · doi:10.1515/auto-2021-0137
On the Primal-Dual Method of Multipliers and its Applications
O'Connor, M. (2018) · Open Access Victoria University of Wellington | Te Herenga Waka (Figshare) · doi:10.26686/wgtn.17134829.v1
Time-varying dual accelerated gradient ascent: A fast network optimization algorithm
Monifi, E., & Mahdavi‐Amiri, N. (2022) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2022.03.014
An Accelerated Algorithm for Distributed Optimization with Barzilai-Borwein Step SizesPreprint
Zhang, X., Liu, S., & Zhao, N. (2022) · SSRN Electronic Journal · doi:10.2139/ssrn.4072692
Distributed Multiagent Systems
Mahmoud, M., & Karaki, B. J. (2022) · Studies in systems, decision and control · doi:10.1007/978-3-030-90940-6_2
Fast ADMM algorithm with efficient communication for distributed optimization of multi-agent systems
Cao, S., Jiang, X., Chi, M., & Zhang, X. (2021) · China Automation Congress (CAC) · doi:10.1109/cac53003.2021.9728441
“In recent years, the research on the the convergence of the algorithm and the convergence rate of the algorithm has become saturated, such as [5] [9].”
BackgroundConsensus and Diffusion for Multi-Hop Distributed Optimization and Machine LearningPreprint
Liao, H., Wu, M., Jin, G., Tan, L., Yang, R., & Xiao, Y. (2022) · SSRN Electronic Journal · doi:10.2139/ssrn.4145292
Lin, Z., Li, H., & Fang, C. (2022) · Springer eBooks · doi:10.1007/978-981-16-9840-8_1 · Cited by 1
Sampling-based Distributed Hybrid Optimization for Multi-agent Systems
Tan, X., & Cao, J. (2022) · Asian Control Conference (ASCC) · doi:10.23919/ascc56756.2022.9828085
Tian, H., & Zhu, W. Q. (2022) · Lecture notes in electrical engineering · doi:10.1007/978-981-19-3998-3_103
Distributed Composite Optimization for Multi-agent Systems with Asynchrony
Li, H., Hu, J., Ran, L., Wang, Z., Lü, Q., Du, Z., & Huang, T. (2022) · Studies in systems, decision and control · doi:10.1007/978-3-030-99776-2_7
Proximal Methods for Self-Healing and Exact Distributed Convex Optimization Extended abstract
Freeman, R. A. (2022) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton49937.2022.9929367
Decentralized Multi-Agent Policy Evaluation Over Directed Graphs
Lin, Q., & Ling, Q. H. (2022) · Chinese Control Conference (CCC) · doi:10.23919/ccc55666.2022.9902191
Self-citationThe Best of Both Worlds: Distributed PCA That is Both Exact and Communication Efficient
Gang, A., & Bajwa, W. U. (2022) · European Signal Processing Conference (EUSIPCO) · doi:10.23919/eusipco55093.2022.9909543 · Cited by 1
Distributed Suboptimal Model Predictive Control with Minimal Information Exchange
Jané-Soneira, P., Giesler, A., Pfeifer, M., et al. (2022) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc51059.2022.9993364
“In this work, we propose a distributed MPC algorithm for unconstrained linear systems coupled through the inputs based on a novel class of distributed optimization algorithms proposed in [20], [21].”
MethodDistributed Relatively Smooth Optimization
Jegnell, S., & Vlaski, S. (2022) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc51059.2022.9992936 · Cited by 1
Projection Algorithms for Distributed Stochastic Optimization
Lü, Q., Liao, X., Li, H., Deng, S., & Gao, S. (2022) · Wireless networks · doi:10.1007/978-981-19-8559-1_2
Event-Triggered Acceleration Algorithms for Distributed Stochastic Optimization
Lü, Q., Liao, X., Li, H., Deng, S., & Gao, S. (2022) · Wireless networks · doi:10.1007/978-981-19-8559-1_5
Accelerated Algorithms for Distributed Convex Optimization
Lü, Q., Liao, X., Li, H., Deng, S., & Gao, S. (2022) · Wireless networks · doi:10.1007/978-981-19-8559-1_1
Primal–Dual Algorithms for Distributed Economic Dispatch
Lü, Q., Liao, X., Li, H., Deng, S., & Gao, S. (2022) · Wireless networks · doi:10.1007/978-981-19-8559-1_7
Proximal Algorithms for Distributed Coupled Optimization
Lü, Q., Liao, X., Li, H., Deng, S., & Gao, S. (2022) · Wireless networks · doi:10.1007/978-981-19-8559-1_3
Edge-based event-triggered distributed inexact gradient descent for convex optimization
Luo, D., Xiong, M., Zhang, B., et al. (2022) · China Automation Congress (CAC) · doi:10.1109/cac57257.2022.10055550
“Up to now, there are many methods for dealing with distributed optimization problems [1], while the distributed gradient descent (DGD) method is commonly used [5], which requires the exact gradient computation in actual operation.”
MethodAccelerated Row-Stochastic Optimization over Directed Networks Based on Momentum Methods
任, 冬. (2023) · Advances in Applied Mathematics · doi:10.12677/aam.2023.123094
Decentralized Multiobjective Optimization Algorithms
Blondin, M. J. (2022) · Springer eBooks · doi:10.1007/978-3-030-54621-2_797-1
An accelerated distributed method with inexact model of relative smoothness and strong convexity
Zhang, X., Liu, S., & Zhao, N. (2023) · IET Signal Processing · doi:10.1049/sil2.12199
Gao, W., Xie, Y., & Ren, H. (2023) · Optimal Control Applications and Methods · doi:10.1002/oca.3000
Robust Network Topologies for Distributed Learning
Wang, C., & Vlaski, S. (2023) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp49357.2023.10094739 · Cited by 1
Malaspina, G., Jakovetić, D., & Krejić, N. (2023) · Optimization Letters · doi:10.1007/s11590-023-02011-x · Cited by 2
Consensus and Diffusion for First-Order Distributed Optimization Over Multi-Hop Network
Wu, M., Liao, H., Tan, L., Jin, G., Zhong, L., Xiao, Y., & Wang, Z. (2023) · IEEE Access · doi:10.1109/access.2023.3297112
A conditionally constrained compound sub‐gradient method for distributed energy coordination
Xu, J., & Sun, S. (2023) · IET Generation Transmission & Distribution · doi:10.1049/gtd2.12912
Constrained distributed online convex optimization with bandit feedback for unbalanced digraphs
Tada, K., Hayashi, N., & Takai, S. (2023) · IET Control Theory and Applications · doi:10.1049/cth2.12548
A Bayesian Framework for Online Nonconvex Optimization over Distributed Processing Networks
Shi, Z., Zheng, Y., & Eryılmaz, A. (2023) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom53939.2023.10228879
Wang, H. (2023) · Numerical Algorithms · doi:10.1007/s11075-023-01650-6 · Cited by 1
“W is doubly stochastic, i.e., W is nonnegative and W Decentralized algorithms require agents over the network to interchange information according to the mixing matrix that has a few typical choices (refer [2, 28] for more details).”
Distributed Optimization-Based Formation Control: A Dynamic Event-Triggered Approach
Yu, H., Yang, J., & Chen, T. (2023) · Chinese Control Conference (CCC) · doi:10.23919/ccc58697.2023.10239883
Meng, X., & Mei, J. (2023) · Chinese Control Conference (CCC) · doi:10.23919/ccc58697.2023.10239849
A comprehensive experimental comparison between federated and centralized learningPreprint
Garst, S. J. F., Dekker, J., & Reinders, M. J. T. (2023) · Research Square · doi:10.21203/rs.3.rs-3223559/v1
A projected decentralized variance-reduction algorithm for constrained optimization problems
Deng, S., Gao, S., Lü, Q., Li, Y., & Li, H. (2023) · Neural Computing and Applications · doi:10.1007/s00521-023-09067-x
“…in [35] considered a novel gradient estimation scheme, the authors in [34, 36] considered the time-varying graph and directed graph, the authors in [37] considered uncoordinated step-sizes for local optimization, and the authors in [38] considered a synchronous gradient-based algorithm, etc.”
Decentralized Stochastic Sharpness-Aware Minimization AlgorithmPreprint
Chen, S., Deng, X., Xu, D., et al. (2023) · SSRN Electronic Journal · doi:10.2139/ssrn.4613604
A Stochastic Gradient-Based Projection Algorithm for Distributed Constrained Optimization
Zhang, K., Gao, S., Chen, Y., Zheng, Z., & Lü, Q. (2023) · Lecture notes in computer science · doi:10.1007/978-981-99-8079-6_28
Finite-Time Consensus Dual Algorithm for Distributed Optimization over Digraphs
Jiang, W., & Charalambous, T. (2023) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2023.10.1083
DINE: Decentralized Inexact Newton With Exact Linear Convergence Rate
Ye, H., He, S., & Chang, X. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3336175
Distributed optimization with unconstrained polynomial objective function
Meng, H., & Li, T. (2023) · Chinese Control and Decision Conference (CCDC) · doi:10.1109/ccdc58219.2023.10327272
Distributed Dual Averaging for Composite OptimizationPreprint
Wu, P., Lu, H., Liu, Z., & Heyan, H. (2023) · SSRN Electronic Journal · doi:10.2139/ssrn.4663056
Distributed Stochastic Optimization with Compression for Non-Strongly Convex Objectives
Li, X., & Xu, Y. (2023) · Computer Modeling in Engineering & Sciences · doi:10.32604/cmes.2023.043247
Distributed Zeroth-order Optimization Over Directed Graphs
Zhao, F. (2023) · Youth Academic Annual Conference of Chinese Association of Automation (YAC) · doi:10.1109/yac59482.2023.10401358
Distributed Second-Order Method with Diffusion Strategy
Qu, Z., Li, X., Li, L., & Hong, Y. (2023) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/smc53992.2023.10394381 · Cited by 1
Aminian, B., & Varagnolo, D. (2023) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/smc53992.2023.10394323
Accelerated Dynamical Approaches for a Class of Distributed Optimization with Set Constraints
Wang, Y., Mei, X., & Jiang, H. (2023) · International Conference on New Trends in Computational Intelligence (NTCI) · doi:10.1109/ntci60157.2023.10403724
Chen, B., Yang, J., Lu, W., Pedrycz, W., & Sun, C. (2024) · Journal of Circuits Systems and Computers · doi:10.1142/s0218126624502220
Randomized Gradient-Free Mirror Descent Algorithm for Distributed Online Optimization
Hua, Y., Yang, Y., Wang, J., et al. (2023) · China Automation Congress (CAC) · doi:10.1109/cac59555.2023.10450774
Distributed accelerated gradient methods with restart under quadratic growth condition
Sharma, C., Narayanan, V., & Balamurugan, P. (2024) · Journal of Global Optimization · doi:10.1007/s10898-024-01395-z
Privacy Preserving Distributed Optimization via Paillier Encryption and Randomness Injection
Cheng, X., Gao, H. B., Zhi, Y., & Zhang, S. (2024) · Lecture notes in electrical engineering · doi:10.1007/978-981-97-3324-8_23
Distributed Optimization on Marix-Weighted NetworksPreprint
Cui, Y., Ji, Z., Liu, Y., et al. (2024) · doi:10.22541/au.171904799.91365564/v1
Linear convergence of event‐triggered distributed optimization with metric subregularity condition
Yu, X., Cheng, S., Qiu, J., & Fan, Y. C. (2024) · Asian Journal of Control · doi:10.1002/asjc.3467
“To achieve a faster convergence rate, [34] proposed the famous EXTRA with a linear convergence rate.”
InfluentialWu, X., & Fu, J. (2024) · Youth Academic Annual Conference of Chinese Association of Automation (YAC) · doi:10.1109/yac63405.2024.10598812
Distributed Time-Varying Optimization with Equality Constraints
Yang, Z., Ma, J., & Xu, X. (2024) · International Conference on Control and Automation · doi:10.1109/icca62789.2024.10591882 · Cited by 1
Distributed sparsity constrained optimization over the Stiefel manifold
Qu, W., Chen, H., Xiu, X.-C., & Liu, W.-Q. (2024) · Neurocomputing · doi:10.1016/j.neucom.2024.128267 · Cited by 2
Heterogeneous Distributed Subgradient
Lin, Y., Gamarra, M., & Liu, J. (2024) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc60939.2024.10645037
A Mixing-Accelerated Primal-Dual Proximal Algorithm for Distributed Nonconvex Optimization
Ou, Z., Qiu, C., Wang, D., & Jie, L. (2024) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc60939.2024.10644289
On f-Consensus Problems Solvable via Distributed Convex Optimization Methods
Yu, S., & Huang, C. (2024) · Chinese Control Conference (CCC) · doi:10.23919/ccc63176.2024.10662494
Decentralized Douglas-Rachford Splitting Methods for Smooth Optimization over Compact Submanifolds
Deng, K., Hu, J., & Wang, H. (2024) · Journal of Computational Mathematics · doi:10.4208/jcm.2407-m2023-0282 · Cited by 7
Privacy-Preserving Algorithms in Distributed Optimization Problems
Huang, L., Su, R., Chen, X., & Wu, J. (2024) · IntechOpen eBooks · doi:10.5772/intechopen.1006864 · Cited by 1
An accelerated decentralized stochastic optimization algorithm with inexact model
Zhang, X., Liu, S., & Zhao, N. (2024) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2024.116383
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.