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 101–200 of 1,070
Distributed Nash Equilibrium Seeking in Consistency-Constrained Multicoalition Games
Zhou, J., Lv, Y., Wen, G., et al. (2022) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2022.3155687 · Cited by 52
“This means that ∑ni m=1 ψ im ij plays the role of tracking τij(∂gi/∂yi)(y), which is similar to the distributed gradient tracking technique in distributed optimization [18].”
MethodDecentralized Accelerated Gradient Methods With Increasing Penalty Parameters
Li, H., Fang, C., Yin, W., & Lin, Z. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3018317 · Cited by 88
“The first type of methods [7], [17]–[19] rely on tracking differences of gradients, which keep a variable to estimate the average gradient and use this estimation in the gradient descent step.”
MethodSupervised Learning Under Distributed Features
Ying, B., Yuan, K., & Sayed, A. H. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2881661 · Cited by 50
A Primal-Dual SGD Algorithm for Distributed Nonconvex Optimization
Yi, X., Zhang, S., Yang, T., Chai, T., & Johansson, K. H. (2022) · IEEE/CAA Journal of Automatica Sinica · doi:10.1109/jas.2022.105554 · Cited by 57
A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
Alghunaim, S. A., & Yuan, K. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3184770 · Cited by 67
“There exists many works that study decentralized optimization methods under deterministic settings (full knowledge of gradients) – see [9], [11], [19], [28]–[33] and references therein.”
BackgroundMethodCharacterizing Trust and Resilience in Distributed Consensus for Cyberphysical Systems
Yemini, M., Nedić, A., Goldsmith, A. J., & Gil, S. (2021) · IEEE Transactions on Robotics · doi:10.1109/tro.2021.3088054 · Cited by 71
Self-citationWang, X., Teel, A. R., Liu, K., & Sun, X. (2019) · Automatica · doi:10.1016/j.automatica.2019.108607 · Cited by 51
Li, W., Zeng, X., Liang, S., & Hong, Y. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3075666 · Cited by 56
Edge-Based Stochastic Gradient Algorithm for Distributed Optimization
Wang, Z., & Li, H. (2019) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2019.2933177 · Cited by 49
“It reveals the superiority of the proposed algorithm in flexible edge weight selections compared with gradient tracking methods [19], [20], [24], [25] and saddle-point methods [34], [44].”
BackgroundMethodInfluentialA Linearly Convergent Proximal Gradient Algorithm for Decentralized OptimizationPreprint
Alghunaim, S. A., Yuan, K., & Sayed, A. H. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.07996 · Cited by 76
“Other works established linear convergence for simpler implementations including EXTRA [15], gradient tracking methods [26, 27], exact diffusion [28], NIDS [40], and others.”
MethodYu, W., Liu, H., Zheng, W. X., & Zhu, Y. (2021) · Automatica · doi:10.1016/j.automatica.2021.109899 · Cited by 53
An Event-Triggered Approach for Gradient Tracking in Consensus-Based Distributed Optimization
Gao, L., Deng, S., Li, H., & Li, C. (2021) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2021.3122927 · Cited by 51
Quantized Distributed Gradient Tracking Algorithm With Linear Convergence in Directed Networks
Xiong, Y., Wu, L., You, K., & Xie, L. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3219289 · Cited by 53
Kajiyama, Y., Hayashi, N., & Takai, S. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2989281 · Cited by 47
“considered a distributed algorithm to achieve linear convergence over time-varying networks [13].”
BackgroundZou, Y., Huang, B., & Meng, Z. (2021) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2021.3068352 · Cited by 48
Wang, D., Yin, J., & Wang, W. (2019) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2018.2890140 · Cited by 47
“Nedi´c et al. [20] proposed a distributed inexact gradient tracking method over time-varying general undirected/unbalanced digraphs to solve the smooth optimization problem and the unbalanced digraph is described by column-stochastic matrices.”
BackgroundMethodA Novel Multiagent Neurodynamic Approach to Constrained Distributed Convex Optimization
Ma, L., & Bian, W. (2019) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2019.2895885 · Cited by 47
“Nedi´c et al. [21] considered the distributed optimization with a time-varying graph.”
BackgroundA Robust Gradient Tracking Method for Distributed Optimization over Directed Networks
Pu, S. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9303917 · Cited by 60
“It is worth noting that the robust gradient tracking technique employed by R-Push-Pull, i.e., using sk and sk+1−sk to track the aggregated history gradients and the average gradient at step k respectively, can also be applied to other gradient tracking based methods such as Push-DIGing/ADDOPT [23], [45].”
MethodInfluentialThroughput-Optimal Topology Design for Cross-Silo Federated LearningPreprint
Marfoq, O., Xu, C., Neglia, G., & Vidal, R. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.12229 · Cited by 117
“[76] Angelia Nedic, Alex Olshevsky, and Wei Shi.”
BackgroundMethodAnalysis and Design of First-Order Distributed Optimization Algorithms Over Time-Varying Graphs
Sundararajan, A., Scoy, B. V., & Lessard, L. (2020) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2020.2988009 · Cited by 67
“Works that consider directed or time varying graphs typically make weaker assumptions, such as a joint spectrum property or B-connectedness [15].”
BackgroundMethodInfluentialDistributed Gradient Tracking for Unbalanced Optimization With Different Constraint Sets
Cheng, S., Liang, S., Fan, Y. C., & Hong, Y. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3192316 · Cited by 46
“As pointed out in [19], the row stochastic matrix brings the consensus of the decision variables and the column stochastic matrix brings an “optimal average value,” In [5], [20], and [21],theauthorshaveintroducedadditionaldynamicstolearnthegradi-ents of global objective functions.”
BackgroundMethodInfluentialFenchel Dual Gradient Methods for Distributed Convex Optimization Over Time-Varying Networks
Wu, X., & Lu, J. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2901829 · Cited by 44
“The convergence rates lead to an evaluable iteration complexity for attaining any given accuracy, which has better scalability with respect to network size and time B to reach connectivity than the algorithms in [10]–[12].”
BackgroundMethodInfluentialA Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
Pu, S., Olshevsky, A., & Paschalidis, I. C. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3126253 · Cited by 72
“incur noises from various sources such as approximation error and modeling and discretization errors. Problem (1.1) has been studied extensively in the literature under various distributed algorithms [42, 25, 26, 19, 15, 16, 38, 11, 34, 23, 44, 33], among which the distributed gradient descent (DGD) method proposed in…”
BackgroundInfluentialSelf-citationDistributed Optimization Methods for Multi-Robot Systems: Part 1—A Tutorial [Tutorial]
Shorinwa, O., Halsted, T., Yu, J., & Schwager, M. (2024) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2024.3358718 · Cited by 90
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning
Elgabli, A., Park, J., Bedi, A. S., Bennis, M., & Aggarwal, V. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.00047 · Cited by 42
“variables to its neighboring nodes per iteration and achieves O(1= p k) convergence rate. In contrast to that, in D-GADMM, only primal variables are shared with neighbors at each iteration. Finally, (Nedic et al., 2017) proposed an algorithm that achieves a linear convergence speed but for strongly convex functions on…”
BackgroundDifferentially Private Distributed Resource Allocation via Deviation Tracking
Ding, T., Zhu, S., Chen, C., Xu, J., & Guan, X. (2021) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2021.3062985 · Cited by 41
“In this paper, we consider more general functions, i.e., strongly convex functions with Lipschitz gradients, which are standard assumptions and widely applied in distributed algorithms for smooth functions [29]–[33].”
MethodZhang, K., Yang, Z., Liu, H., Zhang, T., & Başar, T. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3049345 · Cited by 76
“For the setting with a timevarying communication network, which is a general scenario in decentralized optimization, several recent work Nedic et al. (2017); Tatarenko and Touri (2017); Hong and Chang (2017) can apply.”
MethodAccelerated $AB$/Push–Pull Methods for Distributed Optimization Over Time-Varying Directed Networks
Nguyen, D. T. A., Nguyen, D. T., & Nedić, A. (2023) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2023.3338236 · Cited by 61
“Algorithms such as ADD-OPT [13] and Push-DIGing [14] further improve the convergence rate by incorporating the push-sum protocol with a gradient estimation approach.”
MethodInfluentialSelf-citationWang, P., Ren, W., & Duan, Z. (2018) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2018.2797805 · Cited by 39
“Remark 13: The slow convergence of the method in [17], [18] may result from the small step size in this example, which is 3.”
BackgroundMethodResultInfluentialOptimal Convergence Rates for Convex Distributed Optimization in Networks
Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., & Massoulié, L. (2019) · HAL · Cited by 100
Revisiting EXTRA for Smooth Distributed Optimization
Li, H., & Lin, Z. (2020) · SIAM Journal on Optimization · doi:10.1137/18m122902x · Cited by 56
“EXTRA (Shi et al., 2015a) and the gradient tracking based method (Xu et al., 2015; Qu & Li, 2017a) (also called DIGing in (Nedić et al., 2017)) can be seen as a trade-off between communications and computations, which need equal numbers of communications and gradient computations at each iteration.”
MethodByzantine-robust decentralized stochastic optimization over static and time-varying networks
Peng, J., Li, W., & Ling, Q. H. (2021) · Signal Processing · doi:10.1016/j.sigpro.2021.108020 · Cited by 59
Fast Decentralized Nonconvex Finite-Sum Optimization with Recursive Variance Reduction
Xin, R., Khan, U. A., & Kar, S. (2022) · SIAM Journal on Optimization · doi:10.1137/20m1361158 · Cited by 68
“A dynamic fusion mechanism, called gradient tracking [10,15,23,32,51], removes ζ(2) by tracking the average of the local gradient estimators in GT-SARAH to learn the global gradient at each node.”
Distributed Support Vector Machines Over Dynamic Balanced Directed Networks
Doostmohammadian, M., Aghasi, A., Charalambous, T., & Khan, U. A. (2021) · IEEE Control Systems Letters · doi:10.1109/lcsys.2021.3086388 · Cited by 46
Distributed Zero-Order Algorithms for Nonconvex Multi-Agent optimization
Tang, Y., & Li, N. (2019) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2019.8919690 · Cited by 46
“gradient tracking O ( 1 t ) [14] O ([ 1− c(1−ρ)(2) (μ L )3 2 ]t) [4] (convex)”
MethodWang, D., Fang, X., Wan, Y., Zhou, J., & Wen, G. (2022) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2022.3176895 · Cited by 40
“…algorithm [6], a distributed projected subgradient algorithm [7], an augmented distributed gradient algorithm [10], DIGing [11], [12], an augmented Lagrange stochastic gradient algorithm [13], push-sum distributed optimization algorithms [11], [14]–[16], and push-pull algorithms [17], [18].”
BackgroundMethodDistributed Optimization Methods for Multi-Robot Systems: Part 2—A Survey
Shorinwa, O., Halsted, T., Yu, J., & Schwager, M. (2024) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2024.3352852 · Cited by 66
“The DIGing algorithm [46], [47], whose update equations are shown in Algorithm 2, is one such similar method that extends the faster convergence properties of EXTRA to the domain of directed and time-varying graphs.”
InfluentialHashemi, A., Acharya, A., Das, R., Vikalo, H., Sanghavi, S., & Dhillon, I. S. (2021) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2021.3138977 · Cited by 72
“However, the union of these graphs over all time steps is going to be connected with high probability and therefore decentralized learning methods are expected to converge [31], [32].”
BackgroundLinear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse GradientsPreprint
Mitra, A., Jaafar, R. H., Pappas, G. J., & Hassani, H. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.07053 · Cited by 203
On the Convergence of Decentralized Federated Learning Under Imperfect Information Sharing
Chellapandi, V. P., Upadhyay, A., Hashemi, A., & Żak, S. H. (2023) · IEEE Control Systems Letters · doi:10.1109/lcsys.2023.3290470 · Cited by 38
“While gradient tracking methods [29] don’t require this assumption, they suffer from increased communication cost and the variance, which limits their practicality [30].”
BackgroundMultiagent Fully Decentralized Value Function Learning With Linear Convergence Rates
Cassano, L., Yuan, K., & Sayed, A. H. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2995814 · Cited by 43
“Several other works employ instead a gradient tracking strategy [27], [28], [33].”
BackgroundA Distributed ADMM-like Method for Resource Sharing over Time-Varying Networks
Aybat, N. S., & Hamedani, E. Y. (2019) · SIAM Journal on Optimization · doi:10.1137/17m1151973 · Cited by 60
Liu, C., Li, H., & Shi, Y. (2020) · Automatica · doi:10.1016/j.automatica.2020.108834 · Cited by 45
“For example, the authors in [5] and [9] develop convergence results based on the small-gain theorem and linear system inequalities, respectively.”
BackgroundMethodInfluentialAccelerated First-Order Optimization Algorithms for Machine Learning
Li, H., Fang, C., & Lin, Z. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2020.3007634 · Cited by 52
“[90] A.”
A Fast Randomized Incremental Gradient Method for Decentralized Nonconvex Optimization
Xin, R., Khan, U. A., & Kar, S. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3122586 · Cited by 50
Consensus-Based Distributed Optimization Enhanced by Integral Feedback
Wang, X., Mou, S., & Anderson, B. D. O. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3169179 · Cited by 40
“For existing algorithms characterized by saddle-point dynamics, the extra states must be exchanged across the network [24], [38].”
BackgroundDistributed Computation of Wasserstein Barycenters Over Networks
Uribe, C. A., Dvinskikh, D., Dvurechensky, P. E., Gasnikov, A. V., & Nedić, A. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619160 · Cited by 48
“The flexibilities induced by the distributed setup make it suitable for problems involving large quantities of data with no centralized storage [23], [24], [25], [26].”
BackgroundSelf-citationA Proximal Diffusion Strategy for Multiagent Optimization With Sparse Affine Constraints
Alghunaim, S. A., Yuan, K., & Sayed, A. H. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2960265 · Cited by 44
“The push-sum technique has been utilized before for distributed optimization algorithms (see, for example, [42]).”
MethodPush-SAGA: A Decentralized Stochastic Algorithm With Variance Reduction Over Directed Graphs
Qureshi, M. I., Xin, R., Kar, S., & Khan, U. A. (2021) · IEEE Control Systems Letters · doi:10.1109/lcsys.2021.3090652 · Cited by 35
“Certain convergence aspects of DSGD are further improved in DSGT [5] with the help of gradient tracking [6]–[10].”
BackgroundMethodInfluentialS-DIGing: A Stochastic Gradient Tracking Algorithm for Distributed Optimization
Li, H., Zheng, L., Wang, Z., Yan, Y., Feng, L., & Guo, J. (2020) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2020.3017242 · Cited by 40
“rder to get kxk −x∗k 2 ≤ ε, S-DIGing algorithm needs iterations number k ≥ 1 q log κ ε = 1+ 1 δ log κ ε > 1+ 1 Θ logκ+log ε where Θ is defined in Theorem 1. From the analysis of DIGing algorithm in [14], it can be concluded that the iteration number k ≥ 1+1 Ξ logκ+log 1 ε where Ξ = αµ 1.5−αµ is needed for kxk −x∗k 2…”
MethodInfluentialGTAdam: Gradient Tracking With Adaptive Momentum for Distributed Online Optimization
Carnevale, G., Farina, F., Notarnicola, I., & Notarstefano, G. (2022) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2022.3232519 · Cited by 49
“Thegradienttrackingscheme,whichweextendinthisarticle, hasbeenproposedinseveralvariantsinrecentyearsandstudied underdifferentproblemassumptions[15],[16],[17],[18],[19], [20],[21],[22].”
Robust Finite-Time Dynamic Average Consensus With Exponential Convergence Rates
Xu, K., Gao, L., Chen, F., et al. (2021) · IEEE Transactions on Circuits & Systems II Express Briefs · doi:10.1109/tcsii.2021.3054039 · Cited by 36
“During the past decade, there has been more and more attention devoted to dynamic average consensus due to its significance in various applications such as formation control [2], sensor optimization [6], [7].”
BackgroundLu, K., & Wang, L. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3091096 · Cited by 46
Distributed discrete-time optimization over directed networks: A dynamic event-triggered algorithm
Yang, Y., He, W., Tian, Y., Du, W., & Qian, F. (2023) · Information Sciences · doi:10.1016/j.ins.2023.119168 · Cited by 35
ASY-SONATA: Achieving Linear Convergence in Distributed Asynchronous Multiagent Optimization
Tian, Y., Sun, Y., & Scutari, G. (2018) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2018.8636055 · Cited by 39
“In [35], the authors proved that a special instance of SONATA, when applied to (P) with strongly convex F , converges at an R-linear rate.”
BackgroundMultiagent Newton–Raphson Optimization Over Lossy Networks
Bof, N., Carli, R., Notarstefano, G., Schenato, L., & Varagnolo, D. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2874748 · Cited by 52
Dynamics based privacy preservation in decentralized optimization
Gao, H. B., Wang, Y., & Nedić, A. (2023) · Automatica · doi:10.1016/j.automatica.2023.110878 · Cited by 44
“…based decentralized optimization which includes as special cases many existing decentralized optimization algorithms, such as Aug-DGM [46], DIGing [24, 33], ATC-DIGing [25], AsynDGM [47], AB [45], and Push-Pull [4,32, 53]; 5) We analytically prove that despite the time-varying randomness injected…”
BackgroundMethodInfluentialSelf-citationDynamic Power Distribution System Management With a Locally Connected Communication Network
Zhang, K., Shi, W., Zhu, H., et al. (2018) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2018.2837338 · Cited by 34
Self-citationDistributed Optimization With Coupling Constraints
Wu, X., Wang, H., & Lu, J. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3169955 · Cited by 49
Finite-Bit Quantization for Distributed Algorithms With Linear Convergence
Michelusi, N., Scutari, G., & Lee, C.-S. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3176253 · Cited by 39
“The algorithmic framework (M) encompasses a variety of distributed algorithms, while Theorem 2 captures their convergence properties; in addition to the schemes covered by (M0) as a special case when R = 1, (M) can also represent EXTRA [43] and its proximal version [50], NEXT [40], [41], [49] and its proximal version…”
BackgroundA Fast Row-Stochastic Decentralized Method for Distributed Optimization Over Directed Graphs
Ghaderyan, D., Aybat, N. S., Aguiar, A. P., & Перейра, Ф. Л. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3275927 · Cited by 45
“We set the Huber loss parameter ξ = 2 , and for each i ∈ V , we generated f i ( x ) = H ξ ( M i x − b i ) as described in [31, Sec.”
MethodInfluentialYang, Y., He, W., Du, W., Tian, Y., Han, Q., & Qian, F. (2024) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2024.3357253 · Cited by 33
“Numerous algorithms have been reported to solve this kind of optimization problems (1), where gradient methods, such as DIGing [5] and its extensions, play an essential role.”
BackgroundLiu, H., Zheng, W. X., & Yu, W. (2020) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2020.3029996 · Cited by 38
DC-DistADMM: ADMM Algorithm for Constrained Optimization Over Directed Graphs
Khatana, V., & Salapaka, M. V. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3221856 · Cited by 44
“05 PushDIGing [65] step-size α = 0 .”
MethodOlshevsky, A., Paschalidis, I. C., & Spiridonoff, A. (2018) · arXiv (Cornell University) · Cited by 31
Self-citationA Sharp Estimate on the Transient Time of Distributed Stochastic Gradient DescentPreprint
Pu, S., Olshevsky, A., & Paschalidis, I. C. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.02702 · Cited by 33
“1) has been studied extensively in the literature under various distributed algorithms [43, 25, 26, 19, 15, 16, 39, 11, 35, 23, 45, 34], among which the distributed gradient descent (DGD) method proposed in [25] has drawn the greatest attention.”
BackgroundSelf-citationA Modified Saddle-Point Dynamics for Distributed Convex Optimization on General Directed Graphs
Touri, B., & Gharesifard, B. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2947184 · Cited by 32
Resilient consensus‐based distributed optimization under deception attacks
Fu, W., Ma, Q., Qin, J., & Kang, Y. (2020) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.5026 · Cited by 39
“To solve the distributed optimization problems under general directed graphs, distributed push-sum based algorithms, 22,26-30 and push-pull based algorithms 31,32 are proposed by applying different techniques.”
MethodResource-Aware Exact Decentralized Optimization Using Event-Triggered Broadcasting
Liu, C., Li, H., & Shi, Y. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3014316 · Cited by 34
Dai, P., Yu, W., & Chen, D. (2021) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2021.3082639 · Cited by 32
“Consequently, the design of distributed algorithms [4]–[9] has gained increasing attention.”
BackgroundMethodCommunication-Censored Linearized ADMM for Decentralized Consensus Optimization
Li, W., Liu, Y., Tian, Z., & Ling, Q. H. (2019) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2019.2957719 · Cited by 35
Bilateral Peer-to-Peer Energy Trading via Coalitional Games
Raja, A. A., & Grammatico, S. (2022) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2022.3196339 · Cited by 31
FedHybrid: A Hybrid Federated Optimization Method for Heterogeneous Clients
Niu, X., & Wei, E. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3240083 · Cited by 44
“First-order primal iterative methods, including distributed (sub)-gradient descent (DGD) and related methods [8], [11], [17], have updates in the form of linear combinations of a local gradient descent step and a weighted average among local neighbors.”
MethodFinite Rate Quantized Distributed optimization with Geometric Convergence
Lee, C.-S., Michelusi, N., & Scutari, G. (2018) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2018.8645345 · Cited by 29
“In particular, geometric convergence when each function fi is strongly convex was proved in [6] for the distributed ADMM method, while [7] for the gradient-tracking based distributed method, first introduced in [8]; a recent overview of distributed algorithms can be found in [9].”
MethodMaros, M., & Jaldén, J. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619626 · Cited by 34
A Canonical Form for First-Order Distributed Optimization Algorithms
Sundararajan, A., Scoy, B. V., & Lessard, L. (2019) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2019.8814838 · Cited by 40
“ζ0 ζ1 ζ2 ζ3 EXTRA [17] 12 1 0 0 NIDS [7] 12 1 0 1 2 Exact Diffusion [23] 12 1 0 1 2 DIGing [9, 15] 0 2 1 0 AsynDGM [22] 0 2 1 1 Jakovetić [4] (B = βI) αβ 2 1 0 Jakovetić [4] (B = βW ) αβ 2 1− αβ 0”
MethodAccelerated Distributed Energy Management for Microgrids
Du, W. J., Yao, L., Wu, D. X., et al. (2018) · IEEE Power & Energy Society General Meeting (PESGM) · doi:10.1109/pesgm.2018.8586094 · Cited by 30
“More specifically, inspired by the recently developed distributed optimization algorithms [17], [18], we develop a unified distributed algorithm with a fixed constant step-size for microgrid energy management over both fixed and time-varying communication networks.”
MethodInput-Feedforward-Passivity-Based Distributed Optimization Over Jointly Connected Balanced Digraphs
Li, M., Chesi, G., & Hong, Y. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3028838 · Cited by 30
“algorithms using the solver ode45 with auto-adjust variable stepsize in MATLAB, and with xi(0) ∈ [2, 3], λ(0) = 0 satisfying the initial condition.”
MethodNetworked Signal and Information Processing: Learning by multiagent systems
Vlaski, S., Kar, S., Sayed, A. H., & Moura, J. M. F. (2023) · IEEE Signal Processing Magazine · doi:10.1109/msp.2023.3267896 · Cited by 47
Decentralized gradient tracking with local steps
Liu, Y., Lin, T., Koloskova, A., & Stich, S. U. (2024) · Optimization methods & software · doi:10.1080/10556788.2024.2322095 · Cited by 72
“We introduce the notation and setup in this section.”
Distributed Algorithms with Finite Data Rates that Solve Linear Equations
Lei, J., Yi, P., Shi, G., & Anderson, B. D. O. (2020) · SIAM Journal on Optimization · doi:10.1137/19m1258864 · Cited by 30
Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks
Song, Z., Shi, L., Pu, S., & Yan, M. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3160238 · Cited by 45
“The methods can also be applied to time-varying graphs [21] and asynchronous settings [22].”
MethodPatari, N., Srivastava, A. K., & Li, N. (2022) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2022.3173634 · Cited by 32
“The following assumptions are made in the communication topology while validating performance the proposed online distributed voltage control in mulitphase power grids [36], [37].”
BackgroundDing, T., Zhu, S., He, J., Chen, C., & Guan, X. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619119 · Cited by 28
“In the field of theoretical research, some papers study distributed constrained optimization algorithms [5]–[7], while some concentrate on unconstrained problems [8], [9].”
BackgroundCan Primal Methods Outperform Primal-Dual Methods in Decentralized Dynamic Optimization?
Yuan, K., Xu, W., & Ling, Q. H. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3011640 · Cited by 36
“2 in [26], Section II.”
A Distributed Algorithm for Solving Linear Algebraic Equations Over Random Networks
Alaviani, S. S., & Elia, N. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3010264 · Cited by 38
Distributed Optimization With Projection-Free Dynamics: A Frank-Wolfe Perspective
Chen, G., Yi, P., Hong, Y., & Chen, J. (2023) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2023.3284822 · Cited by 37
“The gradient tracking method in [36] and [37] motivates this part.”
MethodLü, Q., Li, H., Wang, Z., Han, Q., & Ge, W. C. (2019) · IET Control Theory and Applications · doi:10.1049/iet-cta.2018.6026 · Cited by 28
“In light of [22], we have that the upper bound of ∥ V −1 ∥ max is n nB 0 (Note that the upper bound of ∥ V ∥ max is 1).”
BackgroundMethodResultInfluentialImproved Convergence Rates for Distributed Resource AllocationPreprint
Nedić, A., Olshevsky, A., & Shi, W. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.05441 · Cited by 28
Self-citationDistributed Resource Allocation Over Multiple Interacting Coalitions: A Game-Theoretic Approach
Zhou, J., Wen, G., Lv, Y., et al. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3411833 · Cited by 27
Ma, D., Xing, M., Li, Y., & Sun, Q. (2024) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2024.3447089 · Cited by 30
“Although the distributed algorithm can be accelerated to a linear convergence rate with a fixed step size [20], [21], the algorithms in [11], [12], [13], [14], [15], [16], [17], [18], [19] described above can not be directly replaced with a fixed step size.”
InfluentialOn Primal and Dual Approaches for Distributed Stochastic Convex Optimization over Networks
Dvinskikh, D., Gorbunov, E., Gasnikov, A. V., Dvurechensky, P. E., & Uribe, C. A. (2019) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc40024.2019.9029798 · Cited by 30
DeceFL: a principled fully decentralized federated learning framework
Yuan, Y., Liu, J., Jin, D., Yue, Z., Yang, T., Chen, R., Wang, M., Xu, L., Hua, F., Guo, Y., et al. (2023) · National Science Open · doi:10.1360/nso/20220043 · Cited by 34
“Remark 3 Note that Assumption 4 is equivalent to Assumption 3 when B = 1, as in the analysis of time-varying graphs in [7].”
BackgroundMethodTriggered Gradient Tracking for asynchronous distributed optimization
Carnevale, G., Notarnicola, I., Marconi, L., & Notarstefano, G. (2022) · Automatica · doi:10.1016/j.automatica.2022.110726 · Cited by 28
Wang, A., & Liu, W. (2020) · IEEE Access · doi:10.1109/access.2020.2966078 · Cited by 28
Wu, M., Xiong, N. N., Vasilakos, A. V., Leung, V. C. M., & Chen, C. L. P. (2020) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.3011819 · Cited by 28
Cooperative Multiagent Reinforcement Learning With Partial Observations
Zhang, Y., & Zavlanos, M. M. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3288025 · Cited by 41
Accelerated Distributed Nesterov Gradient Descent for smooth and strongly convex functions
Qu, G., & Li, N. (2016) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2016.7852231 · Cited by 28
“It has been generalized to distributed optimization with time-varying graphs [19], directed graphs [22], and with uncoordinated step sizes [20].”
MethodRecent Theoretical Advances in Decentralized Distributed Convex Optimization
Gorbunov, E., Rogozin, A., Beznosikov, A. N., Dvinskikh, D., & Gasnikov, A. V. (2022) · Springer optimization and its applications · doi:10.1007/978-3-031-00832-0_8 · Cited by 48
“This technique is referred to as gradient tracking and is employed in several primal decentralized methods [125, 111, 169, 74, 3, 124, 123].”
MethodDistributed Adaptive Subgradient Algorithms for Online Learning Over Time-Varying Networks
Zhang, M., Hao, B., Ge, Q., Zhu, J., Zheng, R., & Wu, Q. (2021) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2021.3097714 · Cited by 28
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.