Common Errors in VC and Covering Arguments

Why Small Details Matter in VC Arguments

VC and covering arguments often have a compact form: exhibit a shattered set, count traces, or cover a class at a chosen radius. The conclusions can be powerful, but each depends on a precise object. A single missing labeling, an unexamined change of metric, or an unstated dependence on a probability measure can invalidate an otherwise plausible argument.

This tutorial focuses on four checks. For each claim, identify the exact witness or class, the distance being used, and whether the bound holds for one fixed distribution or uniformly over distributions. These checks do not replace the standard VC and entropy results; they help ensure those results are being applied to the right quantities.

Mistake 1: Treating a Partial Witness as Shattering

To prove that the VC dimension is at least \(k\), it is not enough to find a \(k\)-point set on which the class realizes “many” traces, or even all but one of them. Shattering requires every one of the \(2^k\) subsets. A single missing pattern means that this particular set is not a shattering witness.

Proof. A 0–1 labeling of \(S\) corresponds uniquely to the subset \(T\subseteq S\) labeled 1. A class member agrees with that labeling precisely when its trace on \(S\) is \(T\). Thus every labeling is realized exactly when every subset of \(S\) occurs as a trace, which is the definition of shattering. The lower-bound claim follows directly from the definition of VC dimension. \(\square\)

The converse direction needs a different kind of argument. A single failed candidate \(S\) does not establish that the VC dimension is below \(|S|\); it only shows that this particular \(S\) is not shattered. To prove an upper bound, one must rule out shattering for every set of the proposed size.

Mistake 2: Confusing VC Dimension with Class Cardinality

The number of members in a class and its VC dimension are related, but they are not interchangeable. If a class shatters \(k\) points, it must contain at least \(2^k\) distinct members: each required trace must come from a class member, and one member cannot have two different traces on the same set.

Proof. Suppose \(S\) of size \(k\) is shattered. By the definition of shattering, for every \(T\subseteq S\) there is an \(A\in\mathcal A\) with \(A\cap S=T\). If \(T_1\ne T_2\), the corresponding class members must be distinct, since one member has only one trace on \(S\). There are \(2^k\) subsets of \(S\), so \(|\mathcal A|\geq 2^k\). Taking base-two logarithms gives \(k\leq\log_2|\mathcal A|\). Applying this to the largest shattered set proves the claim. \(\square\)

Mistake 3: Changing the Covering Metric Without Changing the Radius

A covering number is defined relative to a metric or pseudometric. The notation \(N(\varepsilon,\mathcal A,L_1(Q))\) specifies both the radius and the probability measure. For set indicators, the \(L_1(Q)\) distance is \(Q(A\triangle B)\). The corresponding \(L_2(Q)\) distance is different: \[ \|\mathbf 1_A-\mathbf 1_B\|_{L_2(Q)}^2=Q(A\triangle B), \qquad \|\mathbf 1_A-\mathbf 1_B\|_{L_2(Q)}=\sqrt{Q(A\triangle B)}. \] Consequently, an \(\varepsilon\)-radius in \(L_2(Q)\) corresponds to an \(\varepsilon^2\)-radius in \(L_1(Q)\) for indicator functions. Reusing the same numerical radius across these metrics can change which pairs of sets are close.

There is also a useful, explicitly checkable way to transfer covers between measures. Write \(Q\leq cP\) when \(Q(E)\leq cP(E)\) for every measurable set \(E\), with \(c\geq 0\). This condition is stronger than merely saying that \(P\) and \(Q\) are both probability measures.

Proof. Apply the measure inequality \(Q(E)\leq cP(E)\) to \(E=A\triangle B\). This gives \[ d_Q(A,B)=Q(A\triangle B)\leq cP(A\triangle B)=c\,d_P(A,B). \] Now let \(C\in\mathcal A\) be a cover center for \(A\) under \(P\), so \(d_P(A,C)\leq\varepsilon\). The inequality just proved yields \(d_Q(A,C)\leq c\varepsilon\). This holds for every \(A\in\mathcal A\), so the same centers form a \(c\varepsilon\)-cover under \(Q\). \(\square\)

Without a condition connecting the measures, a cover under one measure need not be useful under another. For instance, let \(\mathcal A=\{\varnothing,\{0\}\}\) on \(\{0,1\}\). Under \(P\) concentrated at 1, the two sets have distance 0, so one center covers the class at every positive radius. Under \(Q\) concentrated at 0, their distance is 1, so at any radius below 1 two centers are needed. A small covering number for \(P\) alone does not imply a small covering number for \(Q\).

Mistake 4: Turning a Bound for One Measure into a Uniform Bound

A statement about \(N(\varepsilon,\mathcal A,L_1(Q))\) for one specified \(Q\) is a distribution-specific statement. A statement uniform over probability measures quantifies over every \(Q\), including measures that put mass where particular sets differ. The distinction is captured by the order of the quantifiers: a bound for each fixed \(Q\) with a constant that may depend on \(Q\) is not automatically a bound with one constant that works for all \(Q\).

For context, a standard uniform VC entropy result says that if \(\mathcal A\) is a class of measurable sets with finite VC dimension \(v\), then there is a universal constant \(C\) such that, for every probability measure \(Q\) and \(0<\varepsilon<1\), \[ N(\varepsilon,\mathcal A,L_1(Q))\leq (C/\varepsilon)^v. \] The important feature for this tutorial is the explicit uniformity: the same \(C\) and the same bound apply to every \(Q\). In a proposed argument, that uniformity must come from a theorem or a valid measure-independent argument; it cannot be inferred from checking one \(Q\). If measurability conditions are needed for a further probabilistic conclusion, those must also be checked for that conclusion.

A Practical Audit for VC and Covering Claims

When checking a derivation, write down what the argument actually establishes before using it. The following sequence separates the common failure points.

Common Mistakes

• “Almost all patterns” means shattering. It does not: the definition requires every subset of the witness set to occur as a trace.
• “There are many class members, so the VC dimension is large.” Cardinality gives the upper bound \(\operatorname{VC}(\mathcal A)\leq\log_2|\mathcal A|\) for a finite class, but does not determine the dimension.
• “A small cover in one metric is a small cover in another.” Not without translating distances and radii. For indicators, \(L_2\) distance is the square root of \(L_1\) distance.
• “The bound holds for my measure, so it holds uniformly.” Uniformity requires the same bound to hold over the stated collection of measures; a single-measure calculation does not establish it.