Distributed Optimization Over Time-Varying Directed Graphs
The DOI matches its Crossref record; 35 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: 2
- [29] K.I. Tsianos. The role of the Network in Distributed Optimization Algorithms: Convergence Rates, Scalability, Communication / Computation Tradeoffs and Communication Delays . PhD thesis, McGill University, Dept. of Electrical and Computer Engineering, 2013. -
- [7] F. Iutzeler, P. Ciblat, and W. Hachem. Analysis of sum-weightlike algorithms for averaging inwireless sensor networks. IEEE Transactions on Signal Processing , 6(11), 2013. -
Cited by
Items 201–300 of 1,226
Wang, 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
Distributed 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 67
Doostmohammadian, M., Qureshi, M. I., Khalesi, M. H., Rabiee, H. R., & Khan, U. A. (2025) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2025.3526967 · Cited by 49
Hashemi, 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 73
“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].”
BackgroundOnline Distributed Optimization With Nonconvex Objective Functions via Dynamic Regrets
Lu, K., & Wang, L. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3239432 · Cited by 40
“Distributed optimization has received ever-increasing attention in recent years [1], [2], [3], [4], [5], [6], [7], [8].”
BackgroundBianchi, P., Hachem, W., & Iutzeler, F. (2014) · arXiv (Cornell University) · Cited by 36
An, W., Zhao, P., Liu, H., & Hu, J. F. (2022) · International Journal of Systems Science · doi:10.1080/00207721.2022.2063967 · Cited by 38
Distributed Subgradient Method in Open Multiagent Systems
Hayashi, N. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3230771 · Cited by 43
A 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
“Given any w = [wi]i∈N and {γi}i∈N , the results in [29] immediately imply that for any s ∈ Z+, the vector ( diag(W t,sγ)−1W ⊗Im)D γ w converges to the consensus convex combination vector 1N ⊗ pγ(w) with a geometric rate as t increases.”
InfluentialJena, R., Naik, S. P., Pradhan, B., Beydoun, G., Park, H., & Alamri, A. M. (2021) · International Journal of Disaster Risk Reduction · doi:10.1016/j.ijdrr.2021.102642 · Cited by 41
Distributed Optimization with Dynamic Event-Triggered Mechanisms
Du, W. J., Yi, X., George, J., Johansson, K. H., & Yang, T. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619311 · Cited by 44
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
Nedic, A., & Olshevsky, A. (2014) · arXiv · doi:10.48550/arxiv.1406.2075 · Cited by 38
Self-citationDistributed delay-tolerant strategies for equality-constraint sum-preserving resource allocation
Doostmohammadian, M., Aghasi, A., Vrakopoulou, M., Rabiee, H. R., Khan, U. A., & Charalambous, T. (2023) · Systems & Control Letters · doi:10.1016/j.sysconle.2023.105657 · Cited by 38
Fundamental limitations for anonymous distributed systems with broadcast communications
Hendrickx, J. M., & Tsitsiklis, J. N. (2015) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2015.7446980 · Cited by 37
A tutorial on distributed (non-Bayesian) learning: Problem, algorithms and results
Nedić, A., Olshevsky, A., & Uribe, C. A. (2016) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7799315 · Cited by 39
Self-citationDistributed Optimization for Two Types of Heterogeneous Multiagent Systems
Sun, C., Ye, M., & Hu, G. (2020) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.2984584 · Cited by 37
Push-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 36
“[35] Consider Assumption 1 and let Y∞ := limk→∞ Yk, then |||Yk − Y∞ |||2 ≤ Tλ,∀k, where T := √ h‖1n − nπ‖2 and h := π/π > 1.”
Decentralized online optimization with global objectives and local communication
Nedić, A., Lee, S., & Raginsky, M. (2015) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2015.7172037 · Cited by 43
Self-citationDistributed delayed dual averaging for distributed optimization over time-varying digraphs
Wang, D., Liu, J., Lian, J., Liu, Y., Wang, Z., & Wang, W. (2023) · Automatica · doi:10.1016/j.automatica.2023.110869 · Cited by 38
Carli, R., Notarstefano, G., Schenato, L., & Varagnolo, D. (2015) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402236 · Cited by 32
Zeroth Order Nonconvex Multi-Agent Optimization over NetworksPreprint
Hajinezhad, D., Hong, M., & García, A. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.09997 · Cited by 35
Zhang, J., Liu, L., Ji, H., & Wang, X. (2022) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2022.3191938 · Cited by 36
Private Optimization on Networks
Gade, S., & Vaidya, N. H. (2018) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2018.8430960 · Cited by 46
Multiagent 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
“2874748 rates even if the cost functions are smooth [2]–[4] and do not take into account packet loss explicitly.”
BackgroundDynamics 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
“We compared our algorithm with DIGing [25], AB [45], ADD-OPT [44], and Subgradient-Push [27] to evaluate the influence of privacy design on optimization performance.”
MethodSelf-citationDistributed Online Optimization in Time-Varying Unbalanced Networks Without Explicit Subgradients
Xiong, Y., Li, X., You, K., et al. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3194369 · Cited by 34
Stanković, M. S., & Stanković, S. S. (2016) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2016.7524910 · Cited by 32
Dynamic 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
Lu, J., & Tang, C. Y. (2016) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2016.2594487 · Cited by 36
“Moreover, since problem (1) can be viewed as an unconstrained convex quadratic program, it may be solved using existing distributed convex optimization algorithms, including for example the quantized cyclic incremental [14], subgradient-plus-consensus [15], primal-dual subgradient [16], zero-gradient-sum [17], adaptiv…”
BackgroundDistributed 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
Lei, J., & Shanbhag, U. V. (2022) · SIAM Journal on Optimization · doi:10.1137/20m1340071 · Cited by 35
Surplus-based accelerated algorithms for distributed optimization over directed networks
Wang, D., Wang, Z., Lian, J., & Wang, W. (2022) · Automatica · doi:10.1016/j.automatica.2022.110569 · Cited by 35
Privacy-Preserving Distributed Learning via Obfuscated Stochastic Gradients
Gade, S., & Vaidya, N. H. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619133 · Cited by 46
Ma, T., Deng, Z., & Hu, C. (2022) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2022.3161194 · Cited by 36
A 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
“…(14) can be shown similarly since First, we remark that all vector norms on a finite dimensional vector spaces are equivalent, i.e., there exist κ 1 , κ 2 , κ 3 , κ 4 > 0 such that Similar to the results in [29], we also have (cid:6) V ( k ) − V ∞ (cid:6) ≤ Λ λ k for some 0 Λ ∈ R and λ ∈ (0 , 1) .”
MethodLyapunov Criterion for Stochastic Systems and Its Applications in Distributed Computation
Qin, Y., Cao, M., & Anderson, B. D. O. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2910948 · Cited by 33
Liu, H., Zheng, W. X., & Yu, W. (2020) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2020.3029996 · Cited by 38
“Such result on the convergence rate is common for distributed optimization and can also be found in some existing works, such as [34] and [41].”
ResultDC-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
Byzantine Multi-Agent Optimization: Part IIPreprint
Su, L., & Vaidya, N. H. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1507.01845 · Cited by 40
Olshevsky, A., Paschalidis, I. C., & Spiridonoff, A. (2018) · arXiv (Cornell University) · Cited by 31
Self-citationAsynchronous Decentralized Federated Learning for Heterogeneous Devices
Liao, Y., Xu, Y., Xu, H., Chen, M., Wang, L., & Qiao, C. (2024) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2024.3424444 · Cited by 51
Event-Triggered Discrete-Time Distributed Consensus Optimization over Time-Varying Graphs
Lü, Q., & Li, H. (2017) · Complexity · doi:10.1155/2017/5385708 · Cited by 30
A 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
“Notably, in the recent work [14] and using a perturbed version of the so-called push-sum technique [18], a discretetime dynamics for distributed convex optimization is proposed, which is provably convergent on any sequence of uniformly strongly connected directed graphs.”
MethodResilient 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
Distributed Adaptive Algorithm for Resource Allocation Problem Over Weight-Unbalanced Graphs
Lian, M., Guo, Z., Wen, S., & Huang, T. (2023) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2023.3300736 · Cited by 34
“Forconsensus-baseddistributedoptimiza-tionproblems,distributeddiscrete-timealgorithmsbasedon subgadient/gradientpush-sumandpush-pullmethodsarepre-sentedin[22],[23],[24]and[25],respectively.”
Convergence in High Probability of Distributed Stochastic Gradient Descent Algorithms
Lu, K., Wang, H., Zhang, H., & Wang, L. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3327319 · Cited by 31
“Remark 3: The design of DSGD (7) is motivated by the distributed gradient algorithm [3], [4] and the stochastic gradient algorithm [41], [42], [43], [44].”
BackgroundInfluentialNoise-to-State Exponentially Stable Distributed Convex Optimization on Weight-Balanced Digraphs
Mateos‐Núñez, D., & Cortés, J. (2016) · SIAM Journal on Control and Optimization · doi:10.1137/140978259 · Cited by 30
Coordinate Dual Averaging for Decentralized Online Optimization With Nonseparable Global Objectives
Lee, S., Nedić, A., & Raginsky, M. (2016) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2016.2573639 · Cited by 46
Self-citationMaros, M., & Jaldén, J. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619626 · Cited by 34
Input-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
Interplay Between Topology and Social Learning Over Weak Graphs
Matta, V., Bordignon, V., Santos, A., & Sayed, A. H. (2020) · IEEE Open Journal of Signal Processing · doi:10.1109/ojsp.2020.3006436 · Cited by 33
“INTRODUCTION I n a social learning problem, several agents linked through a network topology form their individual opinions about a phenomenon of interest (learning process) by observing the beliefs of their neighboring agents (social interaction) [2]–[8].”
BackgroundDistributed Actor–Critic Algorithms for Multiagent Reinforcement Learning Over Directed Graphs
Dai, P., Yu, W., Wang, H., & Baldi, S. (2022) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3139138 · Cited by 31
“Lemma 8 [42]: Suppose that the graph sequence {Gt} is uniformly strongly connected.”
BackgroundDistributed projection‐free algorithm for constrained aggregative optimization
Wang, T., & Yi, P. (2023) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.6640 · Cited by 35
Networked 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
Distributed primal-dual methods for online constrained optimization
Lee, S., & Zavlanos, M. M. (2016) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2016.7526804 · Cited by 33
Mo, L., Yu, Y., Zhao, L. H., & Cao, X. (2020) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2019.2961421 · Cited by 30
On the Linear Convergence of Distributed Optimization over Directed Graphs
Xi, C., & Khan, U. A. (2015) · arXiv · doi:10.48550/arxiv.1510.02149 · Cited by 29
Li, C., & Liu, G. P. (2018) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2018.04.003 · Cited by 31
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
Decentralized Online Learning Methods Based on Weight-Balancing Over Time-Varying Digraphs
Xu, C., Zhu, J., & Wu, D. O. (2018) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2018.2880771 · Cited by 30
Li, H., Huang, C., Wang, Z., Chen, G., & Umar, H. G. A. (2020) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2020.2967143 · Cited by 32
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 Over Time-Varying Graphs With Imperfect Sharing of Information
Reisizadeh, H., Touri, B., & Mohajer, S. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3207866 · Cited by 39
Asynchronous Networked Aggregative Games
Zhu, R., Zhang, J., You, K., & Başar, T. (2021) · Automatica · doi:10.1016/j.automatica.2021.110054 · Cited by 29
“Then, the proof is similar to that of Nedić & Olshevsky (2014, Lemma 1).”
MethodResultInfluentialPrivacy-Preserving Distributed ADMM With Event-Triggered Communication
Zhang, Z., Yang, S., Xu, W., & Di, K. (2022) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3192346 · Cited by 32
Lü, 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
“Since this paper considers that agents interact with each other over time-varying directed unbalanced networks, we start by explaining the motivation of DPD-PD according to the existing push-sum method [18].”
BackgroundMethodInfluentialImproved 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-citationCommunication compression techniques in distributed deep learning: A survey
Wang, Z., Wen, M., Xu, Y., Zhou, Y., Wang, J. H., & Zhang, L. (2023) · Journal of Systems Architecture · doi:10.1016/j.sysarc.2023.102927 · Cited by 48
Wang, Z., Wang, D., Lian, J., Ge, H., & Wang, W. (2024) · Automatica · doi:10.1016/j.automatica.2024.111596 · Cited by 30
Decentralized consensus optimization with asynchrony and delays
Wu, T., Yuan, K., Ling, Q. H., Yin, W., & Sayed, A. H. (2016) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2016.7869516 · Cited by 34
Distributed Aggregative Optimization via Finite-time Dynamic Average Consensus
Chen, M., Wang, D., Wang, X., Wu, Z., & Wang, W. (2023) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2023.3253143 · Cited by 27
“The Push-sum algorithm [9] and TV-AB algorithm [10] are further designed to solve the distributed optimization problem over time-varying digraphs.”
MethodWang, A., & Liu, W. (2020) · IEEE Access · doi:10.1109/access.2020.2966078 · Cited by 28
Doan, T. T., Beck, C. L., & Srikant, R. (2017) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3154496 · Cited by 40
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
Distributed Estimation Under Sensor Attacks: Linear and Nonlinear Measurement Models
Meng, M., Li, X., & Xiao, G. (2021) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2021.3054981 · Cited by 29
“Consequently, by reviewing the results in [37] and noting that the initial value of x i ( t ) is x i (0) = 0 M , one can find positive numbers C > 0 and 0 λ 1 such that for all t ≥ 1 , where Assumption 5 and (5) are used to get the second and third inequalities, respectively.”
BackgroundMethodDistributed 3D Deployment of Aerial Base Stations for On-Demand Communication
Kimura, T., & Ogura, M. (2021) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2021.3086815 · Cited by 27
Distributed Online Bandit Learning in Dynamic Environments Over Unbalanced Digraphs
Li, J., Li, C., Yu, W., Zhu, X., & Yu, X. (2021) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2021.3093536 · Cited by 27
Algorithm-Level Confidentiality for Average Consensus on Time-Varying Directed Graphs
Gao, H. B., & Wang, Y. (2022) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2022.3140274 · Cited by 30
A Collaborative Neurodynamic Optimization Approach to Distributed Chiller Loading
Chen, Z., Wang, J., & Han, Q. (2023) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2023.3245812 · Cited by 29
Network flows that solve least squares for linear equations
Liu, Y., Lou, Y., Anderson, B. D. O., & Shi, G. (2020) · Automatica · doi:10.1016/j.automatica.2020.109108 · Cited by 28
“It is clear that (3) has exactly the same structure as the flow in [18, 19] in the sense that they are both in the form of “local averaging consensus” + “diminishing local objective”, with the difference that the flow in [18,19] is discrete-time but (3) is continuous-time.”
BackgroundMethodDistributed optimization of multi-integrator agent systems with mixed neighbor interactions
Chen, Z., Nian, X., & Meng, Q. R. (2023) · Automatica · doi:10.1016/j.automatica.2023.111245 · Cited by 25
A distributed algorithm for solving a linear algebraic equation
Mou, S., Liu, J., & Morse, A. S. (2013) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2013.6736534 · Cited by 27
Gradient-Consensus Method for Distributed Optimization in Directed Multi-Agent Networks
Khatana, V., Saraswat, G., Patel, S., & Salapaka, M. V. (2020) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc45564.2020.9147544 · Cited by 30
Enhancing Decentralized Federated Learning for Non-IID Data on Heterogeneous Devices
Chen, M., Xu, Y., Xu, H., & Huang, L. (2023) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde55515.2023.00177 · Cited by 43
“The time-varying graph (i.e., the communication topology) is B -bounded strongly connected to ensure the convergence of model training [31], [38].”
BackgroundMethodDistributed Constrained Online Learning
Paternain, S., Lee, S., Zavlanos, M. M., & Ribeiro, A. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2999671 · Cited by 23
Fast decentralized gradient descent method and applications to in-situ seismic tomography
Zhao, L., Song, W., & Ye, X. (2015) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata.2015.7363839 · Cited by 24
Approximate Projection Methods for Decentralized Optimization With Functional Constraints
Lee, S., & Zavlanos, M. M. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2778696 · Cited by 25
“Changes in Lemma 4: Combining with the results in [5], [16], and [55]–[58], Lemma 4 still holds in this case by replacing θ̄k with θ̂k ∑ i∈V [π]iθi,k and redefining the constants γ and β as γ = 2, β = 1 − 1 NN .”
Feng, Y., Zhang, W., Xiong, J., Li, H., & Rutkowski, L. (2020) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2019.2963330 · Cited by 25
Distributed Nonconvex Event-Triggered Optimization Over Time-Varying Directed Networks
Mao, S., Dong, Z., Du, W., Tian, Y., Liang, C., & Tang, Y. S. (2021) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2021.3103747 · Cited by 25
“Lemma 1 (see [7]): For strongly connected graphs {G ( t ) } , the following inequality is always true: where the vector φ ( t ) is stochastic, 0 ≤ k ≤ t , C > 0 is a constant and λ ∈ ( 0 , 1 ) .”
BackgroundMethodResultInfluentialWang, C., Xu, S., Yuan, D., Zhang, B., & Zhang, Z. (2022) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2022.3200680 · Cited by 24
“For distributed optimization, gradient descent methods are very common applied algorithms [9], [10], [11], [12], [13], [14].”
BackgroundMethodInfluentialDistributed Big-Data Optimization via Blockwise Gradient Tracking
Notarnicola, I., Sun, Y., Scutari, G., & Notarstefano, G. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3008713 · Cited by 26
Segovia, P., Puig, V., Duviella, É., et al. (2021) · Journal of Process Control · doi:10.1016/j.jprocont.2021.01.007 · Cited by 24
Jiang, X., Zeng, X., Sun, J. Q., & Chen, J. (2022) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3170944 · Cited by 28
Multi/Single-Stage Sliding Manifold Approaches for Prescribed-Time Distributed Optimization
Zhou, S., Wei, Y., Cao, J., & Liu, Y. (2024) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2024.3504355 · Cited by 27
Network independent rates in distributed learning
Nedić, A., Olshevsky, A., & Uribe, C. A. (2016) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2016.7525057 · Cited by 24
Self-citationByzantine-Resilient Decentralized Policy Evaluation With Linear Function Approximation
Wu, Z., Shen, H., Chen, T., & Ling, Q. H. (2021) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2021.3090952 · Cited by 40
Garg, K., Baranwal, M., & Panagou, D. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9303778 · Cited by 27
“point of F (·) or its neighborhood [1], [11], [12].”
BackgroundSolving leaderless multi-cluster games over directed graphs
Zimmermann, J., Tatarenko, T., Willert, V., et al. (2021) · European Journal of Control · doi:10.1016/j.ejcon.2021.06.007 · Cited by 23
Distributed decision-coupled constrained optimization via Proximal-Tracking
Falsone, A., & Prandini, M. (2021) · Automatica · doi:10.1016/j.automatica.2021.109938 · Cited by 29
Distributed Stochastic Approximation: Weak Convergence and Network Design
Stanković, M. S., Ilić, N., & Stankovic, S. S. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2545098 · Cited by 27
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.