Why an infinite family needs a different count
A continuous parameter can encode infinitely many predictors. For example, even constant functions with form an infinite family. The finite-list union bound from the preceding section cannot be applied by writing : it gives no useful probability. Yet nearby constants produce nearby losses. A finite grid can represent the whole family to a prescribed accuracy, and concentration need only be paid for at its grid points.
This is one concrete capacity argument. It uses a bounded parameter box and a uniform Lipschitz condition on the loss, and its price can be poor in high dimension. It is not a theorem for arbitrary neural networks or an assertion that a parameter count alone controls generalization.
Setup and the grid guarantee
Definition 10.2.1
(Bounded, uniformly Lipschitz loss family)
Let be i.i.d. with the same distribution as a fresh observation , where . For each , with and positive integer , let be a measurable loss in , where . Assume that, for every and every ,
where is deterministic. Define and .
The uniform Lipschitz condition implies that both risk functions are -Lipschitz. It also makes the supremum below measurable: the supremum over the box equals the supremum over its countable dense rational subset, augmented if necessary at its boundary.
The net is built coordinate by coordinate.
Lemma 10.2.2
(A grid net of the parameter box)
For put . The grid of points whose coordinates all lie in has points, and every has a grid point with .
Proof
(Equal spacing of the coordinates)
Divide each coordinate interval into equal segments and take all endpoints. Their spacing is , and the resulting grid has points. For every , some satisfies . This grid is fixed before the sample is drawn.
With the net in hand, concentration is paid only at its points.
Theorem 10.2.3
(A uniform bound from a parameter net)
Choose and . Put , , and
With probability at least ,
If a measurable, possibly data-dependent satisfies for , then on the same event
The infima are attained here because the two risks are continuous on the compact box, though the argument also works by comparing to an arbitrary parameter and taking an infimum. The probability refers to the sample, not to a random choice of parameter after the event has been established.
Proof: cover first, select afterwards
Proof
(Union bound on the grid, then a Lipschitz transfer)
For any fixed grid point, the preceding bounded-average inequality gives
A union bound shows that all grid discrepancies are at most with probability at least . No independence between the losses at different grid points is needed: they are evaluated on the same sample.
On that event, compare an arbitrary parameter to its grid neighbor. The triangle inequality and the two Lipschitz bounds give
One moves the population risk and the other moves the empirical risk. The same grid event controls every parameter, including one chosen after seeing the data.
Finally, for any comparator , apply the uniform event, approximate minimization, and the event again:
Taking the infimum proves the second claim.
Proof X-ray
Why the grid is fixed first, and where each Lr comes from
The argument runs in a strict order. The grid is chosen before the sample, so is a fixed number and the union bound over fixed points is legitimate. Everything after that is deterministic: on the single grid event, the transfer from to uses no probability at all, and therefore holds simultaneously for every , including the data-dependent .
The transfer costs twice, for different reasons. Moving the population risk from to uses the Lipschitz bound averaged over a fresh ; moving the empirical risk uses it at the sampled points. Both follow only because the bound holds for every , and both match the grid because the Lipschitz condition and the cover use the same distance. The radius then appears twice in the final bound, in and inside , which is the trade-off examined below.
This bound compares with the best risk inside the box. If the ideal predictor lies outside the family, the difference between the best family risk and that ideal risk is an additional approximation error.
Worked examples: continuous constants
Worked example 10.2.4
(Absolute loss on a bounded interval)
Suppose almost surely and consider every constant prediction with . The loss lies in and the reverse triangle inequality gives . Thus and . With , and , the grid has points and
Any exact empirical minimizer therefore has risk at most the best constant risk plus about with probability at least . For this absolute loss an empirical median clipped to the interval is such a minimizer. The guarantee is sufficient and distribution-free; it does not say the actual excess risk equals the bound.
Making smaller decreases the approximation term but increases and hence the concentration term. For fixed , taking gives a bound tending to zero as . But : a large dimension can make the guarantee weak. A tighter covering adapted to the functions or to the data distribution may improve it, but that requires a separate argument.
Worked example 10.2.5
(Choosing the grid radius)
Keep the absolute-loss family with and , so because . The table gives , and , rounded.
The approximation term falls by a factor of ten at each row, while grows only through . The bound improves from to and then gets worse: at the extra grid points cost more in than they save in . Any gives a valid bound; the choice only changes how informative it is.
Worked example 10.2.6
(Edge case: the same accuracy in ten dimensions)
Suppose , , and , so each coordinate has grid values and . To make the theorem needs . For this is , so suffices. For , , so the requirement becomes . The dimension enters only logarithmically through , yet that logarithm grows linearly in , and the sufficient sample size grows by a factor of about .
What the assumptions protect
Each hypothesis of the theorem excludes a concrete failure.
Counterexample mode
Bounded loss alone does not control an unrestricted class
Claim: if every loss lies in , then empirical minimizers have population risk close to the best risk. Let be uniform on , let , and allow every measurable predictor from to with squared loss. For any finite sample, the function that is zero exactly at the sampled inputs and one elsewhere has empirical risk zero and population risk one. The all-zero function also has zero empirical risk and population risk zero. Thus an empirical minimizer can generalize badly; bounded loss by itself does not control an unrestricted class. This example does not satisfy the finite-dimensional uniformly Lipschitz parameter hypothesis above.
Common mistake
(Checking the Lipschitz bound only on the observed sample)
The Lipschitz constant must hold uniformly in observations, not merely on the observed sample. The proof moves the population risk to the grid by averaging the bound over a fresh observation ; a bound verified at says nothing about the values of elsewhere, which is exactly where the function in the counterexample above differs from zero.
Common mistake
(Choosing the family after inspecting the data)
A small training error is consequently not, by itself, evidence that its population error is small. Nor does the proof permit choosing a family after inspecting the same data and then pretending it was fixed in advance. A random family constructed from separate independent training data can be treated conditionally if the same deterministic bounds hold for every realized family.
Common mistake
(Applying the bound to unbounded squared loss)
The guarantee does not cover unbounded squared loss without an additional assumption or a different concentration tool. Bounding the parameter alone is not enough: with unbounded , the loss is unbounded even at , as the second exercise shows.
Exercises
Quick check
(For , and , give and . If , and , write the uniform discrepancy bound exactly.)
Solution · Answer
Here and . The stated bound is , since . It is valid but larger than the maximum possible discrepancy of one; this illustrates that a formally correct bound can be uninformative.
Quick check
(Let and . For squared loss , find valid and in the theorem. Explain why bounded alone would not give the same for unbounded .)
Solution
Since , take . Also
so works. If is unbounded, can be arbitrarily large even at ; the bounded-loss inequality then cannot be invoked with .
Quick check
(On the uniform event suppose the best family risk is , , and an algorithm finds an empirical value within of the infimum. Bound its population risk. If the ideal risk is , identify the excess-risk contributions.)
Solution · Answer
The risk is at most . Relative to the ideal risk, the resulting excess bound is : family approximation contributes , uniform estimation contributes , and optimization contributes .
Quick check
(Suppose . What can the theorem say about risks within the parameter family? Is it still necessary to pay for all grid points in this special case?)
Solution · Answer
The pointwise condition with forces for every pair and every . All population and empirical risks are therefore identical across parameters. A one-point cover controls the entire family, so a direct one-function concentration bound avoids the unnecessary factor; the theorem's larger grid remains valid but is loose.