Minimisation empirique du risque à grande échelle : Optimisation des statistiques U incomplètes.

Résumé Dans un large éventail de problèmes d'apprentissage statistique tels que le classement, le clustering ou l'apprentissage métrique entre autres, le risque est estimé avec précision par des U-statistiques de degré d ≥ 1, c'est-à-dire des fonctionnelles des données d'apprentissage à faible variance qui prennent la forme de moyennes sur k-tuples. D'un point de vue informatique, le calcul de ces statistiques est très coûteux, même pour un échantillon de taille modérée n, car il nécessite de calculer la moyenne de O(n^d) termes. Cela rend les procédures d'apprentissage reposant sur l'optimisation de telles fonctions de données difficilement réalisables en pratique. L'objectif principal de cet article est de montrer que, de manière frappante, de tels risques empiriques peuvent être remplacés par des estimations de Monte-Carlo radicalement plus simples en termes de calcul et basées sur O(n) termes seulement, généralement appelées statistiques U incomplètes, sans nuire au taux d'apprentissage O(1/√n) des procédures de minimisation des risques empiriques (ERM). À cette fin, nous établissons des résultats de déviation uniforme décrivant l'erreur commise lors de l'approximation d'un processus U par sa version incomplète sous des hypothèses de complexité appropriées. Des extensions à la sélection de modèles, aux situations de taux rapides et à diverses techniques d'échantillonnage sont également considérées, ainsi qu'une application à la descente de gradient stochastique pour la MRE. Enfin, des exemples numériques sont présentés afin de fournir des preuves empiriques solides que l'approche que nous promouvons surpasse largement les techniques de sous-échantillonnage plus naïves.