Bracketing maximal inequality for the empirical process

First let $h_1,\dots ,h_m$ be measurable functions with $P{h}_j^2\le {\sigma }^2$ and $\mathrm{\mid }{h}_j\mathrm{\mid }\le b$. Applying [F2] to $h_j(X_i)-P{h}_j$, whose variance is at most ${\sigma }^2$ and whose absolute value is at most $2b$, gives $P\{\mathrm{\mid }{\mathbb{G}}_n(h_j)\mathrm{\mid }>\sqrt{2{\sigma }^{2}u}+2bu\mathrm{/}\sqrt{n}\}\le 2e^{-u}\mathrm{.}$ Put $L=\log (2m)$ and $Z={\max }_j\mathrm{\mid }{\mathbb{G}}_n(h_j)\mathrm{\mid }$. By [F4], for $s\ge 0$, $P\{Z>\varphi (s)\}\le e^{-s},\varphi (s)=\sqrt{2{\sigma }^2(L+s)}+2b(L+s)\mathrm{/}\sqrt{n}\mathrm{.}$ Using [F3] to integrate this tail after the increasing change of variable $t=\varphi (s)$ gives $EZ\le \varphi (0)+{\int }_0^{\mathrm{\infty }}{e}^{-s}{\varphi }^{\mathrm{\prime }}(s)ds\le C_0(\sigma \sqrt{L}+bL\mathrm{/}\sqrt{n})$, since $L\ge \log 2$ and ${\int }_0^{\mathrm{\infty }}{e}^{-s}(L+s{)}^{-1\mathrm{/}2}ds\le L^{-1\mathrm{/}2}$. The same bound follows by continuity if $\sigma =0$ or $b=0$.

For $g\in \mathcal{G}$, abbreviate its cell oscillation by ${\mathrm{\Delta }}_{q}g$. The sequence ${\mathrm{\Delta }}_{q}g$ decreases pointwise and is dominated by $2H$, while $\mathrm{\parallel }{\mathrm{\Delta }}_{q}g{\mathrm{\parallel }}_{P,2}\le 2^{-q}\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}$. By [F7], $P{\mathrm{\Delta }}_{q}g\to 0$; by [F5] and the integrable majorant $2H$, the pointwise limit of ${\mathrm{\Delta }}_{q}g$ consequently has integral zero and is zero $P$-almost everywhere. Countability of $\mathcal{G}$ and finiteness of each partition give one common full-measure set on which all envelope and oscillation bounds hold and every oscillation tends to zero; iid observations avoid its null complement almost surely. Define $A_{q}g={\prod }_{p=q_0}^q{\mathbf{1}}_{\{{\mathrm{\Delta }}_{p}g\le \sqrt{n}{a}_p\}},B_{q_0}g={\mathbf{1}}_{\{{\mathrm{\Delta }}_{q_0}g>\sqrt{n}{a}_{q_0}\}},B_{q}g=A_{q-1}g{\mathbf{1}}_{\{{\mathrm{\Delta }}_{q}g>\sqrt{n}{a}_q\}}(q>q_0)\mathrm{.}$ Nestedness makes these indicators constant on the corresponding cells. At each point either every cutoff passes or there is a unique first failed cutoff. In the first case, ${\pi }_{q}g\to g$ by the vanishing oscillation; in the second, the sum stops at that first failure. In either case, pointwise telescoping gives $g-{\pi }_{q_0}g=(g-{\pi }_{q_0}g)B_{q_0}g+{\sum }_{q>q_0}(g-{\pi }_{q}g)B_{q}g+{\sum }_{q>q_0}({\pi }_{q}g-{\pi }_{q-1}g)A_{q-1}g\mathrm{.}$

The $m_{q_0}$ representatives ${\pi }_{q_0}(C)$ have $L^2(P)$ norm at most $M_{\mathcal{G}}$. Clip each representative to zero on $\{H>\sqrt{n}{a}_{q_0}\}$. The clipped functions have absolute bound $\sqrt{n}{a}_{q_0}$ and the same $L^2$ bound, so step 1.1 bounds their expected maximum by $C_0[M_{\mathcal{G}}\sqrt{L_{q_0}}+a_{q_0}\log (2m_{q_0})]$. The unclipped remainders are bounded by $H{\mathbf{1}}_{\{H>\sqrt{n}{a}_{q_0}\}}$, whose empirical-process maximum has expectation at most $2\sqrt{n}P(H{\mathbf{1}}_{\{H>\sqrt{n}{a}_{q_0}\}})$. Since $m_{q_0+1}\ge m_{q_0}$, the definition of $a_{q_0}$ absorbs the second term into $2^{-q_0}\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}\sqrt{L_{q_0}}$. Thus the coarse representatives contribute at most the first and tail terms in the claimed bound, up to a universal factor.

The first term on the right of step 1.2 is bounded by $2H{\mathbf{1}}_{\{H>\sqrt{n}{a}_{q_0}\mathrm{/}2\}}$, because ${\mathrm{\Delta }}_{q_0}g>\sqrt{n}{a}_{q_0}$ and ${\mathrm{\Delta }}_{q_0}g\le 2H$. For any integrable $Y$, the triangle inequality and $E{P}_n\mathrm{\mid }Y\mathrm{\mid }=P\mathrm{\mid }Y\mathrm{\mid }$ give $E\mathrm{\mid }{\mathbb{G}}_n(Y)\mathrm{\mid }\le 2\sqrt{n}P\mathrm{\mid }Y\mathrm{\mid }$. Thus this first term contributes at most $4\sqrt{n}P(H{\mathbf{1}}_{\{H>\sqrt{n}{a}_{q_0}\mathrm{/}2\}})$.

Fix $q>q_0$. Because $B_{q}g$ is constant on its level-$q$ cell, the functions $w_q={\mathrm{\Delta }}_{q}g{B}_{q}g$ take at most $m_q$ distinct values. On $B_{q}g=1$, ${\mathrm{\Delta }}_{q}g>\sqrt{n}{a}_q$ and ${\mathrm{\Delta }}_{q}g\le {\mathrm{\Delta }}_{q-1}g\le \sqrt{n}{a}_{q-1}$, so $P{w}_q^2\le \frac{a_{q-1}}{a_q}P({\mathrm{\Delta }}_{q}g{)}^2\le \frac{a_{q-1}}{a_q}{4}^{-q}\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}^2,$ and $\mathrm{\mid }{w}_q\mathrm{\mid }\le \sqrt{n}{a}_{q-1}$. Step 1.1 therefore bounds the expected maximum of $\mathrm{\mid }{\mathbb{G}}_n(w_q)\mathrm{\mid }$ by $C_0[2^{-q}\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}\sqrt{\frac{a_{q-1}}{a_q}{L}_q}+a_{q-1}\log (2m_q)]\mathrm{.}$ For each residual $r_q=(g-{\pi }_{q}g)B_{q}g$, $\mathrm{\mid }{r}_q\mathrm{\mid }\le w_q$, whence $\mathrm{\mid }{\mathbb{G}}_n(r_q)\mathrm{\mid }\le \mathrm{\mid }{\mathbb{G}}_n(w_q)\mathrm{\mid }+2\sqrt{n}P{w}_q$. The cutoff also gives $\sqrt{n}P{w}_q\le P({\mathrm{\Delta }}_{q}g{)}^2\mathrm{/}{a}_q\le 2^{-q}\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}\sqrt{L_{q+1}}$. Since $a_{q-1}\mathrm{/}{a}_q=2\sqrt{L_{q+1}\mathrm{/}{L}_q}$ and $a_{q-1}=2^{-(q-1)}\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}\mathrm{/}\sqrt{L_q}$, these bounds are at most a universal multiple of $\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}{2}^{-q}(\sqrt{L_q}+\sqrt{L_{q+1}})$. Summing over $q>q_0$ is bounded by a universal multiple of the entropy tail in the statement.

The functions $v_q=({\pi }_{q}g-{\pi }_{q-1}g)A_{q-1}g$ take at most $m_q$ distinct values by nestedness. On $A_{q-1}g=1$, both representatives lie in the level-$(q-1)$ cell, so $\mathrm{\mid }{v}_q\mathrm{\mid }\le {\mathrm{\Delta }}_{q-1}g\le \sqrt{n}{a}_{q-1}$ and $P{v}_q^2\le 4^{-(q-1)}\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}^2$. Step 1.1 bounds their expected maximum by a universal multiple of $\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}{2}^{-q}\sqrt{L_q}+a_{q-1}\log (2m_q)\le C_1\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}{2}^{-q}\sqrt{L_q}\mathrm{.}$ Summing over $q>q_0$ gives the same entropy-tail bound.

If the entropy tail in the claimed bound is infinite, the result is immediate. Otherwise take finite partial sums in the decomposition of step 1.2: they stabilize at a first failed cutoff or telescope to $g-{\pi }_{q_0}g$, and their absolute values are bounded by $2H$ outside the common null set from step 1.2. Dominated convergence [F5] and convergence of the finite sample averages therefore let the linear empirical-process map pass to the decomposition for each $g$. Now take the supremum over the countable class. Step 2.1 bounds the coarse representatives, step 2.2 bounds the first failed-cutoff term, and steps 2.3–2.4 bound the two series; [F6] justifies summing the nonnegative expected maxima by monotone convergence. Combining these estimates and increasing the universal constant gives the stated inequality.