High Dimensional Probability

Time: Tuesday, Thursday 10:30am - 11:45am

Location: Maxwell Dworkin 119

TA: Jarosław Błasiok (jblasiok (at) g.harvard.edu)

Course Description

CS 229 is a graduate course in probability theory. The primary focus will be on concentration of measure, random matrices and their applications to computer science and statistics.

I have decided to type up some lecture notes so that you can focus on the material in class rather than scrambling to write everything on the board. I will make the corresponding notes available after each lecture.

Lecture Notes

• Lecture 1 (Introduction) 1/29/2019
• Lecture 2 (Proofs of the Central Limit Theorem) 1/31/2019
• Lecture 3 (Proofs of the Central Limit Theorem II- Stein's Method) 2/5/2019
• Lecture 4 (Subgaussian Random Variables) 2/7/2019
• Lecture 5 (Anti-concentration I) 2/12/2019
• Lecture 6 (Anti-concentration II) 2/14/2019
• Lecture 7 (Norm of a Random Matrix) 2/19/2019
• Lecture 8 (Condition Number of Random Matrices) 2/21/2019
• Lecture 9 (Martingales, Bounded Differences & Talagrand's Inequality) 2/26/2019
• Lecture 10 (Applications) 2/28/2019
• Lecture 11 (Empirical Processes) 3/5/2019
• Lecture 12 (Chaining) 3/7/2019
• Lecture 13 (Compressed Sensing) (3/12/2019)
• Lecture 14 (Subsampling Fourier Matrices) (3/14/2019)
• Lecture 15 (Simplicity of Spectrum and Graph Isomorphism) (3/26/2019)
• Lecture 16 (Sums of Random Matrices) (3/28 /2019)
• Lecture 17 (Basic Tensor Theory) (4/2/2019)
• Lecture 18 (Basic Tensory Theory II) (4/4/2019) Notes coming soon!
• Lecture 19 (Guest Lecture: Prayaag Venkat on Mean Estimation) (4/9/2019)
• Lecture 20 (Polynomial Threshold Functions and Random Tensors) (4/11/2019)

Homework Assignments

• Problem Set 1 (Due: 2/19/2019) (tex source)
• Problem Set 2 (Due: 3/7/2019) (tex source)
• Problem Set 3 (Due: 4/9/2019) (tex source)