A Complexity Comparison for Candidate Class Families

Why Compare Candidate Classes?

Two candidate classes can have very different numbers of possible labelings on a sample. That difference matters because growth functions and metric entropy quantify how many distinctions a learning procedure must control. A finite class is naturally bounded by its size; intervals have an exact one-dimensional count; and halfspaces have a dimension-dependent VC bound. Comparing these quantities helps identify which complexity bound is useful at a particular sample size.

We work with classes \(\mathcal F\) of measurable sets. A set \(A\in\mathcal F\) labels a point as positive when it lies in \(A\). For points \(x_1,\ldots,x_n\), the trace of \(A\) is the subset of sample indices it labels positive. Different sets can have the same trace, so counting sets in \(\mathcal F\) and counting sample labelings are different tasks.

For a probability measure \(Q\), define the set-class \(L_1(Q)\) distance by \(d_Q(A,B)=Q(A\triangle B)\), where \(A\triangle B\) is the symmetric difference. The covering number \(N(\epsilon,\mathcal F,L_1(Q))\) is the smallest number of \(L_1(Q)\) balls of radius \(\epsilon\) needed to cover \(\mathcal F\); its logarithm is the metric entropy. On a sample, \(Q=P_n\), the empirical measure assigning mass \(1/n\) to each observation.

Three Basic Comparisons

For a class with \(M\) distinct sets, there are at most \(M\) traces and at most \(2^n\) labelings of \(n\) points. Thus \(\Pi_{\mathcal F}(n)\leq \min(M,2^n)\). A class of VC dimension \(v\) has the sharper general bound below when \(v<n\). The finite-class bound can still be useful when \(M\) is small.

Here is a proof that includes the zero-dimensional case. Let \(S(n,v)=\sum_{j=0}^{\min(v,n)}\binom{n}{j}\). We prove the assertion by induction on \(n\), simultaneously for all \(v\). For \(n=0\), there is just one empty trace, so the claim holds. For any \(n\), if \(v=0\), there cannot be two distinct traces: two different label vectors differ at some point, and therefore realize both labels on that singleton. That would shatter one point. Hence \(\Pi_{\mathcal F}(n)\leq 1=S(n,0)\).

Now take \(1\leq v<n\), and fix \(n\) points. Delete the last point from each trace. Let \(\mathcal B\) be the family of resulting traces on the first \(n-1\) points, and let \(\mathcal C\) be the traces that occur both with and without the last point. Counting the original traces gives \(|\mathcal A|=|\mathcal B|+|\mathcal C|\), where \(\mathcal A\) is the original trace family. The VC dimension of \(\mathcal B\) is at most \(v\). The VC dimension of \(\mathcal C\) is at most \(v-1\): if \(\mathcal C\) shattered \(v\) of the first points, each labeling there could be extended both ways at the last point, so the original family would shatter \(v+1\) points. Applying the induction hypothesis to these families gives

where the equality follows from Pascal’s identity. If \(v\geq n\), the bound is simply \(2^n\), since there are only \(2^n\) label vectors. This completes the induction. \(\square\)

Intervals: An Exact Count

Consider all intervals on the real line, including the empty set. Their VC dimension is 2. Any two distinct points can be labeled in all four ways: an interval can contain neither, either one, or both. But among three points in increasing order, the labeling positive, negative, positive cannot be realized by an interval. Thus no three points are shattered.

The growth function is also available exactly. On \(n\) distinct ordered points, every nonempty interval trace is a consecutive block. There are \(n\) blocks of length one, \(n-1\) of length two, and so on, for \(n(n+1)/2\) nonempty blocks. Including the empty trace gives

This equals Sauer’s bound for \(v=2\), since \(1+n+\binom{n}{2}=1+n(n+1)/2\). Repeated sample values cannot increase the trace count, so the formula is the maximum over samples, as required by the definition of the growth function.

Halfspaces: Dimension-Dependent Bounds

For \(d\geq 1\), a halfspace in \(\mathbb R^d\) is a set of the form \(\{x:a^\mathsf{T}x+b\geq 0\}\), with \(a\in\mathbb R^d\) and \(b\in\mathbb R\). The class of all such halfspaces has VC dimension \(d+1\).

For the lower bound, choose \(d+1\) affinely independent points. Given any assignment of positive and negative labels to them, there is an affine function taking value \(1\) at the positive points and \(-1\) at the negative points: the \(d+1\) values determine an affine function uniquely. Its nonnegative region realizes that labeling.

For the upper bound, take any \(d+2\) points \(x_i\). The \(d+2\) augmented vectors \((x_i,1)\) in \(\mathbb R^{d+1}\) are linearly dependent. Thus there are coefficients, not all zero, satisfying \(\sum_i\lambda_i x_i=0\) and \(\sum_i\lambda_i=0\). The positive and negative coefficients are both present. After dividing each side by the common sum of positive coefficients, these identities give a point in the intersection of the convex hulls of the points with positive and negative coefficients. Label the former positive and the latter negative. An affine function defining a halfspace that realizes these labels would be nonnegative on the first group and strictly negative on the second. At the shared convex-combination point, its value would then be both nonnegative and strictly negative, a contradiction. So \(d+2\) points cannot be shattered.

From Growth to Metric Entropy

A trace-count bound immediately gives an empirical covering bound. On a fixed sample, choose one representative set for each distinct trace. Every set in the class has distance zero from the representative with the same trace under \(P_n\). Therefore, for every \(\epsilon>0\),

Consequently, an empirical entropy bound is the logarithm of the corresponding trace bound. For a class of \(M\) sets it is at most \(\log M\); for intervals it is at most \(\log(1+n(n+1)/2)\); and for a VC class of dimension \(v<n\) it is at most \(\log\big(\sum_{j=0}^{v}\binom{n}{j}\big)\). For halfspaces, use \(v=d+1\).

There is also a radius-dependent consequence. The standard uniform VC entropy bound, equivalently obtained from the VC packing bound by taking a maximal separated set, says that for a measurable set class of VC dimension \(v\geq 1\), there is a universal constant \(A\) such that for every probability measure \(Q\) and \(0<\epsilon\leq 1\),

The constant does not depend on \(Q\), the sample size, or the particular class. This gives intervals an entropy bound with exponent 2 and halfspaces in \(\mathbb R^d\) an exponent \(d+1\). For a finite class, the separate bound \(N(\epsilon,\mathcal F,L_1(Q))\leq M\) always applies, so the smaller of the available upper bounds can be used. These bounds describe different information: growth counts distinct sample labelings, while the radius-dependent bound can be useful even when the underlying sample is large or \(Q\) is not empirical.

Common Pitfall and Practical Use

A common mistake is to treat a valid complexity bound as an exact count. For example, Sauer’s lemma gives at most 176 traces for planar halfspaces on ten points; it does not say that 176 traces occur. Another error is to use only the VC bound when a finite class is available: in the preceding example, the finite-class bound of 20 is sharper than its Sauer bound. The correction is to identify what is known about the class, calculate each applicable bound, and compare them at the sample size and metric of interest.

These comparisons matter because a complexity calculation is a tool for judging how demanding a uniform analysis may be, not a replacement for the actual geometry or structure of the class. A small finite class can be controlled by its cardinality; intervals have a particularly transparent exact count; and halfspaces scale with ambient dimension through their VC dimension. For metric entropy, also keep track of the radius: a trace count yields a radius-independent empirical upper bound, whereas a VC entropy estimate explicitly reflects \(\epsilon\).