A theorem for one event can fail for a whole class

Take independent observations x₁,…,xₗ from a probability space X. For one measurable event A, its relative frequency ν_A^(l): the fraction of sampled points that lie in A: converges in probability to its probability P_A. This is the familiar Bernoulli law. It answers a fixed question: if A is chosen in advance, enough data make its empirical frequency reliable.

Many statistical tasks do not choose one event in advance. They inspect a class S of events using the same data. A threshold may be chosen after seeing the sample; a separating half-space may be selected to fit labels; a report may search thousands of segments and publish the most surprising. The relevant error is then not |ν_A−P_A| for one A but the largest error over all A in S.

Uniform convergence in probability means that, for every positive ε, the probability that π^(l)>ε tends to zero as l grows. The order of operations is decisive. The supremum is taken after the sample is observed. The worst event can therefore adapt to the realised data even though the class itself is fixed beforehand.

The paper begins by warning that uniform convergence can fail in simple examples. On [0,1], let S contain every open set. After seeing any finite sample, one can place tiny open neighbourhoods around every sampled point. Their empirical frequency is one while their true probability can be made arbitrarily small. Every fixed open set obeys the ordinary law, yet the sample-dependent supremum stays near one.

The core achievement is a criterion that depends on the class rather than on the unknown distribution. Vapnik and Chervonenkis measure how flexibly S can distinguish finite samples. Once that combinatorial freedom is controlled, probability theory can convert it into a uniform error guarantee.

Ask what the class can carve from r points

Fix a finite sample x₁,…,xᵣ, without yet assigning probabilities. Every event A in S selects the subsample consisting of the points that lie in A. Different events may select the same subsample. The index Δ^S(x₁,…,xᵣ) counts the number of distinct induced subsamples. It is at most 2ʳ because an r-point sample has only that many subsets.

The growth function m^S(r) takes the maximum index over every possible sample of r points. It asks for the class’s most expressive configuration: on the hardest r points, how many different inclusion patterns can S realise? This definition turns an infinite collection of measurable sets into a finite counting problem.

For rays on the real line of the form x≤a, sorting r distinct points reveals r+1 patterns: include none, the first point, the first two, and so on through all r. The class is infinite because a ranges continuously, but its behaviour on finite data is tightly constrained. Infinite cardinality is therefore not the relevant measure of capacity.

At the other extreme, all open subsets of [0,1] can isolate any chosen subset of finitely many distinct points with small disjoint neighbourhoods. The growth function is 2ʳ. On every sample the class can realise every binary pattern. The paper’s dichotomy says that this complete freedom either persists at all sizes or, once it first fails, the growth function is bounded by a polynomial expression.

The proof introduces Φ(n,r), the maximum number of regions formed by r hyperplanes in n-dimensional space, with a Pascal-like recurrence. A combinatorial lemma shows that if the index is sufficiently large on r points, some n-point subsample is completely realised. Consequently, if complete realisation first fails at size n, then m^S(r) is bounded through Φ(n,r), and hence by rⁿ+1.

Modern accounts call the largest completely realisable sample size the VC dimension and state the counting result through the Sauer–Shelah lemma. The 1971 article uses its own index and first-failure convention. Translating into modern vocabulary is helpful, but silently replacing the historical convention risks an off-by-one mistake and obscures the actual route of the proof.

A second sample makes the unknown probability disappear

The event probabilities P_A are unknown, so π^(l) cannot be computed from the observed sample alone. The main lemma introduces an independent sample of the same size. For every A, compare its frequency in the first half with its frequency in the second. Let ρ^(l) be the largest absolute disagreement over S.

If the first empirical frequency is far from P_A, the second empirical frequency has a substantial chance of remaining near P_A. On that event the two empirical frequencies must disagree. For l≥2/ε², the paper derives a comparison in which the probability of large ρ is at least one half the probability of large π. Controlling empirical-versus-empirical disagreement therefore controls empirical-versus-truth deviation.

The doubled sample also makes capacity finite. On fixed 2l points, infinitely many events in S collapse into at most Δ^S distinct induced subsets. Events that induce the same subset produce the same pair of empirical frequencies under every permutation of those points. The proof can therefore sum over distinct patterns rather than over an uncountable class.

Permutation symmetry supplies concentration. The paper averages over all (2l)! reorderings of a fixed doubled sample. For each induced subset, the number falling into the first half behaves like sampling without replacement. A combinatorial estimate gives an exponential penalty in ε²l. Multiplying that penalty by the number of distinct induced subsets produces the class-level bound.

Exponential concentration must outrun combinatorial growth

Theorem 2 states, for l≥2/ε², that the probability of a uniform deviation exceeding ε is bounded by four times the growth function at 2l times an exponential concentration term.

The inequality exposes the entire bargain. The exponential term improves with sample size. The growth function charges for the number of distinct ways the class can fit the doubled sample. If m(2l) grows polynomially, the exponential eventually dominates for every fixed ε. If it grows like 2^(2l), the multiplicity can overwhelm this argument and uniform convergence may fail.

Combining Theorem 1’s polynomial growth with Theorem 2 gives a distribution-free sufficient condition. No special density, margin or geometric distribution assumption is needed. The class must have a finite first failure of complete realisation, and the sample must be i.i.d. under the product probability measure introduced at the start.

Theorem 3 upgrades the conclusion to convergence with probability one. Polynomial growth makes the tail-probability series summable. A standard probability lemma then implies that deviations above ε occur only finitely often, and a countable sequence of ε values yields almost-sure uniform convergence. This stronger mode is genuinely in the 1971 paper and should not be omitted when describing its scope.

The paper also translates the tail inequality into an explicit sample-size condition for tolerance ε and failure probability η. The expression is conservative, with a leading 16/ε² and logarithmic dependence on the polynomial exponent and confidence. It is a sufficient worst-case design inequality, not an exact description of realised error.

Measurability is explicit in the source. The supremum π^(l), the doubled-sample supremum and the index viewed as a random quantity are assumed measurable where needed. Modern summaries sometimes suppress this qualification. The familiar equivalence between finite VC dimension, uniform laws and learnability requires regularity conditions; pathological classes can exploit measurability gaps.

For a fixed distribution, expected trace entropy must be sublinear

The second half of the paper asks for necessary and sufficient conditions that may depend on the distribution. It studies the random index Δ^S(x₁,…,xₗ) generated by an actual sample, rather than the worst-case growth function over all possible samples. The system entropy is defined as the expected binary logarithm of that random index.

The logarithm turns multiplicative trace growth across concatenated samples into subadditive behaviour. The paper proves that H^S(l)/l has a limit c between zero and one. This normalised entropy describes the asymptotic number of bits of binary pattern freedom per observation under the fixed distribution.

Theorem 4 states that H^S(l)/l→0 is necessary and sufficient for uniform convergence in probability over S. Sufficiency follows by restricting the doubled-sample integral to samples whose realised index is not exponentially large, then applying the earlier permutation bound. Necessity reverses the argument: a positive entropy rate implies sufficiently frequent samples with exponentially many traces, which force a non-vanishing probability of large empirical disagreement and therefore large deviation from truth.

This theorem is subtler than the slogan “finite VC dimension if and only if uniform convergence”. The primary’s distribution-free sufficient condition uses worst-case polynomial growth. Its necessary-and-sufficient statement is for a fixed distribution and uses sublinear expected log-index. A class may be very rich in impossible or negligible regions yet behave simply under one distribution. Worst-case and distribution-dependent capacity answer different questions.

The distinction anticipates a continuing tension in learning theory. Distribution-free capacity gives portable guarantees but can be pessimistic. Distribution-dependent analysis can exploit margins, noise, geometry or localisation, but its conclusions travel only with their assumptions. The 1971 article already separates these ambitions cleanly.

Generalisation appears before PAC language

The article does not speak of training error, test error, hypotheses or PAC learning. It studies event probabilities. Yet binary classification fits the framework: each classifier corresponds to the event on which it predicts one. Its empirical error and true error can be written as frequencies of related events. Uniform convergence then allows a data-selected classifier to inherit a guarantee because every eligible classifier is controlled simultaneously.

Valiant introduced the PAC framework in 1984. Blumer, Ehrenfeucht, Haussler and Warmuth later connected finite VC dimension, uniform convergence and distribution-free learnability under appropriate measurability conditions. Those are major later syntheses. They should be placed in the lineage rather than quoted as sentences from 1971.

Support-vector networks, the next canon paper, add optimisation, margins and kernel representations. Capacity control is one ingredient in that architecture, but the 1971 result does not prove that every small-VC classifier performs well on a particular dataset. Approximation error, optimisation, label noise, distribution shift and model selection all remain.

The conceptual inheritance is nevertheless direct. A learner sees one sample and chooses from many possible rules. The danger is selection: some rule may fit empirical accidents. Capacity measures how many distinct accidents the class can encode on finite data. Concentration defeats selection only when trace growth is sufficiently restrained.

Uniform convergence is a control on the eligible search space

In a production system, the class is larger than the final model family name. It includes hyperparameter grids, feature screens, thresholds, prompt templates, subgroup definitions and stopping decisions that used the same validation evidence. If an analyst tries twenty pipelines and reports one, the statistical search includes all twenty even when only one artefact is deployed.

Capacity need not be computed exactly to improve governance. Enumerate which decisions were data-dependent. Separate fixed transformations from searched alternatives. Preserve the candidate set and the selection rule. Use nested or genuinely independent evaluation when the reported metric guided further changes. Uniform theory explains why these operational controls matter: repeated reuse enlarges the effective class whose worst deviation can be selected.

A small empirical gap is still evidence, not identity. Uniform bounds need assumptions about sampling and measurability, and they are typically conservative. Live performance can differ because the distribution changes, observations depend on earlier actions or outcomes interfere. A generalisation claim should therefore name the population, sampling process, eligible class, confidence target and post-selection steps.

The deepest practical lesson is that reuse is measurable structure. “We only used one dataset” is not reassurance when the same dataset answered a large adaptive family of questions. One sample can answer every event in a restrained class; it cannot grant unlimited reliable discoveries merely because each query looks simple in isolation.

Capacity hides in workflows, not only in model definitions

A formal hypothesis class is only the beginning of the eligible search. Suppose a fixed classifier family is trained after trying five data-cleaning rules, twelve feature groups, four sampling schemes and six stopping epochs. If the same validation set guides every branch, the workflow can induce more outcome patterns than the classifier family considered in isolation. A faithful capacity inventory follows every data-dependent fork from raw evidence to the published choice.

Human judgement can enlarge the class as effectively as code. An analyst who redraws subgroup boundaries after viewing outcomes is selecting from the set of boundaries they might have drawn. A reviewer who requests a new exclusion until a chart “looks stable” adds exclusion rules to the search. Neither action is automatically illegitimate, but the final uncertainty statement must account for exploration or move confirmation to fresh evidence.

The event-class formulation makes this visible. Each potential report corresponds to an event: cases selected by a threshold, region, rule or conjunction. Uniform convergence asks whether all eligible reports have empirical frequencies close to their population probabilities at once. The theorem does not care whether the event was generated by a neural network, a spreadsheet filter or a committee meeting. It cares about the distinct traces the selection process can realise.

Data-dependent preprocessing creates a second subtlety. If missing-value rules, embeddings or labels are estimated from the same sample, the resulting event class may itself be random. One can sometimes condition on the preprocessing, enlarge the class to include every possible output, or use sample splitting. The 1971 theorem begins with a fixed measurable class S. Applying it to a random pipeline therefore requires an explicit bridge rather than a verbal appeal to VC dimension.

Dependence is another boundary. The primary defines a product measure over independent observations. Repeated observations from the same person, time-series windows and networked outcomes do not satisfy that construction merely because their rows are stored separately. Effective sample size heuristics may help engineering, but a theorem for dependent processes must supply the guarantee. The later ergodic literature is evidence that extending uniform laws beyond i.i.d. sampling is a substantive result.

Distribution shift sits outside the uniform supremum. The bound controls differences between empirical frequencies and probabilities under the same P that generated the i.i.d. sample. It does not compare training P with deployment Q. A class can have tiny capacity and perfect uniform convergence under P while failing after the population changes. Capacity control and shift detection solve orthogonal problems.

Linear separators are counted through arrangements, not margins

The paper’s half-space example studies events of the form (x,φ)≥1 in Euclidean space. For a fixed collection of sample vectors, each point determines a hyperplane in the parameter space of φ. Moving φ within one cell of that hyperplane arrangement does not change which sample points satisfy the inequality. Counting cells therefore counts possible induced subsets.

This dual view is important because it avoids enumerating an uncountable parameter space. What matters is where prediction patterns change. The recurrence Φ(n,r)=Φ(n,r−1)+Φ(n−1,r−1) records what happens when one more hyperplane is added: existing cells remain, while cells crossed by the new hyperplane split. The same combinatorial logic later appears across computational geometry and learning theory.

No margin appears in this example. A margin asks how far points lie from a separating boundary and enables finer, data-dependent capacity arguments. The 1971 calculation concerns binary traces of half-spaces. Reading support-vector intuition backwards into it would blur the distinction between counting separations and measuring geometric robustness.

Likewise, the threshold example is not merely a toy. It isolates the reason empirical distribution functions converge uniformly: every threshold produces a prefix of the ordered sample, so only l+1 traces exist. The Glivenko theorem appears in the paper as an application of Theorem 3. A classical result about distribution functions is thereby located inside a general theory of event classes.

The open-set counterexample supplies the opposite lesson. Topological simplicity of each individual event does not guarantee class simplicity. “Open” sounds regular, but the class of all open subsets can fit every binary pattern on distinct finite points. Capacity belongs to the collection’s combined expressive power, not to the descriptive elegance of one member.

Place in the canon: the birth of statistical capacity

Papers 0031 and 0032 studied adaptation through noisy experiments: how an agent moves towards a root or maximum. Paper 0033 changes the axis. The data are now fixed, but the question can vary over an entire class. The central risk is not noisy motion; it is the freedom to choose the most flattering explanation after seeing the sample.

This paper introduces the capacity language needed for statistical learning. The growth function turns a class of rules into finite combinatorics. Symmetrisation turns unknown truth into comparison. Concentration turns trace counts into a probability guarantee. Entropy distinguishes distribution-free control from distribution-specific behaviour.

Paper 0034 will make the next move through support-vector networks. Margins and kernels provide an algorithmic learning system whose generalisation story is inseparable from capacity. Reading the 1971 source first prevents “VC dimension” from becoming a magic noun: it is the finite-sample freedom that a uniform law must pay for.

Executable uniform-frequency laboratory

The laboratory draws seeded samples from the uniform distribution on [0,1] and evaluates the worst empirical-probability gap for four event classes. Thresholds and intervals search structured classes; eight fixed bins form a small predeclared family; the finite-subset memoriser contains the realised sample itself and therefore has empirical frequency one but true probability zero. The audit checks deterministic replay, valid deviation ranges and the class-specific invariant. This finite simulation illustrates mechanisms; it does not prove the paper’s asymptotic bounds.

Memory studio