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
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms
Zhang, K., Yang, Z., & Başar, T. (2021) · Studies in Systems, Decision and Control · doi:10.1007/978-3-030-60990-0_12 · Cited by 1,264
A survey of distributed optimization
Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., Hong, Y., Wang, H., Lin, Z., & Johansson, K. H. (2019) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2019.05.006 · Cited by 913
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization
Nedic, A., Olshevsky, A., & Rabbat, M. G. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2817461 · Cited by 534
Self-citationTutorial on dynamic average consensus: the problem, its applications,\n and the algorithms
Kia, S. S., Scoy, B. V., Cortés, J., Freeman, R. A., Lynch, K., & Martı́nez, S. (2018) · eScholarship (California Digital Library) · Cited by 404
Push–Pull Gradient Methods for Distributed Optimization in Networks
Pu, S., Shi, W., Xu, J., & Nedic, A. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2972824 · Cited by 376
“Unlike the push-sum type protocol used in the previous literature [9], [14], our algorithm uses a row stochastic matrix for the mixing of the decision variables, while it employs a column stochastic matrix for tracking the average gradients.”
BackgroundMethodInfluentialSelf-citationSecure and Privacy-Preserving Consensus
Ruan, M., Gao, H., & Wang, Y. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2890887 · Cited by 347
“To analyze the convergence speed of our approach, following the convergence definition in [31] and [32], we define the convergence rate as at least γ ∈ (0, 1) if there exists a positive constant C such that ∥∥x[k]−α1∥∥ ≤ Cγ holds for all k, where α is the average value of the initial states of all nodes in (15).”
MethodFully Decentralized Multi-Agent Reinforcement Learning with Networked Agents
Zhang, K., Yang, Z., Liu, H., Zhang, T., & Başar, T. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.08757 · Cited by 293
Distributed stochastic gradient tracking methods
Pu, S., & Nedić, A. (2021) · Mathematical Programming · doi:10.1007/s10107-020-01487-0 · Cited by 266
Self-citationLi, Z., Shi, W., & Yan, M. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2926022 · Cited by 244
“Paper [25] aims at achieving geometric convergence over time-varying graphs.”
BackgroundInfluentialSelf-citationA Linear Algorithm for Optimization Over Directed Graphs With Geometric Convergence
Xin, R., & Khan, U. A. (2018) · IEEE Control Systems Letters · doi:10.1109/lcsys.2018.2834316 · Cited by 243
“The step-size condition of DEXTRA was subsequently relaxed in ADD-OPT/Push-DIGing [22], [23], which converge geometrically with a sufficiently small step-size.”
MethodLinear Convergence in Optimization Over Directed Graphs With Row-Stochastic Matrices
Xi, C., Mai, V. S., Xin, R., Abed, E. H., & Khan, U. A. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2797164 · Cited by 215
“, [19], [20], [32], [33], [36].”
BackgroundMethodInfluentialNedic, A. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2975210 · Cited by 211
“Simultaneously and independently of [29] and [30], the idea of tracking the gradients has been employed in [31], where a class of distributed algorithms have been developed for solving nonconvex problems in networks.”
BackgroundMethodInfluentialSelf-citationXin, R., & Khan, U. A. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2942513 · Cited by 201
“Optimization with CS weights : We now relate AB to ADD-OPT/Push-DIGing that only require CS weights [33, 34].”
BackgroundMethodResultInfluentialExact Diffusion for Distributed Optimization and Learning—Part I: Algorithm Development
Yuan, K., Ying, B., Zhao, X., & Sayed, A. H. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2875898 · Cited by 200
Communication-efficient algorithms for decentralized and stochastic optimization
Lan, G., Lee, S., & Zhou, Y. (2020) · Mathematical Programming · doi:10.1007/s10107-018-1355-4 · Cited by 187
Accelerated Distributed Nesterov Gradient Descent
Qu, G., & Li, N. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2937496 · Cited by 187
“Instead, we use a gradient estimation sequence recently proposed in [24], [27], and [28], which is a more efficient use of consensus steps to get the correct descent direction.”
BackgroundMethodDistributed nonconvex constrained optimization over time-varying digraphs
Scutari, G., & Sun, Y. (2019) · Mathematical Programming · doi:10.1007/s10107-018-01357-w · Cited by 210
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., & Stich, S. U. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.10422 · Cited by 151
“However, as we require W to be symmetric, our setting is less general than the one considered in (Nedić et al., 2017; Xi & Khan, 2017; Saadatniaki et al., 2018; Assran & Rabbat, 2018; Scutari & Sun, 2019; Assran et al., 2019).”
MethodDistributed Generalized Nash Equilibrium Seeking in Aggregative Games on Time-Varying Networks
Belgioioso, G., Nedić, A., & Grammatico, S. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3005922 · Cited by 151
Self-citationTracking-ADMM for distributed constraint-coupled optimization
Falsone, A., Notarnicola, I., Notarstefano, G., & Prandini, M. (2020) · Automatica · doi:10.1016/j.automatica.2020.108962 · Cited by 177
“…(firstly pro-Postprint posed in Zhu and Mart´ınez (2010) and further elaborated in Kia et al. (2019)), resulting in the so-called gradient-tracking schemes, see, e.g., Di Lorenzo and Scu-tari (2016); Varagnolo et al. (2016); Nedi´c et al. (2017); Qu and Li (2018); Xu et al. (2018); Xi et al. (2018).”
BackgroundZhu, Y., Yu, W., Wen, G., & Ren, W. (2018) · IEEE Transactions on Circuits & Systems II Express Briefs · doi:10.1109/tcsii.2018.2878250 · Cited by 148
“The proposed algorithm could successfully solve the considered problem over weight-unbalanced directed networks without the need to know certain information of both in-neighbors and out-neighbors, and avoids a limitation that appeared in [26], [27], [31], [34], and [35] which require each agent to simultaneously have…”
ResultGame-Theoretic Multiagent Reinforcement Learning
Yang, Y., Ma, C., Ding, Z., McAleer, S., Jin, C., Wang, J., & Sandholm, T. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.00583 · Cited by 136
Communication-efficient distributed learning: An overview
Cao, X., Başar, T., Diggavi, S., Eldar, Y. C., Letaief, K. B., Poor, H. V., & Zhang, J. (2023) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2023.3242710 · Cited by 139
“decentralized optimization over time-varying networks in [28], decentralized optimization over directed networks (e.”
BackgroundMao, S., Tang, Y. S., Dong, Z., Meng, K., Dong, Z. Y., & Qian, F. (2020) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2020.2996198 · Cited by 135
Distributed Time-Varying Convex Optimization for a Class of Nonlinear Multiagent Systems
Huang, B., Zou, Y., Meng, Z., et al. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2917023 · Cited by 131
“[3] have considered the problem of distributed optimization over timevarying graphs, and Lin et al.”
BackgroundDecentralized Optimization Over Time-Varying Directed Graphs With Row and Column-Stochastic Matrices
Saadatniaki, F., Xin, R., & Khan, U. A. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2969721 · Cited by 172
“Ofrelevanceinthiscontextis[26], which uses gradient estimation and push-sum consensus [19], [20] to implement distributed optimization over time-varying graphs.”
BackgroundMethodInfluentialDing, T., Zhu, S., He, J., Chen, C., & Guan, X. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3059427 · Cited by 126
Distributed optimization over directed graphs with row stochasticity and constraint regularity
Mai, V. S., & Abed, E. H. (2019) · Automatica · doi:10.1016/j.automatica.2018.07.020 · Cited by 136
Convergence rate analysis of distributed optimization with projected subgradient algorithm
Liu, S., Qiu, Z., & Xie, L. (2017) · Automatica · doi:10.1016/j.automatica.2017.06.011 · Cited by 122
A Unification and Generalization of Exact Distributed First-Order Methods
Jakovetić, D. (2018) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2018.2846183 · Cited by 142
Decentralized Proximal Gradient Algorithms With Linear Convergence Rates
Alghunaim, S. A., Ryu, E. K., Yuan, K., & Sayed, A. H. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3009363 · Cited by 151
“Substituting into (11): By multiplying the previous equation by ¯ A = A 2 and noting from (9c) that W i = A 2 Z i , we get the recursion: The above recursion is equivalent to the Aug-DGM [1] (also known as ATC-DIGing [2]) algorithm: By eliminating the gradient tracking variable X i , we can rewrite the previous recurs…”
MethodInfluentialA Dual Approach for Optimal Algorithms in Distributed Optimization over Networks
Uribe, C. A., Lee, S., Gasnikov, A. V., & Nedić, A. (2020) · Information Theory and Applications Workshop (ITA) · doi:10.1080/10556788.2020.1750013 · Cited by 151
Self-citationEnabling Privacy-Preservation in Decentralized Optimization
Zhang, C., & Wang, Y. (2019) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2018.2873152 · Cited by 124
“Remark 3: According to [3], when the weights aij (k) are identical and time-invariant, that is, all equal to 1/N , the convergence rate of algorithm (6)–(7) is geometric, that is, there exists a λ ∈ (0, 1) and some positive constant C such that ‖ x(k) − x∗ ‖≤ Cλ holds for all k [38].”
BackgroundDistributed Projection Subgradient Algorithm Over Time-Varying General Unbalanced Directed Graphs
Li, H., Lü, Q., & Huang, T. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2849616 · Cited by 114
“Compared with doubly-stochastic matrix [9]–[12] and columnstochastic weight matrix [13], [16], [17], [27], it is considered more convenient to be implemented since each agent in the directed graphs can locally adjust the weights on the information obtained from in-neighbors.”
BackgroundMethodXin, R., Kar, S., & Khan, U. A. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2974267 · Cited by 114
“Combining push-sum, respectively, with DSGD [14], [15] and GT-DGD [20]–[22] leads to SGP [40] and ADD–OPT [41], which require CS weights.”
MethodBalancing Communication and Computation in Distributed Optimization
Berahas, A. S., Bollapragada, R., Keskar, N. S., & Wei, E. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2880407 · Cited by 136
“In [29], [61], [60], [47], the authors also show their respective algorithms can achieve a linear rate of convergence.”
BackgroundA General Framework for Decentralized Optimization With First-Order Methods
Xin, R., Pu, S., Nedić, A., & Khan, U. A. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2020.3024266 · Cited by 149
“We note that the general idea of push-sum consensus, explored over the GT-DGD framework as in ADDDOPT/Push-DIGing [13], [40], essentially results from a state transformation in AB / Push-Pull .”
BackgroundMethodResultInfluentialSelf-citationDistributed stochastic optimization with gradient tracking over strongly-connected networks
Xin, R., Sahu, A. K., Khan, U. A., & Kar, S. (2019) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc40024.2019.9029217 · Cited by 122
“Methods for directed graphs that are based on gradient tracking [14]–[21] rely on separate iterations for eigenvector estimation that may impede the convergence.”
Distributed Aggregative Optimization Over Multi-Agent Networks
Li, X., Xie, L., & Hong, Y. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3095456 · Cited by 125
Liang, S., Wang, L. Y., & Yin, G. (2019) · Automatica · doi:10.1016/j.automatica.2019.04.004 · Cited by 106
Variance-Reduced Decentralized Stochastic Optimization With Accelerated Convergence
Xin, R., Khan, U. A., & Kar, S. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3031071 · Cited by 128
“For both GT-SAGA and GT-SVRG , In the following, we first present a few well-known results re-lated to decentralized gradient tracking methods whose proofs can be found in, e.g., [21], [22], [30], [31].”
MethodAchieving Acceleration for Distributed Economic Dispatch in Smart Grids Over Directed Networks
Lü, Q., Liao, X., Li, H., & Huang, T. (2020) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2020.2965999 · Cited by 109
“We note that, the amount of preprocessing in calculating the global parameters is substantially negligible compared with the worst-case running time of D-DLM (see [46] for a specific analysis).”
MethodLi, H., Lü, Q., Liao, X., & Huang, T. (2018) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2018.2823901 · Cited by 110
“Nedi´c et al. [35] was concentrated on the analysis of the distributed optimization problems with coordinated step-size over time-varying undirected/directed graphs.”
BackgroundMethodInfluentialLiu, L.-N., & Yang, G. (2021) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2021.3076526 · Cited by 103
Distributed Optimization for Smart Cyber-Physical Networks
Notarstefano, G., Notarnicola, I., & Camisa, A. (2019) · Foundations and Trends® in Systems and Control · doi:10.1561/2600000020 · Cited by 122
Distributed Smooth Convex Optimization With Coupled Constraints
Liang, S., Wang, L. Y., & Yin, G. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2912494 · Cited by 116
An Improved Convergence Analysis for Decentralized Online Stochastic Non-Convex Optimization
Xin, R., Khan, U. A., & Kar, S. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3062553 · Cited by 147
“Theorem 2 further shows that when the exact gradient oracle is available at each node, i.e., ν 2 i = 0 , ∀ i ∈ V , we note that GT-DSGD reduces to its deterministic counterpart [15], [17], [18] and achieves global linear convergence to an optimal solution with an appropriate constant step-size.”
BackgroundAchieving Linear Convergence in Distributed Asynchronous Multiagent Optimization
Tian, Y., Sun, Y., & Scutari, G. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2977940 · Cited by 120
“The key result is a generalization of the small gain theorem (cf. Theorem 22), first used in [35].”
BackgroundMethodInfluentialLi, H., Lü, Q., & Huang, T. (2018) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2018.2848288 · Cited by 96
“Moreover, the proposed algorithm gives a wider selection of the step-sizes (allows for using uncoordinated step-sizes for all agents) than most existing methods proposed in [20], [21], [24] and [25].”
BackgroundMethodInfluentialA Push-Pull Gradient Method for Distributed Optimization in Networks
Pu, S., Shi, W., Xu, J., & Nedic, A. (2018) · 2018 IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619047 · Cited by 94
“We test our proposed algorithm, Push-Pull, against Push-DIGing [22] and Xi-Row [24].”
BackgroundMethodInfluentialSelf-citationDistributed Zero-Order Algorithms for Nonconvex Multiagent Optimization
Tang, Y., Zhang, J., & Li, N. (2020) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2020.3024321 · Cited by 95
“We refer to [8], [12], and [39] for related analysis, and to Section IV for a numerical example.”
BackgroundMethodInfluentialSun, Y., Scutari, G., & Daneshmand, A. (2022) · SIAM Journal on Optimization · doi:10.1137/19m1259973 · Cited by 155
“Algorithms [9, 10, 14, 15, 18, 20, 29, 38, 40] [27, 46, 48, 56] [19, 21, 25, 31, 55] SONATA”
BackgroundMethodResultInfluentialBastianello, N., Carli, R., Schenato, L., & Todescato, M. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3011358 · Cited by 119
“n-based methods. Distributed gradient descent algorithms in general combine local gradient descent steps with consensus averaging, see for example [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14]. These algorithms can handle many different scenarios, with smooth and non-smooth costs, over both fixed and…”
BackgroundDistributed Dual Gradient Tracking for Resource Allocation in Unbalanced Networks
Zhang, J., You, K., & Cai, K. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2981762 · Cited by 106
“Moreover, PPG has an empirically faster convergence speed than its competitors (e.g. [33]), and its linear update rule is an advantage for implementation.”
BackgroundMethodDistributed Online Convex Optimization With an Aggregative Variable
Li, X., Yi, X., & Xie, L. (2021) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2021.3107480 · Cited by 95
Solving a system of linear equations: From centralized to distributed algorithms
Wang, P., Mou, S., Lian, J. J., & Ren, W. (2019) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2019.04.008 · Cited by 95
Distributed nonconvex multiagent optimization over time-varying networks
Sun, Y., Scutari, G., & Palomar, D. (2016) · 2016 50th Asilomar Conference on Signals, Systems and Computers · doi:10.1109/acssc.2016.7869154 · Cited by 86
“In the same technical report [26], the authors proposed pushDIGing, the extension of DIGing to B-strongly connected digraphs.”
BackgroundMethodInfluentialFROST—Fast row-stochastic optimization with uncoordinated step-sizes
Xin, R., Xi, C., & Khan, U. A. (2019) · EURASIP Journal on Advances in Signal Processing · doi:10.1186/s13634-018-0596-y · Cited by 122
“, and the theorem follows. Note that the notions of sufficiently small step-sizes and the bound on the condition number, D, of the step-size matrix, D, are not uncommon in the literature, see, e.g., [27, 40, 43, 50, 51]. To prove linear convergence to the optimal solution, we need a few more auxiliary relations as foll…”
BackgroundParallel and Distributed Successive Convex Approximation Methods for Big-Data Optimization
Scutari, G., & Sun, Y. (2018) · Lecture notes in mathematics · doi:10.1007/978-3-319-97142-1_3 · Cited by 121
“We are now in the position to show that the algorithms in [170,190,257,259] are all special cases of SONATA and the earlier proposal NEXT [69, 70, 148].”
BackgroundMethodInfluentialDistributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
Xu, J., Tian, Y., Sun, Y., & Scutari, G. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3086579 · Cited by 109
“For instance, consider EXTRA [3] and DIGing [9] (corresponding to Algorithm (24) with B = I , cf.”
BackgroundResultInfluentialDistributed Optimization in Prescribed-Time: Theory and Experiment
Gong, X., Cui, Y., Shen, J., Xiong, J., & Huang, T. (2021) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2021.3126154 · Cited by 88
Exact Diffusion for Distributed Optimization and Learning—Part II: Convergence Analysis
Yuan, K., Ying, B., Zhao, X., & Sayed, A. H. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2875883 · Cited by 103
A review of distributed optimization: Problems, models and algorithms
Zheng, Y., & Liu, Q. (2021) · Neurocomputing · doi:10.1016/j.neucom.2021.06.097 · Cited by 98
Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization
Doan, T. T., Maguluri, S. T., & Romberg, J. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3014095 · Cited by 100
Li, L., Yu, Y., Li, X., & Xie, L. (2022) · Automatica · doi:10.1016/j.automatica.2022.110259 · Cited by 91
Intrusion Detection in Distributed Frequency Control of Isolated Microgrids
Lu, L.-Y., Liu, H. J., Zhu, H., & Chu, C. (2019) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2019.2906573 · Cited by 83
“Informally speaking, considering the communication delay is bounded which can be guaranteed under modern communication infrastructure [46], and the time-varying communication graph G is connected on average [47], [48], it is possible to select a small enough stepsize to guarantee stability.”
BackgroundDistributed Energy Resource Coordination Over Time-Varying Directed Communication Networks
Yang, T., Wu, D. X., Fang, H., Ren, W., Wang, H., Hong, Y., & Johansson, K. H. (2019) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2019.2921284 · Cited by 80
A Distributed Stochastic Gradient Tracking Method
Pu, S., & Nedić, A. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8618708 · Cited by 70
“A distributed gradient tracking method was proposed in [17]–[19], where the agent-based auxiliary variables yi were introduced to track the average gradients of fi assuming accurate gradient information is available.”
BackgroundMethodSelf-citationAdvances in Asynchronous Parallel and Distributed Optimization
Assran, M., Aytekin, A., Feyzmahdavian, H. R., Johansson, M., & Rabbat, M. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2020.3026619 · Cited by 132
“Gradient-tracking methods using a constant step-size, such as ASY-SONATA, have this interdependence, and typically show consensus and optimality simultaneously using (18) and the small-gain theorem [88].”
MethodVariance-Reduced Stochastic Learning by Networked Agents Under Random Reshuffling
Yuan, K., Ying, B., Liu, J., & Sayed, A. H. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2872003 · Cited by 67
“The exact diffusion method, in particular, has been shown to have a wider stability range than EXTRA implementations (i.e., it is stable for a wider range of step-sizes, μ), and is also more efficient in terms of communications than DIGing.”
MethodInfluentialA Nesterov-Like Gradient Tracking Algorithm for Distributed Optimization Over Directed Networks
Lü, Q., Liao, X., Li, H., & Huang, T. (2020) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2019.2960770 · Cited by 79
“Mathematically, there exists L i > 0 such that for any x , y ∈ R p , one has ( Assumption 3 (Strong Convexity [42]): Each local cost function f i , i ∈ V , is μ i -strongly connected.”
BackgroundMethodInfluentialAsySPA: An Exact Asynchronous Algorithm for Convex Optimization Over Digraphs
Zhang, J., & You, K. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2930234 · Cited by 94
“, [13]–[15] and [45]– [47], some of which adopt its idea to address the unbalancedness of digraphs.”
BackgroundDecentralized multi-agent reinforcement learning with networked agents: recent advances
Zhang, K., Yang, Z., & Başar, T. (2021) · Frontiers of Information Technology & Electronic Engineering · doi:10.1631/fitee.1900661 · Cited by 125
Hybrid Voltage Control in Distribution Networks Under Limited Communication Rates
Liu, H. J., Shi, W., & Zhu, H. (2018) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2018.2797692 · Cited by 75
Self-citationDoan, T. T., Maguluri, S. T., & Romberg, J. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3031018 · Cited by 81
Distributed Online Aggregative Optimization for Dynamic Multirobot Coordination
Carnevale, G., Camisa, A., & Notarstefano, G. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3196627 · Cited by 83
Distributed Learning in the Nonconvex World: From batch data to streaming and beyond
Chang, T., Hong, M., Wai, H.-T., Zhang, X., & Lu, S. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2970170 · Cited by 114
Shi, C., & Yang, G. (2018) · Automatica · doi:10.1016/j.automatica.2018.04.010 · Cited by 70
Distributed Nesterov Gradient Methods Over Arbitrary Graphs
Xin, R., Jakovetić, D., & Khan, U. A. (2019) · IEEE Signal Processing Letters · doi:10.1109/lsp.2019.2925537 · Cited by 86
“rate the rowand column-stochastic weight matrices, i.e., a ij= 1=jNin i j;8i; and b ij= 1=jNout j j;8j. We first compare ABNand FROZEN with the following methods over digraphs: ADDOPT/PushDIGing [25], [26], FROST [28], and AB[33]. For comparison, we plot the average residual: 1 n P n i=1 kx i(k) x k 2. A. Strongly-conv…”
BackgroundMethodInfluentialDistributed least squares solver for network linear equations
Yang, T., George, J., Qin, J., Yi, X., & Wu, J. (2020) · Automatica · doi:10.1016/j.automatica.2019.108798 · Cited by 76
“Note that the existing studies (Xu et al., 2015; Qu and Li, 2018; Nedić et al., 2017) only established conservative sufficient conditions on the step-size for the exponential convergence.”
BackgroundResultInfluentialOn the Influence of Bias-Correction on Distributed Stochastic Optimization
Yuan, K., Alghunaim, S. A., Ying, B., & Sayed, A. H. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3008605 · Cited by 89
“The recent work [25] studies the gradient-tracking method (referred to as DIGing in [3]) to the stochastic setting and shows that it can outperform the decentralized gradient descent (DGD) [12], [14] via numerical simulations.”
MethodDAdam: A Consensus-Based Distributed Adaptive Gradient Method for Online Optimization
Nazari, P., Tarzanagh, D. A., & Michailidis, G. C. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3223214 · Cited by 118
“Analogous convergence results are given in [21] for time-varying graphs.”
BackgroundMethodResultSurvey of distributed algorithms for resource allocation over multi-agent systems
Doostmohammadian, M., Aghasi, A., Pirani, M., Nekouei, E., Zarrabi, H., Keypour, R., Rikos, A. I., & Johansson, K. H. (2024) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2024.100983 · Cited by 109
Dual Averaging Push for Distributed Convex Optimization Over Time-Varying Directed Graph
Liang, S., Wang, L. Y., & Yin, G. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2934216 · Cited by 60
“[17]–[19] are the first to develop subgradient push methods to cover time-varying directed graphs, not necessarily balanced.”
BackgroundAssran, M. S., & Rabbat, M. G. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2981035 · Cited by 101
“In these experiments we compare AGP with three synchronous methods: Push DIGing (PD) [31], Extra Push (EP) [44], and Synchronous (Sub)Gradient-Push (SGP) [29].”
S-ADDOPT: Decentralized Stochastic First-Order Optimization Over Directed Graphs
Qureshi, M. I., Xin, R., Kar, S., & Khan, U. A. (2020) · IEEE Control Systems Letters · doi:10.1109/lcsys.2020.3006420 · Cited by 61
“In particular, S-ADDOPT adds gradient tracking to SGP (stochastic gradient push) [16], [24], [25] and can be viewed as a stochastic extension of ADDOPT [14], [28] that uses true gradients.”
BackgroundYi, X., Zhang, S., Yang, T., Chai, T., & Johansson, K. H. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3108501 · Cited by 83
“[19] Strongly convex and smooth local cost functions Uniformly jointly strongly connected, two variables Discrete-time”
BackgroundLü, Q., Li, H., & Xia, D. (2017) · Information Sciences · doi:10.1016/j.ins.2017.09.038 · Cited by 56
Recent advances in optimization and game theoretic control for networked systems
Wu, Y., Cheng, D., Ghosh, B. K., & Shen, T. (2019) · Asian Journal of Control · doi:10.1002/asjc.2303 · Cited by 55
“Extensions of the networked incremental subgradient method to diminishing step-sizes and time-varying graph topologies can be found in [84,85].”
MethodA Compressed Gradient Tracking Method for Decentralized Optimization With Linear Convergence
Liao, Y., Li, Z., Huang, K., & Pu, S. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3180695 · Cited by 90
“, X̂ = X and Ŷ = Y, then C-GT recovers the typical distributed gradient tracking algorithm in [8], [9] for ηi = η.”
BackgroundA Dual Splitting Approach for Distributed Resource Allocation With Regularization
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2018) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2018.2834310 · Cited by 52
Second-Order Guarantees of Distributed Gradient Algorithms
Daneshmand, A., Scutari, G., & Kungurtsev, V. (2020) · SIAM Journal on Optimization · doi:10.1137/18m121784x · Cited by 68
“If R and C are allowed to be time-varying (suitably chosen) (2.2) reduces to the SONATA algorithm applicable to (possibly time-varying) digraphs [30, 27, 26, 29] [or the one later proposed in [20] for strongly convex instances of (P)].”
MethodInfluentialLiu, H., Yu, W., & Chen, G. (2020) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.3022240 · Cited by 55
Primal–Dual Methods for Large-Scale and Distributed Convex Optimization and Data Analytics
Jakovetić, D., Bajović, D., Xavier, J., & Moura, J. M. F. (2020) · Proceedings of the IEEE · doi:10.1109/jproc.2020.3007395 · Cited by 67
“The AHU-type algorithm blueprint leaves us near the structure of efficient distributed first-order primal-dual methods such as EXTRA [30], DIGing [47], and their subsequent generalization in [44].”
MethodInfluentialDistributed Nesterov Gradient and Heavy-Ball Double Accelerated Asynchronous Optimization
Li, H., Cheng, H., Wang, Z., & Wu, G. (2020) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.3027381 · Cited by 62
Lü, Q., & Li, H. (2016) · arXiv · doi:10.48550/arxiv.1611.00990 · Cited by 54
“Proof: The proof procedure can imitate that of Lemma 5 in [25], and thus it is omitted.”
BackgroundMethodInfluentialDong, Z., Mao, S., Perc, M., Du, W., & Tang, Y. S. (2022) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2022.3216572 · Cited by 55
“As shown in the researches of the dual problem, distributed optimization problem, diminishing step sizes influence the convergence rate [17], [18], [19] and the linear convergence rate can be obtained by some algorithms [18], [19] employing fixed step sizes.”
BackgroundMethodInfluentialChen, X., Huang, L., He, L., Dey, S., & Shi, L. (2023) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2023.3264932 · Cited by 55
“Assumption 3 is weaker than assumptions in most previous works (see, e.g., [8], [23], and [24]), where graphs G R and G C are assumed to be strongly connected.”
BackgroundLinear convergence of primal–dual gradient methods and their performance in distributed optimization
Alghunaim, S. A., & Sayed, A. H. (2020) · Automatica · doi:10.1016/j.automatica.2020.109003 · Cited by 72
“Applying the primal-dual gradient algorithm (3) for this case gives: By eliminating the dual variable, this algorithm can be shown to be equivalent to DIGing – see [26, Section 2.2].”
MethodInfluentialWalkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization
Mao, X., Yuan, K., Hu, Y., Gu, Y., Sayed, A. H., & Yin, W. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2983167 · Cited by 90
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.