Trjtdtk

I am currently working on the proof of Theorem 3.1 in the book "Foundations of Machine Learning" (page 35, First edition), and there is a key trick used in the proof (equation 3.10 and 3.11):

$$beginalign*
&E_S,S'left[undersetg in mathcalGtextsupfrac1msum_i=1^m g(z'_i)-g(z_i)right]=E_boldsymbolsigma,S,S'left[undersetg in mathcalGtextsupfrac1msum_i=1^m sigma_i(g(z'_i)-g(z_i))right] \
&textwhere Bbb P(sigma_i=1)=Bbb P(sigma_i=-1)=frac12
endalign*$$

It is also shown in the lecture pdf page 8 in this link:
https://cs.nyu.edu/~mohri/mls/lecture_3.pdf

This is possible because $z_i$ and $z'_i$ can be swapped. My question is, why can we swap $z_i$ and $z'_i$? In the book, it says this is possible because "we are taking the expectation over all possible $S$ and $S'$, it will not affect the overall expectation." Unfortunately, I don't understand the meaning or intuition of this part.

Thank you very much for reading the question and for your time!

This requires hell of a derivation, but I liked the question :)

My question is, why can we swap $z_i$ and $z'_i$?

The key insight is that notation $S sim mathcalD^m$ is equivalent to $Z_1 sim mathcalD, cdots, Z_m sim mathcalD$. This translates to
$$E_S,S'[.]=E_Z_1,cdots,Z_m,Z'_1,cdots,Z'_m[.]$$
which remains the same by reordering the $Z$s.

Therefore the swap argument can be shown by

1. Singling out an arbitrary term $k$ from $sum_i=1^m$,


2. Switching $E_Z_k,Z'_k$ to $E_Z'_k,Z_k$, and


3. Renaming the variables.

That is,
$$beginalign*
&E_S,S'left[undersetg in mathcalGtextsupfrac1msum_i=1^m g(z'_i)-g(z_i)right] \
&oversettextexpand=
E_colorblueZ_1,cdots,Z_m,Z'_1,cdots,Z'_mleft[undersetg in mathcalGtextsupfrac1msum_i=1^m g(z'_i)-g(z_i)right]\
&oversettextseparate=
E_cdots,Z_k,cdots,Z'_k,cdotsleft[undersetg in mathcalGtextsup frac1mleft(colorblueg(z'_k)-g(z_k)+sum_i=1; neq k^m g(z'_i)-g(z_i)right)right] \
&oversettextswitch=
E_cdots,colorblueZ'_k,cdots,colorblueZ_k,cdotsleft[undersetg in mathcalGtextsupfrac1mleft(g(z'_k)-g(z_k)+sum_i=1; neq k^m g(z'_i)-g(z_i)right)right] \
&oversettextreorder=
E_cdots,Z'_k,cdots,Z_k,cdotsleft[undersetg in mathcalGtextsupfrac1mleft(colorblue-(g(z_k)-g(z'_k))+sum_i=1; neq k^m g(z'_i)-g(z_i)right)right] (*)
endalign*$$
Now by renaming $Z_k leftrightarrow Z'_k$, and thus $z_k leftrightarrow z'_k$ in $(*)$ we have:
$$beginalign*
&E_S,S'left[undersetg in mathcalGtextsupfrac1msum_i=1^m g(z'_i)-g(z_i)right] \
&oversettextrename= E_cdots,colorblueZ_k,cdots,colorblueZ'_k,cdotsleft[undersetg in mathcalGtextsupfrac1mleft(-(g(colorbluez'_k)-g(colorbluez_k))+sum_i=1; neq k^m g(z'_i)-g(z_i)right)right]\
&oversettextcollapse= E_S,S'left[undersetg in mathcalGtextsupfrac1mleft(-(g(z'_k)-g(z_k))+sum_i=1; neq k^m g(z'_i)-g(z_i)right)right]\
endalign*$$

which corresponds to $boldsymbolsigma=(sigma_1=1,cdots,sigma_k = -1,cdots,sigma_m=1)$.

We have proved this equality by switching the sign of arbitrary index $k$. Therefore, by defining
$$f(boldsymbolsigma):=E_S,S'left[undersetg in mathcalGtextsupfrac1msum_i=1^m sigma_i(g(z'_i)-g(z_i))right]$$
we have shown that
$$forall boldsymbolsigma_1, boldsymbolsigma_2,f(boldsymbolsigma_1)=f(boldsymbolsigma_2).$$
For example:
$$beginalign*
f(boldsymbol1)&=f(sigma_1=1,cdots,sigma_k=1, cdots,sigma_m=1)\
&=f(sigma_1=1,cdots,sigma_k=-1, cdots,sigma_m=1)
endalign*$$
Knowing that there is $2^m$ equi-probable vectors $boldsymbolsigma_i$, we finally have
$$beginalign*
E_S,S'left[undersetg in mathcalGtextsupfrac1msum_i=1^m g(z'_i)-g(z_i)right]&=f(boldsymbol1) \
&=frac12^m f(boldsymbolsigma_1)+cdots+frac12^mf(boldsymbolsigma_2^m)\
&=E_boldsymbolsigma[f(boldsymbolsigma)] \
&=E_boldsymbolsigma,S,S'left[undersetg in mathcalGtextsupfrac1msum_i=1^m sigma_i(g(z'_i)-g(z_i))right]
endalign*$$
$square$