Distributed Optimization Over Time-Varying Directed Graphs
The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index; 2 of the 13 sources its claims cite were checked for support.
Abstract
We consider distributed optimization by a collection of nodes, each having access to its own convex function, whose collective goal is to minimize the sum of the functions. The communications between nodes are described by a time-varying sequence of directed graphs, which is uniformly strongly connected. For such communications, assuming that every node knows its out-degree, we develop a broadcast-based algorithm, termed the subgradient-push, which steers every node to an optimal value under a standard assumption of subgradient boundedness. The subgradient-push requires no knowledge of either the number of agents or the graph sequence to implement. Our analysis shows that the subgradient-push algorithm converges at a rate of O(\ln t √t). The proportionality constant in the convergence rate depends on the initial values at the nodes, the subgradient norms and, more interestingly, on both the speed of the network information diffusion and the imbalances of influence among the nodes.
Overview
CoChat Summary
TL;DR
The paper introduces the subgradient-push algorithm for distributed convex optimization over time-varying directed graphs that are uniformly strongly connected, requiring each node only to know its outdegree. It proves convergence to a common optimal solution and an objective convergence rate of \(O(\ln t/\sqrt{t})\).
Key findings
- The subgradient-push method drives all nodes to the same optimal point under convexity, nonempty optimal set, bounded subgradients, and standard decaying stepsize conditions.
- For stepsize \(\alpha(t)=1/\sqrt{t}\), the objective converges at rate \(O(\ln t/\sqrt{t})\), with the constant depending on initial values, subgradient norm bounds, the network diffusion speed \(\lambda\), and the influence-imbalance measure \(\delta\).
- For regular directed graphs, \(\delta=1\); in general, \(1/(\delta(1-\lambda))\) is bounded exponentially by \(n^{2nB}\) in the worst case, but for time-varying regular directed graphs it scales polynomially in \(n\).
- Simulations on a scalar quadratic estimation problem with \(n=1000\) nodes and threshold \(\|z(t)-\theta^*1\|\le 0.1\) show sub-geometric decay and time scaling linearly in the number of nodes from \(n=10\) to \(90\).
Methods
- Theoretical design and analysis of a broadcast-based distributed subgradient algorithm combining subgradient updates with the push-sum protocol over time-varying directed graphs.
- Convergence proofs rely on a perturbed push-sum protocol, consensus-product bounds, and deterministic supermartingale-type convergence lemmas; the rate proof uses \(\alpha(t)=1/\sqrt{t}\) and node-maintained running averages \(\tilde z_i(t)\).
- Simulations optimize \(F(\theta)=\sum_{i=1}^n p_i(\theta-u_i)^2\), with half the \(p_i\)'s set to zero and half uniformly random in \([0,1]\), Gaussian initial points, and graph sequences including random two-out-neighbor graphs and alternating undirected star graphs.
Limitations
- The paper states that Theorem 2 does not address convergence of the sequences \(\{\tilde z_i(t)\}\), and it lists open problems on how \(\lambda\) depends on graph-sequence properties and how \(\delta\) depends on combinatorial graph features such as diameters and smallest cuts.
- The text makes evident that the simulations are restricted to a scalar quadratic estimation problem and specific graph models, so empirical behavior for general convex functions or higher-dimensional problems is not demonstrated.
- The algorithm assumes every node knows its outdegree \(d_i(t)\) at every time \(t\), which is an implementation requirement rather than a limitation the paper frames as such.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
2 Valid · 1 Not valid · 3 Not checked · 36 Own results and interpretations
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
“Here, we generalize this result by showing that the protocol remains convergent even if the state of the nodes is perturbed at each step, as long as the perturbations decay to zero.”
- Also stated in: § III. PERTURBED PUSH-SUM PROTOCOL · p. 5 · plain
“When the perturbations are nonzero, Lemma 1 states that if these perturbations decay to zero, then the push-sum method still converges.”
boostedstates a possible 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: § III. PERTURBED PUSH-SUM PROTOCOL · p. 5 · plain
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Indeed, Theorem 2 shows that for a class of time-varying regular directed graphs, 1 / ( δ (1 -λ )) scales polynomially in n .”
boostedstates an association- 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 an assumption not shown here.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The proportionality constant in the convergence rate depends on the initial values at the nodes, the subgradient norms and, more interestingly, on both the speed of the network information diffusion and the imbalances of influence among the nodes.”
- Also stated in: § I. INTRODUCTION · p. 1 · plain
“Our results show that it converges at a rate of O ( ln t/ √ t ) , where the constant depends, among other factors, on the information diffusion speed of the corresponding directed graph sequence and a measure of the influence imbalance among the nodes.”
plainstates an association- 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 3 assumptions not shown here.
- Also stated in: § I. INTRODUCTION · p. 1 · plain
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Our analysis shows that the subgradientpush algorithm converges at a rate of O ( ln t/ √ t ) .”
- Also stated in: § B. Our results · p. 3 · boosted
“We then demonstrate that the subgradient-push converges at a rate of O (ln t/ √ t ) ; this is formally stated in the following theorem.”
boostedstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on 5 assumptions not shown here.
- Also stated in: § B. Our results · p. 3 · boosted
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
“The subgradient-push requires no knowledge of either the number of agents or the graph sequence to implement.”
- Also stated in: § I. INTRODUCTION · p. 1 · plain
“By contrast, our results work in time-varying networks and are fully distributed, requiring no knowledge of either the graph sequence or the number of agents.”
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.
- Rests on an assumption not shown here.
- Also stated in: § I. INTRODUCTION · p. 1 · plain
12 more claims
Create a free account to see all 42 claims and every source verdict.
- It may state two separate claims as one. 13
- Probably not a substantial claim. 8
- The quote only partly states this claim. 7
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing 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.”
From Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs (2017) · cites this paper as [42]
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
§ B. Our results · p. 3
“Theorem 2: Suppose that all the assumptions of Theorem 1 hold, and let α ( t ) = 1 / √ t for t ≥ 1 .”
§ IV. CONVERGENCE RESULTS FOR SUBGRADIENT-PUSH METHOD · p. 12
“Also, by assumption we have ∑ ∞ t =1 α ( t ) = ∞ and ∑ ∞ t =1 α 2 ( t ) < ∞ .”
Citations
Cites
Coordination of groups of mobile autonomous agents using nearest neighbor rules
Jadbabaie, A., Lin, J., & Morse, A. S. (2003) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2003.812781 · Cited by 8,339
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×
“Distributed optimization of a sum of convex functions has received a surge of interest in recent years [18], [23], [9], [14], [12], [13], [28], [16], [3], [24], [5].”
BackgroundMethodStability of multiagent systems with time-dependent communication links
Moreau, L. (2005) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2004.841888 · Cited by 2,706
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
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2161027 · Cited by 947
Distributed optimization in sensor networks
Rabbat, M., & Nowak, R. (2004) · Proceedings of the 3rd international symposium on Information processing in sensor networks · doi:10.1145/984622.984626 · Cited by 901 · cited 1×
“For example, the problems including robust statistical inference [22], formation control [20], non-autonomous power control [25], distributed message routing [19], and spectrum access coordination [10], can be reduced to variations of this problem.”
Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2010) · Cited by 884
Convergence in Multiagent Coordination, Consensus, and Flocking
Blondel, V. D., Hendrickx, J. M., Olshevsky, A., & Tsitsiklis, J. N. (2006) · Proceedings of the 44th IEEE Conference on Decision and Control · doi:10.1109/cdc.2005.1582620 · Cited by 859
Self-citationDistributed Stochastic Subgradient Projection Algorithms for Convex Optimization
Sundhar Ram, S., Nedić, A., & Veeravalli, V. V. (2010) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-010-9737-7 · Cited by 814 · cited 2×
“Specifically, it is standard for a distributed subgradient method to converge at the rate of O(ln t/ √ t) with the constant depending on the subgradientnorm upper bounds Li and the initial conditions xi(0) [5], [24].”
Self-citation
Research works printed but not linked: 1
- tsianos, 2013, The role of the Network in Distributed Optimization Algorithms Convergence Rates Scalability Communication/Computation Tradeoffs and Communication Delays
Cited by
EXTRA: 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
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
Nedić, A., Olshevsky, A., & Shi, W. (2017) · SIAM Journal on Optimization · doi:10.1137/16m1084316 · Cited by 1,069
Self-citationA 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
Harnessing Smoothness to Accelerate Distributed Optimization
Qu, G., & Li, N. (2018) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2017.2698261 · Cited by 565
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
“This Push Sum consensus-based algorithm has been extended to the subgradient-push algorithm in [47], [48] that can deal with convex optimization problems over time-varying directed graphs.”
BackgroundMethodSelf-citationNEXT: In-Network Nonconvex Optimization
Lorenzo, P. D., & Scutari, G. (2016) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2016.2524588 · Cited by 473
“Algorithms belonging to the former class include: i) consensus-based (sub)gradient schemes [1]–[4] along with their accelerated and asynchronous versions [5]–[7]; ii) the (sub)gradient push-method [8], [9]; iii) the dual-average method [10], [11]; and iv) distributed secondorder-based schemes [12], [13].”
MethodLin, P., Ren, W., & Farrell, J. A. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2604324 · Cited by 403
Tutorial 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
Self-citationXu, J., Zhu, S., Soh, Y. C., & Xie, L. (2015) · 2015 54th IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402509 · Cited by 332
1Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed GraphsPreprint
Nedić, A., & Olshevsky, A. (2016) · Cited by 316
Self-citationDistributed Optimization for Control
Nedić, A., & Liu, J. (2018) · Annual Review of Control, Robotics, and Autonomous Systems · doi:10.1146/annurev-control-060117-105131 · Cited by 302
Self-citationDistributed Optimization Under Adversarial Nodes
Sundaram, S., & Gharesifard, B. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2836919 · Cited by 274
A Distributed Algorithm for Economic Dispatch Over Time-Varying Directed Networks With Delays
Yang, T., Lu, J., Wu, D., Wu, J., Shi, G., Meng, Z., & Johansson, K. H. (2017) · IEEE Transactions on Industrial Electronics · doi:10.1109/tie.2016.2617832 · Cited by 264
Li, Z., Shi, W., & Yan, M. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2926022 · Cited by 244
“Another topic of interest is decentralized optimization over directed graphs [41], [43]–[46], which is beyond the scope of this paper.”
BackgroundLi, C., Yu, X., Huang, T., & He, X. (2018) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2017.2691760 · Cited by 252
A 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
Convergence of Asynchronous Distributed Gradient Methods Over Stochastic Networks
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2730481 · Cited by 214
Necessary and sufficient conditions for containment control of multi-agent systems with time delay
Wang, D., Wang, D., & Wang, W. (2019) · Automatica · doi:10.1016/j.automatica.2018.12.029 · Cited by 227
Newton-Raphson Consensus for Distributed Convex Optimization
Varagnolo, D., Zanella, F., Cenedese, A., Pillonetto, G., & Schenato, L. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2449811 · Cited by 219
Linear 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
Fast Convergence Rates for Distributed Non-Bayesian Learning
Nedic, A., Olshevsky, A., & Uribe, C. A. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2690401 · Cited by 212
Self-citationDecision Making in Multiagent Systems: A Survey
Rizk, Y., Awad, M., & Tunstel, E. W. (2018) · IEEE Transactions on Cognitive and Developmental Systems · doi:10.1109/tcds.2018.2840971 · Cited by 219
Nedic, A. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2975210 · Cited by 211
“Subsequently, in [15] a simple (sub)gradient method using the push–sum consensus has been proposed for a general sequence of time-varying directed graphs and is later extended to a stochastic method in [16].”
BackgroundMethodInfluentialSelf-citationXin, R., & Khan, U. A. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2942513 · Cited by 201
Exact 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
Distributed Online Convex Optimization on Time-Varying Directed Graphs
Akbari, M., Gharesifard, B., & Linder, T. (2017) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2015.2505149 · Cited by 190
Distributed Subgradient Projection Algorithm Over Directed Graphs
Xi, C., & Khan, U. A. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2615066 · Cited by 185
DEXTRA: A Fast Algorithm for Optimization Over Directed Graphs
Xi, C., & Khan, U. A. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2672698 · Cited by 172
Accelerated Distributed Nesterov Gradient Descent
Qu, G., & Li, N. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2937496 · Cited by 187
On Nonconvex Decentralized Gradient Descent
Zeng, J., & Yin, W. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2818081 · Cited by 184
Li, Z., Wu, Z., Li, Z., & Ding, Z. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2937500 · Cited by 183
“, [1], [14], [15]; the bottom layer is a local regulator.”
BackgroundADD-OPT: Accelerated Distributed Directed Optimization
Xi, C., Xin, R., & Khan, U. A. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2737582 · Cited by 181
“A. Convergence rate In our first experiment, we compare the convergence rate of algorithms that solve the above distributed consensus optimization problem over directed graphs, including ADD-OPT, DEXTRA, [37], Gradient-Push, [26], Directed-Distributed Gradient Descent, [21], and the Weight Balanced-Distributed Gradien…”
Nash Equilibrium Computation in Subnetwork Zero-Sum Games With Switching Communications
Lou, Y., Hong, Y., Xie, L., Shi, G., & Johansson, K. H. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2504962 · Cited by 172
Non-Convex Distributed Optimization
Tatarenko, T., & Touri, B. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2648041 · Cited by 171
Distributed Algorithms for Searching Generalized Nash Equilibrium of Noncooperative Games
Lu, K., Jing, G., & Wang, L. (2019) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2018.2828118 · Cited by 168
Distributed Time-Varying Quadratic Optimization for Multiple Agents Under Undirected Graphs
Sun, C., Ye, M., & Hu, G. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2673240 · Cited by 160
Distributed nonconvex constrained optimization over time-varying digraphs
Scutari, G., & Sun, Y. (2019) · Mathematical Programming · doi:10.1007/s10107-018-01357-w · Cited by 210
Aybat, N. S., Wang, Z., Lin, T., & Ma, S. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2713046 · Cited by 172
Optimal distributed stochastic mirror descent for strongly convex optimization
Yuan, D., Hong, Y., Ho, D. W. C., & Jiang, G. (2018) · Automatica · doi:10.1016/j.automatica.2017.12.053 · Cited by 154
“To the best of our knowledge, our proposed algorithm is the first distributed algorithm that utilizes the idea of epoch gradient descent to develop a distributed stochastic mirror descent algorithm (different from the distributed stochastic subgradient algorithm in Tsianos and Rabbat (2012)).”
MethodA 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
Nash equilibrium seeking for N -coalition noncooperative games
Ye, M., Hu, G., & Lewis, F. L. (2018) · Automatica · doi:10.1016/j.automatica.2018.05.020 · Cited by 154
Distributed Online Optimization for Multi-Agent Networks With Coupled Inequality Constraints
Li, X., Yi, X., & Xie, L. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3021011 · Cited by 180
Li, H., Liu, S., Soh, Y. C., & Xie, L. (2017) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2017.2694323 · Cited by 155
Tracking-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
Zhu, 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
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
Distributed Convex Optimization with Inequality Constraints over Time-Varying Unbalanced Digraphs
Xie, P., You, K., Tempo, R., Song, S., & Wu, C. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2816104 · Cited by 133
Mao, 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
“This idea makes the gradient term in (5) different from the exact gradient in [25], bringing challenges to the convergence analysis and convergence rate analysis.”
BackgroundMethodResultInfluentialYe, M., & Hu, G. (2016) · IEEE Transactions on Control Systems Technology · doi:10.1109/tcst.2016.2517574 · Cited by 129
Decentralized 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
“Optimization over directed graphs is developed in [16]–[18], where push-sum [19], [20] is used to achieve consensus among the agents.”
BackgroundMethodResultInfluentialDistributed 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
“…in this line of research is the availability of a doubly stochastic weight matrix (i.e., each row and each column sum up to 1) or a column stochastic one (i.e., each column sums up to 1); see, e.g., [9, 17, 19, 23, 24, 31, 32, 38, 41] for the former case and [1,29,41,42,46,48] for the latter.”
BackgroundMethodInfluentialConvergence 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
Distributed Subgradient Method With Edge-Based Event-Triggered Communication
Kajiyama, Y., Hayashi, N., & Takai, S. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2800760 · Cited by 121
A 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-citationA Distributed Algorithm for Resource Allocation Over Dynamic Digraphs
Xu, Y., Han, T., Cai, K., Lin, Z., Yan, G., & Fu, M. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2669896 · Cited by 124
A Finite-Time Distributed Optimization Algorithm for Economic Dispatch in Smart Grids
Mao, S., Dong, Z., Schultz, P., Tang, Y. S., Meng, K., Dong, Z. Y., & Qian, F. (2019) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2019.2931846 · Cited by 119
Decentralized gradient algorithm for solution of a linear equation
Anderson, B. D. O., Mou, S., Morse, A. S., et al. (2016) · Numerical Algebra Control and Optimization · doi:10.3934/naco.2016014 · Cited by 117
Preserving Data-Privacy With Added Noises: Optimal Estimation and Privacy Analysis
He, J., Cai, L., & Guan, X. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2018.2842221 · Cited by 116
Distributed 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
Privacy-Preserving Consensus-Based Energy Management in Smart Grids
Zhao, C., Chen, J., He, J., & Cheng, P. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2872817 · Cited by 121
BRIDGE: Byzantine-Resilient Decentralized Gradient Descent
Fang, C., Yang, Z., & Bajwa, W. U. (2022) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2022.3188456 · Cited by 154
Resilient Distributed Optimization Algorithm Against Adversarial Attacks
Zhao, C., He, J., & Wang, Q. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2954363 · Cited by 126
Shi, X., Cao, J., Wen, G., & Perc, M. (2018) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2018.2850765 · Cited by 111
“For a more general topology, a push-sum method has been put forward in the design of DO algorithms over strongly connected digraph [37]–[41], in which a time-diminishing time-step or parameter is used for the purpose of algorithm convergence,”
MethodA 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
“Its extension, GP (11a)–(11c), to directed graphs adds gradient correction to push-sum consensus [38], [114].”
BackgroundSelf-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
Distributed Optimal Coordination for Distributed Energy Resources in Power Systems
Wu, D. X., Yang, T., Stoorvogel, A. A., & Stoustrup, J. (2016) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2016.2627006 · Cited by 118
Decentralized Consensus Optimization With Asynchrony and Delays
Wu, T., Yuan, K., Ling, Q., Yin, W., & Sayed, A. H. (2018) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2017.2695121 · Cited by 99
Li, H., Wang, Z., Chen, G., et al. (2019) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2019.2945601 · Cited by 105
“Inspired by the gradient push-sum method [19], Yang et al.”
BackgroundMethodPrivacy-Preserving Federated Learning With Malicious Clients and Honest-but-Curious Servers
Le, J., Zhang, D., Lei, X., Jiao, L., Zeng, K., & Liao, X. (2023) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2023.3295949 · Cited by 125
Xiong, Y., Xu, J., You, K., Liu, J., & Wu, L. (2020) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2020.2976273 · Cited by 101
“To conquer the imbalance issue, push-sum-based techniques [18] were developed at the price of introducing additional communications and computations to learn the specific eigenvectors.”
BackgroundMethodDifferentially Private Distributed Online Algorithms Over Time-Varying Directed Networks
Zhu, J., Xu, C., Guan, J., & Wu, D. O. (2018) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2018.2797806 · Cited by 101
Li, 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
“Nedic and Olshevsky [10] proposed a (sub)gradient-push descent algorithm which could find the exact optimal solution even without the knowledge of the number of agents or the graph sequence to implement the assumption that the objective function was (sub)gradient boundedness.”
BackgroundMethodInfluentialLiu, L.-N., & Yang, G. (2021) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2021.3076526 · Cited by 103
LeBlanc, H. J., & Koutsoukos, X. (2017) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2017.2696364 · Cited by 98
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
Stochastic Dual Averaging for Decentralized Online Optimization on Time-Varying Communication Graphs
Lee, S., Nedić, A., & Raginsky, M. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2650563 · Cited by 100
Self-citationLi, H., Lü, Q., & Huang, T. (2018) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2018.2848288 · Cited by 96
A 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
Self-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
“Besides convergence rates, some works have additional focuses, such as time-varying/directed graphs [14], uncoordinated step sizes [15], and stochastic (sub)gradient [16].”
BackgroundOptimization for Reinforcement Learning: From a single agent to cooperative agents
Lee, D., He, N., Kamalaruban, P., & Cevher, V. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2976000 · Cited by 113
Distributed Constrained Optimization and Consensus in Uncertain Networks via Proximal Minimization
Margellos, K., Falsone, A., Garatti, S., & Prandini, M. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2747505 · Cited by 113
Constraint-Coupled Distributed Optimization: A Relaxation and Duality Approach
Notarnicola, I., & Notarstefano, G. (2019) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2019.2925267 · Cited by 99
“Literature has mainly focused on cost-coupled optimization problems in which the cost to be minimized is the sum of local functions depending on a common decision variable, see [12, 13, 18, 22, 24, 25, 27, 32,35,37] and references therein for an overview.”
Sun, Y., Scutari, G., & Daneshmand, A. (2022) · SIAM Journal on Optimization · doi:10.1137/19m1259973 · Cited by 155
Asynchronous Distributed Algorithms for Solving Linear Algebraic Equations
Liu, J., Mou, S., & Morse, A. S. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2714645 · Cited by 95
“One approach to the problem is to reformulate it as a distributed optimization problem [19]–[26].”
BackgroundResultByRDiE: Byzantine-Resilient Distributed Coordinate Descent for Decentralized Learning
Yang, Z., & Bajwa, W. U. (2019) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2019.2928176 · Cited by 172
Bastianello, N., Carli, R., Schenato, L., & Todescato, M. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3011358 · Cited by 119
Distributed 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
Privacy Masking Stochastic Subgradient-Push Algorithm for Distributed Online Optimization
Lü, Q., Liao, X., Xiang, T., Li, H., & Huang, T. (2020) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.2973221 · Cited by 89
“To overcome the imbalance induced by time-varying directed networks, a push-sum mechanism [38], [40] is exploited for designing DP-DSSP in order to counteract the effect of the network’s imbalance.”
BackgroundMethodInfluentialByzantine-Resilient Multiagent Optimization
Su, L., & Vaidya, N. H. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3008139 · Cited by 114
“In fault-free networks (i.e., b = 0 ), one commonly adopted global objective [1], [37], [38] is Unfortunately, when b > 0 , the global objective (1) cannot be minimized.”
BackgroundPrivacy Preservation in Distributed Subgradient Optimization Algorithms
Lou, Y., Yu, L., Wang, S., & Yi, P. (2017) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2017.2728644 · Cited by 101
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
FROST—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
ZONE: Zeroth-Order Nonconvex Multiagent Optimization Over Networks
Hajinezhad, D., Hong, M., & Garcia, A. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2896025 · Cited by 137
Distributed optimization over weighted directed graphs using row stochastic matrix
Mai, V. S., & Abed, E. H. (2016) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2016.7526803 · Cited by 99
Parallel 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
Distributed Algorithms for Computation of Centrality Measures in Complex Networks
You, K., Tempo, R., & Qiu, L. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2604373 · Cited by 97
Pang, Y., & Hu, G. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2914025 · Cited by 85
Metadata
- Authors
- Nedic, A., & Olshevsky, A.
- Affiliations
- University of Illinois Urbana-Champaign (US)
- ORCID
- Olshevsky, Alex
- Venue
- IEEE Transactions on Automatic Control
- Published
- 2015-03
- Volume
- 60
- Issue
- 3
- Pages
- 601-615
- ISSN
- 0018-9286 (ISSN-L)
- 1558-2523
- OpenAlex
- W2137435346
- Cited by
- 1,187
- References
- 33
- Citations by year
- 2026: 67 · 2025: 114 · 2024: 108 · 2023: 125 · 2022: 115 · 2021: 103 · 2020: 138 · 2019: 139 · 2018: 94 · 2017: 89 · 2016: 61 · 2015: 24
- FWCI
- 69.00
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Automatic Control (publishedVersion)
- Funders
- National Science Foundation (NSF) (CMMI 07-42538, CCF 11-11342)
- ONR Navy Basic Research Challenge (N00014-12-1-0998)
- 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 › Engineering › Control and Systems Engineering › Advanced Control Systems Optimization
- Keywords
- distributed optimization, time-varying directed graphs, convex optimization, convergence rate, multi-agent systems
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).
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.