
## B.1 Bounding C ("; H N L ) From Lemma 28,

$${\mathcal{C}}\left(\varepsilon_{1}+\varepsilon_{2},{\mathcal{G}}_{l}{}^{n}\circ{\overline{{{\mathcal{F}}}}}\right)\leq{\mathcal{C}}\left(\varepsilon_{1},{\mathcal{G}}_{l}{}^{n}\right)\,{\mathcal{C}}_{{\mathcal{G}}_{l}{}^{n}}\left(\varepsilon_{2},{\overline{{{\mathcal{F}}}}}\right)$$

$$(68)$$

and from Lemma 29,

$${\mathcal{C}}\left(\varepsilon_{1},{\mathcal{G}}_{l}^{n}\right)\leq{\mathcal{C}}\left(\varepsilon_{1},{\mathcal{G}}_{l}\right)^{n}\,.$$

: (69)
Using similar techniques to those used to prove Lemmas 28 and 29, CGl n ("; F ) can be shown to satisfy

CGl

n ("2; F)  CGl ("2; F) : (70)
Equations (67), (68), (69) and (70) together imply inequality (34).

## B.2 Bounding C ("; H )

We wish to prove that C ("; H )  CGl ("; F) when H is a hypothesis space family of the form H = fGl Æ f : f 2 F g. Note that each H2 H corresponds to some Gl Æ f , and that

$${\mathcal{H}}^{*}(P)=\operatorname*{inf}_{g\in{\mathcal{G}}_{|}}\operatorname{er}_{P}\left(g\,\circ\,f\right).$$

Any probability measure Q on P induces a probability measure QXY on X - Y , defined by

$$Q_{X\times Y}(S)=\int_{\mathcal{P}}P(\,S)\,d Q(P)$$
$$\left|\operatorname*{inf}_{a\,\in\,A}\,h(a)-\operatorname*{inf}_{a\,\in\,A}\,h^{\prime}(a)\right|\leq\operatorname*{sup}_{a\,\in\,A}\left|h(a\,)-h^{\prime}(a)\right|.$$

```
for any S in the -algebra on X - Y . Note also that if h; h0are bounded, positive functions on an
arbitrary set A, then
                         
                          inf
                             
                          a2A
                              
                              h(a)  inf
                                         
                                      a2A
                                         
                                          h0
                                            (a)
                                               
                                                 sup
                                                       
                                                   a2A
                                                       
                                                       h(a)  h0
                                                                 (a)
                                                                     
                                                                      : (71)

```

Let Q be any probability measure on the space P of probability measures on X - Y . Let H
1 ; H
2 be two elements of H with corresponding hypothesis spaces Gl Æ f1; Gl Æ f2. Then,

$$d_{Q}(\mathcal{H}_{1}^{*},\mathcal{H}_{2}^{*})=\int_{P}\left|\inf_{g\in\mathcal{G}}\,\mathrm{er}_{P}(g\circ f_{1})-\inf_{g\in\mathcal{G}_{1}}\,\mathrm{er}_{P}(g\circ f_{2})\right|\,dQ(P)$$ $$\leq\int_{P}\sup_{g\in\mathcal{G}}\left|\mathrm{er}_{P}(g\circ f_{1})-\mathrm{er}_{P}(g\circ f_{2})\right|\,dQ(P)\qquad\text{(by()above)}$$ $$\leq\int_{P}\int_{X\times Y}\sup_{g\in\mathcal{G}_{1}}\left|g\circ f_{1}(x,y)-g\circ f_{2}(x,y)\right|\,dP(x,y)\,dQ(P)$$ $$=d_{|Q_{X\times Y},\mathcal{G}_{1}|}(f_{1},f_{2}).$$

The measurability of supGl g Æ f is guaranteed by the permissibility of H (Lemma 32 part 4, Appendix D). From dQ(H
1; H
2 )  d[QXY ;Gl℄(f1; f2) we have,

$${\mathcal{N}}\left(\varepsilon,\,\mathbb{H}^{\,*},d_{Q}\right)\leq{\mathcal{N}}\left(\varepsilon,\,{\mathcal{F}},d_{\left|Q_{X\times Y},Q_{i}\right|}\right),$$

; (72)
which gives inequality (35).