Structural Risk Minimization

Structural Risk Minimization, or SRM, addresses a model-selection problem: should learning be restricted to one hypothesis class, or should it compare several classes with different levels of complexity? The central idea is to prepare a sequence of hypothesis classes and select both a class and a hypothesis by minimizing a bound on true risk. This connects two related ideas. At the class level, nonuniform learnability is characterized by a countable union of agnostic PAC learnable classes. At the model-selection level, SRM compares empirical performance with a complexity term.

For a binary-classification hypothesis class H, nonuniform learnability holds if and only if H can be written as a countable union of agnostic PAC learnable hypothesis classes. In one direction, if H is nonuniformly learnable, then H has this countable-union structure. In the other direction, if H can be written as such a countable union, then H is nonuniformly learnable. Because both directions are included, this is a characterization rather than only a sufficient condition.

The theorem changes the question we ask. Instead of trying to treat H as one indivisible class, inspect whether it can be decomposed into a sequence of simpler component classes. The components need to be agnostic PAC learnable, and the overall assembly must be countable. The theorem does not say merely that one convenient subclass is learnable; it describes the form required for the complete class H.

For binary hypothesis classes, agnostic PAC learnability is characterized by finite VC dimension. Thus, when checking the components in a countable-union description, finite VC dimension supplies the related criterion for agnostic PAC learnability. These are two different levels of description. Finite VC dimension characterizes whether an individual binary-classifier class is agnostic PAC learnable. The countable-union characterization describes how such component classes can be assembled into a larger class that is nonuniformly learnable.

This example is about recognizing structure, not calculating a VC dimension. A careful solution checks two facts: first, that the union is countable; second, that the component classes are agnostic PAC learnable. If both facts are given, the converse direction of the if-and-only-if characterization applies.

SRM begins with a countable sequence of hypothesis classes, written as H1, H2, H3, and so on. Each class represents a possible family of hypotheses. The sequence lets the procedure compare different levels of model complexity instead of treating complexity as a fixed choice made before learning. A later class can represent a richer candidate family in the sequence, while an earlier class represents another candidate family. The essential point is that the procedure keeps the class index available as part of the learning decision.

The sequence is not merely a list of names. It gives SRM a set of alternatives over which to search. Choosing a model therefore has two parts: select a class index d, then select a hypothesis h within Hd. Fixing one class in advance would remove the first part of this decision and would prevent the SRM procedure from comparing the candidate classes.

For a selected class Hd and a hypothesis h in that class, the SRM bound contains two components. The first is the empirical risk, written as L_S(h). It reflects how the particular hypothesis performs in the empirical setting. The second is a complexity term that depends on the class index d. This term accounts for the complexity associated with the chosen class. SRM combines these terms rather than minimizing empirical risk alone.

The important trace is index, class, hypothesis, and bound. SRM does not ask only which hypothesis has the smallest empirical risk inside a preselected class. It searches across the class indices and the hypotheses they contain. The selected pair is the class index and the hypothesis that minimize the bound on true risk.

The source characterization states that the bound holds with probability at least 1 minus delta for every natural-number index d and every h in Hd. This coverage matters: SRM is allowed to search over the sequence of classes and the hypotheses inside them while using the same bound-based model-selection principle.