PAC learning and uniform convergence

In agnostic binary classification, the distribution on labeled examples is arbitrary and the goal is risk within epsilon of the best rule in a fixed hypothesis class. The learner must meet this goal with probability at least one minus delta over its independent training sample, for every allowed distribution. In the realizable setting, a class member has zero population error. A consistent learner then returns a class member with zero training error, but the premise of a zero-risk class member remains essential to the faster argument.

Classes and losses must be fixed independently of the sample used in the theorem. A class chosen after inspecting labels is not automatically covered by a bound that counts only its final size. The learner’s internal randomness, if any, must also be included in the probability space or handled by a conditioning argument. We use finite nonempty classes and measurable deterministic tie breaking for the explicit bounds, avoiding subtleties about measurable suprema and existence of minimizers.

For any one fixed predictor with loss in[0,1], Hoeffding bounds the probability that its empirical and population risks differ by more than a. A union bound over M predictors gives a simultaneous event. The events for different predictors need not be independent: each predictor’s loss sequence is iid across examples, and the union bound needs no independence across predictors. Exact empirical minimization then has class excess at most twice a on that event by the deterministic comparison already established.

Set a equal to epsilon divided by two and solve for n. The resulting sufficient bound grows like log(M/delta) divided by epsilon squared. It is a guarantee from a particular proof, not a claim that its numerical constant is optimal or that every dataset needs that many observations. If the bound is much larger than an available sample, the calculation is inconclusive rather than proof that learning cannot work. Empirical performance and an absent certificate are different statements.

In the realizable binary setting, a hypothesis with population error greater than epsilon is consistent on n independent examples with probability at most $(1-\varepsilon)^n$, bounded by $e^{-n\varepsilon}$. A union bound over all bad hypotheses shows that n at least log(M/delta) divided by epsilon suffices for every consistent class member to have small true error. This argument uses actual zero-one errors and consistency, rather than a two-sided uniform approximation of all risks.

The inverse-accuracy bound should not be used for noisy data merely because an expressive class interpolates its training sample. Interpolation is a fact about observed labels, whereas realizability asserts that some rule in the predetermined class makes no errors on the entire population. Enlarging the class until it fits every sample may simultaneously increase its complexity. The sample-size comparison below therefore compares two theorems under different assumptions, not two interchangeable formulas for the same unrestricted problem.