Holdout Oracle Inequalities for Finite Candidate Sets

Why a Holdout Oracle Bound Is Needed

A holdout set provides a practical way to compare predictors after they have been constructed using training data. The central question is not whether the holdout estimate of each predictor’s risk is exact; it is whether choosing the smallest estimated risk leaves us close to the best candidate in the set. A finite-sample answer requires controlling the errors of all candidate risk estimates at once, because the chosen candidate depends on those estimates.

The guarantee below is an oracle inequality: it compares the selected predictor with the best member of the finite candidate set, not necessarily with the best possible predictor. Its key assumptions are a finite number of candidates, bounded losses, and a holdout sample independent of the data used to construct them.

Setup and Definitions

Definition: Let $\mathcal T$ denote the training data, and let $h_1,\ldots,h_M$ be $M$ candidate predictors constructed using $\mathcal T$. Let $Z_1,\ldots,Z_m$ be holdout observations that, conditional on $\mathcal T$, are independent and identically distributed and independent of the construction of the candidates. For a loss function $L(h,Z)$, define the conditional risk and holdout empirical risk of candidate $j$ by $$ R_j=E[L(h_j,Z_1)\mid\mathcal T], \qquad \widehat R_j=\frac{1}{m}\sum_{i=1}^m L(h_j,Z_i). $$ The holdout-selected index is $\hat j\in\arg\min_{1\le j\le M}\widehat R_j$, with ties resolved by choosing the smallest index. A conditional-risk oracle index is $j^*\in\arg\min_{1\le j\le M}R_j$, also with ties resolved by the smallest index. The excess risk is $R_{\hat j}-R_{j^*}$.

The risks here are conditional on training randomness. Once the training data are fixed, the candidates are fixed and the remaining randomness comes from the independent holdout observations. This is the validation target relevant to selecting among the fitted candidates. If the losses all lie in a common interval $[a,b]$, write $B=b-a$ for its width.

We use Hoeffding’s inequality in the following form: if $W_1,\ldots,W_m$ are independent random variables, each taking values in an interval of width $B$, then for every $t>0$, $$ P\left(\left|\frac{1}{m}\sum_{i=1}^m W_i-\frac{1}{m}\sum_{i=1}^m E[W_i]\right|\ge t\right) \le 2\exp\left(-\frac{2mt^2}{B^2}\right). $$ Conditionally on $\mathcal T$, this applies to the losses for each fixed candidate.

High-Probability Holdout Oracle Inequality

Theorem: Suppose $M$ is finite, the holdout observations are conditionally independent and identically distributed given $\mathcal T$, and $L(h_j,Z_i)\in[a,b]$ almost surely for every candidate $j$ and holdout observation $i$, with a common nonrandom interval of width $B=b-a>0$. For any $0<\delta<1$, the holdout-selected candidate satisfies $$ P\left(R_{\hat j}-\min_{1\le j\le M}R_j \le B\sqrt{\frac{2\log(2M/\delta)}{m}}\ \middle|\ \mathcal T\right)\ge 1-\delta $$ for almost every training data set. The same probability guarantee holds unconditionally.

The result compares against the best candidate’s conditional risk, even though the identity of that candidate may depend on the training data. Its guarantee is simultaneous over all $M$ candidates, which is what permits the holdout-selected index to be data-dependent.

Proof. Fix a training data set for which the assumptions hold. For each $j$, the $m$ holdout losses for candidate $j$ are conditionally independent, lie in an interval of width $B$, and have conditional mean $R_j$. Hoeffding’s inequality and the union bound therefore give, for every $t>0$,

P\left(\max_{1\le j\le M}|\widehat R_j-R_j|>t\ \middle|\ \mathcal T\right) \le \sum_{j=1}^M 2\exp\left(-\frac{2mt^2}{B^2}\right) =2M\exp\left(-\frac{2mt^2}{B^2}\right).

Choose $t=B\sqrt{\log(2M/\delta)/(2m)}$. Substitution makes the right-hand side equal to $\delta$. Thus, with conditional probability at least $1-\delta$, every candidate simultaneously satisfies $|\widehat R_j-R_j|\le t$. On this event, use the definition of $\hat j$, then the definition of $j^*$:

R_{\hat j} \le \widehat R_{\hat j}+t \le \widehat R_{j^*}+t \le R_{j^*}+2t.

Since $2t=B\sqrt{2\log(2M/\delta)/m}$, this is the asserted inequality. The conditional guarantee holds for almost every $\mathcal T$; averaging its conditional failure probability over $\mathcal T$ gives the same unconditional guarantee. $\square$

Reading the Bound and Its Dependence on Sample Size

The bound has three principal features. First, increasing $m$ reduces its scale as $m^{-1/2}$. Second, increasing $M$ costs only through $\log M$, because the proof controls a finite collection of deviations simultaneously. Third, a larger loss range $B$ enlarges the guarantee linearly. The confidence parameter also matters: asking for smaller $\delta$ increases $\log(2M/\delta)$.

These are finite-sample statements, not asymptotic approximations. They can nevertheless be conservative: the proof uses a worst-case loss range and a union bound, and the resulting upper bound can exceed the entire range of possible excess risks. In that case, the inequality is valid but offers little practical information.

Worked Example: Two Candidates with Losses in a Range of Width Three

Suppose there are $M=2$ candidates, each loss lies in $[0,3]$, the holdout size is $m=100$, and the desired failure probability is $\delta=0.05$. The width is $B=3$. The theorem gives $$ R_{\hat j}-\min_j R_j \le 3\sqrt{\frac{2\log(2\cdot2/0.05)}{100}} =3\sqrt{\frac{2\log(80)}{100}}. $$

Using $\log(80)\approx4.3820266$, the quantity inside the square root is $2(4.3820266)/100\approx0.0876405$. Its square root is approximately $0.29604145$. Therefore the bound is $3(0.29604145)\approx0.88812435$, or $0.8881$ to four decimal places.

The conclusion is that, with probability at least $0.95$, the selected candidate’s conditional risk is no more than about $0.8881$ above the better of the two candidates. It does not say that the selected candidate is always the better one, nor that this bound is the typical gap.

Worked Example: The Cost of Increasing the Candidate Count

Compare $M=2$ and $M=8$ candidates when losses lie in $[0,1]$, $m=100$, and $\delta=0.05$. With two candidates, the bound is $$ \sqrt{\frac{2\log(2\cdot2/0.05)}{100}} =\sqrt{\frac{2\log(80)}{100}} \approx 0.2960. $$

With eight candidates, the same calculation gives $$ \sqrt{\frac{2\log(2\cdot8/0.05)}{100}} =\sqrt{\frac{2\log(320)}{100}} \approx \sqrt{0.1153664} \approx 0.3397. $$

Thus quadrupling the candidate count increases this bound from about $0.2960$ to $0.3397$, rather than multiplying it by four. The increase is due to the logarithmic dependence on $M$. It is still a real cost: selection has more opportunities to favor a candidate whose holdout estimate happens to be unusually low.

An Expected Excess-Risk Bound

A confidence guarantee is useful when a failure probability is important. An expectation bound gives a complementary summary of the average excess risk over repeated holdout samples, conditional on the training data. It follows from controlling the expected largest absolute estimation error.

Result: Under the theorem’s assumptions, for almost every $\mathcal T$, $$ E[R_{\hat j}-\min_j R_j\mid\mathcal T] \le B\sqrt{\frac{2\log(2M)}{m}}. $$

Derivation. Write $D_j=\widehat R_j-R_j$. Conditional on $\mathcal T$, Hoeffding’s lemma gives, for every real $\lambda$, $$ E[\exp(\lambda D_j)\mid\mathcal T]\le \exp\left(\frac{\lambda^2B^2}{8m}\right). $$ The same bound holds with $-D_j$ in place of $D_j$. For $\lambda>0$, the maximum of $2M$ exponentials is no greater than their sum. Jensen’s inequality for the concave logarithm then implies

E\left[\max_j|D_j|\mid\mathcal T\right] \le \frac{1}{\lambda}\log E\left[\sum_{j=1}^M\{\exp(\lambda D_j)+\exp(-\lambda D_j)\}\ \middle|\ \mathcal T\right] \le \frac{\log(2M)}{\lambda}+\frac{\lambda B^2}{8m}.

The right-hand side is minimized at $\lambda=\sqrt{8m\log(2M)}/B$. Substituting this value yields $$ E[\max_j|D_j|\mid\mathcal T]\le B\sqrt{\frac{\log(2M)}{2m}}. $$ For every holdout sample, the selection argument used in the theorem gives $R_{\hat j}-R_{j^*}\le 2\max_j|D_j|$. Taking conditional expectations proves the stated result. $\square$

This expectation bound has the same square-root dependence on holdout size and logarithmic dependence on candidate count as the high-probability bound. It is not a guarantee that the realized excess risk will be below its expectation.

Worked Example: A Holdout Selection with Three Bernoulli-Loss Candidates

Suppose the loss of each candidate on a fresh observation is Bernoulli, with success probabilities (and hence risks) $0.15$, $0.10$, and $0.25$. Take $m=50$ independent holdout observations and suppose the observed totals of unit loss are $4$, $6$, and $9$, respectively. The empirical risks are $$ \widehat R_1=4/50=0.08,\qquad \widehat R_2=6/50=0.12,\qquad \widehat R_3=9/50=0.18. $$

The holdout rule selects candidate 1, because $0.08$ is the smallest empirical risk. The risk oracle is candidate 2, with risk $0.10$. The selected candidate’s excess risk in this instance is therefore $0.15-0.10=0.05$. These observed counts are possible under the specified Bernoulli risks.

For a $90\%$ confidence guarantee, set $M=3$, $B=1$, and $\delta=0.10$. The bound is $$ \sqrt{\frac{2\log(2\cdot3/0.10)}{50}} =\sqrt{\frac{2\log(60)}{50}} \approx\sqrt{0.1637738} \approx0.4047. $$ Across repeated holdout samples, the theorem guarantees with probability at least $0.90$ that the selected candidate’s excess risk is at most $0.4047$. The particular excess risk $0.05$ is below this threshold; the observed counts alone do not establish the theorem’s repeated-sampling probability guarantee.

Assumptions, Use, and a Common Pitfall

The bound is useful for comparing a finite collection of trained predictors when the holdout set has not influenced their construction. The candidates may be random because they depend on training data; the conditional formulation accounts for that randomness without requiring the candidates to be fixed in advance. The result is relative to the best candidate in this set, so it does not remove approximation error between the set and a broader target.

Holdout independence is essential. Conditional on training data, the validation observations must be independent of how the candidates were constructed. Reusing the holdout outcomes to create or modify the candidates invalidates this direct application.
The losses must share a bounded range. A common interval $[a,b]$ gives the width $B$. If losses are unbounded, this Hoeffding-based result does not apply as stated; an appropriate tail condition and a different concentration argument are needed.
The guarantee is an excess-risk bound. It controls distance from the best candidate risk, not the absolute risk of the selected predictor. If every candidate performs poorly, the excess can still be small.

Common mistake: It is tempting to apply a single-candidate concentration bound to the candidate selected after examining all holdout risks, as though that candidate had been fixed before validation. That reasoning ignores that the identity of the selected candidate depends on the same random errors being controlled. The correction is to control all $M$ candidate deviations simultaneously, as in the union-bound proof. This introduces the $\log M$ term and justifies the data-dependent choice.

The bound also clarifies why a larger holdout set helps but cannot make selection risk vanish instantly: the worst-case guarantee shrinks at order $m^{-1/2}$. More candidates make the bound weaker at order $\sqrt{\log M}$, while a wider loss range scales it proportionally. These dependencies are useful for assessing whether a proposed validation comparison has enough data to support a meaningful guarantee.

Check Your Understanding

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

Why are the candidate risks defined conditional on the training data when candidates themselves can be random?
For losses in $[0,2]$, $M=4$, and $m=200$, write the theorem’s excess-risk bound for confidence level $1-\delta$.
In the proof, where does the factor $M$ enter, and why does it yield a logarithm in the final bound?
What goes wrong if holdout observations were used to modify the candidates before choosing among them?
Does a small excess-risk bound guarantee that the selected predictor has small absolute risk? Explain.