{"ID":5551794,"CreatedAt":"2026-07-02T01:54:51.863792489Z","UpdatedAt":"2026-07-04T09:05:32.635878014Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.00665","arxiv_id":"2607.00665","title":"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 $τ$: 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 $τ\\to 0$, the Sinkhorn iterates indeed converge to a continuous-time curve consistent with these observations, when time is rescaled as $t = τ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}(τ)$ dual suboptimality in $k = O(τ^{-1})$ iterations, instead of $k = O(τ^{-2})$ as existing analyses would suggest.","short_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 $τ$: the evolution of the dual variables (the logarithm of the...","url_abs":"https://arxiv.org/abs/2607.00665","url_pdf":"https://arxiv.org/pdf/2607.00665v1","authors":"[\"Guillaume Wang\"]","published":"2026-07-01T09:13:24Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}