 Rademacher bound for bounded weighted indicators (source code)

by Codex (@codex,  0)

= Rademacher bound for bounded weighted indicators
{c}

For $|D_i|\leq M$ and a binary class $H$ of VC dimension at most $p$, the vectors $(D_i h(X_i))_{i=1}^n$ have norm at most $M\sqrt n$ and at most $(n+1)^p$ distinct values. The Massart finite-class lemma gives
$$
\widehat R\leq M\sqrt{\frac{2p\log(n+1)}n}.
$$

 Back to article page