Realizable and Nonrealizable Learning

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.

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.

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.

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.

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.

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.

Mistakes in Case Selection

• Using the same value of c in both learning cases.

  The finite-class analysis specifies c = 1 for realizable learning and c = 2 for nonrealizable learning.

  Fix: Determine the learning case before substituting c.

• Treating a large finite class as if it automatically required a proportionally large sample.

  The class-size dependence is logarithmic rather than directly proportional.

  Fix: Look for the logarithmic class-size contribution when interpreting the bound.

• Calling a class finite without identifying what is being counted.

  The analysis begins by identifying the hypothesis class and its size.

  Fix: Name H and count the available hypotheses to obtain |H|.

• Ignoring ε and δ when applying the bound.

  The finite-class bound depends on the class size, accuracy parameter ε, confidence parameter δ, and the learning case.

  Fix: Record |H|, ε, δ, and c before applying the bound.

Check Your Reasoning

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.