The price of capacity (bias–variance)

Parent: vc-dimension Prereq: learning-theory — err(h), ε, m, H.

Climbing the ladder buys expressiveness, but never for free.

more data: sample complexity grows like VCdim(H)/ε (fundamental-theorem) — a VC-100 class needs ~100× the data of VC-1 for the same guarantee.
overfitting: with fixed data, higher VC widens the gap between training error and true error. A class flexible enough to catch the signal is flexible enough to memorize the noise (VC = ∞ fits anything, generalizes nothing — vc-sin).

The decomposition

For a fixed sample size, the true error of the hypothesis you pick splits as

Writing d = VCdim(H):

\underbrace{\text{true error}}_{\text{want small}} \;\le\; \underbrace{\inf_{h\in H}\text{err}(h)}_{\textbf{bias (approximation)}} \;+\; \underbrace{O\!\left(\sqrt{\tfrac{d}{m}}\right)}_{\textbf{variance (estimation)}}.

Bias (approximation error): how far the best rule in H is from the truth. Shrinks as H grows.
Variance (estimation error): how far your chosen rule can stray from the best-in-class on a finite sample. Grows as H grows (via VC).

Growing H trades one for the other — hence a U-shaped total error.

The lever: structural risk minimization

So raise VC just far enough to contain the truth, no further: too low → can't represent it (bias / underfit); too high → fits noise (variance / overfit). Choosing that level — search a nested chain H₁ ⊂ H₂ ⊂ … and pick the level minimizing train error + capacity penalty — is Vapnik's structural risk minimization (SRM), the theory-side ancestor of regularization.