Proof. Observe that for each n, H (n; m) = H(nm) where H is the collection of all Boolean functions on sequences x1; : : : ; xnm obtained by first choosing n functions h1; : : : ; hn from some H 2 H , and then applying h1 to the first m examples, h2 to the second m examples and so on. By the definition of dH (n), VCdim(H) = ndH (n), hence the result follows from Lemma 9 applied to H.

If one follows the proof of Theorem 4 (in particular the proof of Theorem 18 in Appendix A) then it is clear that for all  > 0, C(H n l

; ") may be replaced by H (n; 2m) in the Boolean case. Making this replacement in Theorem 18, and using the choices of ;  from the discussion following Theorem 26, we obtain the following bound on the probability of large deviation between empirical and true performance in this Boolean setting. Theorem 12. Let P = (P1; : : : ; Pn) be n *probability distributions on* X - f1g and let z *be an*
(n; m)-sample generated by sampling m *times from* X  f1g according to each Pi*. Let* H = fHg be any permissible Boolean hypothesis space family. For all 0 <   1,

$$\operatorname*{Pr}\left\{\mathbf{z}\colon\exists\mathbf{h}\in\mathbb{H}^{n}\colon\,\,\mathrm{er}_{\mathbf{P}}(\mathbf{h})\geq\mathrm{er}_{\mathbf{z}}(\mathbf{h})+\varepsilon\right\}\leq4\Pi_{\mathbb{E}}{\big(}n,2m{\big)}\exp{\big(}-\epsilon^{2}n\,m/64{\big)}.$$

nm=64): (46)
Corollary 13. Under the conditions of Theorem 12, if the number of examples m *of each task* satisfies

$$(46)$$
$$m\,\geq\frac{88}{\varepsilon^{2}}\left[2d_{\mathbb{H}}\left(n\right)\log\frac{2\,2}{\varepsilon}+\frac{1}{n}\log\frac{4}{\delta}\right]$$

$$(47)$$

then with probability at least 1  Æ (over the choice of z), any h 2 H n*will satisfy*

$$\imath/64)\,\leq\,\delta,$$

erP(h)  ^erz(h) + " (48)
Proof. Applying Theorem 12, we require

```
4H (n; 2m) exp(
         2
          
          nm=64)  Æ;
                

```

which is satisfied if

2  dH (n) log 2em dH (n) + 1 n log 4 Æ  m  64

; (49)

where we have used Lemma 11. Now, for all a  1, if

$$m\,=\,\left(1+{\frac{1}{e}}\right)\,a\,\log\,\left(1+{\frac{1}{e}}\right)\,a\,,$$

$$(49)$$

then m  a log m. So setting a = 64dH (n)="2, (49) is satisfied if

$$m\geq\frac{88}{\varepsilon^{2}}\left[2d_{\mathbb{H}}\left(n\right)\log\frac{22}{\varepsilon}+\frac{1}{n}\log\frac{4}{\delta}\right]\,.$$

$\blacksquare$