Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters

By Pavel E. Dvurechensky, Darina Dvinskikh, Alexander V. Gasnikov, César A. Uribe, Angelia Nedić. 2018

108 citations recorded by the source corpus.

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 decentralized 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.

Subfields: Applied Mathematics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Theory and Mathematics

Citations in the corpus

$\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, background): “…and Duchi, 2011, Recht et al., 2011], where all the workers are ensured to obtain information from all others; 2) decentralized parallel learning [Dvurechenskii et al., 2018, He et al., 2018, Li and Yan, 2017, Lian et al., 2017], where each worker can only gather information from a fraction of…”
Automatic Text Evaluation through the Lens of Wasserstein Barycenters (2021, background): “…tractable, the measure µ is often constrained to be a discrete measure with free (Cuturi and Doucet, 2014; Álvarez Esteban et al., 2016; Cuturi and Peyré, 2016; Luise et al., 2019) or fixed support (Benamou et al., 2015; Dvurechenskii et al., 2018; Lin et al., 2020; Janati et al., 2020).”
A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks (2018, background): “Additional examples related to optimal transport problems of computation of Wasserstein barycenter can be found in [15, 24, 85].”
Statistical inference for Bures–Wasserstein barycenters (2019, methodology): “modelling of molecular dynamic Gonzalez et al. [2017], clustering procedures Del Barrio et al.”
Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm (2019, methodology): “The first problem is typically addressed by either fixing the support of the barycenter a-priori [20, 50] or by adopting an alternating minimization procedure to iteratively optimize the support point locations and their weights [12, 14].”