Accelerating Sinkhorn for Entropy-Regularized Optimal Transport

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)=minu 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 O(1/k2) rate under a verifiable stability condition. For an varepsilon-approximation of unregularized OT, the resulting complexity is widetildeO(n2/varepsilon), improved from widetildeO(n2/varepsilon2) for Sinkhorn. On synthetic problems, color transfer, and word alignment, Acc-Sinkhorn gives a 10×--30× speedup over Sinkhorn at small regularization.