VC Bounds for Realizable ERM

From Consistency to Population Error

In realizable binary classification, at least one hypothesis in the class predicts the label correctly with probability one. An empirical risk minimizer can therefore fit the observed sample perfectly, but zero training error alone does not say how well it predicts new observations. The VC growth function controls the number of distinct prediction patterns the class can produce, and hence how many different ways a consistent classifier can adapt to the sample.

Let \(\mathcal X\) be a feature space, let \(\mathcal H\) be a class of functions \(h:\mathcal X\to\{0,1\}\), and let \((X,Y)\) have distribution \(P\) on \(\mathcal X\times\{0,1\}\). For \(h\in\mathcal H\), define its population risk and the empirical risk on an iid sample \((X_i,Y_i)_{i=1}^n\) by

A set of \(m\) points is shattered by \(\mathcal H\) if the restrictions of its hypotheses realize every one of the \(2^m\) binary labelings of those points. The VC dimension \(d\) is the largest size of a shattered set, or infinity if there is no largest finite size. The growth function counts the largest number of different prediction patterns the class can make on any \(m\) points.

We assume the relevant events are measurable (for example, \(\mathcal H\) is countable or satisfies the usual separability conditions). A probability statement about all consistent hypotheses requires this condition; without it, the same bound can be stated using outer probability.

The Realizable VC Bound

The central result controls the probability that any hypothesis consistent with the sample has population risk greater than \(\varepsilon\). Consequently, it applies to any measurable ERM selection, including one whose choice among empirical minimizers depends on the data.

Here is the double-sample argument. Write \(A\) for the event that some consistent \(h\) has \(R(h)>\varepsilon\). Draw an independent ghost sample \((X'_i,Y'_i)_{i=1}^n\) from \(P\). For any fixed witness \(h\) to \(A\), the number \(G=\sum_{i=1}^n\mathbf 1\{h(X'_i)\ne Y'_i\}\) has a binomial distribution with mean \(nR(h)>n\varepsilon\). A multiplicative Chernoff bound gives

Thus, conditional on the original sample and a witness to \(A\), the ghost sample has more than \(n\varepsilon/2\) errors for that witness with probability at least \(1/2\). If \(B\) is the event that some \(h\) makes no errors on the original sample and more than \(n\varepsilon/2\) errors on the ghost sample, then \(P(A)\le2P(B)\).

To bound \(P(B)\), regard the \(2n\) observations as pooled and choose \(n\) of them uniformly for the original sample; the remaining \(n\) form the ghost sample. This random split has the same distribution as the two independent samples. For any fixed hypothesis, its error locations among the pooled observations form a trace. If that trace has \(m>n\varepsilon/2\) locations, the probability that the first half avoids all of them is at most \(2^{-m}\): for \(m\le n\), the probability all \(m\) specified locations fall in the second half is

and for \(m>n\) it is zero. On the pooled feature points, the number of distinct error traces is at most \(\Pi_{\mathcal H}(2n)\), since the observed labels are fixed and each hypothesis's errors are determined by its predictions. A union bound over these traces yields

where \(\log 2>1/2\). Combining this with \(P(A)\le2P(B)\) proves the bound. In a realizable problem there is an \(h^*\in\mathcal H\) with \(R(h^*)=0\). It has zero empirical risk almost surely, so every ERM has zero empirical risk almost surely. The event \(R(\hat h)>\varepsilon\) is therefore contained, up to a null event, in \(A\). \(\square\)

Substituting the VC Dimension

The growth function turns the theorem into a bound involving only the VC dimension. For completeness, the Sauer–Shelah estimate can be obtained by induction on the number \(m\) of points. Split the patterns on \(m\) points according to their restrictions to the first \(m-1\). Let \(B\) be the family of restrictions that occur at least once and \(C\) the restrictions that occur with both possible labels at the last point. The original family has \(|B|+|C|\) patterns. The VC dimension of \(B\) is at most \(d\), while \(C\) has VC dimension at most \(d-1\): if it shattered \(d\) points, the two extensions at the last point would make the original family shatter \(d+1\) points. Induction, with the empty set and dimension-zero cases as bases, gives

For \(1\le d\le m\), this sum is at most \((em/d)^d\). Indeed, put \(x=d/m\le1\). Since \(x^j\ge x^d\) for \(j\le d\),

Consequently, for \(d\ge1\), \(d\le2n\), and \(0<\delta\le1/2\), the theorem implies

If the expression inside the minimum is at least one, the assertion is simply the trivial fact that risk is at most one. Otherwise, take \(\varepsilon\) equal to that expression without the minimum: the growth-function bound is at most \(\delta\), and \(n\varepsilon\ge4\log(2/\delta)\ge8\log2\), so the theorem's condition holds. For \(d=0\), all hypotheses agree on every point (a disagreement at one point would shatter a singleton); realizability then gives zero risk almost surely.

The resulting order is \(O((d\log(en/d)+\log(1/\delta))/n)\), for \(1\le d\le2n\). The factor inside the logarithm matters: the displayed Sauer–Shelah substitution gives \(d\log(2en/d)\), which includes a term of order \(d\). It should not be replaced by \(d\log(n/d)\) without an additional restriction on \(n/d\).

Worked Bounds

Why the Growth Function Matters

For a finite class, one can union-bound over its fixed hypotheses. That argument depends on the number of hypotheses being finite and can be very crude when many hypotheses make identical predictions on the observed points. VC theory instead controls the number of distinct patterns on the pooled sample. The ghost sample is essential to this step: it lets us count traces on \(2n\) points while detecting hypotheses that fit one half but make many errors on the other.

The theorem is a high-probability, realizable guarantee; it does not claim that all consistent classifiers have small error on every sample. Its useful range is when \(n\) is large relative to the complexity and the desired error level. If the resulting upper bound exceeds one, the inequality remains valid but gives no informative improvement over the universal risk bound.

• Pitfall: claiming zero empirical risk on every sample. From \(R(h^*)=0\), it does not follow that every conceivable sample avoids every error point. It follows that each sampled observation is correct almost surely, and hence the full finite sample is correct almost surely.
• Pitfall: union-bounding over an infinite class as if it were finite. There may be infinitely many hypotheses even when their number of patterns on a sample is limited. The proof counts pooled-sample traces, not hypotheses themselves.
• Pitfall: dropping the additive contribution inside the rate. Sauer–Shelah gives \(d\log(2en/d)\), not \(d\log(n/d)\) uniformly over \(n\ge d/2\). In particular, at \(n=d\) the former is positive while the latter vanishes.