Concentration of measure in probability and high-dimensional statistical learning

Two homeworks will count for 25% each of the final note. Homework 1 and Homework 2 are due on November 15th.

Guillaume Aubrun, Aurélien Garivier, Rémi Gribonval

This course will introduce the notion of concentration of measure and highlight its applications, notably in high dimensional data processing and machine learning.
The course will start from deviations inequalities for averages of independent variables, and illustrate their interest for the analysis of random graphs and random projections for dimension reduction.
It will then be shown how other high-dimensional random functions concentrate, and what guarantees this concentration yields for randomized algorithms and machine learning procedures to learn from large training collections.

Presentation slide

- [09.07, Amphi A] (Gribonval) [INFO5161 only] Learning in high-dimension – introduction – basic concentration results – Chernoff-Hoeffding
- [09.11, Amphi F] (Garivier) [INFO5161 only] Martingales, Azuma, McDiarmid and applications
- [09.14 Amphi A] (Gribonval) [MATH5107 & INFO5161 from now on] McDiarmid inequality - The PAC framework for statistical learning - general principles
- [09.18 Amphi F] (Gribonval) Agnostic PAC bounds for ERM - sub-Gaussian and sub-Exponential variables
- [09.21 Amphi D] (Garivier) Uniform convergence, VC dimension and the fundamental theorem of PAC learning
- [09.25 Amphi H] (Aubrun) Geometry of high-dimensional spaces
- [09.28 Amphi D] (Garivier) Lower bounds for large deviations, and No Free Lunch theorems
- [10.02 Amphi H] (Aubrun) Gaussian Concentration
- [10.05 Amphi D] (Garivier) Negative association, Sequential analysis
- [10.09 Amphi H] (Aubrun)
*Correction of the exercises* - [10.12 Amphi D] (Gribonval) Dimensionality reduction
- [10.16 Amphi H] (Aubrun) Chaining
- [10.19 Amphi D] (Gribonval) Random projections
- [10.23 Amphi H] (Aubrun) Analysis of Boolean functions
- [11.02 Amphi D] (Garivier) Case study: optimal discovery and the Good-Turing estimator
- [11.06 Amphi H] (Aubrun) Hypercontractivity
- [11.09 Amphi F] student presentations / exam
- [11.13 Amphi H] student presentations / exam

- Connect to the course web page https://etudes.ens-lyon.fr/course/view.php?id=4270
- Click on the link "Link for the virtual class - cours "Concentration”
- Click on “Enter the session” / “Entrer dans la session”

Exercise sheet number 2

Exercise sheet number 3

- Modèles génératifs des méthodes de réduction de dimension par embedding, avec Franck Picard au LBMC
- Prévision d'extrêmes météorologiques par des méthodes de ML/DL, avec Clément Dombry (LmB), Philippe Naveau (LSCE) et Maxime Taillardat (CNRM, Meteo-France)
- Open Internship positions in Artificial Intelligence and Machine learning in Toulouse

- Achlioptas, D. (2001). Database-friendly random projections (pp. 274–281). Presented at the Principles of database systems (PODS), New York, New York, USA: ACM Press. http://doi.org/10.1145/375551.375608
- Puy, G., Davies, M. E., & Gribonval, R. (2017). Recipes for Stable Linear Embeddings From Hilbert Spaces to $ {\mathbb {R}}^{m}$. IEEE Transactions on Information Theory, 63(4), 2171–2187. http://doi.org/10.1109/tit.2017.2664858
- Tropp, J. A. (2008). On the conditioning of random subdictionaries. Appl. Comput. Harmon. Anal., 25(1), 1–24. https://www.sciencedirect.com/science/article/pii/S1063520307000863
- Bach, F. (2015). On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions. https://jmlr.org/papers/volume18/15-178/15-178.pdf

Basic knowledge of probability theory, linear algebra and analysis over the reals.

- Concentration Inequalities,
*by Stéphane Boucheron, Pascal Massart and Gabor Lugosi* - High-Dimensional Probability – An Introduction with Applications in Data Science,
*by Roman Vershynin* - Understanding Machine Learning, From Theory to Algorithms,
*by Shai Shalev-Shwartz and Shai Ben-David*

Two homeworks: 25% each.
Homework 1 and Homework 2 are due on November 15th.

Project: paper / chapter presentation

a/ Written document: half a page summary

Your ability to explain them: many persons in the audience are not necessarily experts.

Your critical analysis of the studied papers / chapters.

Possible complementary bibliographical references bringing additional viewpoints.