  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 rate 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.
