Accelerating Sinkhorn for Entropy-Regularized Optimal Transport

Zeyi Xu, Long Chen · 2026

Read Accelerating Sinkhorn for Entropy-Regularized Optimal Transport by Zeyi Xu, Long Chen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30267.txt.

Introduction

Zeyi Xu and Long Chen propose Acc-Sinkhorn, a faster variant of Sinkhorn for entropy-regularized optimal transport. From a bilevel view, row scaling solves the inner variable, while column scaling is a dual mirror descent step. This yields a Hessian acceleration keeping Sinkhorn's scaling form, using only combinations of iterates. They prove a rate improving with the square of iteration count under a stability condition, with dependence cut from squared to linear. On synthetic color transfer and word alignment problems, Acc-Sinkhorn gives tenfold to thirtyfold speedup over Sinkhorn.

Catalog record

CREATORZeyi Xu, Long Chen
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68715
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.30267

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Accelerating Sinkhorn for Entropy-Regularized Optimal Transport Zeyi Xu, Long Chen 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 u exactly and defines the reduced dual objective f ⁡ ( v ) = min u ⁡ F ⁡ ( u , v ) f(v)=\min_{u}F(u,v) , while the remaining column scaling is a unit-step dual mirror descent step in v 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 𝒪 ⁡ ( 1 / k 2 ) \mathcal{O}(1/k^{2}) rate under a verifiable stability condition. For an ε \varepsilon -approximation of unregularized OT, the resulting complexity is 𝒪 ~ ​ ( n 2 / ε ) \widetilde{\mathcal{O}}(n^{2}/\varepsilon) , improved from 𝒪 ~ ​ ( n 2 / ε 2 ) \widetilde{\mathcal{O}}(n^{2}/\varepsilon^{2}) for Sinkhorn. On synthetic problems, color transfer, and word alignment, Acc-Sinkhorn gives a 10 × 10\times – 30 × 30\times speedup over Sinkhorn at small regularization. 1 Introduction Entropic optimal transport. Given two discrete distributions a\in\mathbb{R}^{n}_{+} and b\in\mathbb{R}^{m}_{+} , the entropy-regularized optimal transport (EOT) problem is \min_{P\in\Pi(a,b)}\langle C,P\rangle+\varepsilon\sum_{i,j}P_{ij}(\log P_{ij}-1), (1) where C\in\mathbb{R}^{n\times m}_{+} is a cost matrix, \varepsilon>0 controls the strength of the entropic regularization, and \Pi(a,b):=\Big\{P\in\mathbb{R}^{n\times m}_{+}:\;\sum_{j}P_{ij}=a_{i},\;i=1,\ldots,n,\quad\sum_{i}P_{ij}=b_{j},\;j=1,\ldots,m\Big\} is the transportation polytope. Since its introduction to machine learning by 14 , EOT has become a standard tool in generative modeling, domain adaptation, image processing, computer vision, and natural language processing [ 19 , 13 , 30 , 32 , 2 ] . The original OT problem \min_{P\in\Pi(a,b)}\langle C,P\rangle (2) is a linear program and can be solved by standard LP methods, including simplex and interior-point methods [ 25 ] . These methods scale poorly for large problems: P has nm entries, interior-point methods require large KKT solves, and simplex-type methods may need many pivots on degenerate transport polytopes. In contrast, EOT has a unique positive minimizer and admits simple \mathcal{O}(nm) -per-iteration algorithms that exploit the transport structure and are easy to parallelize on GPUs. Sinkhorn algorithm. The Sinkhorn algorithm [ 29 ] alternately rescales the rows and columns of the kernel matrix K=\exp(-C/\varepsilon) to enforce the marginal constraints. Each iteration costs \mathcal{O}(nm) and is easy to parallelize. Its convergence has been studied through Hilbert’s projective metric, block coordinate descent, sharp \varepsilon -dependent estimates, and mirror descent in continuous and discrete time [ 17 , 5 , 20 , 8 , 27 , 24 , 21 , 3 , 11 ] . Despite these advances, a central question remains: can Sinkhorn be accelerated to improve its accuracy dependence without losing its simplicity? Related Work. We call a method accelerated if its error decays as \mathcal{O}(1/k^{2}) rather than the \mathcal{O}(1/k) rate of Sinkhorn, where k is the number of full Sinkhorn-type iterations. For simplicity, we discuss complexity for m=n . For an \varepsilon -approximation of the original OT problem, the total cost is often \mathcal{O}(n^{p}/\varepsilon^{q}) for positive p and q . Existing acceleration methods fall into three broad categories. (i) Coordinate-wise and stochastic methods. Coordinate-wise and stochastic variants, such as Greenkhorn, reduce the cost of each iteration by updating only part of the variables or by using stochastic estimates [ 1 , 22 , 18 ] . These methods can improve practical efficiency, but they retain the \mathcal{O}(1/k) convergence behavior of Sinkhorn and thus do not improve its dependence on \varepsilon . (ii) Nesterov acceleration and primal-dual methods. Accelerated primal-dual methods, such as APDAGD, improve the \varepsilon -dependence of Sinkhorn by applying Nesterov-type acceleration or accelerated mirror descent to the EOT dual problem [ 15 , 22 ] . However, they typically require line search or adaptation to local smoothness and are more complex to implement than Sinkhorn. (iii) Sinkhorn variants with modified update rules. Sinkhorn variants with modified update rules, such as overrelaxed Sinkhorn and annealed Sinkhorn, keep the scaling structure of Sinkhorn while changing the update or regularization schedule [ 31 , 10 ] . They can improve local convergence or practical behavior, but they do not give a global \mathcal{O}(1/k^{2}) acceleration with a parameter-free update. In short, existing methods do not simultaneously achieve an accelerated \mathcal{O}(1/k^{2}) rate, \mathcal{O}(n^{2}/\varepsilon) complexity, and a parameter-free simple implementation; see Table 1 . Table 1 : Comparison of algorithms for entropy-regularized optimal transport ( n=m ). Method Rate Total complexity Parameters L,\mu Sinkhorn [ 14 , 1 ] \mathcal{O}(1/k) \widetilde{\mathcal{O}}(n^{2}/\varepsilon^{2}) free Greenkhorn [ 1 , 22 ] \mathcal{O}(1/k) \widetilde{\mathcal{O}}(n^{2}/\varepsilon^{2}) free Overrelaxed Sinkhorn [ 31 ] O(\rho^{k}) (local) \widetilde{\mathcal{O}}(n^{2}/\varepsilon) (local) spectral parameter APDAGD [ 15 , 22 ] \mathcal{O}(1/k^{2}) \widetilde{\mathcal{O}}(n^{5/2}/\varepsilon) linesearch for L APDAMD [ 22 ] \mathcal{O}(1/k^{2}) \widetilde{\mathcal{O}}(n^{2}\sqrt{\delta}/\varepsilon) linesearch for L Annealed Sinkhorn [ 10 ] \mathcal{O}(1/\sqrt{k}) heuristic schedule Acc-Sinkhorn (ours) \mathcal{O}(1/k^{2}) \widetilde{\mathcal{O}}(n^{2}/\varepsilon) L=1 ; homotopy \mu Our contribution. The main contribution of this paper is Acc-Sinkhorn , a simple accelerated variant of Sinkhorn that keeps the \mathcal{O}(nm) per-iteration cost of Sinkhorn while improving the convergence rate from \mathcal{O}(1/k) to \mathcal{O}(1/k^{2}) . As shown in Table 1 , Acc-Sinkhorn is the only method in the table that combines accelerated convergence, Sinkhorn-level per-iteration cost, and a simple update rule without line search. Its smoothness parameter is fixed by the geometry, namely L=1 , and the strong-convexity parameter \mu is handled by a homotopy schedule rather than by manual tuning. Numerically, Acc-Sinkhorn achieves a 10\times – 30\times speedup over Sinkhorn on synthetic datasets, color transfer, and word alignment at small \varepsilon . The acceleration is built on a bilevel view of Sinkhorn. Let F(u,v) be the dual objective of ( 1 ), where (u,v) are the Lagrange multipliers for the marginal constraints. For each fixed v , the inner problem u(v)=\arg\min_{u}F(u,v) is exactly the row-scaling step of Sinkhorn. This defines the reduced outer objective f(v)=F(u(v),v)=\min_{u}F(u,v), and Sinkhorn can be viewed as an exact inner solve in u followed by an outer descent step in v . With the mirror function \phi(v)=\sum_{j}b_{j}(e^{v_{j}}-v_{j}) , the outer Sinkhorn step can be written as the unit-step dual mirror descent update v_{k+1}=v_{k}-\nabla\phi^{*}(\nabla f(v_{k})). (3) Moreover, the dual relative smoothness constant is L=1 : \nabla^{2}\phi^{*}(\nabla f(v))\preceq\nabla^{2}f^{*}(\nabla f(v)). Using this bilevel structure, Acc-Sinkhorn (Algorithm 1 ) applies a Hessian-driven Nesterov acceleration gradient flow [ 6 ] with nonlinear preconditioning to the reduced outer problem. The method keeps two sequences (x_{k},y_{k}) and uses essentially one Sinkhorn step per iteration; the extra cost is only a few vector operations. A homotopy outer loop (Algorithm 2 ) decreases the unknown strong-convexity parameter \mu by a predefined schedule and gives an accelerated \mathcal{O}(1/k^{2}) rate. Acc-Sinkhorn needs \mathcal{O}(\tau^{-1/2}) Sinkhorn steps to reach accuracy \tau , whereas Sinkhorn needs \mathcal{O}(\tau^{-1}) steps. For the unregularized OT problem, this inner complexity is combined with the standard entropic approximation error \mathcal{O}(\varepsilon\log n) . Balancing optimization and regularization errors by setting \tau=\varepsilon^{2} gives an overall complexity of order \mathcal{O}(n^{2}/\varepsilon) for an \varepsilon -approximation of the OT cost. Limitations. In our experiments, Acc-Sinkhorn uses the step size \alpha=\sqrt{2\mu} and shows stable accelerated behavior. The current proof is more conservative: it gives the full accelerated guarantee under a stability condition, which holds for sufficiently small \alpha and can be enforced by linesearch. The gap comes

Read the complete text