Covering and Packing Numbers

Covering counts how many small balls hide a set, packing counts how many separated points fit inside it. Both measure the effective size of a function class at a given resolution.

Seven small balls of radius 0.10 cover a patch while four well separated dots pack inside it, bracketing its size at that resolution

Why Does This Exist?

Uniform convergence asks for one guarantee over a whole class: every function in the class has train error near test error at once. You cannot union-bound over infinitely many functions, so you discretise. Cover the class with finitely many balls of radius $\varepsilon$ (a tolerance), prove the bound on the centres, then extend to every function by approximation. The price of discretisation is the covering number $N(\varepsilon)$ : how many balls you needed.

Packing numbers are the twin. They count how many points you can fit with pairwise distance above $\varepsilon$ , which lower-bounds how hard the class is. Together they bracket complexity: packing says the class is at least this rich, covering says it is at most this rich. Every chaining argument and many generalisation bounds start by estimating one of them.

Prerequisite in one paragraph. You need a metric, which is a distance rule $d(x, y)$ giving the separation between two points, and a ball of radius $\varepsilon$ around a centre. Distance and similarity metrics covers the rules, and compactness explains when finite covers exist at all.

Think of It Like This

Tents over a field, and fence posts inside it

To count how big a field is at tent resolution, ask two questions. How many tents of fixed size cover the whole field with overlaps allowed. And how many fence posts can you plant so every pair stays ten metres apart.

Seven tents might cover a patch while only four well-spaced posts fit inside. The tent count overestimates slightly because of overlap; the post count underestimates slightly because of gaps. The true size sits between them. Refine the tent size and both counts grow, tracing how the field fills at every scale.

Where the analogy stops: fields are two-dimensional and flat. Function classes curve, and their covering counts can grow exponentially in $1/\varepsilon$ rather than polynomially, which changes every downstream rate.

How It Actually Works

Fix a set $T$ with metric $d$ . The covering number $N(T, d, \varepsilon)$ is the smallest number of balls of radius $\varepsilon$ whose union contains $T$ . An $\varepsilon$ -net is the set of their centres: finitely many points within $\varepsilon$ of everything. The packing number $M(T, d, \varepsilon)$ is the largest number of points in $T$ with all pairwise distances above $\varepsilon$ .

They bracket each other: $M(T, d, 2\varepsilon) \le N(T, d, \varepsilon) \le M(T, d, \varepsilon)$ . In words, a maximal packing at scale $\varepsilon$ is automatically an $\varepsilon$ -cover, and two packed points cannot share one $\varepsilon/2$ -ball. Metric entropy is $\log N$ , the log count, which is what enters generalisation bounds additively.

The workhorse estimate is volumetric. The unit Euclidean ball in $d$ dimensions satisfies $N \le (1 + 2/\varepsilon)^d$ . Each coordinate needs about $1/\varepsilon$ grid points and dimensions multiply.

Worked example

Cover the ball of radius $1$ in $5$ dimensions at resolution $\varepsilon = 0.10$ . The bound gives $N \le (1 + 2/0.10)^5 = (1 + 20)^5 = 21^5$ . Compute $21^2 = 441$ , $21^4 = 441^2 = 194{,}481$ , times $21$ gives $4{,}084{,}101$ . So about $4.1$ million balls of radius $0.10$ always suffice, and $\log N \le 5\ln 21 \approx 5 \times 3.04 = 15.2$ . That log count $15.2$ is the complexity price this resolution adds to a uniform bound.

Packing gives the floor. The same volume ratio shows at least $(1/\varepsilon)^d = 10^5 = 100{,}000$ points at separation $0.10$ fit, so $M \ge 100{,}000$ . True complexity sits between $100{,}000$ and $4.1$ million at this scale, and both grow exponentially in dimension, which is the curse of dimensionality in covering form.

Watch Out For

Quoting a covering number in the wrong metric

A class can have a tiny covering number under the sup norm over $n$ fixed points but an enormous one under the true sup over all inputs. Plugging the empirical count into a bound that needs the population count understates complexity and produces a guarantee that fails on new points.

Fix: match the metric to the theorem. Chaining with Rademacher needs the empirical $L_2$ cover; uniform laws need the sup cover. Name the metric every time.

Treating log N as N in the bound

Generalisation bounds pay $\sqrt{\log N / n}$ , not $\sqrt{N/n}$ . With $N = 4.1$ million and $n = 10{,}000$ , the correct price is $\sqrt{15.2/10{,}000} \approx 0.039$ . Using $N$ directly gives $\sqrt{410} \approx 20$ , vacuous nonsense that sends people hunting for more data when the bound was simply misread.

Fix: always take the log first. Metric entropy is the currency, not the raw count.

The Quick Version

Covering counts balls hiding a set at resolution $\varepsilon$ ; packing counts $\varepsilon$ -separated points inside it.
They bracket: a maximal packing is a cover, and packed points need distinct small balls.
A 5-dimensional unit ball needs between 100,000 and 4.1 million balls of radius 0.10.
Bounds pay metric entropy $\log N$ , which is 15.2 in that example, not $N$ itself.
Always name the metric, because the same class has wildly different covers under different distances.