Formal Learning Theory Kernel: Blueprint v1

The proof uses the symmetrization (or “ghost sample”) technique of Vapnik and Chervonenkis  [ .

Step 1: Symmetrization. Draw two independent samples \(S, S' \sim D^m\). We claim that for \(m \geq 8/\varepsilon ^2\),

This follows because if \(|R_D(h) - \hat{R}_S(h)| {\gt} \varepsilon \) for some \(h\), then with probability at least \(1/2\) (by a Chebyshev argument on \(S'\)), the ghost sample satisfies \(|\hat{R}_{S'}(h) - R_D(h)| \leq \varepsilon /2\), and hence \(|\hat{R}_S(h) - \hat{R}_{S'}(h)| {\gt} \varepsilon /2\) by the triangle inequality.

Step 2: Permutation argument. Let \(T = S \cup S'\) be the pooled sample of size \(2m\). Conditioned on \(T\), the partition into \(S\) and \(S'\) is uniformly random among all \(\binom {2m}{m}\) splits. By a union bound over the distinct label patterns that \(\mathcal{H}\) induces on \(T\):

The number of distinct behaviors is at most \(\Pi _\mathcal {H}(2m)\), and for each fixed labeling pattern, \(\hat{R}_S(h) - \hat{R}_{S'}(h)\) is a sum of \(2m\) centered random variables (each \(\pm 1/m\) depending on which half the point falls in).

Step 3: Hoeffding bound. For each fixed label pattern, Hoeffding’s inequality gives

Combining with the Sauer–Shelah bound:

Setting this \(\leq \delta \) and solving for \(m\) gives

Realizable improvement. In the realizable setting, \(R_D(c^*) = 0\), so only one-sided deviations matter: we need \(\Pr [\exists h \in \mathcal{H} : \hat{R}_S(h) = 0 \text{ but } R_D(h) {\gt} \varepsilon ] \leq \delta \). For any fixed \(h\) with \(R_D(h) {\gt} \varepsilon \), the probability that \(h\) is consistent with all \(m\) samples is at most \((1 - \varepsilon )^m \leq e^{-m\varepsilon }\). A union bound over the \(\Pi _\mathcal {H}(m)\) distinct behaviors gives

Setting this \(\leq \delta \) yields \(m = O\! \left(\frac{d\log (d/\varepsilon ) + \log (1/\delta )}{\varepsilon }\right)\), confirming the \(1/\varepsilon \) dependence.