Approximation Error
The richest possible hypothesis class is not automatically the best one. A useful class must be flexible enough to avoid a large approximation error while remaining manageable enough to keep estimation error reasonable.
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 Choice Behind Learning
A learning algorithm does not choose from every classifier that could possibly exist. It chooses from a hypothesis class: the set of possible classifiers made available to the algorithm. That design choice creates a trade-off. If the class is too small, it may be unable to represent the classifier needed for the problem. If it is too rich, the available data may not be sufficient to choose reliably among all its possibilities.
The richest possible hypothesis class is not automatically the best one. A useful class must be flexible enough to avoid a large approximation error while remaining manageable enough to keep estimation error reasonable.
Two Sources of Difficulty
Approximation error comes from the hypothesis class itself. It occurs when the class is not rich enough to contain the optimal classifier. Even if the learning algorithm had ideal information for choosing within that class, the desired classifier would still be unavailable.
Estimation error comes from having to learn with a finite sample and from the complexity of the hypothesis class. A richer class offers more possible classifiers, so the available sample may not be sufficient to choose reliably among them. In the source discussion, this difficulty is associated with overfitting.
A Class That Is Too Simple
When flexibility is missing
Imagine a classification problem whose optimal classifier is not included in a small hypothesis class.
- 1Restrict the choices
The learning algorithm can select only from the classifiers in the small class.
- 2Search within the class
The algorithm may choose the best available classifier, but the optimal classifier remains unavailable.
- 3Identify the remaining error
Because the class cannot contain the optimal classifier, the class restriction creates approximation error.
A small hypothesis class can reduce estimation error while increasing approximation error.
The important point is that more data alone does not change what the class can represent. If the optimal classifier is absent from the class, the representation limitation remains. This is why an overly restricted class may lead to underfitting.
A Class That Is Too Rich
When flexibility creates uncertainty
Imagine expanding a hypothesis class so that it contains many additional classifiers.
- 1Add possible classifiers
The learner gains more flexibility and is less likely to be blocked by the class when searching for a good solution.
- 2Increase the number of plausible fits
The same flexibility creates more ways to fit the particular finite sample.
- 3Check the trade-off
The richer class may lower approximation error, but estimation error might increase if the sample is not sufficient to choose reliably.
A rich hypothesis class can reduce approximation error while increasing estimation error and the risk of overfitting.
Complexity Trade-Off
| Hypothesis-class choice | Approximation error | Estimation error | Typical risk |
|---|---|---|---|
| Very small | May increase because the optimal classifier may be absent | Tends to decrease because there are fewer choices | Underfitting |
| Very rich | Tends to decrease because more classifiers are available | May increase because finite data may not distinguish the choices reliably | Overfitting |
| Reasonably designed | Not excessively high | Reasonable | A practical balance |
The two errors respond in opposite ways to changes in hypothesis-class richness.
Increasing class richness gives the learner more possible classifiers. Approximation error therefore decreases because the class is less likely to block a good solution. At the same time, estimation error might increase because it depends on both finite sample size and hypothesis-class complexity. Decreasing richness produces the reverse pressure.
Using Prior Knowledge
Choosing a hypothesis class is not only a contest between the smallest and richest possible classes. Prior knowledge about the problem can guide which classifiers should be included. Even a reasonable conjecture about the structure of the problem can help produce a class whose approximation error is not excessively high while its estimation error remains reasonable.
A domain-informed class
Suppose prior knowledge suggests that the classification problem has a particular structure, but the optimal classifier is unknown.
- 1Use the available knowledge
Design a hypothesis class that includes classifiers consistent with the suspected structure.
- 2Avoid unnecessary alternatives
Do not automatically include every possible classifier merely because a richer class might contain the optimum.
- 3Balance the errors
Evaluate the design by asking whether it avoids excessive approximation error while keeping estimation error reasonable.
Prior knowledge helps define a practical class without requiring a complete description of the optimal classifier.
Practice Check
A learner moves from a small hypothesis class to a richer one. State the likely direction of change for approximation error and the possible direction of change for estimation error. Then explain why neither a very small nor a very rich class is automatically best.
Hints
- Ask first whether the richer class contains more possible classifiers.
- Separate the class's ability to represent the optimal classifier from the finite sample's ability to support a reliable choice.
- Use the terms underfitting and overfitting only after explaining the underlying trade-off.
What do you think happens?
If a class becomes richer, which error is most directly expected to decrease, and which error might increase?
Reveal answer
Approximation error decreases; estimation error might increase
A richer class is less likely to exclude the optimal classifier, but its additional choices can make reliable learning from a finite sample more difficult.
Key Takeaways
- 1A hypothesis class is the set of possible classifiers from which the learning algorithm chooses.
- 2Approximation error occurs when the class is not rich enough to contain the optimal classifier.
- 3Estimation error is related to finite sample size and hypothesis-class complexity.
- 4A small class tends to reduce estimation error but may increase approximation error; a rich class tends to reduce approximation error but may increase estimation error.
- 5Prior knowledge can guide the design of a class that balances representational flexibility with reliable learning.
At a glance
- Approximation error is caused by a hypothesis class that cannot represent the optimal classifier.
- Estimation error is connected to finite sample size and the complexity of the hypothesis class.
- Increasing class richness usually lowers approximation error but may raise estimation error.
- A practical hypothesis class should balance flexibility with reliable learning.
- Prior knowledge can help select a useful class even when the optimal classifier is unknown.