Uniform Laws via Entropy and Symmetrization
Uniform convergence requires the largest empirical error over a function class to vanish. A finite cover separates this error into approximation within the cover and fluctuation at the centers. Symmetrization lets us measure the latter by correlation with random signs. We will use these two descriptions to give sufficient conditions for a uniform law and to examine classes that can fit random signs too well.
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.
We now apply the maximal inequalities to prove a uniform law of large numbers. In particular, we can look at the phenomenon through empirical (metric) entropy. As always, we need to place some kind of restrictions on the function class \(\mathcal F\) we consider. The first result applies when \(\mathcal F\) is the class of uniformly bounded functions.
Lemma 1 (ULLN for uniformly bounded function classes). Let \(\mathcal F\) be a function class of uniformly bounded functions, i.e. \(\sup_{f \in \mathcal F} \lVert f \rVert_\infty \leq R < \infty\). Suppose the following \(L^2\) random entropy condition holds:
Then, \(\mathcal F\) satisfies the uniform law of large numbers.
Proof. We prove convergence in mean first. Given the observations, let \(g_1,\ldots,g_N\) be an internal \(\varepsilon\)-net in \(L^2(P_n)\), where \(N=N(\varepsilon,\mathcal F,L^2(P_n))\). Cauchy–Schwarz gives, for every sign vector,
Each net point has empirical norm at most \(R\). The Rademacher mgf bound and the finite-class log-sum-exp inequality therefore give
The entropy hypothesis makes the second term converge in probability to \(\varepsilon\), while \(0\le R_n(X)\le R\). Boundedness converts this to \(\limsup_n\mathbb E R_n(X)\le\varepsilon\): split the expectation according to \(R_n(X)>\varepsilon+u\), and then let \(u\downarrow0\). Since \(\varepsilon>0\) is arbitrary, \(\mathbb E R_n(X)\to0\). Symmetrization yields \(\mathbb E D_n\le2\mathbb E R_n(X)\to0\), where \(D_n=\|P_n-P\|_{\mathcal F}\).
Changing one observation changes \(D_n\) by at most \(2R/n\). Thus, for \(t>0\),
For each fixed rational \(t>0\), this series is summable. Borel–Cantelli and \(\mathbb E D_n\to0\) imply \(D_n\to0\) almost surely. The case \(R=0\) is immediate. No almost-sure limit is assumed at the start. ◻
The bounded result gives a sufficient empirical-entropy condition for integrably enveloped classes by truncation.
Proposition 2. Suppose the following \(L^1\) random entropy condition holds:
and that \(\int F \dif P < \infty\), where \(F\) is the envelope function of \(\mathcal F\). Then, \(\mathcal F\) satisfies the uniform law of large numbers.
Proof. For an integer \(M\ge1\), set \(\mathcal F_M=\{f1\{F\le M\}:f\in\mathcal F\}\). For \(f,g\in\mathcal F\),
Truncating the centers of an \(L^1(P_n)\) net consequently gives
Lemma 1 applies to every \(\mathcal F_M\). On a common event of probability one, its uniform law and the scalar strong law for \(F1\{F>M\}\) hold for every integer \(M\). On this event,
Let \(M\to\infty\). Integrability of \(F\) makes the right side vanish. The probability-one event is chosen before this limit, so the conclusion concerns all sufficiently large sample sizes, rather than a single random sample size. ◻
Remark 3 (necessity, with the measurability assumptions above). Suppose \(\sup_fP|f|<\infty\) and \(D_n\to0\) almost surely. The minimal envelope \(F=\sup_f|f|\) must then be integrable. Indeed, put \(F_0=\sup_f|f-Pf|\). For \(n\ge2\),
The events \(\{F_0(X_n)>n\}\) are independent. The converse Borel–Cantelli lemma implies \(\sum_nP(F_0>n)<\infty\), hence \(PF_0<\infty\). Since \(F\le F_0+\sup_f|Pf|\), we obtain \(PF<\infty\). An arbitrarily enlarged envelope need not be integrable; the assertion concerns the minimal envelope, or an integrable envelope chosen in its place.
For necessity of the entropy condition, use the converse Glivenko–Cantelli theorem, Wellner’s Delft notes, Theorem 6.2, p. 36: the empirical \(L^2\) entropy divided by \(n\) tends to zero for every bounded truncation \(\mathcal F_M\). To pass to the original \(L^1\) entropy, choose \(M\) with \(PF1\{F>M\}<\varepsilon/8\). Eventually \(P_nF1\{F>M\}<\varepsilon/4\) almost surely. Lift the centers of an \(\varepsilon/4\)-net for \(\mathcal F_M\) to their original functions; their \(L^1(P_n)\) errors are at most \(\varepsilon/4+2P_nF1\{F>M\}<\varepsilon\). Thus the truncated converse implies the asserted full \(L^1\) entropy condition. This necessity argument uses the converse theorem, not Lemma 1 alone.
The next lemma is not used above. It is the chaining tail bound behind an alternative proof of Lemma 1, by symmetrization and Hoeffding’s inequality, and is recorded for reference.
Lemma 4 (truncated chaining tail bound). Fix the observations and let \(d_n(f,g)=\|f-g\|_{P_n,2}\), with \(\sup_f\|f\|_{P_n,2}\le R\), \(R>0\). Suppose a random multiplier vector \(\xi\) satisfies
Let \(K>0\), \(0\le\varepsilon<\eta\), and put \(I=\int_{\varepsilon/(4K)}^R\sqrt{\log N(u,\mathcal F,d_n)}du\) when \(\varepsilon/K<R\). There is \(C=C(C_1,C_2)\) such that if
then
If \(\varepsilon/K\ge R\), the probability is zero by Cauchy–Schwarz. Rademacher signs satisfy the assumptions with \(C_1=2\), \(C_2=\sqrt2\), and \(K=1\).
Proof. First assume \(0<\varepsilon/K<R\). Put \(r_s=R2^{-s}\) and take the first \(S\) with \(r_S\le\varepsilon/K\). Choose internal nets \(T_s\) of sizes \(N_s=N(r_s,\mathcal F,d_n)\), and for each \(f\) choose \(\pi_sf\in T_s\) within \(r_s\). Set \(\pi_0f=0\). The first increment satisfies \(\|\pi_1f\|_{P_n,2}\le R\le3r_1\); later increments have norm at most \(r_s+r_{s-1}=3r_s\). This explicit zero base point is needed for the identity
There are at most \(N_s^2\) possible increments at level \(s\), since the covering counts are nondecreasing along the sequence. For \(u\ge1\), apply the assumed tail bound at threshold
to \(n^{-1/2}\sum_i\xi_i(\pi_sf-\pi_{s-1}f)(X_i)\). A union bound over increments and levels gives failure probability at most
On the complementary event, the normalized process at every finest net point is bounded by \(\sum_sb_s\). By monotonicity of covering numbers,
The last inequality uses \(r_S>\varepsilon/(2K)\). Also \(\sum_sr_s\sqrt s\le R\sum_s s2^{-s}=2R\). Therefore \(\sum_sb_s\le C_0(I+R\sqrt u)\), for a constant depending only on \(C_2\). On the event \(P_n\xi^2\le K^2\), the discarded remainder is at most \(K d_n(f,\pi_Sf)\le\varepsilon\). We have proved
Choose \(u=n(\eta-\varepsilon)^2/(4C_0^2R^2)\). Increasing the constant in (3) ensures \(u\ge1\) and \(C_0I/\sqrt n\le(\eta-\varepsilon)/2\), proving the stated bound. For \(\varepsilon=0\), use all levels and let \(S\to\infty\); the remainder is bounded by \(Kr_S\to0\), and the same series and integral estimates apply. If the required entropy integral is infinite the hypothesis cannot hold. ◻
We now look at a series of examples.
Lemma 5 (weighted monotone classes). Let \(\widetilde{\mathcal F}\) be a class of increasing functions \(\mathbb R\to[-1,1]\), let \(F\) be measurable, and put \(\mathcal F=\{Fh:h\in\widetilde{\mathcal F}\}\). For \(1\le p<\infty\), \(\|F\|_{Q,p}<\infty\), and \(\varepsilon>0\),
The constant may depend on \(p\). If \(P|F|<\infty\), the class satisfies the strong uniform law.
Proof. Use the standard monotone bracketing theorem: bounded monotone functions have \(L^p(Q)\) bracketing entropy at most \(C_p/\varepsilon\), uniformly over probability measures \(Q\). This is the external input in Wellner’s Delft notes, Theorem 9.4, p. 71 (van der Vaart–Wellner, Theorem 2.7.5).
Set \(A=\|F\|_{Q,p}\). If \(A=0\), the class is zero \(Q\)-almost everywhere and one bracket suffices, with width zero in \(L^p(Q)\). Otherwise define \(d\widetilde Q=|F|^pA^{-p}dQ\). A bracket \([l,u]\) for the monotone class induces endpoints \(\min(Fl,Fu)\) and \(\max(Fl,Fu)\); this reversal where \(F<0\) preserves their pointwise order. Its width has norm
Choose monotone brackets of width \(\varepsilon/A\) and apply the external bound. The strong uniform law follows by taking \(p=1\): finitely many \(L^1(P)\) brackets exist at every positive width, and the finite-bracket strong-law argument in the symmetrization note applies. ◻
Example 6 (Sobolev classes). For a fixed integer \(k\ge1\), let \(\mathcal F\) consist of functions on \([0,1]\) whose derivatives through order \(k-1\) have the usual absolutely continuous Sobolev representatives, with \(\|f\|_\infty\le1\) and \(\|f^{(k)}\|_2\le1\). Then
The external Sobolev entropy theorem bounds sup-norm covering entropy of a bounded \(W^{k,2}([0,1])\) ball by this order; see Wellner, Theorem 9.2, p. 70. Here its condition \(2>1/k\) holds, and \(\|f\|_2+\|f^{(k)}\|_2\le2\). A sup-norm cover with centers \(g_j\) and radius \(\varepsilon/2\) gives brackets \([g_j-\varepsilon/2,g_j+\varepsilon/2]\); taking slightly smaller radii accommodates strict-width conventions. This explains the passage from covering to bracketing and the dependence of the constant on \(k\).
Example 7 (bounded variation). For monotone functions \(\mathbb R\to[-1,1]\), Lemma 5 with \(F=1\), \(p=2\) gives \(\log N_{[\:]}(\varepsilon,L^2(P))\le C/\varepsilon\). A monotone class is only one subclass of bounded variation. The same order holds for all \(f\) with \(|f|\le1\) and total variation at most one.
To see this, use the Jordan decomposition \(f=c+u-v\), where \(c=f(-\infty)\in[-1,1]\) and \(u,v\) are increasing, take values in \([0,1]\), and start at zero. Bracket \(u,v\) at width \(\varepsilon/3\) and cover \(c\) by intervals of length \(\varepsilon/3\). The endpoints \(c^L+u^L-v^U\) and \(c^U+u^U-v^L\) give a bracket of width at most \(\varepsilon\). Taking logarithms of the product count gives \(C/\varepsilon+\log(C/\varepsilon)\le C'/\varepsilon\) for small \(\varepsilon\). Since \(\int_0^1\varepsilon^{-1/2}d\varepsilon<\infty\) and the envelope is bounded, the bracketing Donsker theorem applies for every probability law \(P\).
Example 8 (smooth functions on an unbounded domain). Partition \(\mathbb R^d\) into unit cubes \(I_j\). Suppose each restriction belongs to a Hölder ball of smoothness \(\alpha=s+\beta\), with integer \(s\ge0\), \(0<\beta\le1\), and radius \(M_j\). This means derivatives through order \(s\) are bounded by \(M_j\) and derivatives of order \(s\) have \(\beta\)-Hölder seminorm at most \(M_j\). It includes the bound on the function itself. For \(1\le r<\infty\), \(V\ge d/\alpha\), and \(S=\sum_j(M_j^rP(I_j))^{V/(V+r)}<\infty\),
Here is the allocation argument behind the bound. On a unit cube the Hölder entropy theorem gives at most \(\exp(Cu^{-V})\) brackets of uniform width \(uM_j\) for \(0<u<2\); for \(u\ge2\), the single bracket \([-M_j,M_j]\) suffices. See Wellner, Theorem 9.1 and Corollaries 9.1–9.2, pp. 69–71 for this local entropy input. Put \(b_j=M_j^rP(I_j)\) and, when \(b_j>0\), choose
The combined bracket has \(r\)-th power width at most \(\sum_jb_ju_j^r=\varepsilon^r/2^r\). Only finitely many \(u_j<2\), because \(\sum_jb_j^{V/(V+r)}<\infty\); therefore the product of the nontrivial bracket counts is finite. Its logarithm is at most
Cubes with \(b_j=0\) require only a zero-width-in-\(L^r(P)\) bracket, and \(S=0\) is immediate. For \(r=2\) and \(V<2\), finiteness of \(S\) also implies a square-integrable envelope, and the entropy integral is finite. The class is then \(P\)-Donsker by the bracketing theorem.
1. Uniform Law of Large Numbers Via Symmetrization
We can also obtain the uniform law through analyzing quantities that decide the behaviour of uniformity. An important quantity that underlies the study of uniform laws is the Rademacher complexity of the function class \(\mathcal F = \{f : \mathscr X \to \mathbb R\}\) considered. It turns out we ought to look at the following construction: let
for some \(x = (x_1, \dots, x_n) \in \mathscr X^n\). Based on this, we define the empirical Rademacher complexity as
where \(\varepsilon_1, \dots, \varepsilon_n\) are i.i.d. Rademacher random variables. The deterministic quantity from taking the expectation of \(\mathcal R(\cdot)\), i.e.
is called the Rademacher complexity of the function class \(\mathcal F\). Analyzing this quantity is one of the ways we can obtain the uniform law. The broad heuristic is as follows: a function class has high empirical complexity if we can always find a function that has a high correlation with a randomly drawn noise vector. Conversely, when the Rademacher complexity decays as a function of sample size, then it is impossible to find a function that correlates very highly in expectation with a randomly drawn noise vector. Ideally, we’d want a tight control on the upper bound of the Rademacher complexity. The reason is as follows.
Theorem 9 (Uniformly bounded function class: upper bound on Rademacher complexity). For any \(c\)-uniformly bounded class of functions \(\mathcal F\), any positive integer \(n \in \mathbb N\), and any scalar \(\delta \geq 0\), we have
with \(\mathbf P\,\,\!\!\)-probability at least \(1 - e^{-\frac{n\delta^2}{2c^2}}\). Consequently, if \(\mathcal R_n (\mathcal F) = o(1)\), \(\lVert \widehat P_n - \mathbf P\,\,\!\!\rVert_{\mathcal F} \xrightarrow{\rm a.s.} 0\).
To prove this result, we need a preliminary lemma.
Lemma 10 (Convex functions and supremum of random variables). For any function \(f \in \mathcal F\) (any function class), \(\sup_{f \in \mathcal F} \mathbb{E} f(X) \leq \mathbb{E} \sup_{f \in \mathcal F} |f(X)|\). If \(\Phi\) is any nondecreasing and convex function, then \(\sup_{f \in \mathcal F} \Phi (\mathbb{E} f(X)) \leq \mathbb{E} \Phi( \sup_{f \in \mathcal F} |f(X)| )\).
Proof. First, because \(f(X) \leq |f(X)| \leq \sup_{f \in \mathcal F} |f(X)|\) for all \(f \in \mathcal F\), it follows that \(\mathbb{E} f(X) \leq \mathbb{E} \sup_{f \in \mathcal F} |f(X)|\). Taking supremum on both sides yields the desired result. For the second result, since \(\Phi\) is assumed to be nondecreasing, we have
for any \(f \in \mathcal F\). Note the final quantity on the rightmost side is deterministic. And, by the convexity of \(\Phi\), we apply Jensen’s inequality to find that \(\sup_{f \in \mathcal F} \Phi (\mathbb{E} f(X)) \leq \mathbb{E} \Phi (\sup_{f \in \mathcal F} |f(X)|)\), as desired. ◻
Proof of Theorem 9. Put \(D_n=\sup_f|n^{-1}\sum_i(f(X_i)-Pf)|\). If \(x,\widetilde x\) differ only in coordinate \(i\), the supremum inequality \(|\sup a_f-\sup b_f|\le\sup|a_f-b_f|\) and cancellation of \(Pf\) give
McDiarmid's inequality therefore yields \(P(D_n>\mathbb ED_n+t)\le e^{-nt^2/(2c^2)}\) for \(t>0\). No maximizer needs to exist. To bound the mean, take an independent sample \(Y_1,\ldots,Y_n\). Conditional Jensen gives
Swapping \(X_i,Y_i\) whenever an independent sign is negative preserves the joint law of the entire process indexed by \(f\). Thus the last expectation equals the same expression with each difference multiplied by \(\varepsilon_i\). The triangle inequality then bounds it by
Combining the mean and concentration bounds proves the assertion. If \(\mathcal R_n\to0\), then for each rational \(t>0\), eventually \(2\mathcal R_n<t/2\), and \(\sum_nP(D_n>t)<\infty\). Borel–Cantelli proves almost-sure convergence. If \(c=0\), every quantity vanishes. ◻
Now, a natural question is: Theorem 9 guarantees an upper bound on the Rademacher complexity; is there a lower bound to be obtained, at least in the class of \(c\)-uniformly bounded functions? The answer is yes.
Theorem 11 (lower bound on the uniform empirical error). For a measurable class with \(|f|\le c\), \(c>0\), and \(\delta\ge0\), with probability at least \(1-e^{-n\delta^2/(2c^2)}\),
Together with Theorem 9, this implies that a uniformly bounded class obeys the strong uniform law if and only if \(\mathcal R_n(\mathcal F)\to0\).
We need a preliminary step in order to establish the lower bound of Rademacher complexity.
Lemma 12. For all convex, nondecreasing real-valued function \(\Phi : \mathbb R \to \mathbb R\), we have
where \(\mathbb S_n f \triangleq \frac1n \sum_{1 \leq k \leq n} \varepsilon_k f(X_k)\) and \(\overline{\mathcal F} \triangleq \{ f - \mathbb{E} f : f \in \mathcal F \}\).
Proof. Write \(D(X)=\|P_n^X-P\|_{\mathcal F}\) and \(S(X,\varepsilon)=\|\mathbb S_n\|_{\mathcal F}\), and let \(Y\) be an independent copy of the sample. Conditional Jensen, swapping pairs using the signs, and the triangle inequality give
For the reverse direction, replace each \(Pf\) in \(\mathbb S_n(f-Pf)\) by the conditional expectation of \(f(Y_i)\), and use conditional Jensen again. Swapping the pairs removes the signs. Consequently,
The suprema and the nondecreasing convex function preserve each conditional Jensen inequality. Integrability is automatic for the bounded classes used here; otherwise the inequalities are understood when the expectations exist, or for nonnegative extended expectations. ◻
Proof of Theorem 11. Set \(m=\sup_f|Pf|\). Pointwise in \((X,\varepsilon)\),
Only after taking expectations may we use \(\mathbb E|\sum_i\varepsilon_i|\le\sqrt n\), which follows from Cauchy–Schwarz and independence. Lemma 12 with \(\Phi(t)=t\) therefore gives
Apply the lower-tail version of the bounded-differences inequality for \(D_n\) to obtain the asserted probability bound. If the strong uniform law holds, \(0\le D_n\le2c\) implies \(\mathbb ED_n\to0\) by dominated convergence, and the last display implies \(\mathcal R_n\le2\mathbb ED_n+m/\sqrt n\to0\). The converse is Theorem 9. ◻
Example 13 (finite subsets and failure of the uniform law). Let \(P\) be uniform on \([0,1]\) and \(\mathcal F=\{1_S:S\subset[0,1],\ S\text{ finite}\}\). Every \(S\) has \(P(S)=0\), but the set of all observed sample points has empirical mass one. Thus
For distinct sample points, a finite set can include precisely the observations whose signs are positive, or precisely those whose signs are negative. Hence
Distinctness holds almost surely, so \(\mathcal R_n=1/2+\mathbb E|\sum_i\varepsilon_i|/(2n)\ge1/2\). These explicit formulas establish measurability of the suprema and directly prove failure of the uniform law. A vacuous upper bound alone would not prove failure.
Example 14 (Linear classifiers). Let \(\mathcal F=\{x\mapsto\operatorname{sign}\langle\theta,x\rangle:\theta\in\mathbb R^d,\ \|\theta\|_2=1\}\), with any fixed convention for the sign at zero. Suppose \(n\le d\) and \(x_1,\ldots,x_n\in\mathbb R^d\) are linearly independent. Form the matrix with these vectors as rows,
The row rank is \(n\), so \(AA^\top\) is invertible. Given any sign vector \(\varepsilon\in\{-1,1\}^n\), choose \(\beta=A^\top(AA^\top)^{-1}\varepsilon\). Then \(A\beta=\varepsilon\) and \(\beta\ne0\). The unit vector \(\theta=\beta/\|\beta\|_2\) therefore satisfies \(\operatorname{sign}\langle\theta,x_i\rangle=\varepsilon_i\) at every sample point. Consequently,
The lower bound follows by using the interpolating classifier; the upper bound follows because each summand has absolute value one. Thus this sample can realize every labeling and the empirical complexity bound is vacuous. This shows the capacity to fit noise when the design has full row rank; it does not assert that every data distribution or every fitting rule must generalize poorly.