The Distributed Setup, Some Definitions and Problem Statements

Wednesday, November 6, 2019 - 4:00pm to 4:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Cesar A Uribe

Affiliation

LIDS

Building and Room Number

LIDS Lounge

Abstract

Cesar will show some recent results on the study of the optimal convergence rates for distributed convex optimization problems over networks, where the objective is to minimize a sum of local functions of the nodes in the network. We provide optimal complexity bounds for four different cases, namely: the case when each function is strongly convex and smooth, the cases when it is either strongly convex or smooth and the case when it is convex but neither strongly convex nor smooth. Our approach is based on the dual of an appropriately formulated primal problem, which includes the underlying static graph that models the communication restrictions. Our results show distributed algorithms that achieve the same optimal rates as their centralized counterparts (up to constant and logarithmic factors), with an additional cost related to the spectral gap of the interaction matrix that captures the local communications of the nodes in the network. Application examples are shown for the problem of a distributed computation of Wasserstein barycenters.

Biography

Cesar A. Uribe received the M.Sc. degrees in systems and control from Delft University of Technology, in The Netherlands, and in applied mathematics from the University of Illinois at Urbana-Champaign, in 2013 and 2016, respectively. He also received the PhD degree in electrical and computer engineering at the University of Illinois at Urbana-Champaign in 2018.  He is currently a Postdoctoral Associate in the Laboratory for Information and Decision Systems-LIDS at the Massachusetts Institute of Technology-MIT. His research interests include distributed learning and optimization, decentralized control, algorithm analysis, and computational optimal transport.