Learning Theory
PAC learning, VC dimension, Rademacher complexity, and the No-Free-Lunch theorem.
On this page
Beginner: the previous three lessons kept circling the same informal worry — a model can look great on the data it trained on and still fail on new data, and "capacity" seems to be involved somehow. PAC learning ("Probably Approximately Correct") is where that worry finally gets a precise, checkable answer. A hypothesis class is called PAC-learnable if, once you feed a learning algorithm enough training examples, you can guarantee — with high probability (the "probably"), not absolute certainty — that the rule it learns will have error close to the best possible error achievable within that class (the "approximately correct"). The whole theory is really just an honest answer to "how many practice problems do I need before my practice-test score becomes trustworthy evidence about the real exam?"
Intermediate: to make "enough examples" precise, learning theory needs a precise notion of how "big" or "expressive" a hypothesis class is — and the classic tool for that is shattering. A hypothesis class shatters a set of points if, for every one of the possible ways you could label those points (+1/-1), some hypothesis in the class realizes that exact labeling. The VC dimension (Vapnik–Chervonenkis dimension) of a class is the size of the largest set it can shatter. Concretely: a straight-line (half-plane) classifier in the plane can shatter any 3 points that aren't all on one line — for every possible +/- assignment to those 3 points, some line achieves it — but it can never shatter 4 points, no matter how they're arranged: at least one of the 16 possible labelings of any 4 points is unachievable by any single line. The diagram and derivation below make both halves of that claim fully concrete.
Advanced: the payoff is a generalization bound — a formula, not just an intuition — of the shape "true error is at most training error plus a complexity term that grows with the class's VC dimension (or, more precisely and more modernly, its Rademacher complexity) and shrinks as the training set grows." This is the rigorous version of the generalization gap the last three lessons discussed only informally, and it's exactly why capacity (2.1.4) matters for generalization, not just for training accuracy. A separate, equally important result is the No-Free-Lunch theorem: averaged over every conceivable learning problem and data distribution, no single algorithm outperforms every other algorithm. Any algorithm's good performance is only ever relative to some implicit assumption — an inductive bias — about the kind of data it will actually see. That single fact is why the rest of this chapter covers a whole zoo of model families instead of converging on one universally best algorithm.
With probability at least 1 - δ over the random draw of the training set, simultaneously for every hypothesis f in a class H of VC dimension d (this "simultaneously for every f" property is called uniform convergence, and it's the part that makes the bound apply even to whichever f your algorithm happens to pick):
is the true risk (expected error over the whole data distribution — the number you actually care about but can never observe directly), is the empirical risk (error measured on the training set — the number you can observe), n is the number of training examples, and δ is the failure probability you're willing to tolerate. Bigger d (more capacity) makes the complexity term bigger, loosening the bound and demanding more data n to tighten it back up — the exact formal trade-off "capacity vs. data" that the last lesson only sketched qualitatively. Wanting more confidence (a smaller δ, so 1 - δ closer to 1) also loosens the bound, but only through a log(1/δ) term — confidence is cheap; capacity is expensive.
The hypothesis class here is every linear threshold function on :
— every possible straight-line decision boundary, with either side labeled +1 or -1. Proving the VC dimension is exactly 3 takes two separate halves: some set of 3 points can be shattered, and no set of 4 points ever can.
(a) Some 3 points can be shattered. Take 3 points in general position — not all on one line — say a triangle A = (0,0), B = (4,0), C = (0,4). There are possible labelings, and they split into exactly two shapes: all three points sharing one label (2 labelings), or one point isolated from the other two (the remaining 6 — 3 choices of which point, times 2 sign choices). The all-same-label case is trivial — push the boundary line far outside the triangle entirely, e.g. x - 100 > 0 is false everywhere near the triangle, so every point lands on the same side. The "isolate one vertex" case is the one worth checking concretely, because it's the case that actually breaks down at 4 points. To isolate B from {A, C}, take w = (1,-1), b = -2:
— exactly the labeling {A:-1, B:+1, C:-1}. To isolate A instead, take w = (-1,-1), b = 2:
Geometrically, this always works for any triangle: a line placed close to a chosen vertex, cutting through the two edges incident to it, clips that vertex off from the other two — and it can always be placed close enough to do so precisely because that vertex doesn't lie on the segment joining the other two points, which is exactly what "general position" (not collinear) rules out. All 8 labelings are achievable, so this 3-point set is shattered.
(b) No 4 points can ever be shattered. Any 4 points in the plane (with no 3 collinear) fall into exactly one of two configurations, and each one has a specific labeling no line can produce.
Case 1 — one point lies inside the triangle of the other three. Say point D lies strictly inside triangle ABC, so D = αA + βB + γC for some weights α, β, γ ≥ 0 summing to 1. Try to label D as -1 and A, B, C all as +1. For any affine function g(x) = w·x + b, linearity plus α + β + γ = 1 gives g(D) = α·g(A) + β·g(B) + γ·g(C) — check it by substituting and using α+β+γ=1 to distribute b correctly. If a line achieved A, B, C all positive, then g(D) is a weighted average of three positive numbers with non-negative weights, so g(D) > 0 too — D is forced to also read as +1. The desired labeling is impossible.
Case 2 — all four points form a convex quadrilateral. Order them around the quadrilateral as P1, P2, P3, P4 and try the "XOR" labeling: P1 and P3 (one diagonal pair) as +1, P2 and P4 (the other diagonal) as -1. The two diagonals of a convex quadrilateral always cross, at some point X that lies on both segments: X = λP1 + (1-λ)P3 for some λ ∈ (0,1), and also X = μP2 + (1-μ)P4 for some μ ∈ (0,1). If the labeling were achieved, g(P1), g(P3) > 0 would force g(X) — a convex combination of two positive numbers — to be positive; but g(P2), g(P4) < 0 would simultaneously force the very same g(X) — now read as a convex combination of two negative numbers — to be negative. g(X) can't be both, so no such line exists.
Since every 4-point configuration falls into one of these two cases, and each case has a labeling no line achieves, no 4 points can be shattered. Combined with part (a): the VC dimension of linear classifiers in the plane is exactly 3. The same style of argument generalizes to , giving VC dimension exactly d + 1 — one more than the number of input dimensions, matching the d + 1 free numbers (the weight vector plus the bias) that specify a hyperplane, though the full higher-dimensional proof (via Radon's theorem) is beyond what's worth reproducing here.
Where this is used: this is the precise, formal reason "more parameters isn't automatically better" from the previous lesson (2.1.4) on overfitting and capacity. Notice what the VC dimension of a linear classifier does not depend on: the absolute number of features being small. It scales as d + 1 in the number of input dimensions, full stop — a linear classifier over 500 features has VC dimension 501 whether or not that's "too much," and whether it generalizes well is entirely about how 501 compares to how many training examples n you have, exactly the ratio sitting inside the Formula bound above. Capacity is never good or bad in isolation — it's only ever good or bad relative to n.
With 3 points in general position, every +/- labeling has some separating line. Switch to 4 points (the 4th starts inside the triangle) and the default labeling — isolating that inside point — has none, exactly as proved above; drag the points anywhere and cycle through the palette to see it hold for every configuration.
There's no library function that returns "the VC dimension of this model," so the practical translation of the derivation above is an empirical one: for a small, fixed point set, try every possible +/- labeling and check, by actually attempting to fit a separator, whether each one is achievable. All three implementations below run that same brute-force check — first from scratch in Python and C++, using perceptron convergence as the separability test, then via the tool practitioners reach for instead of hand-computing VC dimension on anything past a textbook example: a learning curve.
import itertools
# A triangle in "general position" (3 points, no two share a line) and the same
# triangle with a 4th point placed strictly inside it -- the two configurations
# from the derivation above, as plain coordinate tuples.
POINTS_3 = [(0.0, 0.0), (4.0, 0.0), (0.0, 4.0)]
POINTS_4 = POINTS_3 + [(1.0, 1.0)]
def perceptron_converges(points, labels, epochs=2000, lr=1.0):
"""Runs the classic perceptron update rule for a fixed number of passes and reports
whether it drove training error to exactly zero. For small, well-behaved point sets
like these, this is a reasonable practical proxy for "is this labeling linearly
separable": the perceptron convergence theorem guarantees zero error is reached in
finitely many passes whenever a separating line genuinely exists, and the algorithm
keeps making mistakes forever whenever one does not.
"""
w1, w2, b = 0.0, 0.0, 0.0
for _ in range(epochs):
mistakes = 0
for (x1, x2), y in zip(points, labels):
score = w1 * x1 + w2 * x2 + b
pred = 1 if score > 0 else -1
if pred != y:
w1 += lr * y * x1
w2 += lr * y * x2
b += lr * y
mistakes += 1
if mistakes == 0:
return True
return False
def count_separable_labelings(points):
n = len(points)
separable = 0
for labels in itertools.product([-1, 1], repeat=n):
if perceptron_converges(points, list(labels)):
separable += 1
return separable, 2 ** n
for name, pts in [("3 points (triangle)", POINTS_3), ("4 points (+ interior point)", POINTS_4)]:
ok, total = count_separable_labelings(pts)
print(f"{name}: {ok}/{total} labelings are linearly separable")
# Running this prints 8/8 for the 3-point set -- fully shattered -- and 14/16 for the
# 4-point set: exactly the two labelings that isolate the interior point alone against
# the other three (the impossible case proved algebraically above) come back "not
# separable"; every other split of the four points is still fine.- Nobody computes exact VC dimension for real models. For a deep network with millions of parameters, it's either intractable to compute or, when bounds do exist, so astronomically loose they're useless in practice (see the expert note below). What survives from the theory isn't the number itself but the qualitative intuition it justifies — which is exactly why regularization, data augmentation, and "rule of thumb" data-size guidelines (e.g. wanting several times as many labeled examples as a model has effective degrees of freedom) remain standard practice: they're all direct, practical responses to the same
dvs.ntension the bound formalizes. - The No-Free-Lunch theorem is the reason model families multiply instead of converging on one winner. Decision trees, kernel methods, and neural networks each bake in a different inductive bias — trees assume axis-aligned splits matter, kernel methods assume similarity in some feature space matters, deep nets assume compositional, hierarchical structure matters. None dominates the others across every possible problem; each dominates on the subset of real-world problems whose structure happens to match its built-in assumptions. Picking a model family is, implicitly, a bet about which assumptions your actual data satisfies.
- Learning curves — training-set-size on the x-axis, train and validation score on the y-axis — are the practical, model-agnostic tool engineers reach for instead of a theoretical bound. A large, non-shrinking gap between the two curves is the observable symptom of exactly the situation the Formula section describes: capacity that's currently too large relative to
n. It's the same diagnosis the theory predicts, arrived at empirically rather than algebraically. - Cross-validation more generally is the field's answer to "the bound is too loose to trust literally": rather than computing a theoretical ceiling on the generalization gap for a whole modeling pipeline (feature engineering, regularization strength, model family, all at once — far too complex for any clean VC-style analysis), just measure the gap directly on held-out data. It's the same question the theory in this lesson was trying to answer in advance, answered empirically instead.
- Treating a VC-dimension-style bound as a literal, usable formula — "I have VC dimension 20, therefore I need exactly this many examples." The constants hidden inside that
O(...)are frequently enormous, and real bounds computed this way are routinely looser than the trivial fact that error is at most 1. They're a correct statement about scaling (more capacity needs more data, roughly like this), never a usable sample-size spec. - Reading the No-Free-Lunch theorem as "all algorithms are equally good in practice, so model choice doesn't matter." It says no algorithm dominates across every conceivable problem and distribution, including adversarially constructed, structureless ones. On the actual, structured problems anyone works with, some algorithms are consistently and often dramatically better than others — the theorem explains why that's not a contradiction (their advantage comes from matching real structure, not from universal superiority), not that it isn't true.
- Equating "more parameters" with "more VC dimension" or "more effective capacity." They're related but not identical — a model can be massively overparameterized in raw parameter count while its architecture, its regularization, or the optimizer's implicit bias (which of the many parameter settings that fit the training data equally well it actually converges to) keeps its effective capacity far lower than the parameter count suggests. This is directly tied to the double-descent phenomenon from the previous lesson (2.1.4): the naive "more parameters, more overfitting" intuition, taken from classical VC-style reasoning, is exactly what double descent violates.
Going deeper
Rademacher complexity is the more modern alternative to VC dimension, and it's often substantially tighter. Instead of asking "what's the largest set this class can shatter" (a worst-case, purely combinatorial, distribution-free question), it asks a distribution-aware one: take random points from the actual data distribution, assign each a uniformly random +1/-1 "noise" label with no real pattern in it at all, and measure how well the best hypothesis in the class can fit those pure noise labels. A class that can fit random noise well is, definitionally, too flexible for its own good — that same flexibility is what lets it also fit real noise in a real training set, which is precisely what generalizes poorly. Rademacher complexity turns that intuition into a number, and because it can depend on the actual data distribution rather than the worst case over all possible inputs, it frequently gives tighter, more realistic bounds than a VC-dimension argument for the same class.
Even so, classical learning theory — VC dimension, Rademacher complexity, and the uniform-convergence bounds built from them — does not fully explain modern deep learning. Networks with vastly more parameters than training examples, and VC-style capacity estimates large enough that the classical bounds are vacuous (predicting nothing tighter than "error is at most 1"), routinely generalize well in practice anyway. This is an acknowledged, still-open gap between the theory in this lesson and deep learning as actually practiced — current explanations lean on ideas like implicit regularization from stochastic gradient descent and "benign overfitting," and connect directly to the double-descent phenomenon flagged in the previous lesson, but there is no settled, textbook-clean theory yet that plays the same role for deep networks that VC dimension plays for linear classifiers.
A hypothesis class has VC dimension 10. You train on n = 50 examples and reach zero training error. Should the generalization bound above make you confident the true error is also near zero? What changes if n = 100,000 instead?
At n = 50 with d = 10, the ratio of n to d is small, so the complexity term inside the square root -- roughly d·log(n/d) plus a log(1/δ) term, all divided by n -- stays large: the bound only guarantees that true error is at most training error plus something not-small, which is compatible with a true error that's still substantial even though training error is exactly zero. The zero isn't strong evidence of good generalization yet; the bound is simply too loose at this n to say much. At n = 100,000, the same fixed VC dimension of 10 makes d/n tiny, the complexity term shrinks toward zero, and the bound now genuinely supports trusting that near-zero training error means near-zero true error. Nothing about the model or the labeling changed between the two cases -- only how much data backs up the same fixed capacity, which is exactly the n-vs-d trade-off the Formula section states directly.
PAC learning turns "will this work on new data?" into a formal, checkable question, and VC dimension makes "how expressive is this hypothesis class?" a single number — exactly 3 for lines in the plane, d + 1 for hyperplanes in d dimensions — that plugs directly into a generalization bound of the shape true error ≤ training error + a complexity term shrinking in n and growing in capacity. That bound is the rigorous backbone underneath every informal "generalization gap" and "capacity" discussion in the previous three lessons. The No-Free-Lunch theorem is the other half of the theoretical foundation: it's the formal reason no single algorithm wins everywhere, which is exactly why the rest of this chapter is organized around a whole family of different model classes rather than one best answer.