mlsanityData to 7 Oct 2026

On the Convergence Rate of Sinkhorn's Algorithm

arXiv 2212.06000 ↗First posted 12 Dec 2022math.OC math.AP math.PRcited by 16

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 6; 2024: 5; 2025: 4; 2026: 1.

16 papers.

Sort:

By area:

  1. 2023Provably Convergent Schr"odinger Bridge with Applications to Probabilistic Time Series Imputationcited by 26
  2. 2023Fused Gromov-Wasserstein Graph Mixup for Graph-level Classificationscited by 15
  3. 2024Accelerating Sinkhorn Algorithm with Sparse Newton Iterationscited by 9
  4. 2023Hilbert's projective metric for functions of bounded growth and exponential convergence of Sinkhorn's algorithmcited by 8
  5. 2023Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approachcited by 7
  6. 2024Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasingcited by 6
  7. 2025Your contrastive learning problem is secretly a distribution alignment problemcited by 6
  8. 2025PINS: Proximal Iterations with Sparse Newton and Sinkhorn for Optimal Transportcited by 5
  9. 2024A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithmcited by 4
  10. 2023Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methodscited by 2
  11. 2023Sinkhorn Flow: A Continuous-Time Framework for Understanding and Generalizing the Sinkhorn Algorithmcited by 1
  12. 2024Auditing and Enforcing Conditional Fairness via Optimal Transportcited by 1
4 more
  1. 2025Forward Reverse Kernel Regression for the Schr"odinger bridge problemcited by 1
  2. 2024Sketching the Heat Kernel: Using Gaussian Processes to Embed Datacited by 0
  3. 2025Hessian stability and convergence rates for entropic and Sinkhorn potentials via semiconcavitycited by 0
  4. 2026Tilted Schr"odinger Bridge Matchingcited by 0