Empirical Risk Selection From A Finite Dictionary

Empirical Selection From a Fixed Dictionary

Suppose a learning procedure is allowed to choose from a specified finite collection of predictors. It evaluates each candidate on the observed data and selects one with the smallest empirical risk. This is empirical risk minimization over a finite dictionary. The definition is simple, but two details matter: a tie can leave the selected predictor ambiguous, and a selection rule should be measurable if it is to be treated as a statistical estimator.

The exact comparison delivered by this procedure is also deliberately limited. It says that the selected candidate fits the observed sample at least as well, under the chosen loss, as every other candidate in the dictionary. By itself, that fact is not a claim about performance on new observations.

Definition and Setup

Let $Z_1,\ldots,Z_n$ be observed data, with each $Z_i$ taking values in a measurable space $(\mathcal Z,\mathcal A)$. For the usual statistical interpretation, suppose the observations are independent and identically distributed with common distribution $P$. Let $\mathcal F=\{f_1,\ldots,f_M\}$ be a fixed, nonempty, finite dictionary of predictors, indexed from $1$ to $M$. A predictor might map a feature vector to a numerical response or a class label.

Let $q(f,z)$ be the loss incurred by predictor $f$ on observation $z$. Assume that, for each candidate $f_j$, $z\mapsto q(f_j,z)$ is a measurable, real-valued function. Nonnegative losses are common, but the empirical selection definition only needs the displayed losses to be real-valued. Define the empirical risk of candidate $f_j$ by

\hat R_n(f_j)=\frac{1}{n}\sum_{i=1}^n q(f_j,Z_i), \qquad j=1,\ldots,M.

The dictionary's empirical-risk minimizers are the indices at which these $M$ numbers attain their minimum. When the candidates are fixed, this is a finite comparison performed on the observed sample. The empirical risk is a function of the sample, so the minimizing index can also be a function of the sample.

Definition: An empirical risk minimizer over $\mathcal F$ is a selected candidate $\hat f\in\mathcal F$ satisfying $$ \hat R_n(\hat f)=\min_{1\le j\le M}\hat R_n(f_j). $$ The associated minimum value, $\min_{1\le j\le M}\hat R_n(f_j)$, is the best empirical risk available within this dictionary.

The phrase “within this dictionary” is essential. The procedure does not search over every possible predictor; it selects one of the listed candidates. In particular, selecting one candidate is different from forming a weighted average or other combination of several candidates.

Worked Example: Selecting a Constant Under Squared-Error Loss

Suppose the observed responses are $0,2,3$, and the dictionary consists of the three constant predictors $f_0(x)=0$, $f_1(x)=1$, and $f_2(x)=2$. Use squared-error loss $q(f,(x,y))=(y-f(x))^2$. Since each predictor is constant, the feature values do not affect the calculation.

For $f_0$, the three squared errors are $0^2,2^2,3^2$, so $\hat R_3(f_0)=(0+4+9)/3=13/3$.

For $f_1$, the squared errors are $(0-1)^2,(2-1)^2,(3-1)^2$, giving $\hat R_3(f_1)=(1+1+4)/3=6/3=2$.

For $f_2$, they are $(0-2)^2,(2-2)^2,(3-2)^2$, giving $\hat R_3(f_2)=(4+0+1)/3=5/3$.

Because $5/3<2<13/3$, the selected candidate is $f_2$. Its empirical risk equals the smallest of the three calculated values. This conclusion concerns only the listed constants and these three observed responses.

A Measurable Rule for Ties

If multiple candidates attain the minimum, saying “choose a minimizer” does not specify a unique selected index. A convenient deterministic convention is to choose the smallest index among all minimizers. The ordering is part of the rule: a different fixed ordering can select a different candidate when a tie occurs.

Write $r_j=\hat R_n(f_j)$. Define $\hat j$ as the smallest index $j$ for which $r_j=\min_k r_k$, and set $\hat f=f_{\hat j}$. To show this choice is measurable, view the full sample as a point $z=(z_1,\ldots,z_n)$ in $\mathcal Z^n$, equipped with its product sigma-algebra. For each $j$, the map $r_j(z)=n^{-1}\sum_{i=1}^n q(f_j,z_i)$ is measurable: coordinate projections are measurable, composition with the measurable loss is measurable, and a finite sum of measurable real-valued functions is measurable.

For each possible selected index, consider the sample set

A_j= \bigcap_{k<j}\{z:r_j(z)<r_k(z)\} \;\cap\; \bigcap_{k>j}\{z:r_j(z)\le r_k(z)\}.

An intersection over no indices is the whole sample space. Each comparison set is measurable: for example, $r_j-r_k$ is measurable, and the sets where a measurable real-valued function is less than or equal to zero, or strictly less than zero, are measurable. Thus each $A_j$ is measurable.

Result: If the dictionary is finite and each candidate's loss is measurable and real-valued, the rule that chooses the smallest index attaining the minimum empirical risk is a measurable, uniquely specified selection.

To verify the result, suppose first that $z\in A_j$. The inequalities in the definition give $r_j<r_k$ for every $k<j$, and $r_j\le r_k$ for every $k>j$. Therefore $r_j$ is a minimum over all indices, and no smaller index attains that minimum. The first minimizing index is exactly $j$. Conversely, if $j$ is the first index attaining the minimum, then every earlier value must be strictly greater than $r_j$, while every later value must be at least $r_j$. Hence $z\in A_j$. The sets $A_1,\ldots,A_M$ are therefore disjoint and cover $\mathcal Z^n$, and $\{\hat j=j\}=A_j$ is measurable for every $j$. Since the index set is finite with its discrete sigma-algebra, this proves that $\hat j$ is a measurable, finite-valued statistic. $\square$

The strict inequality for earlier indices is what enforces the tie rule. Replacing it by a non-strict inequality would allow an earlier tied candidate to be assigned to a later index as well, so the resulting sets would not describe the specified first-minimizer rule.

Worked Example: A Tie Under Zero-One Loss

Consider four binary labels $Y=(0,1,1,0)$, and two classifiers whose predictions on these four observations are $f_1=(0,0,1,1)$ and $f_2=(1,1,0,0)$. Under zero-one loss, an observation contributes $1$ for a wrong prediction and $0$ for a correct prediction.

For $f_1$, the predictions are wrong on observations 2 and 4. Its empirical risk is $(0+1+0+1)/4=2/4=1/2$. For $f_2$, the predictions are wrong on observations 1 and 3, so its empirical risk is also $(1+0+1+0)/4=2/4=1/2$.

Both indices attain the minimum. Under the smallest-index rule, $\hat j=1$ and the selected predictor is $f_1$. Choosing $f_2$ instead would also minimize empirical risk, but it would be a different tie-breaking convention. In either case, the empirical minimum value remains $1/2$.

The Empirical Comparison

Once the selection rule is defined, its basic comparison with the dictionary follows directly from minimization. The statement is pointwise in the observed sample: it does not require the data to be independent, the candidates to be distinct, or a particular loss such as squared error.

Theorem: For every sample and every $j\in\{1,\ldots,M\}$, an empirical risk minimizer $\hat f$ over $\mathcal F$ satisfies $$ \hat R_n(\hat f)\le \hat R_n(f_j). $$ Consequently, $$ \hat R_n(\hat f)=\min_{1\le j\le M}\hat R_n(f_j). $$

Proof. By definition, the selected index $\hat j$ attains the minimum of the finite list $\hat R_n(f_1),\ldots,\hat R_n(f_M)$. A minimum of a finite list is no greater than any entry in that list. Thus, for every $j$, $\hat R_n(\hat f)=\hat R_n(f_{\hat j})\le\hat R_n(f_j)$. Since $\hat f$ is itself one of the dictionary members, its empirical risk is also an entry in the list. These two facts give the claimed equality with the minimum. $\square$

Worked Example: Checking the Comparison for Every Candidate

Return to the squared-error example, where the empirical risks of $f_0,f_1,f_2$ were $13/3,2,5/3$, respectively, and the selected predictor was $f_2$. The comparison for $j=0$ is $5/3\le13/3$, which holds because $5\le13$. For $j=1$, it is $5/3\le2$, or $5\le6$ after multiplying by $3$. For $j=2$, it is $5/3\le5/3$, equality. Thus the selected empirical risk is no greater than the empirical risk of each dictionary member, not just the risk of one convenient comparator.

More generally, the comparison holds simultaneously for all $j$ on the same sample. It even holds if a comparator index is chosen after seeing the data: for each realized sample, the selected risk is no greater than any entry of that realized finite list.

What the Comparison Does—and Does Not—Say

If the observations have distribution $P$ and the losses have finite expectations, the population risk of a fixed candidate is $R(f_j)=E[q(f_j,Z)]$, where $Z\sim P$. Population risk concerns the distribution of a new observation; empirical risk is calculated from the particular observed sample. The empirical comparison theorem orders the observed empirical risks. It does not, without additional assumptions and analysis, order the population risks.

This distinction matters because the candidate is selected using the same observations on which its empirical risk is evaluated. A candidate can fit features of the observed sample that do not persist in new data. Establishing a relationship between the selected empirical risk and population risk requires a statistical guarantee beyond the deterministic minimization argument here.

The result also depends on which candidates and which loss were specified. Expanding or changing the dictionary can change its minimum empirical risk and its selected member. Changing the loss changes the empirical values being compared. The procedure makes no claim that its dictionary contains the best possible predictor, only that it finds a minimum under the stated empirical criterion among the listed candidates.

Common Mistake

Wrong reasoning: “The selected predictor has the smallest empirical risk, so it must have the smallest population risk.” Minimization compares only the observed empirical values; it does not establish that those values rank candidates in the same order as their population risks. Correction: State the exact conclusion as $\hat R_n(\hat f)\le\hat R_n(f_j)$ for every dictionary member. A population-risk conclusion needs a separate argument.
Leaving ties unspecified: “Choose any minimizer” may be enough to assert existence, but it does not define a unique selected index. Correction: Give a deterministic rule, such as choosing the smallest minimizing index, and verify measurability when the selection is used as a statistical procedure.
Confusing selection with aggregation: An empirical risk minimizer from $\mathcal F$ is one member of the dictionary. Correction: A weighted combination of candidates is a different procedure unless that combination is itself included as a dictionary member.

Key takeaway: For a fixed finite dictionary with measurable candidate losses, empirical risk minimization selects a measurable minimizer when ties are resolved by a fixed ordering. Its exact guarantee is an empirical one: on every sample, the selected candidate's empirical risk equals the dictionary minimum.

Check Your Understanding

Use the definitions and comparisons above to answer the following questions.

For a dictionary of $M$ predictors, write the empirical risk of candidate $f_j$ in terms of the observed losses.
Why does choosing the smallest minimizing index require strict inequalities against earlier indices in the definition of $A_j$?
If two candidates have the same minimum empirical risk, what does the first-minimizer rule select, and what does it leave unchanged?
Does the empirical comparison theorem require independent and identically distributed observations? Explain which part of the setup uses that assumption and which conclusion holds sample by sample.
What additional kind of argument is needed before inferring that an empirical risk minimizer has low population risk?