High-dimensional Probability and Statistics (2025)

Classes

Wednesdays 13:00–16:00, in room G110.

Teachers: Fedor Noskov, Quentin Paris

Teaching Assistant: Fedor Noskov

Lecture/Seminar content

Probability

• (15.01.24) Chapter 3.1, Examples 3.5 and 3.14 from [BLM]

• (22.01.24) Chapters 3.6-3.7 from [BLM]. For the Sobolev spaces, weak derivatives and the approximation argument, see Chapters 5.2-5.3 [EvansPDE]. See also Chapters 2.1-2.3 of [Ziemer].

• (29.01.24) Chapter 2.1.2, Proposition 2.14 from [Wainwright]. Concentration of order statistics (folklore).

• (05.02.24) Chapter 2.2 from [Wainwright].

• (12.02.24) Chapter 2.1.3 from [Wainwright]. Orlicz norms, see Chapter 2.5 from [Vershynin].

• (19.02.24) Orlicz norms, see Chapter 2.5 from [Vershynin]. Sanov's theorem and KL-divergence, Chapter 6.2 from [Weissman].

• (26.02.24) KL-divergence. Definition of entropy. Herbst's argument (Proposition 3.2 from [Wainwright]). Gaussian Logarithmic Sobolev inequality (Theorem 5.4 from [BLM]). Sub-additivity of the entropy (Section 4.13 [BLM]). Concentration of Gaussian Lipschitz functions.

• (05.03.24) Uniform Johnson-Lindenstrauss lemma (Theorem 5.10 from [BLM]). A modified logarithmic Sobolev inequality (Theorem 6.7 from [BLM]).

• (12.03.24) Functional Hoeffding inequality (Theorem 3.26 from [Wainwright]). Largest eigenvalue of a random symmetric matrix (Example 6.8 from [BLM]). Matrix Chernoff bound (Lemma 6.12 from [Wainwright].

• (17.03.24) Matrix Chernoff from PSD matrices (Theorem 5.1.1 from [Tropp]). Application to graph sparsifying (Chapter 32 from [Spielman]).

Grading

The final grade is obtained as follows:

0.2 HW HDP + 0.3 Midterm HDP + 0.2 HW HDS + 0.3 Exam HDS,

where HW stands for home assignment, HDP stands for High-Dimensional Probability, HDS stands for High-Dimensional Statistics.

Midterm

See the midterm program here.

Home assignments

Please, send your solutions to Google classroom.

• Optional home assignment I. The deadline is April, 6, 23:59.

• Obligatory home assignment I. The deadline is March 30, 23:59.

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

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

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

[EvansPDE] Lawrence Evans. Partial Differential Equations

[Ziemer] William Ziemer. Weakly Differentiable Equations

[Weissman] Tsachy Weissman. Information theory, Lecture notes

[Tropp] Joel Tropp. An Introduction to Matrix Concentration Inequalities

[Spielman] Daniel Spielman. Spectral and Algebraic Graph Theory