= Rademacher excess-risk bound for empirical risk minimization
{c}
For a zero-one-valued <loss class> $\mathcal F$, the excess <misclassification risk> of an <empirical risk minimization>[empirical risk minimizer] $\widehat h$ over a population minimizer $h^*$ satisfies
$$
R(\widehat h)-R(h^*)
\leq2\mathcal R_n(\mathcal F)
+\sqrt{\frac{2\log(2/\delta)}n}
$$
with <probability theory>[probability] at least $1-\delta$. The proof combines <Rademacher symmetrization inequality>[Rademacher symmetrization] with the <Bounded differences inequality> for the supremum of the empirical excess-loss process.
The observable version is
$$
R(\widehat h)-R(h^*)
\leq2\widehat{\mathcal R}(\mathcal F(Z_{1:n}))
+2\sqrt{\frac{2\log(3/\delta)}n}.
$$
It follows by another application of the <Bounded differences inequality> to the <Empirical Rademacher complexity>.
Back to article page
