# Improved Complexity Bounds in Wasserstein Barycenter Problem

arXiv: https://arxiv.org/abs/2010.04677 · HTML: https://mlsanity.com/paper/2010.04677/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2020.

## Built on by (most cited first, 9 of 9)

- [Wasserstein K-means for clustering probability distributions](https://mlsanity.com/paper/2209.06975/) (2022)
- [Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees](https://mlsanity.com/paper/2110.03313/) (2021)
- [Fixed Support Tree-Sliced Wasserstein Barycenter](https://mlsanity.com/paper/2109.03431/) (2021)
- [Distributed Saddle-Point Problems Under Similarity](https://mlsanity.com/paper/2107.10706/) (2021)
- [On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methods](https://mlsanity.com/paper/2312.13970/) (2023)
- [An Accelerated Stochastic Variance-Reduced Algorithm for Entropic Wasserstein Barycenters](https://mlsanity.com/paper/2203.00813/) (2022)
- [Analysis of Kernel Mirror Prox for Measure Optimization](https://mlsanity.com/paper/2403.00147/) (2024)
- [On Robust Wasserstein Barycenter: The Model and Algorithm](https://mlsanity.com/paper/2312.15762/) (2023)
- [Approximative Algorithms for Multi-Marginal Optimal Transport and Free-Support Wasserstein Barycenters](https://mlsanity.com/paper/2202.00954/) (2022)

## Abstract (arXiv)

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(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 widetilde O(mn2/e) complexity.