
Here (a) uses Lemma REF  with the fact that since every \(g\in \mathcal {H}\Delta \mathcal {H}\)  can be represented as a linear threshold network of depth 2 with 2 hidden units, the VC dimension of \( \mathcal {H}\Delta \mathcal {H}\)  is at most \(2d\)  [1]}, [2]}; (b) uses Hoeffding's inequality in Lemma REF . Similarly, we have
\(\mathcal {F}_t(h) - \mathcal {F}_t(h_*)\le & \mathcal {F}_t(h_*,\widetilde{f}_*) + \mathcal {F}_t(h,\widetilde{h}_*) + \mathcal {F}_s(\widetilde{h}_*,\widetilde{f}_*) + \frac{3}{2}\widehat{d}_{\mathcal {H} \Delta \mathcal {H}}(\mathcal {U}_s,\mathcal {U}_t) + 12\sqrt{\frac{2d\log (2n)+\log (8/\delta )}{n}}\\\le & \mathcal {F}_t(h_*,\widetilde{f}_*) + \widehat{\mathcal {F}}_t(h,\widetilde{h}_*) + \mathcal {F}_s(\widetilde{h}_*,\widetilde{f}_*) + \frac{3}{2}\widehat{d}_{\mathcal {H} \Delta \mathcal {H}}(\mathcal {U}_s,\mathcal {U}_t) \\&+ \sqrt{\frac{\log (8/\delta )}{2n}}+12\sqrt{\frac{2d\log (2n)+\log (8/\delta )}{n}}.\) 
