# On the Convergence Rate of Sinkhorn's Algorithm

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2022.

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

- [Provably Convergent Schr"odinger Bridge with Applications to Probabilistic Time Series Imputation](https://mlsanity.com/paper/2305.07247/) (2023)
- [Fused Gromov-Wasserstein Graph Mixup for Graph-level Classifications](https://mlsanity.com/paper/2306.15963/) (2023)
- [Accelerating Sinkhorn Algorithm with Sparse Newton Iterations](https://mlsanity.com/paper/2401.12253/) (2024)
- [Hilbert's projective metric for functions of bounded growth and exponential convergence of Sinkhorn's algorithm](https://mlsanity.com/paper/2311.04041/) (2023)
- [Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach](https://mlsanity.com/paper/2304.06549/) (2023)
- [Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasing](https://mlsanity.com/paper/2408.11620/) (2024)
- [Your contrastive learning problem is secretly a distribution alignment problem](https://mlsanity.com/paper/2502.20141/) (2025)
- [PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transport](https://mlsanity.com/paper/2502.03749/) (2025)
- [A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm](https://mlsanity.com/paper/2412.09235/) (2024)
- [Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods](https://mlsanity.com/paper/2301.13006/) (2023)
- [Sinkhorn Flow: A Continuous-Time Framework for Understanding and Generalizing the Sinkhorn Algorithm](https://mlsanity.com/paper/2311.16706/) (2023)
- [Auditing and Enforcing Conditional Fairness via Optimal Transport](https://mlsanity.com/paper/2410.14029/) (2024)
- [Forward Reverse Kernel Regression for the Schr"odinger bridge problem](https://mlsanity.com/paper/2507.00640/) (2025)
- [Tilted Schr"odinger Bridge Matching](https://mlsanity.com/paper/2609.34642/) (2026)
- [Sketching the Heat Kernel: Using Gaussian Processes to Embed Data](https://mlsanity.com/paper/2403.07929/) (2024)
- [Hessian stability and convergence rates for entropic and Sinkhorn potentials via semiconcavity](https://mlsanity.com/paper/2504.11133/) (2025)

## Abstract (arXiv)

We study Sinkhorn's algorithm for solving the entropically regularized optimal transport problem. Its iterate πt is shown to satisfy H(πt|π*)+H(π*|πt)=O(t-1) where H denotes relative entropy and π* the optimal coupling. This holds for a large class of cost functions and marginals, including quadratic cost with subgaussian marginals. We also obtain the rate O(t-1) for the dual suboptimality and O(t-2) for the marginal entropies. More precisely, we derive non-asymptotic bounds, and in contrast to previous results on linear convergence that are limited to bounded costs, our estimates do not deteriorate exponentially with the regularization parameter. We also obtain a stability result for π* as a function of the marginals, quantified in relative entropy.