Sample Complexity of Sinkhorn divergences

MaRDI QIDQ6307773zbMATH OpenFDO

Authors Aude Genevay, Lénaïc Chizat, Francis Bach, Marco Cuturi, Gabriel Peyré

Publication date 5 October 2018

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 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}logn)$, $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/sqrtn$ 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/sqrtn$ (as in MMD), with a constant that depends however on $varepsilon$, making the bridge between OT and MMD complete.

This page was built for publication: Sample Complexity of Sinkhorn divergences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6307773)