Accelerating Sinkhorn for Entropy-Regularized Optimal Transport

Abstract

We propose Acc-Sinkhorn, a simple accelerated variant of Sinkhorn for entropy-regularized optimal transport (EOT). The method is derived from a bilevel optimization view: Sinkhorn row scaling solves the inner variable $u$ exactly and defines the reduced dual objective $f(v)={\min }_{u}F(u,v)$, while the remaining column scaling is a unit-step dual mirror descent step in $v$. This structure yields a Hessian-driven Nesterov acceleration that keeps Sinkhorn's scaling form and per-iteration cost, using only extrapolated combinations of Sinkhorn iterates. We prove an $\mathcal{O}(1/k^2)$ rate under a verifiable stability condition. For an $\epsilon$-approximation of unregularized OT, the resulting complexity is $\tilde{\mathcal{O}}(n^2/\epsilon )$, improved from $\tilde{\mathcal{O}}(n^2/{\epsilon }^2)$ for Sinkhorn. On synthetic problems, color transfer, and word alignment, Acc-Sinkhorn gives a $10\times$--$30\times$ speedup over Sinkhorn at small regularization.