Bracketing Entropy for VC Classes

Why Brackets Are Stronger Than Covers

A metric cover approximates each function by a nearby representative. A bracket does something more structured: it encloses a function pointwise between a lower and an upper function. For indicator functions, those endpoints can be viewed as uncertain membership decisions. The measure of the region where the endpoints disagree is the bracket’s width.

This distinction matters in empirical-process arguments, where pointwise bounds can control whole collections of functions at once. For a VC class of sets, the number of brackets required at a given width is finite and grows at most polynomially in the reciprocal width. The bound below is uniform over the choice of probability measure.

Definition: Let $(\mathcal X,\mathcal A,P)$ be a probability space and let $\mathcal C$ be a class of sets in $\mathcal A$. Write $1_A$ for the indicator of $A\in\mathcal C$. An $L^1(P)$ bracket is a pair of measurable functions $[l,u]$ with $0\leq l\leq u\leq1$ pointwise. It contains $1_A$ if $l(x)\leq1_A(x)\leq u(x)$ for every $x$. Its width is $P(u-l)=\int (u-l)\,dP$. The bracketing number $N_{[]}(\epsilon,\mathcal C,L^1(P))$ is the smallest number of brackets of width at most $\epsilon$ whose union contains every $1_A$, $A\in\mathcal C$; it is infinite if no finite such collection exists.

The endpoints need not themselves be indicators. They may take any values in $[0,1]$, and pointwise ordering is part of the definition. For a set bracket $[L,U]$, where $L\subseteq U$, the corresponding function bracket is $[1_L,1_U]$, with width $P(U\setminus L)$.

The VC Bracketing Bound

The VC dimension of $\mathcal C$ is the largest integer $v$ for which some set of $v$ points is shattered by $\mathcal C$: every subset of those points is the trace of a member of $\mathcal C$. If no finite set is shattered, the dimension is infinite. In this tutorial, the finite-dimensional case is the one of interest.

Theorem (VC bracketing bound): There is a universal constant $K$ such that the following holds. Let $\mathcal C$ be a countable class of measurable sets with finite VC dimension $v\geq1$, and let $P$ be any probability measure on the underlying measurable space. For $0<\epsilon\leq1$, $$ N_{[]}(\epsilon,\mathcal C,L^1(P)) \leq \left(\frac{K}{\epsilon}\right)^{2v}. $$ The constant does not depend on $P$, the space, or the particular class. The same conclusion holds for a class that is pointwise measurable—one having a countable subclass whose indicators approximate those of every class member pointwise—provided the brackets and envelopes used are measurable. A class of VC dimension zero has at most one distinct set and needs one bracket.

The exponent and constant in this convenient bound are not intended to be sharp. Its central implication is finite bracketing entropy: for every positive target width, finitely many brackets suffice. The countability condition avoids measurability problems with uncountable unions and suprema; pointwise measurability is a common sufficient substitute in applications.

Proof ingredient (VC bracketing lemma): For a measurable VC class of dimension $v\geq1$ under a probability measure $P$, the sets can be enclosed by at most $(K/\epsilon)^{2v}$ measurable set brackets $[L_j,U_j]$ satisfying $P(U_j\setminus L_j)\leq\epsilon$. The bound holds first for finite classes and is uniform in their cardinality. One proof uses a finite-sample encoding: record the traces of class members on a sample, form lower and upper sets from the members sharing an encoded trace, and count the resulting enclosures by applying the Sauer–Shelah growth bound to the traces. A double-sampling argument controls the $P$-mass of the gaps; choosing the sample size proportional to $v\epsilon^{-1}$ and applying the growth bound gives a polynomial count, bounded by $(K/\epsilon)^{2v}$ after enlarging the universal constant. Finite-subclass bounds extend to countable classes by taking increasing finite subclasses and using measurable limits of the endpoints.

To obtain the theorem, apply the lemma to $\mathcal C$, and replace each set bracket $[L_j,U_j]$ by the function bracket $[1_{L_j},1_{U_j}]$. If $A$ is enclosed by the set bracket, then $L_j\subseteq A\subseteq U_j$, so $1_{L_j}\leq1_A\leq1_{U_j}$ pointwise. The function-bracket width is $$ P(1_{U_j}-1_{L_j})=P(U_j\setminus L_j)\leq\epsilon. $$ Thus the set brackets give brackets for the indicator class with the same count and width bound. For a pointwise measurable class, apply the finite-subclass construction to the countable approximating subclass and use the stated measurable-envelope condition to pass to the full class. $\square$

Worked Examples

Worked Example: Threshold Sets Under Lebesgue Measure

Let $\mathcal X=[0,1]$, let $P$ be the uniform (Lebesgue) probability measure, and consider $\mathcal C=\{[0,t]:0\leq t\leq1\}$. This class has VC dimension one: a single point can be included or excluded by choosing $t$, but two ordered points cannot realize the trace that includes the larger point while excluding the smaller one.

Fix $\epsilon=0.2$, and partition $[0,1]$ into five intervals of length $0.2$. For $j=0,\ldots,4$, use the set bracket $[0,0.2j]\subseteq A\subseteq[0,0.2(j+1)]$ for thresholds $t$ in the corresponding interval. Include the singleton threshold at $t=0$ in the first bracket and $t=1$ in the last.

For each bracket, the gap is the interval between its endpoints, whose Lebesgue measure is $0.2$. Hence five brackets suffice, and each has width exactly $0.2$. The VC theorem also guarantees a finite bound, though its general numerical upper bound is much looser than this explicit construction.

Worked Example: A Finite Class and the Meaning of Width

Let $\mathcal X=\{a,b,c\}$ with $P(\{a\})=0.5$, $P(\{b\})=0.3$, and $P(\{c\})=0.2$. Consider the class $\mathcal C=\{\varnothing,\{a\},\{a,b\}\}$. It has VC dimension one: the point $a$ is shattered, while no pair of points is shattered.

For $\epsilon=0.3$, use three brackets. The exact bracket $[\varnothing,\varnothing]$ contains the empty set and has width zero. The exact bracket $[\{a\},\{a\}]$ contains $\{a\}$ and also has width zero. For the last set, use $[\{a\},\{a,b\}]$; its gap has measure $P(\{b\})=0.3$.

All three brackets satisfy the width requirement, and together they cover the class. This example also shows why width is measured by probability, not by the number of points in the gap: a one-point gap can have mass $0.3$, while another one-point gap in a different distribution could have much smaller mass.

Worked Example: Singleton Sets on a Large Finite Space

Let $\mathcal X=\{1,\ldots,100\}$, give each point probability $0.01$, and let $\mathcal C$ consist of the empty set and all singleton sets. Its VC dimension is one. Take $\epsilon=0.1$. The single bracket $[\varnothing,\{1,\ldots,100\}]$ has width one, so it is too wide.

Instead, partition the 100 singleton sets into ten groups of ten. For each group $G$, use the bracket $[\varnothing,G]$. It contains the empty set and every singleton in $G$, and its width is $P(G)=10(0.01)=0.1$. Ten such brackets cover all singleton sets, and one of them also covers the empty set.

The class has 101 members, but the required bracket count at this width is only ten in this construction. This illustrates why counting all class members is not the right way to reason about bracketing entropy: a bracket may cover several distinct sets when the probability mass of their combined uncertainty is small enough.

Thresholding Endpoints: What It Does and Does Not Preserve

For endpoints in $[0,1]$, a function bracket for indicators can be converted into a set bracket by thresholding at one. If $l\leq1_A\leq u$, then $$ \{x:l(x)=1\}\subseteq A\subseteq\{x:u(x)=1\}. $$ The left inclusion holds because $l(x)=1$ and $l(x)\leq1_A(x)\leq1$ force $1_A(x)=1$. The right inclusion holds because $1_A(x)=1$ and $1_A(x)\leq u(x)\leq1$ force $u(x)=1$. Thus thresholding preserves coverage under the stated endpoint convention.

It does not necessarily preserve the bracket’s width. For example, if $l=0.9$ and $u=1$ on a set of probability $0.2$, the function-bracket width there is $0.1(0.2)=0.02$. But thresholding produces lower set empty and upper set equal to that whole region, with set-bracket width $0.2$. Coverage remains valid; the width can increase.

Common Mistake

Confusing a cover with a bracket cover. A collection of nearby representatives in $L^1(P)$ is not automatically a collection of pointwise enclosures. Brackets require lower and upper endpoints that contain each target function at every point.
Ignoring the measure. A bracket is small relative to $P$, not necessarily in a point-counting or uniform sense. The same sets can have very different bracket widths under different probability measures.
Claiming thresholding preserves width. For endpoints in $[0,1]$, thresholding at one preserves coverage, but it can enlarge the gap measured as a set. The function-bracket width and the thresholded set-bracket width are different quantities.
Omitting measurability conditions. For an uncountable class, unions or intersections used to define bracket endpoints need not be measurable. Countability or suitable measurable-envelope assumptions ensure the probability widths are defined.

Key takeaway: For a measurable VC class of finite dimension $v$, the $L^1(P)$ bracketing number is finite at every positive width and admits a universal polynomial bound in $1/\epsilon$. Each bracket must enclose its indicator pointwise, and its width is the probability mass between its endpoints.

Check Your Understanding

Use the definitions and theorem to answer the following.

What two properties must a pair $[l,u]$ satisfy to be an $L^1(P)$ bracket for an indicator class?
For a set bracket $[L,U]$, express its function-bracket width in terms of $P$.
Why does the VC bracketing theorem require a measurability condition on the class or its envelopes?
Does thresholding endpoints in $[0,1]$ at one preserve coverage, width, both, or neither? Explain.
For the singleton example, why can ten brackets of width $0.1$ cover 100 singleton sets under the uniform distribution?