Selection Among Finite Candidate Predictors

Why Selection Needs a Risk Guarantee

Suppose we have a finite collection of candidate predictors and must choose one using the same data that will be used to assess its empirical performance. The candidate with the smallest empirical risk need not have the smallest population risk: even when each empirical risk is accurate on average, searching across many candidates makes it more likely that at least one looks unusually good by chance. A useful selection guarantee accounts for this search and compares the selected predictor with the best candidate in the collection.

This tutorial makes that comparison in two ways. Empirical-risk minimization chooses the smallest observed risk and pays a uniform search cost. Penalized selection adds candidate-specific terms that can reflect different complexity weights. Both bounds are relative to the best candidate in the finite set; neither says that this candidate is necessarily the best possible predictor outside that set.

Setup and Definitions

Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations from a distribution $P$. Consider a fixed collection of $M$ measurable candidate predictors $f_1,\ldots,f_M$, and a measurable loss function $\ell(f,z)$ taking values in $[0,1]$. The candidates are fixed before observing this sample, or were chosen independently of it. Define the population risk and empirical risk of candidate $j$ by

R_j=E[\ell(f_j,Z)],\qquad \widehat R_j=\frac{1}{n}\sum_{i=1}^{n}\ell(f_j,Z_i), \qquad j=1,\ldots,M,

where $Z$ has distribution $P$. The finite-candidate oracle risk is $R_*=\min_{1\le j\le M}R_j$: it is the smallest population risk among the candidates under consideration.

Definition: An empirical-risk selector is an index $\hat j_{\mathrm{ERM}}$ minimizing $\widehat R_j$ over $j=1,\ldots,M$. A penalized selector, for specified nonnegative penalties $\operatorname{pen}_j$, is an index $\hat j_{\mathrm{pen}}$ minimizing $\widehat R_j+\operatorname{pen}_j$. A fixed tie-breaking rule makes each selection well defined.

The bounded-loss assumption gives a precise concentration statement. Hoeffding's inequality says that for each fixed $j$ and every $t>0$, $P(|\widehat R_j-R_j|>t)\le 2\exp(-2nt^2)$. The candidates need not have independent empirical risks; the finite-class arguments below use a union bound, not independence between candidates.

Empirical-Risk Selection: A Uniform Bound

For a finite collection, one can make the deviations small for all candidates at once. Let $0<\delta<1$ be the allowed failure probability and set

\epsilon_{M,n,\delta} = \sqrt{\frac{\log(2M/\delta)}{2n}}.

Theorem: Under the setup above, with probability at least $1-\delta$, $$ R_{\hat j_{\mathrm{ERM}}} \le \min_{1\le j\le M}R_j + 2\sqrt{\frac{\log(2M/\delta)}{2n}}. $$

Proof. For any fixed $j$, Hoeffding's inequality at $t=\epsilon_{M,n,\delta}$ gives $P(|\widehat R_j-R_j|>\epsilon_{M,n,\delta})\le \delta/M$, because $2\exp(-2n\epsilon_{M,n,\delta}^2)=\delta/M$. By the union bound, the probability that any of the $M$ deviations exceeds this threshold is at most $M(\delta/M)=\delta$. Thus, with probability at least $1-\delta$, every candidate satisfies $|\widehat R_j-R_j|\le\epsilon_{M,n,\delta}$.

On that event, choose any oracle index $j_*$ with $R_{j_*}=R_*$, which exists because the collection is finite. The definition of empirical-risk selection and the simultaneous deviation bounds give

R_{\hat j_{\mathrm{ERM}}} \le \widehat R_{\hat j_{\mathrm{ERM}}}+\epsilon_{M,n,\delta} \le \widehat R_{j_*}+\epsilon_{M,n,\delta} \le R_{j_*}+2\epsilon_{M,n,\delta}.

Since $R_{j_*}=R_*$, this is the claimed inequality. $\square$

The factor $2$ appears because the selected candidate's empirical risk may underestimate its population risk, while the oracle candidate's empirical risk may overestimate its population risk. The bound also shows the cost of searching: at fixed $n$ and $\delta$, the deviation term grows with $M$, through $\log M$.

Worked Example: A Uniform Bound With 100 Candidates

Suppose there are $M=100$ fixed candidates, the sample size is $n=1200$, the failure probability is $\delta=0.10$, and the smallest candidate risk is $0.04$. Calculate the empirical-risk selection bound.

First substitute all three quantities into the radius: $2M/\delta=2(100)/0.10=2000$, so

\epsilon_{100,1200,0.10} = \sqrt{\frac{\log(2000)}{2(1200)}} = \sqrt{\frac{7.60090246}{2400}} \approx 0.05628.

The excess-risk term is twice this radius: $2\epsilon\approx 2(0.0562765)=0.112553$. Therefore, with probability at least $0.90$,

R_{\hat j_{\mathrm{ERM}}} \le 0.04+0.112553 \approx 0.15255.

This is a valid upper bound, not a prediction that the selected risk will equal $0.15255$. Its gap above $0.04$ reflects uncertainty from sampling and searching across 100 candidates.

Penalized Selection With Candidate-Specific Weights

A single uniform radius treats all candidates alike. When candidates are assigned different complexity weights, a corresponding penalty can give a candidate-specific deviation allowance. Let $w_1,\ldots,w_M$ be positive numbers with $\sum_{j=1}^{M}w_j\le 1$, and define

a_j = \sqrt{\frac{\log(2/(\delta w_j))}{2n}}, \qquad \operatorname{pen}_j=a_j.

A smaller weight gives a larger penalty: it allocates less of the total failure probability to that candidate, so its deviation allowance must be larger. The weights may encode prior complexity information, but they must be specified independently of the sample being used for selection.

Theorem: Under the stated finite-candidate setup and for positive weights summing to at most one, let $\hat j_{\mathrm{pen}}$ minimize $\widehat R_j+a_j$. With probability at least $1-\delta$, $$ R_{\hat j_{\mathrm{pen}}} \le \min_{1\le j\le M}\{R_j+2a_j\}. $$

Proof. For each $j$, Hoeffding's inequality gives $P(|\widehat R_j-R_j|>a_j)\le 2\exp(-2na_j^2)=\delta w_j$. The union bound therefore shows that the probability of any failure is at most $\sum_j\delta w_j\le\delta$. On the resulting event, every deviation is bounded by its own $a_j$. For any candidate $k$, penalized minimization and these deviations imply

R_{\hat j_{\mathrm{pen}}} \le \widehat R_{\hat j_{\mathrm{pen}}}+a_{\hat j_{\mathrm{pen}}} \le \widehat R_k+a_k \le R_k+2a_k.

This holds for every $k$, so taking the minimum over $k$ proves the result. $\square$

The oracle comparison is now candidate-specific: a candidate with a larger risk may still have a smaller value of $R_j+2a_j$ if it receives a sufficiently smaller penalty. This is a guarantee about the risk of the selected predictor, not a claim that the penalty makes the empirical risk itself more accurate.

Worked Example: Weighted Penalties for Three Candidates

Take $M=3$, $n=2000$, $\delta=0.05$, weights $(w_1,w_2,w_3)=(1/2,1/3,1/6)$, and candidate risks $(0.08,0.05,0.03)$. The weights sum to one. Calculate the penalties and the oracle bound.

For the first candidate, $2/(\delta w_1)=2/(0.05\cdot0.5)=80$, hence $a_1=\sqrt{\log(80)/4000}\approx0.03310$. For the second, $2/(\delta w_2)=120$, hence $a_2=\sqrt{\log(120)/4000}\approx0.03460$. For the third, $2/(\delta w_3)=240$, hence $a_3=\sqrt{\log(240)/4000}\approx0.03702$.

The three values of $R_j+2a_j$ are, respectively, $0.08+2(0.033098)\approx0.14620$, $0.05+2(0.034596)\approx0.11919$, and $0.03+2(0.037016)\approx0.10403$. The theorem therefore guarantees that the selected predictor has risk at most $0.10403$, with probability at least $0.95$.

For illustration, suppose the observed empirical risks are $0.090$, $0.055$, and $0.040$. The penalized criteria are approximately $0.12310$, $0.08960$, and $0.07702$, so the third candidate is selected. The guarantee compares that selected risk with the smallest of the three oracle bounds just calculated; it does not require the empirical risks to equal the population risks.

When the Penalty Changes the Choice

A penalty affects selection only when it differs across candidates. For example, adding the same constant $c$ to every empirical risk leaves the minimizer unchanged, since $\widehat R_j+c\le\widehat R_k+c$ exactly when $\widehat R_j\le\widehat R_k$. A useful complexity penalty must therefore vary with the candidate.

Worked Example: Empirical-Risk and Penalized Choices Differ

Consider two candidates with risks $R_1=0.10$ and $R_2=0.08$. Use $n=1000$, $\delta=0.05$, and weights $w_1=0.9$, $w_2=0.1$. Suppose the observed empirical risks are $\widehat R_1=0.100$ and $\widehat R_2=0.095$. Compare the choices.

Empirical-risk minimization selects candidate 2 because $0.095<0.100$. The weighted radii are

a_1=\sqrt{\frac{\log(2/(0.05\cdot0.9))}{2000}} =\sqrt{\frac{\log(44.4444)}{2000}} \approx0.04355, \qquad a_2=\sqrt{\frac{\log(400)}{2000}} \approx0.05473.

The penalized criteria are approximately $0.100+0.04355=0.14355$ for candidate 1 and $0.095+0.05473=0.14973$ for candidate 2. Thus penalized selection chooses candidate 1, accepting its slightly larger empirical risk in exchange for its smaller penalty.

The candidate-specific oracle terms are $R_1+2a_1\approx0.18710$ and $R_2+2a_2\approx0.18947$. The theorem bounds the selected risk by their minimum, approximately $0.18710$, with probability at least $0.95$. The example illustrates how the penalty can change a choice; it does not establish that penalization always improves the realized risk.

Common Pitfalls and Interpretation

Confusing empirical and population risk. The selector minimizes quantities computed from the sample, while the guarantee concerns $R_j$, an expectation under the data distribution. They are not interchangeable.
Forgetting the search cost. A deviation bound for one fixed candidate does not automatically hold simultaneously for $M$ candidates. The factor $\log M$ in the uniform bound comes from accounting for the whole collection.
Adding a constant and calling it a complexity penalty. A common additive constant cannot change the selected index. Candidate-specific penalties are needed to alter the ranking.
Reading an oracle inequality as a model-recovery guarantee. These results bound the selected candidate's risk relative to candidates in the finite set. They do not guarantee selection of the index with smallest true risk.

The main practical distinction is that empirical-risk selection uses one common allowance for the whole collection, whereas weighted penalized selection assigns different allowances across candidates. In either case, the validity of the guarantee depends on the stated assumptions: the collection is finite and fixed independently of the sample, the loss is bounded, and the observations are i.i.d. The resulting bound is a probability statement, not a deterministic assertion about every dataset.

Check Your Understanding

Work through these questions using the definitions and bounds above.

Why does the uniform empirical-risk bound contain a factor of $2$ multiplying the deviation radius?
For $M=10$, $n=500$, and $\delta=0.05$, write the uniform deviation radius before evaluating it numerically.
Explain why adding the same constant to each candidate's empirical risk cannot change the selected candidate.
For two candidates with weights $w_1=0.8$ and $w_2=0.2$, which one receives the larger weighted radius, and why?
What does the finite-candidate oracle risk compare against, and what does it not guarantee?