News
- Mar 23: Assignment 3 is now posted
- Mar 4: The midterm exam is over
- Mar 2: Assignment 2 is now posted
- Feb 2: Assignment 1 is now posted
- Jan 26: Tutorial 1 slides have been posted on Piazza → Resources
Information
- Online lectures
- Tue 5:30-6:15pm Thu 2:30-4:15pm
- Online tutorials
- Tue 3:30-4:15pm (Certain weeks only)
- Zoom
-
956 1463 3060 (for both lectures and tutorials)No passcode, but CUHK-authenticated Zoom accounts are required to join
- Instructor
- Siu On CHAN Office hours: Thu 4:30-6:30pm (Zoom 984 7747 9788)
- Teaching assistant
-
Hao WU
hwu@cse - Prerequisites
- Probability, Discrete Math, Engineering Math (Linear Algebra), Computational Complexity (NP-Hardness)
- Textbook
- An Introduction to Computational Learning Theory, Michael J. Kearns and Umesh V. Vazirani (link) (accessible online at the university library webpage, one user at a time)
- References
- Understanding Machine Learning: From Theory to Practice, Shai Shalev-Shwartz and Shai Ben-David (free online copy at the author’s homepage)
- Forum
- Please sign up on Piazza
- Grading
- Homework (30%), Midterm exam (30%), Final exam (40%)
- Similar courses
- Introduction to Computational Learning Theory (Spring 2021), Rocco Servedio
- Machine Learning Theory (Fall 2020), Ilias Diakonikolas
- Theoretical Foundations of Machine Learning (Spring 2018), Michael Kearns
- Computational Learning Theory (Hilary & Trinity 2021), Varun Kanade
Topics
This course focuses on theoretical aspects of supervised learning, with emphasis on provable guarantees of classification algorithms. This course is for mathematically and theoretically minded students, and complements other machine learning courses that are application-oriented.
- Online mistake bound model
- Probably Approximately Correct (PAC) learning model
- VC dimension
- Occam’s Razor
- Weak learning vs strong learning
- Boosting
- AdaBoost
- Computational hardness of learning
- Statistical Query learning
- Learning with noise
- Differential privacy
- Rademacher complexity
- Inherent hardness of learning
Lectures
Lecture recordings will be posted on Piazza → Resources after classes
| Date | Topic | Readings | Notes | Tutorials | HW | |
|---|---|---|---|---|---|---|
| 1 | Jan 12 | Introduction; Learning models & problems | §1.1, Blum §3 | |||
| 2 | Jan 14 | Online mistake bound; decision lists | Blum §3.1 | |||
| 3 | Jan 19 | Winnow algorithms | Littlestone §5 | |||
| 4 | Jan 21 | Perceptron and Halving algorithms | Littlestone §3 | |||
| 5 | Jan 26 | Generic bounds for online learning; VC dimension | §3.1-3.3 | ✔ | ||
| 6 | Jan 28 | Weighted majority | LW §1-2 | |||
| 7 | Feb 2 | PAC learning | §1.2 | HW 1 | ||
| 8 | Feb 4 | Online to PAC conversion | ||||
| 9 | Feb 9 | Occam’s Razor | §2.1 | |||
| Feb 11 | Lunar New Year Holiday | |||||
| Feb 16 | Lunar New Year Holiday | |||||
| 10 | Feb 18 | Chernoff bounds; Hypothesis testing | §2.1 | |||
| 11 | Feb 23 | Proper vs improper learning; 3-term DNFs | §1.3-1.4 | ✔ | ||
| 12 | Feb 25 | Sample size bounds via VC dimension | §3.5-3.6 | |||
| 13 | Mar 2 | Sauer–Shelah lemma | §3.4 | HW 2 | ||
| Mar 4 | Online Midterm exam | |||||
| 14 | Mar 9 | Weak and strong learning; Boosting | §4.1-4.2 | |||
| 15 | Mar 11 | AdaBoost | ||||
| 16 | Mar 16 | Neural networks | §3.7 | ✔ | ||
| 17 | Mar 18 | Random classification Noise; Statistical Query model | §5.1-5.3 | |||
| 18 | Mar 23 | Learning with noise via Statistical Query model | §5.4 | HW 3 |
| Date | Topic | Readings | Notes | Tutorials | HW | |
|---|---|---|---|---|---|---|
| 1 | Jan 12 | Introduction; Learning models & problems | §1.1, Blum §3 | |||
| 2 | Jan 14 | Online mistake bound; decision lists | Blum §3.1 | |||
| 3 | Jan 19 | Winnow algorithms | Littlestone §5 | |||
| 4 | Jan 21 | Perceptron and Halving algorithms | Littlestone §3 | |||
| 5 | Jan 26 | Generic bounds for online learning; VC dimension | §3.1-3.3 | ✔ | ||
| 6 | Jan 28 | Weighted majority | LW §1-2 | |||
| 7 | Feb 2 | PAC learning | §1.2 | HW 1 | ||
| 8 | Feb 4 | Online to PAC conversion | ||||
| 9 | Feb 9 | Occam’s Razor | §2.1 | |||
| Feb 11 | Lunar New Year Holiday | |||||
| Feb 16 | Lunar New Year Holiday | |||||
| 10 | Feb 18 | Chernoff bounds; Hypothesis testing | ||||
| 11 | Feb 23 | Proper vs improper learning; 3-term DNFs | §1.3-1.4 | ✔ | ||
| 12 | Feb 25 | Sample size bounds via VC dimension | §3.5-3.6 | |||
| 13 | Mar 2 | Sauer–Shelah lemma | §3.4 | HW 2 | ||
| Mar 4 | Online Midterm exam | |||||
| 14 | Mar 9 | Weak and strong learning; Boosting | §4.1-4.2 | |||
| 15 | Mar 11 | AdaBoost | ||||
| 16 | Mar 16 | Neural networks | §3.7 | ✔ | ||
| 17 | Mar 18 | Random classification Noise; Statistical Query model | §5.1-5.3 | |||
| 18 | Mar 23 | Learning with noise via Statistical Query model | §5.4 | HW 3 | ||
| 19 | Mar 25 | Lower bound for Statistical Query model | ||||
| Mar 30 | Reading week | |||||
| Apr 1 | Reading week | |||||
| Apr 6 | Day after Easter Monday | |||||
| 20 | Apr 8 | Differential privacy | ||||
| 21 | Apr 13 | Differential privacy via Statistical Query algorithms | ✔ | |||
| 22 | Apr 15 | Rademacher complexity | ||||
| 23 | Apr 20 | Generalization bound from Rademacher complexity | ||||
| 24 | Apr 22 | Inherent hardness of learning |
Homework
There will be three homework assignments
Submit your answers as a single PDF file via Blackboard by 11:59pm
You are encouraged to either typeset your solution in LaTeX or Word, or scan or take photos of your handwritten solution (please bundle your scans/photos into a single PDF file)
Collaboration on homework and consulting references is encouraged, but you must write up your own solutions in your own words, and list your collaborators and your references on the solution sheet
- Assignment 1 due Wed Feb 17
- Assignment 2 due Mon Mar 15
- Assignment 3 due Tue Apr 6