CSCI4230 Computational Learning Theory — Spring 2023

News

Information

Lectures
Tue 10:30-12:15pm (MMW 703) Wed 2:30-3:15pm (MMW 705)
Zoom
960 6586 2487 (for both lectures and tutorials)
No passcode, but CUHK-authenticated Zoom accounts are required to join
Instructor
Siu On CHAN Office hours: Tue 2:30-4:30pm
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%), Project report (40%)
Similar courses

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.

Lectures

Lecture recordings will be posted on Piazza → Resources after classes

Schedule
Date Topic Readings Notes Tutorials HW
1 Jan 10 Introduction; Learning models & problems §1.1, Blum §3 pdf
2 Jan 11 Online mistake bound; decision lists Blum §3.1 pdf
3 Jan 17 Winnow algorithms Littlestone §5 pdf
4 Jan 18 Perceptron and Halving algorithms Littlestone §3 pdf
Jan 24 Lunar New Year Holiday
Jan 25 Lunar New Year Holiday
5 Jan 31 Generic bounds for online learning; VC dimension §3.1-3.3 pdf
6 Feb 1 Weighted majority LW §1-2 pdf HW 1
7 Feb 7 PAC learning §1.2 pdf
8 Feb 8 Online to PAC conversion pdf
9 Feb 14 Occam’s Razor §2.1 pdf
10 Feb 15 Chernoff bounds; Hypothesis testing pdf
11 Feb 21 Proper vs improper learning; 3-term DNFs §1.3-1.4 pdf
12 Feb 22 Sample size bounds via VC dimension §3.5-3.6 pdf HW 2
Feb 28 Midterm exam
13 Mar 1 Sauer–Shelah lemma §3.4 pdf
Mar 7 Reading week
Mar 8 Reading week
Tentative schedule
Date Topic Readings Notes Tutorials HW
1 Jan 10 Introduction; Learning models & problems §1.1, Blum §3
2 Jan 11 Online mistake bound; decision lists Blum §3.1
3 Jan 17 Winnow algorithms Littlestone §5
4 Jan 18 Perceptron and Halving algorithms Littlestone §3
Jan 24 Lunar New Year Holiday
Jan 25 Lunar New Year Holiday
5 Jan 31 Generic bounds for online learning; VC dimension §3.1-3.3
6 Feb 1 Weighted majority LW §1-2 HW 1
7 Feb 7 PAC learning §1.2
8 Feb 8 Online to PAC conversion
9 Feb 14 Occam’s Razor §2.1
10 Feb 15 Chernoff bounds; Hypothesis testing
11 Feb 21 Proper vs improper learning; 3-term DNFs §1.3-1.4
12 Feb 22 Sample size bounds via VC dimension §3.5-3.6 HW 2
Feb 28 Midterm exam
13 Mar 1 Sauer–Shelah lemma §3.4
Mar 7 Reading week
Mar 8 Reading week
14 Mar 14 Weak and strong learning; Boosting §4.1-4.2
15 Mar 15 AdaBoost
16 Mar 21 Neural networks §3.7
17 Mar 22 Random classification Noise; Statistical Query model §5.1-5.3 HW 3
18 Mar 28 Learning with noise via Statistical Query model §5.4
19 Mar 29 Lower bound for Statistical Query model
20 Apr 4 Differential privacy
Apr 5 Ching Ming Festival
21 Apr 11 Differential privacy via Statistical Query algorithms
22 Apr 12 Rademacher complexity
23 Apr 18 Generalization bound from Rademacher complexity
24 Apr 19 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