Key points are not available for this paper at this time.
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 Rᵈ. 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 - ( (-c_/) ) achievable via Hilbert's projective metric. Specifically, we prove a contraction rate value of 1- (²/c_²) when has a bounded log-density. In some cases, such as when is log-concave and the cost function is c (x, y) =- x, y, this rate improves to 1- (/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.
Chizat et al. (Mon,) studied this question.