Title: On the Complexity of Approximating Wasserstein Barycenter,
Abstract: We study the complexity of approximating Wassertein barycenter of $m$
discrete measures, or histograms of size $n$ by contrasting two alternative
approaches, both using entropic regularization. The first approach is based on
the Iterative Bregman Projections (IBP) algorithm for which our novel analysis
gives a complexity bound proportional to $\frac{mn^2}{\varepsilon^2}$ to
approximate the original non-regularized barycenter.
Using an alternative accelerated-gradient-descent-based approach, we obtain a
complexity proportional to $\frac{mn^{2.5}}{\varepsilon} $. As a byproduct, we
show that the regularization parameter in both approaches has to be
proportional to $\varepsilon$, which causes instability of both algorithms when
the desired accuracy is high. To overcome this issue, we propose a novel
proximal-IBP algorithm, which can be seen as a proximal gradient method, which
uses IBP on each iteration to make a proximal step. We also consider the
question of scalability of these algorithms using approaches from distributed
optimization and show that the first algorithm can be implemented in a
centralized distributed setting (master/slave), while the second one is
amenable to a more general decentralized distributed setting with an arbitrary
network topology.