Machine Learning: Theory and Algorithms (MALTA), 2024-2025
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. Up to one extra point for solving the optional exercises given at the end of the lecture.
Lessons
Lessons will be on Fridays from 13.30 to 16.30 in B104 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 13): 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 20):
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 and its quantitative version [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 27, E309):
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 4, taught by Samir Perlaza):
linear predictors [section 9.1, video lecture 8 from 1:11:54],
linear regression [section 9.2].
Fifth lesson (October 11, taught by Samir Perlaza):
logistic regression and surrogate functions [sections 9.2 and 12.3],
introduction to boosting (decision stumps: their linear combination and efficient implementation of ERM) [sections 10.1.1 and 10.3],
adaboost [sections 10.2 and 10.4, videos lecture 18 (from minute 38) and 19].
Sixth lesson (October 18):
Lipschitzness, smoothness and learnability of convex problems [chapter 12 starting from section 12.1.2]
regularization and stability [chapter 13],
Seventh lesson (October 25):
model selection and validation [chapter 11],
neural networks [chapter 20].
Assignment
Exam
The exam will be on November 8 in room E309, Templiers, from 13.30 to 16.30.
