40718 Machine Learning Theory

Hamid Beigy, Sharif University of Technology, Spring Semester 2021-22.

Course Description

Machine learning theory concerns questions such as: What kinds of guarantees can we prove about practical machine learning methods, and can we design algorithms achieving desired guarantees? This course answers these questions by studying the theoretical aspects of machine learning, with a focus on statistically and computationally efficient learning. Broad topics will include: PAC-learning, uniform convergence, PAC-Bayesian, model selection; supervised learning algorithms including SVM, boosting, kernel methods; online learning algorithms, ranking algorithms, and analysis; unsupervised learning with guarantees.

Course Information

Required Texts

  1. [SB] Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014.

  2. [MRT] Mehryar Mohri and Afshin Rostamizadeh and Ameet Talwalkar, Foundations of Machine Learning, MIT Press, Second Edition, 2018.

  3. Please read the scribe notes for the first 10 sessions: Notes.

Optional Texts

  1. [KV] Michael Kearns and Umesh Virkumar Vazirani, An Introduction to Computational Learning Theory, MIT Press, 1994.

  2. [AB] Martin Anthony and Norman Biggs, Computational Learning Theory: An Introduction, Cambridge University Press, 1992.

Grading Policy

  1. 30%: Mid-term exam (1401/01/24).

  2. 30%: Final exam.

  3. 25%: Homeworks.

  4. 10%: Quiz.

  5. 10%: Paper & Project. Explore a theoretical or empirical question and present it. Deadline for choosing paper: 1401/02/01.

Lecture Schedule


Lecture Date Topics Related Readings and Links Homework & Assignments
1 1400-11-23Introduction: What is machine learning theory? Chapter 1 of MRT
Chapter 1 of SB
2 1400-11-25Formal model of learning and consistency model Section 2.1 of MRT
Chapter 6 of AB
3
4
1400-11-30
1400-12-02
PAC & Agnostic PAC
learning model
Sections 2.1 - 2.4 of MRT
Sections 3.1 & 3.2 & Chapter 4 of SB
5
6
1400-12-07
1400-12-09
Growth function
VC dimension
Rademacher complexity
Section 2.4 of MRT
Chapters 4 & 6 of SB
7
8
1400-12-14
1400-12-16
Nonuniform learning Chapter 7 of SB
9 1400-12-21Model selection Chapter 4 of MRT
Chapter 5 of SB
10 1399-01-25Computational complexity of learning Chapter 8 of SB
11
12
1401-01-15
1401-01-20
Analysis of support vector machine Chapter 5 of MRT
Section 9.1 and Chapter 15 of SB
13 1401-01-22Analysis of kernel methods Chapter 6 of MRT
Chapter 16 of SB
14
15
1401-01-27
1401-01-29
Analysis of Boosting Chapter 7 of MRT
Chapter 10 of SB
16
17
18
19
1401-02-05
1401-02-10
1401-02-12
1401-02-17
On-line learning Chapter 8 of MRT
Chapter 21 of SB
20
21
1401-02-19
1401-02-24
Ranking algorithms Chapter 9 of MRT
Chapter 21 of SB
22
23
1401-02-26
1401-02-31
Regression algorithms Chapter 11 of MRT
Chapter 11 of SB
24
25
1401-03-02
1401-03-07
Convex learning problemsChapters 12 and 14 of SB
26 1401-03-09PAC-Bayesian theory Chapter 31 of SB
27 1399-03-16Active learning
Theory of clustering
References in slides
Chapter 22 of SB