Textbook of AI

Also known as: SLT

Statistical learning theory (SLT) is the mathematical theory of supervised learning from finite samples, founded by Vladimir Vapnik and Alexey Chervonenkis at the Moscow Institute of Control Sciences in the 1960s and 70s. The central question: under what conditions does empirical risk minimisation (choosing the hypothesis with smallest training error) approximate true risk minimisation (choosing the hypothesis with smallest expected error on unseen data)?

The framework's central tools are uniform convergence bounds: probabilistic guarantees that, with high probability, the empirical risk of the chosen hypothesis is close to its true risk uniformly over the entire hypothesis class. The VC dimension characterises when such bounds hold and gives explicit rates: for a class of VC dimension d trained on m examples, sup_{h ∈ H} |R(h) − R̂(h)| = O(√(d log m / m)) with high probability.

Structural risk minimisation (SRM) uses such bounds to guide model selection: choose the model class that minimises a sum of empirical risk and a capacity-based complexity penalty. SRM provides one of the cleanest theoretical accounts of the bias–variance trade-off.

SLT is contrasted with the PAC learning framework of Leslie Valiant (1984), which approaches the same questions from a more computational angle: a class is PAC-learnable if there exists a polynomial-time algorithm that, with high probability, returns a hypothesis with low error. The two frameworks have largely converged.

Modern overparameterised neural networks pose deep puzzles for classical SLT, they routinely have VC dimension exponentially larger than the training set yet generalise well. The double-descent phenomenon (Belkin et al., 2019) and interpolation regime analyses are recent attempts to extend SLT to this setting.