Sharper exponential convergence rates for Sinkhorn’s algorithm in continuous settings

This paper presents a significant advancement in understanding the convergence rates of Sinkhorn’s algorithm, a widely used method for solving entropy-regularized optimal transport problems, particularly in continuous settings where at least one of the probability measures possesses a density.

Optimal Transport (OT) is a powerful mathematical framework with applications across machine learning, statistics, and physics. Sinkhorn’s algorithm provides an efficient way to compute approximations to OT solutions by introducing an entropy regularization term. A long-standing challenge in the field has been to precisely characterize the algorithm’s convergence speed. Previous work typically fell into two categories:
1. Exponential convergence rates: These guaranteed rapid convergence but came with a severe dependency on problem parameters (specifically, the ratio of the cost function’s oscillation, \(c_\infty\), to the regularization parameter, \(\lambda\)), where the contraction rate was exponentially worse for large \(c_\infty/\lambda\). This made the theoretical guarantees loose in many practical scenarios.
2. Polynomial convergence rates: These offered better, polynomial dependence on \(c_\infty/\lambda\) but exhibited a slower, polynomial decay in the number of iterations.

The key innovation of this paper is to bridge this gap, achieving a “best-of-both-worlds” scenario: exponential convergence with robust, polynomial dependence on \(c_\infty/\lambda\), under specific geometric assumptions on the problem’s inputs. This represents a substantial improvement over prior results.

The main innovations are:

1. Sharper Exponential Rates: The paper provides exponential convergence guarantees for the dual sub-optimality gap with contraction rates of \(1 - \Theta(\lambda^2/c_\infty^2)\) and, in some cases, \(1 - \Theta(\lambda/c_\infty)\). These rates are polynomial in \(\lambda/c_\infty\), a significant improvement over the \(1 - \exp(-c_\infty/\lambda)\) type dependence previously known for exponential convergence. The \(1 - \Theta(\lambda/c_\infty)\) rate is particularly sharp, matching the known rate for transport between isotropic Gaussian measures, suggesting its tightness.
2. Leveraging Geometric Structure: The improved rates are obtained by exploiting additional geometric assumptions on the problem’s components. Specifically, the paper considers cases where the cost function is semi-concave (a common property for many relevant costs like squared Euclidean distance) and one of the marginal probability measures (source or target) has either a bounded log-density or a log-concave density. These assumptions allow for a deeper analysis of the problem’s underlying structure.
3. Novel Analytical Tools: The enhanced convergence analysis relies on a combination of sophisticated mathematical tools:
   • Bernstein’s Inequality: This concentration inequality is employed to derive a sharper one-step improvement bound for Sinkhorn’s algorithm. Unlike prior analyses that used less refined inequalities like Hoeffding’s, Bernstein’s inequality allows replacing a crude bound dependent on the cost oscillation \(c_\infty\) with a term related to the variance of relevant quantities, leading to tighter estimates.
   • Prékopa-Leindler Inequality: This fundamental inequality from convex geometry and probability theory is crucial for establishing strong-concavity estimates of the semi-dual functional. This strong concavity, in turn, allows linking the variance terms (introduced via Bernstein’s inequality) back to the overall sub-optimality gap, enabling the proof of exponential convergence.

The main prior ingredients needed for this work are:

• Entropy-Regularized Optimal Transport: The core problem formulation, including its primal and dual forms, is foundational.
• Sinkhorn’s Algorithm: The iterative scheme itself, involving alternating “c-transforms” (or their entropic counterparts), is the central object of study.
• Dual Formulation of OT: The paper analyzes the convergence of the dual sub-optimality gap, a standard approach in optimization.
• Hilbert’s Projective Metric: Earlier analyses of Sinkhorn’s algorithm utilized this metric to establish contraction properties and exponential convergence, providing a baseline against which the new “sharper” rates are compared.
• Concepts from Convex Analysis: Notions like semi-concavity/convexity, strong convexity, and properties of convex conjugates (c-transforms) are essential building blocks.
• Probability Theory and Concentration Inequalities: Beyond Bernstein’s and Prékopa-Leindler, a general understanding of measure theory and properties of random variables is implicitly used throughout the derivations.

In essence, this paper significantly pushes the theoretical understanding of Sinkhorn’s algorithm by demonstrating that, under reasonable geometric conditions on the data, one can achieve highly desirable exponential convergence rates that are far more robust and practically relevant than previously understood.