Paperlane

no. 7 · Tuesday 3 November 2026

Accelerating Sinkhorn for Entropy-Regularized Optimal Transport

Long Chen and Zeyi Xu

math.OC · v3

Abstract

Entropy-regularized optimal transport is widely used to compare and align data distributions, but Sinkhorn can converge slowly at small regularization. We introduce Acc-Sinkhorn, a two-state Hessian-driven Nesterov iteration built on the dual mirror geometry of the row-reduced Sinkhorn map. The method combines momentum acceleration with an inexpensive descent safeguard, sta- ble log-domain evaluation, and a prescribed homotopy schedule requiring neither line search nor curvature estimation. We prove global linear convergence of the safeguarded method, rule out con- secutive restarts, and establish local accelerated convergence for fixed parameters without restarts through spectral analysis. Numerical comparisons with six methods on synthetic problems, color transfer, and bilingual word alignment show runtime speedups of up to about 26 over Sinkhorn, with additional rendering-accuracy comparisons for color transfer.

fields
Optimization and Control
pdf ↗ page arXiv:2605.30267 ↗