Notes for the master course Statistical Machine Learning (Prof. Dr. Ulrike von Luxburg, University of Tübingen, Summer Term 2026).
The course does not explain many algorithms. It explains the statistical principles that have to be in place so that machine learning works at all: what the best possible prediction is, when learning from a finite sample converges to it, how the complexity of the function class or the stability of the algorithm controls the gap between training and test error, and why modern overparameterized models still generalize. The last part is about machine learning in society: data and measurement, fairness, explainability and law.
Goal of the course
After this course, students should be able to:
- state the formal learning setup (risk, loss, Bayes classifier, consistency) and reason inside it
- derive and compare generalization bounds (finite classes, VC dimension, Rademacher complexity, stability)
- explain why regularization, bagging and boosting work, and when overparameterized models generalize
- compute and judge fairness criteria and explanations of real prediction systems
Lectures
| # | Lecture | Key concepts |
|---|---|---|
| 1.1 | Introduction and Decision Theory | inductive inference, loss and risk, Bayes classifier, regression function, maximum likelihood, MAP, cost-sensitive decisions |
| 1.2 | Learning from Finite Samples | consistency, plug-in classifier, empirical risk, ERM, estimation and approximation error, bias-variance decomposition, No Free Lunch |
| 2 | Perceptron Mistake Bound | perceptron as SGD on the linear loss, margin, mistake bound, leave-one-out generalization bound |
| 3 | Statistical Learning Theory | Hoeffding and McDiarmid, uniform convergence, finite classes, shattering coefficient, VC dimension, Sauer-Shelah, Rademacher complexity |
| 4 | Algorithmic Stability | uniform stability, stability implies generalization, ERM with strongly convex loss, stability of SGD |
| 5 | Regularization | least squares, ridge regression (Tikhonov), stability of regularized ERM, lasso and sparsity |
| 6 | Aggregation, Bagging and Boosting | bootstrap, bagging, random forests, AdaBoost, training and test error bounds, gradient boosting |
| 7 | Data, Measurement and Validity | measurement vs. construct, harms in data, features, kernels, random features, benchmarks, four notions of validity |
| 8 | Overparameterized Learning | double descent, implicit regularization, minimum norm solution, benign overfitting, why large models |
| 9.1 | Fairness | demographic parity, equalized odds, predictive parity, impossibility results, pre-, in- and post-processing |
| 9.2 | Explainability and Law | feature importance, SHAP, LIME, counterfactual explanations, EU AI Act, GDPR, copyright |
Lecture pages are linked here as soon as they are written.
Terms that appear in several lectures have their own short page under Concepts.
Find a topic
For looking something up later: which lecture and section explains a definition, a theorem or a task type. The table grows with every lecture.
| Topic | Where |
|---|---|
| Inductive bias, why learning needs assumptions | L1.1: Why should ML work at all? |
| Loss, true risk, Bayes risk, Bayes classifier | L1.1: Bayes risk and Bayes classifier |
| Regression function , Bayes classifier for the 0-1 loss (Theorem 2), Bayes error | L1.1: Explicit Bayes classifier |
| Hinge, exponential, logistic loss and their Bayes predictors | L1.1: Bayes predictors for various losses |
| Squared loss: is optimal, Bayes risk | L1.1: Regression under the squared loss |
| ML, MAP, Bayes decision rule with costs | L1.1: Bayes decision rule |
| Exam task: decision boundaries from a density diagram, prior or costs backwards | L1.1: Reading decision boundaries off a diagram |
| Consistency, universal consistency, Stone’s kNN theorem | L1.2: Consistency |
| Convergence in probability, almost surely, in | L1.2: Convergence of random variables |
| Empirical risk, law of large numbers for a fixed function | L1.2: Proposition 6 |
| ERM and the counterexample where it fails | L1.2: Is ERM always successful? |
| Estimation vs. approximation error, over- and underfitting | L1.2: Estimation and approximation error |
| Classical vs. modern regime, double descent | L1.2: Modern regime |
| Bias-variance decomposition (squared loss) | L1.2: Bias-variance |
| No Free Lunch theorem | L1.2: Propositions 7 to 9 |
| Perceptron algorithm, perceptron by hand (exam worksheet) | L2: The perceptron by hand |
| Distance to a hyperplane, margin | L2: Margin |
| Mistake bound (Novikoff) and its proof | L2: Theorem 1 |
| Test error of the perceptron, leave-one-out, fast rate | L2: Theorem 2 |
| Hoeffding and McDiarmid, error of a fixed function, samples | L3: Error of a fixed function |
| Uniform convergence, Vapnik-Chervonenkis theorem | L3: Uniform convergence |
| Finite classes, union bound, sample sizes | L3: Finite classes |
| Shattering coefficient, symmetrization, growth function rules | L3: Growth function |
| Exam task: VC dimension from a growth function table | L3: Growth function tables |
| VC dimension, Sauer-Shelah, VC bound | L3: Sauer-Shelah |
| VC of linear, margin and neural network classifiers | L3: Linear classifiers |
| Rademacher complexity, summary of all bounds | L3: Summary of bounds |
| Average and uniform stability, generalization gap = average stability | L4: Proposition 1 |
| Uniform stability bound, which rates work () | L4: Which rates are good enough? |
| Exam task: stability rate table (yes/no) | L4: Stability rates |
| Strong convexity, ERM is stable with | L4: Theorem 3 |
| Smoothness, stability of GD and SGD, early stopping | L4: Stability of GD |
How to read these notes
Every lecture page has the same structure: a short TL;DR, the content in the order of the slides, small worked examples, exam-style tasks, a self-test and links to related lectures. The table of contents on the right follows the slide sections. Small labels like Slides 12-15 say where a topic is in the original slides. The notation is the lecturer’s: is the true risk, the empirical risk, the Bayes classifier.
Callouts mark what matters most:
Definition
The exact meaning of a term.
Key formula or theorem
Formulas and statements you should know.
Intuition
Why something works, in plain words.
Proof
The proof from the slides, step by step. Click to open.
Common mistake
Typical misunderstandings and wrong exam answers.
Exam relevance
What was asked in the exam or is likely to be asked.
Exam-style task
A task in the format of the real exam: a table or a small data set, then (a) easy, (b) harder, (c) transfer.
Solution
The worked solution with points per part. Try the task first.
Self-test question
Answer
Click to reveal.
Figures marked Interactive are visualizations made for these notes. Move the sliders or click through the steps to see how a method behaves.
Course organization
| Lecturer | Prof. Dr. Ulrike von Luxburg |
| Tutorials | weekly, attendance of at least 9 of 12 tutorials is needed for the exam admission |
| Assignments | one sheet per week, handed in by teams of two; at least 50% of the points on average are needed for the exam admission |
| Grading | the final exam determines the grade |
| Exam | 120 minutes, one A4 page (one side) of handwritten notes allowed |
| Exam dates | 28 July 2026 and 8 October 2026 |
| Course page | https://www.tml.cs.uni-tuebingen.de/teaching/2026_sml/index.php |
- Exam format: 7 tasks with 4 points each. Task 1 is multiple choice with exactly one correct answer per question. Tasks 2 to 7 have three parts each: (a) an easy computation or reading off a table, (b) a computation plus a check or an interpretation, (c) a transfer question, a construction or reasoning backwards. Most tasks start from a table or a small toy data set. No points are lost for wrong multiple choice answers.
- The info sheet says that exam tasks are similar to the homework assignments, so the assignment sheets are good practice.
Requirements: linear algebra, multivariate analysis, probability theory, statistics and optimization (for example from Mathematics for Machine Learning), Python, and an introductory machine learning course.
Literature: