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 converge 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.
翻译:在这项工作中,我们为多种边际正规化的最佳运输问题建议了一个分批版本的Greenkhorn算法。我们的框架非常笼统,足以涵盖某些现有的算法,如双边环境的Sinkhorn和Greenkhorn算法,以及(greedy)多边最佳运输的MultiSinkhorn。我们根据反复的布雷格曼预测法和贪婪控制法的特性提供了完全的趋同分析。获得了全球线性趋同率和对迭代复杂性的明确约束。在进行上述计算时,我们的结果提供了新的洞察力和/或改进了现有的算法。