Concepts / True Risk

True Risk

Approximation error asks what the best hypothesis in the class can achieve. Estimation error asks how far the learned hypothesis is from the true risk because it was learned from a finite sample.

  • 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…

Two Sources of Poor Performance

A model can perform poorly for two importantly different reasons. First, the hypothesis class may be too limited to represent the underlying relationship well. This is approximation error. Second, the learning algorithm may select a poor hypothesis from that class because it learned from only a finite sample. This is estimation error. The distinction matters because the two problems call for different remedies.

True hypothesisunderlying relationshipApproximation errorclass limitationBest class memberbest hypothesis availableEstimation errorfinite-sample learningLearned hypothesisselected from dataclass gapmeasures gaplearning from samplefinite-sample gap
What part of the total prediction problem comes from limitations of the hypothesis class, and what part comes from learning from limited data?
Key point

Approximation error asks what the best hypothesis in the class can achieve. Estimation error asks how far the learned hypothesis is from the true risk because it was learned from a finite sample.

Following Risk as Complexity Changes

Training risk is the risk measured on the sample used to fit the hypothesis. Empirical risk is the risk observed on that finite sample. As a model becomes more capable, its empirical risk can become small even when its performance on the broader data distribution is not equally good. The contrast between empirical risk and true risk is therefore more informative than training risk by itself.

High training risklow complexityHigh validation risklow complexityLower training riskmore suitable complexityLower validation riskmore suitable complexityLow training riskhigh complexityHigher validationriskhigh complexityboth remain highboth improverisk gap grows
How do training risk and validation risk change as model complexity increases, and where do underfitting and overfitting appear?

The underfitting pattern is large empirical risk: the hypothesis performs poorly even on the sample used for learning. The overfitting pattern is different: empirical risk is small, but the gap between empirical risk and true risk is large. Validation risk helps reveal this gap because validation evaluates the learned hypothesis on data outside the training sample.

Reading the Learned Hypothesis

Worked example

Two Models, Two Diagnoses

Imagine comparing two learned hypotheses using their training and validation performance. What can the patterns suggest?

  1. 1
    Model A

    Model A has high training risk and high validation risk. Because its empirical risk is already large, the pattern is consistent with underfitting.

  2. 2
    Model B

    Model B has low training risk but much higher validation risk. The large empirical-to-true-risk pattern is consistent with overfitting.

  3. 3
    Interpretation

    The observations help diagnose the learned hypothesis, but they do not directly reveal the approximation error of the whole hypothesis class.

Result

High training risk points toward underfitting, while a large gap between training and validation performance points toward overfitting.

Training samplefinite dataLow empirical risktraining performanceLarge risk gapoverfitting patternTrue distributionbroader data sourceHigh true riskdistribution performanceevaluate onevaluate oncompare with true riskcompare with empirical risk
Why can a hypothesis have low training risk while still having high risk on the true data distribution?

The training sample and the true data distribution answer different questions. Training performance describes how the learned hypothesis behaves on the finite sample used to fit it. True risk concerns performance on the true distribution. A learned hypothesis can therefore have low empirical risk and still have high true risk; the large gap is the pattern associated with overfitting.

Validation Beyond the Training Sample

Learned hypothesisselected from training dataValidation riskobserved estimateTrue risklearned hypothesisValidation dataoutside training sampleevaluateprovides examplesestimates
How does validation data provide an estimate of how well a learned hypothesis will perform on unseen examples?

Validation evaluates the learned hypothesis on a validation set rather than relying only on the sample used to fit it. This gives an estimate of the learned hypothesis's true risk. The source notes that the difference between distribution risk and validation risk can be bounded quite tightly using Theorem 11.1, which makes validation useful for assessing the learned hypothesis.

The Approximation Gap

True hypothesisunderlying relationshipBest class memberbest available hypothesisApproximation errorgap to true hypothesisHypothesis classavailable candidatescontainscompared withcompared with
What is the relationship between the true hypothesis, the best hypothesis available in a restricted class, and the approximation gap?

Approximation error is about the gap between the true hypothesis and the best hypothesis available in a class. It concerns what the class can achieve in principle, not merely what one learning run produced. The learned hypothesis is only one member selected from that class, so its training risk cannot be read as a direct measurement of the class's approximation error.

  • Common mistake

    Treating low training risk as proof that approximation error is low.

    What it looks like

    A learned hypothesis has low empirical risk on the training sample.

    Why it fails

    The learned hypothesis may fit the finite sample well while still having a large empirical-to-true-risk gap. That pattern is associated with overfitting.

    Do this instead

    Use validation to assess the learned hypothesis and keep the class-level approximation question separate.

  • Common mistake

    Treating validation risk as a direct measurement of approximation error.

    What it looks like

    A validation result is used to conclude that the best hypothesis in the class must be close to the true hypothesis.

    Why it fails

    Validation assesses the learned hypothesis, which is only one member selected from the class.

    Do this instead

    Interpret validation as evidence about the learned hypothesis's true risk, not as a direct estimate of the class's approximation gap.

  • Common mistake

    Assuming every poor result has the same remedy.

    What it looks like

    A poor model is changed without first checking whether the pattern suggests underfitting or overfitting.

    Why it fails

    Poor performance can arise from a limited hypothesis class or from a poor hypothesis learned from finite data.

    Do this instead

    Use training and validation patterns to identify which source of error is more plausible before choosing a remedy.

Choosing a Remedy

Risk patterntraining and validationHigh empirical riskunderfitting patternClass limitationapproximation concernLarge risk gapoverfitting patternFinite-samplelearningestimation concerninspectinspectmay indicatemay indicate
How should the response differ when high error is caused by approximation error versus estimation error?

When empirical risk is large, underfitting is a plausible diagnosis, so the hypothesis class may be unable to represent the relationship well. When empirical risk is small but the empirical-to-true-risk gap is large, overfitting is a plausible diagnosis, so the learning result may be unreliable outside the training sample. These patterns do not prove the exact source of error, but they provide more informed guidance than training risk alone.

MEDIUM

A learned hypothesis has high training risk and high validation risk. Another learned hypothesis has low training risk and substantially higher validation risk. Identify the more plausible pattern for each hypothesis and state whether the concern is primarily underfitting or overfitting.

Hints
  • Start with the size of empirical or training risk.
  • Then compare training performance with validation performance.
  • A large gap between the two is diagnostically different from high risk on both.

Key Takeaways

  1. 1
    Approximation error is the gap between the true hypothesis and the best hypothesis in a class.
  2. 2
    Estimation error is the difference between empirical risk and true risk caused by learning from a finite sample.
  3. 3
    High empirical risk is associated with underfitting, while a large empirical-to-true-risk gap is associated with overfitting.
  4. 4
    Validation estimates the true risk of the learned hypothesis, but it does not directly measure the approximation error of the whole class.
  5. 5
    Training risk and validation evidence should be interpreted together before choosing a remedy.

At a glance

  • Approximation error concerns the limitation of the hypothesis class.
  • Estimation error concerns the gap created by learning from a finite sample.
  • Underfitting is associated with large empirical risk; overfitting is associated with a large empirical-to-true-risk gap.
  • Validation helps estimate the true risk of a learned hypothesis outside its training sample.
  • Neither training risk nor validation risk alone directly reveals approximation error.

Related Topics

Related concepts

More concepts starting with T