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

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.

This course is offered as part of the MasterMath program. We use the MasterMath ELO for submitting homework, and receiving grades.

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.

- Wouter M. Koolen (CWI)
- Tim van Erven (UvA)

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.

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.