Improved Complexity Bounds in Wasserstein Barycenter Problem

MaRDI QIDQ6350913zbMATH OpenFDO

Authors Darina Dvinskikh, Daniil Tiapkin

Publication date 9 October 2020

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 $widetildeO(m{n}^{2}sqrtn/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 $widetildeO(m{n}^2/e)$ complexity.

This page was built for publication: Improved Complexity Bounds in Wasserstein Barycenter Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6350913)