Generalization

Formally, assume there is a fixed but unknown distribution $\mathcal{D}$ over input-output pairs $(x, y)$, and a loss function $\ell(f(x), y)$ measuring how badly a model $f$ predicts $y$ from $x$. The quantity we actually care about is the population risk (also called true risk or expected risk):

We cannot compute $R(f)$ directly because $\mathcal{D}$ is unknown — we only have a finite training sample $S = \{(x_1,y_1), \dots, (x_n,y_n)\}$ drawn i.i.d. from $\mathcal{D}$. What we can compute is the empirical risk:

Learning algorithms minimize $\hat{R}_S(f)$ over some hypothesis class $\mathcal{H}$ (this is empirical risk minimization, ERM), but the actual object of interest is $R(f)$. The generalization gap of a hypothesis $f$ is defined as

A model generalizes well if this gap is small — its behavior on the training sample is representative of its behavior everywhere. Note the gap can be estimated but never known exactly, since $R(f)$ is unobservable; this is exactly why we hold out a test set, whose empirical risk $\hat R_{\text{test}}(f)$ serves as an unbiased estimate of $R(f)$ for a model not fit to that test set. Two failure modes correspond to the two ways this gap can arise. Overfitting occurs when $\hat{R}_S(f)$ is very low but $R(f)$ is high — the model has fit peculiarities of the specific sample (including noise) that do not reflect the true distribution. Underfitting occurs when both $\hat{R}_S(f)$ and $R(f)$ are high — the hypothesis class is too restrictive to capture the true relationship, so the gap may be small, but for the wrong reason (nothing was learned). Generalization is therefore not simply "small training error" nor "small gap" in isolation; it is small population risk, achieved through a training procedure whose gap is controlled.

There is no single "generalization algorithm" — rather, generalization is a property that any supervised learning pipeline must be designed to achieve, and it is monitored and controlled through a specific workflow. The mechanism has three moving parts: (1) splitting data so that a model is never evaluated on what it was fit to, (2) fitting on the training portion, and (3) using the held-out portion as a proxy for the true population risk, which then informs decisions about model complexity. ``` ALGORITHM: Estimate and Control Generalization Gap Input: dataset D of n i.i.d. samples from distribution 𝒟, hypothesis class family {H_1, H_2, ..., H_k} of increasing complexity (e.g., polynomial degree, tree depth, regularization strength) 1. Split D into: D_train (e.g., 60%) D_val (e.g., 20%) -- used to select complexity level D_test (e.g., 20%) -- used ONLY ONCE, at the very end 2. for each candidate hypothesis class H_j in {H_1, ..., H_k}: f_j <- ERM(H_j, D_train) // fit by minimizing empirical risk train_risk_j <- empirical_risk(f_j, D_train) val_risk_j <- empirical_risk(f_j, D_val) // proxy for R(f_j) gap_j <- val_risk_j - train_risk_j 3. j <- argmin_j val_risk_j // pick complexity with best proxy for R(f) 4. f_final <- ERM(H_{j}, D_train ∪ D_val) // optional: refit on more data test_risk <- empirical_risk(f_final, D_test) // final, honest estimate of R(f_final) 5. report test_risk as the generalization performance (D_test must never influence steps 1-3, or the estimate is biased) Output: f_final, an honest estimate test_risk ≈ R(f_final) ``` The crucial invariant enforced by this procedure is sample independence between fitting and evaluation. Any information leak — tuning hyperparameters on the test set, preprocessing using statistics computed over the full dataset before splitting, or peeking at test labels — breaks the guarantee that $\hat{R}_{\text{test}}(f)$ is an unbiased estimate of $R(f)$, and silently reintroduces the very gap the split was designed to expose. This is why step 4's test evaluation happens exactly once: reusing the test set to pick between multiple final models turns it into a second validation set, and the resulting number is no longer trustworthy.

Time and space complexity. The overhead introduced specifically by generalization control — splitting and holding out data — is $O(n)$ to partition the dataset and $O(1)$ additional space beyond storing the data itself (splits are index sets, not copies, in a well-engineered implementation). The dominant cost is the $k$-fold refitting in step 2: if a single ERM fit over $m$ examples costs $C(m)$, evaluating $k$ candidate hypothesis classes costs $O(k \cdot C(n_{\text{train}}))$, plus $O(k \cdot n_{\text{val}})$ to score each on the validation set. This is the same order of cost as ordinary hyperparameter search; the generalization-checking machinery adds no asymptotic overhead beyond what tuning already requires. This is honest: the statistical cost of generalization — how much data you need to trust the estimate — is a separate and more important question, addressed below.

Why the empirical risk is a biased-low estimate of population risk. Let $f^* = \arg\min_{f \in \mathcal{H}} \hat{R}_S(f)$ be the ERM solution. Because $f^*$ was chosen to minimize risk on this particular sample $S$, it is likely to fit quirks specific to $S$ (including label noise) that do not appear in a fresh draw. Formally, for a fixed $f$ not depending on $S$, $\mathbb{E}_S[\hat{R}_S(f)] = R(f)$ — the empirical risk is unbiased for any hypothesis chosen before seeing the sample. But $f^*$ depends on $S$, so this identity fails for $f^*$; in general

with strict inequality whenever the hypothesis class is rich enough to fit sample-specific noise. This is the precise reason training error systematically understates true risk — it is not a quirk of any one algorithm, it is a structural consequence of optimizing and evaluating on the same data.

Bounding the gap: uniform convergence. Learning theory formalizes how large the gap can be. For a hypothesis class $\mathcal{H}$ with VC dimension $d$ (or, more generally, Rademacher complexity $\mathfrak{R}_n(\mathcal{H})$), a uniform convergence bound of the following flavor holds with probability at least $1-\delta$ over the draw of $S$, simultaneously for every $f \in \mathcal{H}$:

Three honest lessons follow directly from this bound, and each foreshadows a later topic:

• The gap shrinks as $n$ grows, at rate $O(1/\sqrt{n})$ — more data provably tightens the guarantee, which is why "get more data" is often the single most effective fix for overfitting.
• The gap grows with hypothesis class complexity ($d$) — richer classes can drive $\hat{R}_S(f)$ to zero while $R(f)$ stays large, exactly the overfitting failure mode. This complexity/fit tradeoff is made quantitative in the Bias-Variance Tradeoff.
• The bound requires $S$ to be i.i.d. from $\mathcal{D}$ — if training data is not representative of deployment data (distribution shift), no amount of data or regularization closes the gap, because the theorem's premise is violated, not its conclusion.

Correctness of the workflow. The train/val/test procedure is "correct" in the sense that $\hat{R}_{\text{test}}(f_{\text{final}})$ is an unbiased estimator of $R(f_{\text{final}})$ provided $D_{\text{test}}$ was never used, even indirectly, to choose $f_{\text{final}}$ or its hyperparameters. This is a direct consequence of the identity above: $D_{\text{test}}$ plays the role of "a fixed $f$" evaluation — it is the hypothesis, not the data, that was chosen in advance of seeing this particular sample. Violate that independence — by tuning on the test set, or by running many models against it and reporting the best — and the estimate inherits the same optimistic bias that training error has, just one level removed (this is sometimes called "test set overfitting" via repeated reuse).

Tradeoffs. Holding out data for validation/test reduces the sample available for fitting, which itself worsens the achievable gap for the training set — a real cost, mitigated in practice by Cross-Validation, which reuses data more efficiently by rotating which subset plays the validation role.

Consider fitting polynomials of increasing degree to $n = 12$ noisy samples of $y = \sin(x) + \varepsilon$, $\varepsilon \sim \mathcal{N}(0, 0.1^2)$, with $x$ drawn uniformly from $[0, 2\pi]$. We use 8 points for training and 4 held out for validation, and measure mean squared error.

Reading this table the way the algorithm in "How it works" prescribes: degree 1 is rejected because both columns are bad — no gap, but no fit either (underfitting). Degrees 9 and 11 show training error collapsing toward zero while validation error explodes — the textbook signature of overfitting, and exactly what the uniform-convergence bound predicts as $d$ (here, effectively the number of polynomial coefficients) grows relative to $n = 8$. Degree 3 has the smallest validation error and a modest gap — it is selected as $j^*$, and only now, having fixed the model, would we touch the untouched 4-point test set to report a final, trustworthy estimate of $R(f_3)$. Note the qualitative shape: gap is small-but-bad at low complexity, small-and-good at moderate complexity, and enormous at high complexity. Generalization is not maximized by making the gap zero (degree 11 does that on the training portion in the limit) — it is maximized by minimizing $R(f)$, which the validation column approximates. This distinction — small gap versus small population risk — is precisely the one algebraic warning in the "The idea" section made concrete with numbers.

The theoretical backbone of generalization — bounding how far empirical performance can diverge from true performance — was built by statisticians and computer scientists formalizing what it means for a learning rule to be trustworthy at all.

Every production machine learning system is, in effect, a bet on generalization: a recommendation engine, a credit-scoring model, or a self-driving perception stack is trained once and then must perform indefinitely on inputs it has never seen. Model cards and evaluation reports at organizations like Google, Meta, and financial institutions almost always report held-out test metrics precisely because training accuracy is known to be an unreliable and optimistic signal. Kaggle-style competitions enforce hidden test sets for exactly the reason described above — public leaderboard overfitting (repeatedly submitting to the same test proxy) is a well-documented failure mode. In regulated domains such as clinical machine learning, regulators explicitly require prospective validation on genuinely unseen patient cohorts, because retrospective training-set performance is understood not to imply generalization. The theoretical machinery here — VC dimension, uniform convergence, PAC bounds — also underlies modern arguments for why heavily overparameterized deep networks can still generalize, an active research frontier building directly on the classical framework introduced here.

Ask the tutor: How does VC dimension formally quantify a hypothesis class's capacity to overfit, and how is it computed for a class like linear classifiers?