From Candidate Classes to a Selection Rule
Structural risk minimization (SRM) turns a collection of candidate model classes into a data-dependent choice. The central tradeoff is concrete: a richer class may approximate the best predictor more closely, but its empirical risk is harder to control uniformly. This workshop makes that tradeoff explicit and carries it through to a finite-sample oracle guarantee.
Let \(Z_1,\ldots,Z_n\) be independent observations with common distribution \(P\). A predictor \(f\) has loss \(\ell_f(Z)\), assumed measurable and bounded between 0 and 1. Its true risk and empirical risk are
Consider a finite or countable collection of model indices \(m\). For each \(m\), let \(\mathcal F_m\) be a nonempty finite class of predictors fixed independently of the data. Write \(N_m=|\mathcal F_m|\) and
The quantity \(R_m^*\) is the best-in-class risk. It describes approximation quality within class \(m\), not the error of the predictor eventually selected from the data. Choose positive numbers \(\delta_m\) with \(\sum_m\delta_m\leq\delta\), where \(0<\delta<1\), and set
This penalty accounts for the number of predictors in the class and the portion of the total failure probability assigned to that class. SRM selects a predictor by minimizing empirical risk plus this penalty:
Assume the minimum is attained; for countable unions, a fixed tie-breaking rule can be used whenever it is attained. No nesting assumption is needed. The index \(m\) can represent dimension, degree, resolution, or another complexity ordering.
Worked Example: A Small Sieve With Known Approximation Risks
Worked Example: Three Nested Predictor Classes
Let \(X\) be uniform on \(\{1,2,3,4\}\), and let \(Y\) be determined by \(Y=(0,0,1,1)\) at those four values of \(X\). Use squared-error loss \(\ell_f(X,Y)=(Y-f(X))^2\), with predictors taking values in \(\{0,1\}\). Thus every loss is bounded by 1. Define \(f_0=(0,0,0,0)\), \(g=(0,0,0,1)\), \(h=(0,0,1,1)\), and \(q=(1,1,1,1)\), where each vector lists predictions at \(X=1,2,3,4\). Take \(\mathcal F_1=\{f_0\}\), \(\mathcal F_2=\{f_0,g\}\), and \(\mathcal F_3=\{f_0,g,h,q\}\).
For \(f_0\), the predictions are wrong at \(X=3,4\), so \(R(f_0)=2/4=0.5\). For \(g\), only \(X=3\) is wrong, giving \(R(g)=1/4=0.25\). The predictor \(h\) is correct at every point, so \(R(h)=0\). The predictor \(q\) is wrong at \(X=1,2\), so \(R(q)=0.5\). Consequently, the best-in-class risks are \(R_1^*=0.5\), \(R_2^*=0.25\), and \(R_3^*=0\).
Set \(n=100\), \(\delta=0.05\), and \(\delta_m=\delta/[m(m+1)]\). The three allocations are \(0.025\), \(0.008333\ldots\), and \(0.004166\ldots\); their infinite sum is \(0.05\). The resulting penalties are
The larger classes pay higher penalties, but the approximation improvement is greater here. The oracle criteria \(R_m^*+2t_m\) are approximately \(0.7960\), \(0.6014\), and \(0.3814\), respectively. Thus class 3 minimizes this bound. This calculation identifies the best comparator class; the actual SRM choice still depends on the observed empirical risks.
Why the Penalties Control Estimation Error
For each fixed predictor \(f\), Hoeffding's inequality applies because its \(n\) losses are independent and lie in \([0,1]\). It gives
The number \(t_m\) is chosen so that this probability is at most \(\delta_m/N_m\). Taking a union bound over predictors and classes gives the simultaneous guarantee needed for selection.
Proof. For a fixed \(m\) and \(f\in\mathcal F_m\), substitute \(t_m\) into Hoeffding's inequality:
There are \(N_m\) predictors in \(\mathcal F_m\), so the probability that any one of them violates the bound is at most \(\delta_m\). Applying the union bound over \(m\), the probability of at least one violation is at most \(\sum_m\delta_m\leq\delta\). Taking the complement proves the result. For a countable collection, the union of these measurable violation events is measurable. \(\square\)
This is a simultaneous statement: on one event, the bound holds for every candidate predictor, including the predictor chosen after seeing the data. That is why it can be used in a selection argument rather than only for a predictor fixed in advance.
Worked Example: Complexity and Probability Allocation
Worked Example: A Three-Class Risk Comparison
Let \(X\) be uniform on \(\{1,\ldots,100\}\), let \(Y=0\) always, and use squared-error loss with binary-valued predictors. A predictor that equals 1 on exactly \(k\) points has risk \(k/100\). Construct \(\mathcal F_1\) with one predictor of risk \(0.30\); let \(\mathcal F_2\) contain that predictor and three distinct predictors, one of which has risk \(0.18\) and the others risk at least \(0.18\). Extend it to \(\mathcal F_3\) by adding twelve distinct predictors, including one of risk \(0.10\), with every added predictor having risk at least \(0.10\). Such predictors exist: each is the indicator of a subset of \(\{1,\ldots,100\}\), and there are many distinct subsets of each required size. Thus the class sizes are \(1,4,16\) and the best-in-class risks are \(0.30,0.18,0.10\).
Take \(n=500\), \(\delta=0.05\), and allocate \(\delta_m=\delta 2^{-m}\) for \(m=1,2,3\). These allocations sum to \(0.04375\), which is no greater than \(0.05\). The penalties are
The oracle criteria are \(0.30+2(0.0662)\approx0.4324\), \(0.18+2(0.0804)\approx0.3408\), and \(0.10+2(0.0924)\approx0.2848\). Although class 3 has the largest estimation penalty, its smaller approximation error makes it the best comparator under this bound.
The Oracle Comparison
The simultaneous deviation theorem gives both directions of control: \(R(f)\leq\hat R_n(f)+t_m\) and \(\hat R_n(f)\leq R(f)+t_m\) for each \(f\in\mathcal F_m\). Combine these inequalities with the definition of the selected predictor.
Proof. Fix any model index \(m\), and choose a true-risk minimizer \(f_m^*\in\mathcal F_m\), which exists because \(\mathcal F_m\) is finite. Apply the deviation bound to the selected predictor, use the minimizing property of \((\hat m,\hat f)\), and then apply the other side of the deviation bound to \(f_m^*\):
This holds for every \(m\), so taking the infimum proves the claim. The \(2t_m\) bound follows with the selection penalty \(t_m\) itself; no larger penalty is needed. \(\square\)
For interpretation, let \(R_{\mathrm{cand}}^*=\inf_m R_m^*\), the best risk available anywhere in the candidate collection. Then
The first term inside the braces is the approximation cost of using class \(m\) rather than the best candidate class; \(2t_m\) is the estimation cost certified for that class. The inequality does not say that SRM identifies a uniquely correct model. It says its risk is close to the risk of the best available tradeoff, with probability at least \(1-\delta\).
Worked Example: Checking the Probability Budget
Worked Example: Why the Number of Classes Matters
Let \(X\) be uniform on \(\{1,\ldots,10\}\), let \(Y=0\), and use squared-error loss with binary predictors. Consider five fixed classes, each containing ten distinct predictors. For \(n=1000\), \(\delta=0.05\), and equal allocations \(\delta_m=0.01\), the penalty for every class is
If the factor for five classes were omitted, one might instead use \(t_0=\sqrt{\log(2\cdot10/0.05)/2000}=\sqrt{\log(400)/2000}\approx0.0548\). But the union-bound failure probability at this smaller threshold is at most
That calculation does not certify a failure probability of \(0.05\). Allocating the probability budget across classes is part of penalty calibration, not an optional adjustment.
Common Pitfalls and Practical Meaning
- Adding an unnecessary penalty term in the oracle proof. The selection rule already compares \(\hat R_n(f)+t_m\). On the simultaneous event, compare the selected predictor directly with the true-risk minimizer \(f_m^*\): \(R(\hat f)\leq\hat R_n(\hat f)+t_{\hat m}\leq\hat R_n(f_m^*)+t_m\leq R_m^*+2t_m\). The last inequality uses one deviation allowance for \(f_m^*\), and the first uses one for \(\hat f\).
- Ignoring class size or the number of models. A deviation bound for one fixed predictor does not automatically hold for a predictor selected from many candidates. The logarithmic factors in \(t_m\) account for the union bound over both predictors and classes.
- Calling the oracle a guarantee of model recovery. The result controls risk relative to the best approximation-penalty tradeoff. Different classes can have similar risks, so a risk guarantee alone does not establish that the selected index is the uniquely correct one.
- Applying the calculation to unbounded losses without new assumptions. The displayed Hoeffding penalty relies on losses in \([0,1]\). If losses are unbounded, this derivation does not apply as written; a suitable tail or moment assumption and a corresponding deviation bound are needed.
In practice, the result provides a disciplined way to compare candidate model sizes: state the candidate classes, quantify their best-in-class risks when possible, and use penalties calibrated to the class sizes and a total probability budget. When approximation risks are unknown, the selection rule remains implementable because it uses empirical risks and known complexity penalties; the oracle inequality explains what that rule can achieve without requiring the best model scale to be known in advance.
Check Your Understanding
Use the definitions and calculations above to check your understanding.
- Why must the deviation event hold simultaneously over all predictors that might be selected?
- For a class with \(N_m=8\), sample size \(n=200\), and allocation \(\delta_m=0.01\), write the corresponding penalty \(t_m\).
- In the oracle proof, identify which inequality uses the minimizing property of the selected pair and which two inequalities use the deviation event.
- If a new class lowers \(R_m^*\) but increases \(N_m\), which two terms in the oracle criterion change?
- Why does the oracle inequality not by itself prove that \(\hat m\) equals the index of the best-in-class risk?