Conditional and Unconditional Validity of a Random Holdout

What Does a Holdout Estimate?

A validation estimate is often reported as if it were simply “the model’s risk.” That phrase can refer to two different quantities. One is the risk of the particular predictor fitted to the training data that were actually observed. The other is the average risk of the learning procedure over hypothetical training samples. A holdout can estimate the first quantity accurately even when the second varies substantially from one training sample to another.

We will make this distinction precise for a single random holdout. Assume the training observations and validation observations are independent samples from the same distribution. Equivalently, one may randomly split an independent and identically distributed sample and condition on the split assignment. The learning rule is deterministic for now. Later we state how to handle a randomized rule without incorrectly treating its validation losses as independent after averaging over its randomization.

Definition: Let $Z_1,\ldots,Z_n$ be the training observations and let $Z'_1,\ldots,Z'_m$ be independent validation observations, all with distribution $P$. A deterministic learning rule maps the training data $T=(Z_1,\ldots,Z_n)$ to a predictor $f_T$. For a loss function $L(f,z)$, the realized-model risk is $$ R(T)=E[L(f_T,Z)\mid T]=\int L(f_T,z)\,dP(z), $$ where $Z\sim P$ is a fresh observation. The holdout estimate is $$ \widehat R_{\mathrm{val}}=\frac{1}{m}\sum_{j=1}^m L(f_T,Z'_j). $$ The average procedure risk is $E_T[R(T)]$, where the expectation is over training samples.

The conditioning matters. Once the training sample is fixed, the fitted predictor is fixed. If the validation observations are independent of training, their losses are then independent observations from the loss distribution of that particular predictor. This is the setting in which a usual bounded-loss concentration bound applies.

Conditional Validity for the Realized Predictor

Suppose the loss is bounded: $a\leq L(f,z)\leq b$ for every predictor and observation under consideration, with $a<b$. Conditional on $T$, each validation loss has mean $R(T)$. Hoeffding’s inequality therefore gives a guarantee centered on the risk of the predictor fitted to that training sample.

Theorem: Under the independent-sample setup above, for a deterministic learning rule and a loss bounded in $[a,b]$, for almost every training sample $T$ and every $\varepsilon>0$, $$ P\left(\left|\widehat R_{\mathrm{val}}-R(T)\right|\geq\varepsilon\mid T\right) \leq 2\exp\left(-\frac{2m\varepsilon^2}{(b-a)^2}\right). $$

Proof. Fix a training sample $T$ outside any null set on which the conditional setup may fail. Then $f_T$ is fixed, and $L(f_T,Z'_1),\ldots,L(f_T,Z'_m)$ are independent, bounded in $[a,b]$, and each has conditional mean $R(T)$. Applying Hoeffding’s inequality to their average gives $$ P\left(\widehat R_{\mathrm{val}}-R(T)\geq\varepsilon\mid T\right) \leq \exp\left(-\frac{2m\varepsilon^2}{(b-a)^2}\right). $$ Applying the same inequality to the negative deviations gives the same bound for $P(R(T)-\widehat R_{\mathrm{val}}\geq\varepsilon\mid T)$. The two deviation events cover the event that the absolute error is at least $\varepsilon$; adding their bounds proves the result. $\square$

This is a conditional guarantee: for each realized training set, the probability is taken over the still-random validation sample. It says the reported estimate is likely to be near that fitted predictor’s risk. It does not say that the fitted predictor’s risk is near the average risk of the learning procedure.

Worked Example: A Conditional Error Bound

Suppose the loss lies in $[0,1]$, the holdout has $m=50$ observations, and we want to control an error of at least $\varepsilon=0.2$. For any fixed realized training set, the theorem gives $$ P\left(\left|\widehat R_{\mathrm{val}}-R(T)\right|\geq 0.2\mid T\right) \leq 2\exp(-2\cdot 50\cdot 0.2^2) =2e^{-4}\approx 0.0366. $$

Thus the bound is at most about 3.66% for the fitted predictor, conditional on its training data. The number does not depend on the value of $R(T)$, but it does depend on the bounded-loss and independence assumptions. For example, if the observed validation estimate is $0.34$, the corresponding two-sided Hoeffding radius at 95% confidence is $$ \sqrt{\frac{\log(2/0.05)}{2\cdot 50}} =\sqrt{\frac{\log 40}{100}} \approx 0.1921. $$ The resulting interval is approximately $[0.1479,0.5321]$ for $R(T)$, with conditional coverage of at least 95% under the stated assumptions.

What Unconditional Validity Does—and Does Not—Add

An unconditional guarantee averages over both training and validation randomness. Integrating the conditional inequality over the distribution of $T$ preserves the same bound, but its center remains the random quantity $R(T)$. This follows from the law of total probability; it does not replace the random center by the average procedure risk.

Result: Under the theorem’s assumptions, $$ P\left(\left|\widehat R_{\mathrm{val}}-R(T)\right|\geq\varepsilon\right) \leq 2\exp\left(-\frac{2m\varepsilon^2}{(b-a)^2}\right). $$ This probability averages over both training and validation samples, and still concerns the difference between the holdout estimate and the risk of the realized predictor.

Derivation. Let $A$ be the event $\{|\widehat R_{\mathrm{val}}-R(T)|\geq\varepsilon\}$. By the law of total probability and the conditional bound, $$ P(A)=E\big[P(A\mid T)\big] \leq E\left[2\exp\left(-\frac{2m\varepsilon^2}{(b-a)^2}\right)\right] =2\exp\left(-\frac{2m\varepsilon^2}{(b-a)^2}\right). $$ The expression inside the expectation is constant in $T$, which gives the final equality. $\square$

By contrast, the error around average procedure risk is $\widehat R_{\mathrm{val}}-E_T[R(T)]$. Its sources of variation include both the validation sample and the training sample. When the relevant second moments exist, the law of total variance gives $$ \operatorname{Var}(\widehat R_{\mathrm{val}}) = E\left[\operatorname{Var}(\widehat R_{\mathrm{val}}\mid T)\right] +\operatorname{Var}\left(E[\widehat R_{\mathrm{val}}\mid T]\right) = E\left[\operatorname{Var}(\widehat R_{\mathrm{val}}\mid T)\right] +\operatorname{Var}(R(T)). $$ The first term reflects validation-sample noise; the second is training-to-training variation in realized risk. Increasing $m$ reduces the first term, but cannot by itself remove the second.

Worked Example: Validation Noise and Training Variation

Consider a learning procedure whose realized risk $R(T)$ equals $0.2$ with probability $1/2$ and $0.8$ with probability $1/2$. Conditional on the training sample, suppose each validation loss is Bernoulli with success probability $R(T)$, and take $m=25$. This is a bounded-loss example with conditionally independent validation losses.

The average procedure risk is $$ E[R(T)]=\tfrac12(0.2)+\tfrac12(0.8)=0.5. $$ The variance of realized risk is $$ \operatorname{Var}(R(T)) =\tfrac12(0.2-0.5)^2+\tfrac12(0.8-0.5)^2 =0.09. $$ For either possible training risk $p$, the conditional variance of the holdout mean is $p(1-p)/25$. Since $0.2(0.8)=0.8(0.2)=0.16$, $$ E[\operatorname{Var}(\widehat R_{\mathrm{val}}\mid T)] =\frac{0.16}{25}=0.0064. $$ Also $E[\widehat R_{\mathrm{val}}\mid T]=R(T)$, so the variance decomposition yields $$ \operatorname{Var}(\widehat R_{\mathrm{val}})=0.0064+0.09=0.0964. $$ Even if the validation sample were made arbitrarily large, the validation-noise term would tend to zero while the $0.09$ training-variation term would remain. A bound centered on $R(T)$ is therefore not, by itself, a concentration bound around $0.5$.

The estimate is nevertheless unbiased for average procedure risk when averaged over both sources of randomness: $$ E[\widehat R_{\mathrm{val}}] =E\big[E[\widehat R_{\mathrm{val}}\mid T]\big] =E[R(T)]. $$ Unbiasedness is an expectation statement, not a guarantee that one reported estimate is close to that expectation. A deviation guarantee around $E[R(T)]$ requires additional control of the distribution of $R(T)$, such as a suitable bound or concentration result for training-to-training variation. No such control follows merely from having many validation observations.

Worked Example: A Holdout Can Miss the Average Procedure Risk

Let each observation be $Z=(X,Y)$, where $X\sim\operatorname{Bernoulli}(1/2)$ and $Y=0$ with probability one. Use zero-one classification loss. The training set has one observation, and the deterministic rule predicts the constant class $f_T(x)=X_1$, where $X_1$ is the training observation’s feature.

If $X_1=0$, the predictor always predicts 0, so every test label is classified correctly and $R(T)=0$. If $X_1=1$, it always predicts 1, so every test label is misclassified and $R(T)=1$. Since $P(X_1=0)=P(X_1=1)=1/2$, $$ E_T[R(T)]=\tfrac12(0)+\tfrac12(1)=0.5. $$ Every validation label is also zero. Therefore the holdout estimate equals $0$ when $X_1=0$ and $1$ when $X_1=1$. In either case, $$ \left|\widehat R_{\mathrm{val}}-E_T[R(T)]\right|=0.5, $$ for every holdout size $m$. Yet $\widehat R_{\mathrm{val}}=R(T)$ exactly, so the conditional holdout guarantee is satisfied perfectly. The example separates accuracy for the realized predictor from concentration around average procedure risk.

Randomized Learning Rules

A randomized learning rule introduces another source of randomness. A common mistake is to average over that randomness first and then apply a conditional Hoeffding argument as though validation losses were independent. They need not be: validation observations may be independent given the randomly selected predictor, but losses that share that predictor can be dependent after it is averaged out.

The clean conditional formulation is to include the learning rule’s random seed in the conditioning information. Suppose $S$ is independent of the training and validation observations, and the rule is deterministic given $(T,S)$. Define $C=(T,S)$, let $f_C$ be the realized predictor, and define $R(C)=E[L(f_C,Z)\mid C]$. Conditional on $C$, the predictor is fixed, so the bounded-loss theorem applies with $R(C)$ as its center. Integrating over both $T$ and $S$ also gives the same unconditional bound around this realized risk.

If the target instead averages over the random seed, then the target conditional on training data is $E_S[R(T,S)\mid T]$. A Hoeffding bound centered at that seed-averaged risk does not follow from the preceding argument: the validation losses share the same realized seed. One must either retain the realized seed in the target or separately analyze the extra variation due to randomization. If algorithmic randomness is not independent of the validation sample, even the conditional independence argument needs additional justification.

Interpreting a Reported Validation Estimate

A conventional holdout estimate is most directly interpreted as an estimate of the risk of the fitted predictor, under the distribution from which the validation observations were sampled. The conditional guarantee is useful precisely because it refers to the model that was actually trained. The unconditional version says the same kind of error control holds when training sets are also viewed as random; it does not change the estimand.

A reported value can be described as estimating average procedure risk in an expectation sense when the split and data-generating assumptions justify $E[\widehat R_{\mathrm{val}}]=E[R(T)]$. But a single holdout value does not automatically carry a small-error guarantee for that average. Such a claim needs an additional argument about training variability, as well as the usual care about whether the validation data were used in selecting or repeatedly adjusting the model.

Common Mistake

Wrong reasoning: “The validation losses are independent and bounded, so Hoeffding’s inequality says the holdout estimate is close to average procedure risk.” This silently changes the center of the bound. Conditional on a training set, the losses are centered at $R(T)$, not at $E_T[R(T)]$. Averaging the conditional tail bound preserves the random center $R(T)$; it does not make training risk nonrandom.

Correction: State the target before applying a concentration result. For the realized predictor, condition on the training data (and on an independent random seed, if present); the holdout losses are then independent and the bound is centered at the realized risk. For average procedure risk, establish an additional bound on the training-to-training variation of $R(T)$. If the learner is randomized and the target averages over its randomness, account for the dependence induced by the shared random predictor rather than assuming the same Hoeffding bound applies.

Key takeaway: Conditional and unconditional holdout guarantees can both be valid while targeting the risk of the realized fitted predictor. Neither, without further assumptions, guarantees that one reported validation estimate is close to risk averaged over training samples or algorithmic randomness.

Check Your Understanding

For each question, identify the relevant conditioning information and the risk quantity being discussed.

What is the center of the bounded-loss Hoeffding bound conditional on a deterministic training sample?
Why does averaging a conditional tail bound over training samples not replace realized-model risk by average procedure risk?
If validation losses are Bernoulli with parameter $R(T)$ conditional on training, what are their conditional mean and the mean of their sample average?
What additional source of variability remains when the validation sample size grows but realized risk varies across training sets?
For a randomized learner, what should be included in the conditioning information to apply the holdout bound to the realized predictor?