Adaptive Online Learning for Nonparametric Regression

Abstract

Cette thèse s'inscrit dans le domaine de l'apprentissage statistique. Nous nous intéressons à la conception d'algorithmes adaptatifs pour la régression non paramétrique, ainsi qu'à l'analyse de leurs garanties statistiques. Dans un premier temps, nous nous plaçons dans le cadre de la prédiction séquentielle de suites arbitraires, dans lequel les données sont révélées au fil du temps, et sans aucune hypothèse sur la manière dont elles sont générées. À chaque instant, l'algorithme doit produire une prédiction à partir des informations dont il dispose, observe ensuite la perte associée à cette prédiction, puis met à jour sa stratégie en conséquence. La performance est mesurée par le regret, c'est-à-dire l'écart entre la perte cumulée de l'algorithme et celle d'un prédicteur de référence appartenant à une classe de fonctions. Nous considérons en particulier des classes de fonctions lipschitziennes, höldériennes et, plus généralement, des espaces de Besov. Nous utilisons des approches multi-échelles, basées sur des structures d'arbre et des méthodes d'ondelettes, afin de développer des algorithmes à la fois constructifs, adaptatifs et efficaces pour ces classes de référence. L'analyse des algorithmes développés repose sur la théorie minimax. Nous montrons qu'ils atteignent des taux de regret minimax optimaux, tout en s'adaptant à différentes propriétés sous-jacentes des données, telles que la régularité effective de la fonction de référence, ses variations locales, ainsi que la courbure des fonctions de perte considérées. Enfin, nous étudions le cadre statistique usuel, dans lequel les données sont désormais supposées issues d'un modèle stochastique i.i.d. et où la performance de l'algorithme est mesurée par le risque, c'est-à-dire l'erreur de prédiction moyenne sur une nouvelle observation. Nous montrons, par des arguments d'online-to-batch, que nos algorithmes conduisent à des estimateurs qui satisfont, avec grande probabilité, des garanties adaptatives et minimax optimales sur des classes non paramétriques usuelles.