Exponential Convergence of Sinkhorn Under Regularization Scheduling
Exponential Convergence of Sinkhorn Under Regularization Scheduling
复制标题
DOI：
10.48550/arxiv.2207.00736
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Jingbang Chen;Yang P. Liu;Richard Peng;Arvind Ramaswami
中科院分区：
文献类型：
--
作者：
Jingbang Chen;Yang P. Liu;Richard Peng;Arvind Ramaswami
2013年，Cuturi[Cut13]引入了矩阵缩放的Sinkhorn算法作为计算正则化最优运输问题解的方法。为了获得更好的收敛速度以获得更高精度的解，我们对正则化调度下的Sinkhorn算法进行了理解，并在此基础上对其进行了改进，使正则化参数周期性地自适应加倍。在具有整数供需的最优运输问题中，我们证明了这种改进的Sinkhor型算法具有指数收敛速度，迭代复杂度依赖于$\log(1/varepsilon)，而不是以前的分析[Cut13][ANWR17]中的$\varepsilon^{-O(1)}$。此外，利用成本和运力调整过程，一般的最优运输问题也可以以对数依赖于$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 $\eta$ 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.