Angelia Nedich - Tutorial Session - 57th Allerton Conference on Communication, Control, and Computing

SCHEDULE

Registration: 1:00-2:00 pm in the lower level lobby of Coordinated Science Laboratory

Afternoon Tutorial by Angelia Nedich 
Session begins: 2:00pm-3:30pm
Afternoon break: 3:30pm-4:00pm (Snacks and water will be provided)
Session resumes: 4:00pm-5:30pm

Conference Welcome Reception will follow from 6:00-8:00pm in the Electrical and Computer Engineering Building, Room 3002

Angelia Nedich will start her tutorial presentation at 2:00pm-5:30pm (includes a 30 minute break from 3:30-4:00pm)

Title: Distributed Algorithms for Optimization in Networks

Abstract:

We will overview the distributed optimization algorithms starting with the basic underlying idea illustrated on a prototype problem in machine learning. In particular, we will focus on convex minimization problem where the objective function is given as the sum of convex functions, each of which is known by an agent in a network. The agents communicate over the network with a task to jointly determine a minimum of the sum of their objective functions. The communication network can vary over time, which is modeled through a sequence of graphs over a static set of nodes (representing the agents in a system). In this setting, the basic distributed first-order methods will be discussed that make use of a consensus protocol, which is a mechanism virtually replacing the role of a coordinator. In these basic distributed methods, the agents are somewhat selfish as they greedily process only the gradients of their own objective function, while they mix (through a consensus step) their decision variables. As a result, the methods are slow and cannot be used with a constant stepsize value, which is desirable for a faster convergence. Nevertheless, these methods are useful in the implementations with noisy (stochastic) gradients or noisy/unreliable communication links.

We will then discuss some recent developments of fast distributed gradient methods that can match the performance of the centralized gradient method. In particular, these fast methods are constructed by having the agents be aware of the system objective function in the sense that they are more cooperative in the process of diffusing the gradient information, while still directly processing only their own local objective function. The diffusion of the gradient information is based on a gradient-tracking mechanism, which allows for a proper mixing of the gradient-based directions that the agents are using. Through the diffusion of the agent decision variables and directions, the distributed methods with gradient tracking work with a suitably selected constant stepsize and can be as fast as a centralized gradient method. One of these methods (Apush-Bpull) recently developed, surprisingly, uses a weighted-averaging consensus to diffuse the decision variables, and a push-sum consensus to diffuse the directions. This is quite interesting since most of the prior work on the distributed methods with gradient tracking have used either weighted-averaging consensus or push-sum consensus depending on whether the underlying connectivity graph is undirected or directed. Finally, we will discuss the convergence rate results for these fast distributed methods, provide some intuition behind their analysis, and provide some simulation results that demonstrate their performance.

Biography: Angelia Nedich has a Ph.D. from Moscow State University, 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 is a professor at the school of Electrical, Computer and Energy Engineering at Arizona State University (ASU) at Tempe. Prior to joining ASU, she has been a Willard Scholar faculty at the University of Illinois, Urbana-Champaign. She is a recipient (jointly with co-authors) of the Best Paper Awards at the Winter Simulation Conference 2013, and the International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks 2015. Her research interest is in optimization theory and algorithms, stochastic optimization, variational inequality problems, Nash equilibrium problems, and dynamics of large scale complex systems.