Packing Bounds for VC Classes

Why Population Separation Can Be Controlled by VC Dimension

A class of sets may contain infinitely many different sets, yet a probability distribution can make it impossible to distinguish very many of them at a fixed resolution. The relevant question is: how large can a family be if every pair differs on at least an $\varepsilon$ fraction of probability mass? For a class with finite VC dimension, the answer is finite and grows at most polynomially in $1/\varepsilon$.

The argument has two parts. First, a random sample is likely to distinguish a fixed pair of well-separated sets; a sufficiently large sample distinguishes all pairs in a finite family simultaneously. Second, the Sauer–Shelah lemma limits how many different membership patterns the class can produce on that sample. The resulting bound is uniform over the probability distribution and the underlying domain.

Definition: Let $\mathcal A$ be a class of measurable subsets of a space $\mathcal X$, and let $Q$ be a probability distribution on $\mathcal X$. For $A,B\in\mathcal A$, define their $Q$-symmetric-difference distance by $$ d_Q(A,B)=Q(A\triangle B), $$ where $A\triangle B=(A\setminus B)\cup(B\setminus A)$. A family $\mathcal F\subseteq\mathcal A$ is $\varepsilon$-separated under $Q$ if $d_Q(A,B)\geq\varepsilon$ whenever $A,B\in\mathcal F$ are distinct. Here $0<\varepsilon\leq 1$.

This distance is a pseudometric: distinct sets can have distance zero if they differ only on a $Q$-null set. A packing bound therefore counts sets that are separated in probability, not sets that are merely different as pointwise subsets. The class has VC dimension $d$ if $d$ is the largest size of a finite subset of $\mathcal X$ that it shatters; a class of VC dimension zero cannot shatter even a singleton.

Sauer–Shelah lemma: If $\mathcal A$ has VC dimension $d$, the number of distinct traces $\{A\cap S:A\in\mathcal A\}$ on any $m$-point sample is at most $\sum_{j=0}^{d}\binom{m}{j}$. For $m\geq d\geq1$, this is at most $(em/d)^d$.

A Sampling Lemma

The first result turns population separation into distinct membership patterns on one finite sample. The family is fixed before sampling, and all its sets are assumed measurable so that the probabilities below are defined.

Lemma: Suppose $\mathcal F$ is a finite $\varepsilon$-separated family of $M\geq2$ measurable sets under $Q$. Let $X_1,\ldots,X_m$ be independent observations from $Q$, with $m=\left\lceil 2\log(M)/\varepsilon\right\rceil$. There is a realization of the sample on which all $M$ sets have distinct traces.

Proof. Fix distinct $A,B\in\mathcal F$. Their sample traces agree only if every observation avoids $A\triangle B$. By independence and separation, $$ P\bigl((\mathbf 1_A(X_i))_{i=1}^m=(\mathbf 1_B(X_i))_{i=1}^m\bigr) =(1-Q(A\triangle B))^m \leq(1-\varepsilon)^m \leq e^{-\varepsilon m} \leq M^{-2}. $$ Let $C$ be the number of unordered pairs in $\mathcal F$ whose traces agree. Summing the collision probabilities over the $\binom{M}{2}$ pairs gives $$ E[C]\leq \binom{M}{2}M^{-2}<\frac12. $$ Since $C$ is a nonnegative integer, there must be a sample realization with $C=0$; otherwise $C\geq1$ always and $E[C]\geq1$. On that realization no two traces agree. $\square$

A Distribution-Uniform Packing Bound

The sampling lemma applies to any finite separated subfamily. The Sauer–Shelah lemma bounds the number of distinct traces on the sample, which converts the existence of an injective trace map into a bound on the family size.

Theorem: Let $\mathcal A$ be a class of measurable sets with finite VC dimension $d\geq1$. For every probability distribution $Q$, every $0<\varepsilon\leq1$, and every finite $\varepsilon$-separated subfamily $\mathcal F\subseteq\mathcal A$, $$ |\mathcal F|\leq\left(\frac{4e}{\varepsilon}\right)^{2d}. $$ Consequently, the same bound applies to the cardinality of any $\varepsilon$-separated family, including an infinite family: every finite subfamily obeys the bound, so no larger family can exist.

Proof. Write $M=|\mathcal F|$. If $M\leq1$, the result holds immediately. Suppose $M\geq2$, and take $m=\lceil2\log(M)/\varepsilon\rceil$. By the sampling lemma, some sample of size $m$ gives $M$ distinct traces. If $m<d$, there are at most $2^m\leq2^d$ possible traces, so $M\leq2^d\leq(4e/\varepsilon)^{2d}$. It remains to consider $m\geq d$.

For this case, Sauer–Shelah gives $$ M\leq\left(\frac{em}{d}\right)^d. $$ Set $y=M^{1/d}$, so $\log(M)=d\log(y)$. Since $m\leq1+2\log(M)/\varepsilon$, $$ y\leq\frac{em}{d} \leq \frac{e}{d}+\frac{2e}{\varepsilon}\log(y) \leq e+A\log(y),\qquad A=\frac{2e}{\varepsilon}. $$ Here $A\geq2e$. Set $B=4A^2=(4e/\varepsilon)^2$, and define $h(t)=t-A\log(t)-e$. For $t\geq B$, $h'(t)=1-A/t>0$. Also $\log(4A^2)\leq A$ for $A\geq2e$: the difference $A-\log(4A^2)$ is positive at $2e$ and has derivative $1-2/A>0$ thereafter. Therefore $$ h(B)=4A^2-A\log(4A^2)-e \geq3A^2-e>0. $$ If $y\geq B$, monotonicity would imply $h(y)>0$, contradicting $y\leq e+A\log(y)$, which says $h(y)\leq0$. Thus $y<B$, and $M=y^d\leq B^d=(4e/\varepsilon)^{2d}$. This proves the bound for every finite subfamily. Because the bound does not depend on $Q$, it is distribution-uniform. $\square$

Worked Example: A Threshold Packing at Separation 0.25

Let $\mathcal A=\{[0,t]:0\leq t\leq1\}$ on $[0,1]$, and let $Q$ be the uniform distribution. This threshold class has VC dimension $d=1$: it can shatter one point, but cannot shatter two ordered points because it cannot label the smaller point outside while including the larger one. For thresholds $t$ and $s$, $d_Q([0,t],[0,s])=|t-s|$.

The five sets with thresholds $0,0.25,0.50,0.75,1$ are pairwise at distance at least $0.25$. The theorem gives the upper bound $$ |\mathcal F|\leq\left(\frac{4e}{0.25}\right)^2=(16e)^2\approx 1{,}891.60. $$ Because the family size is an integer, this real-valued bound implies $|\mathcal F|\leq1{,}891$. The five displayed thresholds are one valid packing; the bound is a uniform upper limit, not a prediction that a packing of that size can be achieved.

Worked Example: A Different Resolution for the Same VC Dimension

Use the same threshold class and uniform distribution, but set $\varepsilon=0.19$. For thresholds $0,0.2,0.4,0.6,0.8,1$, every pair differs in probability by at least $0.2$, which is greater than $0.19$. Thus these six sets form a $0.19$-separated family.

With $d=1$, the theorem yields $$ |\mathcal F|\leq\left(\frac{4e}{0.19}\right)^2\approx 3{,}274.93. $$ The integer-valued family size is consequently at most $3{,}274$. This bound is larger than the one at separation $0.25$, as expected: a smaller required distance allows a potentially larger packing. The numerical bound is deliberately conservative.

Worked Example: Intervals Under an Arbitrary Distribution

Let $\mathcal A$ be the class of intervals on the real line, and let $Q$ be any probability distribution on the real line, including a discrete distribution with atoms. Intervals have VC dimension $d=2$: two points can be shattered, while three ordered points cannot be shattered because the two outer points cannot both be included while excluding the middle point. At $\varepsilon=0.5$, any $0.5$-separated family satisfies $$ |\mathcal F|\leq\left(\frac{4e}{0.5}\right)^4=(8e)^4\approx223{,}634. $$ The calculation uses $8e\approx21.7463$, so $(8e)^4\approx(21.7463)^4$. No assumptions about a density or the locations of the atoms were needed: the same upper bound applies to every $Q$.

What the Bound Does—and Does Not—Say

The theorem’s value is its uniformity. Its right-hand side depends only on the VC dimension and the requested separation, not on the shape of the domain, the locations of probability mass, or a particular choice of $Q$. For any fixed resolution $\varepsilon>0$, it rules out arbitrarily large separated families in a finite-VC class. The bound grows polynomially in $1/\varepsilon$, with exponent $2d$.

The proof is intentionally not a sharp estimate. The sample size is chosen to distinguish every pair in the finite family using a union bound, and this simple route gives the displayed exponent and constant. In applications, an upper bound can still be useful without being close to the true packing size: it provides a finite, distribution-independent ceiling that can be used to control complexity.

Common pitfall: It is incorrect to say that a sample of size $m$ has only a few traces and therefore every population-separated family is small, without first showing that the sample preserves separation. Two sets can differ on a set of positive probability and nevertheless have identical traces on a particular observed sample. The correction is to choose the sample size using the pairwise collision probabilities, show that one sample distinguishes the entire fixed finite family, and only then apply Sauer–Shelah. The sample is a proof device; the conclusion concerns population distance under the original, arbitrary $Q$.

A related mistake is to treat $d_Q$ as a metric that always distinguishes distinct sets. It is only a pseudometric: sets differing on a $Q$-null region have distance zero and cannot both belong to a positively separated family. The theorem controls distinguishability at resolution $\varepsilon$, not pointwise uniqueness.

Check Your Understanding

Answer each question by identifying the relevant distance, sampling step, or growth bound.

Why can two distinct sets have $d_Q(A,B)=0$, and can both belong to an $\varepsilon$-separated family for $\varepsilon>0$?
For a family of $M\geq2$ sets separated by at least $\varepsilon$, what sample size is used in the sampling lemma, and what is the collision probability for one fixed pair?
Where does the VC dimension enter the proof of the packing theorem?
Why does a finite-subfamily bound also rule out an infinite $\varepsilon$-separated family?
Which part of the argument would fail if one applied Sauer–Shelah before establishing that the sample traces are all distinct?

What You'll Learn