Fixed-Support Wasserstein Barycenter: Computational Hardness and Efficient Algorithms

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.

• Algorithms and Theory

• Machine Intelligence