
## A.2 Proof Of Theorem 2

Another piece of notation is required for the proof. For any hypothesis space H and any probability measures P = (P1; : : : ; Pn) on Z, let

$${\mathrm{\acute{e r}}}_{\mathbf{P}}({\mathcal{H}}):={\frac{1}{n}}\sum_{i=1}^{n}\operatorname*{inf}_{h\in{\mathcal{H}}}\operatorname{er}_{P_{i}}(h).$$

Note that we have used ^erP(H) rather than erP(H) to indicate that ^erP(H) is another empirical estimate of erQ(H).

With the (n; m)-sampling process, in addition to the sample z there is also generated a sequence of probability measures, P = (P1; : : : ; Pn) although these are not supplied to the learner.

This notion is used in the following Lemma, where Prf(z; P) 2 (X - Y )
(n;m)

- Pn
: Ag means
"the probability of generating a sequence of measures P from the environment (P; Q) and then an (n; m)-sample z according to P such that A holds".

## Lemma 23. If

$$\operatorname*{Pr}\left\{\left(\mathbf{z},\mathbf{P}\right)\in\left(X\times Y\right)^{\left(n,m\right)}\times{\mathcal{P}}^{n}:\;\operatorname*{sup}_{\Xi}d_{\nu}\left[\mathrm{{\acute{e}}}_{\mathbf{z}}({\mathcal{H}}),\mathrm{{\acute{e}}}_{\mathbf{P}}({\mathcal{H}})\right]>{\frac{\alpha}{2}}\right\}\leq{\frac{\delta}{2}},$$

$$(62)$$

; (62)
and

$$\operatorname*{Pr}_{\mathbf{P}}\left\{\mathbf{P}\in{\mathcal{P}}^{n}\colon\,\operatorname*{sup}_{\mathbb{R}}d_{\nu}\left[{\hat{\mathrm{er}}}_{\mathbf{P}}({\mathcal{H}}),\operatorname{er}_{Q}({\mathcal{H}})\right]>{\frac{\alpha}{2}}\right\}\leq{\frac{\delta}{2}},$$

; (63)
then

$$\operatorname*{Pr}\left\{\mathbf{z}\in(X\times Y)^{(n\,,m)}\colon\operatorname*{sup}_{\mathbb{E}}d_{\nu}\left[\mathrm{{\acute{e}r}}_{\mathbf{z}}({\mathcal{H}}),\mathrm{{er}}_{Q}({\mathcal{H}})\right]>\alpha\right\}\leq\,\delta.$$

Proof. Follows directly from the triangle inequality for d . We treat the two inequalities in Lemma 23 separately.

## A.2.1 Inequality (62)

In the following Lemma we replace the supremum over H 2 H in inequality (62) with a supremum over h 2 H n.

Lemma 24.

$$\Pr\left\{(\mathbf{z},\mathbf{P})\in(X\times Y)^{(n,m)}\times\mathcal{P}^{n}:\sup_{\mathbb{H}}d_{\nu}\left[\mathrm{er}_{\mathbf{z}}(\mathcal{H}),\mathrm{er}_{\mathbf{P}}(\mathcal{H})\right]>\alpha\right\}$$ $$\leq\Pr\left\{(\mathbf{z},\mathbf{P})\in(X\times Y)^{(n,m)}\times\mathcal{P}^{n}:\sup_{\mathbb{H}}d_{\nu}\left[\mathrm{er}_{\mathbf{z}}(\mathbf{h}),\mathrm{er}_{\mathbf{P}}(\mathbf{h})\right]>\alpha\right\}\.$$

$$(64)$$
