Description: This course covers fundamental techniques and a range of mathematical tools that underlie today’s research in theoretical computer science and are essential knowledge for students pursuing research in theoretical computer science or machine learning theory. The course targets current graduate and undergraduate students interested in pursuing research in these areas. Topics will be chosen from four core areas: 1) Concentration Inequalities and their Applications. 2) Selected Topics in Convex Analysis and Optimization. 3) Foundations of Spectral Methods. 4) Discrete Fourier Analysis. Depending on student interest, additional topics will be chosen. The topics may include applied analysis for learning theory, coding theory, probabilistic proofs, graph algorithms, and sampling.
Time/Location: TTH 3:00 PM - 4:15 PM at HAAS G066
Instructor: Ruizhe Zhang Office hours: by appointment only
Teaching Assistant: Xiuyu Ye Office hours: 10:30 AM - 11:30 AM at DSAI B024
Course policy: See syllabus for detailed overview.
Assignments will be posted below and in Brightspace when they become available.
The schedule will be updated as we progress through the course.
| Date | Topic | Materials | Resources |
|---|---|---|---|
| Jan 13 | Introduction | [slides] |
|
| Jan 15 | No lecture | ||
| Jan 20 | Mathematical Basics | [slides] |
|
| Jan 22 | Concentration inequalities (I): Markov inequality and Chebyshev inequality | [slides] |
|
| Jan 27 | Concentration inequalities (II): Chernoff bounds | [slides] |
|
| Jan 29 | Concentration inequalities (III): Martingale method | [slides] |
|
| Feb 3 | Glivenko–Cantelli theorem; Concentration inequalities (IV): Entropy method | [slides] |
|
| Feb 5 | Concentration inequalities (IV): Talagrand's inequality | [slides] |
|
| Feb 10 | Special Topic: Asymptotic Convex Geometry | ||
| Feb 12 | Convex geometry and analysis (I) | ||
| Feb 17 | Convex geometry and analysis (II) | ||
| Feb 19 | Convex optimization (I): Gradient descent | ||
| Feb 24 | Convex optimization (II): Polynomial approximation | ||
| Feb 26 | Convex geometry / optimization | ||
| Mar 3 | Spectral methods (I): Basics | ||
| Mar 5 | Spectral methods (II): Markov chains | ||
| Mar 10 | Spectral methods (III): Matrix perturbation theory | ||
| Mar 12 | Matrix concentration inequalities (I) | ||
| Mar 24 | Matrix concentration inequalities (II) | ||
| Mar 26 | Boolean function analysis (I): Basics of discrete Fourier analysis | ||
| Mar 31 | Boolean function analysis (II): Linearity testing | ||
| Apr 2 | Boolean function analysis (III): Degree, query complexity, and sensitivity | ||
| Apr 7 | Boolean function analysis (IV): Degree, query complexity, and sensitivity | ||
| Apr 9 | Boolean function analysis (V): Isoperimetric inequalities over the hypercube | ||
| Apr 14 | Boolean function analysis (VI): Isoperimetric inequalities over the hypercube | ||
| Apr 16 | Special topics (I) | ||
| Apr 21 | Special topics (II) | ||
| Apr 23 | Project presentations | ||
| Apr 28 | Project presentations | ||
| Apr 30 | Project presentations |