Optimal transport (OT) provides a powerful mathematical framework for comparing probability distributions, but computing it exactly can be computationally daunting. By adding an entropic regularization term, the problem transforms from a rigid linear program into a smooth optimization landscape. This regularized formulation is traditionally solved using Sinkhorn's algorithm, which alternates between scaling rows and columns to match target marginal distributions.
While Sinkhorn's algorithm is widely celebrated for its simplicity, understanding why and how fast it converges—especially in continuous spaces or when the regularization parameter approaches zero—has long been a theoretical challenge. Recent insights have shifted from pessimistic, worst-case bounds to sharp, non-asymptotic convergence guarantees by uncovering the hidden geometric and operator-theoretic structures of the problem.
Continuous Flows and Contraction Analysis
To understand the deep mechanics of convergence, it is useful to view Sinkhorn's algorithm not merely as discrete matrix scaling, but as the discretization of a continuous-time gradient flow. For instance, David Siska et al. in Gradient Flows for Regularized Stochastic Control Problems established a foundational connection between entropy-regularized stochastic control problems and gradient flows on the space of probability measures. They proved that strong entropic regularization guarantees exponential convergence to a unique invariant measure.
When we look at the continuous-time analog of Sinkhorn's algorithm—known as the Sinkhorn mirror flow—we can analyze its convergence through the lens of contraction analysis. The goal is to show that any two distinct trajectories of the flow exponentially collapse toward one another, guiding the system to the unique optimal transport plan.
Coercivity of the Conditional Expectation Operator
How do we guarantee this contraction property without getting bogged down in intractable analytical conditions? A breakthrough by Anand Srinivasan et al. in A simple contraction criterion for the Sinkhorn mirror flow provides an elegant answer rooted in the coercivity of a conditional expectation operator.
To build intuition, think of Sinkhorn updates as alternating projections. We have a joint probability distribution, and we project functions onto the subspaces defined by its marginals. The conditional expectation operator performs this projection. If this operator is coercive, it means that projecting a function onto one marginal and then onto the other retains a guaranteed fraction of the function's energy; the subspaces do not become orthogonal.
[Function Space] ───(Project to Marginal A)───> [Subspace A]
│
(Project to Marginal B)
│
▼
[Retained Energy ≥ α]
By examining the Gateaux derivative and the second variation of the objective function, the authors demonstrated that ensuring this specific coercivity inequality directly translates into a strict contraction metric for the Sinkhorn flow. This operator-theoretic perspective bridges the gap between abstract functional analysis and the practical convergence rates of optimal transport algorithms.
Unlocking Small Regularization via Geometry
A major practical hurdle in entropic OT is that we often want the regularization parameter ($\lambda$) to be as small as possible to accurately approximate the true, unregularized transport plan. However, general convergence bounds degrade exponentially as $\lambda \to 0$, rendering them practically useless for high-accuracy applications.
The key to overcoming this barrier is to assume the underlying distributions possess geometric structure. Lénaïc Chizat et al. in Sharper Exponential Convergence Rates for Sinkhorn’s Algorithm in Continuous Settings demonstrated that if the marginal measures are log-concave (or have bounded log-density) and the cost function is semi-concave, Sinkhorn's algorithm achieves exponential convergence rates that depend polynomially rather than exponentially on the regularization parameter.
Why does log-concavity matter? Intuitively, log-concave distributions prevent mass from being trapped in isolated, highly concentrated pockets. The probability density fades smoothly, which keeps the underlying Schrödinger potentials stable and prevents the algorithm's iterates from oscillating wildly. In Sharper exponential convergence rates for Sinkhorn's algorithm in continuous settings, the authors demonstrated that these polynomial-dependence rates of $1 - \Theta(\lambda/c_\infty)$ are tight for isotropic Gaussian measures and linear costs, establishing an optimal theoretical benchmark.
Stability and Generalizations
This geometric perspective also unlocks stronger convergence metrics. Rather than just proving that the objective value converges, Marcel Nutz et al. in Stability of Schrödinger potentials and convergence of Sinkhorn’s algorithm proved that for quadratic costs and subgaussian marginals, Sinkhorn's algorithm converges to the true optimal transport plan in the strict total variation norm. This implies that small perturbations in the input marginals lead to stable, controlled changes in the resulting potentials.
To handle the challenges of unbounded costs, Promit Ghosal et al. in On the Convergence Rate of Sinkhorn’s Algorithm established exponential moment estimates for the iterates, providing robust, non-asymptotic bounds that do not deteriorate with the regularization parameter.
The reach of these convergence principles extends well beyond standard probability spaces:
- Constrained Domains: Wei Deng et al. in Reflected Schrödinger Bridge for Constrained Generative Modeling connected static optimal transport to dynamic Reflected Schrödinger Bridges, allowing generative models to operate smoothly within complex, bounded domains by leveraging reflected Brownian motion.
- Sign-Indefinite Data: Anqi Dong et al. in Data Assimilation for Sign-indefinite Priors: A generalization of Sinkhorn's algorithm generalized Sinkhorn's algorithm to calibrate sign-indefinite data arrays (such as those found in financial or gene regulatory networks), proving that the linear convergence properties carry over even when dealing with non-probability measures.
- Wasserstein Barycenters: In the optimization of population barycenters, Joaquin Fontbona et al. in Stochastic gradient descent for barycenters in Wasserstein space introduced pseudo-associative Karcher means to guarantee uniqueness and derive explicit convergence rates for online stochastic gradient descent algorithms.
Ultimately, whether viewed as a continuous gradient flow contracting via operator coercivity or as a discrete algorithm stabilized by log-concave geometry, the convergence of entropic optimal transport relies on a beautiful harmony between geometry and functional analysis.
Key Foundational Work
Sharper Exponential Convergence Rates for Sinkhorn’s Algorithm in Continuous Settings (2024) — contributed 4 concept elements to this direction.
Stability of Schrödinger Potentials and Convergence of Sinkhorn's Algorithm (2023) — contributed 1 concept elements to this direction.
Gradient Flows for Regularized Stochastic Control Problems (2024) — contributed 1 concept elements to this direction.