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 \(\mathbb {R}^d\) . For a semi-concave cost function bounded by \(c_{\infty }\) and 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_{\infty }\) . This represents an exponential improvement over the known contraction rate \(1 - \Theta (\exp (-c_{\infty }/\lambda ))\) achievable via Hilbert’s projective metric. Specifically, we prove a contraction rate value of \(1-\Theta (\lambda ^2/c_\infty ^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)=-\langle x, y\rangle \) , this rate improves to \(1-\Theta (\lambda /c_\infty )\) . The latter rate matches the one that we derive for the transport between isotropic Gaussian measures, indicating tightness in the dependency in \(\lambda /c_\infty \) . Our results are fully non-asymptotic and explicit in all the parameters of the problem.
