Fall 2017 Joint CSC@USC/CommNetS-MHI Seminar Series
 |
Angelia Nedich,
Arizona State University
|
Abstract
We will discuss the problems of distributed optimization over graphs. For the case of undirected graphs, we introduce a distributed algorithm, referred to as DIGing, which is a combination of a distributed inexact gradient method and a gradient-tracking mechanism. The DIGing algorithm uses doubly stochastic mixing matrices and employs fixed step-sizes and, yet, drives all agents’ iterates to a common global minimizer. When the graphs are directed, in which case the implementation of doubly stochastic mixing matrices is unrealistic, we construct an algorithm that incorporates the push-sum protocol into the DIGing structure, thus obtaining Push-DIGing algorithm. Under the strong convexity assumption for the objective function, we prove that both algorithms converge at R-linear (geometric) rates, as long as the step-sizes do not exceed some upper bounds. We establish explicit convergence rate estimates for the convergence rates. When the graph is undirected, we show that the convergence rate of DIGing scales polynomially in the number of agents. We also provide some numerical experiments to demonstrate the efficacy of the proposed algorithms and to validate our theoretical findings. We then discuss the variants of these algorithms for resource allocation problems in graphs.
Joint work with Alexander Olshevsky, Boston University, and Wilbur (Wei) Shi, Arizona State University.
Biosketch
Angelia Nedich holds a PhD from Moscow State University, Moscow, Russia, in Computational Mathematics and Mathematical Physics (1994), and a PhD from Massachusetts Institute of Technology, Cambridge, USA in Electrical Engineering and Computer Science (2002). She has worked as a senior engineer in BAE Systems North America, Advanced Information Technology Division in Burlington, MA. She is the recipient of an NSF CAREER Award in 2007 in Operations Research for her work on distributed multi-agent optimization. She is a recipient (jointly with her co-authors) of the Best Paper Award at the Winter Simulation Conference 2013 and the Best Paper Award at the International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt) 2015 (with co-authors). She has served as an Associate Editor for IEEE Transactions on Automatic Control and Transactions of Control of Network Systems. She is currently serving on Editorial Board of SIAM Journal on Optimization and for INFORMS Operations Research. Her current interests are in large-scale optimization, games, control and information processing in networks.