Sample Complexity of Sinkhorn Divergences

Optimal transport (OT) distances and maximum mean discrepancies (MMD) are now routinely used in machine learning to compare probability measures. Our focus in this paper is on Sinkhorn divergences (SDs), a regularized variant of OT distances that can interpolate, depending on the regularization strength ε, between OT (ε = 0) and MMD (ε = ∞). Although the tradeoff induced by that regularization is by now well understood computationally (OT, SDs and MMD require respectively O(n³log n), O(n²) and n²operations to compare two samples of size n), much less is known in terms of the sample complexity of SDs, namely bounding the gap between the evaluation of SDs on two densities vs. samples from these densities. That complexity for OT and MMD stand at two extremes: O(1/n^1/d) for OT in dimension d and O(1/√n) for MMD. that for SDs has only been studied empirically. In this paper, we (i) derive a bound on the approximation error made with SDs when approximating OT as a function of the regularizer ε, (ii) prove that the optimizers of regularized OT are bounded in a Sobolev (RKHS) ball independent of the two measures and (iii) reformulate SDs as a maximization problem in a RKHS to obtain a sample complexity in 1/√n (as in MMD), with a constant that depends however on ε, making the bridge between OT and MMD complete.