Apprentissage séquentiel et actif pour l'optimisation – SeqALO
Le but de ce projet est de développer cette théorie pour qu’elle puisse prendre en compte des cas réels d’application. D’abord, il est important dans de nombreuses applications sensibles aux risques (comme l’agronomie) de considérer d’autres fonctions d’utilité. Deuxièmement, de nombreux applications comme les essais cliniques font apparaître une structure naturelle sur l’ensemble X et des restrictions sur l’ensemble des fonctions f possibles. Par exemple, il peut être connu à l’avance que F[f(x, .)] est une fonction monotone, unimodale, ou à variations lentes. Troisièmement, dans des cas comme les systèmes de recommandation, l’ensemble X peut être très grand mais posséder une structure de graphe pouvant être exploitée pour accélérer énormément l’optimisation. Enfin, l’espace X peut être continu (comme c’est le cas de certains paramètres en autoML); nous traiterons ce cas en combinant les analyses des deux cas précédents avec les idées classiques de statistique non-paramétrique.
Cette chaire se destine également à développer l’enseignement en intelligence artificielle à l’ENS de Lyon, établissement très sélectif accueillant un nombre limité d’étudiants se destinant à travailler dans la recherche. C’est un aspect important de la mission pour laquelle j’ai été recruté l’an dernier à l’intersection des départements de mathématiques et d’informatique. En m’appuyant sur les excellents formations d’informatique théorique et de mathématiques générales, je veux former un groupe de spécialistes en apprentissage statistique chaque année, avec des bases solides en statistique mathématique et en théorie de l’apprentissage en général, et une spécialisation en optimisation bruitée et pour le traitement des code numériques.
Ce projet développe un champ d’expertise de la recherche française. Cette approche de l’optimisation a connu de nombreux succès au cours des dix dernières années, et constitue l’une des briques essentielles de récents succès marquants de l’intelligence artificielle : moteurs de recherche personnalisés, systèmes de recommandation et de publicité, apprentissage par renforcement et MCTS, systèmes d’enchères en ligne, l’autoML, etc. Ce projet contribue à tous ces aspects, fournissant à la fois une théorie générale de la complexité pour l’optimisation bruitée et et des algorithmes et méta-algorithmes permettant de traiter des cas particuliers.
Publications :
Non-Asymptotic Sequential Tests for Overlapping Hypotheses and applica tion to near optimal arm identification in bandit models
Aurélien Garivier, Emilie Kaufmann
Sequential Analysis vol.40, Mar. 2021 (pp.61-96)
A Non-asymptotic Approach to Best-Arm Identification for Gaussian Bandits
Antoine Barrier, Aurélien Garivier, Tomáš Kocák
International Joint Conference on Artificial Intelligence (IJCAI) n°31 (AISTAT’22)
Navigating to the Best Policy in Markov Decision Processes
Aymen Al Marjani, Aurélien Garivier, Alexandre Proutiere
Neural Information Processing Systems Dec. 2021
Sequential Algorithms for Testing Closeness of Distributions
Aadil Oufkir, Omar Fawzi, Nicolas Flammarion, Aurélien Garivier
Neural Information Processing Systems (spotlight) Dec. 2021
A A/B/n Testing with Control in the Presence of Subpopulations
Yoan Russac, Christina Katsimerou, Dennis Bohle, Olivier Cappé, Aurélien Garivier, Wouter M Koolen
Neural Information Processing Systems Dec. 2021
Fast Rate Learning in Stochastic First Price Bidding
Juliette Achddou, Olivier Cappé, Aurélien Garivier
Asian Conference on Machine Learning (ACML) n°13 Nov. 2021
Epsilon Best Arm Identification in Spectral Bandits
Tomáš Kocák, Aurélien Garivier
International Joint Conference on Artificial Intelligence (IJCAI) n°30 Aug. 2021
Self-Concordant Analysis of Generalized Linear Bandits with Forgetting
Yoan Russac, Olivier Cappé, Aurélien Garivier
24th International Conference on Artificial Intelligence and Statistics (AISTAT’21) Apr. 2021
Efficient Algorithms for Stochastic Repeated Second-price Auctions
Juliette Achddou, Olivier Cappé, Aurélien Garivier
Algorithmic Learning Theory (ALT) n o 32, Mar. 2021
Le recrutement de nouveaux collaborateurs (postdoc et doctorants) va permettre de poursuivre le projet notamment sur son workpackage 4 (optimisation continue) jusqu'alors en standby. Le développement d'un axe plus important que prévu sur l'apprentissage par renforcement (modèles de décision markoviens) vient enrichir les objectifs initiaux, de même que l'importance que tend à prendre les travaux portant sur les algorithmes garantissant la confidentialité des utilisateurs (differential privacy).
Publications :
Non-Asymptotic Sequential Tests for Overlapping Hypotheses and applica tion to near optimal arm identification in bandit models
Aurélien Garivier, Emilie Kaufmann
Sequential Analysis vol.40, Mar. 2021 (pp.61-96)
A Non-asymptotic Approach to Best-Arm Identification for Gaussian Bandits
Antoine Barrier, Aurélien Garivier, Tomáš Kocák
International Joint Conference on Artificial Intelligence (IJCAI) n°31 (AISTAT’22)
Navigating to the Best Policy in Markov Decision Processes
Aymen Al Marjani, Aurélien Garivier, Alexandre Proutiere
Neural Information Processing Systems Dec. 2021
Sequential Algorithms for Testing Closeness of Distributions
Aadil Oufkir, Omar Fawzi, Nicolas Flammarion, Aurélien Garivier
Neural Information Processing Systems (spotlight) Dec. 2021
A A/B/n Testing with Control in the Presence of Subpopulations
Yoan Russac, Christina Katsimerou, Dennis Bohle, Olivier Cappé, Aurélien Garivier, Wouter M Koolen
Neural Information Processing Systems Dec. 2021
Fast Rate Learning in Stochastic First Price Bidding
Juliette Achddou, Olivier Cappé, Aurélien Garivier
Asian Conference on Machine Learning (ACML) n°13 Nov. 2021
Epsilon Best Arm Identification in Spectral Bandits
Tomáš Kocák, Aurélien Garivier
International Joint Conference on Artificial Intelligence (IJCAI) n°30 Aug. 2021
Self-Concordant Analysis of Generalized Linear Bandits with Forgetting
Yoan Russac, Olivier Cappé, Aurélien Garivier
24th International Conference on Artificial Intelligence and Statistics (AISTAT’21) Apr. 2021
Efficient Algorithms for Stochastic Repeated Second-price Auctions
Juliette Achddou, Olivier Cappé, Aurélien Garivier
Algorithmic Learning Theory (ALT) n o 32, Mar. 2021
Le but de ce projet est de développer une nouvelle théorie de l’optimisation séquentielle et active, de la mettre en œuvre dans des projets industriels, et de développer une filière d’enseignement dédiée à l’apprentissage automatique en général et à la théorie de la décision séquentielle en particulier au sein de l’ENS de Lyon.
Soit f:X*E?R un code numérique stochastique, où X désigne un espace de variables de contrôle et où O désigne un espace probabilité représentant les variables non contrôlées. Au temps t, un agent choisit un point x_t à l’aide de ses observations précédentes, et il observe f(x_t, ?) pour un certain ? aléatoire de E. Quelle est la meilleure stratégie possible pour optimiser x->F[f(x, .)], si F est une fonction d’utilité (comme par exemple l’espérance) ?
On se place dans le cadre PAC, avec un paramètre de risque d et une tolérance e. Dans le cas simpliste où X est un ensemble fini, où f peut être n’importe quelle fonction, et où F est l’espérance, j’ai montré avec Emilie Kaufmann qu’identifier un point x e-optimal avec probabilité 1-d nécessite au moins T(f)*log(1/d) observations, où T(f) désigne la complexité d’optimisation de la fonction. Nous avons proposé un algorithme (appelé Track-and-Stop) qui permet d’atteindre cette borne.
Le but de ce projet est de développer cette théorie pour qu’elle puisse prendre en compte des cas réels d’application. D’abord, il est important dans de nombreuses applications sensibles aux risques (comme l’agronomie) de considérer d’autres fonctions d’utilité. Deuxièmement, de nombreux applications comme les essais cliniques font apparaître une structure naturelle sur l’ensemble X et des restrictions sur l’ensemble des fonctions f possibles. Par exemple, il peut être connu à l’avance que F[f(x, .)] est une fonction monotone, unimodale, ou à variations lentes. Troisièmement, dans des cas comme les systèmes de recommandation, l’ensemble X peut être très grand mais posséder une structure de graphe pouvant être exploitée pour accélérer énormément l’optimisation. Enfin, l’espace X peut être continu (comme c’est le cas de certains paramètres en autoML); nous traiterons ce cas en combinant les analyses des deux cas précédents avec les idées classiques de statistique non-paramétrique.
Cette chaire se destine également à développer l’enseignement en intelligence artificielle à l’ENS de Lyon, établissement très sélectif accueillant un nombre limité d’étudiants se destinant à travailler dans la recherche. C’est un aspect important de la mission pour laquelle j’ai été recruté l’an dernier à l’intersection des départements de mathématiques et d’informatique. En m’appuyant sur les excellents formations d’informatique théorique et de mathématiques générales, je veux former un groupe de spécialistes en apprentissage statistique chaque année, avec des bases solides en statistique mathématique et en théorie de l’apprentissage en général, et une spécialisation en optimisation bruitée et pour le traitement des code numériques.
Ce projet développe un champ d’expertise de la recherche française. Cette approche de l’optimisation a connu de nombreux succès au cours des dix dernières années, et constitue l’une des briques essentielles de récents succès marquants de l’intelligence artificielle : moteurs de recherche personnalisés, systèmes de recommandation et de publicité, apprentissage par renforcement et MCTS, systèmes d’enchères en ligne, l’autoML, etc. Ce projet contribue à tous ces aspects, fournissant à la fois une théorie générale de la complexité pour l’optimisation bruitée et et des algorithmes et méta-algorithmes permettant de traiter des cas particuliers.
Il s’inscrit dans la recherche académique en apprentissage automatique de l’Université de Lyon et Saint-Etienne, qui s’est unie dans la fédération de recherche SciDoLySE incluant outre l’UMPA et du LIP l’ICJ, des équipes INRIA et le LHC, donnant à mes travaux et cours une audience à l’échelle du site tout entier.
Coordination du projet
Aurélien GARIVIER (Unité de mathématiques pures et appliquées de l'ENS de Lyon)
L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.
Partenaire
UMPA Unité de mathématiques pures et appliquées de l'ENS de Lyon
Aide de l'ANR 539 568 euros
Début et durée du projet scientifique :
août 2020
- 48 Mois
