# Sharper Exponential Convergence Rates for Sinkhorn's Algorithm in Continuous Settings

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

## Key facts

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

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

- [Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasing](https://mlsanity.com/paper/2408.11620/) (2024)
- [A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm](https://mlsanity.com/paper/2412.09235/) (2024)
- [New Trends in the Stability of Sinkhorn Semigroups](https://mlsanity.com/paper/2601.12633/) (2026)
- [Robust Sublinear Convergence Rates for Iterative Bregman Projections](https://mlsanity.com/paper/2602.01372/) (2026)
- [Hessian stability and convergence rates for entropic and Sinkhorn potentials via semiconcavity](https://mlsanity.com/paper/2504.11133/) (2025)
- [Designing Algorithms for Entropic Optimal Transport from an Optimisation Perspective](https://mlsanity.com/paper/2507.12246/) (2025)
- [Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate](https://mlsanity.com/paper/2510.25287/) (2025)
- [Unfolding with a Wasserstein Loss](https://mlsanity.com/paper/2603.20903/) (2026)

## Abstract (arXiv)

We study the convergence rate of Sinkhorn's algorithm for solving entropy-regularized optimal transport problems when at least one of the probability measures, μ, admits a density over ℝd. For a semi-concave cost function bounded by c∞ and a regularization parameter λ > 0, we obtain exponential convergence guarantees on the dual sub-optimality gap with contraction rate polynomial in λ/c∞. This represents an exponential improvement over the known contraction rate 1 - Theta(exp(-c∞/λ)) achievable via Hilbert's projective metric. Specifically, we prove a contraction rate value of 1-Theta(λ2/c_∞2) when μ has a bounded log-density. In some cases, such as when μ is log-concave and the cost function is c(x,y)=-langle x, y rangle, this rate improves to 1-Theta(λ/c_∞). The latter rate matches the one that we derive for the transport between isotropic Gaussian measures, indicating tightness in the dependency in λ/c_∞. Our results are fully non-asymptotic and explicit in all the parameters of the problem.