On the Complexity of Approximating Wasserstein Barycenters

Alexey Kroshnin, Nazarii Tupitsa, Darina Dvinskikh, Pavel Dvurechensky, Alexander Gasnikov, Cesar Uribe
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:3530-3540, 2019.

Abstract

We study the complexity of approximating the Wasserstein barycenter of m discrete measures, or histograms of size n, by contrasting two alternative approaches that use entropic regularization. The first approach is based on the Iterative Bregman Projections (IBP) algorithm for which our novel analysis gives a complexity bound proportional to mn2/ε2 to approximate the original non-regularized barycenter. On the other hand, using an approach based on accelerated gradient descent, we obtain a complexity proportional to mn2/ε. As a byproduct, we show that the regularization parameter in both approaches has to be proportional to ε, which causes instability of both algorithms when the desired accuracy is high. To overcome this issue, we propose a novel proximal-IBP algorithm, which can be seen as a proximal gradient method, which uses IBP on each iteration to make a proximal step. We also consider the question of scalability of these algorithms using approaches from distributed optimization and show that the first algorithm can be implemented in a centralized distributed setting (master/slave), while the second one is amenable to a more general decentralized distributed setting with an arbitrary network topology.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-kroshnin19a, title = {On the Complexity of Approximating {W}asserstein Barycenters}, author = {Kroshnin, Alexey and Tupitsa, Nazarii and Dvinskikh, Darina and Dvurechensky, Pavel and Gasnikov, Alexander and Uribe, Cesar}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {3530--3540}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/kroshnin19a/kroshnin19a.pdf}, url = {https://proceedings.mlr.press/v97/kroshnin19a.html}, abstract = {We study the complexity of approximating the Wasserstein barycenter of $m$ discrete measures, or histograms of size $n$, by contrasting two alternative approaches that use entropic regularization. The first approach is based on the Iterative Bregman Projections (IBP) algorithm for which our novel analysis gives a complexity bound proportional to ${mn^2}/{\varepsilon^2}$ to approximate the original non-regularized barycenter. On the other hand, using an approach based on accelerated gradient descent, we obtain a complexity proportional to ${mn^{2}}/{\varepsilon}$. As a byproduct, we show that the regularization parameter in both approaches has to be proportional to $\varepsilon$, which causes instability of both algorithms when the desired accuracy is high. To overcome this issue, we propose a novel proximal-IBP algorithm, which can be seen as a proximal gradient method, which uses IBP on each iteration to make a proximal step. We also consider the question of scalability of these algorithms using approaches from distributed optimization and show that the first algorithm can be implemented in a centralized distributed setting (master/slave), while the second one is amenable to a more general decentralized distributed setting with an arbitrary network topology.} }
Endnote
%0 Conference Paper %T On the Complexity of Approximating Wasserstein Barycenters %A Alexey Kroshnin %A Nazarii Tupitsa %A Darina Dvinskikh %A Pavel Dvurechensky %A Alexander Gasnikov %A Cesar Uribe %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-kroshnin19a %I PMLR %P 3530--3540 %U https://proceedings.mlr.press/v97/kroshnin19a.html %V 97 %X We study the complexity of approximating the Wasserstein barycenter of $m$ discrete measures, or histograms of size $n$, by contrasting two alternative approaches that use entropic regularization. The first approach is based on the Iterative Bregman Projections (IBP) algorithm for which our novel analysis gives a complexity bound proportional to ${mn^2}/{\varepsilon^2}$ to approximate the original non-regularized barycenter. On the other hand, using an approach based on accelerated gradient descent, we obtain a complexity proportional to ${mn^{2}}/{\varepsilon}$. As a byproduct, we show that the regularization parameter in both approaches has to be proportional to $\varepsilon$, which causes instability of both algorithms when the desired accuracy is high. To overcome this issue, we propose a novel proximal-IBP algorithm, which can be seen as a proximal gradient method, which uses IBP on each iteration to make a proximal step. We also consider the question of scalability of these algorithms using approaches from distributed optimization and show that the first algorithm can be implemented in a centralized distributed setting (master/slave), while the second one is amenable to a more general decentralized distributed setting with an arbitrary network topology.
APA
Kroshnin, A., Tupitsa, N., Dvinskikh, D., Dvurechensky, P., Gasnikov, A. & Uribe, C.. (2019). On the Complexity of Approximating Wasserstein Barycenters. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:3530-3540 Available from https://proceedings.mlr.press/v97/kroshnin19a.html.

Related Material