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.
Nous verrons dans cette introduction en quoi consiste l'approche "machine learning" pour la résolution de problèmes, quels sont les grands types de problème résolubles par apprentissage, quel type de données les algorithmes d'apprentissage savent traiter, et comment parfois s'y ramener, quels sont les grandes familles d'algorithmes d'apprentissage et quels outils permettent de les mettre en oeuvre. Nous détaillerons ensuite deux cas pratiques de problèmes industriels pour lesquels des solutions s'appuyant sur l'apprentissage automatique ont été proposées. Le premier exemple concerne les systèmes d'enchères sur internet, et le second a trait à la catégorisation automatique de questions pour la création d'une FAQ.
After Florent Krzakala's second lecture in les Houches, we present some insights on the possibility to learn in very high dimension, and on the double descent phenomenon, in some simple (and less simple) teacher-student settings.
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.
We present Neural Networks for classification and Regression, and three necessary but challenging mathematical problems they suggest: approximation, optimization, and generalization.
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.
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.
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.
We present sequential and active statistics problems, and how Information Theory can help providing lower bounds, but also optimal algorithms.
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.
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.
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
Introduction à l'apprentissage statistique : cadre formel, premiers algortihmes, minimisation du risque empirique et structurel, SVM et réseaux de neurones
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
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
Présentation de mon domaine de recherche en 15 minutes
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
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
Compte-rendu de lecture du rapport Villani par Philippe Besse, Aurélien Garivier, Sébastien Gerchinovitz et Mathieu Serrurier, suivi d'un débat
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
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
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
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
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
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
Bilan du projet UPS-INSA : Statistique et Informatique pour les Big Data
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Bandit models, and especially the UCB algorithms, are presented together with statistical challenges they involve: non-asymptotic estimation, self-normalized deviations, Empirical Likelihood.
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
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
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
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
This paper presents a finite-time analysis of the KL-UCB algorithm, an online, horizon-free index policy for stochastic bandit problems. We prove two distinct results: first, for arbitrary... more