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

This paper presents a distributed algorithm for computing Wasserstein barycenters. The basic setup is that each agent in the decentralized system has access to one probability distribution; similar to "gossip" based optimization techniques in the classical case (e.g. It seems this paper missed the closest related work, "Stochastic Wasserstein Barycenters" (Claici et al., ArXiv/ICML), which proposes a nonconvex semidiscrete barycenter optimization algorithm. Certainly any final version of this paper needs to compare to that work carefully. It may also be worth noting that the Wasserstein propagation algorithm in "Convolutional Wasserstein Distances: Efficient Optimal Transportation on Geometric Domains" (2015) could be implemented easily on a network in a similar fashion to what is proposed in this paper; see their Algorithm 4. Like lots of previous work in OT, this technique uses entropic regularization to make transport tractable; they solve the smoothed dual.

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.