= Solution
For $z=(x,y)$ define the <misclassification loss>
$$
f_h(z)=\mathbf1_{\{h(x)\ne y\}},
$$
and take the <loss class>
$$
\boxed{\mathcal F=\{f_h:h\in\mathcal H\}.}
$$
Write $Pf=\mathbb Ef(Z)$ and $P_nf=n^{-1}\sum_{i=1}^nf(Z_i)$, so the <misclassification risk> and <empirical misclassification risk> are $R(h)=Pf_h$ and $\widehat R(h)=P_nf_h$.
Because $\widehat h$ is an <empirical risk minimization>[empirical risk minimizer], $P_n(f_{\widehat h}-f_{h^*})\leq0$. Hence its <excess risk> obeys
$$
R(\widehat h)-R(h^*)
\leq G(Z_{1:n}),
\qquad
G(Z_{1:n})
=\sup_{h\in\mathcal H}(P-P_n)(f_h-f_{h^*}).
$$
Introduce an independent ghost sample and perform <Rademacher symmetrization inequality>[Rademacher symmetrization]. The contribution involving the fixed function $f_{h^*}$ has zero expectation over the <Rademacher random variable>[Rademacher signs], so each of the two independent sample terms has supremum expectation $\mathcal R_n(\mathcal F)$. Therefore
$$
\mathbb EG\leq2\mathcal R_n(\mathcal F).
$$
Every difference $f_h-f_{h^*}$ 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 theory>[probability] at most $\delta/2$,
$$
G\leq\mathbb EG+\sqrt{\frac{2\log(2/\delta)}n}.
$$
Combining these inequalities proves, with <probability theory>[probability] at least $1-\delta$,
$$
\boxed{
R(\widehat h)-R(h^*)
\leq2\mathcal R_n(\mathcal F)
+\sqrt{\frac{2\log(2/\delta)}n}.
}
$$
Back to article page
