Title: Decentralized Online Optimization with Global Objectives and Local Communication
This talk, based on joint work with Soomin Lee and Angelia Nedich, focuses on a decentralized online convex optimization problem, where each agent controls only one coordinate of the global decision vector. The agents communicate with their neighbors over a static undirected graph or over a time-varying sequence of directed graphs under a uniform connectivity condition. We propose a decentralized variant of Nesterov’s primal-dual algorithm with dual averaging. To mitigate the disagreements on the primal-vector updates that arise due to locality of communication, the agents implement a generalization of the local information-exchange dynamics recently proposed by Li and Marden in the undirected case, and a broadcast-based gradient push-sum dynamics in the directed case. We show that, when the step size is chosen appropriately and the objective functions are Lipschitz with Lipschitz gradients, the resulting regret is sublinear in the time horizon.
Maxim Raginsky received the B.S. and M.S. degrees in 2000 and the Ph.D. degree in 2002 from Northwestern University, all in electrical engineering. He has held research positions with Northwestern, University of Illinois at Urbana-Champaign (where he was a Beckman Foundation Fellow from 2004 to 2007), and Duke University. In 2012, he returned to UIUC, where he is currently an Associate Professor and William L. Everitt Fellow with the Department of Electrical and Computer Engineering. Dr. Raginsky received a Faculty Early Career Development (CAREER) Award from the National Science Foundation in 2013. His research interests lie at the intersection of information theory, machine learning, and control. He is a member of the editorial boards of Foundations and Trends in Communications and Information Theory and IEEE Transactions on Network Science and Engineering.