Google Research

Fixed-Support Wasserstein Barycenter: Computational Hardness and Efficient Algorithms

  • Tianyi Lin
  • Nhat Ho
  • Xi Chen
  • Marco Cuturi
  • Michael I. Jordan
Neurips 2020 (to appear)


We study in this paper the finite-support Wasserstein barycenter problem (FS-WBP), which consists in computing the Wasserstein barycenter of $m$ discrete probability measures supported on a finite metric space of size $n$. We show first that the constraint matrix arising from the linear programming (LP) representation of the FS-WBP is totally unimodular when $m \geq 3$ and $n = 2$, but not totally unimodular when $m \geq 3$ and $n \geq 3$. This result answers an open problem, since it therefore proves that the FS-WBP is not a minimum-cost flow problem and cannot therefore be efficiently solved using linear programming. Building on this negative result, we propose and analyze two simple and efficient variants of the iterative Bregman projection (IBP) algorithm, currently the most widely adopted algorithm so solve the FS-WBP. The first variant is an accelerated IBP algorithm, which achieves the complexity bound of $\bigOtil(mn^{7/3}/\varepsilon)$. This bound is better than that obtained for the standard IBP algorithm---$\bigOtil(mn^{2}/\varepsilon^2)$---in terms of $\varepsilon$, and that from accelerated primal-dual gradient algorithm---$\bigOtil(mn^{5/2}/\varepsilon)$---in terms of $n$. The second algorithm is an asynchronous IBP algorithm, which displays empirically speedups on a multi-core system. We provide a convergence analysis for this algorithm under mild conditions of the delays. Experiments on synthetic and real data, including the MNIST and Fashion-MNIST image datasets, illustrate the efficiency of our proposed algorithms.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work