Timezone: »

 
Spotlight
Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters
Pavel Dvurechenskii · Darina Dvinskikh · Alexander Gasnikov · Cesar Uribe · Angelia Nedich

Thu Dec 06 01:45 PM -- 01:50 PM (PST) @ Room 517 CD
in Thu Track 3 -- Session 2 »

We study the decentralized distributed computation of discrete approximations for the regularized Wasserstein barycenter of a finite set of continuous probability measures distributedly stored over a network. We assume there is a network of agents/machines/computers, and each agent holds a private continuous probability measure and seeks to compute the barycenter of all the measures in the network by getting samples from its local measure and exchanging information with its neighbors. Motivated by this problem, we develop, and analyze, a novel accelerated primal-dual stochastic gradient method for general stochastic convex optimization problems with linear equality constraints. Then, we apply this method to the decen- tralized distributed optimization setting to obtain a new algorithm for the distributed semi-discrete regularized Wasserstein barycenter problem. Moreover, we show explicit non-asymptotic complexity for the proposed algorithm. Finally, we show the effectiveness of our method on the distributed computation of the regularized Wasserstein barycenter of univariate Gaussian and von Mises distributions, as well as some applications to image aggregation.

Author Information

Pavel Dvurechenskii (Weierstrass Institute, Berlin)

Since 2015 Research assistant, Research Group 6 "Stochastic Algorithms and Nonparametric Statistics", Weierstrass Institute for Applied Analysis and Stochastics, Berlin 2014 - 2015 Research assistant, Institute for Information Transmission Problems, Moscow, Russia 2009 - 2015 Junior researcher, Moscow Institute of Physics and Technology, Moscow, Russia 2013 Ph.D., Moscow Institute of Physics and Technology, Moscow, Russia 2010 Master's Diploma, Moscow Institute of Physics and Technology, Moscow, Russia 2008 Bachelor's Diploma, Moscow Institute of Physics and Technology, Moscow, Russia

Darina Dvinskikh (WIAS im Forschungsverbund Berlin e. V.)

2018 Master's Diploma, Moscow Institute of Physics and Technology, Moscow, Russia 2018 Master's Diploma, Skolkovo Institute of Science and Technology, Moscow, Russia 20016 Bachelor's Diploma, Moscow Institute of Physics and Technology, Moscow, Russia

Alexander Gasnikov (SkolTech)
Cesar Uribe (Massachusetts Institute of Technology)
Angelia Nedich (Arizona State University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors