Symmetrization, Bracketing, and Covering Numbers
A pointwise law of large numbers does not control a function selected from the data. For that we need a bound on the largest empirical error over the class. Symmetrization replaces the unknown centering by independent random signs; brackets and covers then reduce the class to finitely many approximations. The approximation error and the size of this finite collection determine whether the bound tends to zero.
Let \(X_1,\ldots,X_n\) be i.i.d. with law \(P\). For a function \(f\), write \(Pf=\mathbb{E} f(X_1)\), \(P_nf=n^{-1}\sum_{i=1}^n f(X_i)\), and \(\mathbb G_nf=\sqrt n(P_n-P)f\). Rademacher variables are independent random signs, independent of the observations. See the empirical-process setup for measurability conventions.
Informally, we know the central limit theorem tells us that for a collection of i.i.d. random variables \(\{X_k\}_{1 \leq k \leq n}\), the sum \(\sum_{1 \leq k \leq n} (f(X_k) - \mathbf P\,\,\!\!f)\) for some bounded function \(f\), once rescaled by \(\frac{1}{\sqrt{n}}\), yields a Gaussian limit (nondegenerate when the variance is positive). So, sums of this sort is of order \(\sqrt{n}\) in probability, even though we might suspect that this is of order \(n\) (since we are adding \(n\) terms of order \(1\)). Though, we can somewhat imagine why this is the case: the summand contains independent observations, so their signs are probably not all identical. Heuristically, we can think that these random signs are the factor that leads to the nontrivial limiting behaviour. If we introduce random sign fluctuations, there might be a chance we can obtain a nontrivial limiting behaviour; this is the broad heuristic behind symmetrization.
Formally, let \(X_1, \dots, X_n\) denote i.i.d. random variables defined on \(\mathscr X\). Suppose \(X_i\) has distribution \(\mathbf P\,\,\!\!\). Let \(\mathcal F\) denote a function class on \(\mathscr X\).
Proposition 1. Let \(X_1,\ldots,X_n\) be iid with law \(P\), let \(Y_1,\ldots,Y_n\) be an independent copy, and let \(\varepsilon_i\) be independent Rademacher signs independent of both samples. For a countable class of integrable functions, or a pointwise measurable class with an integrable envelope,
The same inequality holds with \(f(X_i)\) replaced by \(f(X_i)-Pf\) on the right. If suprema are not measurable, the statement uses outer expectations.
Proof. Conditional Jensen first replaces \(Pf\) by the ghost-sample value \(f(Y_i)\). Swapping the two entries of any independent pair \((X_i,Y_i)\) leaves their joint law unchanged. Therefore the entire difference process, simultaneously for every \(f\), has the same law after multiplication by independent signs:
The triangle inequality separates the two samples and gives the factor two. The centered version follows from \(f(X_i)-f(Y_i)=(f(X_i)-Pf)-(f(Y_i)-Pf)\). □
Symmetrization arguments also work for bounding tail probabilities.
Proposition 2. Let \(X\) and \(Y\) be random variables such that \(\mathbb{E} f(X) \leq \mathbb{E} f(Y)\) holds for every convex, increasing function \(f\). Suppose
and for some \(c_2 > 0\) and \(c_1, n \geq 1\), then
Proof. First prove the assertion for exponent one. For \(a\geq0\), the increasing convex function \(z\mapsto(z-a)_+\) and tail integration imply
If \(t>1/c_2\), choose \(a=t-1/c_2\). On \(X\geq t\), we have \((X-a)_+\geq1/c_2\). Markov therefore gives \(\mathbb P(X\geq t)\leq c_1e^{1-c_2t}\). For \(0\leq t\leq1/c_2\), the claimed upper bound is at least one.
For the stated exponent \(n\geq1\), put \(U=(X_+)^n\) and \(V=(Y_+)^n\). The map \(z\mapsto(z_+)^n\) is convex and increasing on all of \(\mathbb R\), so composition with any increasing convex test function preserves the assumed comparison. Moreover \(\mathbb P(V\geq s)\leq c_1e^{-c_2s}\) for \(s>0\), and the bound at zero is valid because \(c_1\geq1\). Apply the exponent-one result to \(U,V\) at \(s=t^n\). For \(t>0\), \(U\geq t^n\) is equivalent to \(X\geq t\); at \(t=0\) the desired inequality is trivial. Using the positive part avoids the source's invalid composition with \(z^n\) at negative \(z\). ◻
1. Tools to Study the Complexity of Function Classes
Suppose that \(X_1, \dots, X_n\) are independent random variables defined on the space \(\mathscr X\) with probability measure \(\mathbf P\,\,\!\!\). Suppose furthermore that \(X_1, \dots, X_n\) are identically distributed, and let \(F\) denote the distribution function of \(\mathbf P\,\,\!\!\). The strong law of large numbers says that for any Borel measurable function (i.e. measurable when both the domain and the range are equipped with the Borel \(\sigma\)-algebra) \(h: \mathbb R \to \mathbb R\) such that \(\mathbb{E} |h(X_i)| < \infty\), we have
as \(n \to \infty\). But it turns out that an even stronger statement is true: take the function \(h(X_i) = \mathbb 1 \{X_i \leq x\}\) for \(x \in \mathbb R\), so that the left-hand side of (1) reduces to the empirical distribution function
and the stronger statement is upgrading (1) to hold true over the entire domain \(\mathbb R\), i.e.
as \(n \to \infty\). This is the original formulation of the Glivenko-Cantelli theorem. Note that there is a certain “hardness” to showing this statement is true: \(\widehat F_n\) is random, as it depends on the realizations of \(X_1, \dots, X_n\). However, the problem is much easier to tackle when we examine this from the perspective of the function class we are working with. The rest of this section develops tools to characterize and study function classes.
1.1. Bracketing
As above, heuristically, whether the uniform convergence holds depends on the complexity of the class of functions we consider. Here, we follow historical development and described the case when the function class considered is the set of indicator functions, \(g_x (t) = \mathbb 1 \{t \leq x\}\). A priori, if we could somehow “approximate” this class of functions by a small class of functions, then we could apply the strong law of large numbers to each function in the small class, and hope the “approximation error” is small. We develop the definitions in a general setting, with an eye to apply this to Glivenko-Cantelli theorem in the extended remark below.
For \(1\leq q<\infty\), let \(L^q (\mathbf P\,\,\!\!)\) denote the space of functions \(g\) (defined on some ambient space \(\mathscr X\)) such that \(P |g|^q < \infty\). The choice of norm affects the size of a bracket, so we distinguish \(L^q (\mathbf P\,\,\!\!)\) for different \(q\); so, we write \(\lVert \cdot \rVert_{\mathbf P\,\,\!\!,q}\) for the norm on \(L^q(P)\). In the sequel, it is useful to think about \(\mathcal F = (\mathcal F, \lVert \cdot \rVert_{\mathbf P\,\,\!\!,q})\) as a subset of the normed space \(L^q (\mathbf P\,\,\!\!)\). For now, take any functions \(l, u \in L^q (\mathbf P\,\,\!\!)\), and suppose \(l \leq u\) pointwise (i.e. holds at every point \(x \in \mathscr X\)). Then, we define the bracket of the class of functions \(L^q (\mathbf P\,\,\!\!)\), denoted \([l,u]\), as
An \(\varepsilon\)-bracket is a bracket \([l,u]\) with \(\lVert l-u \rVert_{\mathbf P\,\,\!\!,q} = (\mathbf P\,\,\!\!|l-u|^q)^{\frac1q} < \varepsilon\). For \(\mathcal F\), the bracketing number \(N_{[\:]} (\varepsilon, \mathcal F, \lVert \cdot \rVert_{\mathbf P\,\,\!\!,q})\) is the minimum number of \(\varepsilon\)-brackets needed to cover \(\mathcal F\); here, \(l\) and \(u\) do not need to belong to \(\mathcal F\). Finally, we say a function \(x \mapsto F(x)\) is an envelope function of a class \(\mathcal F\) if \(|f(x)| \leq F(x)\) for every \(x \in \mathscr X\) and \(f \in \mathcal F\). The minimum envelope function is \(x \mapsto \sup_{f \in \mathcal F} |f(x)|\).
Remark 3 (Glivenko-Cantelli). On \(\mathbb R\), consider the class of indicator functions
For clarity, let us write \(\mathcal F_1 = \{ g_x : x \in \mathbb R \}\). Since these functions are defined on the real line, we look at \(L^1 (\mathbf P\,\,\!\!)\) functions. We can show a number of things is true about this function class.
Lemma 4. \(N_{[\:]} (\varepsilon, \mathcal F_1, \lVert \cdot \rVert_{\mathbf P\,\,\!\!,1}) < \infty\) for any \(\varepsilon > 0\).
Proof. Choose an integer \(m\geq2\) with \(1/m<\varepsilon\), and let \(q_j=\inf\{x:F(x)\geq j/m\}\), \(1\leq j<m\). Each quantile is finite. List their distinct values as \(t_1<\cdots<t_k\), and adjoin \(t_0=-\infty\), \(t_{k+1}=+\infty\).
For consecutive cuts, \(P(t_j<X<t_{j+1})\leq1/m\). Indeed, if \(F(t_{j+1}-)-F(t_j)>1/m\), some grid level \(r/m\) lies strictly between these values. Right continuity at \(t_j\) and the definition of the left limit at \(t_{j+1}\) would then put \(q_r\) strictly inside this gap, a contradiction. The identical grid argument handles both infinite end intervals.
For each \(j\), use the bracket
where the lower endpoint is zero at \(t_0=-\infty\) and the upper endpoint is one at \(t_{k+1}=+\infty\). Its \(L^1(P)\) width is \(P(t_j<X<t_{j+1})\leq1/m<\varepsilon\). Every \(g_x\) belongs to the bracket whose cuts satisfy \(t_j\leq x<t_{j+1}\). The closed lower half-line and open upper half-line are essential: they keep any atom at a cut out of the bracket width while covering the indicator at that cut in the next bracket. There are only finitely many brackets. ◻
The same finite-approximation argument proves a uniform law for any class with finite bracketing numbers at every positive scale, under the integrability assumptions below. In what follows, let
denote the empirical measure of i.i.d. \(X_1, \dots, X_n\) observations on \(\mathscr X\).
Theorem 5. Let \(\mathcal F\) be a function class such that \(N_{[\:]} (\varepsilon, \mathcal F, \lVert \cdot \rVert_{\mathbf P\,\,\!\!,1}) < \infty\) for any \(\varepsilon > 0\). Then, \(\sup_{g \in \mathcal F} | \widehat P_n g - Pg | \to 0\) almost surely.
Note that a lot of texts write \(\lVert \widehat P_n - \mathbf P\,\,\!\!\rVert_{\mathcal F} \triangleq \sup_{g \in \mathcal F} |\widehat P_n g - \mathbf P\,\,\!\!g|\).
Proof. Fix \(\varepsilon>0\), and choose finitely many pointwise brackets \([l_j,u_j]\) covering \(\mathcal F\), with integrable endpoints and \(P(u_j-l_j)<\varepsilon\). For any \(g\) in bracket \(j\),
The lower bound uses \(P_n g\geq P_nl_j\) and \(P(g-l_j)\leq P(u_j-l_j)\); the upper bound is analogous. Hence
The strong law makes the finite maximum tend to zero on an event of probability one. Perform this construction for \(\varepsilon=1/r\), \(r=1,2,\ldots\), and intersect the countably many probability-one events. On that single event the limsup of the supremum is at most every \(1/r\), and hence is zero. This argument also gives a pointwise assertion outside a measurable null set if the supremum itself is not measurable. ◻
The Glivenko-Cantelli theorem then follows directly from Theorem 5.
Remark 6 (Glivenko-Cantelli via concentration inequality). Let \(X_1, \dots, X_n\) denote i.i.d. random variables on \(\mathscr X\). Let \(\mathcal F\) denote a collection of real-valued functions on \(\mathscr X\) uniformly bounded by a positive constant \(M\), i.e.
Assume the class is countable, or has a countable pointwise dense subclass, so that the supremum below is measurable. Define
Replacing only coordinate \(i\) changes each expression inside the supremum by at most \(|f(x_i)-f(x_i')|/n\leq2M/n\). The inequalities \(||a|-|b||\leq|a-b|\) and \(|\sup a_f-\sup b_f|\leq\sup|a_f-b_f|\) therefore give \(|G(x)-G(x^{(i)})|\leq2M/n\). McDiarmid yields
Equivalently, for \(0<\delta<1\), the deviation is at most \(\sqrt{(2M^2/n)\log(1/\delta)}\) with probability at least \(1-2\delta\). Thus bounding \(\mathbb EG\) controls the uniform empirical error. For the half-line class this expectation can be bounded by counting its distinct values on the sample.
Theorem 7. Let \(X_1, \dots, X_n\) are i.i.d. real-valued random variables with distribution \(\mathbf P\,\,\!\!\) and cumulative distribution function \(F\). Let \(\widehat F_n\) denote the empirical distribution function associated with the data \(X_1, \dots, X_n\). Then,
Proof. Put \(G_n=\sup_x|\widehat F_n(x)-F(x)|\). Right continuity makes this equal to the supremum over rational \(x\), so it is measurable. Symmetrization gives 1
For fixed observations, the vectors \((f(X_1),\ldots,f(X_n))\) as \(f\) varies over half-line indicators take at most \(n+1\) values: ordering the observations shows that the ones are added in successive tied groups. Each normalized coefficient vector has Euclidean norm at most \(1/\sqrt n\). The Rademacher maximum bound from Example 6 of the concentration note therefore gives
Consequently \(\mathbb EG_n\leq2\sqrt{2\log(2(n+1))/n}\leq4\sqrt{\log(n+1)/n}\). Replacing one observation changes \(G_n\) by at most \(1/n\). The one-sided McDiarmid inequality yields \(\mathbb P(G_n\geq\mathbb EG_n+t)\leq e^{-2nt^2}\). This is stronger than the displayed bound (5), since its baseline \(8\sqrt{\log(n+1)/n}\) is larger and \(e^{-2nt^2}\leq e^{-nt^2/2}\). Finally, for any fixed \(\eta>0\), the baseline is eventually below \(\eta/2\), so (5) bounds \(\mathbb P(G_n>\eta)\) by a summable exponential sequence. Borel–Cantelli for \(\eta=1/r\), followed by a countable intersection, proves almost-sure uniform convergence. ◻
This clearly then implies the Glivenko-Cantelli theorem by Borel-Cantelli.
We return to the study of the uniform law of large numbers in Section Uniform Laws via Entropy and Symmetrization.
1.2. Covering
Another way of looking at complexity of a function class is via covering numbers. For a set \(\Theta\) equipped with a metric \(d\), let \(\Theta \subset \overline \Theta\) such that \(d(\cdot,\cdot)\) is defined on \(\overline \Theta\). We say a set \(\{\theta_1, \dots, \theta_N\} \subset \overline \Theta\) is an \(\varepsilon\)-cover for \(\Theta\) is, for all \(\theta \in \Theta\), there exists some \(j \in \{1, \dots, N\}\) such that \(d(\theta,\theta_j) \leq \varepsilon\). Correspondingly, the \(\varepsilon\)-covering number for \(\Theta\) is the smallest \(N\) such that \(\{\theta_1, \dots, \theta_N\}\) is an \(\varepsilon\)-cover for \(\Theta\), formally written as
We say \(\Theta\) is totally bounded if \(N(\varepsilon, \Theta, d)\) is finite for all \(\varepsilon > 0\).
In addition to looking at covering, we could also look at packing. An \(\varepsilon\)-packing of a set \(\Theta\) (with respect to metric \(d\)) is a set \(\{\theta_1, \dots, \theta_D\} \subset \Theta\) such that for all \(i \neq j\), \(i,j \in \{1,\dots,D\}\), \(d(\theta_i, \theta_j) > \varepsilon\). Corresponding, the \(\varepsilon\)-packing number of \(\Theta\) is the maximum number \(D\) such that \(\{\theta_1, \dots, \theta_D\}\) is an \(\varepsilon\)-packing of \(\Theta\), formally written as
By definitions, we can understand the covering number as the minimum number of \(\varepsilon\)-balls required to cover \(\Theta\). And, we can understand the packing number as the maximum number of \(\varepsilon\)-separated points in \(\Theta\). Neither of these quantities need to be finite. The next inequalities show that covering and packing numbers measure the same size, up to a change of scale.
Lemma 8. For any \(\varepsilon > 0\),
We can view this as a form of duality: the packing number is defined in terms of a supremum, but the covering number is defined in terms of an infimum.
Proof. If \(D(\varepsilon,\Theta,d)<\infty\), a packing of largest cardinality exists because its possible finite sizes are integers with a finite supremum. Such a packing covers \(\Theta\) by closed \(\varepsilon\)-balls: otherwise an uncovered point could be added. Therefore \(N(\varepsilon)\leq D(\varepsilon)\). If \(D(\varepsilon)=\infty\), that inequality is automatic in the extended sense.
For the other inequality, take any finite \(\varepsilon\)-cover and any \(2\varepsilon\)-packing. Each covering ball contains at most one packing point, because two points in the same ball have distance at most \(2\varepsilon\), contrary to strict separation. Thus every such packing has size at most the cover's size. Taking the supremum of packing sizes and then the minimum cover size proves \(D(2\varepsilon)\leq N(\varepsilon)\). If there is no finite cover, the inequality is automatic. These arguments also apply to pseudometrics and to covers whose centers lie in an ambient space. ◻
Example 9. We can explicitly bound the covering number in some examples. In \(\mathbb R^d\), let \(B^d_2\) denote the Euclidean ball with respect to the Euclidean distance. Clearly, for \(\varepsilon \geq 1\), \(N(\varepsilon, B^d_2, \lVert \cdot \rVert) = 1\): the singleton \(\{0\}\) constitutes the desired \(\varepsilon\)-cover.
For the case \(\varepsilon \in (0,1)\), we appeal to the volume argument to construct some desired bounds on the covering number. A packing gives disjoint small balls inside a slightly enlarged ball, so volume bounds its size. A cover gives a union containing the original ball, so volume bounds the number of balls from below. When we “overcover”, the sum of the volumes of these balls serve as an upper bound for the volume of the Euclidean ball, thereby giving us a lower bound on \(N(\varepsilon, B^d_2, \lVert \cdot \rVert)\).
The formal descriptions are as follows. In the following, let \(\lambda\) denote the Lebesgue measure on \(\mathbb R^d\). By an abuse of notation again, writing \(D = D(2\varepsilon, B^d_2, \lVert \cdot \rVert)\), suppose \(\{\theta_1, \dots, \theta_D\}\) is the maximal \(2\varepsilon\)-packing of \(B^d_2\). Since \(\lVert \theta - \widetilde\theta \rVert > 2\varepsilon\) for all \(\theta, \widetilde\theta \in D\) such that \(\theta \neq \widetilde\theta\), the balls \(\{B_\varepsilon (\theta) : \theta \in D\}\) must be disjoint. Meanwhile, it must be that \(B_\varepsilon (\theta)\) must be contained in \(B_{1+\varepsilon}(0)\) if \(\theta \in B^d_2\). Therefore, we have the inequality
By the scaling properties of the Lebesgue measure, we have \(\lambda(B_\varepsilon (t)) = \varepsilon^d \lambda(B_1(0))\). As such, we must have
Because this holds for every \(2\varepsilon\)-packing, we’ve shown an upper bound of \(\left( \frac{3}{2\varepsilon} \right)^d\) for \(\varepsilon < \frac12\). The lower bound follows from an analogous argument: if \(N\) is an \(\varepsilon\)-cover for \(B^d_2\), then an identical argument via properties of the Lebesgue measure means that we have
Applying Lemma 8, this means we have
for \(\varepsilon \in (0,1)\).
For the upper covering bound in Example 9, apply the displayed packing estimate at radius \(\varepsilon/2\): \(N(\varepsilon)\leq D(\varepsilon)\leq(1+2/\varepsilon)^d\leq(3/\varepsilon)^d\) for \(0<\varepsilon<1\). This specifies the scale change in Lemma 8.
Remark 10 (Bounded need not mean totally bounded). For \(b>0\), let \(\mathscr C([0,1],b)\) be the convex functions on \([0,1]\) with sup-norm at most \(b\). Define
Each function is continuous and convex, has values in \([0,b]\), and is linear from \((0,b)\) to \((2^{-j},0)\) before remaining zero. If \(j<k\), evaluation at \(x=2^{-(j+1)}\) gives \(f_j(x)=b/2\) and \(f_k(x)=0\). Thus every pair of distinct functions is at least \(b/2\) apart in sup-norm. A ball of radius less than \(b/4\) contains at most one of them, so no finite collection of such balls covers the class. For \(b=0\), the class consists only of the zero function and is totally bounded.
Example 11 (Boolean hypercube). Let \(\mathbb H^d = \{-1,1\}^d\) denote the \(d\)-dimensional hypercube. Define the rescaled Hamming metric
For \(0\leq\varepsilon\leq1\), to derive an upper bound on the \(\varepsilon\)-covering number, construct the set \(S = \{1, 2, \dots, \lceil (1-\varepsilon)d \rceil\}\). Then, denote \(U(\varepsilon) \triangleq \{\theta \in \mathbb H^d : \theta_i = 1 \:\: \text{for all } i \notin S\}\). Therefore, for any \(\theta \in \mathbb H^d\), there exists a \(\widetilde \theta \in U(\varepsilon)\) such that \(d_H (\theta, \widetilde \theta) \leq \varepsilon\). It then follows that
A more precise argument is as follows: suppose there is already an \(\varepsilon\)-packing. Then, \(\frac{\varepsilon}{2}\)-balls do not intersect. Hence, the total number of elements in the union of those balls is at most \(2^d\). By setting \(\widetilde\varepsilon \triangleq \frac2d \lfloor \frac{\varepsilon d}{2} \rfloor \leq \varepsilon\), we have
which is true if and only if
where \(Z_d\) is the sum of \(d\) many \(\operatorname{Ber}(\frac12)\) random variables. It then follows from the lower bound on binomial tails that
where
is the Kullback-Leibler divergence between Bernoulli distributions with parameter \(\frac{\varepsilon}{2}\) and \(\frac12\).
Here is the binomial lower bound used above. Put \(r=\lfloor\varepsilon d/2\rfloor\) and \(p=r/d=\widetilde\varepsilon/2\). For \(0<r<d\), the term at \(r\) is a mode of the \(\operatorname{Bin}(d,p)\) mass function (compare consecutive mass ratios), and hence is at least \(1/(d+1)\). It follows that
The endpoint \(r=0\) follows directly from probability \(2^{-d}\), with \(0\log0=0\). Insert this lower bound into the reciprocal packing bound to obtain the displayed KL estimate. The closed Hamming balls used there are disjoint because their integer radii sum to \(2r\leq\varepsilon d\), while packing distances are strictly greater than \(\varepsilon d\).
The following result is derived using the arguments of the Varshamov-Gilbert lemma.
Lemma 12. Let \(N\ge2\), let \(2\le s\le d\) be even, and put \(U=\{u\in\{0,1,\ldots,N-1\}^d:\|u\|_0=s\}\). For the normalized Hamming metric \(d_H(u,v)=d^{-1}\sum_i\mathbf1\{u_i\ne v_i\}\), set \(D=D(s/(2d),U,d_H)\). If \(s\le Nd/25\), then
When \(N=3\) and \(s\le d/8\), the following bound also holds:
Proof. Write \(H=dd_H\) for the unnormalized number of differing coordinates. A closed \(H\)-ball of radius \(s/2\) has at most \(\binom d{s/2}N^{s/2}\) points, even before restricting to \(U\): choose a set of \(s/2\) coordinates containing all changes and assign their values. A maximal packing with pairwise \(H\)-distance greater than \(s/2\) covers \(U\) by these balls. Equivalently, whenever their union does not cover \(U\), an uncovered point has distance greater than \(s/2\) from every selected point and can be added. Hence
Here we used \(\binom ds\ge(d/s)^s\) and \(\binom d{s/2}\le(2ed/s)^{s/2}\). Since \((1-1/N)^2\ge1/4\), writing \(R=Nd/s\ge25\) gives \(\log D\ge(s/2)\log(R/(8e))\ge(s/64)\log R\); the last inequality follows from \(25>(8e)^{32/31}\).
For the final assertion use the sharper factor \((1-1/3)^2=4/9\). With \(q=d/s\ge8\), the same bound gives \(\log D\ge(s/2)\log(2q/(3e))\). The inequality \(32\log(2q/(3e))\ge\log(eq)\) holds at \(q=8\) and its left side minus its right side increases with \(q\). This proves the stated consequence without invoking the incompatible condition \(3d/s\ge25\) at its endpoint. □
In (6), \(\mathbb E_\varepsilon\) integrates the signs with the observations fixed; \(\mathbb E_X\) then integrates the observations. Their composition is the joint expectation, by independence and Tonelli. The absolute value remains inside the supremum. ↩︎