From Metric Entropy to Uniform Deviations

Why a Finite Net Controls an Infinite Class

A uniform-deviation question asks how far empirical risk can be from population risk simultaneously for every predictor in a class. Even when the class is infinite, a finite approximation can make this question manageable: concentration bounds control the finitely many approximating predictors, while a Lipschitz condition limits the effect of replacing any predictor by a nearby one.

The metric matters. Here the net uses the uniform distance between prediction functions. This choice ensures that closeness controls the change in loss at every observation and under the population distribution alike. The result has two contributions: a concentration term that depends on the size of the net, and an approximation term that depends on its radius.

Setup and Definitions

Let \(Z_1,\ldots,Z_n\) be independent and identically distributed observations with common distribution \(P\). Write \(Z_i=(X_i,Y_i)\), where \(X_i\) is an input and \(Y_i\) is an outcome. For a measurable prediction function \(f\), define its loss function by \(\ell_f(x,y)=\ell(y,f(x))\). The population and empirical risks are

Assume the loss is bounded, \(0\leq \ell(y,u)\leq M\), and is Lipschitz in its prediction argument: for a constant \(L\geq 0\),

for every outcome \(y\) and every pair of prediction values \(u,v\) under consideration. For prediction functions, use the uniform distance \(d_\infty(f,g)=\sup_x|f(x)-g(x)|\), where the supremum is over the input domain.

For the probability statement below, assume each loss is measurable and the supremum of deviations over \(\mathcal F\) is measurable; for example, this is automatic when \(\mathcal F\) is countable. A finite net need not make an arbitrary uncountable supremum measurable by itself, so this condition should not be omitted.

The Approximation Step

The key deterministic fact is that a nearby predictor has nearby empirical and population risks. The same uniform distance controls both, which is why the approximation cost in a deviation bound has two contributions.

Proof. By the Lipschitz condition and the definition of the uniform distance, for every observation \((x,y)\), \(|\ell_f(x,y)-\ell_g(x,y)|\leq L|f(x)-g(x)|\leq L\varepsilon\). Averaging this inequality over \(Z_1,\ldots,Z_n\) gives \(|P_n\ell_f-P_n\ell_g|\leq L\varepsilon\). Taking expectation under \(P\) gives \(|P\ell_f-P\ell_g|\leq L\varepsilon\). Finally, add and subtract \(P_n\ell_g\) and \(P\ell_g\), then apply the triangle inequality: \[ |(P_n-P)\ell_f| \leq |P_n\ell_f-P_n\ell_g|+|(P_n-P)\ell_g|+|P\ell_g-P\ell_f| \leq |(P_n-P)\ell_g|+2L\varepsilon. \] This proves the claim. \(\square\)

Uniform-Deviation Bound from a Finite Net

Proof. Fix a realization of the sample. For each \(f\in\mathcal F\), choose a net element \(g\in\mathcal G\) with \(d_\infty(f,g)\leq\varepsilon\). The lemma implies \[ |(P_n-P)\ell_f|\leq |(P_n-P)\ell_g|+2L\varepsilon. \] Therefore, if the supremum over \(\mathcal F\) exceeds \(2L\varepsilon+t\), at least one net element has deviation exceeding \(t\). Thus \[ \left\{\sup_{f\in\mathcal F}|(P_n-P)\ell_f|>2L\varepsilon+t\right\} \subseteq \bigcup_{g\in\mathcal G}\{|(P_n-P)\ell_g|>t\}. \] For a fixed \(g\), the random variables \(\ell(Y_i,g(X_i))\) are independent, identically distributed, and lie in \([0,M]\). Hoeffding's inequality for the difference between their sample mean and expectation gives \[ P\bigl(|(P_n-P)\ell_g|>t\bigr) \leq 2\exp\!\left(-\frac{2nt^2}{M^2}\right). \] The union bound over the \(N\) centers proves the first inequality. Setting \(t=M\sqrt{\log(2N/\delta)/(2n)}\) makes its right-hand side equal to \(\delta\), proving the confidence statement. \(\square\)

This derivation separates the two sources of error. The finite collection contributes a term that grows with \(\log N\); approximating the original class contributes \(2L\varepsilon\). A smaller radius reduces the approximation cost, but may require a larger net. The bound is useful only when the chosen radius and the corresponding net size together produce a meaningful total.

Worked Applications

Common Pitfalls and Interpretation

A frequent error is to control the deviations of net elements and then assert that the same control holds for every predictor, with no additional term. The net approximates predictors; it does not make their losses identical. The correction follows from the lemma: the population risk can shift by as much as \(L\varepsilon\), and so can the empirical risk. The uniform-deviation bound must therefore include \(2L\varepsilon\).

A second error is to use a metric that only controls average prediction error under \(P\), then treat it as though it controls the empirical average for the realized sample. Such control does not follow automatically: an observation can lie where the predictors differ substantially. This tutorial uses the uniform metric precisely to control both averages without an additional argument. Other metrics can support related bounds, but their empirical and population approximation steps must be justified separately.

Finally, a small net radius alone does not guarantee a useful bound. Refining the net can increase \(N\), and the concentration term depends on \(\log N\). The practical choice balances the approximation contribution against the cost of having more net elements. This is the basic route from metric entropy to uniform deviations: quantify how many approximating functions are needed at a given scale, then apply finite-class concentration and account explicitly for the approximation error.