Finite Predictor Dictionaries And Oracle Risk

Introduction

A finite collection of candidate predictors provides a clear benchmark for learning: how well could one do if the best candidate were known? This benchmark is called the oracle risk. It depends on the population distribution, not on a particular training sample, so it is different from the risk of a rule that uses data to choose a predictor.

Keeping these quantities separate is essential. A selector can choose a candidate whose population risk is not the smallest, and a predictor formed by combining candidates may not belong to the original collection at all. The finite dictionary and its oracle give us a precise reference point for describing both situations.

Finite Dictionaries and Population Risk

Let $(X,Y)$ have a joint distribution $P$ on a predictor space $\mathcal X$ and an outcome space $\mathcal Y$. Let $\mathcal A$ be an action space, and let $\ell:\mathcal A\times\mathcal Y\to[0,\infty)$ be a measurable loss function. A predictor is a measurable function $f:\mathcal X\to\mathcal A$. Assume that $(x,y)\mapsto\ell(f(x),y)$ is measurable for each predictor under consideration and that the risks below are finite.

Definition: A finite predictor dictionary is a nonempty finite indexed collection $\mathcal F=\{f_1,\ldots,f_M\}$ of measurable predictors, where $M\geq 1$. The population risk of $f_j$ is $$ R(f_j)=E[\ell(f_j(X),Y)]=\int \ell(f_j(x),y)\,dP(x,y). $$ The oracle risk in the dictionary is $$ R_{\mathcal F}^*=\min_{1\leq j\leq M}R(f_j). $$ A predictor $f^*\in\mathcal F$ attaining this minimum is a best-in-dictionary oracle predictor.

The word oracle signals that the benchmark uses the population risks, which are determined by $P$. In applications, $P$ is generally unknown, so the identity of a best candidate is generally unknown too. The definition does not assume that the dictionary contains the best predictor among all measurable functions; it only compares members of $\mathcal F$.

The dictionary is indexed because two entries can represent the same function. Repeated entries do not change the minimum risk, but keeping their indices can matter when describing a selection rule. No uniqueness is implied: several candidates may share the smallest risk.

Worked Example: Finding the Oracle in a Regression Dictionary

Suppose $Y\sim N(2,1)$, the loss is squared error, and the three predictors are constant functions $f_0(x)=0$, $f_1(x)=1$, and $f_3(x)=3$. The value of $X$ is immaterial because the predictors are constant.

For a constant predictor $f_c(x)=c$, $$ R(f_c)=E[(Y-c)^2]=\operatorname{Var}(Y)+(E[Y]-c)^2. $$ Since $E[Y]=2$ and $\operatorname{Var}(Y)=1$, the risks are $$ R(f_0)=1+(2-0)^2=5,\qquad R(f_1)=1+(2-1)^2=2,\qquad R(f_3)=1+(2-3)^2=2. $$

Therefore $R_{\mathcal F}^*=2$, attained by both $f_1$ and $f_3$. The oracle risk is a number; the oracle predictor need not be unique. These are population calculations and do not depend on a training sample.

Existence and Meaning of the Oracle

For a finite dictionary with finite risks, existence of a best member requires no compactness argument or limiting procedure. It follows directly from taking a minimum of finitely many real numbers.

Proposition: If $\mathcal F=\{f_1,\ldots,f_M\}$ is a nonempty finite dictionary and each $R(f_j)$ is finite, then $R_{\mathcal F}^*$ is finite and is attained by at least one member of $\mathcal F$.

Proof. The list $R(f_1),\ldots,R(f_M)$ consists of $M\geq1$ finite real numbers. A finite nonempty list of real numbers has a smallest element: compare the first two, retain the smaller, and continue through the list. The retained value after the $M$th comparison is the minimum. Its index, say $j^*$, satisfies $R(f_{j^*})=\min_{1\leq j\leq M}R(f_j)$. Thus $f_{j^*}$ attains the oracle risk. If multiple entries have that value, each is a minimizer. $\square$

This proposition establishes attainment only within the specified collection. It says nothing about whether a richer predictor class could have smaller risk, and it does not provide a method for identifying $j^*$ from data. Those are separate questions.

Data-Dependent Selection and Its Risk

Let $D$ denote training data, and suppose a selection rule returns one dictionary member, $\hat f_D=f_{I(D)}$, where $I(D)\in\{1,\ldots,M\}$ is a measurable index. The population risk of the selected predictor, conditional on the observed training data, is $R(\hat f_D)$. It is random through $D$. Equivalently, it is the expected loss on a fresh observation $(X_{\mathrm{new}},Y_{\mathrm{new}})\sim P$ independent of $D$, conditional on $D$.

Theorem: For a measurable selector taking values in a finite dictionary, $$ R(\hat f_D)=\sum_{j=1}^M \mathbf{1}\{I(D)=j\}R(f_j) $$ for each realized $D$, and $$ E_D[R(\hat f_D)]-R_{\mathcal F}^* =\sum_{j=1}^M P_D(I(D)=j)\bigl(R(f_j)-R_{\mathcal F}^*\bigr)\geq 0. $$ Here $E_D$ and $P_D$ refer to the distribution of the training data.

Proof. For every realized data set, exactly one of the indicators $\mathbf{1}\{I(D)=j\}$ equals one. The selected predictor is therefore the corresponding $f_j$, whose population risk is $R(f_j)$. This proves the first identity. Taking expectation over $D$, and using that each $R(f_j)$ is a fixed finite number, gives $$ E_D[R(\hat f_D)] =\sum_{j=1}^M E_D[\mathbf{1}\{I(D)=j\}]R(f_j) =\sum_{j=1}^M P_D(I(D)=j)R(f_j). $$ The selection probabilities sum to one because exactly one index is selected. Subtracting $R_{\mathcal F}^*$ and using that fact yields the displayed excess-risk identity. Every term in the sum is nonnegative: $P_D(I(D)=j)\geq0$, and $R(f_j)\geq R_{\mathcal F}^*$ by definition of the minimum. Hence the expected selected risk cannot be below the oracle risk. $\square$

The inequality is a benchmark statement, not a guarantee that a particular selector will be close to the oracle. If the rule often chooses candidates with risks much larger than $R_{\mathcal F}^*$, its expected risk can be much larger too. Nor does the inequality claim that every predictor outside the dictionary must have at least the oracle risk.

Worked Example: A Selector Can Miss the Oracle

Let $Y\sim\operatorname{Bernoulli}(0.25)$, use squared-error loss, and consider the constant predictors $f_0(x)=0$ and $f_1(x)=1$. Their population risks are $$ R(f_0)=E[Y^2]=P(Y=1)=0.25,\qquad R(f_1)=E[(1-Y)^2]=P(Y=0)=0.75. $$ Thus $R_{\mathcal F}^*=0.25$.

Suppose the training data consist of one observation $Y_1$, and the selector chooses $f_1$ if $Y_1=1$, choosing $f_0$ otherwise. The selected predictor has risk $0.75$ with probability $0.25$ and risk $0.25$ with probability $0.75$. Evaluating on a fresh, independent observation, $$ E_D[R(\hat f_D)]=0.25(0.75)+0.75(0.25)=0.1875+0.1875=0.375. $$ This exceeds the oracle risk $0.25$, as the theorem requires. The training observation determines which fixed candidate is used; it does not change either candidate's population risk.

Aggregates Need Not Share the Dictionary's Benchmark

A predictor formed by combining dictionary members may fall outside the dictionary. Its risk is still defined by the same population expectation, but $R_{\mathcal F}^*$ is not, by definition, a lower bound for that risk. The oracle compares only the listed candidates.

Worked Example: An Aggregate Outside the Dictionary

Suppose $Y=0$ with probability one, use squared-error loss, and let the dictionary contain the constant predictors $f_{-1}(x)=-1$ and $f_1(x)=1$. Each has risk $$ R(f_{-1})=E[(-1-0)^2]=1,\qquad R(f_1)=E[(1-0)^2]=1. $$ Therefore $R_{\mathcal F}^*=1$.

Now form the fixed average $g(x)=\tfrac12 f_{-1}(x)+\tfrac12 f_1(x)=0$. This is not one of the two dictionary members, and its risk is $$ R(g)=E[(0-0)^2]=0. $$ So this aggregate has risk below the best-in-dictionary oracle risk. There is no contradiction: the oracle benchmark is restricted to $\{f_{-1},f_1\}$, while $g$ is outside that set. This example does not imply that every aggregate improves on the dictionary.

Common Mistake: Treating the Oracle as the Selected Risk

A common but incorrect argument is: “The selector chooses from the dictionary, so its risk is the oracle risk.” Membership only ensures that the selected risk is one of the dictionary risks. The selected member may not be a minimizer. In the Bernoulli example, the rule chooses the higher-risk candidate with probability $0.25$, giving expected risk $0.375$, not the oracle risk $0.25$.

The correction is to identify which quantity is being discussed. $R_{\mathcal F}^*$ is the minimum of the fixed population risks. $R(\hat f_D)$ is the population risk of the candidate selected for the realized data, and $E_D[R(\hat f_D)]$ averages that random risk over training samples. For a predictor formed by aggregation, first check whether it belongs to the dictionary before comparing its risk with the in-dictionary minimum.

Key takeaway: A finite dictionary defines a population benchmark, $R_{\mathcal F}^*=\min_{f\in\mathcal F}R(f)$, attained by at least one dictionary member. A data-dependent selector has its own random risk, while an aggregate may be outside the dictionary and is not constrained by the same minimum.

Check Your Understanding

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

What conditions on the dictionary and its risks ensure that a best-in-dictionary oracle predictor exists?
If two dictionary members have equal smallest population risk, is the oracle predictor unique? Explain.
Why is the risk of a selected dictionary member random across training samples, even though each candidate's population risk is fixed?
In the Bernoulli example, why must the expected risk of the selector be at least $0.25$?
Can the risk of a predictor formed by averaging dictionary members be below the oracle risk? Explain what that does, and does not, imply.