Realizable and Nonrealizable Learning

A finite-class analysis follows a short chain: identify H, determine |H|, identify whether learning is realizable or nonrealizable, and then substitute the matching value of c into the finite-class bound.

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

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 ~ D^{^m} 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 L_{_S} 0.0617). Lowest average L_{_D}(h_{_S}): 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…

The Choice Before the Bound

When analyzing empirical risk minimization over a finite hypothesis class, the first important question is not how many examples you have. It is which learning case you are in. If some hypothesis in the class achieves zero training error in the intended realizable setting, use c = 1. If every hypothesis makes errors in the nonrealizable setting, use c = 2. The same class can therefore receive different sample-complexity treatment depending on the learning case.

Key point

What Makes a Class Finite

A finite hypothesis class is a class containing a limited number of available predictors. Its hypotheses may be different rules, models, or predictors, but the total number of possibilities is finite. We write the class as H and its number of hypotheses as |H|. The finite-class analysis uses this count to bound how many examples are sufficient for learning.

One common reason a class is finite is that the representations used to describe its hypotheses are bounded. If only a limited collection of representations is allowed, only a limited collection of predictors can be formed. The analysis does not require the class to be small in an everyday sense; it requires the number of hypotheses to be limited.

How can bounded representations produce a finite set of possible predictors?

In the real world

Generated example: suppose a learning problem permits only a fixed list of candidate predictors. The class is finite because each candidate can be counted, and the total count is |H|. The important step is not to estimate the class informally but to identify the number of available hypotheses.

Candidate Rules You Can Count

Generated example: consider a class made from a finite list of candidate threshold rules. Each candidate threshold defines one hypothesis, so the class consists of the individual rules in that list. If the list contains a limited number of candidates, the resulting hypothesis class is finite and its size is the number of candidates.

How can individual hypotheses in a finite class be enumerated?

Key point

The threshold example is finite because the candidate rules are restricted to a limited list. The finite-class result applies after the available hypotheses have been identified and counted.

Realizable Versus Nonrealizable Learning

In the realizable case, the learning setting assumes that some hypothesis achieves zero training error. In the nonrealizable case, every hypothesis makes errors, so zero training error is not available within the class. The finite-class analysis distinguishes these cases with the constant c: c = 1 for realizable learning and c = 2 for nonrealizable learning.

How do the assumptions, error guarantees, and required sample-size calculations differ between realizable and nonrealizable learning?

Feature	Realizable case	Nonrealizable case
Hypothesis assumption	Some hypothesis achieves zero training error	Every hypothesis makes errors
Value of c	1	2
Use of the finite-class bound	Substitute c = 1	Substitute c = 2

The same finite hypothesis class can be analyzed differently after the learning case is identified.

Applying the Finite-Class Bound

The finite-class sample-complexity bound uses the size of the hypothesis class, the target accuracy ε, the confidence parameter δ, and a case-dependent constant c. The source specifies c = 1 for realizable learning and c = 2 for nonrealizable learning. Because the exact displayed equation is not included in the source pack, the safe application procedure is to identify every input and substitute the correct c without replacing the bound with an invented formula.

Worked example

Selecting the Correct Case

Generated example: a finite class H contains 1,000 hypotheses. The requested accuracy is ε and the requested confidence is δ. Determine which case constant belongs in the finite-class sample-complexity bound when a hypothesis achieves zero training error, and when no hypothesis has zero training error.

1
Identify the class size
The class-size input is |H| = 1,000.
2
Identify the learning case
If some hypothesis achieves zero training error, the setting is realizable. If every hypothesis makes errors, the setting is nonrealizable.
3
Select c
Use c = 1 in the realizable case and c = 2 in the nonrealizable case.
4
Substitute the remaining inputs
Use the identified |H|, the requested ε, the requested δ, and the selected value of c in the finite-class bound.

Result

The class size is the same in both analyses, but the case constant changes from c = 1 to c = 2 when moving from realizable to nonrealizable learning.

What sequence of decisions is needed before using the finite-class sample-complexity bound?

Why Class Size Matters Mildly

The important structural feature of the finite-class bound is the logarithm around the class size. When |H| grows, the sample complexity does not grow in direct proportion to the number of hypotheses. Instead, the contribution from the class size grows logarithmically. This is why even a very large finite class can have a comparatively mild contribution to the number of required samples.

What happens to the class-size contribution when the number of hypotheses becomes very large?

Worked example

Reading a Large Class-Size Contribution

Generated example: suppose a displayed finite-class bound contains a class-size contribution represented by 10,000 rather than by 2^10,000. What lesson does this illustrate?

1
Compare the quantities
The number 2^10,000 is the size of a very large class in this example, while 10,000 is its logarithmic contribution in the displayed bound.
2
Interpret the bound
The sample-complexity contribution is based on the logarithm of the class size, not on the full class size itself.

Result

A finite class can contain an extremely large number of predictors while contributing a comparatively mild class-size term to the sample complexity.

Mistakes in Case Selection

Common mistake
Using the same value of c in both learning cases.
What it looks like
Applying c = 1 even when every hypothesis makes errors.
Why it fails
The finite-class analysis specifies c = 1 for realizable learning and c = 2 for nonrealizable learning.
Do this instead
Determine the learning case before substituting c.
Common mistake
Treating a large finite class as if it automatically required a proportionally large sample.
What it looks like
Assuming that doubling the number of hypotheses doubles the class-size contribution in the bound.
Why it fails
The class-size dependence is logarithmic rather than directly proportional.
Do this instead
Look for the logarithmic class-size contribution when interpreting the bound.
Common mistake
Calling a class finite without identifying what is being counted.
What it looks like
Saying that a collection of predictors is finite without identifying H or |H|.
Why it fails
The analysis begins by identifying the hypothesis class and its size.
Do this instead
Name H and count the available hypotheses to obtain |H|.
Common mistake
Ignoring ε and δ when applying the bound.
What it looks like
```
Using only |H| and c.
```
Why it fails
The finite-class bound depends on the class size, accuracy parameter ε, confidence parameter δ, and the learning case.
Do this instead
Record |H|, ε, δ, and c before applying the bound.

Check Your Reasoning

MEDIUM

Generated practice: A hypothesis class contains a limited list of predictors. In one analysis, a hypothesis achieves zero training error. In a second analysis, every hypothesis makes errors. For each analysis, identify whether it is realizable or nonrealizable, choose c, and list the other quantities that must be supplied before applying the finite-class sample-complexity bound.

Hints

Start by naming the class H and its size |H|.
Zero training error for some hypothesis identifies the realizable case.
The bound also requires ε and δ.

Your attempt (not saved)

What do you think happens?

A finite hypothesis class is analyzed once in the realizable case and once in the nonrealizable case. Does the value of c stay the same?

Yes, because the hypothesis class is unchanged
No, it is 1 in the realizable case and 2 in the nonrealizable case

Reveal answer

Answer:

No, it is 1 in the realizable case and 2 in the nonrealizable case.

The value of c is determined by the learning case, not only by the identity or size of the hypothesis class.

A Reliable Analysis Routine

1
Identify the hypothesis class H.
2
Count its available hypotheses to determine |H|.
3
Record the requested accuracy ε and confidence parameter δ.
4
Decide whether the setting is realizable or nonrealizable.
5
Set c = 1 for realizable learning or c = 2 for nonrealizable learning.
6
Substitute all identified quantities into the finite-class sample-complexity bound.
7
Interpret the class-size contribution logarithmically rather than as direct proportional growth.

This routine separates two ideas that are easy to confuse: the number of hypotheses and the quality of the learning setting. The number of hypotheses determines |H|, while the realizable or nonrealizable assumption determines c. Keeping those roles separate makes the finite-class analysis systematic.

Key Takeaways

A finite hypothesis class contains a limited number of available predictors, represented by H with size |H|.
Finite-class sample-complexity analysis uses |H|, ε, δ, and a case-dependent constant c.
Use c = 1 for realizable learning and c = 2 for nonrealizable learning.
The class-size contribution is logarithmic, so a very large finite class does not increase the bound in direct proportion to its number of hypotheses.
A reliable workflow is to identify H, count |H|, determine the learning case, choose c, and then apply the bound.

Related concepts

More concepts starting with R