Machine Learning: Theory and Algorithms (MALTA), 2023-2024
The course introduces the mathematical foundations of machine learning.
Its first goal is to formalize the main questions behind machine learning: What is learning? How can a machine learn? Is learning always possible? How do we quantify the resources needed to learn?
To this purpose, the course presents the probably-approximately correct (PAC) learning paradigm.
Its second goal is to present several key machine learning algorithms and show how they follow from general machine learning principles.
The course has a theoretical focus, and the student is assumed to be comfortable with basic notions of probability, linear algebra, analysis, and algorithms.
Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, available here.
There are also video lessons from Shai Ben-David, and lecture notes from Shai Shalev-Shwartz (together with videos in Hebrew if you prefer it to English).
Evaluation
30% classwork (a 10-minute test at every lesson, only 5 best marks will be considered), 30% a mid-course assignement, 40% final exam.
Lessons
Lessons will be on Fridays from 13.30 to 16.30 in B208 Templiers, unless otherwise specified.
For each lesson, the corresponding sections of the book are indicated and the corresponding videos of Shai Ben-David's course are listed.
First lesson (September 15): introduction, what is machine learning, when it should be used, and how it relates to statistics, artificial intelligence, and computer science,
types of learning (supervised, unsupervised, reinforcement, active vs passive learners, helpfulness of the teacher, online vs batching),
[chapter 1, video lecture 1 up to 1:07:00];
formal model for learning, empirical and expected loss, empirical risk minimization, introduction to PAC learnability,
proof that a finite class is PAC-learnable [chapter 2, videos lectures 1, 2, and 3 up to 0:27:45],
formal definition of PAC learnability and agnostic PAC learnability [chapter 3, videos lecture 3 and lecture 4 up to 0:56:35].
Second lesson (September 22):
there exists a PAC-learnable class with infinite size (proof postponed after the fundamental theorem of statistical learning) [section 6.1, video lecture 6 up to 0:52:50],
the no-free-lunch theorem [section 5.1, video for lecture 8 up to 0:46:00],
the need for inductive bias,
uniform convergence [section 4.1, video lecture 4],
uniform convergence is sufficient for agnostic PAC learnability, finite classes have the uniform convergence property [sections 4.1-4.2, video lecture 5],
the fundamental theorem of statistical learning [section 6.4, videos lecture 8 from 0:57:31 up to 1:11:54 and lecture 9 from 1:01:41],
VC-dimension [sections 6.2-6.3, video lecture 7].
Third lesson (September 29): quantitative version of the fundamental theorem,
bias-complexity tradeoff [section 5.2, video lecture 6 from 1:15:14],
computational complexity of learning algorithms [chapter 8],
convex learning problems [chapter 12].
Fourth lesson (October 6, taught by Othmane Marfoq):
linear predictors [section 9.1, video lecture 8 from 1:11:54]
Fifth lesson (October 13):
linear regression [section 9.2],
logistic regression and surrogate functions [sections 9.2 and 12.3],
Lipschitzness, smoothness and learnability of convex problems [chapter 12 starting from section 12.1.2]
Sixth lesson (October 20):
regularization and stability [chapter 13],
introduction to boosting (decision stumps: their linear combination and efficient implementation of ERM) [sections 10.1.1 and 10.3]
section 12.1.1, beginning of section 12.2, sections 12.3, 9.2, 9.3, videos for lectures 19 (from 0:57:43), 20, 21, and 22 (you can skip between 0:14:30 and 0:48:20).
Seventh lesson (October 27):
adaboost [sections 10.2 and 10.4, videos lecture 18 (from minute 38) and 19],
model selection and validation [chapter 11],
neural networks [chapter 20].
Assignment
12/10 Students organize themselves in groups of 4 people.
13/10 Each group is tasked with 1) preparing lecture notes for a hypothetical 1.5-hour lecture on their assigned topic, and 2) reviewing the lecture notes of another group.
29/10 Deadline to send the lecture notes in pdf format to the teacher and to the reviewing group.
3/11 Deadline to send the review to the teacher.
Lecture notes will count for 70% of the assignment mark, reviews for 30%.
Evaluation criteria for the lecture notes: 1) clear definition of the questions the lecture is addressing, 2) adaptation of the content to the target duration, 3) links to the course lectures, 4) correctness, 5) clarity.
Review format: grade the lecture notes (/20) according to the criteria above and motivate your grades, write suggestions to improve the lecture notes.
Evaluation criteria for the reviews: quality of the comments and suggestions, mismatch between the proposed grades and the teacher grades.
At the exam, each student will need to answer a question on both topics.
Exam
The exam will be on November 10th in room E302, Templiers, from 13.30 to 16.30.
Last modified: 7 November, 2023