Exercise : $($for correct symbols see the picture$)$ Fix $Hsub{Y}^x$ and a loss $l$:hat$(Y)Y[0,1].$ In this exercise we will show that under the

assumption that $l_D(H)$ is small, we can derive stronger sample complexity bounds. In particular,

in the binary setting $($i$.$e$.$ when $Y=$hat$(Y)=\{+-1\}$ and $l$ is the zero$-$one loss$),$ we will sharpen the

sample complexity bound of tilde$(O)(\frac{VC(H)}{lo{n}^2})$ to tilde$(O)(\frac{l_D(H)VC(H)}{lo{n}^2}+\frac{VC(H)}{lon}).$ If the case that $l_D(H)=0,$

$($the so called realizable setting$)$ we get a sample complexity of tilde$(O)(\frac{VC(H)}{lon}).$

Fix Sin$(xY{)}^{2m}.$ Assume for now that $S$ is not random. Suppose we generate from $S$ two

samples $S_1,S_{2}in(xY{)}^m$ as follows. For each $1im,$ w$.$p$.\frac{1}{2}$ we put the $(2i{)}^{\text{'}}\text{'}$th example

in $S_1$ and the $)\text{'}$th example in $S_2,$ and w$.$p$.\frac{1}{2}$ we put the $(2i{)}^{\text{'}}\text{'}$th example in $S_2$ and the

$\text{'}\text{'}$th example in $S_1.$ Fix some $h^{*}$inH, and let hat$(h)inH$ be a function that minimizes $L_{S_1}(hat(h)).$

Show that $L_{S_2}(h)$ is $\sqrt[\phantom{2}]{2L_S(h)}-$SubGaussian and that $L_{S_1}(h^{*})-L_{S_1}(h)$ is $\sqrt[\phantom{2}]{2(L_S(h)+L_S(h^{*}))}-$

SubGaussian. Conclude that if $L_S(h^{*})+lo\frac{n}{2}{L}_S(h)$ then

$Pr(L_{S_2}(h)L_S(h^{*})+lon)e^{-\frac{(L_S(h^{*})-L_S(h)+lon{)}^{2}m}{4L_S(h)}}{e}^{-\frac{lo{n}^{2}m}{16(L_S(h^{*})+lo\frac{n}{2})}}$

Otherwise, if $L_S(h^{*})+lo\frac{n}{2}{L}_S(h)$ show that

$Pr(L_{S_1}(h)L_{S_1}(h^{*}))e^{-\frac{(L_S(h)-L_S(h^{*}){)}^{2}m}{4(L_S(h)+L_S(h^{*}))}}$

$e^{-\frac{lo{n}^{2}m}{16(2L_S(h^{*})+lo\frac{n}{2})}}$

Conclude that

$Pr(L_{S_2}((hat(h)))L_S(h^{*})+lon){}_{2m}(H)e^{-\frac{lo{n}_m^2}{16(2L_S(h^{*})+lo\frac{n}{2})}}$