Sample Complexity of Sinkhorn Divergences

By Aude Genevay, Lénaïc Chizat, Francis R. Bach, Marco Cuturi, G. Peyr'e. International Conference on Artificial Intelligence and Statistics, 2018

346 citations recorded by the source corpus.

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 \emph{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 (OT, SDs and MMD require respectively $O(n^3\log n)$, $O(n^2)$ and $n^2$ operations given a sample size $n$), much less is known in terms of their \emph{sample complexity}, namely the gap between these quantities, when evaluated using finite samples \emph{vs.} their respective densities. Indeed, while the sample complexity of OT and MMD stand at two extremes, $1/n^{1/d}$ for OT in dimension $d$ and $1/\sqrt{n}$ for MMD, that for SDs has only been studied empirically. In this paper, we \emph{(i)} derive a bound on the approximation error made with SDs when approximating OT as a function of the regularizer $\varepsilon$, \emph{(ii)} prove that the optimizers of regularized OT are bounded in a Sobolev (RKHS) ball independent of the two measures and \emph{(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.

Subfields: Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/dd5e54b08b2c1520d179e88cd524e9bd4fe1f6ab

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Subspace Robust Wasserstein distances (2019, background): “A line of work initiated in (Cuturi, 2013) advocates adding an entropic penalty to the original OT problem, which results in faster and differentiable quantities, as well as improved sample complexity bounds (Genevay et al., 2019).”
Fast geometric learning with symbolic matrices (2020, neutral): “These two regimes correspond to typical applications in computer vision [24, 38] and statistics [43, 46, 48], respectively.”
Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm (2019, methodology): “We conclude noting that while [23] studied the sample complexity of the Sinkhorn divergence, Thm.”