Motivation
A sample average can be unbiased and still fluctuate too much for a useful decision. The elementary variance bound answers one question about those fluctuations. When every observation lies in a known bounded interval, we can use that stronger information to obtain an exponentially decreasing probability bound. This matters when a prediction procedure compares many alternatives: a guarantee for each alternative separately does not automatically protect the winner selected after seeing their scores.
Imagine training sixty-four candidate predictors using one training set, then comparing their losses on a separate validation set. Before examining the validation labels, the candidates form a fixed list conditional on training. The validation results are random. We want a statement strong enough to remain valid after selecting whichever candidate looks best. The useful event is that every candidate's validation score is close to its population risk simultaneously.
There is another source of confusion. “Bias” can mean a model family cannot represent the target, or it can mean the mean fitted predictor differs from the target. These statements are related but different. We will derive both the finite-family risk comparison and the bias–variance decomposition, specifying the randomness and the loss in each. No theorem below promises that an arbitrary network class is statistically controlled merely because individual predictions are bounded.
Definitions
Let be independent real random variables with common mean , each lying in almost surely, where are known. Identical distributions are sufficient but not necessary here. Set . A concentration inequality bounds the probability of a specified deviation of this random average from its mean.
Definition 10.1.1
(Population and validation risk)
For a prediction rule , define population and validation risks by
The validation observations are i.i.d. and independent of the procedure that produced the candidate list , with . The loss lies in for every candidate, where is a deterministic bound. All finite-family statements can instead be read conditionally on independent training data. They do not require losses of different candidates on the same observation to be independent.
Definition 10.1.2
(Approximate empirical minimizer)
An approximate empirical minimizer belongs to this list and satisfies , with . This tolerance measures incomplete optimization of the validation criterion. It does not account for dependence created by using validation labels to construct new candidates outside the list.
Definition 10.1.3
(Training-average predictor)
For squared-error prediction, write . Let be random training data independent of a fresh test pair , and let be the fitted function. Its training-average prediction is . We assume the joint second moments needed below are finite; conditional means and functions are interpreted up to sets of input probability zero.
Theorem/proposition
Theorem 10.1.4
(Bounded independent averages concentrate exponentially)
Under the boundedness and independence assumptions above, for every ,
Consequently, with probability at least , where , every member of the fixed candidate list satisfies
On this same event, . A probability upper bound larger than one can always be replaced by one.
Theorem 10.1.5
(Training randomness separates squared bias from variance)
Assume and independent training and test data. Then
The three terms are conditional noise, squared bias of the training-average predictor, and variability across training samples. The identity does not say that a particular training procedure minimizes any one of them.
Proof sketch or proof idea
Proof
(Exponential moments and Markov's inequality)
We first prove the exponential-moment fact that drives the first theorem. If , let . Boundedness permits differentiation under the expectation for every real . The second derivative is the variance of under the exponentially tilted probability law. Under any law supported on this interval, variance is at most : the inequality gives a variance bound , whose maximum is the claimed value. Since , integrating the second-derivative bound twice yields
For positive , Markov's inequality and independence multiply these bounds across observations. The resulting upper-tail bound is . Its minimizing value is . Apply the same argument to the negative deviation and add the two probabilities. This proves the two-sided inequality without a normal approximation or an estimated standard deviation.
Proof X-ray
Why one variance bound controls every exponential moment
The decisive observation is that the variance bound holds for every probability law on , so it applies to each exponentially tilted law at once; boundedness is used there and nowhere else. That uniform bound on , together with , integrates to the quadratic bound for the logarithmic moment. Independence is used only to multiply the moment bounds. The free parameter is then chosen to minimize the Markov bound, which produces the factor in the exponent. A finite variance alone bounds at only, not along the whole tilt.
Proof
(A union bound over the fixed list)
Apply the inequality to the validation losses of one fixed candidate, then use the union bound over all candidates. The probability that any candidate violates the tolerance is at most . Choosing the displayed tolerance makes this at most . Once all candidates are controlled, the selected index may depend on every validation result: the same event already covers that index. The proof needs independent observations, not independent models.
On this event, compare the selected rule to any list member: move from population risk to validation risk at cost , use approximate minimization at cost , then return to population risk at another cost . Minimizing over the comparator gives the risk inequality. Relative to an ideal risk , the difference is a separate approximation term. Thus representation, statistical comparison, and imperfect fitting contribute distinct quantities.
When the candidates are random because they were trained on an earlier sample, condition on that entire sample first. For each realized candidate list, the failure probability over independent validation data is at most the same chosen level. Averaging this conditional probability over training randomness preserves the bound. This is why sharing one training set across candidates is harmless here, while allowing validation labels to alter the candidate-generating procedure is a different matter. The independent sample supplies the separation needed by the proof.
Proof X-ray
Where independence is used and where it is not
Independence enters once, inside the exponential-moment step: independence of the validation observations lets the moment generating function of the sum factor into a product. Nothing is assumed about the candidates, whose losses on the same observation may be strongly correlated. The union bound needs no independence at all; it pays the factor by treating the failure events as if they were disjoint.
The non-obvious point is the order of quantifiers. A bound that holds for each fixed index says nothing about a random index chosen after looking at the scores, whereas the simultaneous event over all contains whatever index is chosen. Fixing the list before the validation labels are seen is the hypothesis that makes a fixed number; an adaptive search would have to replace by everything it could have produced. The in the risk inequality records crossing between population and validation risk twice.
Proof
(Conditioning on the training sample)
For the second theorem, condition first on and apply the conditional-mean risk identity to the fresh test pair. Next write . Averaging over training data kills the cross term because . Square integrability justifies the products and interchange of averages. This proof also explains why a training-dependent test response cannot simply be treated as fresh noise.
The decomposition compares the expected risk of a randomly trained predictor with the risk of its training-average function. The former exceeds the latter by the integrated training variance. This does not make the average function directly available: computing it exactly would require averaging over the distribution of possible training sets. Averaging several fitted predictors can sometimes approximate that idea, but their correlation determines how much variability is removed. The identity itself does not assume that a practical collection of fitted predictors is independent.
Worked examples
Worked example 10.1.6
(A probability estimate with a bounded range)
For independent Bernoulli observations, the range length is one. To make the probability of absolute sample-proportion error at least no larger than , it suffices to require . Rounding up gives 738 observations. The earlier variance-only inequality gave a conservative uniform requirement of 2000. The stronger conclusion uses boundedness, and it is still a sufficient condition rather than a necessary sample size. Neither calculation certifies the realized error after inspecting one sample.
Worked example 10.1.7
(Choosing among sixty-four independently trained candidates)
Suppose validation losses lie in , , and . Then . Exact empirical selection has population risk at most the best candidate risk plus about , on an event of probability at least . Allowing optimization tolerance increases that excess bound to about .
The candidates may share training observations, features, or architecture. That does not invalidate this conditional argument if the entire list was fixed before accessing independent validation labels. By contrast, repeatedly inventing additional candidates after examining those labels changes the list being controlled. A valid analysis must include that larger selection procedure or reserve another independent sample.
Worked example 10.1.8
(A biased estimate can have smaller prediction risk)
Let responses be Bernoulli with probability , and fit a constant predictor from independent training responses. Consider with fixed . Its squared bias relative to is , and its training variance is . Fresh-response risk adds the unavoidable noise .
For and , the sample mean has estimation error . Choosing gives squared bias and variance , totaling . Fresh prediction risks are therefore and . The biased rule wins at this distribution. For , however, the sample mean is exact while the same biased rule has estimation error . This is a comparison, not a universal endorsement of shrinkage.
Common mistakes
Finite variance does not imply a bounded range, so it does not justify the exponential bound just proved. A rare, very large loss can have finite variance while violating every proposed small deterministic range. The proof used boundedness in the variance step, and a variance hypothesis cannot replace it.
Counterexample mode
Finite variance does not give the bounded-range exponent
Claim: for independent observations with variance , the inequality holds with replaced by , the squared width of a two-point law with that variance. Take and let equal or with probability each and otherwise. Then , , and . The claimed bound at is , about , far below the actual probability. With the correct range the theorem gives , a trivial but true statement. An exponential bound with a variance-sized exponent needs further hypotheses that this section does not prove.
Common mistake
(Bounding predictions but not responses)
For squared loss, bounding both the response and every prediction in gives the valid range . Bounding predictions alone does not bound squared loss when responses remain unbounded.
Common mistake
(Counting only the models that survive an adaptive search)
A finite list and a class fitted to validation labels are different objects. Merely counting the final few models does not account for every possibility examined during an adaptive search. Likewise, a training score cannot be substituted for an independent validation score in this argument. The proof's target is a simultaneous event for a family fixed independently of the evaluation sample.
A finite net of the class, or a Rademacher complexity, takes the place of the union over a fixed list.
A natural next question
What replaces the logarithm of M for an infinite class?
A finite net of the class, or a Rademacher complexity, takes the place of the union over a fixed list.
The union bound pays , which is useless for a parametric family with infinitely many members. If the loss depends Lipschitz-continuously on a parameter in a bounded set, a finite net of that set can serve as the list, at the cost of a discretization error. Alternatively, the expected largest deviation over the class can be bounded through its Rademacher complexity. The following notes in this chapter develop both routes.
Common mistake
(Confusing approximation error with squared bias)
Bias–variance language must identify the estimator and its randomness. Approximation error is about the best function available in a family. Squared bias is about the mean function produced by a particular training procedure. That procedure may introduce bias even when its family contains the truth. Increasing family size may reduce best-in-family error and still increase the variability of the fitted rule.
Summary
Known boundedness strengthens mean-error control to an exponential probability inequality. A finite union bound makes the guarantee survive selection among a fixed list. The resulting risk comparison separates best-in-family risk, estimation tolerance and fitting tolerance. For squared loss, averaging over independent training samples further separates conditional noise, squared bias and training variance. Each conclusion depends on its stated data split and probability model.
Exercises
Quick check
(Losses lie in for each of sixteen candidates fixed independently of validation. How large must be, using the theorem, to ensure simultaneous risk discrepancy at most with probability at least ? Give an exact logarithmic expression and an integer.)
Solution · Answer
Solving gives . This is approximately , so 1615 observations suffice. The boundedness and independent-validation assumptions are essential to this calculation.
Quick check
(For Bernoulli training data with , compare the squared estimation errors of and . Does this pointwise comparison identify an estimator that is best for every ?)
Solution · Answer
At both rules are unbiased. Their estimation errors are and , respectively, so smaller improves this particular comparison. At the sample mean has zero error while any has positive squared bias. Therefore a conclusion at one distribution does not supply uniform dominance over all Bernoulli laws.
Quick check
(Suppose and every candidate prediction lies in . Find a valid bound for squared loss. If the candidate list's best risk exceeds an ideal risk by , the uniform discrepancy tolerance is , and fitting tolerance is , give the resulting excess-risk bound.)
Solution · Answer
The largest absolute response–prediction difference is five, so is valid; the loss is nonnegative. On the simultaneous event, excess risk over the ideal is at most . A sharper range than the symmetric common-bound shortcut is legitimate because it follows directly from the stated response and prediction intervals.
Quick check
(Explain why a zero training error does not trigger the finite-list theorem. Give a concrete distribution and a training-dependent function with zero training error but population squared risk one.)
Solution · Answer
Let be uniform on and . For a finite realized training input set, define the predictor to be zero on those points and one elsewhere. It is measurable, has zero training loss, and has population risk one because a fresh continuous input hits that finite set with probability zero. The predictor was constructed from the evaluated observations, and the collection of all possible such functions is not the independently fixed finite list in the theorem.