Start by conceding two impossibilities: you see only finitely many samples, so you might always draw an atypical batch; and even with a typical batch you will not be exactly right. Valiant's 1984 compromise is brutally practical — define "learned" as Probably (with high chance) Approximately Correct (with small error). Two tolerances: $\varepsilon$ lets you be a little wrong, $\delta$ lets you be unlucky once.
Here is an example you can compute end to end. The target is an axis-aligned rectangle in the plane, and the algorithm is trivial: take the smallest rectangle enclosing all positive examples. It can only under-shoot, never over-shoot, so all the error hides in four thin strips just inside the true rectangle's edges. If one strip carries probability mass above $\varepsilon/4$ and yet none of the $m$ samples landed in it, that bad event has probability $(1-\varepsilon/4)^m$; a union bound over the four strips gives $4e^{-m\varepsilon/4}\le\delta$, hence $m\ge\frac{4}{\varepsilon}\ln\frac{4}{\delta}$. "I have learned it" has been translated into a piece of arithmetic about sample size.
$D$ is the unknown true distribution behind the data; $S$ is $m$ samples drawn independently from $D$; $\hat h$ is the hypothesis the algorithm returns after seeing $S$; $\mathrm{err}_D$ is its error rate on the real world. The outer $\Pr$ governs luck in sampling, the inner $\varepsilon$ governs precision — two layers of uncertainty, one dial each. Learnable means: there is an algorithm whose sample size $m(\varepsilon,\delta)$ is polynomial in $1/\varepsilon$ and $1/\delta$.
It turns "learning," a philosopher's word, into a provable proposition — and exposes the structure of the price along the way: $\varepsilon$ appears as $1/\varepsilon$, but $\delta$ appears only as $\ln(1/\delta)$. Precision is expensive, confidence is cheap. Driving your failure rate from 5% to 0.001% costs a few times more data; halving your error costs double or worse. That asymmetry explains why "run it a few more times to confirm" is a bargain in engineering while "one more order of magnitude of accuracy" never is. And it is distribution-free.
PAC is the shared language of active learning, bandit sample complexity (Day 54), and differential-privacy budget analysis. Boosting was born from a question posed inside the framework: does weak learnability (barely better than a coin flip) imply strong learnability? Schapire proved in 1990 that it does; AdaBoost and XGBoost are constructive byproducts of that proof. Asking how many samples an A/B test needs is still asking for the same $m(\varepsilon,\delta)$.
How do you measure how "powerful" a model family is? Don't count parameters — count how many points it can shatter. Given $d$ points, if for every one of the $2^d$ ways of labelling them $\pm$ some member of the family fits perfectly, the family shatters those points. The largest such $d$ is the VC dimension.
Lines in the plane: take any 3 non-collinear points and all 8 labellings are linearly separable. Four points? Place them as a square with equal signs on the diagonals — that is XOR, and no line can do it. So a planar linear classifier has VC dimension exactly 3; in $d$ dimensions it is $d+1$.
Meanwhile $\mathrm{sign}(\sin\theta x)$ has a single parameter and infinite VC dimension. There is no reliable exchange rate between parameter count and capacity.
$\mathcal H_{|S}$ is the set of labelling patterns the class $\mathcal H$ can actually produce once restricted to the point set $S$ — two functions that label $S$ identically count as one pattern. So $|\mathcal H_{|S}|=2^d$ says "all $2^d$ patterns, none missing."
The real theorem is the Sauer–Shelah lemma: if $\mathrm{VC}(\mathcal H)=d$, the number of patterns on any $m$ points is $\le\sum_{i=0}^{d}\binom{m}{i}=O(m^d)$. A quantity that could have been $2^m$ collapses to a polynomial in $m$ the moment the VC dimension is finite — and the transition happens exactly at $m=d$.
This is a purely combinatorial dichotomy. One expects "complexity" to be continuous, graded, hard to pin down; Sauer–Shelah says a function class has only two fates — shatter everywhere ($2^m$, infinite VC, unlearnable) or be pinned by a single integer $d$ to $O(m^d)$. There is no middle ground. More striking still, the lemma was discovered independently three times: in extremal combinatorics, in Shelah's stability theory (NIP) in model theory, and in the $\varepsilon$-net theorem of discrete geometry. Three groups who never spoke hit the same wall — usually a sign they were touching the same structure.
This is where the SVM gets its theoretical licence: kernels lift data to infinite dimension with infinitely many parameters, yet the max-margin constraint bounds the effective VC dimension by $(R/\gamma)^2$ ($R$ the data radius, $\gamma$ the margin), independent of the ambient dimension — the first elegant proof that the curse of dimensionality can be sidestepped geometrically.
Low training error is not by itself evidence — you picked this hypothesis after seeing the answers, which is shooting the arrow and then painting the target. To make training error trustworthy you must guarantee that every member of the hypothesis class has training error close to its true error (that is uniform convergence), so that whichever one you pick afterwards is safe.
And "every" costs money: the larger the class, the higher the insurance premium on your freedom to choose in hindsight. Every generalization bound therefore has the same shape — true error ≤ how well you fit + how big a pool you picked from.
With probability $1-\delta$, simultaneously for all $h$ in the class. $\widehat{\mathrm{err}}_S$ is training error, $d$ the VC dimension, $m$ the sample count. Three details worth reading: the outer square root comes from the central limit theorem — estimating one mean from $m$ samples has error of order $1/\sqrt m$; $d\log(m/d)$ is exactly the Sauer–Shelah polynomial after taking a logarithm, and stands for "how many essentially distinct hypotheses must be covered at once"; $\log(1/\delta)$ confirms once more that confidence is cheap. The ratio that matters is $d/m$.
It gives Occam's razor a quantitative form. "The simpler explanation is more likely right" was an aesthetic preference for two thousand years; here it becomes a provable theorem — small $d$ converts directly into a tighter guarantee. Vapnik then turned it into an algorithm, structural risk minimization: do not minimize training error, minimize "training error + complexity penalty." Every regularization term you have ever written descends from this one inequality.
L2/L1 regularization, tree pruning, early stopping and dropout can all be read as suppressing effective capacity rather than fitting power. The more modern Rademacher complexity swaps in a different measuring stick — "how well can this class fit pure random labels?" — which varies with the actual data distribution and hugs reality far more closely than VC dimension.
Classical theory makes a clear prediction: far more parameters than samples → capacity explodes → catastrophic overfitting. Reality says otherwise. Zhang et al. ran a merciless experiment in 2017: randomize every CIFAR-10 label, and the network still trains to zero error — its capacity really is enough to memorize anything. Put the true labels back and the same network generalizes well. One model class can memorize pure noise and also learn structure, which means capacity is not what decides its fate. The algorithm's preference is.
More counterintuitive still is double descent: as model size grows, test error first falls then rises (the classical U), peaks right at the interpolation threshold (parameters ≈ samples), and then — keep growing — falls again, often below the first valley. Classical theory only ever saw the left half of this curve.
The key idea is implicit regularization: among all solutions that drive training error to zero, gradient descent does not pick one at random — it leans systematically toward a particular kind. $R$ is that preference: a complexity measure defined implicitly by the optimizer, not by the loss function. This is not hand-waving — on separable data, gradient descent on a linear classifier provably converges in direction to the max-margin solution (which lands us straight back on the VC card). Nobody knows what $R$ is for deep nonlinear networks; that ignorance is the open problem.
This is a genuine theoretical crisis whose resolution is not to overthrow the old theory but to notice it asked the wrong question. Uniform convergence asks "is the entire hypothesis class safe?"; what actually happens is that the algorithm only ever visits one tiny corner of that class. Demand safety for the whole class and you get a vacuous bound. Benign overfitting supplies the other half: in high dimensions, noise can be absorbed into directions that barely affect prediction, so overfitting and generalization coexist. Mathematics did not fail — our ruler for capacity was simply too coarse, and knowing where it is coarse is itself progress.
This rewrites practical intuition: why "make it bigger" so often helps rather than hurts (the theoretical undertone of scaling laws); why model selection in the interpolating regime must rely on held-out data rather than a complexity penalty; why weight decay, early stopping and data augmentation are not interchangeable — each changes which solution the algorithm walks to, not which solutions exist in the class.