Realizable ERM and Zero-Error Sample Complexity

Why Zero Training Error Needs a Guarantee

In binary classification, a learner may return a classifier that makes no mistakes on the observed sample. That is an exact statement about those observations, not automatically about future data. A classifier can agree with every sampled label while still disagreeing with the population label on a region the sample did not cover.

The realizable setting gives a useful starting point: the class contains at least one classifier whose population error is zero. Consequently, a classifier minimizing empirical error can achieve zero training error. The question is then how many observations make it unlikely that any zero-training-error classifier has population error greater than a chosen tolerance.

In the realizable case, \(\hat R_S(h^*)=0\) with probability one. Thus the minimum empirical risk over \(\mathcal H\) is zero, and every exact empirical risk minimizer has zero empirical error. A zero-error guarantee concerns the risk of such a fit, not whether the fitted classifier is the unique classifier with zero risk.

A Baseline: Finite Classes

For a finite class, a direct union bound gives a simple guarantee. Fix a classifier \(h\) with \(R(h)>\varepsilon\). Its probability of making no mistakes on \(n\) independent observations is \((1-R(h))^n\), which is at most \(\exp(-n\varepsilon)\). Taking a union bound over the class controls the chance that even one high-risk classifier fits the sample perfectly.

Proof. For a fixed \(h\), independence gives

If \(R(h)>\varepsilon\), then

using \(1-u\le e^{-u}\) for \(u\ge0\). There are at most \(|\mathcal H|\) classifiers to consider. Therefore the probability that at least one classifier with risk greater than \(\varepsilon\) has zero empirical error is at most \(|\mathcal H|\exp(-n\varepsilon)\). Outside that event, all zero-error empirical fits have risk at most \(\varepsilon\). Realizability ensures that an exact empirical minimizer is one of those fits. \(\square\)

For a desired failure probability \(\delta\), it is sufficient that

When the class is infinite, its cardinality cannot provide this bound. But on any particular finite sample, classifiers that make identical predictions cannot be distinguished by their sample labels. The growth function measures how many different labelings the class can produce, and can be finite even for an infinite class.

A Growth-Function Bound

The following bound applies to finite or countable measurable classes. Countability ensures that the event of interest is measurable and that, whenever a high-risk zero-error fit exists, one can select the first such fit in a fixed enumeration. The proof compares the observed sample with an independent sample of the same size, then conditions on their pooled observations.

Thus any exact empirical risk minimizer has risk at most \(\varepsilon\) with probability at least \(1-\delta\) whenever \(n\varepsilon\ge8\) and \(2\Pi_{\mathcal H}(2n)2^{-n\varepsilon/2}\le\delta\). The appearance of \(2n\) reflects the proof’s use of two samples.

Proof. Let \(S'\) be an independent sample of size \(n\), and let \(A\) denote the event that some classifier has zero empirical risk on \(S\) and population risk greater than \(\varepsilon\). On \(A\), select the first such classifier \(h\) from an enumeration of \(\mathcal H\). Conditional on \(S\), the number of errors \(h\) makes on \(S'\) has a binomial distribution with mean \(nR(h)>n\varepsilon\). The multiplicative Chernoff bound gives a probability at most \(\exp(-nR(h)/8)\) that this count is below half its mean. Since \(n\varepsilon\ge8\), that probability is at most \(e^{-1}<1/2\). In particular, with conditional probability at least \(1/2\), \(h\) makes at least \(n\varepsilon/2\) errors on \(S'\). Let \(B\) be the event that some classifier has zero errors on \(S\) and at least \(n\varepsilon/2\) errors on \(S'\). It follows that \(P(B)\ge P(A)/2\), so \(P(A)\le2P(B)\).

To bound \(P(B)\), pool the \(2n\) iid observations and regard the assignment of \(n\) of them to \(S\) as a uniformly random split. Conditional on the pooled observations, each classifier induces an error pattern: a vector indicating which of the \(2n\) observations it misclassifies. There are at most \(\Pi_{\mathcal H}(2n)\) such patterns, because the observed labels are fixed and each prediction vector determines one error pattern.

For \(B\) to occur for a given pattern, every error in it must be assigned to \(S'\), while \(S\) receives none of them. If the pattern contains \(m\) errors, this is impossible when \(m>n\). Otherwise its probability is

because each factor \((n-j)/(2n-j)\) is at most \(1/2\). Event \(B\) also requires \(m\ge n\varepsilon/2\), so this probability is at most \(2^{-n\varepsilon/2}\). A union bound over the at most \(\Pi_{\mathcal H}(2n)\) patterns gives \(P(B)\le\Pi_{\mathcal H}(2n)2^{-n\varepsilon/2}\). Combining this with \(P(A)\le2P(B)\) proves the claim. \(\square\)

Worked Examples

What the Guarantee Does—and Does Not—Say

The finite-class bound depends on the number of classifiers; the growth-function bound depends on the number of distinct labelings they can generate on a finite set of inputs. This distinction matters when \(\mathcal H\) is infinite: many classifiers may behave identically on the observed inputs, so the raw cardinality can be uninformative while the growth function still provides a bound.

The guarantee is probabilistic and distribution-free within the realizable setting: it holds for any distribution for which some classifier in \(\mathcal H\) has zero population risk. It does not say that a particular finite sample must contain every region where classifiers disagree, nor that a zero-training-error fit has exactly zero population risk. Instead, it bounds the probability of selecting—or even having available—a zero-error fit whose risk exceeds the chosen tolerance.

Common Mistake

• Wrong reasoning: “The training error is zero, and the problem is realizable, so the fitted classifier has population error zero.” Realizability only guarantees that some member of the class has zero population risk. Other classifiers can also fit the observed sample perfectly while making errors elsewhere.
• Correction: Control the probability that any high-risk classifier is consistent with the sample. The finite-class bound does this through \(|\mathcal H|\); the growth-function bound does it through \(\Pi_{\mathcal H}(2n)\). Both require an explicit sample-size calculation to obtain a stated risk tolerance and confidence level.