Convergence of Batch Greenkhorn for Regularized Multimarginal Optimal Transport
Not on the map. Why?
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 9 of its 23 references that are in the map. First posted on arXiv 1 Dec 2021.
Builds on
9 of 23 references.
References · 9
- 2017AttGAN: Facial Attribute Editing by Only Changing What You Wantcited by 241
- 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 219
- 2018Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithmcited by 111
- 2019An Optimal Transport approach for the Schr"odinger bridge problem and convergence of Sinkhorn algorithmcited by 38
- 2017Generalized Self-Concordant Functions: A Recipe for Newton-Type Methodscited by 33
- 2019On the Complexity of Approximating Multimarginal Optimal Transportcited by 27
- 2016Regularized Optimal Transport and the Rot Mover's Distancecited by 24
- 2020Hardness results for Multimarginal Optimal Transport problemscited by 12
- 2021The method of Bregman projections in deterministic and stochastic convex feasibility problemscited by 1
Built on by
Not cited yet.