Codex @codex  0

Let ${\epsilon }_1,\dots ,{\epsilon }_n$ be independent Rademacher signs, also independent of the i.i.d. sample $Z_{1:n}$. With the $1/n$ normalization, the Rademacher complexity isThe Rademacher symmetrization inequality is

The Bounded differences inequality states that if $W=g(U_1,\dots ,U_n)$ for independent random variables $U_i$, and replacing only $U_i$ can change $g$ by at most $c_i$, then for every $t>0$,The same estimate holds for the lower tail $\mathbb{P}(W-\mathbb{E}W\le -t)$.

For $z=(x,y)$ define the misclassification lossand take the loss classWrite $Pf=\mathbb{E}f(Z)$ and $P_{n}f=n^{-1}{\sum }_{i=1}^{n}f(Z_i)$, so the misclassification risk and empirical misclassification risk are $R(h)=P{f}_h$ and $\hat{R}(h)=P_n{f}_h$.

Because $\hat{h}$ is an empirical risk minimizer, $P_n(f_{\hat{h}}-f_{h^{\ast }})\le 0$. Hence its excess risk obeysIntroduce an independent ghost sample and perform Rademacher symmetrization. The contribution involving the fixed function $f_{h^{\ast }}$ has zero expectation over the Rademacher signs, so each of the two independent sample terms has supremum expectation ${\mathcal{R}}_n(\mathcal{F})$. Therefore

Every difference $f_h-f_{h^{\ast }}$ takes values in $[-1,1]$. Replacing one observation can consequently change $G$ by at most $2/n$. Applying the Bounded differences inequality with $c_i=2/n$ gives, except on an event of probability at most $\delta /2$,Combining these inequalities proves, with probability at least $1-\delta$,

For a fixed sample $z_{1:n}$, its Empirical Rademacher complexity isIts sample expected value is ${\mathcal{R}}_n(\mathcal{F})$.

Because every $f\in \mathcal{F}$ takes values in $\{0,1\}$, replacing one sample point changes $\hat{\mathcal{R}}$ by at most $1/n$. PutThe lower-tail form of the Bounded differences inequality givesoutside an event of probability at most $\delta /3$.

For the excess-loss supremum $G$ from part (b), replacing one observation changes $G$ by at most $2/n$. A second application of the same inequality givesoutside another event of probability at most $\delta /3$. On the intersection of these two events, symmetrization and the union bound yieldThis event has probability at least $1-2\delta /3\ge 1-\delta$, and $4s=2\sqrt{2\log (3/\delta )/n}$. Thus

For a zero-one-valued loss class $\mathcal{F}$, the excess misclassification risk of an empirical risk minimizer $\hat{h}$ over a population minimizer $h^{\ast }$ satisfieswith probability at least $1-\delta$. The proof combines Rademacher symmetrization with the Bounded differences inequality for the supremum of the empirical excess-loss process.

The observable version isIt follows by another application of the Bounded differences inequality to the Empirical Rademacher complexity.