On the Convergence Rate of Sinkhorn’s Algorithm

We study Sinkhorn’s algorithm for solving the entropically regularized optimal transport problem. Its iterate [Formula: see text] is shown to satisfy [Formula: see text], where H denotes relative entropy and [Formula: see text] denotes the optimal coupling. This holds for a large class of cost functions and marginals, including quadratic cost with sub-Gaussian marginals. We also obtain the rate [Formula: see text] for the dual suboptimality and [Formula: see text] for the marginal entropies. More precisely, we derive nonasymptotic bounds, and in contrast to previous results on linear convergence that are limited to bounded costs, our estimates do not deteriorate exponentially with the regularization parameter. We also obtain a stability result for [Formula: see text] as a function of the marginals quantified in relative entropy. Funding: P. Ghosal was supported by the National Science Foundation [Grant DMS-2153661]. M. Nutz was supported by the National Science Foundation [Grants DMS-1812661, DMS-2106056, and DMS-2407074].