High-dimensional Probability and Statistics (2025) — различия между версиями
Материал из Wiki - Факультет компьютерных наук
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 21: | Строка 21: | ||
* (12.02.24) Chapter 2.1.3 from [[#wainwright|[Wainwright]]]. Orlicz norms, see Chapter 2.5 from [[#vershynin|[Vershynin]]]. | * (12.02.24) Chapter 2.1.3 from [[#wainwright|[Wainwright]]]. Orlicz norms, see Chapter 2.5 from [[#vershynin|[Vershynin]]]. | ||
| − | * (19.02.24) Orlicz norms, see Chapter 2.5 from [[#vershynin|[Vershynin]]]. Sanov's theorem and KL-divergence, Chapter 6.2 from [[#Weissman | + | * (19.02.24) Orlicz norms, see Chapter 2.5 from [[#vershynin|[Vershynin]]]. Sanov's theorem and KL-divergence, Chapter 6.2 from [[#Weissman |[Weissman]]]. |
* (26.02.24) KL-divergence. Definition of entropy. Herbst's argument (Proposition 3.2 from [[#wainwright|[Wainwright]]]). Gaussian Logarithmic Sobolev inequality (Theorem 5.4 from [[#blm|[BLM]]]). Sub-additivity of the entropy (Section 4.13 [[#blm|[BLM]]]). Concentration of Gaussian Lipschitz functions. | * (26.02.24) KL-divergence. Definition of entropy. Herbst's argument (Proposition 3.2 from [[#wainwright|[Wainwright]]]). Gaussian Logarithmic Sobolev inequality (Theorem 5.4 from [[#blm|[BLM]]]). Sub-additivity of the entropy (Section 4.13 [[#blm|[BLM]]]). Concentration of Gaussian Lipschitz functions. | ||
| Строка 29: | Строка 29: | ||
* (12.03.24) Functional Hoeffding inequality (Theorem 3.26 from [[#wainwright|[Wainwright]]]). Largest eigenvalue of a random symmetric matrix (Example 6.8 from [[#blm|[BLM]]]). Matrix Chernoff bound (Lemma 6.12 from [[#wainwright|[Wainwright]]]. | * (12.03.24) Functional Hoeffding inequality (Theorem 3.26 from [[#wainwright|[Wainwright]]]). Largest eigenvalue of a random symmetric matrix (Example 6.8 from [[#blm|[BLM]]]). Matrix Chernoff bound (Lemma 6.12 from [[#wainwright|[Wainwright]]]. | ||
| − | * (17.03.24) Matrix Chernoff from PSD matrices (Theorem 5.1.1 from [[#Tropp | + | * (17.03.24) Matrix Chernoff from PSD matrices (Theorem 5.1.1 from [[#Tropp |[Tropp]]]). Application to graph sparsifying (Chapter 32 from [[#Spielman | [Spielman]]]). |
== Grading == | == Grading == | ||
| Строка 38: | Строка 38: | ||
where HW stands for home assignment, HDP stands for High-Dimensional Probability, HDS stands for High-Dimensional Statistics. | where HW stands for home assignment, HDP stands for High-Dimensional Probability, HDS stands for High-Dimensional Statistics. | ||
| + | |||
| + | |||
| + | == Midterm == | ||
| + | |||
| + | See the midterm program [https://disk.yandex.ru/i/Xd6yWNDGpXRu8Q here]. | ||
== Home assignments == | == Home assignments == | ||
| Строка 46: | Строка 51: | ||
* [https://classroom.google.com/c/NzQ3Njg2NjQ0NTc2/a/NzYyNTY4MzE1OTU3/details Obligatory home assignment I]. The deadline is March 30, 23:59. | * [https://classroom.google.com/c/NzQ3Njg2NjQ0NTc2/a/NzYyNTY4MzE1OTU3/details Obligatory home assignment I]. The deadline is March 30, 23:59. | ||
| + | |||
| + | * [https://classroom.google.com/c/NzQ3Njg2NjQ0NTc2/a/NzY2NzM4MTgxNTIz/details Obligatory home assignment II]. The deadline is June 22, 23:59. | ||
= References = | = References = | ||
| Строка 70: | Строка 77: | ||
<span id="Tropp">[Tropp]</span> [https://disk.yandex.ru/i/nzHbi_l_SALkew Joel Tropp. An Introduction to Matrix Concentration Inequalities] | <span id="Tropp">[Tropp]</span> [https://disk.yandex.ru/i/nzHbi_l_SALkew Joel Tropp. An Introduction to Matrix Concentration Inequalities] | ||
| + | |||
| + | <span id="Spielman">[Spielman]</span> [https://disk.yandex.ru/i/BIqcuUz1yZb0Cg Daniel Spielman. Spectral and Algebraic Graph Theory] | ||
Текущая версия на 19:46, 4 июня 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.
- Obligatory home assignment II. The deadline is June 22, 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
