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
(1972) · Elsevier eBooks · doi:10.1016/c2013-0-06164-6 · Cited by 1,728
Dudley, R. M. (2002) · Cambridge University Press eBooks · doi:10.1017/cbo9780511755347 · Cited by 1,281 · cited 1×
“with mean E [ χEi,t ] = γi for each i ∈ V , by the law of iterated logarithms (see [9], pages 476–479), we have for any q > 0, with probability 1,”
BackgroundPROBLEMS IN DECENTRALIZED DECISION MAKING AND COMPUTATION
Τσιτσικλής, Ι. (2014) · doi:10.12681/eadd/3778 · Cited by 1,278
Distributed average consensus with least-mean-square deviation
Xiao, L., Boyd, S., & Kim, S.-J. (2007) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2006.08.010 · Cited by 1,107 · cited 1×
“A very different distributed computational model has been proposed in [15] and also discussed in [16]–[18], where the network objective function is available to each agent and the processing is distributed by allowing each agent to update only a part of the decision vector.”
BackgroundDistributed 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 1×
“The agent (that has just updated the iterate) passes the iterate to a randomly selected neighbor to perform the next update.”
BackgroundKar, S., & Moura, J. M. F. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.2007111 · Cited by 691 · cited 1×
“this paper is related to the literature on distributed consensus and averaging [10], [11], [15]–[17], [19]–[ 22 ].”
BackgroundNumerical Techniques for Stochastic Optimization
(1988) · Springer Series in Computational Mathematics · doi:10.1007/978-3-642-61370-8 · Cited by 632
Borkar, V. S. (2008) · Texts and Readings in Mathematics · doi:10.1007/978-93-86279-38-5 · Cited by 561
Convex Optimization in Signal Processing and Communications
(2009) · Cambridge University Press eBooks · doi:10.1017/cbo9780511804458 · Cited by 554 · cited 1×
“The agent (that has just updated the iterate) passes the iterate to a randomly selected neighbor to perform the next update.”
BackgroundBroadcast Gossip Algorithms for Consensus
Aysal, T. C., Yildiz, M. E., Sarwate, A. D., & Scaglione, A. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2016247 · Cited by 480 · cited 3×
“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.”
BackgroundMethodBingham, N. H., & Billingsley, P. (1980) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2982142 · Cited by 455
Gradient Convergence in Gradient methods with Errors
Bertsekas, D. P., & Tsitsiklis, J. N. (2000) · SIAM Journal on Optimization · doi:10.1137/s1052623497331063 · Cited by 437 · cited 1×
“A very different distributed computational model has been proposed in [15] and also discussed in [16]–[18], where the network objective function is available to each agent and the processing is distributed by allowing each agent to update only a part of the decision vector.”
BackgroundSome applications of Laplace eigenvalues of graphs
Mohar, B. (1997) · Graph Symmetry · doi:10.1007/978-94-015-8937-6_6 · Cited by 422
Quantized incremental algorithms for distributed optimization
Rabbat, M. G., & Nowak, R. D. (2005) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2005.843546 · Cited by 408 · cited 1×
“I. INTRODUCTION T HE problem of minimizing of a sum of convex func-tions when each component function is available (with stochastic errors) to a specific network agent is an important problem in the context of wired and wireless networks [1]–[5].”
Backgroundstochastic quasigradient methods and their application to system optimization†
Ermoliev, Y. (1983) · Stochastics · doi:10.1080/17442508308833246 · Cited by 280 · cited 1×
“On a much broader basis our work is also related to stochastic optimization literature [ 23 ]–[26] since we consider (sub)gradient methods with stochastic errors.”
BackgroundIncremental Stochastic Subgradient Algorithms for Convex Optimization
Ram, S. S., Nedić, A., & Veeravalli, V. V. (2009) · SIAM Journal on Optimization · doi:10.1137/080726380 · Cited by 239 · cited 2×
“However, wireless media is inherently broadcast and establishing bidirectional communications creates a bottleneck.”
BackgroundMethodCooperative distributed multi-agent optimization
Nedić, A., & Ozdaglar, A. (2009) · Convex Optimization in Signal Processing and Communications · doi:10.1017/cbo9780511804458.011 · Cited by 185 · cited 1×
“Distributed consensus-based algorithms have been studied in [9]–[14], which rely on deterministic consensus schemes, except for [13] where a random consensus scheme is considered.”
BackgroundDistributed subgradient methods and quantization effects
Nedic, A., Olshevsky, A., Ozdaglar, A., & Tsitsiklis, J. N. (2008) · 2008 47th IEEE Conference on Decision and Control · doi:10.1109/cdc.2008.4738860 · Cited by 185
Asynchronous Stochastic Approximations
Borkar, V. S. (1998) · SIAM Journal on Control and Optimization · doi:10.1137/s0363012995282784 · Cited by 167 · cited 1×
“A very different distributed computational model has been proposed in [15] and also discussed in [16]–[18], where the network objective function is available to each agent and the processing is distributed by allowing each agent to update only a part of the decision vector.”
BackgroundAsynchronous gossip algorithms for stochastic optimization
Ram, S. S., Nedić, A., & Veeravalli, V. V. (2009) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2009.5399485 · Cited by 130 · cited 4×
“Date of publication September 27, 2010; date of current version June 08, 2011.”
BackgroundMethodInfluentialOn Distributed Optimization in Networked Systems
Johansson, B. (2008) · KTH Publication Database DiVA (KTH Royal Institute of Technology) · Cited by 114
Distributed Non-Autonomous Power Control through Distributed Convex Optimization
Ram, S. S., Veeravalli, V. V., & Nedic, A. (2009) · IEEE INFOCOM 2009 · doi:10.1109/infcom.2009.5062275 · Cited by 99 · cited 1×
“I. INTRODUCTION T HE problem of minimizing of a sum of convex func-tions when each component function is available (with stochastic errors) to a specific network agent is an important problem in the context of wired and wireless networks [1]–[5].”
BackgroundA simple peer-to-peer algorithm for distributed optimization in sensor networks
Johansson, B., Rabi, M., & Johansson, M. (2007) · 2007 46th IEEE Conference on Decision and Control · doi:10.1109/cdc.2007.4434888 · Cited by 90 · cited 1×
“Another asynchronous algorithm for optimization over networks is the Markov incremental algorithm proposed in [1], [2] and further studied in [8].”
MethodAsynchronous gossip algorithms for stochastic optimization
Sundhar Ram, S., Nedic, A., & Veeravalli, V. V. (2009) · 2009 International Conference on Game Theory for Networks · doi:10.1109/gamenets.2009.5137386 · Cited by 77
Distributed Consensus Algorithms in Sensor Networks: Link Failures and Channel NoisePreprint
Kar, S., & Moura, J. M. F. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0711.3915 · Cited by 63 · cited 1×
“this paper is related to the literature on distributed consensus and averaging [10], [11], [15]–[17], [19]–[22].”
BackgroundRao, S. S. (2009) · Engineering Optimization · doi:10.1002/9780470549124.ch1 · Cited by 49
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
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.