Parallel Streaming Wasserstein Barycenters
Preprint
Abstract
Efficiently aggregating data from different sources is a challenging problem, particularly when samples from each source are distributed differently. These differences can be inherent to the inference task or present for other reasons: sensors in a sensor network may be placed far apart, affecting their individual measurements. Conversely, it is computationally advantageous to split Bayesian inference tasks across subsets of data, but data need not be identically distributed across subsets. One principled way to fuse probability distributions is via the lens of optimal transport: the Wasserstein barycenter is a single distribution that summarizes a collection of input measures while respecting their geometry. However, computing the barycenter scales poorly and requires discretization of all input distributions and the barycenter itself. Improving on this situation, we present a scalable, communication-efficient, parallel algorithm for computing the Wasserstein barycenter of arbitrary distributions. Our algorithm can operate directly on continuous input distributions and is optimized for streaming data. Our method is even robust to nonstationary input distributions and produces a barycenter estimate that tracks the input measures over time. The algorithm is semi-discrete, needing to discretize only the barycenter estimate. To the best of our knowledge, we also provide the first bounds on the quality of the approximate barycenter as the discretization becomes finer. Finally, we demonstrate the practical effectiveness of our method, both in tracking moving distributions on a sphere, as well as in a large-scale Bayesian inference task.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Wasserstein barycenters over Riemannian manifoldsAdvances in Mathematics, 2017
- Discrete Wasserstein barycenters: optimal transport for discrete dataMathematical Methods of Operations Research, 2016
- A Numerical Algorithm forL2Semi-Discrete Optimal Transport in 3DESAIM: Mathematical Modelling and Numerical Analysis, 2015
- Optimal Transport for Applied Mathematicians2015
- Wasserstein Barycenter and Its Application to Texture Mixing2012
- Approximation by finitely supported measuresESAIM: Control, Optimisation and Calculus of Variations, 2011
- An Efficient Stochastic Approximation Algorithm for Stochastic Saddle Point Problems2002
- Adaptive Game Playing Using Multiplicative WeightsGames and Economic Behavior, 1999
- A finite algorithm for finding the projection of a point onto the canonical simplex of ? nJournal of Optimization Theory and Applications, 1986
- Validation of subgradient optimizationMathematical Programming, 1974