Improved Complexity Bounds in Wasserstein Barycenter Problem

In this paper, we focus on computational aspects of Wasserstein barycenter problem. We provide two algorithms to compute Wasserstein barycenter of $m$ discrete measures of size $n$ with accuracy $\e$. The first algorithm, based on mirror prox with some specific norm, meets the complexity of celebrated accelerated iterative Bregman projections (IBP), that is $\widetilde O(mn^2\sqrt n/\e)$, however, with no limitations unlike (accelerated) IBP, that is numerically unstable when regularization parameter is small. The second algorithm, based on area-convexity and dual extrapolation, improves the previously best-known convergence rates for Wasserstein barycenter problem enjoying $\widetilde O(mn^2/\e)$ complexity.