VC DimensionOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

VC Dimension

How do you measure the capacity of a model — its raw ability to fit arbitrary data — independent of any particular dataset? Counting parameters fails: a single sine-wave classifier sign(sin⁡(ωx))\text{sign}(\sin(\omega x)) has one parameter yet can fit any binary labelling of points on a line. The Vapnik–Chervonenkis (VC) dimension answers the question properly, and it is the quantity that turns "complex models overfit" into a provable bound.

Shattering

Fix a hypothesis class H\mathcal{H} — the set of all classifiers a model can express (e.g. all straight-line decision boundaries in the plane). A set of points is shattered by H\mathcal{H} if, for every way of labelling those points +/−+/-, some hypothesis in H\mathcal{H} realises that labelling exactly.

With mm points there are 2m2^m possible labellings. Shattering means all 2m2^m are achievable.

Can a straight line shatter these points?

−−−
Points:Labelling:1 / 8

Tip: click any point to flip its label.

separable labellings8 / 8
this labellingseparable
shattered?yes — VC ≥ 3

A linear classifier shatters a point set if it can realise every +/− labelling. Three points in general position give 8 labellings — all separable. Four points in convex position fail on the diagonal (XOR) labelling, so no line works. The largest set that can always be shattered is the VC dimension: 3 for a 2D linear classifier.

Definition

The VC dimension dVC(H)d_{\text{VC}}(\mathcal{H}) is the size of the largest point set that H\mathcal{H} can shatter.

Two things must be checked to prove dVC=dd_{\text{VC}} = d:

  1. Lower bound (dVC≥dd_{\text{VC}} \ge d): exhibit one set of dd points that H\mathcal{H} shatters. You only need a single good configuration — points in "general position."
  2. Upper bound (dVC<d+1d_{\text{VC}} < d+1): show that no set of d+1d+1 points can be shattered. You must rule out every configuration.

The asymmetry matters: shattering is "there exists a set," failing to shatter is "for all sets."

Worked example: 2D linear classifier

The class H={ sign(w⊤x+b) }\mathcal{H} = \{\,\text{sign}(\mathbf{w}^\top\mathbf{x} + b)\,\} of linear separators in R2\mathbb{R}^2 has dVC=3d_{\text{VC}} = 3.

Three points can be shattered. Place three points in a triangle (not collinear). All 23=82^3 = 8 labellings are linearly separable — for any split into ++ and −-, a straight line cleaves them. (Try every labelling in the visualization above with "3 points" selected: 8 / 8.)

Four points cannot. Take any four points. Either three are collinear / one lies inside the triangle of the others, or they sit in convex position. In the convex case, label the two diagonal points ++ and the other two −- — the XOR labelling. The two ++ points and the two −- points interleave around the hull, so no single line can separate them. Since some labelling always fails, no 4-point set is shattered. Hence dVC=3d_{\text{VC}} = 3.

The general pattern

A linear classifier in Rd\mathbb{R}^d (with bias) has dVC=d+1d_{\text{VC}} = d + 1. In 1D that's 2; in 2D, 3; in 3D, 4. The "+1" is the bias term — it adds one degree of freedom, equivalent to lifting the points into one higher dimension.

Capacity is not parameter count

VC dimension and parameter count often agree but need not:

  • Linear models: dVC=d+1d_{\text{VC}} = d+1 matches the parameter count — the tidy case.
  • 1-nearest-neighbor: dVC=∞d_{\text{VC}} = \infty. It can shatter any finite set (each point is its own nearest neighbor), yet generalizes fine in practice — a hint that VC bounds are worst-case and loose.
  • sign(sin⁡(ωx))\text{sign}(\sin(\omega x)): one real parameter ω\omega, yet dVC=∞d_{\text{VC}} = \infty. A single well-chosen frequency realises any labelling of points on the line.

So capacity is about the richness of achievable behaviours, not the number of knobs.

The growth function and Sauer's lemma

Define the growth function ΠH(m)\Pi_{\mathcal{H}}(m) as the maximum number of distinct labellings H\mathcal{H} can produce on any mm points:

ΠH(m)=max⁡x1,…,xm∣{(h(x1),…,h(xm)):h∈H}∣\Pi_{\mathcal{H}}(m) = \max_{x_1,\dots,x_m} \big|\{(h(x_1),\dots,h(x_m)) : h \in \mathcal{H}\}\big|

It starts at the ceiling 2m2^m (full shattering) but must drop below it once m>dVCm > d_{\text{VC}}. Sauer's lemma makes the drop precise: for m≥d=dVCm \ge d = d_{\text{VC}},

ΠH(m)≤∑i=0d(mi)≤(e md)d\Pi_{\mathcal{H}}(m) \le \sum_{i=0}^{d} \binom{m}{i} \le \left(\frac{e\,m}{d}\right)^{d}

The growth function switches from exponential (2m2^m) to merely polynomial (O(md)O(m^d)) at the VC dimension. That phase change is exactly what makes generalization possible — there are far fewer "effectively different" hypotheses than the infinite class suggests.

The generalization bound

Bounding the gap between true risk R(h)R(h) and empirical risk R^(h)\hat{R}(h) with the polynomial growth function yields the classic VC bound. With probability at least 1−δ1 - \delta over a sample of size nn, simultaneously for all h∈Hh \in \mathcal{H}:

R(h)≤R^(h)+dVC(ln⁡2ndVC+1)+ln⁡4δnR(h) \le \hat{R}(h) + \sqrt{\frac{d_{\text{VC}}\big(\ln\frac{2n}{d_{\text{VC}}} + 1\big) + \ln\frac{4}{\delta}}{n}}

Read it as the slogan gap ∼dVC/n\sim \sqrt{d_{\text{VC}}/n}:

  • More capacity (dVC↑d_{\text{VC}}\uparrow) loosens the bound — complex models need more data.
  • More data (n↑n\uparrow) tightens it — the gap shrinks like 1/n1/\sqrt{n}.
  • A sample roughly n≳dVCn \gtrsim d_{\text{VC}} is the order-of-magnitude needed to learn at all.

The bound is loose

VC bounds are distribution-free and worst-case, so they are usually far too pessimistic to use for actual sample-size planning. Deep networks have enormous (often effectively infinite) VC dimension yet generalize — see double descent. The value of VC theory is the qualitative law it proves, not a tight numeric guarantee.

Common mistakes

  1. "Shattered = can fit this dataset." Shattering requires fitting all 2m2^m labellings of the points, not just the one you happen to have.
  2. Confusing the quantifiers. dVC≥dd_{\text{VC}} \ge d needs one shatterable set; dVC<d+1d_{\text{VC}} < d+1 needs every (d+1)(d+1)-set to fail. People prove the wrong direction by checking a single 4-point set and concluding too much.
  3. Equating VC dimension with parameter count. 1-NN and the sine classifier break this; capacity is about expressible behaviours.
  4. Trusting the bound numerically. It is an existence-style worst-case bound; treat it as a scaling law, not a calculator.

Key takeaways

  • VC dimension = size of the largest point set a hypothesis class can shatter (realise all 2m2^m labellings).
  • A 2D linear classifier has dVC=3d_{\text{VC}} = 3: a triangle is shatterable, but the XOR labelling of any 4 points is not. In general a linear classifier in Rd\mathbb{R}^d has dVC=d+1d_{\text{VC}} = d+1.
  • Sauer's lemma turns the growth function from exponential to polynomial O(mdVC)O(m^{d_{\text{VC}}}) past the VC dimension — the reason learning is possible.
  • The VC bound gives gap ∼dVC/n\sim \sqrt{d_{\text{VC}}/n}: complex models need more data. It is qualitatively right but numerically loose.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
VC DimensionInductive Bias & Equivari…Bias-Variance Decompositi…The Bias–Variance TradeoffLearning Theory & General…Regularization: Ridge & L…