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

Abstract

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