Motivation
A training procedure sees a finite sample, while the predictor it returns will be used on observations that have not yet arrived. The empirical average is therefore both indispensable and potentially misleading. It is indispensable because it is computable from the observations; it is misleading when the same observations are used to search among many possible predictors. A small training error answers a question about the sample. Generalization asks whether that answer remains reliable under fresh sampling.
The distinction appears even without complicated networks. Suppose a binary classifier may assign an arbitrary label to each point of a large finite domain. It can agree with every observed label and behave arbitrarily elsewhere. The problem is not that averages are unreliable for one fixed classifier. The difficulty is the search over a class whose members can adapt to the sample. We need an estimate that holds simultaneously for all candidates, or another argument that accounts for the selection procedure.
This section develops three ways of measuring that search. Counting works for a finite class. Rademacher averages measure the ability to align with independent random signs on a given sample. Covering numbers replace a potentially infinite family of evaluation vectors by a finite collection of approximations. These are complementary descriptions of statistical complexity, rather than automatic guarantees for every loss and every data distribution. The precise sampling and boundedness assumptions carry much of the mathematics.
Definitions
Definition 1.1.1
(Population risk, empirical risk, and approximate ERM)
Let be independent observations with the same distribution on a measurable space. A fixed hypothesis class and measurable loss determine
An -empirical risk minimizer, where , satisfies
The infimum need not be attained; the approximate definition avoids assuming existence of an exact optimizer. Assume all suprema and selected predictors below are measurable, for example by using a finite or countable class, or an appropriately separable parameterization. We will not hide a measurability issue inside an expectation of an arbitrary supremum.
Write . For a deterministic sample , introduce independent signs that are equally likely to be and . Define the absolute empirical Rademacher average by
The absolute value is part of our convention. Equivalently this is the usual one-sided average of the symmetric class . Some texts omit the absolute value; constants and finite-class formulas must be interpreted with the chosen convention. The signs are auxiliary random variables, independent of the data, and do not replace the actual response labels.
For evaluation vectors , use the sample distance . An -net is a finite collection of vectors such that every evaluation vector lies within this distance of one of them. The least possible cardinality, when finite, is the covering number . This is a sample-dependent metric or pseudometric: distinct functions can agree at every sampled point.
Theorem/Proposition
Theorem 1.1.2
(Finite-class uniform convergence and excess risk)
Suppose and . For , with probability at least ,
On this same event, any approximate ERM satisfies
Theorem 1.1.3
(Expected uniform deviation by symmetrization)
Suppose the loss class is bounded and the relevant suprema are measurable. Then
Consequently an approximate ERM with deterministic optimization tolerance obeys
The second result is an expectation bound. It does not itself say that the displayed right-hand side bounds the error with probability . Obtaining a useful high-probability Rademacher theorem requires an additional concentration argument. Also, the complexity here is that of the loss class. Substituting a prediction class without controlling the loss transformation is unjustified.
Proof sketch or proof idea
Proof
(Hoeffding’s inequality and a union bound)
For a fixed hypothesis, the bounded-variable exponential estimate gives
For completeness, the ingredient is when . One proof differentiates the log moment-generating function twice: its second derivative is a variance under an exponentially tilted law, at most because that law is still supported on . Its value and first derivative vanish at zero, so integration gives . Independence multiplies moment-generating functions. Exponential Markov inequality and minimization over give each tail; apply the argument also to .
A union bound over fixed hypotheses gives failure probability at most . Setting this equal to proves the first claim. On the uniform event, compare the selected predictor with a population minimizer :
Proof X-ray
The uniform event is what permits selection
The fixed-hypothesis tail bound uses only independence and the range ; on its own it says nothing about , which depends on the sample. The key move is the union bound: it buys one event on which all deviations are small simultaneously, at the price of replacing by inside the logarithm. On that event the chain of three inequalities uses the uniform bound twice, at the selected and at the comparator , and the definition of approximate ERM once in the middle. The comparator is fixed, so its deviation alone could have been handled by the single-hypothesis bound; it is the selected predictor that needs uniformity. Finiteness of the class enters only through , which is why a class with comparable to defeats the bound.
Proof
(Symmetrization with a ghost sample)
For symmetrization introduce an independent ghost sample . Since , convexity of the supremum of absolute values gives
Independently swapping and leaves their joint distribution unchanged. Thus the last difference may be multiplied pairwise by the independent signs . The triangle inequality splits it into two identical expected absolute Rademacher suprema, proving the factor two. Finally, the deterministic excess-risk comparison uses twice the uniform deviation. If the population infimum is not attained, compare with any hypothesis within of it and let decrease to zero. This yields the factor four asserted above; it is a safe general bound, rather than an optimal constant claim.
Proof X-ray
Where the ghost sample and the signs enter
The population mean is not a sample quantity, so the first move writes it as the mean over an independent ghost sample; Jensen's inequality for the convex map sending a family of numbers to the supremum of their absolute values then moves the expectation over outside. The real idea is the next step. Because and are independent with the same law, swapping any set of pairs leaves the joint law unchanged, so multiplying the th difference by an independent sign changes nothing in distribution; both independence and identical distribution are used here. Only then does the triangle inequality separate the two samples, each contributing one Rademacher average, which is the factor two.
From finite nets to an infinite class
The same Rademacher average can be bounded on a fixed sample by approximating the class with finitely many evaluation vectors.
Lemma 1.1.4
(Single-scale net bound)
Let be a fixed sample with for every and every . If the evaluation vectors of members of form an -net for , then
Proof
(Approximate, then take a maximum over finitely many centers)
Suppose and choose an -net whose centers are evaluation vectors from the class, of size . For every sign vector and every , Cauchy–Schwarz gives
For a fixed center , independence and bound the moment-generating function of by . Applying this to both signs of all centers, taking a logarithm, and optimizing gives
The net pays a deterministic approximation error and a finite-search cost. A tiny radius can make the net enormous, so the bound suggests balancing the two terms. This is a single-scale argument; chaining and entropy integrals require further work.
The net is built on the fixed sample, so it may change with the sample, and its distance measures only the sampled evaluations: it does not claim that two functions are uniformly close on the whole domain. Passing from this sample complexity to a population uniform deviation still requires the ghost-sample symmetrization above.
What a statistical guarantee compares
The comparator in an excess-risk theorem is the best member of the declared class. It is not necessarily the best predictor that could be defined on the observation space. If every member is a poor description of the target, a small excess risk can coexist with a large absolute risk. Enlarging the class may reduce this approximation limitation while increasing the estimation cost. This tradeoff cannot be assessed by looking at training error alone.
There is also a distinction between the distribution of a future observation and the distribution that generated the training sample. All the risk bounds above use the same distribution for both. If deployment changes that distribution, a uniform convergence argument for the training distribution remains mathematically correct but no longer answers the new risk question. The failure is a mismatch of the quantity being estimated, rather than a flaw in the union bound.
Finally, a bound can be numerically larger than one when the loss is at most one. In that case the trivial risk bound is sharper. An uninformative numerical bound is still valid, but it should be reported as uninformative. It is evidence that the chosen argument does not certify the desired accuracy at that sample size; it is not evidence that the actual predictor must fail.
Worked examples
Worked example 1.1.5
(Eight classifiers and a numerical guarantee)
Fix eight classifiers before seeing independent labeled observations. Use zero-one loss and . Then , so . Exact ERM has excess risk at most on the uniform event. If optimization stops within of the best training error, the bound becomes . A training error of also gives the absolute upper bound . These are distinct comparisons: one compares with the best class member, while the other bounds the selected member's own population risk.
Worked example 1.1.6
(A norm-constrained linear class)
Let predictions be with , and suppose each sampled feature satisfies . Symmetry of the parameter ball makes the absolute supremum equal to . Jensen's inequality and cancellation of cross terms imply
For , , and , this prediction-class bound is , independent of ambient dimension. It is not yet a squared-loss bound: squared loss is not globally Lipschitz on unbounded predictions and labels. Bounded ranges or another argument are needed to transfer this calculation to a learning guarantee.
Worked example 1.1.7
(A one-dimensional covering number)
On a fixed sample with , take and . Since , a grid of spacing at most provides a net with at most centers. At and , the displayed net bound is at most . The direct linear-class calculation gives . Both are valid; the coarse net argument loses information and need not be sharp.
Common mistakes
Common mistake
(Choosing the class with the same observations)
An adaptive class is a serious hidden change of assumptions. If model design uses the same observations, the finite class fixed before sampling is no longer the relevant object unless the analysis includes that design search. An untouched validation sample can assess a predictor selected independently of it, but repeatedly selecting against validation results creates another search.
The next example shows what goes wrong when the class is fixed in advance but far too rich.
Counterexample mode
Zero training error over the class of all labelings
Zero training error alone offers no guarantee. On a uniform domain of points with labels always zero, consider the fixed class of all binary functions. Select a function that is zero at sampled points and one elsewhere. It is an exact ERM, yet its population error is at least . With and , this is at least . The loss is bounded and sampling is independent; the class is simply too rich for the desired conclusion. The finite-class theorem is not contradicted: here , so its bound is informative only when is large compared with .
Common mistake
(Treating complexity as a parameter count)
Neither a covering number nor a Rademacher average is just a parameter count. Norm constraints, feature geometry, the metric, and the sample affect these quantities. Finally, statistical error and optimization error have different meanings: solving the empirical problem more accurately reduces but does not shrink a complexity term by itself.
Summary
Uniform convergence repairs the selection bias that arises when empirical averages are compared over a class. Finite counting, sign alignment, and finite nets provide three related ways to control this effect. Every bound has a scope: bounded loss for the finite theorem, explicit measurability for suprema, and a declared metric for covering. Keep those assumptions beside the result when applying it.
Exercises
Quick check
(For hypotheses, bounded loss in , and , find a sufficient integer sample size for exact ERM excess risk at most under the finite-class theorem.)
Solve for .
Solution · Answer
Require . Squaring gives , so suffices. The calculation uses natural logarithms and is sufficient rather than necessary.
Quick check
(If a uniform deviation bound is and the chosen predictor has empirical error within of the empirical infimum, derive the population comparison without assuming the population infimum is attained.)
Compare with a hypothesis whose risk is within of the infimum.
Solution · Answer
For any , choose with . On the uniform event, . Subtract the infimum and let tend to zero to obtain excess risk at most .
Quick check
(For the linear class in the second example, suppose all sampled features are the same unit vector . Express its exact empirical absolute Rademacher average as a scalar expectation and calculate it for .)
The supremum over the ball equals times the norm of , divided by .
Solution · Answer
The sum is , so the exact value is . For two signs their sum is with probabilities ; its expected absolute value is one. The complexity is . The general upper bound remains valid but is larger.
Quick check
(Explain why the memorizing classifier above does not contradict the finite-class theorem. State the class size and estimate the order of its logarithm.)
Count the binary functions on points.
Solution · Answer
There are binary functions on domain points, so . The finite-class bound has scale and is uninformative when greatly exceeds . The theorem does not promise that every finite class generalizes well at every sample size.