Motivation
An expectation guarantee describes repeated sampling, but a fitted predictor is normally deployed after one sample has been observed. We would like to attach a probability statement to that particular training procedure. Two difficulties remain after the introductory symmetrization argument. The uniform deviation can fluctuate above its expectation, and the empirical complexity printed beside a fitted model can fluctuate below its expectation. Both fluctuations must be accounted for if the bound is to use the observed complexity.
A second difficulty is computational and geometric. The class of interest is usually a loss class obtained from predictions by a nonlinear transformation. It is convenient to estimate prediction complexity, but that estimate must survive the transformation. Finally, one coarse covering net can waste information. A chain of finer approximations measures small-scale corrections separately instead of charging the largest distance for every distinction between functions.
We develop these three steps with one fixed convention: the Rademacher supremum contains an absolute value. This convention is useful, but importing constants from a one-sided definition without adjustment can produce a false bound. The proofs below make the constants visible. They establish a usable route from sample geometry to a high-probability risk statement, without claiming the sharpest known constants or treating a divergent entropy estimate as a finite guarantee.
Definitions
Let be i.i.d. with law , and let be a fixed class of measurable functions taking values in . Assume suprema are measurable; finite classes or suitable separable classes suffice. Write
The signs are independent of the sample. The preceding generalization notes prove by introducing an independent sample and swapping observation pairs. We now quantify the fluctuations around those expectations.
Definition 4.1.1
(Coordinate sensitivity and sample geometry)
A function of independent observations has coordinate sensitivities if changing only observation changes its value by at most . On a fixed sample, use the normalized Euclidean distance on evaluation vectors. A finite -net has a center within distance of each vector. Covering numbers below refer to this metric and this sample, not to a population norm.
For contraction, the maps may differ between sample positions, but they must be fixed after the sample is fixed, -Lipschitz on the relevant prediction range together with zero, and zero at the origin. The last condition controls the effect of offsets under the absolute convention. Lipschitz continuity of a squared loss, for example, requires a bounded prediction and response range; it is not a global property of the square function.
Theorem/Proposition
Theorem 4.1.2
(Bounded differences and an empirical complexity guarantee)
If independent coordinates give sensitivities , then
The same inequality holds for . Consequently, for , with probability at least ,
Any -approximate ERM for this loss class then has excess population risk at most twice this right-hand side plus .
Theorem 4.1.3
(Contraction and a finite entropy chain)
For a bounded set and maps as above,
For chaining, take the symmetric evaluation set , with . Put , choose finite -nets inside that set with sizes , and set , . For every integer ,
where denotes the absolute Rademacher average of the original evaluation set.
These nets can depend on the fixed sample. A limiting infinite series gives a useful bound only if its value is finite; the finite- formula remains valid regardless. If , all vectors vanish and the complexity is zero, so no chain is needed.
Proof sketch or proof idea
Proof
(Bounded differences and the data-dependent bound)
Reveal coordinates one at a time and set . For a fixed past, integrate over the unrevealed future. Replacing the newly revealed coordinate changes that conditional expectation by at most , because the original sensitivity bound holds for every future realization. Thus the conditional range of has width at most , and its conditional mean is zero.
If a mean-zero variable lies in an interval of width , its moment-generating function is at most . To justify this ingredient, twice differentiate its log moment-generating function: the second derivative is a variance under a tilted distribution still supported on that interval. That variance is at most , as follows by bounding squared deviation from the interval midpoint. The value and first derivative at zero vanish; integrating twice proves the estimate. Applying it conditionally and using the tower property repeatedly gives
Exponential Markov inequality, optimized at , proves the stated upper tail. Apply the same argument to for the lower tail. If all sensitivities vanish, is constant almost surely and the conclusion is immediate.
For , changing one observation changes every empirical mean by at most , so the supremum changes by at most . The same sensitivity holds for : for each sign vector, the change in the signed average is at most , and taking absolute values, suprema and an expectation preserves this bound. With , a union bound gives simultaneously and . Insert symmetrization to obtain . The ERM comparison uses and the reverse comparison at a nearly population-optimal class member. Letting its approximation tolerance vanish gives the excess-risk claim even if the population infimum is not attained.
Counterexample mode
Bounded differences needs independent coordinates
Claim: the tail bound holds whenever the sensitivities are small, even for dependent observations. Let one fair sign be copied, , and . Changing one coordinate in changes by at most , so and the bound at would be . But , and for every . The repair is independence: the proof integrates the unrevealed coordinates with a law that does not depend on the revealed ones.
The contraction inequality is proved one coordinate at a time with the other signs frozen. The absolute value is dealt with only at the end, and that is where the factor two enters.
Proof
(Contraction by coordinate replacement)
First prove the one-sided inequality for a finite set , replacing one coordinate at a time. Fix coordinate and all other signs, and write their contribution as . Averaging the current sign gives
Lipschitz continuity bounds the last difference by . The expression is symmetric in , so the supremum with equals the supremum with , which is the same average with in place of . Repeat for every coordinate.
For the absolute supremum, first adjoin the zero vector to . Because , the adjoined vector contributes zero to both absolute averages, so neither changes. The positive supremum and the negative supremum are now nonnegative. Their maximum is bounded by their sum, and their expectations are equal since and have the same law. Apply the one-sided result to the positive part and bound the resulting one-sided supremum of over by the absolute supremum over . Dividing by proves the displayed factor , first for finite sets and then by separable approximation.
Proof X-ray
Why the contraction proof pays a factor two
The one-sided step uses only Lipschitz continuity and the independence of the signs; it does not use and loses no constant. The key move is to write the average over one sign as a supremum over a pair : this turns two separate suprema into one expression in which appears as a difference, so the Lipschitz bound applies. Symmetry in then removes the absolute value at no cost.
The centering hypothesis is used exactly once, when zero is adjoined. Without it the adjoined vector would change the transformed average, and the positive and negative suprema need not be nonnegative, so bounding a maximum by a sum would fail; the constant-loss counterexample below shows the conclusion itself then fails. The factor two is the price of that maximum-by-sum step, not of the Lipschitz comparison. Since the one-sided argument replaces coordinates in turn with all other signs fixed, it closes after replacements.
The chaining bound needs no Lipschitz map and no concentration inequality beyond a finite maximal estimate for sign averages.
Proof
(Telescoping through nets at dyadic scales)
For the chain, assign each a center within and use . Telescope as its terminal remainder plus the increments . Cauchy–Schwarz bounds the signed terminal remainder by . Every increment has normalized norm at most . For a finite collection of vectors with normalized norms at most , the sign moment-generating bound and optimization of the exponential parameter give an expected absolute maximum at most . There are at most possible increments at scale . Sum these bounds to finish. No independence between scales is assumed or needed: the supremum of a sum is bounded by the sum of the suprema.
Proof X-ray
Where chaining gains over a single net
Telescoping writes with . The terminal piece needs no counting: Cauchy–Schwarz gives , so it costs at most . The key move is that, although ranges over an infinite set, the increment at scale takes at most values, each of norm at most , so the finite maximal estimate applies scale by scale. A single net at scale would charge the full radius against ; the chain pairs each large count with a small radius.
Reading entropy estimates responsibly
If net sizes grow polynomially in inverse radius, their logarithms grow only linearly in the scale index, while decreases geometrically. The resulting series converges. If an estimated entropy grows too rapidly, one should retain the finite terminal error and optimize the cutoff rather than announce an infinite bound as useful. Moreover, the normalized sample metric is essential to the constants. Replacing it by the unnormalized Euclidean norm changes every radius by .
Worked examples
Worked example 4.1.4
(A data-dependent probability statement)
Take , , and observed absolute loss complexity . Here . The deviation bound is approximately , and exact ERM has excess-risk bound approximately . A tolerance of adds exactly that amount to the excess bound. The observed training error is not required to compute this excess comparison; to bound absolute risk, add the deviation bound to that training error instead.
Worked example 4.1.5
(A shifted squared loss needs centering)
Suppose predictions and responses lie in . For fixed response , define . It vanishes at zero and has derivative bounded in magnitude by four, so contraction gives complexity at most eight times the prediction complexity. The original loss adds . Its extra absolute sign average is at most . Thus the squared-loss complexity is at most eight times prediction complexity plus . A probability theorem for losses in applies after dividing this loss by four, not directly to the unscaled range .
Worked example 4.1.6
(A chain for a scalar prediction family)
Let , , and . The symmetric set has radius at most one. At scale , a parameter grid gives . Hence , including the coarser bound at . The chain is bounded by its terminal radius plus . The infinite series is finite because a geometric factor dominates the square root. This proves the correct order, although the direct linear-class calculation has a better constant.
Common mistakes
Counterexample mode
An uncentered constant defeats a careless contraction claim
Let the prediction class consist only of the zero vector and let . This is zero-Lipschitz, yet its transformed absolute Rademacher average is . The original complexity is zero. The missing condition is centering: subtract the value at zero and separately account for its sign average. Boundedness of the response does not make that offset disappear under an absolute supremum.
The confidence event controls all class members simultaneously, including a data-dependent ERM, but the class must have been fixed independently of the training observations or its design search must be included. The randomness of that event is a fresh draw of the whole training sample. After one sample has been observed, the theorem does not say that the fixed risk of this predictor lies within the bound with some probability; it says that the sampling procedure produces, with at least the stated frequency, samples on which the displayed relation holds. Additional randomness inside the training procedure is harmless, because the uniform event covers every final choice from the declared class. Chaining also does not replace the sampling argument. It estimates a conditional complexity; symmetrization and concentration are what connect that geometry to population risk. Finally, a bound greater than the largest possible loss can be valid and uninformative. Report that limitation instead of treating a large upper bound as proof of bad prediction.
Common mistake
(Accounting for only one fluctuation)
Applying bounded differences to alone and then writing the observed in place of gives . This ignores that can fall below its mean. The correct data-dependent bound spends on each of the two events and pays for plus for the doubled complexity, hence . If the expected complexity is known, the single event gives instead.
Common mistake
(Substituting a search lower bound for the complexity)
The empirical complexity is itself a supremum, which may be difficult to compute exactly. A certified upper bound can replace it throughout the probability statement. A heuristic search that finds only some candidate functions instead gives a lower bound on the supremum; substituting that value as if it were an upper bound is invalid. The statistical theorem does not automatically certify the numerical method used to estimate its complexity term.
Summary
Bounded differences controls both the generalization fluctuation and the empirical-complexity fluctuation. Contraction transfers geometry through a centered Lipschitz loss, while a chain distributes approximation costs over scales. Their assumptions are complementary: none of the three arguments substitutes for the other two.
Exercises
Quick check
(If every loss takes values in an interval of width , derive the empirical-complexity deviation bound with the appropriate concentration term.)
Solution · Answer
The deviation sensitivity is , as is the complexity sensitivity, because replacing an observation changes a function value by at most . Symmetrization is unchanged. Thus on the stated event. A nonzero interval offset is already included in ; range width controls fluctuations, not the absolute size of that complexity.
Quick check
(For , calculate the absolute Rademacher average of the constant vector and explain the contraction counterexample numerically.)
Solution · Answer
The sign sum is with probabilities , so its expected absolute value divided by two is . The zero prediction class has complexity zero, while the constant transformation has complexity despite Lipschitz constant zero.
Quick check
(Prove that adding a fixed vector to an evaluation class increases its absolute complexity by at most .)
Solution · Answer
For every sign vector, use the triangle inequality to separate the translated class from . Then Cauchy–Schwarz in probability gives . Divide by .
Quick check
(Suppose , . Show that the infinite chain converges and identify its dependence on when are fixed.)
Solution · Answer
The logarithm is at most , with only improving the first scale. Each term is bounded by a constant times . The ratio of successive terms tends to , so the sum converges. The terminal radius tends to zero and the final bound has order for fixed .