The aim of this course is to provide an introduction to asymptotic and non-asymptotic methods for the study of random structures in high dimension that arise in probability, statistics, machine learning, numerical mathematics etc. The main emphases is on the development of a common set of tools that has proved to be useful in a wide range of applications in different areas. Topics will include concentration of measure, random matrices, Stein's methods and limit theorem of probability theory.

Program

1. Introduction to concentration of measure; tensorization of variance.
2. Chernoff estimate, Heffding's inequality; applications to multi-armed bandits; exploration vs exploitation; optimism in the face of uncertainty.
3. Bernstein's inequality.
4. Subgaussian and subexponential random variables.
5. Concentration on the sphere and Gaussian concentration; Johnson-Lindenstrauss lemma.
6. Matrix Bernstein's inequality.
7. Applications to community detection and randomized algorithms in computational mathematics; estimation of covariance matrices and projectors.
8. Poincaré's inequality and convergence of Markov processes; applications to diffusion based MCMC algorithms.
9. Stein's method.

The Course is part of the International Thematic Program “Mathematical Foundations of Artificial Intelligence".

Lecturer
Naumov Aleksei Aleksandrovich

Financial support
The course is supported by the Ministry of Science and Higher Education of the Russian Federation (the grant to the Steklov International Mathematical Center, Agreement no.  075-15-2022-265).

Institutions
Steklov Mathematical Institute of Russian Academy of Sciences, Moscow
Steklov International Mathematical Center