TY - JOUR
T1 - Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization
AU - Nedich, Angelia
AU - Olshevsky, Alex
AU - Rabbat, Michael G.
N1 - Funding Information:
Manuscript received September 21, 2017; revised January 15, 2018; accepted February 27, 2018. Date of current version April 24, 2018. The work of A. NediÂc and A. Olshevsky was supported by the U.S. Office of Naval Research under Grant N000014-16-1-2245. The work of A. Olshevsky was also supported by the National Science Foundation (NSF) under Award CMMI-1463262 and by the Air Force Office of Scientific Research (AFOSR) under Award FA-95501510394. The work of M. G. Rabbat was supported by the Natural Sciences and Engineering Research Council of Canada under Awards RGPIN-2012-341596 and RGPIN-2017-06266. (Corresponding author: Michael G.Rabbat.) A. Nedic is with the School of Electrical, Computer, and Energy Engineering, Arizona State University, Tempe, AZ 85281 USA (e-mail: angelia.nedich@asu.edu). A. Olshevsky is with the Department of Electrical and Computer Engineering, Boston University, Boston, MA 02215 USA (e-mail: alexols@bu.edu). M. G. Rabbat is with Facebook Artificial Intelligence Research, MontreÂal, QC, Canada and the Department of Electrical and Computer Engineering, McGill University, MontreÂal, QC H3A 0G4 Canada (e-mail: mikerabbat@fb.com).
Publisher Copyright:
© 2008 IEEE.
PY - 2018/5
Y1 - 2018/5
N2 - In decentralized optimization, nodes cooperate to minimize an overall objective function that is the sum (or average) of per-node private objective functions. Algorithms interleave local computations with communication among all or a subset of the nodes. Motivated by a variety of applications..decentralized estimation in sensor networks, fitting models to massive data sets, and decentralized control of multirobot systems, to name a few..significant advances have been made toward the development of robust, practical algorithms with theoretical performance guarantees. This paper presents an overview of recent work in this area. In general, rates of convergence depend not only on the number of nodes involved and the desired level of accuracy, but also on the structure and nature of the network over which nodes communicate (e.g., whether links are directed or undirected, static or time varying). We survey the state-of-theart algorithms and their analyses tailored to these different scenarios, highlighting the role of the network topology.
AB - In decentralized optimization, nodes cooperate to minimize an overall objective function that is the sum (or average) of per-node private objective functions. Algorithms interleave local computations with communication among all or a subset of the nodes. Motivated by a variety of applications..decentralized estimation in sensor networks, fitting models to massive data sets, and decentralized control of multirobot systems, to name a few..significant advances have been made toward the development of robust, practical algorithms with theoretical performance guarantees. This paper presents an overview of recent work in this area. In general, rates of convergence depend not only on the number of nodes involved and the desired level of accuracy, but also on the structure and nature of the network over which nodes communicate (e.g., whether links are directed or undirected, static or time varying). We survey the state-of-theart algorithms and their analyses tailored to these different scenarios, highlighting the role of the network topology.
KW - Consensus algorithms
KW - distributed averaging
KW - distributed optimization
KW - gossip algorithms
KW - multiagent systems
UR - http://www.scopus.com/inward/record.url?scp=85045736476&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85045736476&partnerID=8YFLogxK
U2 - 10.1109/JPROC.2018.2817461
DO - 10.1109/JPROC.2018.2817461
M3 - Review article
AN - SCOPUS:85045736476
SN - 0018-9219
VL - 106
SP - 953
EP - 976
JO - Proceedings of the IEEE
JF - Proceedings of the IEEE
IS - 5
ER -