Descriptif

La majorité des problèmes d'apprentissage sont formulés comme des problèmes d'optimisation,
à partir de l'observation d'un échantillon de données (ensemble d'entraînement). L'optimisation
d'un objectif défini à partir de cet échantillon permet de proposer un estimateur qui a une bonne
performance sur l'ensemble d'apprentissage. Cependant, on s'intéresse généralement à la
capacité de généralisation de cet estimateur, c'est à dire sa performance sur une nouvelle
observation. Avec l'émergence des grandes quantités de données depuis les années 2000, le
lien entre l'algorithme utilisé et la capacité de généralisation de l'estimateur associé est devenu
un sujet majeur.
Aujourd'hui, la question de la généralisation est encore une problématique de recherche
majeure, tant pour ses aspects théoriques que pratiques.
Dans ce cours, on s'intéresse à l'ensemble des résultats tant théoriques que heuristiques qui
permettent d'aborder ce problème. Plus précisément, on étudiera dans un premier temps les
différentes approches qui permettent d'obtenir des garanties théoriques quant à la
généralisation des algorithmes, en particulier les approches liées à la complexité, à la stabilité
et aux méthodes d'arrêt anticipé (Early stopping, approximation stochastique). Dans une
seconde partie, on étudiera les approches heuristiques et les différences (expliquées ou
constatées) dans le cadre du deep learning (non convexe et over-parametrized).
Prérequis : connaissances élémentaires en optimisation convexe et statistiques. Avoir suivi le
cours d'optimisation pour les data-sciences permettra de mieux cerner les différents algorithmes
en jeu.
Liste de références (non exhaustive) : - Rademacher and Gaussian Complexities: Risk
Bounds and Structural Results, P. Bartlett, S. Mendelson - The Tradeoffs of Large Scale
Learning, L. Bottou, O. Bousquet - Stability and Generalization, O. Bousquet, A. Elisseef - Train
faster, generalize better: Stability of stochastic gradient descent, M. Hardt, B. Recht, Y. Singer -
Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n), F. Bach,
E. Moulines - Understanding deep learning requires rethinking generalization, C. Zhang, S.
Bengio, M. Hardt, B. Recht, O. Vinyals - On early stopping in gradient descent learning, Y Yao,
L. Rosasco, and A. Caponnetto - Generalization properties of multiple passes stochastic
gradient method, S. Villa - Competing with the empirical risk minimizer in a single pass, R.
Frostig, R. Ge, S. M. Kakade, A. Sidford - Deep Learning and Generalization, O. Bousquet
Modalités de contrôle
Présentation d’article / projet