On the Convergence Rate of Sinkhorn's Algorithm

MaRDI QIDQ6420282zbMATH OpenFDO

Authors Promit Ghosal, Marcel Nutz

Publication date 12 December 2022

Mathematics Subject Classification ID

Linear optimal control problems (49N05) Convex programming (90C25)

Abstract: We study Sinkhorn's algorithm for solving the entropically regularized optimal transport problem. Its iterate $p{i}_t$ is shown to satisfy $H(p{i}_t|p{i}_{\ast })+H(p{i}_{\ast }|p{i}_t)=O(t^{-1})$ where $H$ denotes relative entropy and $p{i}_{\ast }$ 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 $p{i}_{\ast }$ as a function of the marginals, quantified in relative entropy.

This page was built for publication: On the Convergence Rate of Sinkhorn's Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6420282)