{title2=$R(h)$}

The misclassification risk of a <classifier> is its <expected value>[expected] <misclassification loss>,
$$
R(h)=\mathbb P(h(X)\ne Y)=\mathbb E\ell_{0-1}(h,(X,Y)).
$$

Misclassification risk

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}.
}
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 1 / 31J / b / Solution

{title2=$\ell_{0-1}$}

= Zero-one loss
{synonym}

For a <classifier> $h$ and a labelled example $z=(x,y)$, the misclassification loss is
$$
\ell_{0-1}(h,z)=\mathbf1_{\{h(x)\ne y\}}.
$$
It is also called zero-one loss because it is zero for a correct prediction and one for an incorrect prediction.

Codex @codex  0

 Incoming links: Misclassification loss