Maximal Inequalities via Uniform Entropy and Bracketing
Symmetrization turns an empirical process into a random-sign process. Conditional on the observations, that process has subgaussian increments in the empirical quadratic norm, so chaining applies. There are two ways to make the resulting bound usable: control covering numbers uniformly over empirical measures, or use brackets measured under the population law. The latter route requires additional control of the pointwise approximation errors.
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 apply the preceding maximal inequalities to the empirical process
where \(\mathcal F\) is some function class. For any such function class defined on \(\mathscr X\), and specifically real-valued functions, the following object will be useful. The \(L^2(\widehat P_n)\)-seminorm defined for all \(f \in \mathcal F\) has the following formula:
To investigate if a function class is large or small, it makes sense to want to link the idea of the entropy integral to the function class somehow. For example, suppose \(\mathcal F\) is a (measurable) uniformly bounded class of functions; we should be able to control the behaviour of \(\lVert \mathbb G_n \rVert_{\mathcal F}\) via its uniform bound (i.e. by the envelope of \(\mathcal F\)) times some potentially large “constants”. An envelope controls the size of each function but does not limit how many different functions can fit the sample. We therefore also need a restriction on the size of the class. We should at least expect the metric entropy (and therefore the covering number) to be finite. The conditional metric depends on the sample. Taking a supremum over discrete probability measures removes that dependence from the entropy bound. It’s referred to as the uniform entropy condition.
Suppose a function class \(\mathcal F\) has a measurable envelope function \(F\). Add the constant function \(f \equiv 0\) to \(\mathcal F\). Define the uniform entropy integral as
for any \(\delta > 0\). Here, the supremum is taken over all discrete probability measures \(R\) on \(\mathscr X\) (with finitely many nonzero values), with \(\lVert F \rVert_{R,2} = (\int F^2 \dif R)^{1/2} > 0\). The uniform entropy condition is (checking whether) \(J(1, \mathcal F, F) < \infty\). For this condition to have the possibility of holding true, \(\mathcal F\) must have finite covering number for all \(\varepsilon > 0\). That is not quite enough, since the integral can still diverge at zero. Therefore, we need to look at the behaviour as \(\varepsilon \to 0\) in the definition of the integral. We first show how this condition bounds the expected supremum; examples of classes satisfying it come later.
Assume throughout that the classes are pointwise measurable and their displayed envelopes have finite second moments, unless a different moment condition is stated. Equivalently, one may use outer expectations and the usual empirical-process measurability conventions. Define \(m_n=0\) if \(P_nF^2=0\); all sample function values then vanish.
Theorem 1. Suppose \(\mathcal F\) is a function class with a measurable envelope function \(F\). Then, for \(m_n \triangleq \sup_{f \in \mathcal F} \frac{\lVert f \rVert_{\widehat P_n, 2}}{\lVert F \rVert_{\widehat P_n, 2}}\),
Remark 2. Since \(m_n \leq 1\), the second inequality makes sense. Two random quantities remain after conditioning on the data. First, \(m_n\) is random, as it is expressed in terms of the \(L^2(\widehat P_n)\) seminorm. Second, \(\lVert F \rVert_{\widehat P_n, 2}\) is random, so it is unclear how to a priori bound it above by \(\lVert F \rVert_{\mathbf P\,\,\!\!, 2}\).
Proof of Theorem 1. Put \(Z_n(f)=n^{-1/2}\sum_i\varepsilon_i f(X_i)\). The ghost-sample symmetrization inequality gives
Conditional on the data, the Rademacher mgf bound gives, with \(d_n(f,g)=\|f-g\|_{P_n,2}\),
If \(d_n(f,g)=0\), the increment is identically zero. Adjoin the zero function and let \(s_n=\sup_f\|f\|_{P_n,2}\). The conditional diameter is at most \(2s_n\). Conditional Dudley chaining therefore gives
The last inequality uses the nonincreasing integrand. Rescale \(u=v\|F\|_{P_n,2}\) and use \(R=P_n\) in the uniform supremum. The result is bounded by \(2\|F\|_{P_n,2}J(m_n,\mathcal F,F)\). Taking expectations proves the first assertion. Finally \(m_n\le1\) and Jensen give \(\mathbb{E}\sqrt{P_nF^2}\le\sqrt{PF^2}\), proving the second. ◻
Remark 3 (Revisiting Remark 6 of the symmetrization note). Suppose \(|f|\le M\), and for all finitely supported probability measures \(R\) and \(0<\varepsilon\le1\),
Then \(J(1)\lesssim\sqrt{v\log A}\), because \(\int_0^1\sqrt{\log(1/u)}du<\infty\). Theorem 1 gives
The entropy assumption must hold for empirical measures as well as for the population measure. A bound only in \(L^2(P)\) would not justify the conditional chaining step.
A result that may be useful if we know information about \(\lVert F \rVert_{\mathbf P\,\,\!\!, 2}\) is the following.
Theorem 4. Suppose \(0 < \lVert F \rVert_{\mathbf P\,\,\!\!, 2} < \infty\), and let \(\sigma^2 > 0\) be any positive constant such that \(\sup_{f \in \mathcal F} P f^2 \leq \sigma^2 \leq \lVert F \rVert_{\mathbf P\,\,\!\!, 2}^2\). Set \(\delta = \frac{\sigma}{\lVert F \rVert_{\mathbf P\,\,\!\!, 2}}\) and \(M = \sqrt{\mathbb{E} \sup_{1 \leq k \leq n} F(X_k)^2}\). Then,
Proof. Write \(A=\|F\|_{P,2}\), \(B=(P_nF^2)^{1/2}\), \(S=\sup_f(P_nf^2)^{1/2}\), \(M_n=\max_iF(X_i)\), and
Conditional chaining, as in Theorem 1, gives \(R_X\leq C B J(S/B)\), with zero assigned when \(B=0\). Assume \(J(\delta)<\infty\); otherwise the claimed bound is automatic. The function \(J\) is increasing and concave, with \(J(0)=0\), because its integrand is nonnegative and decreasing. Moreover \(\phi(x)=J(\sqrt x)^2\) is concave: at almost every positive \(x=r^2\), its derivative is \((J(r)/r)J'(r)\), a product of two nonnegative decreasing functions. Jensen under the probability measure with density \(B^2/A^2\) therefore yields
This also follows by approximation at any nondifferentiable points. Consequently \((\mathbb ER_X^2)^{1/2}\leq C A J(Q/A)\).
We use the elementary Rademacher contraction inequality \(\mathbb E_\varepsilon\sup_t|\sum_i\varepsilon_i\varphi_i(t_i)|\leq2L\mathbb E_\varepsilon\sup_t|\sum_i\varepsilon_i t_i|\), where each \(\varphi_i(0)=0\) is \(L\)-Lipschitz on the relevant range. Here is a proof: for a finite index set, conditioning on all but one sign replaces its expected supremum by
The last equality uses symmetry in the pair \((s,t)\). Iterating contracts the expected supremum without absolute values. Adjoin zero, bound the absolute supremum by the sum of the positive and negative suprema, and use symmetry of the signs to obtain the factor two. Increasing finite subsets gives the countable version.
Conditionally, squaring is \(2M_n\)-Lipschitz on \([-M_n,M_n]\), so contraction and symmetrization of the squared class give
All quantities are finite because \(S\leq B\), \(PF^2<\infty\), and \(\mathbb EM_n^2=M^2\leq nPF^2\). Put \(z=Q/A\), \(b=CM/(A\sqrt n)\). Then \(z^2\leq\delta^2+bJ(z)\). If \(z\leq\delta\), monotonicity suffices. If \(z>\delta\), concavity gives \(J(z)\leq zJ(\delta)/\delta\); divide the resulting inequality by \(z\) to obtain \(z\leq\delta+bJ(\delta)/\delta\). Thus in either case
Finally \(\mathbb E\|\mathbb G_n\|_{\mathcal F}\leq2\mathbb ER_X\leq C A J(z)\), by symmetrization and the square-moment bound. Substitution gives exactly the two asserted terms. For pointwise measurable classes use their countable determining subclasses; the integrable envelope permits the required dominated limits. ◻
There are maximal inequalities that use bracketing numbers. However, the difficulty here is reversed from earlier: it is easier to use bracketing to prove the Glivenko-Cantelli theorem but much harder to use covering arguments. Here, bracketing results are much more difficult to prove. One of the major difficulties come from the fact that bracketing provides pointwise control: a bracket \([l,u]\) requires \(l \leq u\) pointwise (for all \(x \in \mathscr X\)). In giving up pointwise control, the maximal inequalities using metric entropy were derived by considering all measures \(R\), and taking the supremum over all such \(R\) supported on realizations of \(f(X_1), \dots, f(X_n)\).
For bracketing, write \(\operatorname{Log}x=\max(1,\log x)\). This convention keeps a nonzero bound even for a singleton class. Adding zero to the class is harmless and will be understood in each bracketing integral.
Because we have pointwise control, we can look at the bracketing integral, defined as
The following result, while it looks innocuous, is difficult to prove directly.
Theorem 5. Suppose \(\mathcal F\) is a function class with a measurable envelope function \(F\). Then,
However, we note that Theorem 5 is a straightforward consequence of the following result, which is elementary in its statement but difficult to show.
Theorem 6. Suppose \(Pf^2<\delta^2\) for every \(f\in\mathcal F\), with envelope \(F\). Put
Then, with a universal implicit constant,
The following proof expands the stopped-chain argument in van der Vaart, Asymptotic Statistics, Lemma 19.34, pp. 286–288. The finite-class estimate used below is Lemma 7. Refining bracket partitions changes their cardinalities, and the residual terms require their own empirical-process bound.
Proof of Theorem 6. We may assume \(J_{[\:]}(\delta)<\infty\). Put \(\tau=\sqrt n\,a(\delta)\). The tail part satisfies
For the remaining proof replace each function and its bracket endpoints by their products with \(\mathbf1_{F\leq\tau}\). This does not increase bracket widths, so we may suppose \(|f|\leq F\leq\tau\).
Nested partitions and thresholds. Set \(r_q=4\delta\,2^{-q}\), \(q\geq0\), and let \(N_q\) be the original bracketing number at radius \(r_q\). Turn each finite cover into a disjoint partition of the class, then refine all partitions through level \(q\). There are at most \(K_q=\prod_{j=0}^qN_j\) cells. Within each nonempty refined cell, intersect its ancestral brackets, clipping endpoints to \([-F,F]\). Its width \(\Delta_qf\), constant over that cell as a function of the index \(f\), obeys
Choose a representative \(\pi_qf\) from each cell. Then \(|f-\pi_qf|\leq\Delta_qf\), \(|\pi_qf|\leq F\), and \(P(\pi_qf)^2<\delta^2\). Put \(L_q=1+\sum_{j=0}^q\log N_j\) and \(a_q=r_q/\sqrt{L_{q+1}}\). Since \(N_0,N_1\leq N_{[\:]}(\delta)\), \(L_1\leq3H(\delta)\), so \(a_0\geq4\delta/\sqrt{3H(\delta)}>2a(\delta)\). In particular \(\Delta_0f\leq2F\leq\sqrt n a_0\).
Let \(A_qf\) indicate that all width bounds \(\Delta_jf\leq\sqrt n a_j\), \(0\leq j\leq q\), hold at the point under consideration. Let \(B_qf=A_{q-1}f\,\mathbf1_{\Delta_qf>\sqrt n a_q}\), \(q\geq1\), indicate the first failure. Thus \(A_0f=1\). For every finite \(K\), direct telescoping up to the first failure gives the exact identity
The last term has absolute value at most \(\sqrt n a_K\), so its empirical-process supremum is at most \(2n a_K\to0\) for fixed \(n\). This justifies the infinite decomposition uniformly over the class without interchanging an expectation and a supremum.
Retained increments. The function \(h_qf=(\pi_qf-\pi_{q-1}f)A_{q-1}f\) takes at most \(K_q\) distinct values, has \(|h_qf|\leq\sqrt n a_{q-1}\), and has \(L^2(P)\)-norm at most \(r_{q-1}=2r_q\). Lemma 7 therefore gives
because \(a_{q-1}=2r_q/\sqrt{L_q}\).
Stopped residuals. Majorize \(|(f-\pi_qf)B_qf|\) by \(g_qf=\Delta_qf B_qf\). This majorant has at most \(K_q\) values, \(L^2(P)\)-norm at most \(r_q\), and sup-norm at most \(\sqrt n a_{q-1}\), since widths decrease and the preceding level has not failed. Also
For any \(|h|\leq g\), \(|\mathbb G_nh|\leq\sqrt n(P_n+P)g=\mathbb G_ng+2\sqrt n Pg\). Consequently Lemma 7 applied to the finite class of majorants gives
This bound retains the empirical fluctuation of the majorants; replacing it by the supremum of their population means would be invalid.
Base term and summation. The class of \(\pi_0f\) has at most \(N_0\) elements, second moments below \(\delta^2\), and absolute bound \(\tau\). Lemma 7 bounds its expected supremum by \(C\{\delta\sqrt{H(\delta)}+a(\delta)H(\delta)\}\leq C'J_{[\:]}(\delta)\). For the other terms,
The second inequality follows by interchanging nonnegative sums and summing the geometric sequence \(\sum_{q\geq\max(1,j-1)}r_q\leq4r_j\). The coarse terms \(j=0,1\) are bounded by \(6\delta\sqrt{H(\delta)}\leq6J_{[\:]}(\delta)\). For \(j\geq2\), monotonicity gives
These intervals partition \((0,\delta]\). Summing proves the desired bound for the truncated process, and adding its envelope tail proves Theorem 6. For a pointwise measurable class, a countable determining subclass gives the displayed ordinary expectations. The bracketing proof also holds for arbitrary classes of measurable functions with outer expectations: every retained-increment class and stopped-residual majorant class is finite, and the final residual has the deterministic uniform bound just proved. Taking outer expectations in those pointwise bounds requires no measurability of the original supremum. ◻
Lemma 7. For a nonempty finite class \(\mathcal H\) with \(Ph^2\le\sigma^2\) and \(|h|\le b\),
Proof. Centering gives \(|h-Ph|\le2b\) and variance at most \(\sigma^2\). Bernstein's mgf bound, followed by log-sum-exp over both signs, yields for \(0<t<3\sqrt n/(2b)\),
Take \(t\) of order \(\min\{\sqrt{\log(2|\mathcal H|)}/\sigma,\sqrt n/b\}\), bounded away from the pole. If \(\sigma=0\), all centered functions vanish almost surely. This proves the assertion, including singleton classes. The same proof applies to independent Rademacher sums, whose summands already have mean zero. ◻
Proof of Theorem 5. Put \(A=\|F\|_{P,2}\). If \(A=0\), pointwise measurability makes the empirical supremum zero almost surely. Otherwise apply Theorem 6 at \(\delta=3A\). The one bracket \([-F,F]\) covers the class at this radius, so \(H(3A)=1\) and \(a(3A)=3A\). Moreover,
Since the entropy integrand is nonincreasing and at least one, \(J_{[\:]}(3A)\le3J_{[\:]}(A)\) and \(A\le J_{[\:]}(A)\). Theorem 6 now gives the claimed global bound. ◻
1. Extensions
The next two maximal inequalities use the same bracketing integral under different moment assumptions. Their exact statements are Lemmas 19.36–19.37 of van der Vaart’s Chapter 19, pp. 288–289. Proofs are referenced there to Lemmas 3.4.2–3.4.3 and Chapter 2.14 of (Vaart and Wellner 2000) deals with these results.
Theorem 8. Let \(\mathcal F\) be a function class of measurable functions \(f : \mathscr X \to \mathbb R\) such that \(\mathbf P\,\,\!\!f^2 < \delta^2\) for all \(f \in \mathcal F\). Let \(F\) be the envelope of \(\mathcal F\). Suppose \(\lVert f \rVert_\infty \leq M\) for every \(f \in \mathcal F\). Then,
Justification from the cited theorem. Apply van der Vaart's Lemma 19.36 (p. 288) to \(\mathcal F\cup\{0\}\). Its variance radius is this \(\delta\), its uniform bound is \(M\), and its bracketing integral uses the same population \(L^2(P)\) widths and \(\operatorname{Log}\) convention. Taking the supremum over the original class only decreases the left side. A full stopped-bracketing derivation for this bounded case is given in the following note on local bracketing bounds.
Theorem 9. Let \(\mathcal F\) be a function class of measurable functions \(f : \mathscr X \to \mathbb R\). Let \(F\) be the envelope of \(\mathcal F\). Define the Bernstein size (often called the Bernstein norm, although it is not homogeneous)
for any measurable function \(f\). Suppose \(\lVert f \rVert_{P,B} < \delta\) for every \(f \in \mathcal F\). Then,
Justification from the cited theorem. This is Lemma 19.37 (p. 289) of the same chapter, applied to \(\mathcal F\cup\{0\}\). Bracket width is measured by the displayed Bernstein size, with no assertion of homogeneity. Since \(e^u-1-u\geq u^2/2\) for \(u\geq0\), a finite Bernstein size also ensures the individual \(L^2(P)\) integrability needed to center the process. The lemma's radius and entropy integral then agree with the displayed quantities. This strengthened bracketing inequality is used as an external theorem; the squared-exponential moment condition is not replaced by an ordinary variance assumption.
Lemma 10 (Symmetrization). Let \(\mathcal F\) be a (countable, or otherwise measurable) class of measurable \(f:\mathscr X\to\mathbb R\). Let \(\varepsilon_1,\dots,\varepsilon_n\) be i.i.d. Rademacher signs, independent of \(X_1,\dots,X_n\). Then
Proof. Write \(Z_f \equiv \sqrt n(\widehat P_n - P)f = n^{-1/2}\sum_{i=1}^n (f(X_i)-\mathbf P\,\,\!\!f)\). Let \(X_1',\dots,X_n'\) be an i.i.d. auxiliary sample, independent of everything, with the same law \(\mathbf P\,\,\!\!\). Then for each fixed \(f\),
where \(\mathbb{E}'\) is expectation over the auxiliary sample. By Jensen (outer expectation form if needed),
Independently swapping each pair \((X_i,X_i')\) preserves its joint law. Thus, as processes indexed by the entire class, the following equality holds in the unconditional distribution (not conditional on the observed pairs):
hence
Using subadditivity of \(\sup|\cdot|\) and symmetry of \((\varepsilon_i)\),
Taking \(\mathbb{E}\mathbb{E}'\) and using that \((X_i')\) has same law as \((X_i)\) and is independent of \((\varepsilon_i)\),
◻