High-dimensional Probability and Statistics (2025) — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показаны 3 промежуточные версии этого же участника)
Строка 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, [[#Weissman]|[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)  
+
* (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.
 +
 
 +
* (05.03.24) Uniform Johnson-Lindenstrauss lemma (Theorem 5.10 from [[#blm|[BLM]]]). A modified logarithmic Sobolev inequality (Theorem 6.7 from [[#blm|[BLM]]]).
 +
 
 +
* (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 |[Tropp]]]). Application to graph sparsifying (Chapter 32 from [[#Spielman | [Spielman]]]).
  
 
== Grading ==
 
== Grading ==
Строка 32: Строка 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 ==
Строка 40: Строка 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 =
Строка 62: Строка 75:
  
 
<span id="Weissman">[Weissman]</span> [https://disk.yandex.ru/i/OPDZenkw-OPSAA Tsachy Weissman. Information theory, Lecture notes]
 
<span id="Weissman">[Weissman]</span> [https://disk.yandex.ru/i/OPDZenkw-OPSAA Tsachy Weissman. Information theory, Lecture notes]
 +
 +
<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).
  • (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.

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

Источник — «http://wiki.cs.hse.ru/index.php?title=High-dimensional_Probability_and_Statistics_(2025)&oldid=91071»