Concepts / Overfitting and Generalization

Overfitting and Generalization

Generalization asks whether the training-based choice also performs well under the data distribution.

  • Programming
Interactive lab

Try it: Empirical Risk Minimization

How ERM picks the hypothesis in a finite class H with the smallest empirical risk on a random sample , how far its true risk can be from , how often ERM misses ε over many samples compared with the finite-class sample-complexity bounds, and how a richer class trades approximation error for estimation error until memorising the sample overfits.

How it works

  1. D is known: x is uniform over n points in [0, 1] and its label is a target rule f (a threshold or an interval), flipped with probability η; so every can be computed exactly.
  2. Draw : independent labelled examples from a seeded random stream.
  3. For every h in H (thresholds or intervals on a grid, listed in order), count its mistakes on S to get , and compute its true risk from . For the class of all functions, ERM simply memorises S: the majority label at each seen point, 0 elsewhere.
  4. ERM returns , the first hypothesis with the smallest . Compare with , and split into plus .
  5. Repeat with R fresh samples and count how often . The finite-class bound says (realizable, ) or (agnostic, ) keeps that frequency at most δ.
  6. Run the same samples through richer and richer classes: falls, the average rises, and memorising (all functions) reaches small with a large .

Default run (16 steps): D: x uniform over 20 points in [0, 1], label f(x) = 1[x >= 0.4] flipped with probability η = 0.1. H = thresholds on the grid i/10, |H| = 11. The learner never sees D; it gets S ~ Dm with m = 20. … Richer classes on the same 200 samples: ε_app falls from 0.42 (thresholds, k = 1) to 0.1 (all functions), while the average ε_est rises to 0.2282 for all functions (average LS 0.0617). Lowest average LD(hS): thresholds, k = 5 (0.1136).

Simplified: A toy domain of 8-40 equally likely points on a line, a target that is a threshold or an interval, and symmetric label noise, so is an exact finite sum rather than an integral over a continuous distribution. Hypotheses are thresholds or intervals with endpoints on a grid i/k, or all functions on the n points. ERM ties are broken towards the first hypothesis in listing order (for all functions: towards label 0), where the textbook allows any minimiser. Failure frequencies come from at most 400 seeded samples, so they estimate the probability rather than compute it; the bounds use the natural logarithm.

Educational simulation

Loading the simulation…

A Perfect Training Score

Imagine two hypotheses that both classify every example in a training sample correctly. One may have learned a pattern that continues to work on new data. The other may have matched accidental details of the sample and perform poorly beyond it. This is the central difficulty of overfitting: success on the observed sample does not by itself establish success under the data distribution.

Training sampleobserved examplesZero empirical riskno sample errorsUnseen datadata distributionHigh true riskmany distribution errorsevaluated onevaluated on
How can a hypothesis make no mistakes on the training sample yet still make many mistakes on unseen data?

The ERM Selection Process

Suppose a learner may choose only from a fixed collection of predictors, called a hypothesis class. In this article, the class contains a finite number of candidates. Empirical risk minimization, or ERM, evaluates how each candidate performs on the training sample and selects a hypothesis with minimum empirical risk. ERM therefore turns the training sample into a choice among the available candidates.

Finite hypothesisclasscandidate predictorsTraining sampleobserved dataEvaluate candidatessample performanceCompare empiricalrisksfind minimumERM resultminimum empirical riskprovides candidatesprovides evidenceproduces risksselects minimum
How does ERM compare candidate hypotheses and select the one with the lowest empirical risk?
Worked example

Selecting among three candidates

An ERM learner compares three hypotheses on the same training sample. Hypothesis A makes errors on the sample, while hypotheses B and C make no errors.

  1. 1
    Evaluate

    ERM examines the performance of A, B, and C on the training sample.

  2. 2
    Compare

    A has higher empirical risk than B and C. B and C are tied for the minimum empirical risk.

  3. 3
    Select

    ERM chooses a hypothesis with minimum empirical risk, so it selects B or C in this example.

Result

The ERM result has zero empirical risk on the sample, but this result alone does not establish low true risk.

Realizability and the Sample

Definition

The realizability assumption places a target hypothesis h* inside the hypothesis class H and gives h* zero true risk. In other words, the class contains a hypothesis that agrees with the target labeling rule in the setting under discussion.

Because h* has zero true risk, a random sample drawn from the data distribution and labeled by the target rule has empirical risk zero for h* with probability 1. Thus, under realizability, the class contains at least one candidate that labels every training example correctly. ERM can use this candidate as a benchmark.

Target ruleh*Hypothesis classHZero true riskRandom labeled sampleZero empirical riskbelongs tohasimplies correct labels ongives h*
What does it mean for the target labeling rule to belong to the hypothesis class, and why does that imply that some hypothesis labels every training example correctly?

From Sample Fit to Generalization

Under realizability, h* has zero empirical risk on the random training sample with probability 1. Since ERM chooses a hypothesis with minimum empirical risk, every ERM result h_S also has empirical risk zero in this setting. This is an important intermediate conclusion: ERM can fit the observed sample perfectly.

The conclusion is still limited to the sample. The fact that h_S has zero empirical risk does not by itself prove that h_S has low true risk. A selected hypothesis can agree with all observed examples while reflecting accidental patterns that do not continue beyond the sample. Generalization asks whether the training-based choice also performs well under the data distribution.

Worked example

Two hypotheses with the same training score

Consider two candidates selected after examining a training sample. Both classify every training example correctly. Candidate A follows a pattern that also agrees with the target rule on unseen data. Candidate B matches the training examples but uses accidental details that do not continue on unseen data.

  1. 1
    On the training sample

    Both candidates have zero empirical risk because neither makes an error on the observed examples.

  2. 2
    Beyond the sample

    The candidates can differ in true risk because their behavior under the data distribution need not be the same.

  3. 3
    Interpret the result

    Zero empirical risk identifies perfect sample performance, not automatically good generalization.

Result

A learner must reason about the hypothesis class and the amount of training data, not only the training score.

Training samplesame observed examplesHypothesis Azero empirical riskLow true riskunseen dataHypothesis Bzero empirical riskHigh true riskunseen datafitsfitsmay havemay have
How can two hypotheses with identical training performance differ when evaluated under the data distribution?

Why Class Size Matters

A finite hypothesis class gives ERM a controlled candidate set. Finiteness does not necessarily mean that the modeling idea is extremely narrow. For example, the source material describes a class of predictors implementable by a C++ program using at most 10^9 bits of code. It also describes axis-aligned rectangles: the class is infinite when real-valued parameters have no finite representation limit, but discretizing those parameters with a 64-bit floating-point representation makes the resulting class finite.

Restricting the learner to a finite collection limits the number of candidate explanations that ERM can compare and select from. This control can limit overfitting because the learner is not choosing from an unbounded set of possible predictors. The required amount of training data is tied to the size of the class: as the class becomes larger, the required training-sample size grows in relation to that class size.

Smaller classfewer candidatesRequired datasmaller amountLarger classmore candidatesRequired datalarger amountis tied tois tied to
Why does ERM need more training examples when it chooses from a larger hypothesis class?
Finite candidatesetcontrolled choicesControlled ERM searchlimits possible fitsUnbounded candidatechoicesmore possible fitsAccidental patternsmore ways to fitprovidesallows more
How does restricting the learner to a finite set of candidate hypotheses reduce the number of ways it can fit accidental patterns in the training data?

Common Reasoning Errors

  • Common mistake

    Treating zero empirical risk as zero true risk.

    What it looks like

    A hypothesis labels every observed training example correctly, so the learner concludes that it will also be correct on unseen data.

    Why it fails

    Empirical risk concerns the training sample, while true risk concerns performance under the data distribution.

    Do this instead

    State the conclusion precisely: the hypothesis has zero empirical risk on the sample. Generalization still requires reasoning about true risk.

  • Common mistake

    Assuming ERM selects the universally correct hypothesis.

    What it looks like

    The learner says that ERM must choose h* whenever it chooses a minimum-risk hypothesis.

    Why it fails

    ERM selects a hypothesis with minimum empirical risk. Multiple candidates can have the same sample performance, and the sample result alone does not identify the target hypothesis.

    Do this instead

    Describe ERM as a training-sample selection procedure, then separately ask whether its result generalizes.

  • Common mistake

    Forgetting the realizability assumption when claiming zero empirical risk for ERM.

    What it looks like

    The learner claims that ERM always has a zero-error candidate available.

    Why it fails

    The zero-empirical-risk conclusion follows here because realizability places h* in the class and gives it zero true risk.

    Do this instead

    Identify the assumption first: under realizability, h* has zero empirical risk on the random labeled sample with probability 1.

  • Common mistake

    Interpreting a finite class as necessarily very small.

    What it looks like

    The learner assumes that a class is not meaningfully finite unless it contains only a few simple predictors.

    Why it fails

    A finite class can still contain many candidates. The source gives examples involving bounded-length C++ programs and discretized axis-aligned rectangles.

    Do this instead

    Use finite to mean that the candidate collection has a finite number of members, not that the collection is tiny.

  • Common mistake

    Ignoring class size when discussing the amount of data needed.

    What it looks like

    The learner expects the same training-sample amount to be sufficient regardless of how many candidates ERM can choose from.

    Why it fails

    The required amount of training data grows in relation to the size of the hypothesis class.

    Do this instead

    Always connect the data requirement to the number of available hypotheses.

Check Your Understanding

MEDIUM

A finite hypothesis class contains a target hypothesis h* with zero true risk. A random sample is labeled by the target rule, and ERM selects a hypothesis with minimum empirical risk. What can you conclude about the ERM result on the training sample? What can you not conclude from that fact alone?

Hints
  • Use the fact that h* belongs to the class and has zero true risk.
  • Remember that ERM chooses a minimum empirical-risk hypothesis.
  • Separate performance on the observed sample from performance under the data distribution.
Worked example

Checking the conclusion

Explain the consequence of realizability for ERM and distinguish it from a generalization claim.

  1. 1
    Locate h*

    Realizability places h* inside H and gives h* zero true risk.

  2. 2
    Transfer to the sample

    A random sample labeled by the target rule has empirical risk zero for h* with probability 1.

  3. 3
    Apply ERM

    Because ERM chooses a minimum empirical-risk hypothesis, its result also has empirical risk zero in this setting.

  4. 4
    Limit the conclusion

    This establishes perfect performance on the observed sample, not automatically low true risk under the data distribution.

Result

Under realizability, ERM has access to a zero-error candidate on the sample and therefore selects a zero-empirical-risk result, but generalization remains the separate question.

Key Takeaways

  1. 1
    ERM examines a finite collection of candidate hypotheses and selects one with minimum empirical risk on the training sample.
  2. 2
    Under realizability, the class contains h* with zero true risk, so h* has zero empirical risk on a random labeled sample with probability 1.
  3. 3
    Consequently, every ERM result has zero empirical risk in this realizable finite-class setting.
  4. 4
    Zero empirical risk concerns the observed sample and is not the same as low true risk under the data distribution.
  5. 5
    The required amount of training data grows in relation to the size of the hypothesis class, which is why controlling the candidate set can limit overfitting.

At a glance

  • ERM selects a minimum-empirical-risk hypothesis from a finite candidate class.
  • Realizability places a zero-true-risk target hypothesis inside that class.
  • Under realizability, ERM achieves zero empirical risk on the random training sample with probability 1.
  • Zero empirical risk does not by itself guarantee low true risk or good generalization.
  • Larger finite hypothesis classes require a larger amount of training data, so restricting the candidate set can help control overfitting.

Related Topics

Related concepts

More concepts starting with O