
## 2.4 Uniform Convergence For Bias Learners

Now we have enough machinery to state the main theorem. In the theorem the hypothesis space family is required to be *permissible*. Permissibility is discussed in detail in Appendix D, but note that it is a weak measure-theoretic condition satisfied by almost all "real-world" hypothesis space families. All logarithms are to base e.

Theorem 2. Suppose X and Y are separable metric spaces and let Q be any probability distribution on P, the set of all distributions on X - Y . Suppose z *is an* (n; m)-sample generated by sampling n times from P according to Q *to give* P1; : : : ; Pn, and then sampling m *times from each* Pi *to generate* zi = f(xi1; yi1); : : : ; (xim; yim)g, i = 1; : : : ; n*. Let* H = fHg be any permissible hypothesis space family. If the number of tasks n *satisfies*

$$n\,\geq\,\operatorname*{max}\left\{{\frac{256}{\varepsilon^{2}}}\log{\frac{8C\left({\frac{\varepsilon}{32}},\,\mathbb{H}^{*}\right)}{\delta}},{\frac{64}{\varepsilon^{2}}}\right\},$$

$$(21)$$
$$(22)$$
$\mathcal{U}\mathcal{H}\in\mathbb{H}$ *will satisfy*
$$(23)$$
$\square$
and the number of examples m *of each task satisfies*

$$m\,\geq\,\operatorname*{max}\left\{{\frac{25\,6}{n\varepsilon^{2}}}\log{\frac{8C\left({\frac{\varepsilon}{32}},\,\|\mathbb{H}_{l}^{n}\right)}{\delta}},{\frac{64}{\varepsilon^{2}}}\right\},$$

then with probability at least 1  Æ *(over the* (n; m)-sample z), all H 2 H *will satisfy*

$$\operatorname{er}_{Q}({\mathcal{H}})\leq\operatorname{\hat{e}}_{\mathbf{z}}({\mathcal{H}})+\varepsilon$$
erQ(H)  ^erz(H) + " (23)
 *Proof.* See Appendix A. 
There are several important points to note about Theorem 2:

1. Provided the capacities C ("; H ) and C("; H n l

) are finite, the theorem shows that any bias learner that selects hypothesis spaces from H can bound its generalisation error erQ(H) in terms of ^erz(H) for sufficiently large (n; m)-samples z. Most bias learner's will not find the exact value of ^erz(H) because it involves finding the smallest error of any hypothesis h 2 H
on each of the n training sets in z. But any upper bound on ^erz(H) (found, for example by gradient descent on some error function) will still give an upper bound on erQ(H). See Section 3.3.1 for a brief discussion on how this can be achieved in a feature learning setting.

2. In order to learn bias (in the sense that erQ(H) and ^erz(H) are close uniformly over all H 2 H ), both the number of tasks n and the number of examples of each task m must be sufficiently large. This is intuitively reasonable because the bias learner must see both sufficiently many tasks to be confident of the nature of the environment, and sufficiently many examples of each task to be confident of the nature of each task.

3. Once the learner has found an H 2 H with a small value of ^erz(H), it can then use H to learn novel tasks P drawn according to Q. One then has the following theorem bounding the sample complexity required for good generalisation when learning with H (the proof is very similar to the proof of the bound on m in Theorem 2).