##### Master’s Programme “Statistical Learning Theory”, 2nd year

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, computer science, and mathematics.

Lectures: Alexey Naumov (naumovne@gmail.com).
Seminars: Leonid Iosipoi (iosipoileonid@gmail.com).

Grade Components: home assignments (40%) + individual project (20%) + oral final exam (40%).

Important dates: defence of projects – December 6, final exam – December 13.

## Seminars

12.09.2019

#### Catalan numbers.

Recursive Definition of the Catalan numbers (balanced parentheses, Dyck paths, rooted binary trees, rooted trees). Generating function and explicit formula for the Catalan numbers.

Notes: Problem set 1.

#### Wigner’s Semicircular law.

Wigner matrices. Method of Moments. Moments of the Semicircular law. Proof of the Semicircular law (convergence in expectation). Generalized Wigner and Wigner type matrices.

Notes: Problem set 2.

References
[1] T. Davis. Catalan Numbers. Mathematical Circles Topics;
[2] T. Tao. Topics in Random Matrix Theory;
[3] Z. Bai, J. Silverstein. Spectral Analysis of Large Dimensional Random Matrices.

20.09.2019

#### Marchenko-Pastur law.

Sample covariance matrices. Moments of the Marchenko-Pastur law. Proof of the Marchenko-Pastur law (convergence in expectation).

Notes: Problem set 3.

References
[1] Z. Bai, J. Silverstein. Spectral Analysis of Large Dimensional Random Matrices;
[2] B. Valko. Lecture Notes on Random Matrices;
[3] T. Tao. Topics in Random Matrix Theory.

27.09.2019

#### Basic concentration inequalities and apllications.

Basic concentration inequalities: Markov and Chernoff bounds. Sub-Gaussian and sub-exponential random variables. Hoeffding bound. Johnson-Lindenstrauss embedding. Erdos-Renyi model.

Notes: Problem set 4.

References
[1] R. Vershynin. High-Dimensional Probability;
[2] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint;
[3] S. Boucheron, G. Lugosi, P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence.

04.10.2019

#### Epsilon-net argument.

Covering number of a unit sphere. Epsilon-net argument. A bound on the operator norm of a matrix with sub-Gaussian entries. Optimality of the epsilon-net argument.

Notes: Problem set 5.

References
[1] R. Vershynin. High-Dimensional Probability;
[2] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint.

11.10.2019

#### Epsilon-net argument for sample covariance matrices.

Sub-Gaussian random vectors. Epsilon-net argument for sample covariance matrices.

Notes: Problem set 6.

References
[1] J. A. Tropp. An Introduction to Matrix Concentration Inequalities;
[2] R. Vershynin. High-Dimensional Probability;
[3] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint.

18.10.2019

#### Comparison Method. Part I.

Lipschitz functions of Gaussian variables. Gaussian comparison inequalities (Sudakov-Fernique inequality). Bound on the expected value of the operator norm.

Notes: Problem set 7.

References
[1] R. Vershynin. High-Dimensional Probability;
[2] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint.

15.11.2019

#### Comparison Method. Part II.

Lipschitz functions of Gaussian variables. Gaussian comparison inequalities (Sudakov-Fernique inequality). Bound on the expected value of the operator norm.

Notes: Problem set 7.

References
[1] R. Vershynin. High-Dimensional Probability;
[2] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint.

22.11.2019

#### Bernstein-type bound

Bernstein condition for random variables. Bernstein inequality for random variables. Bernstein condition for random matrices. Bernstein inequality for random matrices.

Notes: Problem set 8.

References
[1] J. A. Tropp. An Introduction to Matrix Concentration Inequalities;
[2] R. Vershynin. High-Dimensional Probability;
[3] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint.