How Big Is Your Hypothesis Class? Capacity Measures

Why counting hypotheses fails

The finite-class bound charges you log|H|. But the class of all linear separators in the plane is infinite, so log|H| is infinite and the bound is vacuous — yet linear separators clearly learn. The resolution is that on any finite sample of m points, an infinite class can only produce finitely many distinct labelings. Two hypotheses that agree on all m points are indistinguishable from the data's point of view, so the quantity that should matter is not how many hypotheses exist but how many behaviors they exhibit on m points.

This is the right notion of effective size, and it underlies every capacity measure in this guide. We are replacing a crude count of functions with a measure of how expressively the class can carve up data — its capacity in the operational sense. Three measures formalize this, from the most combinatorial to the most data-adaptive.

VC dimension: the combinatorial answer

The VC (Vapnik–Chervonenkis) dimension measures capacity by shattering. A set of points is shattered by H if, for every one of the 2^k ways to label those k points + or −, some hypothesis in H realizes exactly that labeling. The VC dimension is the size of the largest set H can shatter. Linear separators in d dimensions have VC dimension d + 1; thresholds on a line have VC dimension 1; the sine family sin(θx) has infinite VC dimension despite a single parameter, a vivid warning that parameter count is not capacity.

The magic is the Sauer–Shelah lemma: once the sample size exceeds the VC dimension d, the number of distinct labelings a class can produce grows only polynomially, like m^d, not like 2^m. Plug that polynomial growth function in where log|H| used to sit, and the uniform convergence machine runs again — now with a generalization gap of order sqrt(d·log(m) / m). The class is infinite, but its effective log-size is d·log(m), and learnability is governed by whether the VC dimension is finite.

\Pi_{\mathcal{H}}(m)\;\le\;\sum_{i=0}^{d}\binom{m}{i}\;\le\;\left(\frac{e\,m}{d}\right)^{d}

The Sauer–Shelah lemma: once the sample exceeds the VC dimension d, the number of realizable labelings grows only polynomially in m, not like 2^m.

Covering numbers: capacity by resolution

For real-valued classes — regression, margins, kernel machines — shattering is too blunt. Covering numbers measure capacity geometrically: fix a resolution ε, and ask how many ε-balls you need to cover the class under a chosen metric, so that every function in the class is within ε of some center. The logarithm of that count is the metric entropy. A class you can cover with few balls at every scale is small; one that needs exponentially many is rich.

Covering numbers are the universal currency of empirical-process theory. They connect to VC dimension (a VC class has covering numbers polynomial in 1/ε), they feed chaining arguments — Dudley's integral sums log-covering-numbers across scales to bound the supremum of a process far more tightly than a single union bound — and they are how smoothness assumptions enter learning rates. When you later see a rate like m^(−β/(2β+d)) for a β-smooth function class, it came out of a covering-number calculation.

\hat{\mathfrak{R}}_{S}(\mathcal{H})\;\le\;\inf_{\alpha\ge 0}\left(4\alpha+\frac{12}{\sqrt{m}}\int_{\alpha}^{\infty}\sqrt{\log N(\varepsilon,\mathcal{H},L_2)}\;d\varepsilon\right)

Dudley's entropy integral: chaining turns covering numbers at every resolution ε into a bound on Rademacher complexity.

Rademacher complexity: let the data speak

The sharpest of the three is Rademacher complexity. Take your actual sample, attach a random ±1 sign to each point, and ask how well the class can correlate with that pure noise: the Rademacher complexity is the expected best-case correlation a function in H can achieve with random signs. A class that can fit random labels has high complexity and will overfit; a class that cannot has low complexity and generalizes. It is a direct, data-dependent measurement of overfitting potential — you can estimate it from the very sample you trained on.

\hat{\mathfrak{R}}_{S}(\mathcal{H})=\mathbb{E}_{\sigma}\!\left[\sup_{h\in\mathcal{H}}\frac{1}{m}\sum_{i=1}^{m}\sigma_i\,h(x_i)\right],\quad \sigma_i\in\{-1,+1\}

Empirical Rademacher complexity: how well the class can correlate with random ±1 signs attached to your own sample.

Rademacher complexity dominates the picture because the other measures bound it: it is never larger than a VC-based estimate, and Dudley's chaining bounds it through covering numbers. Crucially it adapts to the distribution — if your data lives on a benign low-dimensional structure, the empirical Rademacher complexity is small even when the VC dimension is huge. This is the first measure tight enough to sometimes match reality, and the localized version in guide 4 sharpens it further.

# empirical Rademacher complexity (Monte Carlo estimate)
#   sigma_i ~ uniform({+1,-1});  S = sample of m points
R_hat = E_sigma[  sup_{h in H}  (1/m) * sum_i sigma_i * h(x_i)  ]
# gen. gap  <=  2 * R_hat  +  sqrt( log(1/delta) / (2m) )

If H can line up with random signs, it can fit noise — and will overfit.

From capacity to choice: SRM

Capacity measures do more than bound a fixed class — they let you choose one. Structural risk minimization (SRM) arranges your hypotheses into a nested ladder of classes of increasing complexity, then minimizes empirical risk plus a complexity penalty derived from the capacity of each rung. You are explicitly optimizing the bias–variance tradeoff: low rungs underfit (high bias), high rungs overfit (high variance), and the penalty steers you to the rung where the bound on true risk is smallest.

SRM is the theoretical ancestor of every regularized objective you have ever trained, and the margin-maximizing support vector machine is its most celebrated instance: rather than penalize parameter count, the SVM controls a capacity that shrinks as the margin grows — the bridge to margin theory we build in guide 4.