40718 Machine Learning Theory

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

• Instructor: Hamid Beigy

• Teaching Assistants: Heydar Soudani, Pooya Moieni, Hossein Mojab

• Time and Location: Saturday/Monday: 10:30 am -12:00 am, virtual class

• Contact: Please contact the teaching staffs on Piazza site.

• Course page: Also check the course page on CE.

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