Asynchronous Broadcast-Based Convex Optimization Over a Network
The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Abstract
We consider a distributed multi-agent network system where each agent has its own convex objective function, which can be evaluated with stochastic errors. The problem consists of minimizing the sum of the agent functions over a commonly known constraint set, but without a central coordinator and without agents sharing the explicit form of their objectives. We propose an asynchronous broadcast-based algorithm where the communications over the network are subject to random link failures. We investigate the convergence properties of the algorithm for a diminishing (random) stepsize and a constant stepsize, where each agent chooses its own stepsize independently of the other agents. Under some standard conditions on the gradient errors, we establish almost sure convergence of the method to an optimal point for diminishing stepsize. For constant stepsize, we establish some error bounds on the expected distance from the optimal point and the expected function value. We also provide numerical results.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
Olfati-Saber, R., & Murray, R. M. (2004) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2004.834113 · Cited by 12,788 · cited 1×
“Since we are dealing with a random broadcast scheme for consensus, on a broader scale our work in this paper is related to the literature on distributed consensus and averaging [30], [31], [3], [12], [22], [32], [15], [18], [21].”
BackgroundCoordination 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
PE, & Billingsley, P. (1996) · Journal of the American Statistical Association · doi:10.2307/2291440 · Cited by 6,481
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
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 1×
“The agent (that has just updated the iterate) passes the iterate to a randomly selected neighbor to perform the next update.”
BackgroundBoyd, S., Ghosh, A., Prabhakar, B., & Shah, D. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.874516 · Cited by 2,439 · cited 1×
“As in [6], [7], [27], we find it easier to study the algorithm in terms of a single virtual clock that ticks whenever any of the local Poisson clock ticks.”
BackgroundConvex Analysis and Optimization
Bertsekas, D. P., Nedić, A., & Ozdaglar, A. (2003) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 2,148
Constrained Consensus and Optimization in Multi-Agent Networks
Nedic, A., Ozdaglar, A., & Parrilo, P. A. (2010) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2041686 · Cited by 2,086 · cited 1×
“this paper is related to the literature on distributed consensus and averaging [10], [11], [15]–[17], [19]–[22].”
BackgroundDistributed 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
(1989) · Choice Reviews Online · doi:10.5860/choice.26-5109 · Cited by 1,755
Research works printed but not linked: 2
- lobel, 2008, Distributed subgradient methods over random networks
- ram, 2010, Sensor Networks When Theory Meets Practice
Cited by
An Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination
Cao, Y., Yu, W., Ren, W., & Chen, G. (2013) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2012.2219061 · Cited by 2,399
“Further results in this topic can be found in [244]–[246], where a similar distributed multi-agent optimization problem was studied within various scenarios , such as under constraints [ 244], over random networks [ 245], and with broadcast-based communications in an asynchronou s setting [246].”
BackgroundDistributed Optimization Over Time-Varying Directed Graphs
Nedic, A., & Olshevsky, A. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2364096 · Cited by 1,187
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
Fast Distributed Gradient Methods
Jakovetic, D., Xavier, J., & Moura, J. M. F. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2298712 · Cited by 624
Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
Chang, T.-H., Nedic, A., & Scaglione, A. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2308612 · Cited by 401
Distributed Asynchronous Constrained Stochastic Optimization
Srivastava, K., & Nedic, A. (2011) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2011.2118740 · Cited by 350
Distributed Algorithms for Aggregative Games on Graphs
Koshal, J., Nedić, A., & Shanbhag, U. V. (2016) · Operations Research · doi:10.1287/opre.2016.1501 · Cited by 341
“This idea has attracted a lot of attention recently in an effort to extend the algorithm of [57] to more general and broader range of problems [35, 46, 45, 19, 18, 36, 54, 33, 26, 58, 48, 59, 5].”
BackgroundMethodInfluentialXu, 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
“In [21], an asynchronous broadcast-based algorithm is designed to handle the problem of random link failures as well as uncoordinated update over random networks.”
Method1Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed GraphsPreprint
Nedić, A., & Olshevsky, A. (2016) · Cited by 316
Distributed Nash equilibrium seeking: A gossip-based algorithm
Salehisadaghiani, F., & Pavel, L. (2016) · Automatica · doi:10.1016/j.automatica.2016.06.004 · Cited by 309
“By Lemma 2 in Nedic (2011), γ 1.”
BackgroundInfluentialDecentralized Federated Learning: A Survey and Perspective
Yuan, L., Wang, Z., Sun, L., Yu, P. S., & Brinton, C. G. (2024) · IEEE Internet of Things Journal · doi:10.1109/jiot.2024.3407584 · Cited by 290
“The broadcast protocol is a one-peer-to-all-peers approach that allows the client to broadcast its model to all clients [147].”
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
Distributed multi-agent optimization subject to nonidentical constraints and communication delays
Lin, P., Ren, W., & Song, Y. (2016) · Automatica · doi:10.1016/j.automatica.2015.11.014 · Cited by 249
Convergence of a Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex Optimization
Bianchi, P., & Jakubowicz, J. (2013) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2012.2209984 · Cited by 245
“In order to distinguish both broadcast algorithms, we will designate the algorithm of [23] as the broadcast algorithm with sleeping phases, referring to the fact that each agent does not update its estimates as long as it is not the recipient of a message.”
BackgroundMethodInfluentialLi, Z., Shi, W., & Yan, M. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2926022 · Cited by 244
“It and its variants [16, 33] are intuitive and simple but usually slow due to the diminishing step-size that is needed to obtain a consensual and optimal solution, even if the objective functions are differentiable and strongly convex.”
BackgroundEvent-triggered zero-gradient-sum distributed consensus optimization over directed networks
Chen, W., & Ren, W. (2016) · Automatica · doi:10.1016/j.automatica.2015.11.015 · Cited by 234
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
“74 These methods have the advantage of being easily distributed, 75 to have limited computational requirements and to be inherently 76 asynchronous as shown in [30], [31], [32].”
MethodConvergence 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
“In particular, an asynchronous broadcast-based algorithm has been designed to deal with random link failures as well as uncoordinated updates [33].”
BackgroundMethodInfluentialCommunication-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
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
“Our work here contributes to the growing literature on distributed methods for optimization over networks [5], [9], [12], [14]–[16], [19]–[23], [28], [32], [34], [40], [43].”
MethodA Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimization
Bianchi, P., Hachem, W., & Iutzeler, F. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2512043 · Cited by 180
“- ABG: the asynchronous broadcast gradient [39].”
Quantized Subgradient Algorithm and Data-Rate Analysis for Distributed Optimization
Yi, P., & Hong, Y. (2014) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2014.2357513 · Cited by 169
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
“Gossip [15], [16] Reduced No Yes Average Consensus Yes Randomized Consensus [17], [18] Reduced No Yes Average Consensus Yes Randomized DGD [19], [26] Reduced No Yes Aggregate Optimization No Asynchronous Diffusion [27]–[29] Reduced No Yes Aggregate stochastic Optimization No Randomized ADMM [20], [22], [25] Reduced No…”
BackgroundGeometrically convergent distributed optimization with uncoordinated step-sizes
Nedic, A., Olshevsky, A., Shi, W., & Uribe, C. A. (2017) · 2017 American Control Conference (ACC) · doi:10.23919/acc.2017.7963560 · Cited by 145
“Initial approaches for general and possibly time-varying graphs were based in distributed sub-gradients with extensions to handle stochasticity and asynchronous updates [11]–[13].”
BackgroundBalancing Communication and Computation in Distributed Optimization
Berahas, A. S., Bollapragada, R., Keskar, N. S., & Wei, E. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2880407 · Cited by 136
“A number of later contributions [15], [16], [17], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30] extended DGD to other settings, including stochastic networks, constrained problems, and noisy environments.”
BackgroundErgodic Randomized Algorithms and Dynamics Over Networks
Ravazzi, C., Frasca, P., Tempo, R., & Ishii, H. (2014) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2014.2367571 · Cited by 129
“Venues for applicat ion include gossip algorithms to solve problems of simultaneou s estimation and classification in sensor networks [39], conv ex optimization [37], and optimization in power networks [40] .”
MethodDistributed 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
Performance of a Distributed Stochastic Approximation Algorithm
Bianchi, P., Fort, G., & Hachem, W. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2275131 · Cited by 122
“It is known that convergence of stochastic approximation algorithms to an attractive set is established provided that the sequence remains in a compact set with probability one and is, with probability one, infinitely often in the domain of attraction of this attractive set.”
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
Randomized Gradient-Free Method for Multiagent Optimization Over Time-Varying Networks
Yuan, D., & Ho, D. W. C. (2014) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2014.2336806 · Cited by 121
“From a different viewpoint, [22] develops an asynchronous distributed algorithm for the multiagent optimization problem; they also establish convergence results of the algorithm.”
BackgroundAchieving Linear Convergence in Distributed Asynchronous Multiagent Optimization
Tian, Y., Sun, Y., & Scutari, G. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2977940 · Cited by 120
“(c) Random/cyclic activations and some form of delays [4]– [10]: The class of optimization problems along with the key features of the algorithms proposed in these papers are summarized in Table 1 and briefly discussed next.”
BackgroundMethodInfluentialOptimization 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
“Other distributed optimization algorithms include the exact first-order algorithm for decentralized consensus optimization [46], push-sum algorithm [47] for directed graph models, and gossip-based algorithm [48], among others.”
MethodRobustness Analysis of Asynchronous Sampled-Data Multiagent Networks With Time-Varying Delays
Xiao, F., Shi, Y., & Ren, W. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2756860 · Cited by 112
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
Newton-Raphson consensus for distributed convex optimization
Zanella, F., Varagnolo, D., Cenedese, A., Pillonetto, G., & Schenato, L. (2011) · IEEE Conference on Decision and Control and European Control Conference · doi:10.1109/cdc.2011.6160605 · Cited by 96
“These methods have the advantage of being easily distributed, to have limited computational requirements and to be inherently asynchronous as shown in [31], [32], [33].”
MethodConvergence Rate of Distributed Averaging Dynamics and Optimization in Networks
Nedić, A. (2015) · Foundations and Trends® in Systems and Control · doi:10.1561/2600000004 · Cited by 105
Gossip Dual Averaging for Decentralized Optimization of Pairwise FunctionsPreprint
Colin, I., Bellet, A., Salmon, J., & Clémençon, S. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1606.02421 · Cited by 103
“Since (δk(t))t≥1 is a Bernoulli process of parameter 1/pk, by the law of iterative logarithms (Dudley, 2010), (Nedić, 2011, Lemma 3) one has with probability 1 and for any q > 0 lim t→+∞ |mk(t)− t| t 1 2+q = 0, and the result holds.”
MethodAssran, M. S., & Rabbat, M. G. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2981035 · Cited by 101
Privacy 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
Asynchronous Gossip-Based Random Projection Algorithms Over Networks
Lee, S., & Nedić, A. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2460051 · Cited by 97
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
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
“For example, the time interval between two consecutive updates in [16] and [17] is an identically and independently distributed process among nodes, which obviously results in EUR.”
BackgroundDistributed Event-Triggered Gradient Method for Constrained Convex Minimization
Liu, C., Li, H., Shi, Y., & Xu, D. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2916985 · Cited by 93
“Among these works, [20]–[22] considered stochastic settings.”
BackgroundLin, P., Ren, W., Yang, C., & Gui, W. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2910946 · Cited by 92
“In [10] and [11], the distributed optimization problem with nonuniform stepsizes in a stochastic setting was studied, where the communication graphs are required to be undirected and connected.”
BackgroundDecentralized Accelerated Gradient Methods With Increasing Penalty Parameters
Li, H., Fang, C., Yin, W., & Lin, Z. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.3018317 · Cited by 88
“The distributed subgradient method is a representative primalonly distributed optimization algorithm over general networks [14], while its stochastic version was studied in [15], and asynchronous variant in [16].”
MethodA gossip algorithm for aggregative games on graphs
Koshal, J., Nedić, A., & Shanbhag, U. V. (2012) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2012.6426136 · Cited by 80
“More precisely, with F0 = {x0i , i ∈ N}, we have”
BackgroundLi, 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
“The almost sure convergence for diminishing step-sizes and error bounds for constant step-sizes of [16] and [28] were established in the context of strongly convex and smooth cost functions.”
BackgroundMethodInfluentialAsynchronous Optimization Over Heterogeneous Networks Via Consensus ADMM
Kumar, S., Jain, R., & Rajawat, K. (2016) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2016.2593896 · Cited by 78
“While C-DGD has only been proposed for convex problems, it has been implemented in a distributed and asynchronous manner [39], [40], and is therefore an interesting candidate for the non-convex loca lization problem.”
BackgroundDistributed optimization over time-varying directed graphs
Nedic, A., & Olshevsky, A. (2013) · 52nd IEEE Conference on Decision and Control · doi:10.1109/cdc.2013.6760975 · Cited by 72
“Distributed optimization of a sum of convex functions has received a surge of interest in recent years [13], [15], [6], [11], [9], [10], [19], [12], [2], [16], [4].”
Distributed Nash equilibrium seeking in networked graphical games
Salehisadaghiani, F., & Pavel, L. (2017) · Automatica · doi:10.1016/j.automatica.2017.09.016 · Cited by 71
“This work is also related to the literature on distributed optimization [17], [18], [19].”
BackgroundMethodInfluentialAnalysis and Design of First-Order Distributed Optimization Algorithms Over Time-Varying Graphs
Sundararajan, A., Scoy, B. V., & Lessard, L. (2020) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2020.2988009 · Cited by 67
“This includes algorithms involving dual decomposition [4,24,25], inexact dual methods [7], proximal algorithms [27], asynchronous algorithms [15,37], weakly convex cases [13,20,26], accelerated methods [20,33,34].”
MethodSpiridonoff, A., Olshevsky, A., & Paschalidis, I. C. (2018) · PubMed · doi:10.48550/arxiv.1811.03982 · Cited by 65
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
“Undirected Graphs: A number of recent papers proposed subgradient type distributed methods that use consensus or averaging mechanisms for aggregating information among the agents over an undirected network (see [26], [27], [20], [35], [15], [41], [22], [23], [48], [2], [8]).”
BackgroundDistributed Nesterov Gradient and Heavy-Ball Double Accelerated Asynchronous Optimization
Li, H., Cheng, H., Wang, Z., & Wu, G. (2020) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.3027381 · Cited by 62
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 61
A Fast Distributed Asynchronous Newton-Based Optimization Algorithm
Mansoori, F., & Wei, E. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2933607 · Cited by 60
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
“Such problems are termed multi-agent optimization or distributed optimization , and they arise in a variety of contexts such as distributed regression over sensor networks [10] and finite-time optimal rendezvous problem [11].”
BackgroundMethodLü, Q., Li, H., & Xia, D. (2017) · Information Sciences · doi:10.1016/j.ins.2017.09.038 · Cited by 56
Revisiting EXTRA for Smooth Distributed Optimization
Li, H., & Lin, Z. (2020) · SIAM Journal on Optimization · doi:10.1137/18m122902x · Cited by 56
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
Branch-Wise Parallel Successive Algorithm for Online Voltage Regulation in Distribution Networks
Hu, X., Liu, Z., Wen, G., Yu, X., & Li, C. (2019) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2019.2910169 · Cited by 48
Broadcast Gossip Algorithms for Consensus on Strongly Connected Digraphs
Wu, S., & Rabbat, M. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2264056 · Cited by 46
“By exploiting the broadcast nature of wireless communications, broadcast gossip algorithms are more efficient (they converge after fewer transmissions) than other gossip algorithms [6].”
BackgroundPrivate 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
“Solutions to distributed optimization of convex functions have been proposed for myriad scenarios involving directed graphs [16], [17], communication link failures and losses [18], asynchronous communication models [19]–[21], and stochastic objective functions [10], [22].”
BackgroundPrivacy-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
“Convex distributed optimization has been studied in a variety of scenarios involving directed graphs [14], [15], communication link failures and losses [16], asynchronous communication models [17], [18], and stochastic objective functions [7].”
BackgroundDistributed resource allocation over random networks based on stochastic approximation
Yi, P., Lei, J., & Hong, Y. (2018) · Systems & Control Letters · doi:10.1016/j.sysconle.2018.02.009 · Cited by 45
“To describe uncertainties of communication topologies, different from the deterministic switching graphs in [7, 12] and [13], we adopt random graph models like [9, 10, 23] and [24] here.”
BackgroundMethodResultInfluentialA Survey on Smart Agent-Based Microgrids for Resilient/Self-Healing Grids
Dehghanpour, K., Colson, C., & Nehrir, M. H. (2017) · Energies · doi:10.3390/en10050620 · Cited by 45
Fully Asynchronous Distributed Optimization with Linear Convergence in Directed NetworksPreprint
Zhang, J., & You, K. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.08215 · Cited by 43
Accelerated Gradient Tracking over Time-varying Graphs for Decentralized OptimizationPreprint
Li, H., & Lin, Z. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2104.02596 · Cited by 42
“The representative decentralized algorithms include distributed gradient/subgradient descent (DGD) (Nedi´c & Ozdaglar, 2009; Nedi´c, 2011; Ram et al., 2010; Yuan et al., 2016), EXTRA (Shi et al., 2015b;a), gradient tracking (Nedi´c et al., 2017; Qu & Li, 2018; Xu et al., 2015; Xin et al., 2018), NIDS (Li et al., 2019)…”
BackgroundInfluentialAB /Push-Pull method for distributed optimization in time-varying directed networks
Nedić, A., Nguyen, D. T. A., & Nguyen, D. T. (2023) · Optimization methods & software · doi:10.1080/10556788.2023.2261602 · Cited by 42
“Distributed optimization of the sum of convex functions has been of considerable interest and many algorithms have been proposed including gradient-based methods [6,9,22,27,35], dual averaging methods [1], ADMM [26], and Newton methods [5,31].”
Distributed Nash Equilibrium Seeking via the Alternating Direction Method of Multipliers
Salehisadaghiani, F., & Pavel, L. (2017) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2017.08.983 · Cited by 41
Convergence and Applications of a Gossip-Based Gauss-Newton Algorithm
Li, X., & Scaglione, A. (2013) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2013.2276440 · Cited by 41
Superlinearly convergent asynchronous distributed network newton method
Mansoori, F., & Wei, E. (2017) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2017.8264076 · Cited by 41
“imizing summation of local convex objective functions. Various algorithms have been introduced to solve optimization problems in an asynchronous distributed way including primal algorithms [5], [11], [20], [25], [26], [29], [30], primal-dual algorithms [3], [9], [10], [22], [32] and quasi-Newton algorithms [12]. While…”
MethodDistributed Multiagent Convex Optimization Over Random Digraphs
Alaviani, S. S., & Elia, N. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2937499 · Cited by 41
“In [19]–[27], the authors assume that the agents/edge activations are i.”
BackgroundContinuous-time Distributed Convex Optimization with Set Constraints
Liu, S., Qiu, Z., & Xie, L. (2014) · IFAC Proceedings Volumes · doi:10.3182/20140824-6-za-1003.01377 · Cited by 40
“Asynchronous distributed gradient approach is investigated in Srivastava and Nedic (2011), Nedic (2011).”
MethodLi, H., Lin, Z., & Fang, Y. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.04373 · Cited by 40
“The modern distributed gradient descent (DGD) was proposed in (Nedi´c & Ozdaglar, 2009) for the general network topology, and was further extended in (Nedi´c, 2011; Ram et al., 2010a; Yuan et al., 2016).”
BackgroundASY-SONATA: Achieving Linear Convergence in Distributed Asynchronous Multiagent Optimization
Tian, Y., Sun, Y., & Scutari, G. (2018) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2018.8636055 · Cited by 39
“The algorithms in [2], [3] are gradient-based schemes; [4] is a decentralized instance of ADMM; [7] applies an asynchronous parallel ADMM scheme to distributed optimization; and [8] builds on a primal-dual method.”
BackgroundMethodInfluentialStochastic 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
“Our work here contributes to the growing literature on distributed methods for optimization over networks [5], [9], [12], [14]–[16], [19]–[23], [28], [32], [34], [40], [43].”
MethodA 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
“Furthermore, theresultsin[24],[25],and[27]assumeweightedmatrixofthegraphto beindependentandidenticallydistributed(i.i.d.),whereas[26]assumes weightedmatrixofthegraphtobeastate-dependentMarkovprocess.”
A Distributed Algorithm for Convex Constrained Optimization Under Noise
Chatzipanagiotis, N., & Zavlanos, M. M. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2504932 · Cited by 37
“, [33], [47], [48].”
A distributed asynchronous method of multipliers for constrained nonconvex optimization
Farina, F., Garulli, A., Giannitrapani, A., & Notarstefano, G. (2019) · Automatica · doi:10.1016/j.automatica.2019.02.003 · Cited by 37
“Several asynchronous version of distributed optimization algorithms have been proposed in literature, a typical example being the class of gossip-based algorithms [14, 15].”
Zeroth-order feedback optimization for cooperative multi-agent systems
Tang, Y., Ren, Z., & Li, N. (2022) · Automatica · doi:10.1016/j.automatica.2022.110741 · Cited by 36
Bianchi, P., Hachem, W., & Iutzeler, F. (2014) · arXiv (Cornell University) · Cited by 36
Nash equilibrium seeking by a gossip-based algorithm
Salehisadaghiani, F., & Pavel, L. (2014) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2014.7039537 · Cited by 35
“Lemma 2 in [21] yields that Term 1 ≤ √γ‖x̃(k)− (1N ⊗ IN )Z(k)‖.”
Asynchronous and Time-Varying Proximal Type Dynamics in Multiagent Network Games
Cenedese, C., Belgioioso, G., Kawano, Y., Grammatico, S., & Cao, M. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3011916 · Cited by 34
“To model the asynchronous updates we adopt the same mathematical framework as in [13], [20], and [21].”
MethodResource-Aware Exact Decentralized Optimization Using Event-Triggered Broadcasting
Liu, C., Li, H., & Shi, Y. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3014316 · Cited by 34
“ective is further assumed to be strongly convex. It is worth mentioning that there are also other attempts in the literature to develop communication-efficient algorithms. For instance, the authors in [23] considered DGD with random communication link failures, and established convergence rate and error bound for decay…”
ResultDistributed Bregman-Distance Algorithms for Min-Max Optimization
Srivastava, K., Nedić, A., & Stipanović, D. M. (2012) · Studies in computational intelligence · doi:10.1007/978-3-642-34097-0_7 · Cited by 34
“These averaging protocols have led to a new class of distributed algorithms for parameter estimation [37], distributed optimization [29, 25, 23, 19, 21, 35] and control of multi-agent systems [16].”
BackgroundMethodCenedese, C., Belgioioso, G., Grammatico, S., & Cao, M. (2020) · European Journal of Control · doi:10.1016/j.ejcon.2020.08.006 · Cited by 33
Asynchronous Incremental Stochastic Dual Descent Algorithm for Network Resource Allocation
Bedi, A. S., & Rajawat, K. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2807423 · Cited by 32
Distributed time synchronization for networks with random delays and measurement noise
Stanković, M. S., Stanković, S. S., & Johansson, K. H. (2018) · Automatica · doi:10.1016/j.automatica.2018.03.054 · Cited by 32
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
“Remark 2: The proof of Lemma 1 can be found in [8].”
BackgroundDistributed Nesterov-like gradient algorithms
Jakovetić, D., Moura, J. M. F., & Xavier, J. (2012) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2012.6425938 · Cited by 31
“, the algorithm proposed in [2] and extended and analyzed in [3], [2], [4], [5], [6], [7], and the one proposed in [8] and extended and analyzed in [9], [10], converge slowly.”
MethodBroadcast-based distributed alternating direction method of multipliers
Makhdoumi, A., & Ozdaglar, A. (2014) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2014.7028466 · Cited by 30
“For a vector x, xi denotes the ith component of the vector.”
BackgroundDecentralized 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
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
“Since then, the problem of optimizing the sum of convex functions in a distributed manner has received significant interest [6], [7], [8], [9], [10].”
BackgroundYuan, D., Xu, S., Zhang, B., & Rong, L. (2012) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.2856 · Cited by 30
“In the literature, there has been some recent work on the multi-agent optimization problem [1, 15–22].”
BackgroundResultInfluentialPersonalized and Private Peer-to-Peer Machine Learning
Bellet, A., Guerraoui, R., Taziki, M., & Tommasi, M. (2017) · HAL · Cited by 28
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
“Following [12], we replace in our analysis the set of local clocks by a global virtual clock with the rate”
BackgroundMethodInfluentialAsynchronous Distributed Blind Calibration of Sensor Networks Under Noisy Measurements
Stanković, M. S., Stankovic, S. S., & Johansson, K. H. (2016) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2016.2633788 · Cited by 27
“, [30], [36]); in this case the virtual global clock ticks according to a Poisson process with the rate ∑n j=1 μj (see, e.”
BackgroundToward Creating a Subsurface Camera
Song, W., Li, F., Valero, M., & Zhao, L. (2019) · Sensors · doi:10.3390/s19020301 · Cited by 27
“Nedic [39] first filled this gap by considering general decentralized convex optimization similar to Equation (1) under the asynchronous broadcast setting.”
Background
Metadata
- Authors
- Nedic, A.
- Venue
- IEEE Transactions on Automatic Control
- Published
- 2011-06
- Volume
- 56
- Issue
- 6
- Pages
- 1337-1351
- ISSN
- 0018-9286 (ISSN-L)
- 1558-2523
- OpenAlex
- W2130263842
- Cited by
- 310
- References
- 36
- Citations by year
- 2026: 2 · 2025: 14 · 2024: 17 · 2023: 12 · 2022: 10 · 2021: 20 · 2020: 38 · 2019: 36 · 2018: 33 · 2017: 30 · 2016: 21 · 2015: 21 · 2014: 21 · 2013: 15 · 2012: 14
- FWCI
- 15.51
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Automatic Control (publishedVersion)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Keywords
- distributed convex optimization, multi-agent systems, random link failures, constant step size, almost sure convergence, error bounds, distributed optimization
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.
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.