Effective dynamics of the Sinkhorn algorithm in the regime of low entropy regularization

Abstract

The Sinkhorn algorithm is the de facto standard method for numerically solving entropy-regularized optimal transport problems over finite sets. In this work, we investigate a phenomenon arising when Sinkhorn is applied with a small regularization parameter $\tau$: the evolution of the dual variables (the logarithm of the scaling factors) is approximately piecewise-linear, while the primal variables (the approximate transport plans) exhibit a saddle-to-saddle type behavior. We prove that as $\tau \to 0$, the Sinkhorn iterates indeed converge to a continuous-time curve consistent with these observations, when time is rescaled as $t=\tau k$, and we characterize the limiting "cold Sinkhorn" dynamics explicitly. In particular, we show that it acts as a dual optimization dynamics for the unregularized problem with properties analogous to the simplex algorithm. Notably, this dynamics converges in finite time to an unregularized solution, implying a novel guarantee for the Sinkhorn algorithm itself: it achieves $\tilde{O}(\tau )$ dual suboptimality in $k=O({\tau }^{-1})$ iterations, instead of $k=O({\tau }^{-2})$ as existing analyses would suggest.

45 pages, 4 figures