Misspecification And Best-in-Class Oracle Risk

Why the Benchmark Must Allow Misspecification

Structural risk minimization (SRM) selects among models by balancing empirical fit against model-dependent penalties. Its benchmark should not assume that any candidate model contains the predictor we would ideally use. A model may be too restrictive to represent that predictor, and even the best risk within a model may be an infimum that no member attains.

The relevant comparison is therefore with best-in-class risk: the infimal population risk available in each candidate model. SRM can be judged against these approximation limits, with a penalty that accounts for the cost of searching or fitting more complex models.

Definition: Let $Z=(X,Y)$ have the population distribution, let $\ell(f;Z)$ be a loss, and define the population risk $R(f)=E[\ell(f;Z)]$ whenever this expectation is finite. For a nonempty candidate model $\mathcal F_m$, its best-in-class risk is $$ R_m=\inf_{f\in\mathcal F_m}R(f). $$ This is an infimum, not necessarily a minimum: there may be no $f\in\mathcal F_m$ with $R(f)=R_m$.

Fix an ambient predictor class $\mathcal F$ containing the candidate models, and write $R_*=\inf_{f\in\mathcal F}R(f)$ for its infimal risk. This infimum also need not be attained. Since $\mathcal F_m\subseteq\mathcal F$, the model’s approximation gap relative to $\mathcal F$ is $a_m=R_m-R_*\geq 0$. If no candidate model contains a risk-optimal predictor, the gaps describe the cost of approximation; they need not be zero for any one model. In particular, if the ambient infimum is not attained, it is not correct to call $R_*$ a minimum achievable risk.

Definition: Given nonnegative model penalties $p_m$, the penalized oracle benchmark is $$ \inf_m\{R_m+p_m\} = R_*+\inf_m\{a_m+p_m\}, $$ when the same ambient class $\mathcal F$ is used to define $R_*$ and all displayed risks are finite. The infimum over models need not be attained either.

The benchmark balances two distinct quantities. The gap $a_m$ reflects how well model $m$ can approximate risk available in the ambient class; the penalty reflects the cost associated with that model. Even if the candidate models collectively approach the ambient infimal risk, the best penalized trade-off may favor a model with a positive approximation gap.

Squared Loss Makes the Approximation Gap Explicit

For squared-error prediction, the conditional mean is the natural target. The following identity turns the risk comparison into a distance calculation while preserving the distinction between an infimum and an attained value.

Theorem: Suppose $E[Y^2]<\infty$, $m(X)=E[Y\mid X]$, and $f(X)$ is square-integrable. For squared loss $\ell(f;X,Y)=(Y-f(X))^2$, $$ R(f)=E[(Y-m(X))^2]+E[(f(X)-m(X))^2]. $$ Consequently, for any nonempty class of square-integrable predictors $\mathcal G$, $$ \inf_{f\in\mathcal G}R(f) = E[(Y-m(X))^2] +\inf_{f\in\mathcal G}E[(f(X)-m(X))^2]. $$ The second infimum need not be attained.

Proof. The condition $E[Y^2]<\infty$ implies that $m(X)$ is square-integrable, and $f(X)$ is square-integrable by assumption. Expand the squared error: $$ (Y-f(X))^2=(Y-m(X))^2+2(Y-m(X))(m(X)-f(X))+(m(X)-f(X))^2. $$ The cross term is integrable by the Cauchy–Schwarz inequality. Since $m(X)-f(X)$ is a function of $X$, the defining property of conditional expectation gives $$ E[(Y-m(X))(m(X)-f(X))] = E\!\left[E[Y-m(X)\mid X](m(X)-f(X))\right]=0. $$ Taking expectations in the expansion proves the risk identity. The first term on its right does not depend on $f$; taking the infimum over $\mathcal G$ proves the second statement. No attainment is implied by taking that infimum. $\square$

If the ambient class contains $m$, then $R_*=E[(Y-m(X))^2]$, and the model’s gap is exactly the infimum of its squared $L^2(P_X)$ distances to $m$. This is a useful interpretation of approximation error, but it does not make the infimum a “smallest” distance that must be achieved.

Worked Example: A Misspecified Through-Origin Linear Model

Let $X$ be uniform on $\{-1,0,1\}$, let $Y=X^2$, and use squared loss. Take the candidate model $\mathcal F_1=\{f_\beta(x)=\beta x:\beta\in\mathbb R\}$. The ambient class contains $m(x)=x^2$, which predicts $Y$ exactly and has risk $R_*=0$. But $m$ is not a through-origin linear function on these three points.

For this model, $$ R(f_\beta)=E[(X^2-\beta X)^2] =E[X^4]-2\beta E[X^3]+\beta^2E[X^2]. $$ The distribution gives $E[X^4]=2/3$, $E[X^3]=0$, and $E[X^2]=2/3$, so $$ R(f_\beta)=\frac{2}{3}+\frac{2}{3}\beta^2. $$ This is minimized at $\beta=0$, giving $R_1=2/3$. Thus the model’s approximation gap is $a_1=R_1-R_*=2/3$, even though the ambient class has a predictor of risk zero. The gap is not an estimation error: it remains even if the model’s best population predictor is known exactly.

Worked Example: A Best-in-Class Infimum That Is Not Attained

Let $X$ be constant, $Y=\sqrt{2}$ with probability one, and let $\mathcal F_1$ consist of predictors that are rational constants $f_q(X)=q$, $q\in\mathbb Q$. Then $$ R(f_q)=(\sqrt{2}-q)^2. $$ Because the rationals are dense in the real numbers, for every $\varepsilon>0$ there is a rational $q$ with $|q-\sqrt{2}|<\varepsilon$. Hence $R(f_q)<\varepsilon^2$, and $R_1=0$.

However, no rational $q$ equals $\sqrt{2}$, so every $R(f_q)>0$. The risk infimum is not attained in $\mathcal F_1$. If the ambient class contains all real constants, its infimal risk is $R_*=0$, attained by the constant $\sqrt{2}$. This example shows why the oracle comparison must use $\inf_{f\in\mathcal F_m}R(f)$, not assume there is a best predictor inside every model.

An SRM Bound Against the Best-in-Class Oracle

Here is a deterministic comparison that isolates what the penalty must accomplish. Let the collection of models be finite. For a sample of size $n$, let $\widehat R(f)$ be the empirical risk, and let $\widehat m,\hat f$ minimize $\widehat R(f)+p_m$ over all labeled pairs $m$ and $f\in\mathcal F_m$. Assume such a minimizing pair exists. The penalties $p_m$ are nonnegative.

Theorem: Suppose there are deterministic numbers $\delta_m\geq0$ such that, on an event $\mathcal E$, for every model $m$ and every $f\in\mathcal F_m$, $$ |\widehat R(f)-R(f)|\leq\delta_m, \qquad p_m\geq\delta_m. $$ Then, on $\mathcal E$, $$ R(\hat f)\leq \inf_m\{R_m+\delta_m+p_m\} \leq \inf_m\{R_m+2p_m\}. $$ Equivalently, with $a_m=R_m-R_*$, $$ R(\hat f)\leq R_*+\inf_m\{a_m+\delta_m+p_m\} \leq R_*+\inf_m\{a_m+2p_m\}. $$

Proof. Fix any model $m$ and any $f\in\mathcal F_m$. On $\mathcal E$, the deviation bound in the selected model and the defining minimization give, in order, $$ R(\hat f) \leq \widehat R(\hat f)+\delta_{\hat m} \leq \widehat R(f)+p_m-p_{\hat m}+\delta_{\hat m} \leq R(f)+\delta_m+p_m-p_{\hat m}+\delta_{\hat m}. $$ The assumption $p_{\hat m}\geq\delta_{\hat m}$ therefore yields $$ R(\hat f)\leq R(f)+\delta_m+p_m. $$ This holds for every $f\in\mathcal F_m$, so taking the infimum over $f$ gives $R(\hat f)\leq R_m+\delta_m+p_m$. It holds for each model $m$, so taking the infimum over $m$ proves the first inequality. Since $\delta_m\leq p_m$, we have $R_m+\delta_m+p_m\leq R_m+2p_m$ for every $m$; taking infima proves the second inequality. Substituting $R_m=R_*+a_m$ gives the equivalent form. $\square$

The theorem is conditional on a uniform deviation event; it does not assert that such an event always holds. In applications, concentration arguments are used to choose $\delta_m$ and penalties so that $\mathcal E$ has high probability. Its central comparison is that the selected predictor’s risk is controlled by the best model risk plus the cost attached to that model. The comparator may itself be only an infimum: the proof compares against every $f$ and then takes infima, so it never requires an oracle minimizer to exist.

Worked Example: SRM With Three Misspecified Constant Models

Let $Y\sim\operatorname{Bernoulli}(0.4)$, let $X$ be constant, and use squared loss. The regression function is $m(X)=0.4$. Consider three singleton models containing only the constant predictors $c=0$, $c=0.2$, and $c=0.8$. None contains the target $0.4$. For a constant $c$, $$ R(c)=E[(Y-c)^2] =0.4(1-c)^2+0.6c^2 =0.24+(c-0.4)^2. $$ Thus the three risks are $R(0)=0.40$, $R(0.2)=0.28$, and $R(0.8)=0.40$; the ambient risk $R_*$ is $0.24$.

Suppose a sample of size 10 has three ones and seven zeros. This outcome has positive probability under the specified distribution. The empirical squared risks are $$ \widehat R(0)=\frac{3}{10}=0.30,\qquad \widehat R(0.2)=\frac{3(0.8)^2+7(0.2)^2}{10} =\frac{1.92+0.28}{10}=0.22, $$ and $$ \widehat R(0.8)=\frac{3(0.2)^2+7(0.8)^2}{10} =\frac{0.12+4.48}{10}=0.46. $$ Choose penalties $p_0=0.12$, $p_{0.2}=0.08$, and $p_{0.8}=0.15$. The penalized empirical criteria are $0.42$, $0.30$, and $0.61$, respectively, so SRM selects $c=0.2$, with risk $0.28$.

For these singleton models the deviations are $\delta_0=0.10$, $\delta_{0.2}=0.06$, and $\delta_{0.8}=0.06$, all no larger than their penalties. The theorem’s sharper comparator is $$ \min\{0.40+0.10+0.12,\;0.28+0.06+0.08,\;0.40+0.06+0.15\} =0.42. $$ Indeed the selected risk $0.28$ is below $0.42$. The simpler $R_m+2p_m$ comparator is $\min\{0.64,0.44,0.70\}=0.44$. Both comparisons are to a penalized approximation benchmark, not to a model that exactly represents the target.

Common Pitfall and Practical Interpretation

A common mistake is to write “the minimum risk in the model” whenever the intended quantity is an infimum. That wording silently assumes existence of a minimizing predictor. The rational-constant example shows that even a simple model can have risks arbitrarily close to its infimum without containing a predictor that achieves it. The correction is to use infimal risk or best-in-class risk and to say explicitly when attainment is known.

A related mistake is to treat approximation error as zero merely because the model collection is rich. A sequence of models may approach the ambient infimal risk while no single model attains it. For oracle comparisons, the relevant quantity is the infimum across models of approximation gap plus penalty. This formulation accommodates misspecification, non-nested candidates, and nonattainment without changing the logic of the SRM guarantee.

Key takeaway: Under misspecification, SRM is compared with the best penalized model risk, not with an assumed correctly specified model. Write risks and approximation benchmarks as infima unless attainment has been established; an oracle inequality remains meaningful even when no oracle predictor exists.

Check Your Understanding

Use the definitions and comparisons in this tutorial to answer the following questions.

Why is $R_m=\inf_{f\in\mathcal F_m}R(f)$ not necessarily the risk of any predictor in $\mathcal F_m$?
Under squared loss, what two terms make up $R(f)$ when $m(X)=E[Y\mid X]$, and what assumptions justify the identity?
In the through-origin linear example, calculate $a_1$ and explain why it does not vanish with more data.
In the rational-constant example, why is the infimum risk zero even though every candidate risk is positive?
In the SRM theorem, where is the condition $p_m\geq\delta_m$ used in the proof?

Misspecification And Best-in-Class Oracle Risk

What You'll Learn