# Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 56 references that are in the map.
- First posted on arXiv 13 Apr 2023.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [A survey of the Schr"odinger problem and some of its connections with optimal transport](https://mlsanity.com/paper/1308.0215/) (2013)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Statistical Optimal Transport via Factored Couplings](https://mlsanity.com/paper/1806.07348/) (2018)
- [An Optimal Transport approach for the Schr"odinger bridge problem and convergence of Sinkhorn algorithm](https://mlsanity.com/paper/1911.06850/) (2019)
- [Entropic and displacement interpolation: a computational approach using the Hilbert metric](https://mlsanity.com/paper/1506.04255/) (2015)
- [Quantitative Stability of Regularized Optimal Transport and Convergence of Sinkhorn's Algorithm](https://mlsanity.com/paper/2110.06798/) (2021)
- [An improved central limit theorem and fast convergence rates for entropic transportation costs](https://mlsanity.com/paper/2204.09105/) (2022)
- [On the Convergence Rate of Sinkhorn's Algorithm](https://mlsanity.com/paper/2212.06000/) (2022)
- [Stability of Schr"odinger Potentials and Convergence of Sinkhorn's Algorithm](https://mlsanity.com/paper/2201.10059/) (2022)
- [Quantitative contraction rates for Sinkhorn's algorithm: beyond bounded costs and compact marginals](https://mlsanity.com/paper/2304.04451/) (2023)
- [Learning to solve inverse problems using Wasserstein loss](https://mlsanity.com/paper/1710.10898/) (2017)
- [Quantitative Uniform Stability of the Iterative Proportional Fitting Procedure](https://mlsanity.com/paper/2108.08129/) (2021)
- [Langevin diffusions on the torus: estimation and applications](https://mlsanity.com/paper/1705.00296/) (2017)

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

- [Provably Convergent Schr"odinger Bridge with Applications to Probabilistic Time Series Imputation](https://mlsanity.com/paper/2305.07247/) (2023)
- [Hilbert's projective metric for functions of bounded growth and exponential convergence of Sinkhorn's algorithm](https://mlsanity.com/paper/2311.04041/) (2023)
- [A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm](https://mlsanity.com/paper/2412.09235/) (2024)
- [Sinkhorn Algorithm for Sequentially Composed Optimal Transports](https://mlsanity.com/paper/2412.03120/) (2024)
- [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)
- [Schr"odinger bridge problem via empirical risk minimization](https://mlsanity.com/paper/2602.08374/) (2026)

## Abstract (arXiv)

Computational optimal transport (OT) has recently emerged as a powerful framework with applications in various fields. In this paper we focus on a relaxation of the original OT problem, the entropic OT problem, which allows to implement efficient and practical algorithmic solutions, even in high dimensional settings. This formulation, also known as the Schr"odinger Bridge problem, notably connects with Stochastic Optimal Control (SOC) and can be solved with the popular Sinkhorn algorithm. In the case of discrete-state spaces, this algorithm is known to have exponential convergence; however, achieving a similar rate of convergence in a more general setting is still an active area of research. In this work, we analyze the convergence of the Sinkhorn algorithm for probability measures defined on the d-dimensional torus mathbbTLd, that admit densities with respect to the Haar measure of mathbbTLd. In particular, we prove pointwise exponential convergence of Sinkhorn iterates and their gradient. Our proof relies on the connection between these iterates and the evolution along the Hamilton-Jacobi-Bellman equations of value functions obtained from SOC-problems. Our approach is novel in that it is purely probabilistic and relies on coupling by reflection techniques for controlled diffusions on the torus.