Machine Learning Theory

Spring 2021 (weeks 6 - 21). Lectures on Thursday 10:15-13:00 held online.

Aim | Prerequisites | Lecturers | Mode | Schedule | Material

Aim

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.

MasterMath Website

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, forum discussions, and receiving grades.

Prerequisites

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.

Lecturers

Mode

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.

Preliminary Schedule

When What Who
Thu 11 Feb Introduction. Statistical learning. Halfspaces. PAC learnability for finite hyp. classes, realizable case. Chapters 1 and 2 in [1] Tim
Thu 18 Feb PAC learnability for finite hyp. classes, agnostic case. Uniform convergence. Chapters 3 and 4 in [1]. Tim
Thu 25 Feb Infinite classes. VC Dimension part 1. Chapter 6.1-6.3 in [1]. Tim
Thu 4 Mar VC Dimendion part 2. Fundamental theorem of PAC learning. Sauer's Lemma. Chapter 6 in [1]. Tim
Thu 11 Mar Proof of Fund.Th of PAC Learning. Nonuniform Learnability, SRM, Other notions of Learning. Chapter 7 in [1]. Tim
Thu 18 Mar Rademacher Complexity. Chapters 26 in [1]. Tim
Thu 25 Mar Double descent. Generalisation despite zero training loss Tim
Thu 1 Apr Midterm exam
Thu 8 Apr Full Information Online Learning (Experts). Wouter
Thu 15 Apr Bandits. UCB and EXP3. Chapters 2.2 and 3.1 in [3] Wouter
Thu 22 Apr Online Convex Optimization. Sections 3.1 and 3.3 in [2] Wouter
Thu 29 Apr Exp-concavity. Online Newton Step. Wouter
Thu 6 May Boosting. AdaBoost. Margin theory. Chapter 10 in [1] Wouter
Thu 13 May Log-loss prediction. Normalised Maximum Likelihood. Non-parametric classes Wouter
Thu 20 May Reinforcement Learning Wouter
Thu 27 May Bonus (topic tbd) Wouter
Thu 10 Jun Final exam
Thu 1 Jul Retake exam(s)

The dependency graph of the online learning component of the course

graph

Material

We will make use of the following sources