Generalisation Theory

Bias-variance, VC dimension, PAC learning, double descent

Imagine throwing darts at a board, over and over. There are two very different ways to be bad at it. You could throw tightly grouped darts that all land in the same wrong corner — consistent, but consistently off. Or you could throw darts scattered wildly all over — sometimes near the bullseye, sometimes nowhere near, no two alike. The first kind of error is bias: a steady, systematic miss in the same direction. The second is variance: a wild sensitivity that makes every throw different. Almost every model that fails, fails in one of these two ways — and knowing which one is the difference between fixing it and flailing.

Here is the setup that makes it real. You train a model on house prices. Training error: 2%. Test error: 20%. In production it is useless, and nothing in the training loop warned you — it was doing its job perfectly. That 18-point gap is the real problem, and to fix it you have to know *why* it is there.

Splitting the error into three pieces

The test error of any model breaks into three parts.

The first is noise — the random, unpredictable wobble in house prices that no model could ever capture (a seller in a hurry, a surprise bidding war). This is a floor; you cannot beat it.

The second is bias — the model's steady tendency to miss in the same direction, because its assumptions are too simple. A straight line fit to a curvy truth will always cut the same corners. High bias means the model is too rigid to capture the real shape. That is underfitting.

The third is variance — how much the model's predictions jump around when you retrain it on a slightly different sample of houses. A deep, flexible model can bend to fit the training set exactly, but swap out ten houses and it draws a completely different curve. High variance means the model is chasing noise. That is overfitting.

The tug-of-war

Here is the catch that makes this hard: the cure for one makes the other worse. Add flexibility to reduce bias (a deeper tree, more features) and you raise variance — the model now has enough freedom to chase noise. Add regularisation to tame variance and you raise bias — the model is now too constrained to fit the real shape. This is the bias-variance tradeoff, and every knob you turn — model size, regularisation strength, tree depth — is a position on it. The whole game is finding where the total is smallest.

That is also why the two failures need opposite fixes, and why guessing wrong wastes weeks. Training error high *and* test error high (say 15% and 18%)? That is high bias — the model cannot even fit the data it trained on, so give it more power (more features, a more flexible model, less regularisation); more data will not help. Training error low but test error much higher (2% and 20%)? That is high variance — the model memorised the training set, so rein it in (more regularisation, a simpler model, or the most reliable fix, more training data).

How much power is too much? (going deeper)

There is a classical way to measure a model's raw capacity to overfit, called the VC dimension. In plain terms it is the largest number of points the model can label *any way you like* and still fit perfectly. A straight line in a plane can do this for any 3 points but not 4 — so its capacity is small. Pile on features and the capacity climbs, and the rule of thumb is stark: the more capacity you add, the more data you need just to keep the same gap between training and test. Double the features and you roughly double the data you need to stay level. That is the formal price of flexibility.

And there is a modern twist that broke the old picture. The classic story says test error follows a U as you add capacity — too little underfits, too much overfits, one sweet spot in the middle. That U is real, but it is not the whole story. Keep pushing capacity *far* past the point where the model can memorise the training data — into the giant, over-parameterised models behind today's deep learning — and test error, surprisingly, often starts falling *again*. This is double descent. Roughly: when a model has far more capacity than it needs, gradient descent tends to settle on the *smoothest* fit among the many that work, and smooth fits generalise well.

The one belief to drop

"More data always helps." Not true — and knowing when it does not saves you months. More data reliably cuts *variance*: if the model is overfitting, more examples pin it down. But more data does almost nothing for *bias*. A straight line fit to a curve will miss that curve by about the same amount whether you feed it 100 houses or 100,000 — it will just be more confident about the wrong shape. More data fixes a model that is too twitchy. It cannot fix a model that is simply the wrong shape. For that, you fix the model.

Three sets, three jobs: train / validation / test

None of this measurement works without disciplined splits. Training data fits the weights. Validation data tunes the knobs — lambda, tree depth, which model — and you can look at it as often as you like. Test data is touched *once*, at the very end, to get an honest final number. The cardinal sin is letting the test set influence any decision; peek at it while tuning and it stops being an honest estimate — you've overfit to it just as surely as to the training set. Watch too for leakage: any preprocessing (scaling, imputation, feature selection) must be fit on training folds only, or information about the test set sneaks into training and your numbers turn rosy and false. When data is scarce and a single split is too noisy, use k-fold cross-validation — rotate which fold is held out and average — to get a stable estimate.

The decomposition, written down

The three-part split has an exact form. For squared-error regression, the expected test error at a point is:

$E[(y - \hat{f})^2] = \sigma^2 + \text{Bias}^2 + \text{Variance}$

— irreducible noise ($\sigma^2$), the squared bias (how far the average model is from the truth), and the variance (how much the model wiggles across training samples). You can't touch the noise; every knob you turn trades the other two. That's the tradeoff made precise.

VC dimension, precisely: shattering

We said VC dimension is "the most points you can label any way and still fit." The exact word is shatter: a model *shatters* a set of points if, for *every* possible labeling of them, it can fit them perfectly. The VC dimension is the size of the largest set it can shatter — a line in 2D shatters any 3 points but no set of 4, so its VC dimension is 3. Two cautions interviewers probe. First, VC dimension is *capacity*, and it is not the same as parameter count — some models with few parameters have huge capacity and vice versa. Second, the VC generalization bound (gap ∝ √(VC/n)) is *conceptually* central but *numerically loose* — it's a useful way to think, not a number you'd quote to predict real test error.

PAC learning: what the letters actually mean

The module title says PAC, so here's the real content. PAC = Probably Approximately Correct. "Approximately" is an accuracy tolerance ε — the model's error is within ε of the best possible. "Probably" is a confidence δ — it hits that accuracy with probability at least 1−δ. Why both, and why probabilistic? Because you learn from a *random* sample: with bad luck you could draw a misleading sample, so you can never promise correctness with certainty — only "approximately correct, probably." PAC theory then gives sample complexity: how many examples you need to guarantee (ε, δ) for a given hypothesis class (the set of models you're choosing from). Bigger, more expressive hypothesis classes need more samples — the formal echo of "more capacity needs more data."

Capacity isn't just parameter count

This is why "count the parameters" is too crude. What matters is *effective* capacity, and regularisation shrinks it without deleting parameters. L2/weight decay, dropout, early stopping, and data augmentation all reduce how much arbitrary structure the model can actually express, even though the parameter count is unchanged. A giant network trained with heavy augmentation and early stopping can have far less effective capacity than its raw size suggests — which is part of why over-parameterised models don't overfit the way naive capacity counting predicts.

Double descent — with the caveats

Double descent (test error falling again far past the interpolation point) is real, but it's *not* a license to blindly enlarge models. Whether it shows up depends on the optimiser and its implicit regularisation, the data quality and noise level, and the architecture. In many practical, noisy, well-tuned settings you never see a second descent, or the gains are marginal versus the compute. Treat it as "huge models can generalise better than the classic U-curve warns," not "bigger is always better."

The assumption hiding under all of it: same distribution

Every guarantee here — bias-variance, VC bounds, PAC, even the honest test set — quietly assumes train and deployment data come from the *same* distribution. Production breaks that constantly, which is why a model can look great in validation and fail live. Covariate shift: the inputs P(X) drift (new user demographics) while the true relationship holds. Concept drift: the relationship P(Y|X) itself changes (fraud tactics evolve). Train-serving skew: a feature is computed differently in training than in serving. When validation looked good but production didn't, this family — not bias or variance — is usually the culprit.

Key points

• Use the bias-variance lens to read a train/test gap — and measure training error, not just test error. Both training and test error high and close together? That is high bias — the model is too simple, so give it more power (more features, a more flexible model, less regularisation). Training error low but test error much higher? That is high variance — the model memorised noise, so rein it in (more regularisation, a simpler model, or more data). The one move that tells you which you are facing is looking at training error. Diagnose first, because the two fixes are opposite and applying the wrong one makes things worse.
• The trap: reaching for "more data" as a cure-all. More data is the most reliable fix for high variance — it pins down a model that is overfitting. But it does almost nothing for bias. A model that is simply the wrong shape (a straight line on curved data, or missing a key feature) keeps making the same systematic miss no matter how many examples you feed it — just with more false confidence. Before you spend months collecting data, fit a more flexible model on what you already have; if its test error is also high, you have a feature or data-quality problem, not a sample-size one.
• The diagnostic: plot a learning curve — training and validation error as the dataset grows. If both curves sit high and hug each other, you are underfitting (high bias), and more data barely moves them — add capacity. If training error is low but validation stays well above it and the gap refuses to close, you are overfitting (high variance) — regularise, simplify, or gather more data, which slowly pulls the curves together. If they meet but at a stubbornly high error, you have hit the noise floor or a genuinely wrong model.
• Guard the three-way split and know the decomposition it measures. Train fits weights, validation tunes knobs (look freely), test is touched once for an honest final number — peek at test while tuning and it's no longer honest. Fit all preprocessing on training folds only to avoid leakage, and use k-fold CV when data is scarce. What you're estimating has an exact form: $E[(y-\hat f)^2] = \sigma^2 + \text{Bias}^2 + \text{Variance}$ — irreducible noise plus squared bias plus variance, and every knob trades the last two.
• State VC and PAC precisely — capacity is not parameter count. A model *shatters* points if it can fit every possible labeling of them; VC dimension is the largest set it can shatter (a 2D line: 3). The VC bound (gap ∝ √(VC/n)) is conceptually central but numerically loose. PAC = Probably (confidence 1−δ) Approximately (error within ε) Correct — probabilistic because you learn from a random sample — and its sample complexity says bigger hypothesis classes need more data. Crucially, effective capacity is shrunk by L2, dropout, early stopping, and augmentation without changing the parameter count, which is why over-parameterised models needn't overfit.
• Double descent has caveats, and every guarantee assumes a fixed distribution. Test error falling again past the interpolation point is real but depends on the optimiser's implicit regularisation, noise level, and architecture — it's "huge models can beat the U-curve," not "bigger is always better." And all of this — bias-variance, VC, PAC, the honest test set — assumes train and serving data share a distribution. When validation looked fine but production failed, suspect covariate shift (P(X) moves), concept drift (P(Y|X) moves), or train-serving skew, not bias or variance.

Recap

• Test error = noise (irreducible) + bias² + variance.
• Bias = model too simple (underfitting); variance = model too twitchy (overfitting). Opposite fixes.
• Measure training error to tell them apart — high train error = bias, low train + high test = variance.
• More data cures variance, not bias. A wrong-shaped model stays wrong.
• Learning curve (train + validation error vs dataset size) is the diagnostic.
• Capacity ≠ parameter count — VC dimension is the real measure; every PAC guarantee assumes a fixed distribution.
• Double descent breaks the classic U-curve, but with caveats.

Check your understanding