[edit]
Improved Complexity Bounds in Wasserstein Barycenter Problem
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:1738-1746, 2021.
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 ˜O(mn2√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 ˜O(mn2/\e) complexity.