Spring 2021 (weeks 6 - 21). Lectures on Thursday 10:15-13:00 held online.
Machine learning is one of the fastest growing areas of science, with far-reaching applications. In this course we focus on the fundamental ideas, theoretical frameworks, and rich array of mathematical tools and techniques that power machine learning. The course covers the core paradigms and results in machine learning theory with a mix of probability and statistics, combinatorics, information theory, optimization and game theory.
During the course you will learn to
This course strongly focuses on theory. (Good applied master level courses on machine learning are widely available, for example here, here and here). We will cover statistical learning theory including PAC learning, VC dimension, Rademacher complexity and Boosting, as well as online learning including prediction with expert advice, online convex optimisation, bandits and reinforcement learning.
This course is offered as part of the MasterMath program. To participate for credit, sign up here. We use the MasterMath ELO for submitting homework, and receiving grades. We use the MasterMath Zulip MLTs21 stream as our forum. Sign up instructions are here.
The prerequisites are
as covered e.g. in any bachelor mathematics program in the Netherlands, and as reviewed in the Appendix of the book [1]. The course does require general 'mathematical maturity', in particular the ability to combine insights from all three fields when proving theorems.
We offer weekly homework sets whose solution requires constructing proofs. This course will not include any programming or data.
The grade will be composed as follows.
The average of midterm and final exam grades has to be at least 5.0 to pass the course.
It is strongly encouraged to solve and submit your weekly homework in small teams. Exams are personal.
There will be a retake possibility for either/both exams, which are 60% of the grade.
When | What | Lect. | TA |
Thu 11 Feb | Introduction. Statistical learning. Halfspaces. PAC learnability for finite hyp. classes, realizable case. Chapters 1 and 2 in [1] | Tim | N/A |
Thu 18 Feb | PAC learnability for finite hyp. classes, agnostic case. Uniform convergence. Chapters 3 and 4 in [1]. | Tim | Jack |
Thu 25 Feb | Infinite classes. VC Dimension part 1. Chapter 6.1-6.3 in [1]. | Tim | Sarah |
Thu 4 Mar | VC Dimendion part 2. Fundamental theorem of PAC learning. Sauer's Lemma. Chapter 6 in [1]. | Tim | Hédi |
Thu 11 Mar | Proof of Fund.Th of PAC Learning. Rademacher Complexity part 1. Section 28.1 in [1] | Tim | Jack |
Thu 18 Mar | Nonuniform Learnability, SRM, Other notions of Learning. Sections 7.1 and 7.2 in [1] (note the errata about this chapter). Rademacher Complexity part 2. Chapter 26 in [1]. | Tim | Sarah |
Thu 25 Mar | Double descent. Generalisation despite zero training loss. This material is not part of either exam. | Tim | Hédi |
Thu 1 Apr | Midterm exam on material covered in lectures 1-6. | ||
Thu 8 Apr | Full Information Online Learning (Experts). Slides | Wouter | Jack |
Thu 15 Apr | Bandits. UCB and EXP3. Slides and Chapters 2.2 and 3.1 in [3] | Wouter | Sarah |
Thu 22 Apr | Online Convex Optimization. Slides and Sections 3.1 and 3.3 in [2]. | Wouter | Hédi |
Thu 29 Apr | Exp-concavity. Online Newton Step. Slides and Chapter 4 in [2]. | Wouter | Jack |
Thu 6 May | Boosting. AdaBoost. Slides and Chapter 10 in [1] | Wouter | Sarah |
Thu 13 May | No class (ascension day) | ||
Thu 20 May | Log-loss prediction. Normalised Maximum Likelihood. Slides and book chapter on ELO. | Wouter | Hédi |
Thu 27 May | Reinforcement Learning. Slides This material is not part of the exam. | Wouter | Jack |
Thu 10 Jun | Final exam | ||
Thu 1 Jul | Retake exam(s) |
The dependency graph of the online learning component of the course
If below we say "algorithm and regret bound" we might question you on the setting, its main algorithm and (do computations involving) the corresponding regret bound. If we add "analysis" you should be able to reprove the regret bound at the exam.
We will not ask you details about the material for the first half of the class. We will also not ask you about the final lecture about reinforcement learning.
We will make use of the following sources