Accelerating Sinkhorn Algorithm with Sparse Newton Iterations
Xun Tang Michael Shavlovsky Holakou Rahmanian Elisa Tardini Kiran Koshy Thekumparampil Tesi Xiao Lexing Ying
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.