On the complexity of the optimal transport problem with graph-structured cost

Jiaojiao Fan, Isabel Haasler, Johan Karlsson, Yongxin Chen
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:9147-9165, 2022.

Abstract

Multi-marginal optimal transport (MOT) is a generalization of optimal transport to multiple marginals. Optimal transport has evolved into an important tool in many machine learning applications, and its multi-marginal extension opens up for addressing new challenges in the field of machine learning. However, the usage of MOT has been largely impeded by its computational complexity which scales exponentially in the number of marginals. Fortunately, in many applications, such as barycenter or interpolation problems, the cost function adheres to structures, which has recently been exploited for developing efficient computational methods. In this work we derive computational bounds for these methods. In particular, with $m$ marginal distributions supported on $n$ points, we provide a $ \mathcal{\tilde O}(d(\mathcal{T})m n^{w(G)+1}\epsilon^{-2})$ bound for a $\epsilon$-accuracy when the problem is associated with a graph that can be factored as a junction tree with diameter $d(\mathcal{T})$ and tree-width $w(G)$. For the special case of the Wasserstein barycenter problem, which corresponds to a star-shaped tree, our bound is in alignment with the existing complexity bound for it.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-fan22a, title = { On the complexity of the optimal transport problem with graph-structured cost }, author = {Fan, Jiaojiao and Haasler, Isabel and Karlsson, Johan and Chen, Yongxin}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {9147--9165}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/fan22a/fan22a.pdf}, url = {https://proceedings.mlr.press/v151/fan22a.html}, abstract = { Multi-marginal optimal transport (MOT) is a generalization of optimal transport to multiple marginals. Optimal transport has evolved into an important tool in many machine learning applications, and its multi-marginal extension opens up for addressing new challenges in the field of machine learning. However, the usage of MOT has been largely impeded by its computational complexity which scales exponentially in the number of marginals. Fortunately, in many applications, such as barycenter or interpolation problems, the cost function adheres to structures, which has recently been exploited for developing efficient computational methods. In this work we derive computational bounds for these methods. In particular, with $m$ marginal distributions supported on $n$ points, we provide a $ \mathcal{\tilde O}(d(\mathcal{T})m n^{w(G)+1}\epsilon^{-2})$ bound for a $\epsilon$-accuracy when the problem is associated with a graph that can be factored as a junction tree with diameter $d(\mathcal{T})$ and tree-width $w(G)$. For the special case of the Wasserstein barycenter problem, which corresponds to a star-shaped tree, our bound is in alignment with the existing complexity bound for it. } }
Endnote
%0 Conference Paper %T On the complexity of the optimal transport problem with graph-structured cost %A Jiaojiao Fan %A Isabel Haasler %A Johan Karlsson %A Yongxin Chen %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-fan22a %I PMLR %P 9147--9165 %U https://proceedings.mlr.press/v151/fan22a.html %V 151 %X Multi-marginal optimal transport (MOT) is a generalization of optimal transport to multiple marginals. Optimal transport has evolved into an important tool in many machine learning applications, and its multi-marginal extension opens up for addressing new challenges in the field of machine learning. However, the usage of MOT has been largely impeded by its computational complexity which scales exponentially in the number of marginals. Fortunately, in many applications, such as barycenter or interpolation problems, the cost function adheres to structures, which has recently been exploited for developing efficient computational methods. In this work we derive computational bounds for these methods. In particular, with $m$ marginal distributions supported on $n$ points, we provide a $ \mathcal{\tilde O}(d(\mathcal{T})m n^{w(G)+1}\epsilon^{-2})$ bound for a $\epsilon$-accuracy when the problem is associated with a graph that can be factored as a junction tree with diameter $d(\mathcal{T})$ and tree-width $w(G)$. For the special case of the Wasserstein barycenter problem, which corresponds to a star-shaped tree, our bound is in alignment with the existing complexity bound for it.
APA
Fan, J., Haasler, I., Karlsson, J. & Chen, Y.. (2022). On the complexity of the optimal transport problem with graph-structured cost . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:9147-9165 Available from https://proceedings.mlr.press/v151/fan22a.html.

Related Material