Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters
arXiv:1806.03915
Abstract
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.
References in corpus (13)
- Fast Computation of Wasserstein Barycenters
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- Optimal-transport formulation of electronic density-functional theory
- Amplitude and phase variation of point processes
- Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm
- Stochastic Wasserstein Barycenters
- Multilevel Clustering via Wasserstein Means
- Optimal Algorithms for Distributed Optimization
- Distributed Learning for Cooperative Inference
- Parallel Streaming Wasserstein Barycenters
- Construction of Non-asymptotic Confidence Sets in 2-Wasserstein Space
- Primal-Dual Method for Searching Equilibrium in Hierarchical Congestion Population Games
- Adaptive Similar Triangles Method: a Stable Alternative to Sinkhorn's Algorithm for Regularized Optimal Transport