Adaptation des méthodes d'apprentissage automatique aux statistiques U.

Résumé Avec la disponibilité croissante de grandes quantités de données, la complexité du calcul est devenue la clé de voûte de nombreux algorithmes d'apprentissage automatique. Les algorithmes d'optimisation stochastique et les méthodes distribuées/décentralisées ont été largement étudiés au cours de la dernière décennie et offrent une évolutivité accrue pour optimiser un risque empirique qui est séparable dans l'échantillon de données. Pourtant, dans un large éventail de problèmes d'apprentissage statistique, le risque est estimé avec précision par des statistiques U, c'est-à-dire des fonctionnelles des données d'apprentissage à faible variance qui prennent la forme de moyennes sur d-tuples. Nous abordons d'abord le problème de l'échantillonnage pour le problème de minimisation du risque empirique. Nous montrons que les risques empiriques peuvent être remplacés par des estimations de Monte-Carlo drastiquement 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. Nous établissons des résultats de déviation uniforme et des exemples numériques montrent que cette approche surpasse les techniques de sous-échantillonnage plus naïves. Nous nous concentrons ensuite sur le sujet de l'estimation décentralisée, où l'échantillon de données est distribué sur un réseau connecté. Nous introduisons de nouveaux algorithmes de commérage aléatoire synchrone et asynchrone qui propagent simultanément les données à travers le réseau et maintiennent des estimations locales de la statistique U d'intérêt. Nous établissons des limites de taux de convergence avec des termes explicites dépendant des données et du réseau. Enfin, nous traitons de l'optimisation décentralisée de fonctions qui dépendent de paires d'observations. Comme dans le cas de l'estimation, nous introduisons une méthode basée sur des mises à jour locales concurrentes et la propagation des données. Notre analyse théorique révèle que les algorithmes proposés préservent le taux de convergence de la double moyenne centralisée jusqu'à un terme de biais additif. Nos simulations illustrent l'intérêt pratique de notre approche.