Batch Greenkhorn Algorithm for Entropic-Regularized Multimarginal Optimal Transport: Linear Rate of Convergence and Iteration Complexity
Abstract
In this work we propose a batch multimarginal version of the Greenkhorn algorithm for the entropic-regularized optimal transport problem. This framework is general enough to cover, as particular cases, existing Sinkhorn and Greenkhorn algorithms for the bi-marginal setting, and greedy MultiSinkhorn for the general multimarginal case. We provide a comprehensive convergence analysis based on the properties of the iterative Bregman projections method with greedy control. Linear rate of convergence as well as explicit bounds on the iteration complexity are obtained. When specialized to the above mentioned algorithms, our results give new convergence rates or provide key improvements over the state-of-the-art rates. We present numerical experiments showing that the flexibility of the batch can be exploited to improve performance of Sinkhorn algorithm both in bi-marginal and multimarginal settings.
Cite
Text
Kostic et al. "Batch Greenkhorn Algorithm for Entropic-Regularized Multimarginal Optimal Transport: Linear Rate of Convergence and Iteration Complexity." International Conference on Machine Learning, 2022.Markdown
[Kostic et al. "Batch Greenkhorn Algorithm for Entropic-Regularized Multimarginal Optimal Transport: Linear Rate of Convergence and Iteration Complexity." International Conference on Machine Learning, 2022.](https://mlanthology.org/icml/2022/kostic2022icml-batch/)BibTeX
@inproceedings{kostic2022icml-batch,
title = {{Batch Greenkhorn Algorithm for Entropic-Regularized Multimarginal Optimal Transport: Linear Rate of Convergence and Iteration Complexity}},
author = {Kostic, Vladimir R. and Salzo, Saverio and Pontil, Massimiliano},
booktitle = {International Conference on Machine Learning},
year = {2022},
pages = {11529-11558},
volume = {162},
url = {https://mlanthology.org/icml/2022/kostic2022icml-batch/}
}