# Accelerating Sinkhorn for Entropy-Regularized Optimal Transport

arXiv: https://arxiv.org/abs/2605.30267 · HTML: https://mlsanity.com/paper/2605.30267/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2026.

## Built on by (most cited first, 1 of 1)

- [Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp](https://mlsanity.com/paper/2608.11760/) (2026)

## Abstract (arXiv)

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.