# Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasing

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 32 references that are in the map.
- First posted on arXiv 21 Aug 2024.

## Builds on (most cited first, 17 of 17)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Learning with a Wasserstein Loss](https://mlsanity.com/paper/1506.05439/) (2015)
- [Optimal Entropy-Transport problems and a new Hellinger-Kantorovich distance between positive measures](https://mlsanity.com/paper/1508.07941/) (2015)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Optimal Transport Tools (OTT): A JAX Toolbox for all things Wasserstein](https://mlsanity.com/paper/2201.12324/) (2022)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [Faster Wasserstein Distance Estimation with the Sinkhorn Divergence](https://mlsanity.com/paper/2006.08172/) (2020)
- [An Optimal Transport approach for the Schr"odinger bridge problem and convergence of Sinkhorn algorithm](https://mlsanity.com/paper/1911.06850/) (2019)
- [Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM](https://mlsanity.com/paper/2206.08873/) (2022)
- [An explicit analysis of the entropic penalty in linear programming](https://mlsanity.com/paper/1806.01879/) (2018)
- [Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport](https://mlsanity.com/paper/1711.01851/) (2017)
- [On the Convergence Rate of Sinkhorn's Algorithm](https://mlsanity.com/paper/2212.06000/) (2022)
- [Optimal transport: discretization and algorithms](https://mlsanity.com/paper/2003.00855/) (2020)
- [Sharper Exponential Convergence Rates for Sinkhorn's Algorithm in Continuous Settings](https://mlsanity.com/paper/2407.01202/) (2024)
- [Convergence Rates of the Regularized Optimal Transport : Disentangling Suboptimality and Entropy](https://mlsanity.com/paper/2306.06940/) (2023)

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

- [Faster Computation of Entropic Optimal Transport via Stable Low Frequency Modes](https://mlsanity.com/paper/2506.14780/) (2025)
- [Avoiding Premature Collapse: Adaptive Annealing for Entropy-Regularized Structural Inference](https://mlsanity.com/paper/2601.23039/) (2026)
- [Unregularized limit of stochastic gradient method for Wasserstein distributionally robust optimization](https://mlsanity.com/paper/2506.04948/) (2025)
- [Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport](https://mlsanity.com/paper/2510.27340/) (2025)
- [Learning Permutation from Structure Without Supervision](https://mlsanity.com/paper/2605.25551/) (2026)
- [Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory](https://mlsanity.com/paper/2609.33814/) (2026)
- [Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning](https://mlsanity.com/paper/2610.04264/) (2026)

## Abstract (arXiv)

Sinkhorn's algorithm is a method of choice to solve large-scale optimal transport (OT) problems. In this context, it involves an inverse temperature parameter β that determines the speed-accuracy trade-off. To improve this trade-off, practitioners often use a variant of this algorithm, Annealed Sinkhorn, that uses an nondecreasing sequence (βt)_t∈ mathbbN where t is the iteration count. However, besides for the schedule βt=Theta(log t) which is impractically slow, it is not known whether this variant is guaranteed to actually solve OT. Our first contribution answers this question: we show that a concave annealing schedule asymptotically solves OT if and only if βt→+∞ and βt-βt-1→ 0. The proof is based on an equivalence with Online Mirror Descent and further suggests that the iterates of Annealed Sinkhorn follow the solutions of a sequence of relaxed, entropic OT problems, the regularization path. An analysis of this path reveals that, in addition to the well-known "entropic" error in Theta(β-1t), the annealing procedure induces a "relaxation" error in Theta(βt-βt-1). The best error trade-off is achieved with the schedule βt = Theta(√t) which, albeit slow, is a universal limitation of this method. Going beyond this limitation, we propose a simple modification of Annealed Sinkhorn that reduces the relaxation error, and therefore enables faster annealing schedules. In toy experiments, we observe the effectiveness of our Debiased Annealed Sinkhorn's algorithm: a single run of this algorithm spans the whole speed-accuracy Pareto front of the standard Sinkhorn's algorithm.