Computing the optimal transport distance between statistical distributions is
a fundamental task in machine learning. One remarkable recent advancement is
entropic regularization and the Sinkhorn algorithm, which utilizes only matrix
scaling and guarantees an approximated solution with near-linear runtime.
Despite the success of the Sinkhorn algorithm, its runtime may still be slow
due to the potentially large number of iterations needed for convergence. To
achieve possibly super-exponential convergence, we present
Sinkhorn-Newton-Sparse (SNS), an extension to the Sinkhorn algorithm, by
introducing early stopping for the matrix scaling steps and a second stage
featuring a Newton-type subroutine. Adopting the variational viewpoint that the
Sinkhorn algorithm maximizes a concave Lyapunov potential, we offer the insight
that the Hessian matrix of the potential function is approximately sparse.
Sparsification of the Hessian results in a fast $O(n^2)$ per-iteration
complexity, the same as the Sinkhorn algorithm. In terms of total iteration
count, we observe that the SNS algorithm converges orders of magnitude faster
across a wide range of practical cases, including optimal transportation
between empirical distributions and calculating the Wasserstein $W_1, W_2$
distance of discretized densities. The empirical performance is corroborated by
a rigorous bound on the approximate sparsity of the Hessian matrix.

通过引入早停止和牛顿类型子程序，Sinkhorn-Newton-Sparse（SNS）算法提供了超指数收敛，并且在实际情况下收敛速度比 Sinkhorn 算法快几个数量级，包括离散密度的经验分布之间的最优输运和计算 Wasserstein W1，W2 距离。