Metric Entropy of Bounded Linear Function Classes

Why Parameter Dimension Controls Function Covers

A class of linear functions may contain infinitely many functions, even when its parameter vectors lie in a bounded region. Metric entropy asks how many simple representatives are needed to approximate the class to a specified accuracy. For linear functions, a finite-dimensional parameter net gives a direct answer: if inputs are bounded, nearby parameter vectors produce nearby function values, and hence nearby functions in \(L_2(Q)\).

The key is to keep track of the metric and the scale. A Euclidean parameter net of radius \(\delta\) yields an \(L_2(Q)\) cover at radius at most \(R\delta\), where \(R\) bounds the input norm. The volume of a Euclidean ball then gives a bound whose exponent is the parameter dimension.

Class, Metric, and Covering Number

Let \(d\) be a positive integer, let \(B\geq 0\) and \(R\geq 0\), and consider inputs \(x\in\mathbb{R}^d\). For a parameter vector \(w\in\mathbb{R}^d\), define the linear function \(f_w(x)=w^\top x\). Restrict the parameters to the Euclidean ball of radius \(B\).

Assume the input distribution is supported on the Euclidean ball of radius \(R\): \(Q(\{x:\|x\|_2\leq R\})=1\). Define \(\mathcal{F}_B=\{f_w:w\in\mathbb{R}^d,\ \|w\|_2\leq B\}\). The support condition ensures that every \(f_w\) in this class has a finite second moment. The class can still have zero distance between distinct functions when \(Q\) does not distinguish their parameter vectors; \(L_2(Q)\) is then a pseudometric on the parameterized class.

From Parameter Distance to Function Distance

The first step is a deterministic inequality. It holds pointwise for each input, so averaging it under \(Q\) gives the desired metric comparison.

Proof. Since \(f_w(x)-f_v(x)=(w-v)^\top x\), the Cauchy–Schwarz inequality gives \(|f_w(x)-f_v(x)|\leq\|w-v\|_2\|x\|_2\leq R\|w-v\|_2\). Squaring and integrating with respect to \(Q\) gives \(E[(f_w(X)-f_v(X))^2]\leq R^2\|w-v\|_2^2\). Taking square roots proves the \(L_2(Q)\) inequality. \(\square\)

This lemma means that an approximation in parameter space transfers to an approximation in function space, with the input bound \(R\) setting the scale. It does not assert that parameter distance and function distance are equal: a distribution concentrated on a lower-dimensional set may make some parameter changes invisible.

A Finite-Dimensional Euclidean Net

A Euclidean net is a finite collection of points such that every point in the set of interest lies within a specified distance of one of them. The following volume argument supplies a net for the parameter ball while keeping its centers inside that ball.

Proof. Choose points successively in the radius-\(B\) ball, adding a point whenever it is more than \(\delta\) from every point already chosen. Any finite collection chosen this way is \(\delta\)-separated: distinct centers are more than \(\delta\) apart. The open Euclidean balls of radius \(\delta/2\) around these centers are disjoint. Each lies inside the ball of radius \(B+\delta/2\) centered at the origin, by the triangle inequality.

The volume of a radius-\(r\) Euclidean ball in \(\mathbb{R}^d\) is \(r^d\) times the volume of the unit ball. Comparing the total volume of the disjoint smaller balls with that of the containing ball shows that the number \(m\) of chosen centers satisfies \(m(\delta/2)^d\leq(B+\delta/2)^d\), and thus \(m\leq(1+2B/\delta)^d\). In particular, the selection procedure cannot continue indefinitely: any finite separated collection has size bounded by this same finite number. When the procedure stops, no point of the parameter ball is more than \(\delta\) from the selected centers, so they form a \(\delta\)-net. \(\square\)

The Metric-Entropy Bound

Combining the two lemmas gives the principal covering-number result. For \(B>0\), \(R>0\), and \(\epsilon>0\), use a parameter net with radius \(\delta=\epsilon/R\). Every parameter vector is then within \(\epsilon/R\) of a net center; the first lemma ensures that the associated functions are within \(\epsilon\) in \(L_2(Q)\).

Proof. By the Euclidean-net lemma, choose a \(\delta\)-net \(w_1,\ldots,w_m\) for the parameter ball, with centers in the ball and \(m\leq(1+2B/\delta)^d\). For each \(w\) in the ball, choose a center \(w_j\) satisfying \(\|w-w_j\|_2\leq\delta\). The distance lemma gives \(d_{L_2(Q)}(f_w,f_{w_j})\leq R\delta\). Set \(\delta=\epsilon/R\). Then the functions \(f_{w_1},\ldots,f_{w_m}\) belong to \(\mathcal{F}_B\), cover it at radius \(\epsilon\), and their number satisfies \(m\leq(1+2BR/\epsilon)^d\). This proves the claim. \(\square\)

Taking logarithms yields the corresponding entropy bound \(\log N(\epsilon,\mathcal{F}_B,L_2(Q))\leq d\log(1+2BR/\epsilon)\). The dimension appears as a multiplicative factor in log covering number, or equivalently as the exponent in covering number. The dependence on \(BR/\epsilon\) reflects the ratio between the largest parameter-induced function scale and the desired approximation accuracy.

Degeneracies, Interpretation, and a Common Pitfall

The formula is intended for \(B>0\), \(R>0\), and \(\epsilon>0\). If \(B=0\), the class contains only the zero function, so its covering number is \(1\). If \(R=0\), then \(X=0\) almost surely and every function in the class equals zero in \(L_2(Q)\), again giving covering number \(1\). For positive \(B\) and \(R\), the bound is uniform over all distributions supported on the radius-\(R\) ball; it need not be sharp for any particular \(Q\).

One way to see why the bound can be loose is to write the exact squared distance using the second-moment matrix \(\Sigma=E[XX^\top]\): \(d_{L_2(Q)}(f_w,f_v)^2=(w-v)^\top\Sigma(w-v)\). This follows by expanding \(((w-v)^\top X)^2\) and taking expectation. Since \(\|X\|_2\leq R\) almost surely, \(a^\top\Sigma a=E[(a^\top X)^2]\leq R^2\|a\|_2^2\) for every \(a\). The earlier distance inequality follows again. But if \(\Sigma\) has zero eigenvalues, changes along the corresponding directions have zero \(L_2(Q)\) distance, so counting all \(d\) parameter directions can overstate the true complexity.

Common pitfall: It is incorrect to take a parameter net of radius \(\epsilon\) and conclude that its function values form an \(L_2(Q)\) cover of radius \(\epsilon\). The transfer inequality gives only \(d_{L_2(Q)}(f_w,f_v)\leq R\|w-v\|_2\), so a parameter radius \(\epsilon\) guarantees a function radius \(R\epsilon\), not generally \(\epsilon\). To obtain the latter, use parameter radius \(\epsilon/R\) when \(R>0\).

This bound is useful because it converts finite-dimensional geometry into a distribution-uniform control of function-class size. It is a covering-number statement, not by itself a probability bound or a generalization guarantee. Using metric entropy to establish uniform deviations requires additional arguments, which build on rather than follow automatically from this calculation.