Scribe Notes and Slides for MATH 888

Scribe notes, as well as slides, will be posted here as they become available.

List of Topics

Here is a tentative outline (click on the links for more details).

1. Statistical background I: Point estimation

2. Basic concentration inequalities: Hoeffding, Bernstein, Hanson-Wright

3. Sub-Gaussian vectors, random matrices and metric entropy with applications to mean and covariance estimation

4. Statistical background II: Hypothesis testing with an introduction to the multiple testing problem

5. Information-theoretic lower bounds

6. Sparse linear regression and related matrix estimation problems

Slides

We will occasionally use slides. They will be posted here.

• Lecture 1 (09/08/21): Introduction to high-dimensional data

• Lecture 2 (09/10/21): Review of point estimation

• Lecture 3 (09/13/21): Important probability facts

• Lecture 6 (09/20/21): Lp spaces

• Lecture 9 (09/27/21): Facts about conditional expectation

• Lecture 11 (10/01/21): Matrix norms and singular value decomposition

• Lecture 12 (10/04/21): Isotropy

• Lecture 16 (10/13/21): Extremal characterization of eigenvalues and perturbation theory

• Lecture 19 (10/20/21): Isometries

• Lecture 20 (10/22/21): Matrix Bernstein's inequality

• Lecture 24 (11/01/21): Review of hypothesis testing

• Lecture 25 (11/03/21): Information-theoretic concepts

• Lecture 27 (11/08/21): Overview of multiple testing

• Lecture 28 (11/11/21): Controlling the false discovery rate

• Lecture 40 (12/10/21): Spectral clustering for almost exact community recovery

Scribe notes

Scribe notes will be posted below. See the instructions for scribing.

• Lecture 3 (09/13/21): Comparison of estimators (source)

• Lecture 4 (09/15/21): Cramer-Rao bound: setting and statement (source; alternate notes: PDF, source)

• Lecture 5 (09/17/21): Cramer-Rao bound: proof and examples (source; alternate notes: PDF, source)

• Lecture 6 (09/20/21): Sub-Gaussian variables (source)

• Lecture 7 (09/22/21): Hoeffding's and Bernstein's inequalities (source; alternate notes: PDF, source)

• Lecture 8 (09/24/21): Concentration of the norm (source; alternate notes: PDF, source)

• Lecture 9 (09/27/21): Hanson-Wright inequality: statement and proof ideas (source; alternate notes: PDF, source)

• Lecture 10 (09/29/21): Hanson-Wright inequality: decoupling and comparison (source; alternate notes: PDF, source)

• Lecture 11 (10/01/21): Hanson-Wright inequality: proof and application (source; alternate notes: PDF, source)

• Lecture 12 (10/04/21): Sub-Gaussian vectors (source)

• Lecture 13 (10/06/21): Mean estimation for sub-Gaussian vectors (source; alternate notes: PDF, source)

• Lecture 14 (10/08/21): Mean estimation for anisotropic sub-Gaussian vectors (source; alternate notes: PDF, source)

• Lecture 15 (10/11/21): Application to linear regression (source; alternate notes: PDF, source)

• Lecture 16 (10/13/21): A first oracle bound (source; alternate notes: PDF, source)

• Lecture 17 (10/15/21): Suprema of processes: finite case (source; alternate notes: PDF, source)

• Lecture 18 (10/18/21): Suprema of processes: eps-nets and Lipschitz processes (source)

• Lecture 19 (10/20/21): Spectral norm of a random matrix (source)

• Lecture 20 (10/22/21): Covariance estimation (source)

• Lecture 21 (10/25/21): PCA and spiked covariance model: setting (source)

• Lecture 22 (10/27/21): PCA and spiked covariance model: proof sketch (source)

• Lecture 23 (10/29/21): PCA and spiked covariance model: finishing the proof (source)

• Lecture 26 (11/05/21): Lower bounds: from estimation to testing (source)

• Lecture 29 (11/12/21): Lower bounds: proof (source)

• Lecture 30 (11/15/21): Lower bounds: more examples (source)

• Lecture 31 (11/17/21): Fano's method: statement and example (source; alternate notes: PDF, source)

• Lecture 32 (11/19/21): Fano's method: example continued (source; alternate notes: PDF, source)

• Lecture 33 (11/22/21): Fano's method: proof (source)

• Lecture 34 (11/24/21): Sparse linear regression: first steps (source)

• Lecture 35 (11/29/21): Sparse linear regression: first steps continued (source)

• Lecture 36 (12/01/21): Sub-Gaussian sequence model (source)

• Lecture 37 (12/03/21): Lasso estimator: slow and fast rates (source)

• Lecture 38 (12/06/21): Incoherence of a random design; Sparse oracle inequality (source; alternate notes: PDF, source)

• Lecture 39 (12/08/21): Community recovery: basic definitions (source)

• Lecture 40 (12/10/21): Community recovery: almost exact recovery (source)

• Lecture 41 (12/13/21): Community recovery: almost exact recovery continued (source)

• Lecture 42 (12/15/21): Community recovery: exact recovery (source)

Additional reading

Some optional reading will be posted here.

• PCA in High Dimensions: An Orientation, by Iain M. Johnstone and Debashis Paul

• Community Detection and Stochastic Block Models, by Emmanuel Abbe

• Spectral Methods for Data Science: A Statistical Perspective, by Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma

• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing by Chao Gao, Zongming Ma