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 101–200 of 1,226
Distributed Optimal Dispatch of Distributed Energy Resources Over Lossy Communication Networks
Wu, J., Yang, T., Wu, D. X., Kalsi, K., & Johansson, K. H. (2017) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2017.2720761 · Cited by 89
“In [17], a distributed algorithm based on the push-sum and (sub)gradient method was developed to solve the optimization problem over directed time-varying communication networks.”
InfluentialA 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
Distributed Discrete-Time Optimization in Multiagent Networks Using Only Sign of Relative State
Zhang, J., You, K., & Başar, T. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2884998 · Cited by 86
Lin, P., Ren, W., Yang, C., & Gui, W. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2910946 · Cited by 92
Stochastic Proximal Gradient Consensus Over Random Networks
Hong, M., & Chang, T. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2673815 · Cited by 85
“It is the stochastic varian t of the so-calledB-strongly connected network which has been widely considered in the literature, under ve ry different context [1], [7], [18], [31].”
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
“1) Inspired by the push-sum and gradient method [23], we first propose a distributed algorithm with diminishing step sizes and show that the proposed distributed algorithm with the properly chosen step sizes is capable of achieving the optimal DER coordination if the timevarying directed communication network is unifo…”
BackgroundMethodInfluentialHua, H., Wei, Z., Qin, Y., Wang, T., Li, L., & Cao, J. (2021) · IET Cyber-Physical Systems Theory & Applications · doi:10.1049/cps2.12007 · Cited by 85
Li, H., Lü, Q., Chen, G., Huang, T., & Dong, Z. Y. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2994024 · Cited by 81
1 Nonasymptotic Convergence Rates for Cooperative Learning Over Time-Varying Directed GraphsPreprint
Olshevsky, A., & Uribe, C. A. (2016) · Cited by 76
Self-citationOn the distributed optimization over directed networks
Xi, C., Wu, Q., & Khan, U. A. (2017) · Neurocomputing · doi:10.1016/j.neucom.2017.06.038 · Cited by 84
“The black curve shows he convergence behavior of the subgradient-push algorithm, proosed in [15,16] .”
BackgroundExtraPush for Convex Smooth Decentralized Optimization over Directed Networks
Zeng, J., & Yin, W. (2017) · Journal of Computational Mathematics · doi:10.4208/jcm.1606-m2015-0452 · Cited by 82
A 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
“In contrast to [51] (doubly stochastic matrix) and [39]–[50] (column-stochastic matrix), D-DNGT with row-stochastic matrix, is relatively easy to be achieved in a distributed way if each unit can privately regulate the weights on information which acquires from in-neighbors.”
BackgroundMethodInfluentialDistributed Submodular Maximization With Limited Information
Gharesifard, B., & Smith, S. L. (2016) · IEEE Transactions on Control of Network Systems · doi:10.1109/acc.2016.7525053 · Cited by 80
AsySPA: 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
Harnessing smoothness to accelerate distributed optimization
Qu, G., & Li, N. (2016) · 2016 IEEE 55th Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798263 · Cited by 72
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
“The work on directed graphs [21], [22], [25]–[28] requires Perron eigenvector estimation [29], [30].”
BackgroundExponential convergence of a distributed algorithm for solving linear algebraic equations
Liu, J., Morse, A. S., Nedić, A., & Başar, T. (2017) · Automatica · doi:10.1016/j.automatica.2017.05.004 · Cited by 67
Self-citationDistributed Algorithm Design for Nonsmooth Resource Allocation Problems
Deng, Z., Nian, X., & Hu, C. (2019) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2019.2901256 · Cited by 71
Sun, H., & Hong, M. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2943230 · Cited by 85
“(b) B = 200,K = 10, = 10−15 Figure 17: Comparison of NEXT and xFILTER over path graphs with increasing number of nodes (M ∈ [10, 150] in (a) and M ∈ [5, 50] in (b)).”
BackgroundAnalysis of Consensus-Based Economic Dispatch Algorithm Under Time Delays
Zhao, C., Duan, X., & Shi, Y. (2018) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2018.2840821 · Cited by 69
Virtual Power Plants for Grid Resilience: A Concise Overview of Research and Applications
Xie, Y., Zhang, Y., Lee, W., Lin, Z., & Shamash, Y. (2024) · IEEE/CAA Journal of Automatica Sinica · doi:10.1109/jas.2024.124218 · Cited by 88
Distributed Proximal Algorithms for Multiagent Optimization With Coupled Inequality Constraints
Li, X., Feng, G., & Xie, L. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2989282 · Cited by 75
“According to Lemma 1 in [23] without perturbations or errors, it can be concluded that zi,k+1 → ωi,k+1 ∑N j=1 zj,k/N exponentially.”
InfluentialOnline Distributed Optimization With Strongly Pseudoconvex-Sum Cost Functions
Lu, K., Jing, G., & Wang, L. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2915745 · Cited by 65
Perturbed proximal primal–dual algorithm for nonconvex nonsmooth optimization
Hajinezhad, D., & Hong, M. (2019) · Mathematical Programming · doi:10.1007/s10107-019-01365-4 · Cited by 62
Survey 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
Push-Based Distributed Economic Dispatch in Smart Grids Over Time-Varying Unbalanced Directed Graphs
Wang, Z., Wang, D., Wen, C., Guo, F., & Wang, W. (2021) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2021.3063128 · Cited by 69
“Proof: The subsequent analysis is similar to the previous work [32].”
BackgroundResultInfluentialExtraPush for convex smooth decentralized optimization over directed networks
Zeng, J., & Yin, W. (2015) · arXiv · doi:10.48550/arxiv.1511.02942 · Cited by 65
Gradient‐free method for distributed multi‐agent optimization via push‐sum algorithms
Yuan, D., Xu, S., & Lu, J. (2014) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.3164 · Cited by 59
“In recent years, the problem of minimizing the sum of convex functions that all share a common decision variable has attracted a lot of research attention [1–12].”
BackgroundMethodInfluentialNonasymptotic convergence rates for cooperative learning over time-varying directed graphs
Nedić, A., Olshevsky, A., & Uribe, C. A. (2015) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2015.7172262 · Cited by 96
Self-citationGuo, F., Li, G., Wen, C., et al. (2019) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2019.2936829 · Cited by 62
Byzantine-Resilient Decentralized Stochastic Optimization With Robust Aggregation Rules
Wu, Z., Chen, T., & Ling, Q. H. (2023) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2023.3300629 · Cited by 97
“Existing methods such as pushsum [37] and push-pull [38] copes with non-doubly stochastic mixing matrices with correction techniques, but they incur additional transmissions that increase the difficulty of defending against Byzantine attacks.”
MethodDual 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
“Also, compared with [17], our method further addresses constrained problems.”
BackgroundMethodSingle-Bit Consensus With Finite-Time Convergence: Theory and Applications
Doostmohammadian, M. (2020) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2020.2965811 · Cited by 60
Distributed economic dispatch via a predictive scheme: Heterogeneous delays and privacy preservation
Chen, F., Chen, X., Xiang, L., et al. (2020) · Automatica · doi:10.1016/j.automatica.2020.109356 · Cited by 60
Distributed resource allocation via multi-agent systems under time-varying networks
Lu, K., Xu, H., & Zheng, Y. (2021) · Automatica · doi:10.1016/j.automatica.2021.110059 · Cited by 62
Graph balancing for distributed subgradient methods over directed graphs
Makhdoumi, A., & Ozdaglar, A. (2015) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402401 · Cited by 64
Distributed Algorithms for Robust Convex Optimization via the Scenario Approach
You, K., Tempo, R., & Xie, P. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2828093 · Cited by 68
“In comparison, the algorithm in [20] only focuses on the unconstrained optimization, involves nonlinear iterations and requires the updates of four vectors.”
MethodCentral Server Free Federated Learning over Single-sided Trust Social Networks
He, C., Tan, C., Tang, H., Qiu, S., & Liu, J. (2019) · arXiv · doi:10.48550/arxiv.1910.04956 · Cited by 60
“, 2018), and time-varying (Nedić and Olshevsky, 2015; Lian et al., 2018) during training.”
Lü, Q., Li, H., & Xia, D. (2017) · Neurocomputing · doi:10.1016/j.neucom.2017.01.021 · Cited by 60
A Bregman Splitting Scheme for Distributed Optimization Over Networks
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2805260 · Cited by 62
Assran, M. S., & Rabbat, M. G. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2981035 · Cited by 101
“Nedi´c and Olshevsky [21] continue this line of work by introducing and analyzing the Subgradient-Push method; the analysis in [21] focuses on minimizing (weakly) convex, Lip-schitz functions, for which diminishing step-sizes are required to obtain convergence.”
InfluentialDistributed Randomized Gradient-Free Mirror Descent Algorithm for Constrained Optimization
Yu, Z., Ho, D. W. C., & Yuan, D. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3075669 · Cited by 62
Decentralised federated learning with adaptive partial gradient aggregation
Jiang, J., & Hu, L. (2020) · CAAI Transactions on Intelligence Technology · doi:10.1049/trit.2020.0082 · Cited by 64
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
“, GP [20], [21], ADDOPT [14], [31], and SGP [16], [25], [26].”
Consensus-based distributed optimization with malicious nodes
Sundaram, S., & Gharesifard, B. (2015) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2015.7447011 · Cited by 60
“There is a vast literature devoted to designing distributed algorithms, both in discrete and continuous-time, that guarantee convergence to an optimizer of the sum of the objective functions, under reasonable convexity and continuity assumptions [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12].”
BackgroundDistributed Averaging and Balancing in Network Systems
Hadjicostis, C. N., Domínguez-García, A. D., & Charalambous, T. (2018) · Foundations and Trends® in Systems and Control · doi:10.1561/2600000016 · Cited by 74
Lü, Q., Li, H., & Xia, D. (2017) · Information Sciences · doi:10.1016/j.ins.2017.09.038 · Cited by 56
A 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
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
“The extension of the DGD algorithm to digraphs was proposed in [19] for convex unconstrained optimization, and later extended in [31] to nonconvex objectives.”
MethodLiu, H., Yu, W., & Chen, G. (2020) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.3022240 · Cited by 55
Lü, Q., & Li, H. (2016) · arXiv · doi:10.48550/arxiv.1611.00990 · Cited by 54
Robust Distributed Estimation by Networked Agents
Al-Sayed, S., Zoubir, A. M., & Sayed, A. H. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2703664 · Cited by 52
Push-Sum Distributed Online Optimization With Bandit Feedback
Wang, C., Xu, S., Yuan, D., Zhang, B., & Zhang, Z. (2022) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.2999309 · Cited by 53
Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning
Elgabli, A., Park, J., Bedi, A. S., Issaid, C. B., Bennis, M., & Aggarwal, V. (2021) · IEEE Transactions on Communications · doi:10.1109/tcomm.2020.3026398 · Cited by 51
Wang, X., Teel, A. R., Liu, K., & Sun, X. (2019) · Automatica · doi:10.1016/j.automatica.2019.108607 · Cited by 51
Edge-Based Stochastic Gradient Algorithm for Distributed Optimization
Wang, Z., & Li, H. (2019) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2019.2933177 · Cited by 49
Yu, W., Liu, H., Zheng, W. X., & Zhu, Y. (2021) · Automatica · doi:10.1016/j.automatica.2021.109899 · Cited by 53
An Event-Triggered Approach for Gradient Tracking in Consensus-Based Distributed Optimization
Gao, L., Deng, S., Li, H., & Li, C. (2021) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2021.3122927 · Cited by 51
Quantized Distributed Gradient Tracking Algorithm With Linear Convergence in Directed Networks
Xiong, Y., Wu, L., You, K., & Xie, L. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3219289 · Cited by 53
Deng, Z., & Luo, J. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3301957 · Cited by 48
Kajiyama, Y., Hayashi, N., & Takai, S. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2989281 · Cited by 47
Distributed Resource Allocation Over Dynamic Networks With Uncertainty
Doan, T. T., & Beck, C. L. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3041248 · Cited by 50
Distributed Nash Equilibrium Seeking for Aggregative Games With Directed Communication Graphs
Fang, X., Wen, G., Zhou, J., Lü, J., & Chen, G. (2022) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2022.3168770 · Cited by 57
Wang, D., Yin, J., & Wang, W. (2019) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2018.2890140 · Cited by 47
“The SP method combined with push-sum consistence is proposed to solve the smooth optimization problem and the weight adjacent matrix is column stochastic based on outneighbors information in [9].”
BackgroundMethodInfluentialAnalysis of Distributed ADMM Algorithm for Consensus Optimization in Presence of Node Error
Majzoobi, L., Lahouti, F., & Shah‐Mansouri, V. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2896266 · Cited by 48
Wang, D., Chen, M., & Wang, W. (2019) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2018.2890115 · Cited by 49
Spatially distributed sampling and reconstruction
Cheng, C., Jiang, Y., & Sun, Q. (2017) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2017.07.007 · Cited by 53
A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks
Pu, S. (2020) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc42340.2020.9303917 · Cited by 60
Chen, W., Wang, Z., Dong, H., Mao, J., & Liu, G. P. (2023) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2023.3321027 · Cited by 51
“Lemma 1 ([40] and [41]): Under Assumption 1, there exist a scalar γ ∈ ( 0 , 1 ) and a stochastic vector with K ≥ 4.”
BackgroundLiang, S., Wang, L. Y., & Yin, G. (2018) · Automatica · doi:10.1016/j.automatica.2018.11.056 · Cited by 43
Mitra, A., Richards, J. A., & Sundaram, S. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3033126 · Cited by 48
“While the above assumption on the network connectivity pattern is not necessary for solving the problem at hand, it is fairly standard in the analysis of distributed algorithms over time-varying networks [10, 22, 23].”
BackgroundPredefined-time optimization for distributed resource allocation
Lin, W.-T., Wang, Y., Li, C., & Yu, X. (2019) · Journal of the Franklin Institute · doi:10.1016/j.jfranklin.2019.06.024 · Cited by 47
Distributed Gradient Tracking for Unbalanced Optimization With Different Constraint Sets
Cheng, S., Liang, S., Fan, Y. C., & Hong, Y. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3192316 · Cited by 46
Preserving Strong Connectivity in Directed Proximity Graphs
Poonawala, H. A., & Spong, M. W. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2671352 · Cited by 48
Distributed extremum-seeking control over networks of dynamically coupled unstable dynamic agents
Guay, M., Vandermeulen, I., Dougherty, S. P., & McLellan, P. J. (2018) · Automatica · doi:10.1016/j.automatica.2018.03.081 · Cited by 46
Distributed optimal resource allocation over strongly connected digraphs: A surplus-based approach
Chen, G., & Li, Z. (2021) · Automatica · doi:10.1016/j.automatica.2020.109459 · Cited by 46
Yi, X., Li, X., Yang, T., Xie, L., Chai, T., & Johansson, K. H. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2022.3230766 · Cited by 44
Xian, C., Zhao, Y., Wen, G., & Chen, G. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3335797 · Cited by 46
Multi-agent mirror descent for decentralized stochastic optimization
Rabbat, M. (2015) · IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing · doi:10.1109/camsap.2015.7383850 · Cited by 43
Decentralized Consensus Algorithm with Delayed and Stochastic Gradients
Sirb, B., & Ye, X. (2018) · SIAM Journal on Optimization · doi:10.1137/16m1081257 · Cited by 52
Fenchel Dual Gradient Methods for Distributed Convex Optimization Over Time-Varying Networks
Wu, X., & Lu, J. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2901829 · Cited by 47
Byzantine-Resilient Distributed Optimization of Multi-Dimensional Functions
Kuwaranancharoen, K., Xin, L., & Sundaram, S. (2020) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc45564.2020.9147396 · Cited by 50
Distributed Optimization Methods for Multi-Robot Systems: Part 1—A Tutorial [Tutorial]
Shorinwa, O., Halsted, T., Yu, J., & Schwager, M. (2024) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2024.3358718 · Cited by 90
He, X., Yu, J., Huang, T., Li, C., & Li, C. (2018) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2018.2869249 · Cited by 42
Distributed Signal Processing and Optimization Based on In-Network Subspace Projections
Lorenzo, P. D., Barbarossa, S., & Sardellitti, S. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2981204 · Cited by 48
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning
Elgabli, A., Park, J., Bedi, A. S., Bennis, M., & Aggarwal, V. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.00047 · Cited by 42
“On the other hand, there are a variety of distributed optimization algorithms proposed in the literature, such as primal methods (Jakovetić et al., 2014; Nedić and Olshevsky, 2014; Nedić and Ozdaglar, 2009; Shi et al., 2015) and primal-dual methods (Chang et al.”
MethodDistributed Privacy Preserving Algorithm for Economic Dispatch Over Time-Varying Communication
Zhao, D., Liu, D., & Liu, L. (2023) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2023.3246998 · Cited by 42
“Lemma 3: ([33], [34]).”
Online Learning Over Dynamic Graphs via Distributed Proximal Gradient Algorithm
Dixit, R., Bedi, A. S., & Rajawat, K. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3033712 · Cited by 47
“However, {Gt} is still required to be uniformly strongly connected or B-connected [17]; see Sec.”
BackgroundMethodJin, B., Li, H., Yan, W., & Cao, M. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3021528 · Cited by 47
Accelerated $AB$/Push–Pull Methods for Distributed Optimization Over Time-Varying Directed Networks
Nguyen, D. T. A., Nguyen, D. T., & Nedić, A. (2023) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2023.3338236 · Cited by 63
Self-citationChen, W., Wang, Z., Liu, Q., Yue, D., & Liu, G. P. (2024) · Automatica · doi:10.1016/j.automatica.2024.111715 · Cited by 48
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
Nedić, A., & Olshevsky, A. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2529285 · Cited by 181
Self-citationByzantine-robust decentralized stochastic optimization over static and time-varying networks
Peng, J., Li, W., & Ling, Q. H. (2021) · Signal Processing · doi:10.1016/j.sigpro.2021.108020 · Cited by 59
DiNNO: Distributed Neural Network Optimization for Multi-Robot Collaborative Learning
Yu, J., Vincent, J. A., & Schwager, M. (2022) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2022.3142402 · Cited by 58
“Subsequent research has focused on improving convergence rates [12] and extending analysis to a broader range of problems including timevarying communication graphs [13], and online or streaming convex objectives [14].”
Differentially Private Distributed Optimization With an Event-Triggered Mechanism
Mao, S., Yang, M., Yang, W. D., Tang, Y. S., Zheng, W. X., Gu, J., & Werner, H. (2023) · IEEE Transactions on Circuits and Systems I Regular Papers · doi:10.1109/tcsi.2023.3266358 · Cited by 40
“Lemma 1 ([24]): If directed graphs G(t) are strongly connected, then, for some stochastic vector 8(t), 0 ≤ k ≤ t , some constant M > 0 and β ∈ (0, 1), there holds ∥[A(t)A(t − 1) · · · A(k + 1)A(k)]i j −8 j (k)∥ ≤ Mβ t−k .”
BackgroundMethodInfluentialDistributed Collaborative 3D-Deployment of UAV Base Stations for On-Demand Coverage
Kimura, T., & Ogura, M. (2020) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom41043.2020.9155283 · Cited by 45
Differentially private distributed online learning over time‐varying digraphs via dual averaging
Han, D., Liu, K., Lin, Y., et al. (2021) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.5635 · Cited by 40
“33 ).”
Distributed Support Vector Machines Over Dynamic Balanced Directed Networks
Doostmohammadian, M., Aghasi, A., Charalambous, T., & Khan, U. A. (2021) · IEEE Control Systems Letters · doi:10.1109/lcsys.2021.3086388 · Cited by 46
Privacy-Preserving Dual Averaging With Arbitrary Initial Conditions for Distributed Optimization
Han, D., Liu, K., Sandberg, H., Chai, S., & Xia, Y. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3097295 · Cited by 40
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.