  We study Sinkhorn's algorithm for solving the entropically regularized
optimal transport problem. Its iterate $\pi_{t}$ is shown to satisfy
$H(\pi_{t}|\pi_{*})+H(\pi_{*}|\pi_{t})=O(t^{-1})$ where $H$ denotes relative
entropy and $\pi_{*}$ the optimal coupling. This holds for a large class of
cost functions and marginals, including quadratic cost with subgaussian
marginals. We also obtain the rate $O(t^{-1})$ for the dual suboptimality and
$O(t^{-2})$ for the marginal entropies. More precisely, we derive
non-asymptotic 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 $\pi_{*}$ as a function of the marginals, quantified in relative
entropy.
