Selected Presentations

Colloquium du laboratoire de mathématiques

Feb. 2020 -

Sur la complexité des problèmes d'optimisation séquentielle

Université Clermont-Ferrand

Que ce soit pour des essais cliniques, pour les moteurs de recommandation ou pour l'optimisation des paramètres d'algorithmes d'apprentissage automatique, de nombreux problèmes nécessitent la maximisation d'une fonction dite "boite noire", dont on peut observer des évaluations bruitées en un nombre limité de points de notre choix. La complexité de ce problème d'optimisation est mesuré par le nombre d'observations nécessaires avant de pouvoir donner, avec un risque faible, une bonne approximation du maximum. En commençant par des exemples très simples, puis élargissant progressivement le champ, nous présenterons comment des outils de théorie de l'information et d'apprentissage séquentiel permettent de déterminer cette complexité, ainsi que des algorithmes ne pouvant être beaucoup améliorés.

clermont20200220.pdf

Keywords:

Sequential Decision Making, Optimization, Bandits

Jan. 2020 -

Mathematical Challenges in Machine Learning

Lyon,

Journée Thématique Machine Learning, IdEX Milyon

We present Neural Networks for classification and Regression, and three necessary but challenging mathematical problems they suggest: approximation, optimization, and generalization.

journeeML_mathsML_Garivier.pdf

Keywords:

Sequential Decision Making, Optimization, Bandits

Jan. 2020 -

The problem-dependent complexity of sequential optimization

Paris, Google France

Deepmind Seminar

We will present the current status of our research on exact bounds for the sequential sample complexity of optimizing functions perturbed by centered noise. The simplest setting (PAC best-arm identification in finite bandit models) is now well understood, and precise information bounds are known. Our current effort to extend these results to more structured models (involving a graph or a continuous space) will be presented.

deepmind20200120.pdf

Keywords:

Nov. 2019 -

Éthique et Intelligence Artificielle

Lyon,

Les cafés de la statistique

Associant données massives (big data) et algorithmes d’apprentissage automatique (machine learning), la puissance des outils de décision automatique suscite autant d’espoir que de craintes. De nombreux textes législatifs européens (RGPD) et français récemment promulgués tentent d’encadrer les usages de ces outils. Cependant, les risques de discrimination, les problèmes de transparence et ceux de qualité des décisions algorithmiques sont toujours très présents : la législation va toujours moins vite que la pratique… Les incompatibilités entre exploitation des données et respect de la vie privée sont explorées depuis longtemps. La banalisation des algorithmes d’intelligence artificielle vient exacerber cette tension. Pour détecter et réduire le risque de discrimination ainsi que pour répondre au droit à l’explication légitime des citoyens, les algorithmes exploitant des données personnelles se doivent d’être déployés dans un cadre juridique et éthique strict. Au-delà du constat, nous nous attacherons, lors de ce café et pour répondre à cette nécessité, à lister également quelques possibilités de contrôle à développer.

201911_cafeStat.pdf

Keywords:

Machine learning, fairness

Nov. 2019 -

Regret Minimization on Non-Parametric Bandits via the Empirical Likelihood Method

Madrid, Real Academia de Ciencias

Conference of the Euro-Maghreb International Research Network in Mathematics and Applications

An agent must choose at each time stp among K options, each producing an independent draw of an unknown probability distribution. Her goal is to maximize the sum of the values obtained. How should she make her choices? For the case where the random variables are only assumed to be bounded, we propose an asymptotically optimal algorithm based on the construction of upper confidence bounds obtained by the Empirical Likelihood Method.

Madrid201911_GE2MI.pdf

Keywords:

Machine learning, Bandit Models, Empirical Likelihood

Nov. 2019 -

On Information Inequalities and the Complexity of Sequential Decision Problems

Orsay

Seminar of the Machine Learning Master

We present sequential and active statistics problems, and how Information Theory can help providing lower bounds, but also optimal algorithms.

semM2orsay20191105.pdf

Keywords:

Introduction, by Aurélien Garivier

Oct. 2019 -

Introduction to the mathematics of Deep Learning

ENS Lyon

Lyon Probability Seminar Reading Group

Presentation of Neural Networks for classification and Regression, and some challenges for a mathematical analysis: approximation, optimization, and generalization. This talk introduces the three next lectures: [Daniely '17. Depth Separation for Neural Networks], [Mei, Montanari, Nguyen '18-'19. A Mean Field View of the Landscape of Two-Layers Neural Networks] and [Bartlett, Long, Lugosi, Tsigler '19 Benign Overfitting in Linear Regression]. It was followed by a presentation by Rémi Gribonval on some approximation results.

On approximation: a lecture of [Daniely '17. Depth Separation for Neural Networks], by Mikaël de la Salle and Tomáš Kocák

On optimisation: a lecture of [Mei, Montanari, Nguyen '18-'19. A Mean Field View of the Landscape of Two-Layers Neural Networks], by Aurélien Garivier

Keywords:

Colloque francophone international sur l'enseignement de la statistique

Sep. 2019 -

Automatic Decision by Machine Learning and Fairness

Strasbourg

L'objectif de cet exposé est de sensibiliser à la question de la loyauté des algorithmes de décision automatique basé sur l'apprentissage statistique. Après avoir rappelé la démarche de cette dernière, nous développerons un exemple illustrant quelques problèmes qu'ils peuvent poser, et la manière dont des statisticiens peuvent l'aborder.

201909Strasbourg_CFIES.pdf

Keywords:

cvGrad_Montanari_small.pdf

Jun. 2019 -

On the convergence of Gradient Descent for depth 2 Neural Networks

ENS Lyon, Reading group: Maths of Deep Learning

Groupe Scidolyse

We present recent results by Montanari and al. on a statistical physics interpretation of gradient descent for depth-2 neural networks, which yields convergence results

Keywords:

Journées Calcul et Apprentissage du GDR Calcul

Apr. 2019 -

Introduction à l'apprentissage statistique

Lyon, Université Claude Bernard

Introduction à l'apprentissage statistique : cadre formel, premiers algortihmes, minimisation du risque empirique et structurel, SVM et réseaux de neurones

introML_small.pdf

Keywords:

Machine learning, Recommender systems, Bandit Problems

Nov. 2018 -

Complexity of Sequential Decision Problems

ENS Lyon, Théminaire

Théminaire de l'ENS Lyon

From clinical trials to content recommender systems, dynamic allocation systems are present everywhere, and various strategies have been developed in order to optimize them. We present on a simple... more

theminaire20181112.pdf

Keywords:

Oct. 2018 -

Introduction à certains problèmes de décisions séquentielles

Rencontre des Statisticiens Lyonnais (RSL), Campus de La Doua

Que ce soit pour les systèmes de recommandation, pour l'allocation dynamique de ressources ou pour l'exploration des arbres dans les jeux, de nombreux systèmes de décision automatiques s'appuient... more

RSL20181012_small.pdf

Keywords:

UCB, Bandit Problems

Oct. 2018 -

Comment les maths peuvent-elles aider les machines à apprendre ?

ENS Lyon, Journée de rentrée de l'UMPA

Présentation de mon domaine de recherche en 15 minutes

UMPA181001_small.pdf

Keywords:

Laboratoire de l'Informatique du Parallélisme

May. 2018 -

Missing Mass, and Optimal Discovery

ENS Lyon

We consider an original problem that arises from the issue of security analysis of a power system and that we name optimal discovery with probabilistic expert advice. We address it with an... more

LIP20180514_goodTuring_small.pdf

Keywords:

Machine learning, UCB, Good-Turing, Bandit Problems

Apr. 2018 -

Minimisation du regret pour des bandits non-paramétriques grâce à la méthode de la vraisemblance empirique

ENS Lyon

Séminaire de l'UMPA

Un agent doit choisir à chaque instant parmi K options produisant chacune une variable aléatoire de distribution inconnue. Son but est de maximiser la somme des variables obtenues. Comment doit-il... more

Lyon20180426.pdf

Keywords:

Empirical Likelihood, Non-Parametrics, Bandit Problems

Apr. 2018 -

Rapport Villani sur l'IA: rapide tour d'horizon

Toulouse, groupe de travail learning

Equipe-projet AOC

Compte-rendu de lecture du rapport Villani par Philippe Besse, Aurélien Garivier, Sébastien Gerchinovitz et Mathieu Serrurier, suivi d'un débat

AOC_Rapport_Villani_2018.pdf

Keywords:

Big Data, Machine learning

Mar. 2018 -

Quelques idées pour les problèmes de décisions séquentielles

ENS Lyon

Laboratoire de l'Informatique du Parallélisme

Que ce soit pour les systèmes de recommandation,

pour l'allocation dynamique de ressources ou pour l'exploration des arbres dans les jeux, de nombreux systèmes de décision automatiques s'appuient... more

LIP20180314_small.pdf

Mar. 2018 -

Vers une intelligence artificielle responsable

Université Paris 5 Descartes

Journée Intelligence Artificielle de la SFDS

La plupart des succès qui valent à l'intelligence artificielle son retentissement médiatique actuel présentent une double caractéristique : certes ils voient des systèmes automatiques réaliser de... more

SFDS20180326_small.pdf

Keywords:

Big Data, Machine learning

Sep. 2017 -

On the Complexity of Best Arm Identification with Fixed Confidence

Séminaire UT1-UT3, Toulouse

We consider the problem of finding the highest mean among a set of probability distributions that can be sampled sequentially. We provide a complete characterization of the complexity of this task... more

20170920_Garivier_UT1.pdf

Jul. 2017 -

The Complexity of Best-Arm Identification

Barcelona, FoCM2017

Workshop on Stochastic Computation

FOCM17_garivier.pdf

Keywords:

Présentation Thématique Big Data au Conseil de Prospective de l'IMT

Apr. 2017 -

Institut de Mathématiques de Toulouse

Avec Fabrice Deluzet et Francesco Costantino, nous présentons pour l'ensemble du laboratoire un aperçu de la thématique Big Data. Nous discutons en particulier de quelques thèmes de recherche... more

20170418_bigdata.pdf

Keywords:

Big Data

Jan. 2017 -

Big Data, Machine Learning : qu'est-ce que la science des données ?

Bordeaux, Journées IREM

Journées de conférences ou ateliers à destination des enseignants et étudiants.

slides de la présentation
vidéo de la présentation (voir... more

Keywords:

Big Data, Machine learning

Aug. 2016 -

Sur la complexité de l'identification du meilleur bras sous contrainte de risque dans un modèle de bandits

Grenoble, Journées MAS 2016

Journées MAS 2016

Nous considérons un modèle d'optimisation discrète où, à chaque instant, le choix d'une option donne accès à une observation bruitée de la valeur associée. Nous donnons une estimation précise du... more

MAS20160830_compressed_images.pdf

Keywords:

Projet Enseignement : Statistique et Informatique pour les Big Data

Jul. 2016 -

INP ENSIACET Labège

Toulouse Tech

Bilan du projet UPS-INSA : Statistique et Informatique pour les Big Data

pres20160607IDEX.pdf

Keywords:

Teaching

Jun. 2016 -

Optimal Best Arm Identification with Fixed Confidence

New York

COLT 2016, videolectures

We provide a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the... more

COLT20160624_long.pdf

Keywords:

Jun. 2016 -

On the Complexity of Best Arm Identification with Fixed Confidence

Séminaire Pluridisciplinaire d'Optimisation de Toulouse

SPOT

I will present a complete characterization of the complexity of best-arm identification in one-parameter bandit problems.
In other words, we give a new, tight lower bound for the expected... more

SPOT20160606.pdf

Keywords:

Bandit Problems

May. 2016 -

Recent advances in the understanding of bandit models

Grenoble, rencontres

ANR ALICIA

I present here our recent contributions on the following problems (joint work with Emilie Kaufmann, Tor Lattimore, Pierre Ménard, Gilles Stoltz): what is the complexity of best-arm identification... more

ALICIA20160527.pdf

Keywords:

Bandit Problems

May. 2016 -

De l'intérêt des méthodes séquentielles (une introduction)

Toulouse, rencontres

ANR SPADRO

We study the problem of minimising regret in two-armed bandit problems with Gaussian noise. Our
objective is to use this simple setting to illustrate that strategies based on an exploration... more

Keywords:

Bandit Problems

Mar. 2016 -

Sequential Optimization and Computer Experiments

Toulouse

MASCOT-NUM 2016 Meeting

Every day, one pick a point $x$ and observe the (possibly noisy) value of an unknown function $f$ at point $x$. How to find as fast as possible the minimum value of $f$? In this introductory... more

mascotnum_20160323.pdf

Keywords:

Multi-armed Bandit Workshop 2016 at STOR-i

Jan. 2016 -

Optimal Discovery with Probabilistic Expert Advice

Lancaster University, UK

We consider a variant of a bandit model that arises from some issue of security analysis of a power system. We address it with an optimistic, UCB-type policy using the Good-Turing missing mass... more

garivier_Lancaster_201601.pdf

GoodUnifExpN500_coded.avi

Keywords:

UCB, Good-Turing, Bandit Problems

Jun. 2015 -

Systèmes de recommandation et algorithmes de bandits: notebook ipython pour l'enseignement

Lille, JDS

47èmes Journées de Statistique de la SFdS

Les systèmes de recommandation automatiques à très grande échelle sont aujourd'hui omniprésents sur internet : ouvrages conseillés à l'achat dans les librairies en ligne, articles... more

demoBandits.ipynb

Introduction aux bandits pour la recommandation

Keywords:

Big Data, Teaching, UCB, Bandit Problems

May. 2015 -

Optimism in Reinforcement Learning and Kullback-Leibler Divergence

Toulouse, CIMI

IMPRECISE PROBABILITIES WORKSHOP

We consider model-based reinforcement learning in finite Markov Decision Processes (MDPs), focussing on so-called optimistic strategies. In MDPs, optimism can be implemented by carrying out... more

ImpreciseProba.pdf

Keywords:

Self-Normalized, Reinforcement Learning, Empirical Likelihood

Mar. 2015 -

On the Complexity of Best Arm Identiﬁcation in Multi-Armed Bandit Models

Berkeley

Information Theory, Learning and Big Data Workshop, Simons Institute, youtube presentation

The stochastic multi-armed bandit model is a simple abstraction that has proven useful in many different contexts in statistics and machine learning. Whereas the achievable limit in terms of... more

Berkeley_150317.pdf

Keywords:

Big Data, Machine learning, UCB, Empirical Likelihood, Bandit Problems

Oct. 2014 -

Bandits for Exploration: Best Arm Identification and Discovery with Probabilistic Experts

Imperial College, Multi-armed bandits meeting

http://wwwf.imperial.ac.uk/~amijatov/IP/lps.php

Whereas the achievable limits in terms of regret minimization in simple bandit models are now well known, it is often meaningful to consider slightly different goals and/or slightly different... more

Imperial_141031.pdf

Keywords:

UCB, Self-Normalized, Good-Turing, Bandit Problems

Oct. 2014 -

Allocation dynamique de ressources et modèles de bandits

Toulouse School of Economics, UT1

séminaire MAD

Un agent doit choisir, à chaque instant, une action parmi une famille d'actions
disponibles. Chaque action conduit à une récompense aléatoire de distribution
inconnue. Comment... more

MAD_141003.pdf

Keywords:

UCB, Reinforcement Learning, Good-Turing, Bandit Problems

Sep. 2014 -

Allocation dynamique de ressources et modèles de bandits

INRA Toulouse

Séminaire MIAT

Un agent doit choisir, à chaque instant, une action parmi une famille d'actions
disponibles. Chaque action conduit à une récompense aléatoire de distribution
inconnue. Comment... more

INRA_140919.pdf

Keywords:

UCB, Reinforcement Learning, Good-Turing, Bandit Problems

Sep. 2014 -

Cours de Machine Learning

Aussois,

Ecole d'été pluridisciplinaire de Théorie des Jeux

Ce cours vise à présenter l'apprentissage statistique aux doctorants et post-doctorants en théorie des jeux : après une introduction générale, un accent particulier est mis sur les liens... more

Keywords:

Machine learning, UCB

Jul. 2014 -

Perfect Simulation of Processes With Long Memory: A ``Coupling Into and From The Past'' Algorithm

Buenos Aires, Conference on Stochastic Processes and their Applications

SPA'14

We describe a new algorithm for the perfect simulation of variable length Markov chains and random systems with perfect connections. This algorithm generalizes Propp and Wilson's simulation... more

SPA_140730.pdf

Keywords:

VLMC, Perfect Simulation

Jun. 2014 -

Empirical Likelihood Upper Confidence Bounds For Bandit Models

Barcelona, Journées Statistiques du Sud 2014

7èmes Journées Statistiques du Sud

The classical Upper-Confidence Bound policies are known to have some nice optimality
properties in simple bandit models. In more general contexts, however, they appear
to be quite... more

slidesJSS14.pdf

Keywords:

UCB, Self-Normalized, Empirical Likelihood, Bandit Problems

Apr. 2014 -

Empirical Likelihood for Optimistic Algorithms in Dynamic Resource Allocation

Paris X Nanterre

ANR SPADRO kick-off meeting

Bandit models, and especially the UCB algorithms, are presented together with statistical challenges they involve: non-asymptotic estimation, self-normalized deviations, Empirical Likelihood.

kickoffSPADRO.pdf

Keywords:

VLMC, UCB, Self-Normalized, Empirical Likelihood, Non-Parametrics, Bandit Problems

Apr. 2014 -

Optimistic Solutions for Dynamic Resource Allocation

Paris (AgroParisTech)

StatLearn 2014

In applications such as recommender systems, classical dynamic allocation rules are not a completely satisfying because they tend to propose always the same "blockbusters" and do not... more

slidesSTATLEARN.pdf

Keywords:

UCB, Good-Turing, Empirical Likelihood, Bandit Problems

Dec. 2013 -

Optimal Discovery with Probabilistic Expert Advice: Finite Time Analysis and Macroscopic Optimality

CIRM, Rencontres de Statistique Mathématique "Mathematical Statistics with Applications in Mind"

site web, Programme de la rencontre

We consider an original problem that arises from the issue of security analysis of a power system and that we name optimal discovery with probabilistic expert advice. We address it with an... more

slidesCIRM.pdf

Keywords:

UCB, Good-Turing, Bandit Problems

Sep. 2013 -

Informational Confidence Bounds for Self-Normalized Averages and Applications

Seville (Spain)

2013 IEEE Information Theory Workshop

We present deviation bounds for self-normalized averages and applications to estimation with a random number of observations.
The results rely on a peeling argument in exponential martingale... more

slidesSeville.pdf

Keywords:

VLMC, UCB, Self-Normalized, Bandit Problems

May. 2013 -

Quelques idées sur les problèmes de bandits

Mini-colloque LPT-IMT 2013, Séminaire de l'équipe GEPETTO (LAAS Toulouse)

Un agent doit choisir, à chaque instant, une action parmi une famille d'actions disponibles. Chaque action conduit à une récompense aléatoire de distribution inconnue. Comment doit-il s'... more

LPT-IMT.pdf

Keywords:

Fête Parisienne in Computation, Inference and Optimization in IHES (Bures sur Yvette)

Mar. 2013 -

Dynamic resource allocation as an estimation problem

IHES1303.pdf

Keywords:

Bandit Problems, Empirical Likelihood, Non-Parametrics, Self-Normalized, UCB

Feb. 2013 -

Problèmes de décisions séquentielles

plusieurs exposés dans le cadre du

groupe de travail co-organisé avec Sébastien Gerchinovitz à l'IMT

Keywords:

Based on this article by Yuval Peres (AoS 92)

Nov. 2012 -

Iterating von neumann procedure for extracting random bits : une introduction biaisée à la théorie de l'information

Groupe de travail de Probabilités de l'IMT

Keywords:

Universal Coding

Nov. 2012 -

Extraction d'information en grandes dimensions & allocation dynamique de ressources

avec Jean-Michel Loubès

Séminaire FREMIT

Keywords:

Groupe de travail "modélisation" de Paris 7

Jul. 2012 -

Problèmes de bandits et estimation

Séminaire de recherche du département TSI de Telecom ParisTech

paris1207bandits.pdf

Keywords:

Bandit Problems, Bayesian Methods, Non-Parametrics, UCB

May. 2012 -

Couplage par le passé des chaînes de Markov d'ordre variable : extension de l'algorithme de Propp et Wilson

paris1205pwct.pdf

Keywords:

Perfect Simulation, VLMC

Jan. 2012 -

Apprentissage par renforcement et déviations auto-normalisées

Séminaire de statistiques de Toulouse , Séminaire parisien

toulouse120124.pdf

Keywords:

Bandit Problems, Non-Parametrics, Reinforcement Learning, Self-Normalized, UCB

Dec. 2011 -

Exploration optimale à l'aide d'experts probabilistes

Séminaire du CMAP (Ecole Polytechnique, Palaiseau)

cmap1111gooducb.pdf

Keywords: