Relaxing the Realizability Assumption
Relaxing the realizability assumption means that the discussion does not require a prediction rule to classify every possible example associated with D correctly.
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
- 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.
- Draw : independent labelled examples from a seeded random stream.
- 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.
- ERM returns , the first hypothesis with the smallest . Compare with , and split into plus .
- Repeat with R fresh samples and count how often . The finite-class bound says (realizable, ) or (agnostic, ) keeps that frequency at most δ.
- 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.
Loading the simulation…
The Evaluation Problem
A learner must choose a prediction rule h, but choosing a rule is not enough. The learner also needs a way to evaluate how well that rule predicts labels. Two evaluation sources matter: the probability distribution D and the training data S. True error uses labeled points drawn according to D. Empirical risk uses the particular training data S available to the learner.
The learner wants a prediction rule with low true error, but the learner does not know D. The learner does have access to S, so empirical risk is the directly available evaluation measure.
What do you think happens?
A learner can inspect the training data S but does not know the distribution D. Which measure can the learner calculate directly from the information it has?
Reveal answer
Empirical risk
Empirical risk evaluates prediction error using S, which the learner has. True error is defined using labeled points drawn according to D, but D is unknown to the learner.
True Error Under D
The true error, also called the risk, of a prediction rule h asks how likely h is to make an error on labeled points drawn according to the probability distribution D. The prediction rule is evaluated against the labeled examples that D produces, rather than only against the examples that happened to appear in one training sample.
The distribution D matters in two connected ways. It determines which labeled points are relevant to the evaluation, and it determines how those points contribute to the overall assessment through the distribution from which they are drawn. True error therefore describes performance with respect to D, not merely performance on a finite list of observed examples.
Evaluating the Same Rule Against D
Consider a prediction rule h that is evaluated on labeled points drawn according to a distribution D.
- 1Identify the prediction rule
The object being evaluated is h. True error is not a property of the training data alone; it evaluates this prediction rule.
- 2Use labeled points associated with D
The relevant labeled points are drawn according to D. The evaluation is therefore tied to the distribution that produces the points.
- 3Assess the errors
For each evaluated point, h either makes an error or does not. True error describes how likely an error is for points drawn according to D.
True error is the risk of h with respect to D: it describes the error behavior of h on labeled points drawn according to that distribution.
Training Data and Empirical Risk
Empirical risk evaluates the prediction error of h using the training data S. It is an evaluation based on the finite training sample available to the learner.
Empirical risk and true error evaluate the same kind of object: a prediction rule h. Their difference is the source used for evaluation. True error uses labeled points associated with the unknown distribution D. Empirical risk uses the observed training data S.
| Measure | Evaluation source | Learner's access |
|---|---|---|
| True error | Labeled points drawn according to D | D is unknown |
| Empirical risk | Training data S | S is available |
Both measures evaluate prediction errors made by h, but they use different evaluation sources.
From Observable Risk to Desired Risk
The learner's goal and the learner's information are not the same thing. The learner wants a prediction rule h with low true error because true error describes performance with respect to D. However, the learner cannot directly use D because D is unknown. The learner can inspect S and use empirical risk as an accessible way to evaluate h.
When Perfect Prediction Is Not Required
Relaxing the realizability assumption means that the discussion does not require a prediction rule to classify every possible example associated with D correctly. Some errors may remain part of the evaluation. In that setting, the useful question is not whether h makes no errors everywhere, but how much error h has under D and how much error it has on the observed training data S.
This change does not replace the two evaluation measures. True error still uses D, and empirical risk still uses S. Relaxing the assumption changes how the errors are interpreted: errors are quantities to evaluate and compare rather than evidence that the entire learning setup has failed simply because a perfect rule is unavailable.
Common Misunderstandings
Common mistake Treating true error as the error measured only on S.
What it looks likeCalling the errors observed in the training data the true error of h.
Why it failsTrue error is evaluated with respect to labeled points drawn according to D, while S is the source for empirical risk.
Do this insteadUse true error for the distribution-based evaluation and empirical risk for the training-data evaluation.
Common mistake Assuming the learner knows D.
What it looks likeDescribing the learner as directly calculating the error of h under D.
Why it failsThe learner does not know the data-generating distribution D.
Do this insteadRemember that the learner has access to S and can evaluate empirical risk from that training data.
Common mistake Assuming that the learner's accessible measure is automatically the learner's final goal.
What it looks likeSaying that the learner wants to minimize empirical risk simply because empirical risk can be measured.
Why it failsThe learner wants a prediction rule with low true error, but uses information from S because D is unknown.
Do this insteadKeep the goal, low true error, separate from the accessible evaluation, empirical risk.
Common mistake Interpreting relaxed realizability as ignoring errors.
What it looks likeConcluding that errors no longer need to be evaluated once perfect classification is not required.
Why it failsTrue error and empirical risk still measure the errors made by h; the distinction between D and S remains central.
Do this insteadEvaluate the remaining errors using the appropriate source: D for true error and S for empirical risk.
Check Your Understanding
For a prediction rule h, write a short explanation of the difference between its true error and its empirical risk. Your explanation must name the evaluation source for each measure and state which source the learner can directly access.
Hints
- Start by identifying what D supplies for the true-error evaluation.
- Then identify what S supplies for the empirical-risk evaluation.
- End by separating the learner's desired objective from the information available during learning.
A Complete Distinction
Explain what is being measured when a learner evaluates h using D and when the learner evaluates h using S.
- 1Evaluation with D
This measures the true error, or risk, of h on labeled points drawn according to the probability distribution D.
- 2Evaluation with S
This measures empirical risk by using the training data S available to the learner.
- 3Learning implication
The learner wants low true error but cannot directly use D because D is unknown. The learner can use empirical risk because S is available.
True error is the desired distribution-based evaluation; empirical risk is the training-data-based evaluation available to the learner.
Key Takeaways
- 1True error, or risk, evaluates a prediction rule h on labeled points drawn according to the probability distribution D.
- 2Empirical risk evaluates the same prediction rule h using the training data S.
- 3The learner wants low true error but does not know D.
- 4The learner does have access to S, so empirical risk is the directly available evaluation measure.
- 5Relaxing the realizability assumption allows the discussion to focus on measuring and comparing errors even when perfect classification is not required.
At a glance
- True error measures how likely a prediction rule h is to make an error on labeled points drawn according to D.
- Empirical risk measures h's error on the training data S.
- The learner wants to minimize true error but cannot directly access D.
- Because S is available, the learner can directly evaluate empirical risk.
- Relaxing realizability means that evaluation can account for prediction errors without requiring a perfectly correct rule.