The Johnson–Lindenstrauss Lemma
You can project n points into O(log n / eps^2) dimensions and keep every distance. The theorem underneath every vector database.
Machine-Learning
Why the Generalization Bounds Are Vacuous
PAC learning and VC dimension's bounds predict that an overparameterized network cannot generalize, and it generalizes anyway.
No Free Lunch
Averaged over all problems under a uniform measure — a distribution no real task is drawn from — every learner ties.
The Bias–Variance Decomposition
Error splits into three terms, one of which is irreducible. Still the right first diagnosis of a bad model.
PAC Learning and VC Dimension
How much data you need is a function of hypothesis-class complexity, not of the data. Generalization, made a theorem.
Minimum Description Length and Occam's Razor
Simplicity, formalized as compression; the bridge from information theory to model selection in PAC learning and VC dimension.