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 | [slides] |
|
| Feb 12 | Convex geometry and optimization (I) | [slides] |
|
| Feb 17 | Convex geometry and optimization (I), Cont. | [slides] |
|
| Feb 19 | Convex geometry and optimization (I), Cont. | [slides] |
|
| Feb 24 | Convex geometry and optimization (II): Gradient Descent | [slides] |
|
| Feb 26 | Convex geometry and optimization (III): Oracle and Reductions | [slides] |
|
| Mar 3 | Spectral methods (I): SVD | [slides] |
|
| Mar 5 | Spectral methods (I): SVD | [slides] |
|
| Mar 10 | Midterm | ||
| Mar 12 | Spectral methods (I): SVD | [slides] |
|
| Mar 24 | Spectral methods (II): Markov Chains | [slides] |
|
| Mar 26 | Spectral methods (II): Markov Chains | [slides] |
|
| Mar 31 | Matrix Analysis and Concentration | [slides] |
|
| Apr 2 | Matrix Analysis and Concentration | [slides] |
|
| Apr 7 | Boolean function analysis (I): Basics of discrete Fourier analysis | [slides] |
|
| Apr 9 | Boolean function analysis (II): Linearity testing | [slides] | |
| Apr 14 | Boolean function analysis (III): Degree, query complexity, and sensitivity | ||
| Apr 16 | Boolean function analysis (III): Degree, query complexity, and sensitivity | ||
| Apr 21 | Boolean function analysis (IV): Isoperimetric inequalities over the hypercube | ||
| Apr 23 | Project presentations | ||
| Apr 28 | Project presentations | ||
| Apr 30 | Project presentations |