High-dimensional Probability and Statistics

Classes

Wednesdays 16:20–17:40, in room R307.

Teachers: Alexey Naumov, Quentin Paris

Teaching Assistant: Fedor Noskov

Lecture content

• (17.01.24) Chapter 1 from [van Handel]

Seminar content

Probability

• (17.01.24) Example 2.4 from [Wainwright], Lemma 2.2 from [BLM]

• (24.01.24) Appendix A and Exercise 2.2 of the second chapter of [Wainwright], Section 2.5.1 from [Vershynin]

• (31.01.24) Section 2.1.3 and Example 2.12 from [Wainwright]

• (07.02.24) Section 2.3 from [Wainwright]

• (24.02.24) Herbst's argument (Proposition 3.2 from [Wainwright]), Sub-additivity of the entropy (Theorem 4.22 from [BLM]), logorithmic Sobolev inequality for Gaussian random variables (Theorem 5.5 from [BLM])

• (07.03.24) PAC-Bayesian inequality. (Lemma 2.1 from [Zhivotovsky])

• (14.03.24) Dimension-free concentration of sample covariance matrix in the spectral norm (Theorem 1.2 of [Zhivotovsky])

• (21.03.24) Theorem 1.2 of [Zhivotovsky], Concentration of Lipshitz and separately convex function of bounded random variables (Theorem 6.10 from [BLM]), Concentration of the supremum of an empirical process (Section 3.4 of [Wainwright])

Statistics

• (10.04.24) Linear Regression. Bayesian information criterion. (Theorem 2.4 from [Rigollet])

• (17.04.24) Restricted isometry property and epsilon-incoherence. (Incoherence section, pp.59-62 of [Rigollet])

• (24.04.24) Incoherence of a random matrix with independent Rademacher entries (Incoherence section, pp.59-62 of [Rigollet]). Empirical risk minimization and Rademacher complexity (Sections 4.1-4.2 of [Wainwright]). Bounds on the Rademacher complexity of finite and finite-dimensional classes can be found in [Paris], Theorems 6.1 and 6.3.

• (15.05.24) VC-dimension, Sauer's lemma. (Section 4.3 of [Wainwright]).

• (22.05.24) Packing-covering duality. (Lemma 5.12 of [van Handel]). Uniform bound on the metric entropy via VC-dimension (Theorem 7.16 of [van Handel])

• (29.05.24) Uniform bound on the metric entropy via VC-dimension (Theorem 7.16 of [van Handel])

• (05.06.24) Offset Rademacher Complexity (some parts of [Puchkin])

References

links are available via hse accounts

[van Handel] Ramon van Handel. Probability in High Dimensions, Lecture Notes

[Vershynin] R. Vershynin. High-Dimensional Probability

[Wainwright] M.J. Wainwright. High-Dimensional Statistics

[BLM] Boucheron et al. Concentration inequalities

[Zhivotovsky] Nikita Zhivotovskiy. Dimension-free bounds for sums of independent matrices and simple tensors via the variational principle. Electron. J. Probab. vol. 29 (2024), article no. 13, 1–28.

[Rigollet] Philippe Rigollet and Jan-Christian H¨utter. High-Dimensional Statistics. Lecture Notes

[Paris] Quentin Paris. Statistical Learning Theory. Lecture Notes

[Puchkin] Nikita Puchkin, Nikita Zhivotovskiy. Exploring Local Norms in Exp-concave Statistical Learning. COLT 2023