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。我们根据反复的布雷格曼预测法和贪婪控制法的特性提供了完全的趋同分析。获得了全球线性趋同率和对迭代复杂性的明确约束。在进行上述计算时,我们的结果提供了新的洞察力和/或改进了现有的算法。

0
下载
关闭预览

相关内容

【Google-Marco Cuturi】最优传输,339页ppt,Optimal Transport
专知会员服务
46+阅读 · 2021年10月26日
专知会员服务
15+阅读 · 2020年7月27日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
104+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
保序最优传输:Order-preserving Optimal Transport
我爱读PAMI
5+阅读 · 2018年9月16日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2022年2月3日
VIP会员
Top
微信扫码咨询专知VIP会员