Selected Presentations

We will present the current status of our research on exact bounds for the sequential sample complexity of optimizing discrete 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.

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.

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 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.

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.

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.

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