Textbook of AI

Structural risk minimisation (SRM) is the model-selection principle, due to Vapnik, that chooses a hypothesis class $\mathcal{H}$ to minimise

$$\hat R(\theta) + \Omega(|\mathcal{H}|, N, \delta)$$

where $\hat R$ is empirical risk and $\Omega$ is a complexity penalty derived from a generalisation bound (e.g. VC-dimension-based, Rademacher-based).

The principle: choose the smallest model class that fits the data well. Equivalently, balance bias against variance via the complexity penalty.

Implementation strategies:

Nested classes: $\mathcal{H}_1 \subseteq \mathcal{H}_2 \subseteq \ldots \subseteq \mathcal{H}_K$, each with bounded complexity. Choose $k^* = \arg\min_k [\hat R_k + \Omega_k]$. Polynomial regression of varying degree, decision trees of varying depth, neural networks of varying width are nested classes.

Regularisation: rather than nested classes, add a complexity penalty $\lambda \Omega(\theta)$ to the loss. L2 / weight decay penalises $\|\theta\|^2$, an SRM analogue. L1 penalises $\|\theta\|_1$, favouring sparse models.

SVM-flavoured SRM: SVMs simultaneously minimise empirical error (via slack variables) and a margin-based capacity penalty ($\|w\|^2$). The Vapnik analysis shows the SVM's margin gives a generalisation bound regardless of feature-space dimension.

Modern relevance: SRM was the dominant model-selection principle from ~1995-2010. Modern overparameterised neural networks defy classical SRM, they have huge VC dimension and minimal regularisation yet generalise well. The double-descent phenomenon and theory of implicit regularisation by SGD are partial replacements for classical SRM in the deep-learning regime.