论文标题
正规化计划下的sindhorn的指数收敛
Exponential Convergence of Sinkhorn Under Regularization Scheduling
论文作者
论文摘要
2013年，Cuturi [Cut13]引入了用于矩阵缩放的sindhorn算法，作为一种计算正规最佳运输问题解决方案的方法。在本文中，针对高精度解决方案的更好的收敛速率，我们致力于了解正规化调度下的sindhorn算法，从而将其修改为适应性地将正则化参数$η$η$翻倍的机制。我们证明，这种修改后的Sinkhorn版本具有指数收敛速率作为迭代复杂性，具体取决于$ \ log（1/\ varepsilon）$，而不是先前分析中的$ \ varepsilon^{ - o（1）} $，来自先前的分析[cut13] [cut13] [andr17]在具有整体供求的最佳运输问题中。此外，通过成本和容量缩放程序，可以通过对数$ 1/\ varepsilon $的对数依赖性解决一般的最佳运输问题。
In 2013, Cuturi [Cut13] introduced the Sinkhorn algorithm for matrix scaling as a method to compute solutions to regularized optimal transport problems. In this paper, aiming at a better convergence rate for a high accuracy solution, we work on understanding the Sinkhorn algorithm under regularization scheduling, and thus modify it with a mechanism that adaptively doubles the regularization parameter $η$ periodically. We prove that such modified version of Sinkhorn has an exponential convergence rate as iteration complexity depending on $\log(1/\varepsilon)$ instead of $\varepsilon^{-O(1)}$ from previous analyses [Cut13][ANWR17] in the optimal transport problems with integral supply and demand. Furthermore, with cost and capacity scaling procedures, the general optimal transport problem can be solved with a logarithmic dependence on $1/\varepsilon$ as well.
