Machine Learning Theory - M1 - 8EC

1) Prerequisites
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 course book [1]. The course does require general 'mathematical maturity', in particular the ability to combine insights from all three fields when proving theorems.

2) Aim of the course
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 optimization, bandits and reinforcement learning.

3) Rules about Homework/Exam
We provide weekly homework sets. Even sets are for practice. Odd sets are graded and must be handed in before the next lecture.
The grade will be composed as follows.

  • 30%: odd homework sets to be handed in biweekly.
  • 35%: written mid-term exam.
  • 35%: written final exam.

The average of midterm and final exam grades has to be at least 5.0 to pass the course.
There will be a retake possibility for either or both exams. The homework still counts as part of the grade after the retake.
It is allowed and strongly encouraged to solve and submit the homework in small teams. Exams are personal.
NB Collaboration on homework is only allowed within a team. In particular, solutions may

  • not be copied from the web, math exchange, stack overflow, ...
  • not be copied from other teams
  • not be from the instructors manual
  • not be generated by AI (e.g. ChatGPT)

When using any source that is not on the official literature list, always cite the source.

4) Lecture notes/Literature
The first half of the course will use slides posted on the ELO and the free book

[1] Understanding Machine Learning: From Theory to Algorithms by Shai Shalev-Shwartz and Shai Ben-David.

The second half of the course will use slides posted on the ELO.
5) Lecturers
Wouter Koolen, CWI and UT
Tim van Erven, UvA