Penalized Empirical Risk For Structural Selection

Why Add a Penalty?

A richer model can usually fit the observed sample at least as well as a simpler one. That does not mean it will predict better: a model with more flexibility can adapt to accidental features of the sample. Structural risk minimization (SRM) makes this tension explicit by comparing candidate models using both their empirical fit and a charge for complexity.

The aim here is to understand the selection rule and its consequences. A penalty has to be specified on a scale compatible with the empirical risk, and its form and size affect which model is selected. The selection rule itself does not guarantee that a particular penalty is statistically adequate; establishing guarantees or calibrating penalties requires additional assumptions and analysis.

Definition of Penalized Structural Selection

Let \(Z_1,\ldots,Z_n\) be the observed data, and let \(\ell(f;Z_i)\) be the loss of predictor \(f\) on observation \(Z_i\). Its empirical risk is the average observed loss. Suppose candidate model classes are indexed by \(m\), with class \(\mathcal F_m\). For each class, first choose a predictor with the smallest empirical risk in that class. The structural selection step then compares these fitted predictors.

\widehat R_n(f)=\frac{1}{n}\sum_{i=1}^{n}\ell(f;Z_i), \qquad \widehat f_m\in\operatorname*{arg\,min}_{f\in\mathcal F_m}\widehat R_n(f).

Write \(C_n(m)\) for a nonnegative penalty assigned to model \(m\). It may reflect a complexity measure, the sample size, or both. The SRM selector minimizes the penalized empirical risk:

\widehat m\in\operatorname*{arg\,min}_{m} \left\{\widehat R_n(\widehat f_m)+C_n(m)\right\}, \qquad \widehat f=\widehat f_{\widehat m}.

Definition: Structural risk minimization selects a candidate model by minimizing its empirical risk plus a model-dependent complexity penalty. The selected predictor is an empirical-risk minimizer within the selected model class, subject to any tie-breaking rule used.

The index \(m\) need not be the dimension of a model. It can label a sieve level, a collection of basis functions, or another measure of richness. Nor must the penalty be a simple multiple of dimension. What matters for the selection rule is that each candidate receives a specified penalty on the same scale as its empirical risk.

A common special case writes \(C_n(m)=\lambda c_m\), where \(c_m\) is a nonnegative complexity score and \(\lambda\geq 0\) controls the strength of the penalty. This form makes comparisons easy to interpret: a candidate with a higher complexity score must earn its extra penalty by reducing empirical risk sufficiently.

Worked Comparisons

Worked Example: Constant Versus Linear Regression

Consider three observations with fixed covariates \(x=(-1,0,1)\) and responses \(y=(0,2,4)\). Use squared-error loss and mean empirical risk. Compare a constant model \(\mathcal F_0=\{f(x)=a\}\), with complexity \(c_0=1\), to a linear model \(\mathcal F_1=\{f(x)=a+bx\}\), with complexity \(c_1=2\). The criterion is empirical risk plus \(\lambda c_m\).

For the constant model, the empirical-risk minimizer is the sample mean, \(\hat a=(0+2+4)/3=2\). Its fitted values are \((2,2,2)\), so its squared errors are \(4,0,4\). Therefore, \(\widehat R_3(\widehat f_0)=(4+0+4)/3=8/3\).

The linear model fits \(f(x)=2+2x\), giving fitted values \((0,2,4)\) and squared errors \(0,0,0\). Thus \(\widehat R_3(\widehat f_1)=0\). The two penalized criteria are \(8/3+\lambda\) and \(2\lambda\), respectively. The linear model is selected when \(2\lambda<8/3+\lambda\), or \(\lambda<8/3\); the constant model is selected when \(\lambda>8/3\), with a tie at equality. For example, at \(\lambda=1\) the scores are \(11/3\) and \(2\), so the linear model wins. At \(\lambda=3\) they are \(17/3\) and \(6\), so the constant model wins. The more flexible model's perfect sample fit is not, by itself, enough to determine the selection.

Worked Example: A Threshold Classifier and an Exact-Fit Classifier

Let \(x=1,2,3,4,5\) and let the observed labels be \(y=(0,0,0,1,1)\). Use the empirical distribution that assigns probability \(1/5\) to each observed pair \((x_i,y_i)\), and use zero-one loss. Compare three candidate classes, each containing one specified predictor: \(f_1(x)=0\), with complexity \(c_1=1\); \(f_2(x)=\mathbf{1}\{x\geq4\}\), with \(c_2=2\); and a lookup predictor \(f_3\) that returns the listed label at each of the five observed covariates, with \(c_3=5\).

The first predictor misclassifies the last two observations, so its empirical risk is \(2/5=0.4\). The threshold predictor classifies all five correctly, so its empirical risk is \(0\). The lookup predictor also has empirical risk \(0\). With \(\lambda=0.1\), the penalized scores are \(0.4+0.1(1)=0.5\), \(0+0.1(2)=0.2\), and \(0+0.1(5)=0.5\). The threshold predictor is selected. The lookup model's exact fit does not improve on the threshold model's empirical risk, and its higher penalty makes it less attractive.

Worked Example: The Penalty Can Favor a Worse Sample Fit

Suppose a sample of \(n=10\) binary-labeled observations is evaluated under zero-one loss. Consider three candidate classes whose within-class empirical minimizers make, respectively, \(3\), \(1\), and \(0\) errors. Their empirical risks are \(0.3\), \(0.1\), and \(0\). Let their complexity scores be \(1\), \(2\), and \(3\), and use \(C_n(m)=\lambda c_m\) with \(\lambda=0.12\).

The penalized scores, in order, are \(0.3+0.12(1)=0.42\), \(0.1+0.12(2)=0.34\), and \(0+0.12(3)=0.36\). The second class is selected: it has a higher empirical risk than the third class, but its complexity score is lower. If instead \(\lambda=0.05\), the scores are \(0.35\), \(0.20\), and \(0.15\), so the third class is selected. This calculation shows how the penalty can change the empirical-risk winner; it does not establish which choice has the lowest population risk.

Two Consequences of the Selection Rule

The defining minimization gives a direct pairwise comparison. This is useful for understanding precisely what a selected model has to achieve, without making any probabilistic claim about how well empirical risk estimates population risk.

Proposition: If \(\widehat m\) minimizes \(\widehat R_n(\widehat f_m)+C_n(m)\), then for every candidate \(m\), \(\widehat R_n(\widehat f_{\widehat m})-\widehat R_n(\widehat f_m)\leq C_n(m)-C_n(\widehat m)\).

Proof. By the definition of \(\widehat m\), \(\widehat R_n(\widehat f_{\widehat m})+C_n(\widehat m)\leq\widehat R_n(\widehat f_m)+C_n(m)\). Subtract \(\widehat R_n(\widehat f_m)+C_n(\widehat m)\) from both sides to obtain the stated inequality. In particular, if \(C_n(\widehat m)>C_n(m)\), the selected model must have reduced empirical risk by at least that penalty difference. If its penalty is lower, it may instead have a higher empirical risk. \(\square\)

A second useful fact concerns a common multiplier. It holds for any fixed collection of candidate empirical risks and complexity scores; it is an algebraic property, not a claim that a larger multiplier improves prediction.

Proposition: Fix candidate scores \(a_m\) and complexities \(c_m\), and let \(m_1\) minimize \(a_m+\lambda_1c_m\) and \(m_2\) minimize \(a_m+\lambda_2c_m\). If \(\lambda_1<\lambda_2\), then \(c_{m_1}\geq c_{m_2}\).

Proof. Optimality at \(\lambda_1\) and \(\lambda_2\), respectively, gives \(a_{m_1}+\lambda_1c_{m_1}\leq a_{m_2}+\lambda_1c_{m_2}\) and \(a_{m_2}+\lambda_2c_{m_2}\leq a_{m_1}+\lambda_2c_{m_1}\). Adding the inequalities cancels the \(a_m\) terms. Rearranging gives \((\lambda_2-\lambda_1)(c_{m_1}-c_{m_2})\geq0\). Since \(\lambda_2-\lambda_1>0\), it follows that \(c_{m_1}\geq c_{m_2}\). Ties do not invalidate the argument: it applies to any selected minimizer at each multiplier. \(\square\)

Interpreting the Tradeoff

SRM makes model selection a comparison between two quantities, not a rule that always favors the smallest model or the lowest empirical risk. A larger model can be selected if its improvement in fit outweighs its extra penalty. A simpler model can be selected even when it fits the sample less well, provided its penalty reduction compensates for that loss of fit.

The scale matters. If empirical risk is an average loss, then a penalty added to it must also be expressed on that scale. Changing from average loss to total loss multiplies the empirical-risk term by \(n\); leaving the penalty unchanged would generally change the selected model. Similarly, changing the numerical units of the loss changes the relative influence of a fixed penalty.

A penalty is also not a substitute for inspecting what the model classes represent. Two classes with the same numerical complexity score need not have comparable approximation properties, and the selected index is not automatically a statement about the true mechanism generating the data. The criterion says which candidate wins under the specified empirical risks and penalties. Further assumptions are needed to draw conclusions about population performance.

Common Mistake

Wrong reasoning: “The most complex model has the smallest empirical risk, so SRM must select it.” This ignores the penalty term. The selection compares the full quantities \(\widehat R_n(\widehat f_m)+C_n(m)\), not empirical risks alone.

Correction: Calculate or compare the penalized scores for the candidates. A more complex model is preferred only when its reduction in empirical risk is large enough to compensate for its additional penalty. Conversely, adding a penalty does not guarantee that a simpler model will win: if the empirical-risk improvement is sufficiently large, the richer model can still have the smaller penalized score.

Key takeaway: SRM selects the candidate minimizing empirical risk plus a complexity penalty. The penalty controls the fit–richness tradeoff; the resulting selection is determined by both terms, and its predictive quality requires separate justification.

Check Your Understanding

Use the selection rule and comparisons above to answer the following.

For two models with empirical risks \(0.12\) and \(0.08\), and penalties \(0.01\) and \(0.06\), which has the smaller penalized score?
In the pairwise proposition, what does the selected model's empirical-risk difference have to do when its penalty is larger than a competitor's?
Why can a lookup predictor fit the observed labels perfectly and still lose to a threshold model?
If the multiplier on fixed complexity scores increases, can a minimizing model's complexity increase? Explain using the proved result.
Why does changing empirical risk from an average to a sum affect the interpretation of a fixed penalty?