Empirical L1 Covering Numbers

Why Measure a Prediction Class on a Fixed Sample?

A class of binary prediction rules can be large, but on a particular sample it produces only a collection of binary vectors. Empirical L1 distance measures how often two such vectors disagree on that sample. A covering number then asks how many representative prediction vectors are needed to approximate every vector in the class to a specified empirical accuracy.

This is a sample-dependent measure: the same pair of prediction rules can be close on one sample and far apart on another. Repeated observations matter because the empirical distance counts sample positions, not merely distinct input locations.

Empirical L1 Distance and Covering Number

Definition: Let $S=(x_1,\ldots,x_n)$ be a fixed sample with $n\geq 1$, and let $\mathcal H$ be a nonempty class of functions $h:\mathcal X\to\{0,1\}$. The prediction vector of $h$ on $S$ is $(h(x_1),\ldots,h(x_n))$. For $h,g\in\mathcal H$, their empirical L1 distance is $$ d_S(h,g)=\frac{1}{n}\sum_{i=1}^n |h(x_i)-g(x_i)|. $$ For $\varepsilon\geq 0$, the empirical L1 covering number $N(\varepsilon,\mathcal H,L_1(P_n))$ is the smallest number of centers from $\mathcal H$ whose closed balls of radius $\varepsilon$, under $d_S$, cover $\mathcal H$. Equivalently, it is the least $m$ for which there are $h_1,\ldots,h_m\in\mathcal H$ such that every $h\in\mathcal H$ satisfies $d_S(h,h_j)\leq\varepsilon$ for some $j$.

Here $P_n$ is the empirical distribution that puts mass $1/n$ at each sample position. Since predictions are binary, $|h(x_i)-g(x_i)|$ equals 1 when the predictions disagree and 0 when they agree. Thus $d_S$ is the fraction of sample positions on which the two predictions differ: normalized Hamming distance between their prediction vectors.

Different hypotheses may yield the same vector on $S$, so $d_S$ can be zero for two functions that are not identical everywhere on $\mathcal X$. It is therefore a pseudometric on functions, although it is a metric on the distinct prediction vectors. The covering number depends on the class as observed on the sample, not on distinctions between functions that the sample cannot detect.

Worked Example: Repeated Sample Points Contribute Repeatedly

Take $S=(a,a,b,b,b)$, so $n=5$. Let $h(a)=0,\ h(b)=0$, and $g(a)=1,\ g(b)=0$. Their prediction vectors are $00000$ and $11000$.

The first two positions disagree and the last three agree. Therefore $$ d_S(h,g)=\frac{|0-1|+|0-1|+|0-0|+|0-0|+|0-0|}{5} =\frac{2}{5}. $$ The disagreement at $a$ is counted twice because $a$ occurs twice in the sample.

If we instead counted each distinct location just once, we would get a disagreement fraction of $1/2$ across $\{a,b\}$. That is not the empirical L1 distance for this sample: the empirical measure assigns mass $2/5$ to $a$ and $3/5$ to $b$. For instance, a pair of rules that disagrees only at $b$ has distance $3/5$, since $b$ occurs in three sample positions.

How Repetitions and Duplicate Predictions Affect the Calculation

Repeated sample locations can be collected into weights without changing the definition. Suppose the distinct locations in $S$ are $u_1,\ldots,u_r$, and $u_j$ occurs $m_j$ times. Then $\sum_{j=1}^r m_j=n$, and grouping equal terms in the empirical sum gives

d_S(h,g)=\frac{1}{n}\sum_{j=1}^r m_j\,|h(u_j)-g(u_j)|.

A location contributes its multiplicity times its disagreement indicator. This weighted form is useful for hand calculations, but the normalization remains by the original sample size $n$, not by the number $r$ of distinct locations.

Result: For any fixed sample, the empirical L1 covering number of $\mathcal H$ is exactly the covering number of its set of distinct prediction vectors on that sample, using normalized Hamming distance and centers from that set.

Proof. Let $V=\{(h(x_1),\ldots,h(x_n)):h\in\mathcal H\}$, with duplicate vectors retained only once. The distance between two hypotheses is exactly the normalized Hamming distance between their vectors, by the definition of $d_S$. A cover of $\mathcal H$ by hypotheses therefore gives a cover of $V$ by their vectors; if multiple centers yield the same vector, deleting the repetitions cannot make the cover worse. Conversely, every vector in $V$ is produced by at least one hypothesis in $\mathcal H$. Replace each center vector in a cover of $V$ by one hypothesis that produces it. The resulting hypotheses cover $\mathcal H$ with the same radius and no more centers. The two minimum cover sizes are equal. $\square$

This also gives an immediate finite bound. Even if $\mathcal H$ contains infinitely many functions, there are at most $2^n$ binary vectors of length $n$. If $\mathcal H$ is nonempty, one can choose one hypothesis for each distinct vector, so

1\leq N(\varepsilon,\mathcal H,L_1(P_n))\leq |V|\leq 2^n \qquad (\varepsilon\geq 0).

Worked Example: Covering a Finite Set of Four Vectors

Let the prediction vectors on a four-point sample be $v_1=0000,\ v_2=0011,\ v_3=1100,\ v_4=1111$, and take $\varepsilon=1/2$. A center covers a vector if their normalized Hamming distance is at most $1/2$, or equivalently if they differ in at most two of the four coordinates.

The pairwise distances are $$ d(v_1,v_2)=\frac{2}{4}=\frac12,\quad d(v_1,v_3)=\frac{2}{4}=\frac12,\quad d(v_1,v_4)=\frac{4}{4}=1, $$ $$ d(v_2,v_3)=\frac{4}{4}=1,\quad d(v_2,v_4)=\frac{2}{4}=\frac12,\quad d(v_3,v_4)=\frac{2}{4}=\frac12. $$ The vector $v_1$ is a center for $v_1,v_2,v_3$, but not for $v_4$. The vector $v_4$ is a center for $v_2,v_3,v_4$, but not for $v_1$. Thus two centers, $v_1$ and $v_4$, cover all four vectors.

One center cannot suffice: each of the four candidate centers is at distance 1 from its opposite vector ($v_1$ and $v_4$, or $v_2$ and $v_3$). That distance exceeds $1/2$, so no candidate center covers the whole set. Consequently $N(1/2,\mathcal H,L_1(P_n))=2$ for a class with exactly these four sample prediction vectors.

Basic Properties and a Second Covering Calculation

For a nonempty finite set of sample prediction vectors, the covering number is always finite: taking every distinct vector as a center gives an exact cover at every nonnegative radius. At radius zero, a closed ball contains only vectors at distance zero from its center, so it contains just that center vector. Therefore

N(0,\mathcal H,L_1(P_n))=|V|.

The covering number is also nonincreasing in the radius. If $\varepsilon_1\leq\varepsilon_2$, every ball of radius $\varepsilon_1$ is contained in the ball with the same center and radius $\varepsilon_2$. Any cover at the smaller radius is thus a cover at the larger radius, which proves

N(\varepsilon_2,\mathcal H,L_1(P_n)) \leq N(\varepsilon_1,\mathcal H,L_1(P_n)).

If $\varepsilon$ is at least the largest distance between any two vectors in $V$, one center covers all of $V$, and the covering number is 1. The radius convention matters: here balls are closed, so a vector at distance exactly $\varepsilon$ is covered.

Worked Example: Duplicate Hypotheses Do Not Increase the Cover

On a three-point sample, suppose five hypotheses produce the vectors $000,\ 000,\ 100,\ 110,\ 111$. There are five hypotheses but only four distinct sample prediction vectors. At radius zero, only identical vectors can be covered by one center, so $$ N(0,\mathcal H,L_1(P_n))=4, $$ not 5.

Now take $\varepsilon=1/3$. The distance between two vectors is their number of differing coordinates divided by 3. The center $100$ covers $000,100,110$: the respective distances are $1/3,0,1/3$. The center $110$ covers $100,110,111$: the distances are $1/3,0,1/3$. Together these two centers cover all four distinct vectors.

No single center suffices. The distances from each possible center to a vector it cannot cover are: from $000$ to $111$, $3/3=1$; from $100$ to $111$, $2/3$; from $110$ to $000$, $2/3$; and from $111$ to $000$, $3/3=1$. Each exceeds $1/3$. Hence $N(1/3,\mathcal H,L_1(P_n))=2$. The repeated $000$ hypothesis cannot lower this number or raise it: it adds no new prediction vector.

Common Mistakes and Why the Quantity Matters

Empirical L1 covering numbers turn a collection of prediction rules into a finite approximation problem on the observed sample. They describe how many distinct representatives are needed at a chosen disagreement tolerance. Because the calculation depends on both the sample and the prediction vectors, it can make a large function class manageable for sample-based arguments without claiming that functions are close away from the observed points.

Counting distinct locations instead of sample positions. This changes the empirical distribution when the sample has repetitions. Use each position in the sum, or use the multiplicity-weighted formula and divide by $n$.
Claiming that a disagreement at a location contributes only once, even if the location is repeated. That is incorrect: if two hypotheses disagree at a location appearing $m$ times, the disagreement contributes $m/n$. If they agree at every distinct sample location, their distance is zero regardless of repetitions.
Counting hypotheses instead of distinct prediction vectors. Several functions may make identical predictions on the sample. They all represent the same vector and do not require separate centers.
Using a strict radius condition by accident. Under the closed-ball convention here, distance exactly $\varepsilon$ counts as covered. Check the inequality $d_S\leq\varepsilon$ when deciding whether a center works.

Key takeaway: First form the binary prediction vectors on the fixed sample. Their normalized Hamming distances determine the empirical L1 covering number; repeated sample positions affect the weights, while duplicate prediction vectors do not add complexity.

Check Your Understanding

Use the fixed-sample definition and the closed-ball convention to answer these questions.

If a sample of size 8 contains the same input three times and two hypotheses disagree there but agree elsewhere, what is their empirical L1 distance?
Why can two different functions have empirical L1 distance zero on a sample?
A class produces six hypotheses but only four distinct prediction vectors on the sample. What is its covering number at radius zero?
For a finite set of binary vectors, explain why taking every distinct vector as a center gives a cover for any nonnegative radius.
What property of the covering number follows when the radius is increased, and why?

What You'll Learn