## Formalized Name Symmetrization Bound ## Proof Introduce an independent copy $(Z_1', \ldots, Z_n')$ of $(Z_1, \ldots, Z_n)$, independent of everything else. Since $Z_i'$ is an independent copy of $Z_i$, we have $\mathbb{E}f(Z_i) = \mathbb{E}[f(Z_i') \mid Z_{1:n}]$, so \begin{align*} \sup_{f \in F} \frac{1}{n} \sum_{i=1}^{n} \{f(Z_i) - \mathbb{E}f(Z_i)\} = \sup_{f \in F} \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}[f(Z_i) - f(Z_i') \mid Z_{1:n}]. \end{align*} Apply the key inequality $\sup_{f} \mathbb{E}[V_f \mid Z_{1:n}] \leq \mathbb{E}[\sup_f V_f \mid Z_{1:n}]$ (moving the supremum inside the conditional expectation only makes the bound larger) to obtain \begin{align*} \sup_{f \in F} \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}[f(Z_i) - f(Z_i') \mid Z_{1:n}] \leq \mathbb{E}\left[\sup_{f \in F} \frac{1}{n} \sum_{i=1}^{n} \{f(Z_i) - f(Z_i')\} \,\Bigg|\, Z_{1:n}\right]. \end{align*} Now introduce i.i.d. Rademacher variables $\varepsilon_1, \ldots, \varepsilon_n$ independent of $Z_{1:n}$ and $Z_{1:n}'$. Because each $Z_i - Z_i'$ is symmetric around zero, we have the distributional equality \begin{align*} \sup_{f \in F} \frac{1}{n} \sum_{i=1}^{n} \{f(Z_i) - f(Z_i')\} \stackrel{d}{=} \sup_{f \in F} \frac{1}{n} \sum_{i=1}^{n} \varepsilon_i \{f(Z_i) - f(Z_i')\}. \end{align*} Using the triangle inequality for the supremum: \begin{align*} \sup_{f \in F} \frac{1}{n} \sum_{i=1}^{n} \varepsilon_i \{f(Z_i) - f(Z_i')\} \leq \sup_{f \in F} \frac{1}{n} \sum_{i=1}^{n} \varepsilon_i f(Z_i) + \sup_{g \in F} \frac{1}{n} \sum_{i=1}^{n} (-\varepsilon_i) g(Z_i'). \end{align*} Since $\varepsilon_{1:n} \stackrel{d}{=} -\varepsilon_{1:n}$, both suprema have the same expected value. Taking expectations over $\varepsilon_{1:n}$ and $Z_{1:n}'$ and then over $Z_{1:n}$ yields the bound $2\mathcal{R}_n(F)$.