Fast Distributed Algorithms for Optimization in Time-Varying Graphs
Abstract:
We will discuss the problems of distributed optimization over time-varying 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 the 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. The Push-DIGing uses column stochastic matrices and fixed step-sizes, but it still converges to a global minimizer (common to all agents). 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 problem over time-varying graphs. (Joint work with Alexander Olshevsky, Boston University, and Wilbur (Wei) Shi, Arizona State University.)
Biography:
Angelia Nedich holds a Ph.D. from Moscow State University, Moscow, Russia, in Computational Mathematics and Mathematical Physics (1994), and a Ph.D. from Massachusetts Institute of Technology, Cambridge, USA in Electrical and Computer Science Engineering (2002). She has worked as a senior engineer in BAE Systems North America, Advanced Information Technology Division at Burlington, MA. She is the recipient of an NSF CAREER Award 2007 in Operations Research for her work in 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). Her current interest is in large-scale optimization, games, control and information processing in networks.