Machine Learning Theory

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

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

Formalize learning problems in statistical and game-theoretic settings.
Examine the statistical complexity of learning problems using the core notions of complexity.
Analyze the statistical efficiency of learning algorithms.
Master the design of learning strategies using proper regularization.

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, and receiving grades. We use the MasterMath Zulip MLTs21 stream as our forum. Sign up instructions are here.

Prerequisites

The prerequisites are

Basic probability theory (in particular conditional probability, expectations, discrete and continuous distributions, Markov's and Hoeffding's inequalities)
Basic linear algebra (finite dimensional vector spaces, positive definite matrices, singular value decomposition)
Basic calculus (differentiation and minimisation of multivariate convex functions)

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

The lectures will be held live on zoom, and will be recorded. The zoom link and video archive link will be posted on the ELO. The Thursday 3h slot will consist of 2h of lectures followed by a 1h TA session discussing the homework.

Mode

The grade will be composed as follows.

40%: weekly homework to be handed in before the next lecture.
30%: mid-term exam.
30%: final exam.

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	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

Exams

Final

The final exam will test you on the online learning component of the class. Below is the list of topics. The weekly homework prepares you for the exam.

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.

Topics

Experts
- Mix loss game, lower bound, Aggregating algorithm regret bound and analysis
- Dot loss game, Hedge algorithm regret bound and analysis
Bandits
- Stochastic bandit setting. UCB algorithm, regret bound.
- Adversarial bandit setting. EXP3 algorithm, regret bound.
Online Convex Optimisation
- Convex losses, Online Gradient Descent regret bound and analysis.
- Strongly convex losses, Online Gradient Descent regret bound and analysis.
- Exp-concave losses, Online Newton Step regret bound, without analysis.
Boosting
- Weak learning definition, relation to strong learning.
- AdaBoost algorithm, bound on empirical risk, analysis.
- VC dimension of boosting output hypothesis, without analysis.
- You may skip the material on implementing ERM for decision stumps (10.1.1) and face recognition (10.4).
Log-Loss Prediction:
- Minimax regret/stochastic complexity, and Bayesian predictors for Bernoulli regret bounds.

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.

Material

We will make use of the following sources

[1] Understanding Machine Learning: From Theory to Algorithms by Shai Shalev-Shwartz and Shai Ben-David. See here for errata.
[2] Introduction to Online Convex Optimization by Elad Hazan.
[3] Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems by Sébastien Bubeck and Nicolò Cesa-Bianchi.