the mathematics of whether machines can learn Statistical Learning Theory

The fundamental question of machine learning is not "can a model fit the training data?" — any sufficiently complex model can memorize any finite dataset. The question is: can a model trained on a finite sample perform well on unseen data drawn from the same distribution? Statistical Learning Theory is the mathematical framework that makes this question precise and answers it rigorously.

Empirical Risk Minimization (ERM) is the most natural learning algorithm: simply find the hypothesis in \(\mathcal{H}\) that minimizes the training error. Its mathematical justification — and the conditions under which it provably works — are the heart of classical learning theory.

Uniform convergence is the mathematical property that makes ERM work: if the empirical risk converges to the population risk uniformly over the entire hypothesis class, then minimizing the empirical risk provably minimizes the population risk.

Hoeffding's inequality (covered in depth in the Probability Theory masterclass) is the concentration inequality that underlies most sample complexity bounds in learning theory. Combined with the union bound, it provides the first rigorous guarantee for ERM over finite hypothesis classes.

VC dimension extends the learnability analysis to infinite hypothesis classes by replacing the explicit size \(|\mathcal{H}|\) with a geometric measure of the class's combinatorial richness: its ability to "shatter" finite sets of points.

While VC dimension is a fixed property of a hypothesis class, Rademacher complexity is data-dependent — it measures the ability of a hypothesis class to fit random noise on the specific sample at hand. This leads to strictly tighter generalization bounds, and applies naturally to real-valued function classes (not just binary classifiers).

PAC (Probably Approximately Correct) learning, introduced by Leslie Valiant in 1984, is the formal framework that makes "learning" a precise mathematical concept — defining what it means for an algorithm to "learn" a concept class in terms of provable sample complexity guarantees.

Given the VC bound — that generalization improves when using simpler (lower VC dimension) hypothesis classes — how should one choose among multiple possible classes? Structural Risk Minimization (SRM) formalizes the model selection problem.

Regularization — adding a penalty on hypothesis complexity to the empirical risk — is the practical implementation of the SRM principle. Learning theory provides the exact justification for every regularizer used in practice.

In 2017, Zhang, Bengio, Hardt, Recht & Vinyals published a paper whose central observation caused a crisis in classical learning theory. They demonstrated, with a series of controlled experiments, that the most widely-used theoretical tools for explaining generalization cannot explain the behavior of modern neural networks.

Double descent (introduced in the DL Optimization masterclass from a training-dynamics perspective) has an equally important learning-theoretic interpretation: it reveals that the classical bias-variance U-curve is not wrong — it is simply incomplete, applying only below the interpolation threshold.

Several modern theoretical frameworks provide partial explanations for why deep networks generalize, each capturing a different aspect of the training-and-generalization story. None is complete, but each reveals something genuine.

Statistical learning theory is one of the most intellectually active areas of ML research precisely because it has the hardest open questions. Each of the following problems has significant practical importance and remains mathematically unresolved:

• Non-vacuous generalization bounds for large language models. PAC-Bayes gives non-vacuous bounds for MNIST-scale networks. For GPT-3 or GPT-4 scale (10^11 parameters), no known theoretical tool gives a bound less than 1. This is not a limitation of current proofs — it may require entirely new mathematics.
• Why does in-context learning work, and what does it memorize vs generalize? Large language models "learn" from examples in their prompt without weight updates — a phenomenon entirely outside the classical IID learning framework. Bayesian and kernel perspectives provide partial intuitions (Attention masterclass, §09) but no tight theory.
• The role of data distribution in double descent. Current double descent theory assumes Gaussian features. For realistic data distributions (images, text), the exact form of the double descent curve and the conditions under which it occurs are not well-understood.
• Benign vs malignant overfitting — when does interpolation help or hurt? The conditions under which minimum-norm interpolation generalizes well (benign overfitting, §06) vs causes catastrophic generalization failure are known only for Gaussian linear models. For nonlinear models and realistic data, the boundary is unknown.
• Generalization of transformers. The attention mechanism's unique computational properties — content-addressable memory, in-context learning, quadratic interactions between tokens — are not captured by any existing complexity measure. A theory of transformer generalization would be one of the most important advances in the field.
• The implicit regularization of Adam. Gradient descent on linear models converges to the max-margin / min-norm solution. What is the corresponding implicit bias of Adam (the optimizer used to train virtually all large models in practice)? This question is open even for linear models.

The complete argument, stated precisely:

1. The fundamental problem is the generalization gap: we observe the empirical risk but care about the population risk. All of learning theory is about bounding this gap.
2. ERM minimizes the empirical risk. It is consistent — provably converges to the best hypothesis in \(\mathcal{H}\) — and its error decomposes into approximation error (bias, determined by \(\mathcal{H}\)) and estimation error (variance, determined by \(n\)).
3. Uniform convergence is the bridge: if the empirical risk converges to the population risk uniformly over all of \(\mathcal{H}\), then minimizing the empirical risk minimizes the population risk. Hoeffding's inequality plus the union bound gives the first quantitative bound, scaling as \(\sqrt{\log|\mathcal{H}|/n}\) for finite classes.
4. VC dimension extends this to infinite classes: \(\text{VCdim}(\mathcal{H}) < \infty \iff\) PAC-learnable \(\iff\) uniform convergence holds. The generalization gap scales as \(\sqrt{d/n}\) where \(d\) is the VC dimension — a combinatorial measure of \(\mathcal{H}\)'s richness.
5. Rademacher complexity gives tighter, data-dependent bounds and applies to real-valued function classes. Norm-bounded linear classifiers have Rademacher complexity scaling as \(B/\sqrt{n}\) — norm, not parameter count, is the right complexity measure.
6. SRM and regularization formalize the bias-variance tradeoff: choose the hypothesis class (or regularization strength) that minimizes the upper bound on population risk. Every practical regularizer has a learning-theoretic justification as a complexity control.
7. The deep learning paradox shatters the classical framework: neural networks memorize random labels, have vacuous VC bounds, yet generalize beautifully on real data. Classical theory cannot distinguish these cases.
8. Modern theory — PAC-Bayes (flatness = compressibility), algorithmic stability, NTK — provides partial explanations, but no complete theory exists for why deep networks at scale generalize as they do. The open problems in §13 are not gaps to be plugged — they represent the frontier where new mathematics must be invented.