Structural risk minimization

SSU

Algorithm based on VC Dimension generalization bound.

Algorithm:

1. Construct nested hypothesis classes:

$$H_1\subset H_2\subset \cdots \subset H_K$$

2. Apply ERM on each class:

$$h_i=\arg \underset{h\in H_i}{\min }\hat{R}(T_m,h)$$

3. Select class minimizing the VC generalization bound:

$$i^{\ast }=\arg \underset{i}{\min }\hat{R}(T_m,h_i)+ϵ(m,H_i,\delta )$$

4. Output $h_{i^{\ast }}$

SRM balances empirical risk and model complexity (VC dimension). It operationalizes PAC-learning guarantees using finite-sample VC bounds.