Distributed Algorithms for Optimization in Networks

Abstract

In this talk, I will present a statistical/machine learning approach to solve a decentralized consensus problem in a multi-agent system. The goal is to estimate a parameter θ* ∈ R^d when no agent observes it directly. Agents make local noisy observations of a function of the parameter, and can aggregate observations across the network through communication with their neighbors. In contrast to previous work, I will focus on a social learning approach where agents track both the total sum of observations and their social network’s posterior beliefs about θ*, i.e., agents learn from both observed data and from their neighbors. Given the iterative nature of the algorithm, I will provide the conditions for (almost sure) convergence of all agents’ estimates to the true parameter value. In addition, I will derive a central limit theorem (CLT) result showing asymptotic normality. This is the first such result for distributed estimation/learning that allows for both general observation models and time-varying networks. The CLT enables a precise characterization of the algorithm’s performance, as well as a comparison across different algorithms and network structures. For instance, interestingly, the standard collaborative approach where agents simply average their beliefs with their neighbors (without the averaging with the observations) exhibits the same asymptotic covariance as when agents learn in isolation from their respective local observations. In contrast, the proposed social learning approach, where agents aggregate both their observations and their neighbors’ beliefs, provably improves over the standard approach.

Bio

Angelia Nedić received a B.S. degree in Mathematics in 1987 from the University of Novi Sad, Serbia, an M.S. degree in Mathematics in 1990 from the University of Belgrade, Serbia, and a Ph.D. degree in Engineering Sciences and Applied Mathematics in 2002 from Northwestern University. She is currently a professor in the School for Electrical, Computer and Energy Engineering at Arizona State University. Prior to this appointment, she has been with the University of Illinois at Urbana-Champaign (2003—2018) and the Coordinated Science Laboratory. She also held a research scientist and postdoc position at the Massachusetts Institute of Technology (2002—2003). Her research interests include distributed multi-agent optimization, stochastic optimization methods, and games.