Abstract
Optimal transport (OT) and maximum mean discrepancies (MMD) are now routinely used in machine learning to compare probability measures. We focus in this paper on Sinkhorn divergences (SDs), a regularized variant of OT distances which can interpolate, depending on the regularization strength $\varepsilon$, between OT ($\varepsilon=0$) and MMD ($\varepsilon=\infty$). Although the tradeoff induced by that regularization is now well understood computationally, much less is known in terms of their sample complexity. In this paper, we (i) derive a bound on the approximation error made with SDs when approximating OT as a function of the regularizer $\varepsilon$, (ii) prove that the optimizers of regularized OT are bounded in a Sobolev (RKHS) ball independent of the two measures and (iii) provide the first sample complexity bound for SDs, obtained by reformulating SDs as a maximization problem in a RKHS. We thus obtain a scaling in $1/\sqrt{n}$ (as in MMD), with a constant that depends however on $\varepsilon$, making the bridge between OT and MMD complete.
Introduction
In modern machine learning, measuring the distance between probability distributions is fundamental for tasks ranging from generative modeling (GANs) to domain adaptation. Two primary frameworks dominate this space: Optimal Transport (OT) and Maximum Mean Discrepancy (MMD). While OT is geometrically intuitive, it suffers from the "curse of dimensionality," requiring a sample size $n$ that grows exponentially with dimension $d$ (a rate of $n^{-1/d}$). Conversely, MMD is statistically efficient ($1/\sqrt{n}$) but often fails to capture geometric features when distribution supports do not overlap.
Sinkhorn Divergences (SD) were introduced as a middle ground, utilizing entropic regularization to achieve computational efficiency ($O(n^2)$). This paper provides the critical theoretical bridge, proving that Sinkhorn regularization allows these measures to escape the curse of dimensionality, achieving a sample complexity of $O(1/\sqrt{n})$ regardless of dimension.
Theoretical Framework
The authors employ functional analysis and statistical learning theory to dissect the statistical properties of SDs. The core technical contribution lies in proving Sobolev Regularity: the optimal "potential" functions in the dual formulation of regularized OT are shown to be smooth, belonging to a bounded ball in a Sobolev Space (a type of Reproducing Kernel Hilbert Space, or RKHS).
By establishing that these potentials live in an RKHS, the authors apply Rademacher complexity tools from PAC-learning to bound the empirical estimation error. This demonstrates that entropic regularization acts as a smoothing operator; by adding noise, the optimal transport plan is prevented from becoming too "spiky," which is the key mechanism for breaking the curse of dimensionality.
Empirical Results and Insights
The theoretical findings were validated using synthetic benchmarks, including uniform distributions on hypercubes and standard Normal distributions across varying dimensions ($d=2, 3, 7$).
Breaking the Curse of Dimensionality
The paper proves that for any $\varepsilon > 0$, the sample complexity is $O(1/\sqrt{n})$. As shown in Figure 1, for large regularization ($\varepsilon \geq 1$), the convergence curves for different dimensions are nearly identical and parallel, indicating dimension-independent behavior. As $\varepsilon$ decreases, the curves begin to diverge, reflecting the transition back toward the dimension-dependent regime of unregularized OT.
The Regularization Trade-off
While the $1/\sqrt{n}$ rate is guaranteed for any $\varepsilon > 0$, there is a significant trade-off: the constant factor in the bound grows exponentially as $\varepsilon \to 0$ (approximately $e^{1/\varepsilon}$). Figure 2 illustrates this effect; for a fixed dimension, smaller values of $\varepsilon$ result in higher estimation errors for the same number of samples. This highlights the "Goldilocks" challenge of selecting an $\varepsilon$ that balances approximation accuracy with statistical stability.
Conclusion
This work formalizes the statistical advantages of Sinkhorn Divergences, proving they inherit the $1/\sqrt{n}$ sample complexity of MMD while retaining the geometric sensitivity of OT. Future work remains to determine the optimal $\varepsilon$ for a given sample size $n$ and to extend these proofs to non-smooth cost functions like $L_1$, which empirical results suggest may also benefit from similar smoothing effects.
Summary updated