Efficient algorithms with fast rates for online learning

Nous nous intéressons à la conception d'algorithmes d'apprentissage dans un cadre séquentiel. À chaque instant, l'agent doit faire une prédiction à partir des informations à sa disposition et améliorer sa stratégie après avoir observé le résultat attendu. Pour analyser ces algorithmes, nous nous plaçons dans le cadre de l'apprentissage séquentiel, donc la spécificité est de ne faire aucune hypothèse sur la manière dont sont générées les données. La perte cumulée de l'algorithme est comparée à celle du meilleur estimateur dans une classe de fonction pré-définie. L'analyse doit apporter des garanties sur la différence de performance, aussi appelée regret, quelle que soit la suite d'observations. Dans ce cadre, nous avons étudié trois applications particulières : la régression des moindres carrés, la régression logistique et la sélection de portefeuille. L'attention a été portée sur la conception de nouveaux algorithmes efficaces maintenant des performances statistiques proches de l'optimal. Dans chaque cas, des vitesses de convergences rapides sont atteignables, mais des problèmes spécifiques émergents lorsque l'on cherche à améliorer la complexité de calcul. Les algorithmes résultant de ces travaux ont été implémentés et testés sur des jeux de données pour montrer leur intérêt pratique.