Improved Complexity Bounds in Wasserstein Barycenter Problem

Darina Dvinskikh · Daniil Tiapkin


Keywords: [ Algorithms, Optimization and Computation Methods ] [ Convex optimization ]

[ Abstract ]
[ Slides
Wed 14 Apr 6 a.m. PDT — 8 a.m. PDT

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

Chat is not available.