M2 course, ENS Lyon:
Concentration of measure in probability and high-dimensional statistical learning

MATH5107 & INFO5161 : Master of Advanced Mathematics track Probability and Statistics, and Course CR15 of the M2SIF.

Lecturers

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

Course description

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

Weekly schedule: Mondays 13:30-15:30, Fridays 10:15-12:15

  1. [09.07, Amphi A] (Gribonval) [INFO5161 only] Learning in high-dimension – introduction – basic concentration results – Chernoff-Hoeffding
  2. [09.11, Amphi F] (Garivier) [INFO5161 only] Martingales, Azuma, McDiarmid and applications
  3. [09.14 Amphi A] (Gribonval) [MATH5107 & INFO5161 from now on] McDiarmid inequality - The PAC framework for statistical learning - general principles
  4. [09.18 Amphi F] (Gribonval) Agnostic PAC bounds for ERM - sub-Gaussian and sub-Exponential variables
  5. [09.21 Amphi D] (Garivier) Uniform convergence, VC dimension and the fundamental theorem of PAC learning
  6. [09.25 Amphi H] (Aubrun)
  7. [09.28 Amphi D] (Garivier)
  8. [10.02 Amphi H] (Aubrun)
  9. [10.05 Amphi D] (Garivier)
  10. [10.09 Amphi H] (Aubrun)
  11. [10.12 Amphi D] (Gribonval)
  12. [10.16 Amphi H] (Aubrun)
  13. [10.19 Amphi D] (Gribonval)
  14. [10.23 Amphi H] (Aubrun)
  15. [11.02 Amphi D] (Garivier)
  16. [11.06 Amphi H] (Aubrun)
  17. [11.09 Amphi F] student presentations / exam
  18. [11.13 Amphi H] student presentations / exam

Following at distance

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

Prerequisite

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

Evaluation

Homework, in-class exercices and final exam: 50%. Presentation of a research article: 50%.

Bibliography

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