Organisateurs: Aurélien Garivier, Sébastien Gerchinovitz
17 octobre 2014 : Réunion de rentrée, par Aurélien Garivier et Sébastien Gerchniovitz
Cette première séance permettra de présenter la nouvelle forme que prend le groupe de travail, et de définir les objectifs prioritaires.
Localisation : salle MIP (1R3 1er étage), à 9h30.
24 avril 2014 : Multiresolution Analysis of Incomplete Rankings, par Eric Sibony
Incomplete rankings on a set of items {1, ..., n} are orderings of the form a1 < ... < ak, with {a1, ..., ak} \subset {1, ..., n} and k < n. Though they arise in many modern applications, only a few methods have been introduced to manipulate them, most of them consisting in representing any incomplete ranking by the set of all its possible linear extensions on {1, ..., n}. In this talk, I will introduce a completely novel approach, which allows to treat incomplete rankings directly, representing them as injective words over {1, ..., n}. Unexpectedly, operations on incomplete rankings have very simple equivalents in this setting and the topological structure of the complex of injective words can be interpretated in a simple fashion from the perspective of ranking. We exploit this connection here and use recent results from algebraic topology to construct a multiresolution analysis and develop a wavelet framework for incomplete rankings. Though purely combinatorial, this construction relies on the same ideas underlying multiresolution analysis on a Euclidean space, and permits to localize the information related to rankings on each subset of items. It can be viewed as a crucial step toward nonlinear approximation of distributions of incomplete rankings and paves the way for many statistical applications, including preference data analysis and the design of recommender systems.
Localisation : salle 132 - J. Cavailles (bâtiment 1R2), à 11h.
5 février 2014 : Jeux répétés markoviens avec défaut d’information asymétrique, par Xavier Bressaud
Nous proposons une extension de résultats de Johannes Hörner, Dinah Rosenberg, Eilon Solan et Nicolas Vieille concernant la valeur et les stratégies optimales pour un jeu répété Markovien avec défaut d’information d’un coté introduit par Jérôme Renault. Elle est permise par l’étude du système dynamique (assez simple) représentant l’évolution de la croyance du joueur le moins bien informé sur l’état du jeu. (Travail avec Anthony Quas)
Localisation :salle 106 (bâtiment 1R1), à 10h.
25 juin 2013 : Taux minimax dans des problèmes de régression et apprentissage séquentiel (2/2), par Sébastien Gadat
Suite de l'exposé précédent.
à 15h30, en salle 106 (bâtiment 1R1).
19 juin 2013 : Taux minimax dans des problèmes de régression et apprentissage séquentiel (1/2), par Sébastien Gadat
On s'intéresse au problème de la régression non paramétrique sur [0,1]^d
et l'aptitude des méthodes d'active learning à trouver des vitesses de
reconstruction minimax dans ce contexte.
Nous étudions essentiellement deux méthodes d'apprentissage actif: la
méthode batch produit un design en amont des observations tandis que la
stratégie d'apprentissage actif produit des designs séquentiellement au
fur et à mesure que les observations arrivent.
Nous démontrons alors que les stratégies "batch" ne peuvent pas
améliorer les taux minimax de reconstruction dans les espaces de
fonctions alpha lisses et alpha lisses par morceaux. Au contraire, des
améliorations sont apportées par des méthodes d'apprentissage actif dans
les espaces alpha lisses par morceaux lorsque le signal à reconstruire
contient un certain nombre de discontinuités. Cette efficacité est
quantifiée en fonction de la dimension d et de la régularité alpha.
Références :
- Alexander Korostelev, On minimax rates of convergence in image models under sequential design, Statistics & Probability Letters 43 (1999) 369 – 375.
- Rui Castro, Rebecca Willett and Robert Nowak, Faster Rates in Regression Via Active Learning, version longue de NIPS 2005.
Attention: exceptionnellement, exposé à 14h.
Localisation : Bâtiment 1R2, salle 129 (Picard).
23 mai 2013 : Un algorithme de bandit pénalisé, par Sofiane Saadane
Au cours de cet exposé, nous présenterons l'article de Lamberton et Pagès « a penalized bandit algorithm ». Le problème du bandit à deux bras est très connu des personnes fréquentant les casinos. En effet, un bandit est une machine comportant un bras que l’on actionne en espérant un gain. Le problème que l’on étudie est différent au sens où on a le choix entre deux bras A,B et à chaque étape on choisit d’actionner un des deux bras selon une certaine dynamique. Dans le cas que nous étudions deux traders A et B se partagent la gestion d'un fond géré par une personne Y. Tout les jours Y évalue le trader ayant la plus importante part à gérer et décide en fonction de l'évaluation d'augmenter ou de diminuer la part que gère ce trader. Après une présentation de l'algorithme, nous verrons que sous de faibles hypothèses il est infaillible (au sens où l'on finit toujours par choisir le meilleur bras). Ensuite il sera montré qu'en renormalisant l’algorithme convenablement celui-ci converge vers un processus de Markov particulier appelé PDMP (Piecewise Deterministic Markov Process). Une esquisse de preuve sera proposée pour établir cette convergence, on donnera la méthode plutôt qu'une preuve calculatoire. Enfin selon le temps et l'avancement de mon travail une étude du regret associé sera proposé. Cet exposé est différent des précédents, il a la particularité d'adopter un point de vue purement probabiliste qui contrastera avec l'aspect statistique des précédents.
Notes de l'exposé.
4 avril 2013 : Bandits stochastiques : stratégies Upper Confidence Bounds, par Aurélien Garivier
On présentera dans cette séances les stratégies Upper Confidence Bounds (UCB) : on commencera par la version classique de [Auer et al. ’02], avec la preuve de regret, et on montrera comment il faut modifier cet algorithme pour atteindre la borne inférieure de Lai et Robbins. A cette occasion, on introduira les outils statistiques nécessaires à la définition d’algorithmes de bandits avancés : auto-normalisation, et vraisemblance empirique.
Notes manuscrites de l'exposé.
21 mars 2013 : Problèmes de bandits stochastiques : borne inférieure de Lai et Robbins, par Aurélien Garivier
Dans cet exposé, on se focalisera sur les problèmes d’allocations séquentielles dans un environnement stochastique (et non plus hostile, comme c’était le cas dans les deux exposés précédents). Pour ne pas bloquer les collègues de l’INSA (pris par une journée de recherche) pour la suite des séances, on se focalisera sur la borne inférieure de Lai et Robbins, qui stipule que l’espérance du regret subi par n’importe quelle politique "raisonnable" grandit au moins comme le logarithme de l’horizon, multiplié par une constante dépendant des paramètres que l’on s’efforcera d’interpréter. On verra au cours des séances suivantes quelles stratégies permettent d’atteindre ce regret optimal.
Notes manuscrites de l'exposé.
14 février 2013 : Introduction aux bandits antagonistes (2/2), par Sébastien Gerchinovitz
Au cours de cette séance, nous poursuivrons notre introduction aux
bandits antagonistes. Plus précisément, on expliquera comment appliquer les résultats vus en information parfaite au cadre des bandits. Cela permettra de contrôler une forme faible du regret en espérance (le "pseudo-regret").
Nous donnerons ensuite quelques pistes pour majorer le regret avec
grande probabilité. Enfin, selon le temps disponible, nous pourrons
aborder la question de l'optimalité des bornes obtenues ou expliquer
comment calibrer séquentiellement le paramètre de température.
Notes manuscrites de l'exposé.
7 février 2013 : Introduction aux bandits antagonistes (1/2), par Sébastien Gerchinovitz
Au cours de cet exposé, on s'intéressera au problème de bandits à K bras
lorsque les gains sont choisis de façon déterministe ou même
antagoniste. Cela conduit à des méthodes de décision séquentielle
robustes. On présentera d'abord une méthode adaptée au cas où les gains
de toutes les actions possibles seraient observés à la fin de chaque
tour ("information parfaite"). On expliquera ensuite comment adapter cet algorithme au cadre des
bandits, i.e., lorsque seul le gain associé à l'action choisie est
observé. L'algorithme qu'on présentera procède par pondération
exponentielle.
Référence : on présentera une partie du chapitre 3 de l'
article de survol de Bubeck et Cesa-Bianchi.
Notes manuscrites de l'exposé.
17 janvier 2013 : Présentation du GdT, par Aurélien Garivier et Sébastien Gerchinovitz
Présentation des différents sujets qui seront abordés au cours du GdT, puis planification des séances.