论文标题
加速的Bregman原始偶对偶的方法应用于最佳运输和Wasserstein Barycenter问题
Accelerated Bregman Primal-Dual methods applied to Optimal Transport and Wasserstein Barycenter problems
论文作者
论文摘要
本文讨论了混合原始偶（HPD）类型算法的效率，近似于解决离散的最佳运输（OT）和Wasserstein Barycenter（WB）问题，并且有和没有熵正则化。我们的第一个贡献是分析表明，这些方法在理论上和实际上都产生了最先进的收敛率。接下来，我们将Malitsky和Pock在2018年提出的线路搜索的HPD算法扩展到双重空间具有Bregman Divergence的环境，并且双重功能相对强烈地传达了Bregman的内核。基于目标平滑，该扩展为OT和WB问题产生了一种新方法，该方法也达到了最先进的收敛速率。最后，我们基于缩放的熵函数引入了新的Bregman差异，该功能使该算法在数值上稳定并降低平滑性，从而导致OT和WB问题的稀疏解决方案。我们通过数值实验和比较来补充我们的发现。
This paper discusses the efficiency of Hybrid Primal-Dual (HPD) type algorithms to approximate solve discrete Optimal Transport (OT) and Wasserstein Barycenter (WB) problems, with and without entropic regularization. Our first contribution is an analysis showing that these methods yield state-of-the-art convergence rates, both theoretically and practically. Next, we extend the HPD algorithm with linesearch proposed by Malitsky and Pock in 2018 to the setting where the dual space has a Bregman divergence, and the dual function is relatively strongly convex to the Bregman's kernel. This extension yields a new method for OT and WB problems based on smoothing of the objective that also achieves state-of-the-art convergence rates. Finally, we introduce a new Bregman divergence based on a scaled entropy function that makes the algorithm numerically stable and reduces the smoothing, leading to sparse solutions of OT and WB problems. We complement our findings with numerical experiments and comparisons.
