Sharper Exponential Convergence Rates for Sinkhorn's Algorithm in Continuous Settings

We study the convergence rate of Sinkhorn's algorithm for solving entropy-regularized optimal transport problems when at least one of the probability measures, μ, admits a density over ℝd. For a semi-concave cost function bounded by c∞ and a regularization parameter λ > 0, we obtain exponential convergence guarantees on the dual sub-optimality gap with contraction rate polynomial in λ/c∞. This represents an exponential improvement over the known contraction rate 1 - Theta(exp(-c∞/λ)) achievable via Hilbert's projective metric. Specifically, we prove a contraction rate value of 1-Theta(λ2/c_∞2) when μ has a bounded log-density. In some cases, such as when μ is log-concave and the cost function is c(x,y)=-langle x, y rangle, this rate improves to 1-Theta(λ/c_∞). The latter rate matches the one that we derive for the transport between isotropic Gaussian measures, indicating tightness in the dependency in λ/c_∞. Our results are fully non-asymptotic and explicit in all the parameters of the problem.