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, mu, admits a density over R-d. For a semi-concave cost function bounded by cand a regularization parameter lambda > 0, we obtain exponential convergence guarantees on the dual sub-optimality gap with contraction rates that are polynomial in lambda/c(infinity). This represents an exponential improvement over the known contraction rate 1-Theta(exp(-c(infinity)/lambda)) achievable via Hilbert's projective metric. Specifically, we prove a contraction rate value of 1-Theta(lambda(2)/c(infinity)(2)) when mu has a bounded log-density. In some cases, such as when mu is log-concave and the cost function is c(x, y) _-(x, y), this rate improves to 1-Theta (lambda/c(infinity)). The latter rate matches the one that we derive for the transport between isotropic Gaussian measures, indicating tightness in the dependency in lambda/c(infinity). Our results are fully non-asymptotic and explicit in all the parameters of the problem.