VC Dimension and Uniform Glivenko–Cantelli Convergence

Why VC Dimension Characterizes Uniform Convergence

A binary class may contain infinitely many sets, yet its members can behave simply on every finite sample. VC dimension measures this finite-sample flexibility: it controls how many different patterns the class can realize on observed points. The central question here is whether that control is exactly what is needed for empirical probabilities to approximate true probabilities uniformly over both the class and the data distribution.

The answer is yes. For measurable classes of sets, finite VC dimension is equivalent to distribution-free uniform Glivenko–Cantelli convergence. The two directions have different proofs. A growth-function bound shows that finite VC dimension makes deviations small uniformly over distributions. Conversely, if the VC dimension is infinite, shattered points allow a distribution under which a substantial fraction of the support is missed by the sample.

Definition: Let $\mathcal C$ be a class of measurable subsets of a measurable space $\mathcal X$. For a probability distribution $P$ on $\mathcal X$, let $X_1,\ldots,X_n$ be independent observations from $P$, and define the empirical probability $$ P_n(A)=\frac{1}{n}\sum_{i=1}^n \mathbf 1\{X_i\in A\}, \qquad A\in\mathcal C. $$ The class is distribution-free uniform Glivenko–Cantelli if, for every $\varepsilon>0$, $$ \sup_P P^n\left\{\sup_{A\in\mathcal C}|P_n(A)-P(A)|>\varepsilon\right\}\longrightarrow 0 \quad\text{as }n\longrightarrow\infty, $$ where the supremum is over all probability distributions on $\mathcal X$. Assume throughout that the displayed suprema define measurable events; standard separability conditions are one way to ensure this.

The VC dimension of $\mathcal C$ is the largest cardinality of a finite set $S\subseteq\mathcal X$ that $\mathcal C$ shatters: for every subset $T\subseteq S$, some $A\in\mathcal C$ satisfies $A\cap S=T$. If sets of arbitrarily large finite cardinality are shattered, the VC dimension is infinite. The growth function $\Pi_{\mathcal C}(m)$ is the maximum number of distinct membership patterns that $\mathcal C$ can realize on $m$ points. Repeated points cannot increase this number.

The Characterization

Theorem: For a measurable class $\mathcal C$ of sets, distribution-free uniform Glivenko–Cantelli convergence holds if and only if $\mathcal C$ has finite VC dimension.

We first establish the deviation bound used for the finite-dimension direction. For $n\varepsilon^2\ge 2$, $$ \sup_P P^n\left\{\sup_{A\in\mathcal C}|P_n(A)-P(A)|>\varepsilon\right\} \le 4\Pi_{\mathcal C}(2n)\exp\left(-\frac{n\varepsilon^2}{8}\right). $$ The bound separates the problem into two parts: the number of patterns the class can produce on a sample, and an exponential concentration term.

Lemma: Under the measurability assumption above, the displayed growth-function deviation bound holds for every $n\varepsilon^2\ge2$.

Proof. Take a second independent sample $X_1',\ldots,X_n'$ from $P$, with empirical measure $P_n'$. Conditional on the first sample, if its supremum deviation exceeds $\varepsilon$, there is a set $A\in\mathcal C$ whose deviation exceeds $\varepsilon$. For this fixed set, $P_n'(A)$ has mean $P(A)$ and variance $P(A)(1-P(A))/n\le 1/(4n)$. Chebyshev's inequality gives $$ P^n\left\{|P_n'(A)-P(A)|\ge\frac{\varepsilon}{2}\right\} \le \frac{1/(4n)}{\varepsilon^2/4} =\frac{1}{n\varepsilon^2} \le\frac12. $$ Thus, with conditional probability at least $1/2$, the second empirical probability is within $\varepsilon/2$ of $P(A)$. On that event, $|P_n(A)-P_n'(A)|>\varepsilon/2$. Integrating over the first sample yields $$ P^n\left\{\sup_{A\in\mathcal C}|P_n(A)-P(A)|>\varepsilon\right\} \le 2P^{2n}\left\{\sup_{A\in\mathcal C}|P_n(A)-P_n'(A)|>\frac{\varepsilon}{2}\right\}. $$

To bound the right-hand probability, condition on the $2n$ observations arranged in pairs $(X_i,X_i')$. Independently swapping the two members of each pair leaves their joint distribution unchanged. Given the pairs, each set $A$ produces a vector of $2n$ membership indicators, and therefore a difference vector with coordinates in $\{-1,0,1\}$. There are at most $\Pi_{\mathcal C}(2n)$ such vectors. For any one vector with coordinates $c_i$, a random swapping gives the difference $n^{-1}\sum_{i=1}^n\sigma_i c_i$, where the $\sigma_i$ are independent random signs and $\sum_i c_i^2\le n$. Hoeffding's inequality gives $$ P\left\{\left|\sum_{i=1}^n\sigma_i c_i\right|>\frac{n\varepsilon}{2}\right\} \le 2\exp\left(-\frac{n^2\varepsilon^2/4}{2n}\right) =2\exp\left(-\frac{n\varepsilon^2}{8}\right). $$ A union bound over the possible difference vectors bounds the conditional probability by $2\Pi_{\mathcal C}(2n)\exp(-n\varepsilon^2/8)$. Combining this with the factor $2$ from the second-sample argument proves the lemma. $\square$

Finite VC Dimension Is Sufficient

If the VC dimension is $d$, the Sauer–Shelah lemma gives, for $m\ge d\ge1$, $$ \Pi_{\mathcal C}(m)\le\sum_{j=0}^{d}\binom{m}{j}\le\left(\frac{em}{d}\right)^d. $$ Consequently, for $n\ge d$ and $n\varepsilon^2\ge2$, $$ \sup_P P^n\left\{\sup_{A\in\mathcal C}|P_n(A)-P(A)|>\varepsilon\right\} \le 4\left(\frac{2en}{d}\right)^d \exp\left(-\frac{n\varepsilon^2}{8}\right). $$ For fixed $d$ and fixed $\varepsilon>0$, the right side tends to zero: its logarithm is at most a constant plus $d\log n-n\varepsilon^2/8$, which tends to $-\infty$. This proves convergence uniformly over all $P$. If $d=0$, all sets in the class have the same membership at every point, so they are identical as subsets of $\mathcal X$; the supremum deviation is then just the deviation for one set and also tends to zero uniformly by the same concentration argument.

Worked Example: Thresholds on the Real Line

Let $\mathcal C=\{(-\infty,t]:t\in\mathbb R\}$. Any one point is shattered: a threshold placed below it excludes it, and a threshold at or above it includes it. But two ordered points $x_1<x_2$ cannot be labeled with $x_1$ excluded and $x_2$ included by a lower threshold. Hence the VC dimension is $1$.

On any $m$ ordered observations, a threshold can include an initial segment of length $0,1,\ldots,m$. Thus $\Pi_{\mathcal C}(m)\le m+1$. With $n=1000$ and $\varepsilon=0.5$, the lemma gives, uniformly over all distributions $P$, $$ P^{1000}\left\{\sup_t|P_{1000}((-\infty,t])-P((-\infty,t])|>0.5\right\} \le 4(2001)\exp\left(-\frac{1000(0.5)^2}{8}\right) =8004e^{-31.25} \approx 2.15\times10^{-10}. $$ The numerical bound is small because the exponential term dominates the linear growth in the number of threshold patterns.

Infinite VC Dimension Is Necessary to Exclude

Now suppose $\mathcal C$ has infinite VC dimension. For each $n\ge2$, choose $n$ distinct points $x_1,\ldots,x_n$ that are shattered, and let $P$ put probability $1/n$ on each point. Write $U$ for the number of these points absent from the sample. Each point is absent with probability $(1-1/n)^n$, so $$ E\left[\frac{U}{n}\right]=\left(1-\frac1n\right)^n\ge\frac14,\qquad n\ge2. $$ Since $0\le U/n\le1$, writing $q=P\{U/n>1/8\}$ gives $$ E\left[\frac{U}{n}\right]\le\frac18(1-q)+1\cdot q =\frac18+\frac78q. $$ It follows that $q\ge1/7$. On the event $U/n>1/8$, take the subset of the $n$ points that were not observed. Shattering guarantees a set $A\in\mathcal C$ whose intersection with these points is exactly that subset. Therefore $P_n(A)=0$, while $P(A)=U/n>1/8$. We have proved $$ P^n\left\{\sup_{A\in\mathcal C}|P_n(A)-P(A)|>\frac18\right\}\ge\frac17. $$ This construction works for every $n\ge2$, so the supremum over $P$ cannot tend to zero. The distribution used may depend on $n$; that is permitted because distribution-free uniform convergence takes a supremum over distributions at each sample size. This proves necessity and completes the characterization.

Worked Example: All Finite Subsets of the Natural Numbers

Take $\mathcal X=\mathbb N$ and let $\mathcal C$ be the class of all finite subsets of $\mathbb N$. Any finite collection of $n$ distinct natural numbers is shattered, since each of its subsets is finite and therefore belongs to $\mathcal C$. The VC dimension is infinite.

For a given $n\ge2$, put the uniform distribution on $\{1,\ldots,n\}$. If $U$ of these points are unseen, the finite set consisting of exactly those $U$ points belongs to $\mathcal C$. Its empirical probability is $0$, and its true probability is $U/n$. The calculation above shows $$ P\left\{\sup_{A\in\mathcal C}|P_n(A)-P(A)|>\frac18\right\} \ge P\left\{\frac{U}{n}>\frac18\right\}\ge\frac17. $$ Thus this class fails the distribution-free uniform Glivenko–Cantelli property, despite every individual set being finite.

Worked Example: A Finite Class and a Direct Bound

Consider $\mathcal C=\{\varnothing,\{a\},\{b\},\{a,b\}\}$ on a space containing distinct points $a$ and $b$. This class has four members, so it can realize at most four patterns on any fixed sample: $\Pi_{\mathcal C}(m)\le4$. Applying the deviation lemma with $n=1000$ and $\varepsilon=0.2$, for which $n\varepsilon^2=40\ge2$, gives $$ \sup_P P^{1000}\left\{\sup_{A\in\mathcal C}|P_{1000}(A)-P(A)|>0.2\right\} \le16\exp\left(-\frac{1000(0.2)^2}{8}\right) =16e^{-5}\approx0.108. $$ This bound is valid for every distribution on the space, including distributions that put no mass on $a$ or $b$. It need not be numerically sharp to establish convergence: for fixed $\varepsilon>0$, $16e^{-n\varepsilon^2/8}$ tends to zero.

What the Characterization Does—and Does Not—Say

Finite VC dimension is a criterion for convergence uniformly across distributions, not a claim that every infinite-VC class fails for each fixed distribution. For a particular $P$, the class might have little effective complexity on the part of the space where $P$ places mass. The necessity proof instead selects, at each sample size, a distribution supported on points the class shatters. That is enough to refute a guarantee that must hold uniformly over all distributions.

Common mistake: “If a class has infinite VC dimension, there must be one fixed distribution under which the empirical probabilities fail to converge.” That conclusion does not follow from the argument above. The construction chooses a possibly different shattered set, and hence a possibly different distribution, for each $n$. The correction is to match the claim to its quantifiers: the theorem characterizes convergence with $\sup_P$ outside the probability. Failure of that property requires a distribution giving a large deviation at each sample size, and the sequence of such distributions may vary with $n$.

The practical value of the result is that it turns a distribution-free convergence question into a combinatorial one. For a binary class, finite VC dimension bounds the number of distinct sample patterns by a polynomial in sample size; the exponential concentration factor then forces uniform deviations to vanish. Infinite VC dimension allows enough patterns to select unseen parts of a carefully chosen support, preventing a distribution-free guarantee.

Check Your Understanding

Use the definitions and proof to answer the following questions.

In the definition of distribution-free uniform Glivenko–Cantelli convergence, where does the supremum over probability distributions appear?
Why does a finite VC dimension make the growth-function bound converge to zero for fixed positive $\varepsilon$?
For the uniform distribution on $n$ shattered points, why does the class contain a set that consists exactly of the unobserved points?
Why is a distribution that depends on $n$ sufficient to disprove distribution-free uniform convergence?
Does infinite VC dimension by itself show failure of Glivenko–Cantelli convergence for every fixed distribution? Explain the quantifier distinction.