Statistical Learning Theory
Empirical risk minimisation, uniform convergence, VC dimension, Rademacher complexity and PAC guarantees.
Level 3 — Graduate
- Empirical Risk Minimisation and Uniform Convergence16 min
Why minimising training error can work, why it needs a uniform bound, and the finite-class and PAC guarantees that follow.
Excess risk decomposition for ERMGeneralisation bound for a finite hypothesis classFaster rate in the realizable case - VC Dimension, Sauer's Lemma and Rademacher Complexity18 min
The two standard measures of a hypothesis class's capacity, with complete proofs of Sauer's lemma and the Rademacher generalisation bound.
Shattering, growth function and VC dimensionSauer–Shelah lemmaVC generalisation bound - Bias–Variance, Interpolation and Double Descent7 min
The exact decomposition, the classical U-curve, the second descent past the interpolation threshold, and what is proved about each.
The bias–variance decomposition is an identityThe bias–variance trade-offDouble descent for minimum-norm linear regression
Problems (16)
Open in the browser| Solved | Problem | Type | Difficulty | Time |
|---|---|---|---|---|
| Generalisation for a finite class | Proof | 30 min | ||
| The bias–variance decomposition is an identity | Proof | 15 min | ||
| The excess risk decomposition for ERM | Proof | 15 min | ||
| Gradient descent finds the minimum-norm interpolator | Proof | 30 min | ||
| The fast rate in the realizable case | Proof | 30 min | ||
| VC dimension of halfspaces | Proof | 30 min | ||
| A one-parameter class with infinite VC dimension | Proof | 1 hour | ||
| Massart's finite maximal inequality | Proof | 30 min | ||
| Rademacher complexity of a norm-bounded linear class | Proof | 30 min | ||
| Reproduce double descent run | Coding | 3 hours | ||
| The interpolation peak is a conditioning phenomenon | Proof | 30 min | ||
| The no-free-lunch theorem | Proof | 1 hour |