Estimation Error
Estimation error is part of the second problem: it concerns the difficulty of accurately estimating the model's true parameters from finite data.
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…
Choosing Among Classifiers
When a learning algorithm produces a poor predictor, the poor result alone does not tell you why it failed. The model may be too limited to represent the underlying relationship, or it may be so complex that it has fitted noise in the available data. Estimation error is part of the second problem: it concerns the difficulty of accurately estimating the model's true parameters from finite data. To diagnose model selection correctly, first ask whether the chosen hypothesis class is too simple or too rich.
A hypothesis class is the set of possible classifiers from which the learning algorithm chooses.
Class Complexity and Containment
Imagine comparing a small hypothesis class with a richer one. The richer class contains more possible classifiers, so it has more flexibility when representing the real classification problem. A small class offers fewer choices. That restriction can make learning more manageable from a finite sample, but it can also prevent the class from containing a good or optimal classifier.
Containment is useful because it makes the two pressures visible. A richer class gives the algorithm more candidates and is less likely to block a good solution. A smaller class gives the algorithm fewer candidates to distinguish among, which can reduce estimation error, but the class itself may impose a larger limitation on what can be represented.
Tracing the Two Errors
Approximation error is caused by the hypothesis class itself. It appears when the class is not rich enough to contain the optimal classifier. Estimation error has a different source: the learner must use a finite sample to choose and estimate a model, and the difficulty of doing that is related to both sample size and hypothesis-class complexity.
| Hypothesis-class choice | Approximation error | Estimation error |
|---|---|---|
| Very small class | May increase because the optimal classifier may not fit | May decrease because there are fewer choices |
| Richer class | May decrease because more classifiers are available | May increase because finite data may not support reliable selection |
The two errors respond in opposite directions when class complexity changes.
Increasing richness does not guarantee lower total error. It removes one possible limitation—the class being unable to express a good classifier—but creates more ways to fit the particular sample. With insufficient data, that extra flexibility can increase estimation error. Moving toward a smaller class reverses the pressure: estimation error may decrease while approximation error may increase.
Underfitting and Overfitting
Diagnosing two poor predictors
Two learning systems produce poor predictors. System A uses a very small hypothesis class. System B uses a very rich class and closely follows irregularities in its sample. What kind of limitation should you investigate in each system?
- 1Inspect System A
Because the class is very small, it may be unable to contain the optimal classifier. Its main risk is high approximation error.
- 2Name the behavior
A model that is too simple is associated with underfitting.
- 3Inspect System B
Because the class is very rich, it has many ways to fit the particular sample. With finite data, its estimation may be unreliable.
- 4Name the behavior
A model that is too complex and fits noise is associated with overfitting.
- 5Compare the diagnoses
The two poor results have different likely causes: System A is limited by what it can represent, while System B is at risk of being too closely tied to sample-specific noise.
System A illustrates underfitting and a possible approximation-error problem. System B illustrates overfitting and a possible estimation-error problem.
Balancing the Selection
Model selection seeks a hypothesis class whose approximation error is not excessively high while its estimation error remains reasonable. A class that is too small may fail to express the real classification problem. A class that is too rich may offer so many alternatives that finite data cannot support reliable estimation. The goal is therefore not maximum simplicity or maximum richness, but a useful balance between the two sources of error.
In theory, the ideal hypothesis class would contain only the Bayes optimal classifier. That would avoid choosing among unnecessary alternatives. In practice, this class is generally unavailable because the Bayes optimal classifier depends on the underlying distribution, and that distribution is unknown. If the distribution were already known, there would be little need for learning. This is why practical model selection relies on a reasonable balance rather than a theoretically perfect class.
Using Prior Knowledge
Prior knowledge about the problem can guide the design of a hypothesis class. The knowledge does not need to provide a complete description of the optimal classifier. Even a reasonable conjecture about the structure of the classification problem can help produce a class with acceptable approximation and estimation errors.
The source discussion uses a rectangle to illustrate this principle, not as a universally correct shape for every classification problem. Its role is to show that domain knowledge can motivate a particular class when the optimal classifier is unknown. A useful class is one whose structure is plausible for the problem while still keeping estimation error reasonable.
Common Diagnostic Mistakes
Common mistake Assuming the richest hypothesis class must be best.
What it looks likeChoosing a very rich class only because it contains many possible classifiers.
Why it failsRichness can reduce approximation error, but finite data may make estimation error larger.
Do this insteadLook for a class that is expressive enough while keeping estimation error reasonable.
Common mistake Treating approximation error and estimation error as the same limitation.
What it looks likeSaying that a small class has high estimation error simply because it performs poorly.
Why it failsA small class may perform poorly because it cannot contain the optimal classifier, which is an approximation-error limitation.
Do this insteadSeparate the class's representational limitation from the difficulty of estimating a model from finite data.
Common mistake Calling every poor predictor overfitting.
What it looks likeIncreasing complexity whenever a model produces a poor result.
Why it failsA poor predictor may be underfitting because it is too simple, or overfitting because it is too complex and fits noise.
Do this insteadFirst determine whether the model is too limited or too closely tied to noise.
Common mistake Assuming that the theoretically ideal class is available in practice.
What it looks likeTrying to choose the class containing only the Bayes optimal classifier without knowing the underlying distribution.
Why it failsThe Bayes optimal classifier depends on an unknown distribution.
Do this insteadUse prior knowledge and seek a practical balance between the two errors.
Practice Diagnosis
A learning algorithm uses a class with very few possible classifiers and produces a poor predictor. Explain which error may be high and whether the behavior is associated with underfitting or overfitting. Then describe what risk appears if you replace it with a very rich class while keeping the available sample finite.
Hints
- Ask whether the small class can contain the optimal classifier.
- Then ask what many additional classifier choices do to estimation from finite data.
- Use the terms approximation error, estimation error, underfitting, and overfitting.
What do you think happens?
If a hypothesis class becomes richer, what is the expected pressure on approximation error and estimation error?
Reveal answer
Approximation error may decrease while estimation error may increase.
A richer class is less likely to block a good classifier, but its additional flexibility creates more ways to fit a finite sample. The resulting estimation error may therefore increase.
Key Takeaways
- 1A hypothesis class is the set of classifiers from which the learning algorithm chooses.
- 2Approximation error comes from a class that is not rich enough to contain the optimal classifier.
- 3Estimation error is related to finite sample size and hypothesis-class complexity.
- 4A small class may cause underfitting and higher approximation error, while a very rich class may cause overfitting and higher estimation error.
- 5Good model selection balances expressive power with reliable estimation and uses prior knowledge when available.
At a glance
- Approximation error measures a limitation in what the chosen hypothesis class can capture.
- Estimation error is connected to finite data and the complexity of the hypothesis class.
- Increasing class richness may lower approximation error but may raise estimation error.
- Underfitting is associated with models that are too simple; overfitting is associated with models that are too complex and fit noise.
- Model selection seeks a practical balance, guided where possible by prior knowledge about the problem.