Improved Complexity Bounds in Wasserstein Barycenter Problem

Darina Dvinskikh, Daniil Tiapkin
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 $\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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-dvinskikh21a, title = { Improved Complexity Bounds in Wasserstein Barycenter Problem }, author = {Dvinskikh, Darina and Tiapkin, Daniil}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {1738--1746}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/dvinskikh21a/dvinskikh21a.pdf}, url = {https://proceedings.mlr.press/v130/dvinskikh21a.html}, 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. } }
Endnote
%0 Conference Paper %T Improved Complexity Bounds in Wasserstein Barycenter Problem %A Darina Dvinskikh %A Daniil Tiapkin %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-dvinskikh21a %I PMLR %P 1738--1746 %U https://proceedings.mlr.press/v130/dvinskikh21a.html %V 130 %X 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.
APA
Dvinskikh, D. & Tiapkin, D.. (2021). Improved Complexity Bounds in Wasserstein Barycenter Problem . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:1738-1746 Available from https://proceedings.mlr.press/v130/dvinskikh21a.html.

Related Material