Description
Randomness is one of the strongest tools which enables designing efficient algorithms. The applications of randomness in computer science spans machine learning algorithm, cryptography, networks, distributed systems. In this course, we study a variety of probabilistic tools and techniques that allow us to harness the power of randomness and apply it in algorithm design and learning theory.
Schedule
| Date | Material | Assignment |
|---|---|---|
| 01/09/2024 | Probability overview, testing sortedness Notes, Logistics (slides) |
Fill out this form and scribe sign up sheet.
Due on Monday, January 15, 11:59pm (CT) |
| 01/11/2024 | Testing sortedness (cont.), concenteration of r.v. , coin bias estimation Notes, Section 4.3 in IPT |
Problem set 1
Due on Thursday, January 25, 11:59pm (CT) |
| 01/16/2024 | Class cancelled due to weather condition | |
| 01/18/2024 |
Distribution testing: uniformity Notes, Reading: Section 11 in IPT |
|
| 01/23/2024 |
Poissonization Notes | |
| 01/25/2024 |
Distribution testing: closeness testing Notes (Same file as the previous lecture) | |
| 01/30/2024 |
Distribution testing: Reducing L2-norm via flattening Notes (Same file as the previous lecture) |
|
| 02/01/2024 |
Gaussian distribution, CLT, Berry-Esseen Theorem Notes |
Problem set 2
Due on Saturday, February 17, 11:59pm (CT) |
| 02/06/2024 |
Sub-Gaussian random variables Notes, Reading: Section 2.5 in HDP |
|
| 02/08/2024 | No class (Monday's schedule) | |
| 02/13/2024 |
Sub-exponential random variables Notes, Reading: Section 2.7 in HDP |
|
| 02/15/2024 |
Sub-exponential random variables (cont.), Bernstein condition, Bernstein's inequality Notes |
|
| 02/20/2024 |
Johnson-Lindenstrauss lemma Notes, Reading: Section 5.3 in HDP |
|
| 02/22/2024 |
Linnear regression Notes |
Project guidelines is posted.
Proposal is due on Thursday, March 07, 11:59pm (CT) |
| 02/27/2024 |
PAC learning Notes, Scribe notes, Reading: Chapter 1 of ICLT |
|
| 02/29/2024 |
PAC learning, Uniform convergence Notes, Scribe notes, Reading: Section 4 of UML |
|
| 03/05/2024 |
Uniform convergence (cont.), No free lunch theorem Notes, Scribe notes, Reading: Section 4 and 5 of UML |
|
| 03/07/2024 |
VC dimension, Fundamental theorem of PAC learning, Sauer-Shelah-Perles lemma Notes, Scribe notes, Reading: Section 4 and 6 of UML |
|
| 03/12/2024 | No class (Spring break) | |
| 03/14/2024 | No class (Spring break) |
Problem set 3
Due on Tuesday, April 2, 11:59pm (CT) |
| 03/19/2024 |
Fundamental theorem of PAC learning (cont.) Notes (same file as the previous lecture), Scribe notes, Reading: Section 4 and 6 of UML |
|
| 03/21/2024 |
Fundamental theorem of PAC learning (cont.), Learning in the presence of noise Scribe notes, Reading: Chapter 5 of ICLT |
|
| 03/26/2024 |
Learning boolean conjunctions, Statistical query model Scribe notes, Reading: Chapter 5 of ICLT |
|
| 03/28/2024 |
Learning in SQ model => learning in presence of noise Scribe notes, Reading: Chapter 5 of ICLT |
|
| 04/02/2024 |
Weak learning => Strong learning Scribe notes, Reading: Section 10 of UML |
|
| 04/04/2024 |
Adaboost Scribe notes, Reading: Section 10 of UML |
|
| 04/09/2024 |
Computational hardness of PAC learning: Learning 3-term DNFs Scribe notes, Reading: Chapter 1.4 of ICLT |
|
| 04/11/2024 |
Special topic: differential privacy
Scribe notes A good book: The Algorithmic Foundations of Differential Privacy |
Problem set 4
Due on Friday, April 19, 11:59pm (CT) |
| 04/16/2024 | Project presentations | |
| 04/18/2024 | Project presentations |
Useful material
- Some relevant textbooks (not required):
- An Introduction to Computational Learning Theory, by Michael Kearns and Umesh Vazirani
- High-Dimensional Probability: An Introduction with Applications in Data Science, by Roman Vershynin
- Introduction to Property Testing, by Oded Goldreich
- Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, by Michael Mitzenmacher and Eli Upfal
- Understanding Machine Learning: From Theory to Algorithms, by Shai Shalev-Shwartz and Shai Ben-David
- Useful inequalities cheat sheet, by László Kozma
- LaTeX template for scribe notes or problem set answers