# Convergence of Batch Greenkhorn for Regularized Multimarginal Optimal Transport

arXiv: https://arxiv.org/abs/2112.00838 · HTML: https://mlsanity.com/paper/2112.00838/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 23 references that are in the map.
- First posted on arXiv 1 Dec 2021.

## Builds on (most cited first, 9 of 9)

- [AttGAN: Facial Attribute Editing by Only Changing What You Want](https://mlsanity.com/paper/1711.10678/) (2017)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [An Optimal Transport approach for the Schr"odinger bridge problem and convergence of Sinkhorn algorithm](https://mlsanity.com/paper/1911.06850/) (2019)
- [Generalized Self-Concordant Functions: A Recipe for Newton-Type Methods](https://mlsanity.com/paper/1703.04599/) (2017)
- [On the Complexity of Approximating Multimarginal Optimal Transport](https://mlsanity.com/paper/1910.00152/) (2019)
- [Regularized Optimal Transport and the Rot Mover's Distance](https://mlsanity.com/paper/1610.06447/) (2016)
- [Hardness results for Multimarginal Optimal Transport problems](https://mlsanity.com/paper/2012.05398/) (2020)
- [The method of Bregman projections in deterministic and stochastic convex feasibility problems](https://mlsanity.com/paper/2101.01704/) (2021)

## Abstract (arXiv)

In this work we propose a batch version of the Greenkhorn algorithm for multimarginal regularized optimal transport problems. Our framework is general enough to cover, as particular cases, some existing algorithms like Sinkhorn and Greenkhorn algorithm for the bi-marginal setting, and (greedy) MultiSinkhorn for multimarginal optimal transport. We provide a complete convergence analysis, which is based on the properties of the iterative Bregman projections (IBP) method with greedy control. Global linear rate of convergence and explicit bound on the iteration complexity are obtained. When specialized to above mentioned algorithms, our results give new insights and/or improve existing ones.