Covering Numbers and Metric Entropy

VC dimension is a great complexity measure for classifiers that output a strict $+1$/$-1$ label, because "does this class realize every labeling of these points" is a well-posed question when there are finitely many possible labelings. It breaks down for models that output a continuous number — a regression predicting a return, or a probability between 0 and 1 — because there are infinitely many possible "labelings" (any real number is a valid output), so shattering-based counting has nothing to count. Covering numbers solve this by asking a different, more general question: not "how many outputs can this class produce exactly," but "how many approximate representatives does it take to get within some tolerance $\epsilon$ of every function in the class."

The analogy: how many floodlights to light a whole room

You want to light every corner of a large, oddly-shaped room, and any point within a floodlight's fixed radius counts as "covered," even if not lit dead-center. A tiny closet might need just one floodlight; a sprawling warehouse with many nooks needs many. The number of floodlights required — placed optimally — to guarantee no point in the room is farther than the fixed radius from some floodlight is exactly a covering number: it depends on both the room's size/shape (the hypothesis class) and the radius you're willing to tolerate (the tolerance $\epsilon$). Shrink the tolerable radius and you need more floodlights; that relationship, tracked as $\epsilon \to 0$, is the class's metric entropy.

The formal definition

Given a hypothesis class $\mathcal{H}$ and a distance metric $d(\cdot,\cdot)$ between functions (e.g., how much they disagree on average over the data), the $\epsilon$-covering number $N(\epsilon, \mathcal{H}, d)$ is the smallest number of functions $\{g_1, \dots, g_N\}$ such that every $h \in \mathcal{H}$ is within distance $\epsilon$ of some $g_i$:

$$\forall h \in \mathcal{H}, \; \exists\, g_i \; \text{such that} \; d(h, g_i) \le \epsilon$$

In words: you don't need to list every function in a possibly infinite class — you just need a finite "sample set" of representative functions dense enough that nothing in the class strays farther than $\epsilon$ from its nearest representative. Metric entropy is $\log N(\epsilon, \mathcal{H}, d)$ — the covering number's logarithm — and it plugs into generalization bounds the same conceptual role VC dimension's $\ln(2n/d)$ term does: it measures effective complexity, but continuously, as a function of the tolerance $\epsilon$, rather than as one fixed number.

Worked example 1: covering a simple interval-valued class

Let $\mathcal{H}$ be constant functions $h_c(x) = c$ for $c \in [0, 10]$, distance $d(h_c, h_{c'}) = |c - c'|$. At tolerance $\epsilon = 1$, representatives at $c = 0.5, 1.5, \dots, 9.5$ (10 of them) each cover a width-2 interval, so $N(1, \mathcal{H}, d) = 10$. Tighten to $\epsilon = 0.1$: representatives every $0.2$ are needed, giving $N(0.1, \mathcal{H}, d) = 50$. The covering number grows as $\epsilon$ shrinks — expected, since this simple 1-dimensional class has metric entropy growing only like $\log(1/\epsilon)$, mild growth reflecting genuinely low complexity.

Worked example 2: comparing two classes at the same tolerance

At $\epsilon = 0.1$, the constant-function class above needs $N=50$ representatives. Compare to linear functions $h_{a,b}(x) = ax+b$ over a bounded domain: with two free parameters instead of one, its covering number at the same $\epsilon=0.1$ scales roughly like the square of a single-parameter class's — thousands rather than tens. More free parameters means many more representatives to cover the same tolerance, making the intuitive "more parameters, more complexity" idea numerically precise, and extending smoothly to non-classification model classes.

Drag the curve above and note the shape: metric entropy typically grows like $\log(1/\epsilon)$ for well-behaved low-dimensional classes, which is the mild, controllable growth a useful generalization bound needs.

What this means in practice

Covering numbers underpin generalization theory for regression models, kernel methods, and neural networks with continuous outputs, exactly where VC dimension's binary-labeling framework doesn't apply cleanly. "Polynomial" versus "exponential" metric entropy growth as $\epsilon \to 0$ does the same complexity-control job VC dimension does for classifiers — it says how fast generalization guarantees improve with more data.