The VC Dimension

What decides whether an infinite class of classifiers can be learned, and from how many examples. Defines restrictions, shattering and the Vapnik–Chervonenkis dimension, and proves that a class shattering arbitrarily large sets is not PAC learnable; proves the VC dimensions of thresholds (1), intervals (2), axis-aligned rectangles (4) and half-spaces in d dimensions (d + 1, by Radon's theorem, also proved), and that the one-parameter class of sine classifiers has infinite VC dimension; proves the Sauer–Shelah–Perles lemma in full and the polynomial bound (em/d)^d on the growth function; states the fundamental theorem of statistical learning with its sample complexity rates, taking the uniform convergence bound from the article on Rademacher complexity and citing the lower bounds. Worked on thresholds and intervals for diabetes from HbA1c in 5,210 NHANES adults: shattering checked on every pair of the 94 HbA1c values, restriction counts against Sauer's bound, and in 30 seeded samples at each of seven sizes the VC bound stands 6 to 11 times above the largest deviation observed, falling at the same rate. Worked problems on signed intervals, Sauer's bound by hand, a Radon partition of a square and the VC bound for intervals.

A threshold rule for diabetes, "predict diabetes when HbA1c is at least $\theta$", has one real parameter, so there are infinitely many such rules. Stored as a 64-bit number, $\theta$ can take about $2^{64}$ values, and the finite-class bound of PAC Learning and Finite Hypothesis Classes would charge for all of them. Yet on a sample of $m$ adults the thresholds can label the sample in at most $m + 1$ ways, because only the position of $\theta$ among the sorted HbA1c values matters. If the number of rules is not what limits learning, what is?

The Vapnik–Chervonenkis (VC) dimension answers it. It is the size of the largest set of points on which the class can produce every possible labeling. Thresholds can label one point both ways but not two points in all four ways, so their VC dimension is 1, although there are infinitely many thresholds. Vapnik and Chervonenkis (1971) introduced the quantity in a paper on the uniform convergence of relative frequencies to probabilities; Blumer, Ehrenfeucht, Haussler and Warmuth (1989) showed, in the words of their abstract, that "the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension".

First we define shattering and the VC dimension and prove that a class that shatters arbitrarily large sets cannot be learned. Then we compute the VC dimension of the classes that can be pictured: thresholds and intervals on the HbA1c values, rectangles, and half-spaces, where Radon's theorem gives the answer $d + 1$. A one-parameter class of sine waves shows that the dimension is not the number of parameters. Next comes the growth function and the Sauer–Shelah–Perles lemma, which says that a class of VC dimension $d$ produces only polynomially many labelings. Finally we state the fundamental theorem of statistical learning and measure its bound against the NHANES data. The article assumes PAC Learning and Finite Hypothesis Classes, whose definitions, finite-class theorems and no-free-lunch theorem it uses.

Notation and the running data

The notation is that of Empirical Risk Minimization and PAC Learning and Finite Hypothesis Classes: examples $(x, y)$ from a distribution $\mathcal{D}$ on $\mathcal{X} \times \{0, 1\}$, a sample $S \sim \mathcal{D}^m$ of size $m$, a class $\mathcal{H}$ of rules $h : \mathcal{X} \to \{0, 1\}$, risk $L_{\mathcal{D}}(h)$, empirical risk $L_S(h)$ and an empirical risk minimizer $h_S$. Logarithms are natural.

The running data are the unit's 5,210 NHANES 2017 to 2018 adults with an HbA1c result (National Center for Health Statistics, 2020), of whom 806 report diagnosed diabetes. As in PAC Learning and Finite Hypothesis Classes, the adults are a finite population and $\mathcal{D}$ draws one of them at random, so risks are exact fractions and samples are draws with replacement. HbA1c is reported in tenths of a percent and takes 94 distinct values. Two classes are used throughout:

  • thresholds $h_\theta(x) = \mathbf{1}\{x \ge \theta\}$, $\theta \in \mathbb{R}$;
  • intervals $h_{a,b}(x) = \mathbf{1}\{a \le x \le b\}$, $a \le b$, together with the rule that is 0 everywhere.

An interval predicts diabetes only inside a band of HbA1c values. On these data the best interval is the band from 6.7% to the largest value, which is the best threshold; the extra parameter buys nothing here, but it doubles the VC dimension.

Restrictions and shattering

Here is the idea in plain words. A class may contain infinitely many rules, but a sample only sees what they do on its own points. Two rules that agree on every sampled point are indistinguishable from the data. So the relevant count is the number of different labelings a class can put on a set of points.

For a finite set $C = \{c_1, \ldots, c_m\} \subseteq \mathcal{X}$, the restriction of $\mathcal{H}$ to $C$ is the set of labelings it produces there,

$$\mathcal{H}_C = \{(h(c_1), \ldots, h(c_m)) : h \in \mathcal{H}\} \subseteq \{0, 1\}^m.$$

The class shatters $C$ if $\mathcal{H}_C$ is all of $\{0, 1\}^m$, that is, $|\mathcal{H}_C| = 2^m$: every labeling of $C$ is produced by some rule. The VC dimension $\mathrm{VCdim}(\mathcal{H})$ is the largest size of a set that $\mathcal{H}$ shatters, or $\infty$ if it shatters sets of every size (Shalev-Shwartz and Ben-David, 2014, Definitions 6.2, 6.3 and 6.5). The empty set is shattered by any nonempty class, so the VC dimension is at least 0.

The definition has an asymmetry worth noting. To show $\mathrm{VCdim}(\mathcal{H}) \ge d$ it is enough to find one set of $d$ points that is shattered. To show $\mathrm{VCdim}(\mathcal{H}) < d + 1$ one must show that no set of $d + 1$ points is shattered, which means finding, for every such set, a labeling that no rule produces.

Why shattering is the right notion. The no-free-lunch theorem of PAC Learning and Finite Hypothesis Classes (Theorem 4 there) builds, for any learner, a failing distribution on a set $C$ of $2m$ points labeled by one of the $2^{2m}$ functions on $C$. If $\mathcal{H}$ shatters $C$, each of those functions agrees on $C$ with some rule of $\mathcal{H}$, so each of those distributions satisfies the realizability assumption for $\mathcal{H}$. That gives the following.

Theorem 1 (shattered sets defeat every learner). If $\mathcal{H}$ shatters a set of $2m$ points, then for every learning algorithm $A$ there are a distribution $\mathcal{D}$ and a rule $h \in \mathcal{H}$ with $L_{\mathcal{D}}(h) = 0$ such that, on $m$ examples, $P(L_{\mathcal{D}}(A(S)) \ge 1/8) \ge 1/7$. Consequently a class of infinite VC dimension is not PAC learnable.

Proof. Run the proof of Theorem 4 of PAC Learning and Finite Hypothesis Classes with $C$ the shattered set. It produces a distribution $\mathcal{D}_i$ on $C \times \{0, 1\}$ labeled by a function $f_i$ on $C$, with $P(L_{\mathcal{D}_i}(A(S)) \ge 1/8) \ge 1/7$. Because $\mathcal{H}$ shatters $C$, some $h \in \mathcal{H}$ equals $f_i$ on $C$, and since $\mathcal{D}_i$ lives on $C$, $L_{\mathcal{D}_i}(h) = 0$. For the second claim, suppose $\mathcal{H}$ had infinite VC dimension and were PAC learnable with sample complexity $m_{\mathcal{H}}$. Take $\varepsilon < 1/8$, $\delta < 1/7$ and $m = m_{\mathcal{H}}(\varepsilon, \delta)$. The class shatters some set of $2m$ points, and the first part gives a realizable distribution on which the learner's risk exceeds $\varepsilon$ with probability above $\delta$, a contradiction. $\square$

This is Corollary 6.4 and Theorem 6.6 of Shalev-Shwartz and Ben-David (2014). Shalev-Shwartz and Ben-David put the intuition in a sentence: "If someone can explain every phenomenon, his explanations are worthless."

Classes whose dimension can be seen

Proposition 1 (thresholds). The thresholds on $\mathbb{R}$ have VC dimension 1.

Proof. One point $c$ is shattered: $\theta = c$ labels it 1 and $\theta = c + 1$ labels it 0. Two points $c_1 < c_2$ are not: a threshold with $h_\theta(c_1) = 1$ has $\theta \le c_1 < c_2$, so it also labels $c_2$ with 1, and the labeling $(1, 0)$ is never produced. $\square$

Proposition 2 (intervals). The intervals on $\mathbb{R}$ have VC dimension 2.

Proof. Two points $c_1 < c_2$ are shattered: $[c_1, c_2]$ gives $(1, 1)$, $[c_1, c_1]$ gives $(1, 0)$, $[c_2, c_2]$ gives $(0, 1)$ and the empty rule gives $(0, 0)$. Three points $c_1 < c_2 < c_3$ are not: an interval containing $c_1$ and $c_3$ contains everything between them, so $(1, 0, 1)$ is never produced. $\square$

On $m$ distinct points sorted in increasing order, a threshold labels a final run of the points 1 and the rest 0, so it produces exactly $m + 1$ labelings. An interval labels a contiguous run 1, or nothing, so it produces $1 + m + \binom{m}{2}$ labelings: the empty one, $m$ runs of one point and $\binom{m}{2}$ runs with distinct first and last points.

The propositions on HbA1c. The script checked both propositions on the data by brute force, letting $\theta$, $a$ and $b$ range over the 0.1 grid. Every one of the 94 HbA1c values is shattered by thresholds. Every one of the 4,371 pairs of values is shattered by intervals, and none by thresholds. For a seeded selection of 60 sets each of three to six values, the counts match $m + 1$ and $1 + m + \binom{m}{2}$, and the labeling $(1, 0, 1)$ is missing from every triple. On all 94 values together the thresholds produce 95 labelings and the intervals 4,466, out of $2^{94}$.

Proposition 3 (rectangles). The axis-aligned rectangles in the plane, $h(x_1, x_2) = \mathbf{1}\{a_1 \le x_1 \le a_2,\ b_1 \le x_2 \le b_2\}$, have VC dimension 4.

Proof. The four points $(-1, 0)$, $(1, 0)$, $(0, -1)$, $(0, 1)$ are shattered. For a labeling, take the smallest rectangle containing the points labeled 1 (the empty rectangle if there are none). It contains a point labeled 0 only if that point lies between the extreme coordinates of the 1-points, and for this diamond no point lies within the box spanned by any others: each point is the unique extreme of the set in one direction. The script confirms all 16 labelings. Now take any five points. Choose a point with the smallest first coordinate, one with the largest, one with the smallest second coordinate and one with the largest. These are at most four points, so some point $c$ of the five was not chosen. The labeling that gives $c$ the label 0 and the others 1 is never produced: a rectangle containing the chosen points contains their bounding box, which is the bounding box of all five and contains $c$. $\square$

This is §6.3.3 of Shalev-Shwartz and Ben-David (2014) and Example 3.14 of Mohri, Rostamizadeh and Talwalkar (2018).

Finite classes. A class with $|\mathcal{H}|$ rules produces at most $|\mathcal{H}|$ labelings of any set, so it cannot shatter a set of $m$ points when $|\mathcal{H}| < 2^m$, and $\mathrm{VCdim}(\mathcal{H}) \le \log_2|\mathcal{H}|$. The bound can be far from the truth: the 201 grid thresholds of PAC Learning and Finite Hypothesis Classes have $\log_2 201 = 7.65$ and VC dimension 1.

Half-spaces and Radon's theorem

A half-space in $\mathbb{R}^d$ labels a point 1 on one side of a hyperplane: $h_{w,b}(x) = \mathbf{1}\{\langle w, x\rangle + b > 0\}$ with $w \in \mathbb{R}^d$ and $b \in \mathbb{R}$. These are the linear classifiers of Support Vector Machines and Vector Space Classification. The class has $d + 1$ parameters, and its VC dimension is $d + 1$. The upper bound rests on a fact of convex geometry.

Theorem 2 (Radon's theorem). Any $d + 2$ points $x_1, \ldots, x_{d+2}$ of $\mathbb{R}^d$ can be split into two nonempty groups whose convex hulls intersect.

Proof. The equations $\sum_i \beta_i x_i = 0$ (one per coordinate, $d$ in all) and $\sum_i \beta_i = 0$ are $d + 1$ homogeneous linear equations in $d + 2$ unknowns, so they have a solution $\beta \ne 0$. Let $I_1 = \{i : \beta_i > 0\}$ and $I_2 = \{i : \beta_i \le 0\}$. Since the $\beta_i$ sum to zero and are not all zero, some are positive and some negative, so both groups are nonempty. Let $\lambda = \sum_{i \in I_1}\beta_i = -\sum_{i \in I_2}\beta_i > 0$. The first equation gives

$$p \;=\; \sum_{i \in I_1}\frac{\beta_i}{\lambda}\,x_i \;=\; \sum_{i \in I_2}\frac{-\beta_i}{\lambda}\,x_i.$$

On each side the weights are nonnegative and sum to 1, so $p$ lies in the convex hull of both groups. $\square$

The theorem carries the name of Radon (1921); the statement and proof here are those of Mohri, Rostamizadeh and Talwalkar (2018, Theorem 3.13).

Theorem 3 (half-spaces). The half-spaces in $\mathbb{R}^d$ have VC dimension $d + 1$.

Proof. The $d + 1$ points $0, e_1, \ldots, e_d$, where $e_i$ is the $i$-th unit vector, are shattered. Given labels $y_0$ for the origin and $y_i$ for $e_i$, set $b = 1/2$ if $y_0 = 1$ and $b = -1/2$ otherwise, and $w_i = 2$ if $y_i = 1$ and $w_i = -2$ otherwise. At the origin $\langle w, 0\rangle + b = b$ has the sign of the label. At $e_i$ the value $w_i + b$ is $\pm 2 \pm 1/2$, which has the sign of $w_i$, as required.

No $d + 2$ points are shattered. Split them by Radon's theorem into groups $I_1$ and $I_2$ with a common point $p$ of their convex hulls, and consider the labeling that is 1 on $I_1$ and 0 on $I_2$. If some half-space produced it, then $\langle w, x_i\rangle + b > 0$ for $i \in I_1$ and $\le 0$ for $i \in I_2$. The function $x \mapsto \langle w, x\rangle + b$ is affine, so at a convex combination of points its value is the same combination of the values. At $p$, written as a combination of the $I_1$ points, it is therefore positive, and written as a combination of the $I_2$ points it is at most 0. That is a contradiction. $\square$

The script checks the construction for $d = 2$ and $d = 3$ by linear programming, finds Radon partitions of 200 random sets of $d + 2$ points in each dimension, and confirms by linear programming that neither labeling of each partition is produced, with the class's own rule (a value above 0 for label 1, at most 0 for label 0).

For a linear classifier on documents, $d$ is the number of terms in the vocabulary, and the VC dimension is $d + 1$, as large as the vocabulary. Bounds that do not grow with $d$ come from other quantities, such as the margin of Support Vector Machines: Shalev-Shwartz and Ben-David (2014, §26.2 and §26.3) derive, through the Rademacher complexity of linear classes, bounds that depend on the norm of $w$ and of the data instead of on $d$.

Parameters are not dimensions: the sine classifiers

Thresholds have one parameter and VC dimension 1, intervals two and 2, half-spaces $d + 1$ and $d + 1$. The pattern fails. Mohri, Rostamizadeh and Talwalkar (2018, Example 3.16) and Shalev-Shwartz and Ben-David (2014, §6.3.5) give the sine classifiers as the standard counterexample: one parameter, infinite VC dimension. We define them as $h_\theta(x) = \mathbf{1}\{\sin(\theta x) > 0\}$ for $\theta \in \mathbb{R}$, on $x > 0$.

Here is the idea. A large frequency $\theta$ makes $\sin(\theta x)$ oscillate fast enough to put any pattern of signs on the points $2, 4, 8, \ldots, 2^d$. Writing $\theta/\pi$ in binary makes the pattern readable: the sign at $x = 2^k$ is decided by the $k$-th binary digit of $\theta/\pi$.

Theorem 4 (a one-parameter class of infinite VC dimension). For every $d$, the class $\{h_\theta : \theta \in \mathbb{R}\}$ shatters the points $2^1, 2^2, \ldots, 2^d$. Hence its VC dimension is infinite.

Proof. Given labels $y_1, \ldots, y_d$, let $b_k = 1 - y_k$ and

$$u = \sum_{j=1}^d b_j 2^{-j} + 2^{-(d+1)}, \qquad \theta = \pi u.$$

So $u$ is the binary fraction $0.b_1 b_2 \ldots b_d 1$. Fix $k \le d$. Then $2^k u = N + f$ with

$$N = \sum_{j=1}^k b_j 2^{k-j}, \qquad f = \sum_{j=k+1}^d b_j 2^{k-j} + 2^{k-d-1}.$$

$N$ is an integer whose last binary digit is $b_k$, so $N$ is even exactly when $b_k = 0$. The fractional part satisfies $f \ge 2^{k-d-1} > 0$ and $f \le \sum_{j=k+1}^d 2^{k-j} + 2^{k-d-1} = 1 - 2^{k-d} + 2^{k-d-1} = 1 - 2^{k-d-1} < 1$. Now $\sin(\theta 2^k) = \sin(\pi N + \pi f) = (-1)^N \sin(\pi f)$, and $\sin(\pi f) > 0$ because $0 < f < 1$. So $\sin(\theta 2^k) > 0$ exactly when $N$ is even, that is, when $b_k = 0$, that is, when $y_k = 1$. Every labeling of the $d$ points is produced, and $d$ was arbitrary. $\square$

Example (the labeling 1, 0, 1). For $d = 3$ the bits are $b = (0, 1, 0)$, so $u = 0.0101$ in binary, $u = 5/16$ and $\theta = 5\pi/16$. Then $\sin(2\theta) = 0.924$, $\sin(4\theta) = -0.707$ and $\sin(8\theta) = 1$: positive, negative, positive, as required. The script checks every labeling for $d$ up to 12, both numerically and through the exact parities of $N$.

Example (an infinite class can be learnable, and a one-parameter class may not be). The thresholds are infinitely many and have VC dimension 1, so by the theorem below they are PAC learnable. The sine classifiers have one parameter, like the thresholds, and are not PAC learnable at all, by Theorem 1. Neither the number of rules nor the number of parameters decides learnability; the size of the largest shattered set does.

The growth function and the Sauer–Shelah–Perles lemma

Shattering is all or nothing. The growth function counts how much of $\{0, 1\}^m$ the class covers on the worst set of $m$ points:

$$\tau_{\mathcal{H}}(m) = \max_{C \subseteq \mathcal{X},\ |C| = m}|\mathcal{H}_C|$$

(Shalev-Shwartz and Ben-David, 2014, Definition 6.9). Up to $m = \mathrm{VCdim}(\mathcal{H})$ it equals $2^m$. Thresholds have $\tau(m) = m + 1$ and intervals $\tau(m) = 1 + m + \binom{m}{2}$, from the counts above. Both are polynomials of degree equal to the VC dimension. The lemma below says that this is no accident: once $m$ passes the VC dimension $d$, the growth function can grow only like $m^d$, never exponentially.

Here is the plan of the proof. We prove something stronger: the number of labelings of a set is at most the number of its subsets that the class shatters. The proof removes one point and splits the labelings into those that the remaining points determine and those that come in pairs differing only at the removed point. Each part is bounded by induction, and the paired part pays only for shattered sets that contain the removed point.

Theorem 5 (Sauer–Shelah–Perles lemma). Let $\mathcal{H}$ be nonempty.

(a) For every finite set $C$, $|\mathcal{H}_C| \le |\{B \subseteq C : \mathcal{H} \text{ shatters } B\}|$.

(b) If $\mathrm{VCdim}(\mathcal{H}) \le d$, then for every $m$, $\tau_{\mathcal{H}}(m) \le \sum_{i=0}^d \binom{m}{i}$.

Proof. (a) By induction on $m = |C|$, for all classes at once. For $m = 0$ both sides are 1: there is one labeling of the empty set, and the empty set is shattered. Suppose (a) holds for all classes and all sets of size $m - 1$, and let $C = \{c_1, \ldots, c_m\}$ and $C' = \{c_2, \ldots, c_m\}$. Sort the labelings in $\mathcal{H}_C$ by their values on $C'$. Let

$$Y_0 = \{v \in \{0, 1\}^{m-1} : (0, v) \in \mathcal{H}_C \text{ or } (1, v) \in \mathcal{H}_C\}, \qquad Y_1 = \{v : (0, v) \in \mathcal{H}_C \text{ and } (1, v) \in \mathcal{H}_C\}.$$

A labeling $v$ of $C'$ that occurs once in $\mathcal{H}_C$ is counted in $Y_0$ only; one that occurs with both values at $c_1$ is counted in both. So $|\mathcal{H}_C| = |Y_0| + |Y_1|$.

$Y_0$ is the restriction $\mathcal{H}_{C'}$. By the induction hypothesis, $|Y_0| \le |\{B \subseteq C' : \mathcal{H} \text{ shatters } B\}|$, the number of shattered subsets of $C$ that do not contain $c_1$.

For $Y_1$, let $\mathcal{H}'$ be the set of rules $h \in \mathcal{H}$ that have a partner $h' \in \mathcal{H}$ with $h'(c_1) = 1 - h(c_1)$ and $h'(c_j) = h(c_j)$ for $j \ge 2$. The partner is then also in $\mathcal{H}'$, with $h$ as its partner. The labelings of $C'$ produced by $\mathcal{H}'$ are exactly those in $Y_1$, so $Y_1 = \mathcal{H}'_{C'}$, and by the induction hypothesis applied to $\mathcal{H}'$, $|Y_1| \le |\{B \subseteq C' : \mathcal{H}' \text{ shatters } B\}|$. If $\mathcal{H}'$ shatters $B \subseteq C'$, it also shatters $B \cup \{c_1\}$: each labeling of $B$ comes from some $h \in \mathcal{H}'$, and $h$ and its partner extend it with both values at $c_1$. Since $\mathcal{H}' \subseteq \mathcal{H}$, the map $B \mapsto B \cup \{c_1\}$ sends each subset counted for $Y_1$ to a different subset of $C$ that contains $c_1$ and is shattered by $\mathcal{H}$. So $|Y_1|$ is at most the number of shattered subsets of $C$ that contain $c_1$ (if $\mathcal{H}'$ is empty, $Y_1$ is empty and the bound is trivial).

Adding the two bounds, $|\mathcal{H}_C|$ is at most the number of shattered subsets of $C$ that omit $c_1$ plus the number that contain it, which is the number of shattered subsets of $C$.

(b) If $\mathrm{VCdim}(\mathcal{H}) \le d$, a shattered subset has at most $d$ elements, and a set of $m$ points has $\sum_{i=0}^d\binom{m}{i}$ subsets of at most $d$ elements. Apply (a) to the set $C$ of size $m$ that attains $\tau_{\mathcal{H}}(m)$. $\square$

The proof of (a) is that of Shalev-Shwartz and Ben-David (2014, Lemma 6.10), written out. Shalev-Shwartz and Ben-David attribute the lemma to Sauer (1972), proved in response to a problem of Erdős, and to Shelah (1972) with Perles; Mohri, Rostamizadeh and Talwalkar (2018, §3.5) add that Vapnik and Chervonenkis (1971) gave it first, in a somewhat different version. Shelah's paper states the finite case as a result that "Perles and I prove", and adds that "Later and independently Sauer [...] proved it."

The bound is attained: thresholds and intervals have $\tau(m) = \sum_{i \le d}\binom{m}{i}$ exactly. Its consequence is the polynomial growth that the learning theory needs.

Corollary 1. If $\mathrm{VCdim}(\mathcal{H}) = d \ge 1$ and $m \ge d$, then $\tau_{\mathcal{H}}(m) \le (em/d)^d$.

Proof. Since $m/d \ge 1$, multiplying each term by $(m/d)^{d-i} \ge 1$ and then adding the terms for $i > d$ only increases the sum:

$$\sum_{i=0}^d\binom{m}{i} \;\le\; \sum_{i=0}^m\binom{m}{i}\Big(\frac{m}{d}\Big)^{d-i} \;=\; \Big(\frac{m}{d}\Big)^d\sum_{i=0}^m\binom{m}{i}\Big(\frac{d}{m}\Big)^i \;=\; \Big(\frac{m}{d}\Big)^d\Big(1 + \frac{d}{m}\Big)^m \;\le\; \Big(\frac{m}{d}\Big)^d e^d,$$

using the binomial theorem and $1 + u \le e^u$ (Lemma 1 of PAC Learning and Finite Hypothesis Classes with $-u$). $\square$

This is Corollary 3.18 of Mohri, Rostamizadeh and Talwalkar (2018). So a class has one of three behaviors: $\tau(m) = 2^m$ for every $m$ (infinite VC dimension); $\tau(m) \le (em/d)^d$ from $m = d$ on (VC dimension $d \ge 1$); or $\tau(m) = 1$ for every $m$ (VC dimension 0: no single point is labeled both ways, so all rules agree everywhere and the class has one distinct rule).

Checks. On random classes the stronger statement (a) can be tested directly. The script drew 2,000 random classes of labelings on six points (seed 117,100,000), with VC dimensions from 0 to 5. For every one, the number of labelings was at most the number of shattered subsets, which was at most $\sum_{i \le d}\binom{6}{i}$. For 56 of them the first inequality was an equality.

On the NHANES data the growth function's worst case is not reached. A sample of $m$ adults contains repeated HbA1c values, and only distinct values count. With $u$ distinct values among the sampled adults, thresholds produce $u + 1$ labelings and intervals $1 + u + \binom{u}{2}$. The table gives the medians over 30 samples (seeds 117,000,001 to 117,000,030).

$m$ $2^m$ Sauer, $d = 1$ thresholds on HbA1c Sauer, $d = 2$ intervals on HbA1c
5 32 6 6 16 16
10 1,024 11 9 56 37
20 1,048,576 21 15 211 106
100 $1.3 \times 10^{30}$ 101 29.5 5,051 421.5
1,000 $1.1 \times 10^{301}$ 1,001 66 500,501 2,146
Number of labelings of m sampled adults, on log scales: all labelings, Sauer's bound for VC dimension 1 and 2, and the labelings produced by thresholds and intervals on the HbA1c values (median of 30 samples). Notice that the bounds are polynomial while 2^m leaves the chart by m = 30, and that the observed counts fall below the bounds from about m = 10, once samples start to repeat HbA1c values.
Number of labelings of m sampled adults, on log scales: all labelings, Sauer's bound for VC dimension 1 and 2, and the labelings produced by thresholds and intervals on the HbA1c values (median of 30 samples). Notice that the bounds are polynomial while 2^m leaves the chart by m = 30, and that the observed counts fall below the bounds from about m = 10, once samples start to repeat HbA1c values.

The fundamental theorem of statistical learning

Theorem 1 showed that infinite VC dimension rules out learning. The converse holds as well, and with it a list of properties turn out to be the same property.

Theorem 6 (the fundamental theorem of statistical learning). Let $\mathcal{H}$ be a class of functions from $\mathcal{X}$ to $\{0, 1\}$, with the 0-1 loss. The following are equivalent:

  1. $\mathcal{H}$ has the uniform convergence property;
  2. any ERM rule is a successful agnostic PAC learner for $\mathcal{H}$;
  3. $\mathcal{H}$ is agnostic PAC learnable;
  4. $\mathcal{H}$ is PAC learnable;
  5. any ERM rule is a successful PAC learner for $\mathcal{H}$;
  6. $\mathcal{H}$ has finite VC dimension.

This is Theorem 6.7 of Shalev-Shwartz and Ben-David (2014). Most of the implications are proved on this site:

  • 1 ⇒ 2 is the reduction of PAC Learning and Finite Hypothesis Classes: on an $(\varepsilon/2)$-representative sample every ERM is within $\varepsilon$ of the best rule (Empirical Risk Minimization, Proposition 1).
  • 2 ⇒ 3, 3 ⇒ 4 and 2 ⇒ 5 are immediate from the definitions: an agnostic learner is a realizable learner when the best risk is zero.
  • 4 ⇒ 6 and 5 ⇒ 6 are Theorem 1 above: a learnable class cannot have infinite VC dimension.
  • 6 ⇒ 1 is the hard step. Its two ingredients are Theorem 5 (finite VC dimension gives polynomial growth) and a symmetrization argument that replaces the risk by the error on a second, "ghost" sample, so that only the labelings of $2m$ points matter and a union bound over at most $\tau_{\mathcal{H}}(2m)$ of them applies. Shalev-Shwartz and Ben-David (2014, Theorem 6.11) prove in this way that with probability at least $1 - \delta$, every $h$ has $\lvert L_{\mathcal{D}}(h) - L_S(h)\rvert \le \big(4 + \sqrt{\ln\tau_{\mathcal{H}}(2m)}\big)/\big(\delta\sqrt{2m}\big)$. On this site the step is completed in Rademacher Complexity, which proves the symmetrization by a ghost sample and, from Theorem 5 and Corollary 1 here, the explicit bound of Mohri et al. given below (Corollary 1 there) and its two-sided form, $\lvert L_{\mathcal{D}}(h) - L_S(h)\rvert \le \sqrt{2d\ln(em/d)/m} + \sqrt{\ln(2/\delta)/(2m)}$ for every $h$ with probability at least $1 - \delta$ (the second statement of that Corollary 1). For $m \ge d$ the right side decreases to 0 as $m$ grows, so for every $\varepsilon$ and $\delta$ some sample size $m^{\mathrm{UC}}_{\mathcal{H}}(\varepsilon, \delta)$ makes it at most $\varepsilon$, which is the uniform convergence property. We use that result here and do not prove it twice. That page assumes that the suprema involved are measurable, a condition that holds for the thresholds and intervals on the NHANES grid (finitely many distinct rules there) and that Shalev-Shwartz and Ben-David also set aside; the theorem is to be read with it. Its bound needs $d \ge 1$. For $d = 0$ no point is labeled both ways, so every rule agrees with every other at every point, the class has one distinct rule, and Hoeffding's inequality for that one rule gives uniform convergence directly.

The equivalence says more than that finite VC dimension suffices. If a class can be learned at all, ERM learns it, and it learns it because training errors converge to risks uniformly over the class. In binary classification there is no learnable class that needs a cleverer algorithm than ERM, a statement that fails for more general learning problems (Shalev-Shwartz and Ben-David, 2014, Remark 6.3).

How many examples. The VC dimension also fixes the sample complexity up to constant factors.

Theorem 7 (the quantitative fundamental theorem; cited). Let $\mathrm{VCdim}(\mathcal{H}) = d < \infty$. There are absolute constants $C_1, C_2$ such that

  • uniform convergence holds with $C_1\dfrac{d + \ln(1/\delta)}{\varepsilon^2} \le m^{\mathrm{UC}}_{\mathcal{H}}(\varepsilon, \delta) \le C_2\dfrac{d + \ln(1/\delta)}{\varepsilon^2}$;
  • $\mathcal{H}$ is agnostic PAC learnable with $C_1\dfrac{d + \ln(1/\delta)}{\varepsilon^2} \le m_{\mathcal{H}}(\varepsilon, \delta) \le C_2\dfrac{d + \ln(1/\delta)}{\varepsilon^2}$;
  • $\mathcal{H}$ is PAC learnable with $C_1\dfrac{d + \ln(1/\delta)}{\varepsilon} \le m_{\mathcal{H}}(\varepsilon, \delta) \le C_2\dfrac{d\ln(1/\varepsilon) + \ln(1/\delta)}{\varepsilon}$.

This is Theorem 6.8 of Shalev-Shwartz and Ben-David (2014), proved in their Chapter 28. The rates repeat what PAC Learning and Finite Hypothesis Classes found for finite classes with $d$ in place of $\ln|\mathcal{H}|$: about $d/\varepsilon$ examples when a perfect rule exists and $d/\varepsilon^2$ otherwise.

Explicit constants are available in particular forms. Mohri, Rostamizadeh and Talwalkar (2018, Corollary 3.19, equation 3.29) give, for a class of VC dimension $d \ge 1$ and $m \ge d$, with probability at least $1 - \delta$,

$$L_{\mathcal{D}}(h) \;\le\; L_S(h) + \sqrt{\frac{2d\ln(em/d)}{m}} + \sqrt{\frac{\ln(1/\delta)}{2m}} \qquad\text{for every } h \in \mathcal{H}.$$

Their lower bounds show that no algorithm can do much better. In the realizable case (their Theorem 3.20), for $d > 1$ and every algorithm there are a distribution and a target in $\mathcal{H}$ for which the risk exceeds $(d - 1)/(32m)$ with probability at least 1/100. In the agnostic case (Theorem 3.23, also for $d > 1$), there is a distribution for which the excess risk over the best rule exceeds $\sqrt{d/(320m)}$ with probability at least 1/64. The constants in the lower bounds are small, which is why they say more about the rate than about any particular sample size.

The bound against the data

How far is the bound from what happens on the NHANES population? For each of seven sample sizes the script drew 30 samples (seeds 117,000,001 to 117,000,030; each seed's generator draws the sizes in increasing order). For each sample it computed the training error of every threshold and every interval on the 0.1 grid, and the largest one-sided deviation $\max_h\big(L_{\mathcal{D}}(h) - L_S(h)\big)$ over the class, the quantity Mohri et al.'s bound controls. The bound at $\delta = 0.05$ is compared with the finite-grid bound $\sqrt{\ln(|\mathcal{H}|/\delta)/(2m)}$, obtained as in the proof of Theorem 2 of PAC Learning and Finite Hypothesis Classes but with one tail of Hoeffding's inequality only (the lower tail of $L_S(h)$, $P(L_S(h) - L_{\mathcal{D}}(h) \le -\varepsilon) \le e^{-2m\varepsilon^2}$) (Theorem 2 of Concentration Inequalities: Hoeffding and Bernstein), so that the factor 2 disappears: $P(\max_h(L_{\mathcal{D}}(h) - L_S(h)) \ge \varepsilon) \le |\mathcal{H}|e^{-2m\varepsilon^2}$. It is computed for the 201 grid thresholds and the 20,302 grid intervals.

$m$ thresholds: VC bound grid bound observed median (IQR) intervals: VC bound grid bound observed median (IQR)
50 0.6163 0.2881 0.0579 (0.0457 to 0.0869) 0.7540 0.3594 0.1264 (0.1126 to 0.1615)
200 0.3375 0.1440 0.0373 (0.0291 to 0.0524) 0.4214 0.1797 0.0676 (0.0583 to 0.0767)
1,000 0.1645 0.0644 0.0175 (0.0131 to 0.0225) 0.2086 0.0804 0.0299 (0.0227 to 0.0360)
5,000 0.0790 0.0288 0.0072 (0.0049 to 0.0088) 0.1013 0.0359 0.0128 (0.0105 to 0.0143)

(The script also ran $m$ = 100, 500 and 2,000; the figure shows all seven.)

Thresholds (left) and intervals (right) on the diagnosed labels, log scales: the VC bound of Mohri et al. (blue), the finite-grid bound (dashed) and the largest one-sided deviation over the class in 30 samples (median and interquartile range). Notice that all three fall at about the same rate, that the VC bound sits several times above the observations, and that the interval class, which contains the thresholds, has the larger deviations.
Thresholds (left) and intervals (right) on the diagnosed labels, log scales: the VC bound of Mohri et al. (blue), the finite-grid bound (dashed) and the largest one-sided deviation over the class in 30 samples (median and interquartile range). Notice that all three fall at about the same rate, that the VC bound sits several times above the observations, and that the interval class, which contains the thresholds, has the larger deviations.

Four observations, each about this population and these 30 samples:

  • The rate is right. The least-squares slope of the log median deviation on $\log m$, over the five sizes from $m = 200$ to $m = 5{,}000$, is $-0.47$ for thresholds and $-0.50$ for intervals, close to the $-1/2$ of $1/\sqrt{m}$. The VC bound falls slightly more slowly, because of its $\ln m$ factor.
  • The constant is not. The VC bound is between 7.7 and 11.0 times the median deviation for thresholds and between 6.0 and 7.9 times for intervals. Part of the excess is the logarithm in $\sqrt{2d\ln(em/d)/m}$, which a finer argument removes (Theorem 7); part is the worst case over all distributions, of which this population is not one.
  • A finite grid can beat the VC dimension. For these data the grid bound is 2.1 to 2.7 times tighter than the VC bound for thresholds. It uses a fact the VC bound ignores, that HbA1c is reported in tenths, and it would fail for a measurement with finer resolution, while the VC bound would not change.
  • The extra parameter has a measurable cost. The interval class contains the thresholds (every grid threshold $t$ acts on these data as the grid interval $[t, 20.0]$), so its largest deviation can only be larger, whatever the VC dimensions. What the experiment adds is by how much: 1.5 to 2.2 times in the median. The best interval is no better than the best threshold here, so the extra capacity costs estimation error and buys no reduction in approximation error: the median excess risk of the ERM (ties broken toward the smallest threshold, and for intervals toward the smallest left end, then the smallest right end, with the empty rule chosen only when strictly better) was 0.0374 for intervals against 0.0046 for thresholds at $m = 50$, and 0.0019 against 0.0005 at $m = 1{,}000$.

Example (a loose bound is not a useless one). It is tempting to dismiss a bound that is ten times too large. But the experiment shows the bound doing the job it was designed for. It predicted the $1/\sqrt{m}$ decline, its ordering of the two classes matched the observed one (as the nesting of the classes guarantees), and it held in every one of the 210 samples, for both classes. What it does not do is give a usable sample size for this population; for that, a held-out test set, as in Training, Validation, and Test Sets, measures the risk of one chosen rule directly.

What is proved, what is cited, what the experiment shows

Proved here. That a class shattering $2m$ points defeats every learner on $m$ examples, and that infinite VC dimension rules out PAC learning (Theorem 1, from the no-free-lunch theorem of PAC Learning and Finite Hypothesis Classes); the VC dimensions of thresholds, intervals and axis-aligned rectangles (Propositions 1 to 3) and the bound $\log_2|\mathcal{H}|$ for finite classes; Radon's theorem (Theorem 2) and the VC dimension $d + 1$ of half-spaces (Theorem 3); the infinite VC dimension of the sine classifiers (Theorem 4); the Sauer–Shelah–Perles lemma in its strong form (Theorem 5) and the polynomial bound $(em/d)^d$ (Corollary 1); the implications 1 ⇒ 2 ⇒ 3 ⇒ 4, 2 ⇒ 5, 4 ⇒ 6 and 5 ⇒ 6 of the fundamental theorem, by links to the pages that prove their parts.

Proved on a linked page. The implication 6 ⇒ 1 and Mohri et al.'s explicit VC bound (their Corollary 3.19), proved from Theorem 5 and Corollary 1 by symmetrization, McDiarmid's inequality and Massart's lemma in Rademacher Complexity (Corollary 1 there).

Cited. Shalev-Shwartz and Ben-David's form of the uniform convergence bound (2014, Theorem 6.11) and their statement of the fundamental theorem (Theorem 6.7); the quantitative fundamental theorem (Shalev-Shwartz and Ben-David, 2014, Theorem 6.8); Mohri, Rostamizadeh and Talwalkar's (2018) lower bounds (Theorems 3.20 and 3.23). The history of the lemma is reported from Shalev-Shwartz and Ben-David's and Mohri et al.'s bibliographic notes and from Shelah's (1972) paper; Sauer (1972), Radon (1921) and Vapnik and Chervonenkis (1971) are cited for priority and were not opened; Blumer et al. (1989) are reported from their abstract.

Computed. The shattering checks and restriction counts on the HbA1c values are exact enumerations; the counts on samples and the deviations are 30 seeded samples at each size, reported as medians and interquartile ranges, and they describe this population, not the worst case the theorems address. The random-class, half-space and sine checks are exact or verified by linear programming, as stated.

Worked problems

These problems were written for this article; they use the HbA1c classes and small exact cases. The script tools/experiments/statistics/vc-dimension.py recomputes every number.

Problem 1 (signed intervals). A signed interval labels the points of $[a, b]$ with $s$ and the others with $1 - s$, for $s \in \{0, 1\}$: it predicts diabetes either inside a band or outside it. Find its VC dimension.

Solution. 3.

Three points $c_1 < c_2 < c_3$ are shattered. If the points labeled 1 form a contiguous run (including no points or all three), an interval with $s = 1$ around that run produces the labeling. The only labeling of three sorted points whose 1s are not contiguous is $(1, 0, 1)$, and the interval $[c_2, c_2]$ with $s = 0$ produces it. Four points $c_1 < c_2 < c_3 < c_4$ are not shattered: the labeling $(1, 0, 1, 0)$ has neither its 1s contiguous (so $s = 1$ fails) nor its 0s contiguous (so $s = 0$, which needs the 0s to fill an interval, fails). The script confirms both statements by brute force on HbA1c values. By Theorem 5 the class produces at most $1 + m + \binom{m}{2} + \binom{m}{3}$ labelings of $m$ points.

Problem 2 (Sauer's bound by hand). A class has VC dimension 3. At most how many labelings can it produce on 10 points? Compare with Corollary 1 and with $2^{10}$.

Solution. 176.

By Theorem 5, at most $\binom{10}{0} + \binom{10}{1} + \binom{10}{2} + \binom{10}{3} = 1 + 10 + 45 + 120 = 176$. Corollary 1 gives $(10e/3)^3 = 743.9$, a weaker bound, and all labelings number $2^{10} = 1{,}024$. Already at 10 points the class can produce at most 17% of the labelings.

Problem 3 (a Radon partition of a square). Find the Radon partition of the corners $(0, 0)$, $(1, 1)$, $(1, 0)$, $(0, 1)$ of the unit square, and the labelings no line can produce.

Solution. The diagonals: $\{(0, 0), (1, 1)\}$ and $\{(1, 0), (0, 1)\}$; no line labels one diagonal 1 and the other 0, either way round.

Solve $\sum\beta_i x_i = 0$, $\sum\beta_i = 0$ in that order of points: $\beta = (1, 1, -1, -1)$ works, since $(0, 0) + (1, 1) - (1, 0) - (0, 1) = (0, 0)$ and the weights sum to zero. Then $\lambda = 2$ and $p = \tfrac12(0, 0) + \tfrac12(1, 1) = \tfrac12(1, 0) + \tfrac12(0, 1) = (\tfrac12, \tfrac12)$, the center, where the diagonals cross. By the proof of Theorem 3, the labeling $(1, 1, 0, 0)$ is impossible for a line, and so is $(0, 0, 1, 1)$, by the same proof with the two groups exchanged; the script confirms by linear programming that both are infeasible, and that the labeling $(1, 0, 1, 0)$, bottom row against top row, is feasible (the line $x_2 = 1/2$).

Problem 4 (the VC bound for intervals). Evaluate Mohri et al.'s bound for intervals at $m = 1{,}000$ and $\delta = 0.05$, and compare it with the 30 samples.

Solution. 0.2086, about 7 times the observed median of 0.0299.

With $d = 2$: $\ln(e \cdot 1{,}000/2) = 1 + \ln 500 = 7.215$, so the first term is $\sqrt{2 \cdot 2 \cdot 7.215/1{,}000} = 0.1699$. The second is $\sqrt{\ln 20/2{,}000} = 0.0387$. Their sum is 0.2086. The median largest deviation over the 30 samples was 0.0299, and the largest of the 30 was 0.0424. For the risk of a single learned interval, a guarantee from the bound is $L_S(h_S) + 0.2086$, while the ERM's own gap $L_{\mathcal{D}}(h_S) - L_S(h_S)$ had median 0.0055.

Summary

Result Statement
Shattering $\mathcal{H}$ shatters $C$ if $\lvert\mathcal{H}_C\rvert = 2^{\lvert C\rvert}$; $\mathrm{VCdim}$ = largest shattered size
No learning without it infinite VC dimension ⇒ not PAC learnable
Examples thresholds 1, intervals 2, signed intervals 3, rectangles 4, half-spaces in $\mathbb{R}^d$: $d + 1$, sine classifiers $\infty$
Radon $d + 2$ points of $\mathbb{R}^d$ split into two groups with intersecting hulls
Sauer–Shelah–Perles $\lvert\mathcal{H}_C\rvert \le$ number of shattered subsets; $\tau(m) \le \sum_{i \le d}\binom{m}{i} \le (em/d)^d$
Fundamental theorem uniform convergence ⇔ ERM learns ⇔ (agnostic) PAC learnable ⇔ finite VC dimension
Rates agnostic $\Theta((d + \ln(1/\delta))/\varepsilon^2)$; realizable between $(d + \ln(1/\delta))/\varepsilon$ and $(d\ln(1/\varepsilon) + \ln(1/\delta))/\varepsilon$
NHANES VC bound 6 to 11 times the observed largest deviation; same $1/\sqrt{m}$ rate

What we have learned

The capacity of a class of classifiers is not the number of its rules or its parameters but the size of the largest set on which it can produce every labeling. Thresholds on HbA1c have infinitely many rules and VC dimension 1; sine waves with one frequency parameter have infinite VC dimension. A class that shatters arbitrarily large sets cannot be learned, by the no-free-lunch argument; a class of VC dimension $d$ produces at most $\sum_{i \le d}\binom{m}{i}$ labelings of $m$ points, by the Sauer–Shelah–Perles lemma, and that polynomial count is what makes uniform convergence, and with it learning by ERM, possible. On the NHANES thresholds and intervals the VC bound was several times too large, but it predicted the $1/\sqrt{m}$ decline and the cost of the extra parameter.

The step from polynomial growth to uniform convergence went through a symmetrization argument that this article took from the next one. Rademacher Complexity proves it, and replaces the count of labelings by an average correlation with random signs, which can be computed from the data and does not depend on the VC dimension at all.

Every number in this article is computed by tools/experiments/statistics/vc-dimension.py in the site's repository, which downloads the NHANES files from the CDC and checks their checksums (loader tools/experiments/statistics/sltdata.py). The figures are drawn by tools/figures/vc-dimension.py from the script's results.

References