论文标题
重新思考snnhorn算法的初始化
Rethinking Initialization of the Sinkhorn Algorithm
论文作者
论文摘要
虽然最初将最佳运输（OT）问题最初是作为线性程序提出的，但对于许多应用，熵正则化的添加在计算和统计学上都证明是有益的。 Sinkhorn定点算法是解决此正规化问题的最流行方法，因此，已经进行了多次尝试以减少使用其运行时，例如在正则化参数，动量或加速度中退火。这项工作的前提是，sindhorn算法的初始化受到了相对较少的关注，这可能是由于两个先入为主的：由于正规化的OT问题是凸的，因此可能不值得制定良好的初始化，因为任何人都可以正常工作；其次，由于sindhorn算法的输出通常在端到端管道中展开，因此数据依赖于数据的初始化会偏向雅各布的计算。我们挑战了这种传统的观点，并表明与数据相关的初始化器会产生巨大的加速，只要使用隐式分化，就不会影响可不同。我们的初始化依赖于闭合形式用于在1D，高斯或GMM设置中已知的精确或近似OT解决方案。它们可以与最小的调整一起使用，并导致各种OT问题的持续加速。
While the optimal transport (OT) problem was originally formulated as a linear program, the addition of entropic regularization has proven beneficial both computationally and statistically, for many applications. The Sinkhorn fixed-point algorithm is the most popular approach to solve this regularized problem, and, as a result, multiple attempts have been made to reduce its runtime using, e.g., annealing in the regularization parameter, momentum or acceleration. The premise of this work is that initialization of the Sinkhorn algorithm has received comparatively little attention, possibly due to two preconceptions: since the regularized OT problem is convex, it may not be worth crafting a good initialization, since any is guaranteed to work; secondly, because the outputs of the Sinkhorn algorithm are often unrolled in end-to-end pipelines, a data-dependent initialization would bias Jacobian computations. We challenge this conventional wisdom, and show that data-dependent initializers result in dramatic speed-ups, with no effect on differentiability as long as implicit differentiation is used. Our initializations rely on closed-forms for exact or approximate OT solutions that are known in the 1D, Gaussian or GMM settings. They can be used with minimal tuning, and result in consistent speed-ups for a wide variety of OT problems.
