Complexité de l'échantillon des divergences du Sinkhorn.

Résumé Le transport optimal (OT) et les divergences moyennes maximales (MMD) sont désormais couramment utilisés en apprentissage automatique pour comparer des mesures de probabilité. Nous nous concentrons dans cet article sur les \emph{Divergences de Sinkhorn} (SDs), une variante régularisée des distances OT qui peut interpoler, selon la force de régularisation $\varepsilon$, entre OT ($\varepsilon=0$) et MMD ($\varepsilon=\infty$). Bien que le compromis induit par cette régularisation soit maintenant bien compris sur le plan informatique (OT, SDs et MMD nécessitent respectivement $O(n^3\log n)$, $O(n^2)$ et $n^2$ opérations pour une taille d'échantillon $n$), on en sait beaucoup moins en termes de leur \emph{sample complexity}, à savoir l'écart entre ces quantités, lorsqu'elles sont évaluées à l'aide d'échantillons finis \emph{vs.} leurs densités respectives. En effet, alors que la complexité d'échantillon d'OT et de MMD se situe à deux extrêmes, $1/n^{1/d}$ pour OT en dimension $d$ et $1/\sqrt{n}$ pour MMD, celle des SDs n'a été étudiée qu'empiriquement. Dans cet article, nous \emph{(i)} dérivons une borne sur l'erreur d'approximation faite avec les SDs lors de l'approximation d'OT en fonction du régularisateur $\varepsilon$, \emph{(ii)} prouvons que les optimiseurs d'OT régularisés sont bornés dans une boule de Sobolev (RKHS) indépendante des deux mesures et \emph{(iii)} fournissons la première borne de complexité d'échantillon pour les SDs, obtenue en reformulant les SDs comme un problème de maximisation dans un RKHS. Nous obtenons ainsi une mise à l'échelle en $1/\sqrt{n}$ (comme dans la MMD), avec une constante qui dépend toutefois de $\varepsilon$, rendant le pont entre OT et MMD complet.