Uniform Metric Entropy Bounds for VC Set Classes

Why Uniform Metric Entropy Matters

A VC dimension limits how many different patterns a class can produce on a finite collection of points. Metric entropy asks a related but different question: how many representatives are needed to approximate the class at a specified resolution? For set classes, the approximation metric depends on a probability measure \(Q\). The useful fact is that finite VC dimension controls the number of representatives at every resolution, with a bound that does not depend on which probability measure is chosen.

This uniformity matters in statistical learning because the measure relevant to approximation may be the unknown data-generating distribution, rather than a particular empirical distribution. The result below supplies a population-metric bound from the VC packing bound established in the earlier material on packing bounds for VC classes. The main step is to turn a large cover into a separated family, or, equivalently, to use a maximal separated family as a cover.

Distance and Covering Numbers

Let \(\mathcal A\) be a nonempty class of measurable subsets of a measurable space \((\mathcal X,\mathcal F)\), and let \(Q\) be a probability measure on that space. Associate each set \(A\) with its indicator function \(1_A\). Their \(L_1(Q)\) distance is

\|1_A-1_B\|_{L_1(Q)} =\int |1_A(x)-1_B(x)|\,dQ(x) =Q(A\triangle B),

where \(A\triangle B=(A\setminus B)\cup(B\setminus A)\) is the symmetric difference. The equality holds because the absolute difference of the two indicators is \(1\) exactly on \(A\triangle B\), and is \(0\) elsewhere. Sets with \(Q(A\triangle B)=0\) therefore have distance zero, even if they are not identical as subsets of \(\mathcal X\).

Definition: For \(\epsilon>0\), a finite collection \(A_1,\ldots,A_m\) from \(\mathcal A\) is an \(\epsilon\)-cover in \(L_1(Q)\) if for every \(A\in\mathcal A\), there is some \(j\) with \(Q(A\triangle A_j)\leq\epsilon\). The covering number \(N(\epsilon,\mathcal A,L_1(Q))\) is the smallest size of such a cover, with value infinity if no finite cover exists. The cover centers are required to belong to \(\mathcal A\).

A family is \(\epsilon\)-separated if every pair of distinct members has distance strictly greater than \(\epsilon\). This strict inequality pairs naturally with covers using closed balls of radius \(\epsilon\): a maximal \(\epsilon\)-separated family must cover the class at radius \(\epsilon\).

The VC Packing Bound and the Entropy Result

We use the following standard VC packing bound, in the convention that separated pairs have distance greater than the displayed scale. If \(\mathcal A\) has VC dimension \(V\geq1\), \(Q\) is any probability measure, and \(0<\delta\leq1\), then every finite \(\delta\)-separated subfamily satisfies

|\mathcal P|\leq e(V+1)\left(\frac{2e}{\delta}\right)^V.

The important feature here is that the right-hand side depends on \(Q\) only through the fact that it is a probability measure: the same bound applies to every \(Q\). We now derive the covering conclusion from this packing bound.

Theorem: Let \(\mathcal A\) be a nonempty class of measurable sets with finite VC dimension \(V\), and let \(Q\) be any probability measure. For \(0<\epsilon\leq1\),

\log N(\epsilon,\mathcal A,L_1(Q)) \leq 10V\log\left(\frac{10}{\epsilon}\right).

The constant \(10\) is a convenient universal choice, not an optimized constant. In particular, the bound is uniform over all probability measures \(Q\).

Proof. First suppose \(V\geq1\). Begin choosing members of \(\mathcal A\) one at a time. After choosing \(A_1,\ldots,A_m\), if their closed \(L_1(Q)\) balls of radius \(\epsilon\) do not cover \(\mathcal A\), choose an \(A_{m+1}\) outside their union. Then \(Q(A_{m+1}\triangle A_j)>\epsilon\) for each \(j\leq m\), so the selected sets are \(\epsilon\)-separated. The packing bound, applied with \(\delta=\epsilon\), prevents this procedure from selecting more than \(e(V+1)(2e/\epsilon)^V\) sets. Thus it must terminate, and on termination the selected sets form an \(\epsilon\)-cover. Consequently,

N(\epsilon,\mathcal A,L_1(Q)) \leq e(V+1)\left(\frac{2e}{\epsilon}\right)^V.

Taking logarithms gives

\log N(\epsilon,\mathcal A,L_1(Q)) \leq 1+\log(V+1)+V\log\left(\frac{2e}{\epsilon}\right).

For \(V\geq1\), \(\log(V+1)\leq V\), and \(1\leq V\). Hence the right-hand side is at most \(V[2+\log(2e/\epsilon)]\). Since \(0<\epsilon\leq1\), this is at most \(10V\log(10/\epsilon)\). The constants do not involve \(Q\), so the inequality holds uniformly over probability measures.

If \(V=0\), no point can belong to some members of \(\mathcal A\) and not others: otherwise that point would be shattered. Thus all members agree pointwise, and any one member covers the class at distance zero. In this case \(N(\epsilon,\mathcal A,L_1(Q))=1\), and the stated inequality holds with both sides equal to zero. \(\square\)

The proof uses maximality in a precise way. A separated family need not itself be a cover; the family becomes a cover because the selection process stops only when no set remains outside the chosen closed balls. The packing result bounds how long that process can continue.

Worked Examples

Worked Example: Thresholds Under a Continuous Distribution

Let \(\mathcal A=\{(-\infty,t]:0\leq t\leq1\}\) on the real line, and let \(Q\) be uniform on \([0,1]\). Find the exact covering number at \(\epsilon=0.2\).

For \(s,t\in[0,1]\), the symmetric difference of the two threshold sets is the interval between \(s\) and \(t\), up to endpoints of \(Q\)-measure zero. Therefore

Q((-\infty,s]\triangle(-\infty,t])=|s-t|.

The covering problem is thus the problem of covering the parameter interval \([0,1]\) by radius-\(0.2\) intervals centered at threshold values. Centers at \(0.2\), \(0.6\), and \(1\) cover \([0,0.4]\), \([0.4,0.8]\), and \([0.8,1]\), respectively. Three centers suffice. Two radius-\(0.2\) intervals have total length at most \(0.8\), so they cannot cover the whole interval \([0,1]\). Therefore \(N(0.2,\mathcal A,L_1(Q))=3\). This class has VC dimension \(1\); the uniform theorem applies, though its bound is much looser than this exact value.

Worked Example: Singleton Sets on a Finite Support

Let \(\mathcal X=\{1,\ldots,10\}\), let \(Q\) assign mass \(1/10\) to each point, and let \(\mathcal A=\{\{i\}:1\leq i\leq10\}\). Its VC dimension is \(1\): one point is shattered, while no two-point set can be shattered because no member of \(\mathcal A\) contains both points.

For distinct \(i\) and \(j\), the symmetric difference of \(\{i\}\) and \(\{j\}\) contains two points. Thus

Q(\{i\}\triangle\{j\})=\frac{2}{10}=0.2.

At \(\epsilon=0.1\), these ten sets are pairwise more than \(\epsilon\) apart. No one of them can cover another with a radius-\(0.1\) ball, so all ten are needed; taking every set as a center also shows ten suffice. Hence \(N(0.1,\mathcal A,L_1(Q))=10\). The theorem gives \(\log N\leq10\log(100)\), a valid but deliberately non-sharp bound.

Worked Example: Intervals on Three Atoms

Let \(Q\) put mass \(1/3\) on each of the points \(1,2,3\), and let \(\mathcal A\) be the class of all intervals on the real line. The distinct traces of intervals on these three points are the empty set, the three singletons, the two adjacent pairs, and the full set. There are seven such traces. The class has VC dimension \(2\): two points can be shattered, but an interval cannot select points \(1\) and \(3\) while excluding \(2\).

Any two different traces disagree on at least one of the three atoms, so their \(L_1(Q)\) distance is at least \(1/3\). At \(\epsilon=1/4\), the seven traces are therefore pairwise more than \(\epsilon\) apart. A cover must include a center for each trace, and the seven traces themselves give a cover. Thus \(N(1/4,\mathcal A,L_1(Q))=7\). This finite-support calculation also illustrates that sets with the same trace have distance zero, regardless of how they differ away from the support of \(Q\).

What the Uniformity Does—and Does Not—Say

The theorem says that for each probability measure \(Q\), the class has a cover whose size is bounded by the same expression. The cover itself may depend on \(Q\). Uniformity concerns the bound, not the identity of the chosen centers. Nor does the result say that every set in the class is close to a fixed finite list chosen without reference to \(Q\).

The rate is logarithmic in resolution after taking the logarithm of the covering number: \(\log N\) is at most a constant times \(V\log(1/\epsilon)\), up to the displayed constant inside the logarithm. Decreasing \(\epsilon\) demands a finer cover, while increasing \(V\) permits greater complexity. The bound is useful even when it is not sharp, because it controls entropy in a metric tied to the distribution of interest.

Common pitfall: A growth-function bound counts the number of traces on a fixed finite sample. It does not, by itself, give a cover in \(L_1(Q)\) for an arbitrary population measure \(Q\). The correction is to use the VC packing bound, which controls separated families directly under each probability measure, and then obtain a cover from a maximal separated family.

A related mistake is to measure distance by the number of points in a symmetric difference without specifying a measure or normalization. Here the distance is \(Q(A\triangle B)\), which always lies between zero and one. The probability-measure assumption is what makes the stated scale range and uniform bound meaningful.

Check Your Understanding

Answer each question using the definitions and argument above.

Why is the \(L_1(Q)\) distance between two indicator functions equal to the probability of their symmetric difference?
In the covering argument, why does a selected set outside all closed radius-\(\epsilon\) balls have distance strictly greater than \(\epsilon\) from every selected center?
Which part of the theorem's bound may depend on \(Q\): the numerical upper bound, the cover centers, both, or neither?
For singleton sets on ten equally likely points, what is the distance between two distinct members, and why does that determine the covering number at \(\epsilon=0.1\)?
Why does a bound on the number of traces on a sample not alone establish a population \(L_1(Q)\) covering bound?