Theorems 3.3-3.4: a consistent hypothesis from a class of VC dimension d is PAC, with failure ≤ 2Φ_d(2m)2^(−εm/2) and explicit m

Theorem 3.3. Let $C$ be any concept class of VC dimension $d$. Let $L$ be any algorithm that takes as input a set $S$ of $m$ labeled examples of a concept in $C$, and produces as output a concept $h \in C$ that is consistent with $S$. Then $L$ is a PAC learning algorithm for $C$ provided it is given a random sample of $m$ examples from $EX(c, D)$, where $m \ge c_0\big(\tfrac{1}{\epsilon}\log\tfrac{1}{\delta} + \tfrac{d}{\epsilon}\log\tfrac{1}{\epsilon}\big)$ for some constant $c_0 > 0$. Theorem 3.4 is the same with a hypothesis class $H$ of VC dimension $d$ in place of $C$.

Formally, for a class $H$ of measurable hypotheses with $\mathrm{vcDim}(H) \le d$, a measurable target $c$ for which $H$ is well-behaved (the double-sample event is null-measurable), a distribution $D$, $0 < \epsilon < 1$, $0 < \delta < 1$ and $m \ge 8/\epsilon$: (1) the probability that the points of a random sample of $m$ examples fail to form an $\epsilon$-net for the error regions $\{c \,\Delta\, h : h \in H\}$ is at most $2\Phi_d(2m)2^{-\epsilon m/2}$ (the bound of p. 61: $\Pr[A] \le 2\Pr[B]$, and $\Pr[B] \le |\Pi_{\Delta(c)}(S)|\,2^{-\epsilon m/2}$ by the random partition of the double sample); (2) hence every algorithm outputting a hypothesis in $H$ consistent with its sample has error greater than $\epsilon$ with probability at most $2\Phi_d(2m)2^{-\epsilon m/2}$; (3) if moreover $m \ge (4/\epsilon)\log_2(2/\delta)$ and $m \ge (8d/\epsilon)\log_2(13/\epsilon)$, that probability is at most $\delta$ (the explicit constants of Blumer, Ehrenfeucht, Haussler and Warmuth, which instantiate the book's $c_0$); (4) consequently, if $H$ is nonempty, every class $C \subseteq H$ for whose targets $H$ is well-behaved is PAC learnable using $H$. For $H = \emptyset$ no algorithm outputs hypotheses in $H$, so (4) needs $H$ nonempty; the book's classes always are.

Why well-behavedness. The proof bounds the probability that the sample is not an $\epsilon$-net by twice the probability of a double-sample event, and bounds the latter by averaging over the random swaps of the two samples. Both steps integrate over the double sample, so the event must be measurable. Blumer, Ehrenfeucht, Haussler and Warmuth (J. ACM 36, 1989) state the theorem for well-behaved classes for this reason. Without the condition the theorem is false. Take $X = \omega_1$ with the countable–cocountable $\sigma$-algebra and $D$ the probability measure that is $1$ on co-countable sets and $0$ on countable ones. Let $H$ be the final segments $(\alpha, \omega_1)$ together with the empty concept; it has VC dimension $1$ and consists of measurable concepts. For the target $c = \emptyset$, every finite sample misses $(\max S, \omega_1)$, which has weight $1$. So no sample is an $\epsilon$-net, and the consistent learner that outputs $(\max S, \omega_1)$ has error $1$ with probability $1$. The double-sample event fails to be measurable there, because $\{(x, y) : x < y\}$ is not measurable for the product $\sigma$-algebra.