40718 Machine Learning Theory

Hamid Beigy, Sharif University of Technology, Spring Semester 2019-20.

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.

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 (1399/02/08).

  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: 1399/02/13.

Lecture Schedule


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