  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.
