Squared-Error Oracle Bounds For Hard Selection

Why Squared-Error Selection Has an Oracle Bound

Suppose a finite dictionary contains several predictors for a response. Hard selection chooses one predictor with the smallest observed average squared error. This is useful when the goal is to deploy a single candidate, but the selected candidate’s observed performance is not its population risk: sampling variation can make a weaker candidate look best.

An oracle bound compares the selected predictor with the best candidate in the dictionary while accounting for that selection uncertainty. Its two parts have different meanings. The oracle risk is the approximation term: how well the best available candidate predicts. The selection penalty is the price of using the sample to decide which candidate to keep. It is not a guarantee that the dictionary itself contains a good predictor.

Definition: Let $Z=(X,Y)$ have the distribution of a new observation, and let $f_1,\ldots,f_M$ be a finite dictionary of measurable predictors. The squared-error risk of $f_j$ is $R(f_j)=E[(Y-f_j(X))^2]$. Given independent observations $Z_i=(X_i,Y_i)$, $i=1,\ldots,n$, define $\widehat R_n(f_j)=n^{-1}\sum_{i=1}^n(Y_i-f_j(X_i))^2$. A hard empirical risk selector $\hat f$ is a candidate minimizing $\widehat R_n$, with ties resolved by a fixed rule. The dictionary oracle risk is $R_*=\min_{1\le j\le M}R(f_j)$.

Here the oracle is a risk minimizer within the given finite dictionary. It is not necessarily the best predictor among all measurable functions, nor is it automatically the conditional mean $E[Y\mid X]$. The result below concerns the gap between the selected candidate and this finite-dictionary oracle.

Conditions and the Oracle Inequality

Assume the training observations are independent and identically distributed. Suppose that, almost surely, the response and every candidate prediction lie in the same interval $[-B,B]$, where $B>0$. Consequently every squared loss is between zero and $L=4B^2$. Bounded predictions are part of the condition: bounding $Y$ alone does not bound squared loss if candidate predictions can be arbitrarily large.

Theorem: Under the conditions above, for any $0<\eta<1$ and $0<\delta<1$, the empirical hard selector satisfies, with probability at least $1-\delta$, $$ R(\hat f)\leq \frac{1+\eta}{1-\eta}R_*+ \frac{L}{n(1-\eta)} \left(\frac{1}{\eta}+\frac{2}{3}\right) \log\!\left(\frac{M}{\delta}\right). $$ The first term is the oracle approximation term, with a multiplicative factor. The second is an additive selection penalty; it increases with dictionary size and confidence stringency, and decreases with sample size.

A slightly sharper penalty follows from the proof, but the displayed form is convenient and preserves the same separation. The parameter $\eta$ trades off the oracle factor against the penalty: taking $\eta$ small moves the factor closer to one but makes the penalty larger.

Proof of the Bound

Fix an oracle candidate $f_*$ attaining $R_*$, which exists because the dictionary is finite. Write $\ell_f(Z)=(Y-f(X))^2$, and for a candidate $f$ define $D_f(Z)=\ell_f(Z)-\ell_{f_*}(Z)$. The empirical selector satisfies $\widehat R_n(\hat f)-\widehat R_n(f_*)\leq 0$, including when there are ties.

For two numbers $a,b\in[0,L]$, $(a-b)^2\leq a^2+b^2\leq L(a+b)$. Thus $D_f\in[-L,L]$ and $$ \operatorname{Var}(D_f)\leq E[D_f^2]\leq L\{R(f)+R_*\}. $$ Bernstein’s inequality for independent variables bounded in an interval of width $2L$ gives, for each fixed $f$, with probability at least $1-e^{-t}$, $$ E[D_f]\leq \frac{1}{n}\sum_{i=1}^nD_f(Z_i) +\sqrt{\frac{2\operatorname{Var}(D_f)t}{n}} +\frac{2Lt}{3n}. $$ Apply this inequality to each of the $M$ candidates and use the union bound. With $t=\log(M/\delta)$, all these inequalities hold simultaneously with probability at least $1-\delta$. On that event, substitute $f=\hat f$; the empirical difference from $f_*$ is nonpositive. Setting $\Delta=R(\hat f)-R_*\geq0$ and $q=t/n$ gives $$ \Delta\leq \sqrt{2Lq\{R(\hat f)+R_*\}}+\frac{2Lq}{3} =\sqrt{2Lq(2R_*+\Delta)}+\frac{2Lq}{3}. $$ For $S\geq0$, the inequality $\sqrt{2LqS}\leq \eta S+Lq/(2\eta)$ follows by squaring the equivalent nonnegative difference, or from $2\sqrt{uv}\leq u+v$. Use it with $S=2R_*+\Delta$. Then $$ (1-\eta)\Delta\leq 2\eta R_*+ Lq\left(\frac{1}{2\eta}+\frac{2}{3}\right). $$ Adding $R_*$ after dividing by $1-\eta$ yields $$ R(\hat f)\leq \frac{1+\eta}{1-\eta}R_*+ \frac{Lq}{1-\eta}\left(\frac{1}{2\eta}+\frac{2}{3}\right). $$ Since $1/(2\eta)\leq1/\eta$, this implies the stated theorem. $\square$

Worked Calculations

Worked Example: A Three-Candidate Dictionary

Let $Y$ be Bernoulli with success probability $1/2$, and let $X$ carry no additional information. Consider the three constant predictors $f_0=0$, $f_{1/2}=1/2$, and $f_1=1$. The response and predictions lie in $[0,1]$, so $B=1$ and $L=4$. Their risks are $$ R(f_0)=\tfrac12(0-0)^2+\tfrac12(1-0)^2=\tfrac12,\qquad R(f_{1/2})=\tfrac12(\tfrac12)^2+\tfrac12(\tfrac12)^2=\tfrac14, $$ $$ R(f_1)=\tfrac12(0-1)^2+\tfrac12(1-1)^2=\tfrac12. $$ Therefore $M=3$ and $R_*=1/4$. For $n=100$, $\delta=0.05$, and $\eta=1/2$, the theorem gives $$ R(\hat f)\leq 3\left(\tfrac14\right)+ \frac{4}{100(1/2)}\left(2+\tfrac23\right)\log(60) \approx 0.75+0.873460=1.623460. $$ This bound is valid but not informative here, since every candidate’s risk is at most one. That is possible: a distribution-free finite-sample guarantee can be conservative, especially when the sample is modest relative to the confidence and dictionary-size penalty.

Worked Example: Separating Oracle Risk and Selection Cost

Suppose responses and predictions lie in $[-1,1]$, so $L=4$. Let $n=200$, $M=10$, $\delta=0.05$, and suppose the best candidate has risk $R_*=0.08$. Taking $\eta=1/4$ gives the oracle factor $$ \frac{1+\eta}{1-\eta}=\frac{1.25}{0.75}=\frac53. $$ The logarithmic term is $t=\log(M/\delta)=\log(200)$. The selection penalty is $$ \frac{4\log(200)}{200(0.75)} \left(4+\frac23\right) \approx 0.659346. $$ Consequently, $$ R(\hat f)\leq \frac53(0.08)+0.659346 \approx 0.792679, $$ or $0.7927$ to four decimal places. The oracle contribution is approximately $0.13333$; the remaining $0.65935$ is the selection allowance. The result does not assert that the selected predictor has risk $0.08$, only that its risk is bounded relative to the best candidate plus a finite-sample cost.

Worked Example: Choosing the Tuning Parameter

For a dictionary with $M=5$, take $n=500$, $\delta=0.1$, $L=1$, and $R_*=0.05$. Here $t=\log(50)\approx3.912023$, so $t/n\approx0.00782405$. With $\eta=1/4$, the oracle contribution and penalty are $$ \frac53(0.05)=0.0833333,\qquad \frac{\log(50)/500}{0.75}\left(4+\frac23\right)\approx0.04868295, $$ giving $R(\hat f)\leq0.1320163$. With $\eta=1/2$, they are $$ 3(0.05)=0.15,\qquad \frac{0.00782405}{0.5}\left(2+\frac23\right)\approx0.0417282, $$ giving $R(\hat f)\leq0.1917282$. The smaller $\eta$ produces the larger penalty but a smaller oracle factor; in this calculation it yields the tighter total bound. Tuning $\eta$ means comparing the full expressions, not minimizing either term in isolation.

How to Interpret the Penalty

The logarithm of the dictionary size appears because the guarantee must hold for every candidate at once, so that it remains valid for whichever one the data select. The dependence is $\log(M/\delta)$, not $M$ itself. Increasing $n$ reduces this cost at rate $1/n$, while demanding a smaller failure probability $\delta$ increases it through the logarithm.

The boundedness requirement controls the scale of the loss fluctuations. For predictions and responses in $[-B,B]$, the loss bound is $L=4B^2$. If only the response is bounded, but predictors are not, this choice of $L$ is unjustified. One must establish an appropriate loss bound by other means or constrain the predictors before applying this theorem.

Common Mistakes

Calling the oracle risk the irreducible risk. $R_*$ is the smallest risk among the specified candidates, not necessarily the best possible risk. The dictionary may be misspecified.
Using a response bound as if it bounded every loss. Squared residuals also depend on predictions. The stated theorem assumes both responses and predictions are bounded.
Dropping the multiplicative oracle factor. The bound is not simply $R_*+$ a penalty. Its factor $(1+\eta)/(1-\eta)$ is greater than one for every allowed $\eta$.
Substituting into the penalty incorrectly. At $\eta=1/2$, its coefficient is $\frac{1}{1-1/2}(1/(1/2)+2/3)=2(2+2/3)=16/3$, not $10/3$.
Rounding before adding. Calculate the oracle contribution and penalty using unrounded inputs, add them, and round the final result. In the second example, the total rounds to $0.7927$, not $0.7926$.

Key takeaway: For bounded squared loss, empirical hard selection from a finite dictionary has a high-probability risk bound consisting of an inflated best-candidate risk and an additive term of order $L\log(M/\delta)/n$. The bound quantifies selection cost; it does not remove approximation error or guarantee that the selected candidate attains the oracle risk.

Check Your Understanding

Use the definitions and theorem above to answer these questions.

If responses and predictions lie in $[-2,2]$, what value of $L$ is valid for squared loss?
In the theorem, what does $R_*$ compare against, and why need it not equal the risk of the conditional mean?
For fixed $n$, how does doubling $M$ affect the logarithmic selection penalty?
Why is it not enough to assume bounded responses when applying the stated result?
With $\eta=1/2$, verify the oracle factor and the coefficient multiplying $L\log(M/\delta)/n$.