Learning Theory from First Principles

Francis Bach

Mastere MASH 2023/2024


Mandatory registration

The class will be taught in French or (most probably) English, depending on attendance (all slides and class notes are in English).



The goal of this class is to present old and recent results in learning theory, for the most widely-used learning architectures. This class is geared towards theory-oriented students as well as students who want to acquire a basic mathematical understanding of algorithms used throughout the masters program.

A particular effort will be made to prove many results from first principles, while keeping the exposition as simple as possible. This will naturally lead to a choice of key results that show-case in simple but relevant instances the important concepts in learning theory. Some general results will also be presented without proofs.

The class will be organized in eight three-hour sessions, each with a precise topic. See tentative schedule below. Credit: 5 ECTS.

Prerequisites: We will prove results in class so a good knowledge of undergraduate mathematics is important, as well as basic notions in probability. Having followed an introductory class on machine learning is beneficial.


All classes will be "in real life" at ENS (29, rue d'Ulm), on Friday between 9am and 12pm, in the room Paul Langevin (1st floor)

The class will follow the book in preparation (draft available here, since it will be updated frequently, please get the latest version).

Each student will benefit more from the class if the corresponding sections are read before class.



Book chapters

October 6

Learning with infinite data (population setting)
-Decision theory (loss, risk, optimal predictors)
-Decomposition of excess risk into approximation and estimation errors
-No free lunch theorems
-Basic notions of concentration inequalities (MacDiarmid, Hoeffding, Bernstein)

Chapter 2

October 13

Linear Least-squares regression
-Guarantees in the fixed design settings (simple in closed-form)
-Ridge regression: dimension independent bounds
-Guarantees in the random design settings
-Lower bound of performance

Chapter 3

October 20

Empirical risk minimization
-Convexification of the risk
-Risk decomposition
-Estimation error: finite number of hypotheses and covering numbers
-Rademacher complexity
-Penalized problems

Chapter 4

November 3

Optimization for machine learning
-Gradient descent
-Stochastic gradient descent
-Generalization bounds through stochastic gradient descent

Chapter 5

November 10

Local averaging techniques
-Partition estimators
-Nadaraya-Watson estimators
-Universal consistency

Chapter 6

November 17

Kernel methods
-Kernels and representer theorems
-Analysis of well-specified models
-Sharp analysis of ridge regression
-Universal consistency

Chapter 7

November 24

Model selection
-L0 penalty
-L1 penalty
-High-dimensional estimation

Chapter 8

December 8

Neural networks
-Single hidden layer neural networks
- Estimation error
- Approximation properties and universality

Chapter 9

December 15




One written in-class exam.

The draft book is almost finished, and I am still looking for feedback (typos, unclear parts). Please help! (with some bonus in the final grade).