
## A.1.2 Second Symmetrization

The second symmetrization trick bounds the probability of large deviation between two empirical estimates of the loss (i.e. the right hand side of (56)) by computing the probability of large deviation when elements are randomly permuted between the first and second sample. The following definition introduces the appropriate permutation group for this purpose.

Definition 7. For all integers m; n  1, let (2m;n) denote the set of all permutations  of the sequence of pairs of integers f(1; 1); : : : ; (1; n); : : : ; (2m; 1); : : : ; (2m; n)g such that for all i, 1 i  m, either (i; j) = (m + i; j) and (m + i; j) = (i; j) or (i; j) = (i; j) and (m + i; j) =
(m + i; j).

For any z 2 (X - Y )
(2m;n)
and any  2 (2m;n) , let

$$\begin{array}{c c c c}{{}}&{{z_{\sigma\,\,(1\,,1)}}}&{{}}&{{\cdot\,\cdot\,\cdot}}&{{z_{\sigma\,\,(1\,,n\,)}}}\\ {{}}&{{}}&{{\mathbf{z}_{\sigma}\,\,:=}}&{{\vdots}}&{{}}&{{\mathbf{\ddots}}}&{{}}\\ {{}}&{{}}&{{}}&{{z_{\sigma\,\,(2\,m\,,1)}}}&{{\cdot\,\cdot\,\cdot}}&{{z_{\sigma\,\,(2\,m\,,n\,)}\,.}}\end{array}$$

Lemma 21. Let H = H1      Hn *be a permissible set of functions mapping* (X - Y )
n
*into*
[0; 1℄ *(as in the statement of Theorem 18). Fix* z 2 (X - Y )
(2m;n)
*and let* H^:= ff 1

; : : : ; fM g be an =8*-cover for* (H; dz)*, where* dz(h; h0) := 1 2m P2m i=1 jh(~zi)  h0(~zi)j *where the* ~zi are the rows of z*. Then,*

$$\Pr\left\{\sigma\in\Gamma_{\{2m,n\}}\colon\sup_{\mathcal{H}}d_{\nu}\,\left[\hat{\mathrm{or}}_{\mathbf{z}_{\star}(1)}(\mathbf{h}),\hat{\mathrm{or}}_{\mathbf{z}_{\star}(2)}(\mathbf{h})\right]>\frac{\alpha}{2}\right\}\\ \leq\sum_{i=1}^{M}\Pr\left\{\sigma\in\Gamma_{\{2m,n\}}\colon d_{\nu}\,\left[\hat{\mathrm{or}}_{\mathbf{z}_{\star}(1)}(\mathbf{f}^{i}),\hat{\mathrm{or}}_{\mathbf{z}_{\star}(2)}(\mathbf{f}^{i})\right]>\frac{\alpha}{4}\right\},\tag{58}$$

where each  2 (2m;n) *is chosen uniformly at random.*
Proof. Fix  2 (2m;n) and let h 2 H be such that d

-

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

> =2 (if there is no such h for any  we are already done). Choose f 2 H^such that dz(h; f )  =8. Without loss of generality we can assume f is of the form f = f1      fn. Now,

 dz(h; f ) = P2m i=1    Pn j=1 hj (zij )  fj (zij )    2 mn = P2m i=1   Pn j=1 hj (z(i;j))  fj (z(i;j) )    mn   Pm i=1 Pn j=1 -hj (z(i;j) )  fj (z(i;j))      mn + Pm i=1 Pn j=1 -hj (z(i;j) ) + fj (z(i;j) )     P2m i=m+1 Pn j=1 -hj (z(i;j) )  fj (z(i;j))      + mn + P2m i=m+1 Pn j=1 -hj (z(i;j) ) + fj (z(i;j) )  = d - ^erz(1) (h); ^erz(1)(f )  + d - ^erz (2)(h); ^erz(2) (f )  :

