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 ${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.

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