M2 Mathematics of Randomness

probability theory and notions of convex analysis

• Regret minimizing algorithms
• Online linear/convex optimization
• Adaptive regret bounds
• Blackwell's approachability
• Adversarial bandits & partial monitoring
• Application to optimization, variational inequalities, fixed-point iterations
• Application to learning in games

Online learning is an important topic at the intersection of machine learning, optimization and sequential decision. This course focuses on a general class of sequential decision problems in adversarial environments. We first introduce the mathematical tools to design and analyze a wide range of regret minimizing algorithms in online linear/convex optimization. These results are then extended to a wider range of problems through Blackwell's approachability. We then explore deep connections with various optimization problems: (stochastic) optimization, minimax problems, variational inequalities, learning in games, fixed-point iterations.

• "Prediction, learning, and games", Nicolò Cesa-Bianchi and Gábor Lugosi. Cambridge University Press, 2006
• "Approachability, regret and calibration: Implications and equivalences" ,Vianney Perchet, Journal of Dynamics & Games (2014)
• "A modern introduction to online learning", Francesco Orabona, lecture notes, 2023

Dans une première partie nous utiliserons le calcul stochastique pour donner une construction simple des temps locaux des semimartingales continues. Nous étudierons ensuite les temps locaux du mouvement brownien, et notamment les liens entre le processus des temps locaux browniens et certains processus de branchement. Dans un second temps, nous développerons la théorie des excursions, qui est un outil puissant d'étude du mouvement brownien.

To begin with, we will use stochastic calculus to give a simple approach to local times of continuous semimartingales. We will then study local times of Brownian motion, and in particular the connections between Brownian local times and certain branching processes. Finally, we will present excursion theory, which is a powerful tool for studying linear Brownian motion.

Les notions nécessaires de topologie et de géométrie seront introduite ou rappelée au fil du cours.

Plan du cours :

1. Introduction et rappels
2. Fonctions distance et reconstruction d'ensembles compacts.
3. Application à l'estimation de l'homologie de de sous-variétés à partir d'échantillon i.i.d. Aspects algorithmiques et statistiques.
4. Homologie persistente : définition, stabilité et applications (clustering, signatures topologiques,...).
5. Propriétés statistiques de l'homologie persistente.
6. Inférence géométrique pour les mesures de probabilité.

L'estimation des propriétés de nature topologique et géométrique de données souvent représentées par des ensembles de points dans des espaces euclidiens de grande dimension (ou plus généralement des variétés riemanniennes ou des espaces métriques) connait un développement important depuis quelques années. L'analyse topologique des données est motivée par l'observation que généralement les données, qui ne sont pas distribuées uniformément dans l'espace ambiant mais se concentrent autour de structures géométriques de plus petite dimension qu'il est important de comprendre.

L'objectif de ce cours est de donner une introduction à ce sujet en pleine expansion.

This course deals with the stochastic modeling of population dynamics. In the first part, we focus on monotype populations described by one-dimensional stochastic differential equations with jumps. We consider their scaling limits for large populations and study the long time behavior of the limiting processes. This is achieved, thanks to martingale properties, Poisson measure representations, and stochastic calculus. These tools and results will be used and extended to measure-valued processes in the second part. The latter is dedicated to structured populations, where individuals are characterized by a trait belonging to a continuum.

Il s'agit de présenter divers modèles solubles en probabilités. Cela inclut les marches aléatoires en milieu aléatoire sur Z dont la vitesse asymptotique peut se calculer explicitement, l'asymptotique explicite de la longueur de la plus longue sous-suite croissante d'une permutation aléatoire, la formule de Hardy-Ramanujan sur l'asymptotique du nombre de partitions d'un entier, des calculs de formes limites de divers objets, la distribution limite de la mesure spectrale de matrices de Wigner...

L'objectif est de donner un panorama vivant (mais de loin non exhaustif !) de la recherche actuelle en probabilités sans aller dans les avancées les plus récentes de chaque modèle. Chaque calcul peut être présenté en 3 ou 4 heures, et est le fruit d'un " miracle " de calcul, ou de la découverte d'une mesure invariante explicite dans un grand système markovien, de la correspondance avec un système de particules, de l'introduction d'un modèle statistique... qui aiguisent la curiosité et peuvent donner envie aux élèves d'approfondir l'un de ces sujets dans le cadre d'une thèse.

Ce cours traite de problèmes d'inférence génériques aux applications nombreuses (en biologie, traitement de la parole, moteurs de recommandation, étude de réseaux sociaux,…) posés dans le contexte de graphes. Il traitera notamment : la détection de communautés (identification de groupes de sommets semblables d'un graphe), l'alignement de graphes (mise en correspondance des sommets de plusieurs graphes), et la reconstruction d'arbres (identification de caractéristiques de " l'ancêtre " d'un arbre généalogique d'après les traits de ses descendants). Des modèles probabilistes de graphes seront introduits, ainsi que l'analyse d'algorithmes efficaces pour des données échantillonnées selon ces modèles. On s'intéressera notamment à des algorithmes spectraux, dont la compréhension repose sur l'étude de spectres de matrices aléatoires associées aux graphes considérés. On abordera aussi des algorithmes basés sur la programmation semi-définie.

Les éléments d'analyse fonctionnelle nécessaires (produits tensoriels d'espace de Hilbert, opérateurs Hilbert-Schmidt et opérateurs à trace, etc) seront introduits au fur et à mesure du cours.

A la différence du calcul stochastique d'Itô qui utilise la structure temporelle des processus à travers la notion de martingale, le calcul de Malliavin exploite les propriétés des processus gaussiens, à l'instar du mouvement brownien, pour définir le cadre d'une analyse en dimension infinie. L'objet principal en est le gradient de Stroock-Malliavin et la divergence associée qui généralise l'intégrale d'Ito à des processus non adaptés. Ce cours est une introduction à ces concepts ainsi qu'à leurs applications : le théorème de Girsanov généralisé, critère d'absolue continuité pour les solutions d'EDS, formule explicite d'Itô-Clark, calcul anticipatif, délit d'initié, calcul des grecques, transport optimal, etc.

1. Estimateurs à noyaux et par projection d’une densité. Validation croisée. Vitesses de convergence et optimalité.
2. Estimation non-paramétrique de la fonction de régression. Estimateurs par polynômes locaux, par projection (bases de Fourier, bases d’ondelettes). Vitesses de convergence et adaptation.
3. Estimation de fonctionnelles et tests non paramétriques. Vitesses de convergence et de tests, principes des intervalles de confiance non paramétriques.

L’objet de ce cours est de présenter quelques méthodes classiques de l’estimation non-paramétrique.

A.B.Tsybakov : Introduction to Nonparametric Estimation. Springer, New York, 2009. A.B.Tsybakov : Apprentissage statistique et estimation non-paramétrique. Polycopié de l’Ecole Polytechnique, 2014. L. Wasserman : All of Nonparametric Statistics. Springer, New York, 2006. L. Devroye : A Course in Density Estimation. Birkhauser, Boston, 1987. A.Nemirovski : Topics in non-parametric statistics. Ecole d’Eté de Probabilités de Saint-Flour XXVIII - 1998. Lecture Notes in Mathematics, v.1738. Springer, 2000.

Nous présenterons le modèle de Percolation. Il s’agit du modèle probabiliste le plus simple qui exhibe un phénomène complexe de transition de phases. L’intérêt pour ce modèle n’a fait que croître depuis son introduction et il joue désormais un rôle central en théorie des probabilités. Le cours ne nécessite pas de prérequis compliqués, au-delà des notions de base en probabilité, géométrie et topologie.

Comprendre les problèmes posés par la grande dimension ; fournir des bases conceptuelles et méthodologiques solides, indispensables pour développer des analyses statistiques pertinentes et performantes ; acquérir des techniques mathématiques fondamentales en vue d'une thèse. La principale difficulté du statisticien face aux données du XXIe siècle est de vaincre le fléau de la grande dimension. Ce fléau oppose aux statisticiens deux difficultés : d'une part il rend les méthodes statistiques classiques totalement inopérantes par manque de précision, d'autre part il oblige à développer des approches gardant sous contrôle la complexité algorithmique des procédures d'estimation. Nous verrons comment vaincre ce fléau dans un contexte général, puis comment rendre opérationnels ces concepts, avec une attention sur les frontières du possible. Les différentes situations sont illustrées à l'aide d'exemples issus des sciences du vivant.

Le cours introduira des notions importantes pour comprendre certains comportements des réseaux de neurones: implicit regularization, begnin overfitting, NTK, etc

Nous travaillerons sur des données liées à l'énergie (consommation électrique, production PV et éolien…). Nous étudierons différentes méthodes de régression non-linéaire issues de récents développements en statistiques et machine learning et ayant faits leurs preuves dans ce contexte : generalized additive model, random forest, gradient boosting machine, curve linear regression, agrégation d'experts. e cours propose une démarche fréquente dans l'industrie ou lors de la conduite d'un projet de recherche en statistique appliquée. Plusieurs étapes seront menées : data mining exploratoire (analyse descriptive, visualisation, recherche bibliographique sur les données et le phénomène à modéliser), la modélisation proprement dite (choix de modèle, prétraitements/transformation des données, construction d'un code, validation) puis enfin l'évaluation des performances et la restitution des résultats (présentation et rédaction d'un rapport).

L'objectif du projet est d'acquérir une expérience de modélisation statistique, de la préparation des données à la réponse au problème posé. Il s'agit de comparer différents modèles et méthodes statistiques pour analyser un jeu de données associé à une problématique de prévision. L'objectif du projet est d'aboutir à une modélisation performante des données (réalisant une faible erreur de prévision et pouvant raisonnablement être mise en œuvre).

Le cours sera consacrée à la théorie du calcul stochastique. On présentera d'abord le mouvement brownien et certaines de ses propriétés les plus importantes. On discutera ensuite les martingales continues, processus aléatoires qui généralisent le mouvement brownien, et on introduira les semi-martingales continues, qui peuvent s'écrire comme somme d'une martingale continue et d'un processus à variation finie. On développera dans ce cadre la théorie du calcul stochastique d'Itô, et on donnera en particulier une forme générale de la formule d'Itô, puis on développera plusieurs applications, dont le célèbre théorème de Girsanov ou le théorème de Dubins-Schwarz qui affirme que toute martingale continue peut s'écrire comme un mouvement brownien changé de temps. On terminera en utilisant le calcul stochastique pour traiter l'exemple fondamental des processus de diffusion, qui sont obtenus comme solutions d'équations différentielles stochastiques dirigées par un mouvement brownien multi-dim.

I. Karatzas, S. Shreve : Brownian motion and stochastic calculus. Springer J.F. Le Gall : Brownian motion, martingales and stochastic calculus. Springer 2016 D. Revuz, M. Yor : Continuous martingales and Brownian motion. Springer L.C.G. Rogers, D. Williams : Diffusions, Markov processes and martingales, vol. II. Wiley

Probability Theory Measure Theory

• Online learning with experts
• Azuma-Hoeffding inequality
• Stochastic multi-armed bandits : regret bounds of main algorithms
• Kullback Leibler divergence
• Lower bounds
• Linear bandits
• Contextual and continuous bandits
• Best arm identification

Sequential learning deals with data observed on the fly. Algorithms treat these data in a sequential (or online) manner, hoping to maximise their cumulated reward. It has been popularised in the last decade due to its numerous applications, which include online recommandation, repeated auctions or spam detection. The objective of this course is to introduce the main concepts of stochastic online learning (regret, adaptivity...) from a rigorous mathematical point of view. In particular, the course will focus on stochastic multi-armed bandits, aiming at understanding the main proofs techniques and algorithms. This course will also introduce the technical tools used in the regret bounds proof, including concentration inequalities and information theory.

"Prediction, learning, and games" Nicolò Cesa-Bianchi and Gábor Lugosi. Cambridge University Press, 2006 "Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems" Sebastien Bubeck and Nicolò Cesa-Bianchi. In Foundations and Trends in Machine Learning, 2012 "Bandit algorithms" Tor Lattimore and Csaba Szepesvári. Cambridge University Press, 2020.

Voici une liste des thèmes que nous aborderons : Marches aléatoires. Arbres de Bienaymé--Galton--Watson et leurs codages. Graphe aléatoire d'Erdös-Rényi, propriétés locales et transition de phase pour la composante géante. Modèle de configuration. Arbres à attachement préférentiel. Permutations uniformes. Echangeabilité, urne de Polya.

Le polycopié est disponible sur la page web de N. Curien

La première partie du cours est consacrée à l'étude de la notion de convergence en loi, dans un cadre assez général où les objets aléatoires considérés prennent leurs valeurs dans un espace métrique complet (éventuellement infini-dimensionnel). On démontre en particulier le théorème de Prohorov qui caractérise les familles de mesures de probabilité relativement compactes pour la topologie en loi. Cette théorie est ensuite appliquée pour établir le théorème de Donsker, selon lequel une marche aléatoire à pas indépendants et de même loi converge après renormalisation vers un mouvement brownien. Dans la seconde partie du cours, on étudie les mesures aléatoires de Poisson, puis les processus de Lévy : ce sont des processus aléatoires généralisant le mouvement brownien et admettant possiblement des sauts, et ils sont classifiés par le théorème de Lévy-Khintchine. La première partie du cours permet d'en donner une construction à la Donsker.

Un des deux buts poursuivis dans ce cours est de donner un aperçu de la théorie non asymptotique pour la sélection de modèles qui s'est construite au cours de ces dix dernières années. Dans différents contextes d'estimation fonctionnelle, il est possible de construire des critères de type log-vraisemblance pénalisée où la pénalité dépend non seulement du nombre de paramètres définissant des modèles comme dans les critères classiques, mais aussi de la " complexité " de la liste de modèles. Dans cette approche, les dimensions des modèles ainsi que la liste de modèles elle-même sont autorisés à dépendre du nombre d'observations. L'expression des pénalités tout autant que l'analyse des performances de ces procédures pénalisées en terme de risque de manière essentielle d'inégalités dites de concentration dont le prototype est l'inégalité de Talagrand pour les processus empiriques.

Nous introduirons tout d'abord le formalisme de base (noyau, opérations sur les noyaux, opérateurs) puis étendrons au cas continu des résultats élémentaires (Chapman-Kolmogorov, Markov fort, problèmes de Dirichlet et Poisson). Nous étudierons ensuite l'ergodicité des chaînes et le contrôle de convergence. Nous présenterons tout d'abord l'ergodicité uniforme en variation totale (sous la condition de Doeblin uniforme), que nous étendrons à l'ergodicité non uniforme sous les conditions de Foster-Lyapounov (existence d'un petit ensemble et condition de dérive). Nous spécialiserons ensuite ces résultats à des espaces topologiques, en introduisant tout d'abord des résultats généraux sur les chaînes Felleriennes et fortement Felleriennes puis en présentant des méthodes permettant d'obtenir des résultats de convergence plus quantitifs (convergence en distance de Wasserstein, étude des systèmes itératifs). Nous présenterons succinctement les extensions non géométriques.

L'objet de ce cours est d'introduire les outils d'analyse de chaînes de Markov sur des espaces généraux. Nous illustrerons ces théories avec de nombreux exemples, permettant de comprendre la richesse de cette méthode, mais aussi ses limites.

La première partie du cours présentera les fondements de la théorie statistique de l’apprentissage supervisé, en classification et en régression. Nous établirons des bornes sur l’erreur de prédiction de plusieurs méthodes d’apprentissage parmi les plus classiques : moyennage local (partitions, k plus proches voisins, noyaux) et minimisation du risque empirique. La deuxième partie du cours se focalisera sur les méthodes de rééchantillonnage (bootstrap, sous-échantillonnage, validation croisée, etc.) et à leur application en apprentissage. Nous étudierons en particulier leurs propriétés pour l’estimation de l’erreur de prédiction d’une méthode d’apprentissage, et pour la sélection parmi une famille de méthodes d’apprentissage.

L'expression des pénalités tout autant que l'analyse des performances de ces procédures pénalisées en terme de risque de manière essentielle d'inégalités dites de concentration dont le prototype est l'inégalité de Talagrand pour les processus empiriques. Ces nouveaux outils de calcul des probabilités seront également étudiés pour eux-mêmes. Nous développerons en particulier la méthode entropique initiée par Michel Ledoux il y a une dizaine d'années. Cette méthode permet en effet d'accéder à des résultats fins avec une économie de moyens remarquable.

La majorité des problèmes d’apprentissage sont formulés comme des problèmes d’optimisation, à partir de l’observation d’un échantillon de données (ensemble d’entrainement). L’optimisation d’un objectif défini à partir de cet échantillon permet de proposer un estimateur qui a une bonne performance sur l’ensemble d’apprentissage. Cependant, on s’intéresse généralement à la capacité de généralisation de cet estimateur, c’est à dire sa performance sur une nouvelle observation.

Dans ce cours, on s’intéresse à l’ensemble des résultats tant théoriques qu’heuristiques qui permettent d’aboder de problème. Plus précisément, on étudiera dans un premier temps les différentes approches qui permettent d’obtenir des garanties théoriques quant à la généralisation des algorithmes, en particulier les approches liées à la complexité, à la stabilité, aux méthodes d’arrêt anticipé (Early stopping). Dans une seconde partie, on étudiera les approches heuristiques et les différences (expliquées ou constatées) dans le cadre du deep learning (non convexe et over-parametrized).Le cours comportera également des séances d’ouverture pour explorer le flot de gradient et la quantification de l’incertitude en termes de généralisation.Dans ce cours, on s’intéresse à l’ensemble des résultats tant théoriques qu’heuristiques qui permettent d’aboder de problème. Plus précisément, on étudiera dans un premier temps les différentes approches qui permettent d’obtenir des garanties théoriques quant à la généralisation des algorithmes, en particulier les approches liées à la complexité, à la stabilité, aux méthodes d’arrêt anticipé (Early stopping). Dans une seconde partie, on étudiera les approches dans le cadre du deep learning.

General Topology and Functional Analysis

1. Convex Sets.- 2. Convex Funtions.- 3. Subdifferential.- 4. Proximal Operator.- 5. Convex Duality.-