VC Dimension generalization bound

SSU

Theorem (Vapnik):
Let $\mathcal{H}\subset \{-1,+1{\}}^{\mathcal{X}}$ with VC dimension$d_{\text{VC}}(\mathcal{H})<\infty$. Let $T_m=\{(x_i,y_i){\}}_{i=1}^m$ be i.i.d. samples. Then for any $\delta \in (0,1)$, with probability at least $1-\delta$:

$$\forall h\in \mathcal{H}:R(h)\le \hat{R}(T_m,h)+4\sqrt{\frac{d_{\text{VC}}\log \frac{2em}{d_{\text{VC}}}+\log \frac{4}{\delta }}{m}}$$

Where:

• $R(h)=\mathbb{E}[[y\ne h(x)]]$ = true risk
• $\hat{R}(T_m,h)=\frac{1}{m}{\sum }_i[[y_i\ne h(x_i)]]$ = empirical risk

Implications:

• Minimize empirical risk
• Control complexity (VC dimension, sample size)