Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
Open accessThe DOI matches its Crossref record; 89 of the 89 references it cites were found in a registry or an index; 10 of the 34 sources its claims cite were checked for support.
Abstract
This paper considers the problem of distributed optimization over time-varying graphs. For the case of undirected graphs, we introduce a distributed algorithm, referred to as DIGing, based on a combination of a distributed inexact gradient method and a gradient tracking technique. The DIGing algorithm uses doubly stochastic mixing matrices and employs fixed step-sizes and, yet, drives all the agents' iterates to a global and consensual minimizer. When the graphs are directed, in which case the implementation of doubly stochastic mixing matrices is unrealistic, we construct an algorithm that incorporates the push-sum protocol into the DIGing structure, thus obtaining the Push-DIGing algorithm. Push-DIGing uses column stochastic matrices and fixed step-sizes, but it still converges to a global and consensual minimizer. Under the strong convexity assumption, we prove that the algorithms converge at R-linear (geometric) rates as long as the step-sizes do not exceed some upper bounds. We establish explicit estimates for the convergence rates. When the graph is undirected it shows that DIGing scales polynomially in the number of agents. We also provide some numerical experiments to demonstrate the efficacy of the proposed algorithms and to validate our theoretical findings.
Overview
CoChat Summary
TL;DR
The paper introduces DIGing for distributed optimization over time-varying undirected graphs and Push-DIGing for time-varying directed graphs, both using fixed step-sizes and gradient tracking. Under strong convexity and smoothness, it proves global R-linear (geometric) convergence and gives explicit rate bounds.
Key findings
- DIGing uses doubly stochastic mixing matrices and fixed step-sizes; under Assumptions 1, 4, and 5, it converges to the unique optimum at a global R-linear rate \(O(\lambda^k)\) for step-sizes \(\alpha \in (0, 1.5(1-\delta)^2 \bar{\mu} J_1]\).
- Push-DIGing incorporates the push-sum protocol with column stochastic matrices and fixed step-sizes; under Assumptions 4–7, it also converges at a global R-linear rate \(O(\lambda^k)\) for \(\alpha \in (0, 1.5(1-\delta)^2 \bar{\mu} J_2]\).
- For undirected graphs, Corollary 11 gives iteration complexity \(O(\tau^{-2} B^3 n^{4.5} \bar{\kappa}^{1.5} \ln(1/\varepsilon))\), polynomial in the number of agents \(n\). For lazy Metropolis mixing on time-invariant connected undirected graphs, Corollary 12 gives rate \(\lambda = 1 - 1/(161312\, n^{4.5} \bar{\kappa}^{1.5})\) and iteration complexity \(O(n^{4.5} \bar{\kappa}^{1.5} \ln(1/\varepsilon))\).
- Numerical experiments with \(n=12\), \(m_i=1\), \(p=3\), and Huber loss show DIGing and variants have R-linear rates, while the push-gradient method has only sublinear rate; DIGing-ATC is faster in iterations than DIGing but has higher per-iteration communication cost, and Push-DIGing can be as fast as DIGing-ATC at half communication cost per iteration.
Methods
- The paper studies distributed convex optimization \(\min \sum_{i=1}^n f_i(x)\) over time-varying undirected and directed graphs, assuming smoothness with Lipschitz gradients and strong convexity of at least one local function.
- It proposes DIGing: \(x(k+1)=W(k)x(k)-\alpha y(k)\), \(y(k+1)=W(k)y(k)+\nabla f(x(k+1))-\nabla f(x(k))\), and Push-DIGing, which adds push-sum variables \(u,v,V\) and uses column stochastic matrices.
- Convergence analysis uses the small-gain theorem with an ergodic norm and a cycle of arrows \(q \to z \to \check{y} \to \check{x} \to q\); numerical experiments compare push-gradient, DIGing, DIGing-ATC, and Push-DIGing on time-invariant directed, time-varying undirected, and time-varying directed graphs.
Limitations
- The paper states an open question is obtaining improved estimates on convergence rates, especially scaling with the number of agents \(n\), and extensions to local constraints and couplings among agents.
- Step-size selection requires agents to agree on common upper bounds on \(n\) and \(B\), plus lower \(\bar{\mu}\) and upper \(L\); the paper assumes all agents use the same step-size, though it notes uncoordinated step-sizes are possible in subsequent work.
- The paper states its bounds on step-sizes are often conservative and uses hand-optimized step-sizes in experiments; the numerical experiments use a small network of \(n=12\), so the empirical validation is limited in scale.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
9 Valid · 0 Not valid · 10 Not checked · 37 Own results and interpretations
The cited sources support only part of this claim — read each source’s verdict below.
In the paper
“This compares favorably to some of the existing literature, e.g., [70,76], which require detailed spectral information about the network for step-size selection.”
What the sources say
- Supportedcites [70] C. Xi and U. Khan, On the Linear Convergence of Distributed Optimization over Directed Graphs , preprint,arXiv:1510.02149, 2015. source
The part of the sentence this citation is offered for — that the cited work's step-size selection needs detailed spectral information about the network — is borne out by our copy: Theorem 1 (p. 13) sets α_min and α_max in terms of λ_min(M+M^⊤), d_- and d_∞, and the discussion after it (p. 14) states outright that 'the values of α and ᾱ need the knowledge of the network topology, which may not be available in a distributed manner,' flagging avoidance of that global knowledge as an open question. Section VI (p. 22) demonstrates the requirement in practice, computing λ_max/λ_min of H_i^⊤H_i, the degree constants and λ_min(M+M^⊤) to estimate the interval [9.6×10^-4, 0.26] before picking α = 0.1. The comparative framing ('compares favorably') is the citing authors' own conclusion and is not attributed to this source, so it is not judged here. (LLM, conf=0.85)
- Partly supportedcites [76] J. Zeng and W. Yin, ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks , preprint,arXiv:1511.02942, 2015. sourceExperimental — accuracy not yet measured
Theorem 4 (p. 8) gives a condition on the step size, and the discussion on p. 9 relates the convergence bound to eigenvalues of network-derived matrices. But p. 9 calls the step-size condition sufficient, not necessary, and §6.1 (p. 12) selects step sizes by hand. The paper therefore supports a spectral dependence in its theoretical bound, not the categorical claim that step-size selection requires detailed spectral information. (LLM, conf=0.79)
plain- 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
Every source the paper cites for this claim was checked and supports it.
In the 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) .”
What the sources say
- Supportedcites [62] matched to “EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization” (2015) source
The paper’s discussion of Proposition 2.1 (p. 6) says that, under null{I−W} = span{1}, a point satisfying its consensus and optimality conditions has identical rows that solve problem (1.1). Lemma 3.1’s proof (p. 9) identifies 1ᵀ∇f(x*) = 0 as the optimality condition. The citing proposition paraphrases those conditions and conclusion. (LLM, conf=0.92)
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
Every source the paper cites for this claim was checked and supports it.
In the paper
“While the subgradient-push eliminates the requirement of graph balancing [22], it suffers from a slow sublinear 2 convergence rate even for strongly convex smooth functions due to its employment of diminishing step-size [41].”
What the sources say
- Supportedcites [41] A. Nedić and A. Olshevsky, Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs , preprint, arXiv:1406.2075, 2014. source
The paper reports an O((ln t)/t) rate for strongly convex functions with Lipschitz gradients using an appropriately chosen diminishing step-size (main-result passage; page unavailable). This is sublinear, although the Introduction and Conclusion emphasize that it improves on the earlier O((ln t)/√t) rate and is close to the best achievable rate in the noisy setting; “slow” is the citing authors’ characterization. (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
Every source the paper cites for this claim was checked and supports it.
In the paper
“Assumption 2 is typical for many results in multi-agent coordination and distributed optimization [42]. It is much weaker than the assumption of every G un ( k ) being connected.”
What the sources say
- Supportedcites [42] matched to “Distributed Optimization Over Time-Varying Directed Graphs” (2015) source
In II. Problem, Algorithm and Main Results (p. 2), the paper calls its connectivity assumption typical and says it is considerably weaker than requiring each graph to be connected, because the necessary edges can appear over time. (LLM, conf=0.91)
plain- 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 result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“When the graph is undirected it shows that DIGing scales polynomially in the number of agents.”
- Also stated in: § ACHIEVING GEOMETRIC CONVERGENCE FOR DISTRIBUTED OPTIMIZATION OVER TIME-VARYING GRAPHS ∗ · p. 4 · plain
“Moreover, we show that the convergence rate of DIGing scales polynomially in the total number of agents in the network.”
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.
- Rests on 2 assumptions not shown here.
- Also stated in: § ACHIEVING GEOMETRIC CONVERGENCE FOR DISTRIBUTED OPTIMIZATION OVER TIME-VARYING GRAPHS ∗ · p. 4 · plain
25 more claims
Create a free account to see all 56 claims and to verify the 2 references still open.
- It may state two separate claims as one. 13
- Probably not a substantial claim. 14
- The quote only partly states this claim. 1
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 2: Push-DIGing · p. 21
“N out i ( k ) is the set of agents that can receive the information from agent i (in-neighbors of agent i ) at time k .”
§ Algorithm 2: Push-DIGing · p. 21
“N out i ( k ) = { j ∣ ∣ ( - → i, j ) ∈ A ( k ) }”
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: DIGing · p. 10
“the gradients are close to zero in the neighborhood of the optimal point”
§ ACHIEVING GEOMETRIC CONVERGENCE FOR DISTRIBUTED OPTIMIZATION OVER TIME-VARYING GRAPHS ∗ · p. 5
“not necessarily a point where ∇ f i ( x ) = 0 ∀ i”
Citations
Cites
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000016 · Cited by 17,075
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
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 2×
“References [60–62] use a difference structure to cancel the steady state error in decentralized gradient descent [47, 75], thereby developing the algorithm EXTRA and its proximal-gradient variant.”
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
Markov Chains and Mixing Times
Levin, D., Peres, Y., & Wilmer, E. (2008) · doi:10.1090/mbk/058 · Cited by 2,241
Distributed asynchronous deterministic and stochastic gradient optimization algorithms
Tsitsiklis, J., Bertsekas, D., & Athans, M. (1986) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1986.1104412 · Cited by 1,967
Gossip-based computation of aggregate information
Kempe, D., Dobra, A., & Gehrke, J. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238221 · Cited by 1,480 · cited 4×
“Instead, if every agent knows its out-degree, it is possible for the agents to construct a column stochastic matrix C and perform the following recursions with initialization u(0) = x(0) and v(0) = 1 to achieve the average (push-sum protocol [27]):”
BackgroundMethodInfluentialEXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
Shi, W., Ling, Q., Wu, G., & Yin, W. (2015) · SIAM Journal on Optimization · doi:10.1137/14096668x · Cited by 1,261
Self-citationDistributed 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
Self-citationDistributed 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 · cited 1×
“Some examples include distributed averaging [7,50,72], distributed spectrum sensing [1], formation control [49, 58], power system control [21, 55], statistical inference and learning [20, 45, 53].”
Background
Research works printed but not linked: 9
- Chen A., 2012, Allerton, 601
- Di Lorenzo P., 2015, Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 229
- Forero P., 2010, J. Mach. Learn. Res., 59, 1663
- Mokhtari A., 2016, J. Mach. Learn. Res., 17, 1
- Nedić A., 2008, UK, 3
- A. Olshevsky, Efficient Information Aggregation Strategies for Distributed Control and Signal Processing , Ph.D. thesis, Massachusetts Institute of Technology, 2010.
- Rabbat M., 2004, New York, 20
- Ram S., 2009, Proceedings of INFOCOM, 3001
- Sayed A., 2013, New York, 323
Cited by
Items 901–1,000 of 1,070
Consensus and Approximation-based Distribution Statistics in Network Systems
Li, Y., Jiao, Q., Wang, H., & He, J. (2021) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc50511.2021.9483081
“Note that the complexity can be reduced to O ( n log m max ε ) with additional assumptions [23].”
BackgroundAsymptotic Properties of $\mathcal{S}$-$\mathcal{AB}$ Method with Diminishing StepsizePreprint
Zhao, S., & Liu, Y. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2109.07981
“Compared with distributed gradient tracking method [24], AB/push-pull method utilizes a row stochastic matrix for mixing the decision variables and a column stochastic matrix for tracking the average gradients.”
MethodRan, L., Hu, J., Liu, H., & Li, H. (2021) · Chinese Control Conference (CCC) · doi:10.23919/ccc52363.2021.9550251
Distributed Gaussian Process Mapping for Robot Teams with Time-varying CommunicationPreprint
Di, J., Zobeidi, E., Koppel, A., et al. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.06401
“As established in [25], an important property of the Metropolis weight matrix is that Assumption 1 ensures Πt=τW t → 11 ⊤ n , i.”
BackgroundMethodInfluentialDistributed Randomized Block Stochastic Gradient Tracking MethodPreprint
Yousefian, F., Yevale, J., & Kaushik, H. D. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2110.06575
“Further, in [7], integrating the ideas from DIGing [16] and a fast incremental gradient method (SAGA) [3], S-DIGing algorithm is developed.”
BackgroundMethodDistributed algorithm for non-convex stochastic optimization with variance reduction.Preprint
Jiang, X., Zeng, X., Sun, J. Q., & Chen, J. (2021) · arXiv (Cornell University)
Distributed Methods with Stochastic Communication
Ananduta, W. (2021) · Springer theses · doi:10.1007/978-3-030-89803-8_5
Distributed multi-agent consensus under constraints
Qiu, Z. (2017) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/72344
Federated Learning with Incrementally Aggregated Gradients
Mitra, A., Jaafar, R. H., Pappas, G. J., & Hassani, H. (2021) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc45484.2021.9683443 · Cited by 3
Ran, L., Wang, C., Zheng, L., Li, H., & Wang, Z. (2022) · Optimal Control Applications and Methods · doi:10.1002/oca.2886
“+ ( M41 C + αM′41 C ) θC1 + αM 42 C θC2 + ( M43 C + αM′43 C +M′43 C ) θC3 + αM 44 C θC4, (42)”
Gradient-Tracking-basierte Lösung von Multi-Cluster-Spielen
Zimmermann, J., Tatarenko, T., Willert, V., et al. (2022) · at - Automatisierungstechnik · doi:10.1515/auto-2021-0106
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
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
Extended ADMM with Paillier Cryptosystem for Nonsmooth Decentralized Optimization
Wang, L., Shi, X., Guo, L., Yu, L., & Zhang, Y. (2022) · Lecture notes in electrical engineering · doi:10.1007/978-981-19-3998-3_28
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
“Such methods include EXTRA [4], DIGing [5], [6], NIDS [7], Exact Diffusion [8], SVL [9], DOGT [10], and Push-Pull [11] (and see [9] for other examples).”
MethodWang, D., Zhou, J., Zheng, W. X., et al. (2022) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc51059.2022.9992866
“To solve the DOP over weight-unbalanced directed communication topologies, in the discrete-time setting, push-sum distributed optimization algorithms [9], [16] and push-pull algorithms [17] were proposed.”
MethodEvent-Triggered 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_8
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
Accelerated Row-Stochastic Optimization over Directed Networks Based on Momentum Methods
任, 冬. (2023) · Advances in Applied Mathematics · doi:10.12677/aam.2023.123094
Wu, X., Sou, K. C., & Lu, J. (2023) · Optimization methods & software · doi:10.1080/10556788.2023.2189713
“It is a standard connectivity condition on time-varying networks, and is also considered in many existing works such as [1,6,9,10,12,15,17,18,20,24,26].”
BackgroundAn 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
D-SVM over networked systems with non-ideal linking conditions
Doostmohammadian, M., Aghasi, A., & Zarrabi, H. (2023) · Iran Journal of Computer Science · doi:10.1007/s42044-023-00146-9
“For this part, unlike existing literature with strong convexity condition [1,26,27,32,38,44], we only assume strict convexity (Assumption 1).”
BackgroundResultMalaspina, G., Jakovetić, D., & Krejić, N. (2023) · Optimization Letters · doi:10.1007/s11590-023-02011-x · Cited by 2
“The assumptions over the sequences {G} and {W }, which are the same hypotheses considered in [18], are stated below.”
InfluentialA Survey of Distributed Algorithms for Aggregate Games
Yang, K., & Song, R. (2023) · International Conference on Cyber-Energy Systems and Intelligent Energy (ICCSIE) · doi:10.1109/iccsie55183.2023.10175241
“The so-called dynamic tracking is that a group of players can follow the average value of some referenced inputs for gradient tracking, for example [30].”
BackgroundA conditionally constrained compound sub‐gradient method for distributed energy coordination
Xu, J., & Sun, S. (2023) · IET Generation Transmission & Distribution · doi:10.1049/gtd2.12912
Qi, Y., Yu, W., Wang, H., & Liu, H. (2023) · IEEE International Conference on Cyber Technology in Automation, Control, and Intelligent Systems · doi:10.1109/cyber59472.2023.10256579
Wang, C., Zhu, R., Wang, F., & Liu, Z. (2023) · Lecture notes in electrical engineering · doi:10.1007/978-981-99-6847-3_62
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
“…[33] discussed the power system problem on undirected networks, the authors 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…”
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
Moreau Envelope ADMM for Decentralized Weakly Convex Optimization
Mirzaeifard, R., Venkategowda, N. K. D., Jung, A., & Werner, S. (2023) · Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC) · doi:10.1109/apsipaasc58517.2023.10317303
Continuous-time min-max consensus protocol: A unified approach
Rezaei, V., & Khanmirza, E. (2023) · Mathematics and Computers in Simulation · doi:10.1016/j.matcom.2023.11.020
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
“Gradient tracking is another important tool to achieve linear convergence rates for decentralized optimization, which has been used to design several decentralized algorithms [13], [19], [26], [27], [28], [29].”
MethodLinear convergence of a primal-dual algorithm for distributed interval optimization
Wang, Y., Wang, J., Song, X., & Hu, Y. (2024) · Electronic Research Archive · doi:10.3934/era.2024041
“In fact, when local objective functions were strongly convex, the algorithms of [2, 26, 27] achieved linear convergence rates for the centralized and distributed counterparts.”
BackgroundDistributed 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
“As shown in [28], the adapt-then-combine strategy improved the performance of the gradient tracking strategy [29], [30].”
BackgroundAccelerated 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
“For example, fixed step size EXTRA [10], DIGing algorithm [11-12] based on gradient tracking technology and distributed inexact method, consensus theory [13-14], distributed gradient descent method [15-16], projected primal-dual distributed dynamical systems [17-18], second-order accelerated method…”
MethodBorkar, V. S. (2023) · Texts and readings in mathematics · doi:10.1007/978-981-99-8277-6_11
A Fast Distributed Stochastic Algorithm over Directed Networks
宫, 秀. (2024) · Advances in Applied Mathematics · doi:10.12677/aam.2024.132081
Distributed consensus protocols for cooperative decision-making
Zhang, H., Huang, C., Wang, Z., & Yan, H. (2024) · Elsevier eBooks · doi:10.1016/b978-0-44-321859-0.00012-8
(2024) · Elsevier eBooks · doi:10.1016/b978-0-44-321859-0.00025-6
Natural Gradient Primal-Dual Method for Decentralized Learning
Niwa, K., Ishii, H., Sawada, H., Fujino, A., Harada, N., & Yokota, R. (2024) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2024.3388948
“…recent popular algorithms may be (b) Stochastic Variance Reduction (SVR), including decentralized SCAFFOLD [6], Gradient Tracking (GT) [7], [8], GT-SVR [9], or (c) primal-dual formalism to solvetheconstrainedloss-summinimizationproblemsincluding…”
MethodLiu, D., Nian, X., & Li, F. (2024) · Systems & Control Letters · doi:10.1016/j.sysconle.2024.105872
Distributed Optimal Consensus of Second-order MASs over Directed Graphs*
Wang, D. (2024) · Youth Academic Annual Conference of Chinese Association of Automation (YAC) · doi:10.1109/yac63405.2024.10598607
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
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
Accelerated Design for Distributed Asynchronous Optimization
Zhang, Z. X., Yu, X. Y., Wang, Y., Cheng, S., & Fan, Y. C. (2024) · Chinese Control Conference (CCC) · doi:10.23919/ccc63176.2024.10662678
“We recall the small gain theorem from [24].”
MethodDecentralized 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
“To address this issue, algorithms using local historic iterative information, such as EXTRA [22], [23], gradient-tracking [24]–[26], and the proximal gradient primal-dual algorithm [14] have been proposed.”
MethodPrivacy-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
Hu, J., Guo, X., Li, W., et al. (2024) · International Conference on Electronic Engineering and Informatics (EEI) · doi:10.1109/eei63073.2024.10696139
“Since DeSSO-AD replaces the consensual aggregation process with the p - norm penalized approximation, it is more resilient in adverse conditions than decentralized algorithms [16]– [19].”
BackgroundMethodAccurate Decentralized Information Communication for Effective Decisions in Robotic Networks
Safwat, M., & Devasia, S. (2024) · IEEE/ASME Transactions on Mechatronics · doi:10.1109/tmech.2024.3477307
“For the special case when all agents have access to information, then methods such as dynamic average consensus [7] achieve good tracking of the overall average information and have been used in distributed optimization [14] and sensor fusion algorithms [15].”
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
Asynchronous Algorithms in Distributed Optimization Over Multi-Agent Network
You, K., & Du, Y. (2024) · Elsevier eBooks · doi:10.1016/b978-0-443-14081-5.00084-2
Robustified Distributed Average Consensus
Charalambous, T., Domínguez-García, A. D., & Hadjicostis, C. N. (2024) · Elsevier eBooks · doi:10.1016/b978-0-443-14081-5.00076-3 · Cited by 3
A Survey of Distributed Optimization
Yu, W., Zhu, Y., & Liu, H. (2024) · Elsevier eBooks · doi:10.1016/b978-0-443-14081-5.00077-5
Distributed Constrained Optimization with Uncoordinated Step Sizes: A Case Study on Ethylene Plant
Liu, B., Li, Z., & Du, W. (2024) · China Automation Congress (CAC) · doi:10.1109/cac63892.2024.10865107
Distributed Consensus, Optimization and Computation in Networked Systems
Yao, L. (2018) · University of North Texas Digital Library (University of North Texas) · doi:10.12794/metadc1404555
Cohesive-Tracking versus Fast-Convergence with Dynamic Average Consensus
Safwat, M., & Devasia, S. (2024) · Indian Control Conference · doi:10.1109/icc64753.2024.10883730
“…the time-varying average is relevant to applications such as: sensor fusion with distributed sensor networks [2], formation control in leaderless multi-robot coordination [3], gradient tracking in distributed optimization [4], and demand-response averaging in distributed resource allocation [5].”
On Linear Convergence of PI Consensus Algorithm under the Restricted Secant Inequality
Chakrabarti, K., & Baranwal, M. (2024) · Indian Control Conference · doi:10.1109/icc64753.2024.10883750 · Cited by 1
“Notable discrete-time algorithms that are built upon DGD include ADMM [12], EXTRA [13], DIGing [14], PI [2], APM-C [15], Mudag [16], Accelerated EXTRA [6], DAccGD [17], and ACC-SONATA [18].”
Tighter Analysis for Decentralized Stochastic Gradient Method: Impact of Data Homogeneity
Li, Q., & Wai, H.-T. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3545551 · Cited by 1
“An important class of variants includes the use of gradient tracking: Nedi´c et al. [23] combined the inexact gradient method with gradient tracking to develop the DIGing algorithm, Di Lorenzo et al. [24] developed the NEXT algorithm using gradient tracking for time-varying graph and analyzed its…”
MethodAchieving Local Consensus Over Compact Submanifolds
Hu, J., Zhang, J., & Deng, K. (2025) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2025.3545711 · Cited by 8
Estimation Network Design framework for efficient distributed optimization
Bianchi, M., & Grammatico, S. (2024) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc56724.2024.10885996
Accelerating Gradient Tracking with Periodic Global Averaging
Feng, S., & Jiang, X. (2024) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc56724.2024.10886594
“Thus, with a suitable design of the PGA period, GT-PGA improves the convergence rate of vanilla GT. Numerical experiments are conducted to support our theory, and simulation results reveal that the proposed GT-PGA accelerates practical convergence, especially when the network is sparse.”
Deep-Relative-Trust-Based Diffusion for Decentralized Deep Learning
Li, M., Fainman, A., & Vlaski, S. (2025) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp49660.2025.10889869
“Other strategies for decentralized optimization and learning, such as EXTRA [8] or Exact diffusion [9] rely on primal-dual constructions, while gradient-tracking based algorithms such as NEXT [10] or DIGing [11] rely on the dynamic consensus mechanism.”
Distributed Optimization With Compressed Communication
Xu, L., Yi, X., Shi, Y., Johansson, K. H., Chai, T., & Yang, T. (2025) · Elsevier eBooks · doi:10.1016/b978-0-443-14081-5.00130-6
Communication-Efficient and Privacy-Preserving Algorithms for Distributed Optimization
He, W., Yang, S., & Yang, Z. (2025) · Elsevier eBooks · doi:10.1016/b978-0-443-14081-5.00052-0
Distributed Policy Evaluation with Local Updates over Time-Varying Communication Network
Crespo, M., & Enyioha, C. (2025) · Conference on Information Sciences and Systems · doi:10.1109/ciss64860.2025.10944666
“Researchers in the distributed optimization literature have explored how to maintain convergence in such settings, demonstrating that by appropriately designing communication protocols, agents can achieve optimal solutions even when the network topology changes [12]–[14].”
Event–Triggered Distributed Average Tracking with False Data Injection Attacks
Chen, X., Qiu, Z., Zhuang, J., et al. (2025) · Unmanned Systems · doi:10.1142/s2301385026500378
Accelerated Nesterov Design for Distributed Optimization Over Directed Graphs
Zhang, Z., Yin, X., Fan, Y. C., & Cheng, S. (2025) · International Journal of Control Automation and Systems · doi:10.1007/s12555-024-0424-0 · Cited by 1
“Assumption 2 (Smoothness) : Remark 2: Assumptions 2 and 3 are standard conditions for achieving linear convergence when the first-order algorithms [15,29,36,38].”
InfluentialData Privacy in Multi-Agent Optimization Under Uncertainty
Margellos, K., Falsone, A., Garatti, S., & Prandini, M. (2025) · Elsevier eBooks · doi:10.1016/b978-0-443-14081-5.00170-7 · Cited by 1
BrainDiffU-Net: A Distributed Diffusion-Based U-Net for Brain Tumor Segmentation
Sharma, P., & Pradhan, P. M. (2024) · International Conference on Computer Theory and Applications (ICCTA) · doi:10.1109/iccta64612.2024.10974899
“Diffusion training operates in two key phases during each iteration: adaptation , in which each agent refines its model using its local dataset, and combination , where agents share their model updates with neighboring agents and integrate the received updates into their own models [17].”
Decentralized Online Dual Averaging Optimization Ensuring Differential Privacy and Expected Regret
Cheng, H., Lü, Q., Hu, J., et al. (2024) · International Conference on Neuromorphic Computing (ICNC) · doi:10.1109/icnc64304.2024.10987847
“For the decentralized offline algorithms, a number of notable works have emerged, including methods like [3], [4], [5], etc.”
Almost sure convergence of distributed optimization with imperfect information sharing
Reisizadeh, H., Gokhale, A., Touri, B., & Mohajer, S. (2025) · Automatica · doi:10.1016/j.automatica.2025.112391 · Cited by 5
Resilient Distributed Optimization
Kuwaranancharoen, K., Xin, L., & Sundaram, S. (2025) · Elsevier eBooks · doi:10.1016/b978-0-443-14081-5.00072-6
Modular Distributed Nonconvex Learning With Error Feedback
Carnevale, G., & Bastianello, N. (2025) · IEEE Control Systems Letters · doi:10.1109/lcsys.2025.3582677
“The main classes of distributed optimization algorithms are based on gradient tracking [6] and Alternating Direction Method of Multipliers ( ADMM ) [7].”
A variance‐reduced distributed stochastic momentum algorithm over directed networks
Gong, X., Gao, J., & Liu, X. (2025) · Asian Journal of Control · doi:10.1002/asjc.3775 · Cited by 1
Liu, S., Wang, D., & Chen, M. (2025) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2025.107865
Li, C., & Ma, Y. (2025) · Symmetry · doi:10.3390/sym17071159 · Cited by 1
Distributed online stochastic gradient tracking
Fu, K., Fu, X., Chen, Y., & Li, T. (2025) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2025.107902
Analysis of DGD for decentralized high-dimensional statistical models: beyond the least squares
Gao, J., & Lian, H. (2025) · Analysis and Applications · doi:10.1142/s0219530525500459
Event-triggered decentralized gradient tracking algorithms for stochastic optimization in networks
Lü, Q., Liao, X., Li, H., et al. (2025) · Elsevier eBooks · doi:10.1016/b978-0-44-333337-8.00010-x
Variance-reduced decentralized projection algorithms for constrained optimization in networks
Lü, Q., Liao, X., Li, H., Deng, S., Li, Y., & Zhang, K. (2025) · Elsevier eBooks · doi:10.1016/b978-0-44-333337-8.00009-3
A New Paradigm for Decentralized Nonconvex Optimization with Improved Convergence
Phuong, T. T., & Phong, L. T. (2025) · Lecture notes on data engineering and communications technologies · doi:10.1007/978-3-031-96099-4_29
Decentralized Coordination in Robotic Swarms: An Adaptive Strategy for Shared Resource Management
Fedele, G., & D’Alfonso, L. (2025) · IEEE International Workshop on Metrology for Living Environment (MetroLivEnv) · doi:10.1109/metrolivenv64961.2025.11107050
“However, these methods typically require strong assumptions regarding network connectivity, global knowledge of resource constraints, or synchronized updates among agents [12].”
Distributed Personalized Optimization on Riemannian Manifolds with Gradient Tracking
Zhao, Y., Huang, Y., Zhang, H., & Xu, J. (2025) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc63710.2025.11107888
“Building on the success of gradient-tracking-based approaches in Euclidean space [1]–[3], which relies on auxiliary variables for tracking the overall gradient, a decentralized Riemannian gradient tracking algorithm was presented in [19], which requires diminishing step sizes for convergence.”
Variance-Reduced Gradient Estimator for Nonconvex Zeroth-Order Distributed Optimization
Mu, H., Tang, Y., & Li, Z. (2025) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc63710.2025.11107900 · Cited by 1
Warm-Up Gradient Tracking for Distributed Nonconvex Optimization with Data Heterogeneity
Zhang, Z., Huang, Y., & Xu, J. (2025) · International Conference on Control and Automation · doi:10.1109/icca65672.2025.11129713
“In particular, Nedich et al. [8] proposed the DIGing algorithm, which improves the convergence performance of DGD by employing a fixed stepsize, achieving global optimality at a linear rate.”
Distributed Newton Optimization with ADMM-Based Consensus
Carnevale, G., Bastianello, N., Notarstefano, G., et al. (2025) · Lecture notes in control and information sciences - proceedings · doi:10.1007/978-3-031-83191-1_20
Chen, Y., Lin, P., & Zhang, B. (2025) · Computational Statistics · doi:10.1007/s00180-025-01667-6
Hu, Z. (2025) · Chinese Control Conference (CCC) · doi:10.23919/ccc64809.2025.11178293
“The authors of [19] consider an event-triggered approach to reduce unnecessary communication processes during collaboration.”
A Unified Framework for Robust Distributed Optimization Under Bounded Disturbances
Liu, C., Huang, R., Chen, W.-H., Du, W., & Shi, Y. (2025) · Chinese Control Conference (CCC) · doi:10.23919/ccc64809.2025.11178647
“Every sensor i knows its location r i , i ∈ [10] , and collects 15 measurements.”
InfluentialYuan, R., Zhao, Z., Liu, J., et al. (2025) · Chinese Control Conference (CCC) · doi:10.23919/ccc64809.2025.11179365
“Over the years, extensive research has been conducted on integrating co-operative control with optimization, with advancements in both discrete-time algorithms [1, 2] and continuous-time algorithms [3, 4].”
Asynchronous Distributed Composite Optimization via Publish-Subscribe Paradigm
Huang, R., Liu, C., Nanavati, R. V., Liu, C., & Chen, W.-H. (2025) · International Conference on Automation and Computing (ICAC) · doi:10.1109/icac65379.2025.11196425
Metadata
- Authors
- Nedić, A., Olshevsky, A., & Shi, W.
- Affiliations
- Boston University (US)
- Arizona State University (US)
- Venue
- SIAM Journal on Optimization
- Published
- 2017-01
- Volume
- 27
- Issue
- 4
- Pages
- 2597-2633
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W2963649943
- Cited by
- 1,069
- References
- 38
- Citations by year
- 2026: 95 · 2025: 147 · 2024: 130 · 2023: 124 · 2022: 118 · 2021: 114 · 2020: 138 · 2019: 106 · 2018: 64 · 2017: 29
- FWCI
- 46.51
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- SIAM Journal on Optimization (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- U.S. Air Force (AF FA95501510394)
- Office of Naval Research (N00014-12-1-0998)
- National Science Foundation (CNS 15-44953)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Keywords
- distributed optimization, dynamic graphs, geometric convergence, R-linear convergence, gradient tracking, strong convexity, fixed step size, undirected graphs, directed graphs
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 and gpt-6-sol).
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.