
## A.1.1 First Symmetrization

An extra piece of notation: for all z 2 (X - Y )
(2m;n)
, let z(1) be the top half of z and z(2) be the bottom half, viz:

z(1) = z11 : : : z1n ......... z(2) = zm+1;1 : : : zm+1;n ......... zm1 : : : zmn z2m;1 : : : z2m;n

The following lemma is the first "symmetrization trick." We relate the probability of large deviation between an empirical estimate of the loss and the true loss to the probability of large deviation between two independent empirical estimates of the loss.

Lemma 20. Let H *be a permissible set of functions from* (X - Y )
n
*into* [0; 1℄ and let P *be a* probability measure on (X - Y )
n
. For all  > 0; 0 <  < 1 and m  2 2

,

$$\Pr\left\{\mathbf{z}\in\left(X\times Y\right)^{\left\lfloor m,n\right\rfloor}:\sup_{\mathcal{H}}d_{\nu}\left[\hat{\mathrm{e}}_{\mathbf{1}}(h),\mathrm{e}_{\mathbf{1}^{\prime}P}(h)\right]>\alpha\right\}$$ $$\leq2\Pr\left\{\mathbf{z}\in Z^{\left\lfloor2\left\lfloor m,n\right\rfloor}:\sup_{\mathcal{H}}d_{\nu}\left[\hat{\mathrm{e}}_{\mathbf{1}\left\lfloor1\right\rfloor}(h),\hat{\mathrm{e}}_{\mathbf{1}\left\lfloor2\right\rfloor}(h)\right]>\frac{\alpha}{2}\right\}.\tag{56}$$

Proof. Note first that permissibility of H guarantees the measurability of suprema over H (Lemma 32 part 5). By the triangle inequality for d , if d

-

^erz(1) (h); erP (h)

>  and d

-

^erz(2)(h); erP (h)

< =2, then d

-

^erz(1) (h); ^erz(2) (h)

> =2. Thus,

$$\Pr\Big{\{}\mathbf{z}\in(X\times Y)^{\{2m,n\}}:\exists h\in\mathcal{H}\colon d_{\nu}\,\left[\hat{\mathrm{e}}_{\mathbf{z}_{1}\{1\}}(h),\hat{\mathrm{e}}_{\mathbf{z}_{2}\{2\}}(h)\right]\,>\frac{\alpha}{2}\Big{\}}\tag{57}$$ $$\qquad\qquad\geq\Pr\Big{\{}\mathbf{z}\in(X\times Y)^{\{2m,n\}}\colon\exists h\in\mathcal{H}\colon d_{\nu}\,\left[\hat{\mathrm{e}}_{\mathbf{z}_{1}\{1\}}(h),\mathrm{e}_{\Gamma_{P}}(h)\right]\,>\,\alpha\text{and}$$ $$\qquad\qquad d_{\nu}\,\left[\hat{\mathrm{e}}_{\mathbf{z}_{2}\{2\}}(h),\mathrm{e}_{\Gamma_{P}}(h)\right]\,<\,\alpha/2\Big{\}}.$$

By Chebyshev's inequality, for any fixed h,

$$\Pr\left\{\mathbf{z}\in\left(X\times Y\right)^{\left(m,n\right)}:d_{\nu}\left[\mathrm{er}_{\mathbf{z}}\left(h\right),\mathrm{er}_{P}\left(h\right)\right]<\frac{\alpha}{2}\right\}$$ $$\geq\Pr\left\{\mathbf{z}\in\left(X\times Y\right)^{\left(m,n\right)}:\frac{\left|\mathrm{er}_{\mathbf{z}}\left(h\right)-\mathrm{er}_{P}\left(h\right)\right|}{\nu}<\frac{\alpha}{2}\right\}$$ $$\geq1-\frac{\mathrm{er}_{P}\left(h\right)\left(1-\mathrm{er}_{P}\left(h\right)\right)}{m\,\nu\alpha^{2}/4}$$ $$\geq\frac{1}{2}$$

as m  2=(2) and erP (h)  1. Substituting this last expression into the right hand side of (57) gives the result.