Core ML1971advanced9 min read

On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

حول التقارب المنتظم للتكرارات النسبية للأحداث نحو احتمالاتها

Vapnik, V. N. · Chervonenkis, A. Ya. — Theory of Probability and Its Applications

The problem

The law of large numbers says a single event's observed frequency converges to its true probability as the sample grows. But learning algorithms don't test a single hypothesis — they search a whole class to find the one with the lowest error. When does that search preserve the guarantee? Without an answer, no learning has a mathematical right to generalize.

The contribution

Vapnik and Chervonenkis proved that uniform convergence — the simultaneous convergence of empirical frequencies to true probabilities across every event in a class — happens if and only if the class has a finite combinatorial measure of complexity they called the . They also proved the Sauer–Shelah lemma showing that a class with finite VC dimension d can produce at most O(n^d) distinct labelings on n points, far fewer than the 2^n possible. This polynomial growth is what makes possible.

The impact

This paper created statistical learning theory. The VC dimension became the central tool for analyzing whether a learning algorithm can generalize. It directly enabled PAC learning theory, , and the invention of support vector machines. Every modern generalization bound — from Rademacher complexity to PAC-Bayes — traces its intellectual ancestry to this result.

Imagine a fishing tournament on a lake. One angler casts a single line and catches 6 fish in 10 casts — a 60% catch rate that probably reflects the lake. Now imagine 10,000 anglers each trying a different spot. The best angler might report 90%, but that tells you more about how many anglers tried than about the fish.

VC theory asks: how many fishing spots can you try before the best catch rate becomes meaningless? The answer depends on the "richness" of the spots — how many fundamentally different patterns of fish they can produce. If the spots are few and simple, the winner's rate is trustworthy. If they can produce every conceivable pattern, nothing can be trusted.

The gap: one hypothesis converges, but searching many may not

The law of large numbers gives a simple promise: for one event $A$ , the fraction of times it occurs in $n$ trials converges to its probability $P(A)$ as $n \to \infty$ .

But a learning algorithm doesn't evaluate one hypothesis — it searches a class $\mathcal{H}$ of hypotheses and picks the one with the lowest empirical error. This is like checking many events simultaneously. The question becomes: does the worst-case gap between observed frequency and true probability, across all hypotheses in $\mathcal{H}$ , also shrink to zero?

$\sup_{h \in \mathcal{H}} |\hat{R}(h) - R(h)| \xrightarrow{P} 0$

This is uniform convergence — and it is strictly harder to achieve than pointwise convergence for any single $h$ .

Open in Lab

Left: one hypothesis — empirical error converges to true error. Right: searching many hypotheses — the best training error may underestimate the true error. Increase sample size to see uniform convergence close the gap.

The demo wakes as you arrive…

Shattering: can your model produce every possible labeling?

The crucial insight is geometric. Given $n$ data points, a hypothesis class $\mathcal{H}$ of binary classifiers assigns each point a label — $+$ or $-$ . There are $2^n$ possible labelings. If $\mathcal{H}$ can produce all $2^n$ labelings on some set of $n$ points, we say $\mathcal{H}$ shatters that set.

means the class is too flexible for those points — it can memorize any pattern, including noise. Think of it this way: if your can paint any picture on $n$ data points, it has no . It cannot distinguish signal from noise.

Open in Lab

Try all 2ⁿ labelings. A line in 2D can shatter 3 points but not 4 — there's always one labeling it cannot achieve.

The demo wakes as you arrive…

VC dimension: the shattering limit

The VC dimension of a hypothesis class $\mathcal{H}$ is the size of the largest set of points it can shatter. Formally:

$\text{VCdim}(\mathcal{H}) = \max\{n : \exists\, x_1,\ldots,x_n \text{ that } \mathcal{H} \text{ shatters}\}$

To establish VCdim $= d$ , you must show two things: (1) some set of $d$ points can be shattered, and (2) no set of $d+1$ points can be shattered.

The VC dimension measures the effective complexity of a hypothesis class. It does not count parameters — it measures how many data patterns the class can memorize. A class with infinitely many hypotheses can still have a small VC dimension if those hypotheses are structurally constrained.

Open in Lab

Explore VC dimension for different hypothesis classes. Switch between lines, circles, and higher-dimensional separators to see how complexity grows.

The demo wakes as you arrive…

The growth function: from exponential to polynomial

The $\Pi_{\mathcal{H}}(n)$ counts the maximum number of distinct labelings that $\mathcal{H}$ can produce on any set of $n$ points:

$\Pi_{\mathcal{H}}(n) = \max_{x_1,\ldots,x_n} |\{(h(x_1),\ldots,h(x_n)) : h \in \mathcal{H}\}|$

Before Vapnik and Chervonenkis, the natural bound was $\Pi_{\mathcal{H}}(n) \leq 2^n$ — exponential in $n$ . Their breakthrough was showing that once $n$ exceeds the VC dimension $d$ , the growth function drops from exponential to polynomial. This is the Sauer–Shelah lemma:

\Pi_{\mathcal{H}}(n) \leq \sum_{i=0}^{d}\binom{n}{i} \leq \left(\frac{en}{d}\right)^d

Sauer–Shelah lemma — the polynomial ceiling — The VC dimension marks a critical threshold in a model class's ability to fit arbitrary label patterns. Below this threshold, the number of different labelings that can be realized grows extremely rapidly. Beyond it, growth becomes much more restricted and follows a polynomial pattern rather than an exponential one. This limitation is fundamental to statistical learning theory because it prevents model complexity from growing without bound and makes meaningful generalization guarantees possible.

Think of it as a highway with an exit ramp. Up to $n = d$ , the growth function races along the exponential highway: $\Pi_{\mathcal{H}}(n) = 2^n$ , the class can produce every possible labeling. At $n = d+1$ , it hits the Sauer–Shelah exit ramp and transitions onto the polynomial road $O(n^d)$ , never returning to the exponential.

This is not a loose bound — it is tight. The transition happens exactly at $n = d$ , and the polynomial degree is exactly the VC dimension.

Open in Lab

The growth function equals 2ⁿ up to n = d, then bends to follow a polynomial curve. Drag the VC dimension slider to see how the bend point shifts.

The demo wakes as you arrive…

The main theorem: finite VC dimension ⟺ uniform convergence

With the growth function bounded, Vapnik and Chervonenkis could now state their central result — the fundamental theorem of statistical learning theory. It gives both a necessary and sufficient condition for learnability:

A hypothesis class $\mathcal{H}$ has the uniform convergence property if and only if its VC dimension is finite.

In more concrete terms, if $\text{VCdim}(\mathcal{H}) = d < \infty$ , then for any $\epsilon > 0$ and $\delta > 0$ , with probability at least $1 - \delta$ :

\sup_{h \in \mathcal{H}} |\hat{R}(h) - R(h)| \leq \sqrt{\frac{d \ln(n/d) + \ln(1/\delta)}{n}}

VC generalization bound — This bound quantifies how closely a model's performance on training data is expected to match its performance on unseen data. The gap becomes smaller when more training examples are available and larger when the hypothesis class is more expressive or complex. In other words, better generalization can be achieved either by collecting more data or by using simpler models with lower capacity.

Read the bound as a tug-of-war. The VC dimension $d$ pulls the bound up — richer models can diverge more. The sample size $n$ pulls it down — more data tames the complexity. The $\sqrt{d/n}$ tells you the "exchange rate": to halve the bound, either quarter the model complexity or quadruple the data.

Open in Lab

Adjust VC dimension and sample size to see how the generalization bound changes. Notice the √(d/n) tradeoff.

The demo wakes as you arrive…

From theory to practice: ERM and structural risk minimization

The VC bound decomposes a model's true error into two terms:

$R(h) \leq \hat{R}(h) + \Omega(d, n, \delta)$

The first term $\hat{R}(h)$ is the training error — it decreases as the model gets more complex (more to fit the data). The second term $\Omega$ is the complexity penalty — it increases with the VC dimension $d$ . This creates a U-shaped curve: too simple models underfit (high training error), too complex models overfit (high complexity penalty).

Empirical Risk Minimization (ERM) minimizes the first term alone — pick the hypothesis with the lowest training error. VC theory proves ERM is valid when the VC dimension is finite.

Structural Risk Minimization (SRM) — introduced by Vapnik — minimizes the sum. It nests hypothesis classes $\mathcal{H}_1 \subset \mathcal{H}_2 \subset \cdots$ with increasing VC dimension and picks the class that best balances fit and complexity. This idea directly inspired support vector machines.

Open in Lab

The U-curve in action. Drag the complexity slider to see training error decrease while the VC penalty increases. The sweet spot minimizes total risk.

The demo wakes as you arrive…

The same idea in code

Computing VC dimension and the generalization boundpython

Simplified to show the idea — not the real implementation.

import numpy as np
from itertools import product

def is_shattered(points, classifier_factory):
    """Check if a set of points is shattered by a classifier class."""
    n = len(points)
    for labeling in product([0, 1], repeat=n):  # all 2^n labelings
        found = False
        for clf in classifier_factory():         # search for a matching classifier
            preds = [clf(p) for p in points]
            if tuple(preds) == labeling:
                found = True
                break
        if not found:
            return False                         # one labeling unrealizable = not shattered
    return True

def sauer_bound(n, d):
    """Sauer-Shelah: max distinct labelings for VC dimension d on n points."""
    if n <= d:
        return 2 ** n                            # exponential regime
    return sum(
        np.math.comb(n, i) for i in range(d + 1) # polynomial regime
    )

def vc_bound(n, d, delta=0.05):
    """VC generalization bound: worst-case gap between train and true error."""
    return np.sqrt((d * np.log(n / d) + np.log(1 / delta)) / n)

# Example: lines in 2D have VC dimension 3
d = 3
for n in [10, 100, 1000, 10_000]:
    print(f"n={n:>6}  Sauer bound={sauer_bound(n,d):>12}  "
          f"out of 2^n={2**n:.1e}  "
          f"VC gap≤{vc_bound(n, d):.4f}")

Why it changed everything

1971
VC Theory
Vapnik and Chervonenkis prove the fundamental theorem — finite VC dimension characterizes uniform convergence. Published in Theory of Probability and Its Applications.
1974
Theory of Pattern Recognition
Vapnik and Chervonenkis publish their book expanding the theory to include structural risk minimization and the foundations of statistical learning.
1984
PAC Learning
Valiant introduces Probably Approximately Correct learning. VC dimension becomes the key quantity in PAC sample complexity bounds.
1992
Blumer–Ehrenfeucht–Haussler–Warmuth
The Fundamental Theorem of Computational Learning Theory is formalized: VC dimension characterizes PAC learnability for binary classification.
1995
Support Vector Machines
Vapnik and Cortes introduce SVMs — a direct application of structural risk minimization. The maximum-margin principle optimizes the VC bound by construction.
2000
Beyond VC — Rademacher, PAC-Bayes
Rademacher complexity and PAC-Bayes bounds refine generalization theory with data-dependent and algorithm-dependent measures, extending the intellectual framework that VC theory established.

VC theory didn't just add a theorem — it created the language in which machine learning reasons about generalization. The concepts of capacity, shattering, and complexity penalties are now so embedded in the field that every discussion of , model selection, or traces back to this 1971 paper.

CitationVapnik, V. N. and Chervonenkis, A. Ya.. On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities. Theory of Probability and Its Applications, 1971.

Terms in this paper

VC Dimensionبُعد VC
Generalizationالتعميم
Overfittingفرط التخصيص
Shatteringالتهشيم
Growth Functionدالة النمو
Structural Risk Minimizationتقليل المخاطر البنيوي
Empirical Risk Minimizationتقليل المخاطر التجريبية
Convergenceالتقارب الحسابي
Capacityسعة
Bias-Variance Tradeoffالموازنة بين الانحياز والتباعد