Chaining and Uniform Limits

Fix any $\mathrm{\ell }\in \mathcal{L}$. On the stated event, $R(\widehat{\mathrm{\ell }})\le R_n(\widehat{\mathrm{\ell }})+ϵ$ by applying the uniform deviation bound to $\widehat{\mathrm{\ell }}$.

The approximate-minimization property gives $R_n(\widehat{\mathrm{\ell }})\le R_n(\mathrm{\ell })+\eta$, and the same event gives $R_n(\mathrm{\ell })\le R(\mathrm{\ell })+ϵ$. Combining these inequalities with step 1.1 yields $R(\widehat{\mathrm{\ell }})\le R(\mathrm{\ell })+2ϵ+\eta$.

Since step 2.1 holds for every $\mathrm{\ell }\in \mathcal{L}$, take the infimum of its right-hand side over $\mathcal{L}$ to obtain the claimed bound.

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.

First derive a finite-maximum estimate. If $Y_1,\dots ,Y_m$ are centered and each has sub-Gaussian proxy at most $s^2$, then for $\lambda >0$, $\mathbb{E}{e}^{\lambda {\max }_j\mathrm{\mid }{Y}_j\mathrm{\mid }}\le {\sum }_{j=1}^m(\mathbb{E}{e}^{\lambda Y_j}+\mathbb{E}{e}^{-\lambda Y_j})\le 2m{e}^{{\lambda }^2{s}^2\mathrm{/}2}\mathrm{.}$ By [F3], $\mathbb{E}{\max }_j\mathrm{\mid }{Y}_j\mathrm{\mid }\le {\lambda }^{-1}\log (2m)+\lambda s^2\mathrm{/}2$. For $s>0$, choosing $\lambda =\sqrt{2\log (2m)}\mathrm{/}s$ gives $\mathbb{E}{\max }_j\mathrm{\mid }{Y}_j\mathrm{\mid }\le s\sqrt{2\log (2m)}$; for $s=0$, the proxy bound forces every $Y_j=0$ almost surely by [F4] applied to $e^{\pm \lambda Y_j}$ and letting $\lambda \to \mathrm{\infty }$.

If $D=0$, every pair in $T$ has distance zero. The proxy-zero case of step 1.1 applied to each increment, together with separability and [F6] for the countable intersection of probability-one events, makes the supremum zero. Assume $D>0$. Fix $k\ge 1$ and put ${ϵ}_k=2^{-k}D$. Total boundedness gives a finite cover of $T$ by $N({ϵ}_k\mathrm{/}4,T,d)$ closed balls of radius ${ϵ}_k\mathrm{/}4$. Approximate each center by a point of the dense set $T_0$ within ${ϵ}_k\mathrm{/}4$ to obtain a cover of $T$ by the same number of balls of radius ${ϵ}_k\mathrm{/}2$. Since the specified countable dense set is listed, choose the first finite tuple under its induced enumeration that is an ${ϵ}_k$-net and has cardinality at most this cover size; such a tuple exists by the construction. Denote it by $T_k$. For each $t$, choose the least-index point ${\pi }_k(t)\in T_k$ within ${ϵ}_k$. These canonical choices across scales require no choice axiom. Put $T_0^{(0)}=\{t_0\}$ and ${\pi }_0(t)=t_0$.

For a finite subset $A\subset T_0$, telescope $X_t-X_{t_0}$ through ${\pi }_1(t),\dots ,{\pi }_m(t)$ for every $t\in A$. At level $1$ there are at most $\mathrm{\mid }{T}_1\mathrm{\mid }$ increments, each with proxy at most $D^2$; for $k\ge 2$ there are at most $\mathrm{\mid }{T}_k\mathrm{\mid }\mathrm{\mid }{T}_{k-1}\mathrm{\mid }$ increments, each with proxy at most $({ϵ}_k+{ϵ}_{k-1}{)}^2=(3{ϵ}_k{)}^2$. Applying step 1.1 to the finite set of increments at each level, and the triangle inequality for their maxima, yields $\mathbb{E}{\max }_{t\in A}\mathrm{\mid }{X}_{{\pi }_m(t)}-X_{t_0}\mathrm{\mid }\le C_1{\sum }_{k=1}^m{ϵ}_k\sqrt{1+\log N({ϵ}_k\mathrm{/}4,T,d)}$ for a universal $C_1$; the $k=1$ term is absorbed using ${ϵ}_1=D\mathrm{/}2$ and $N({ϵ}_1\mathrm{/}4)\ge 1$.

The residual maximum over $A$ has expectation at most ${ϵ}_m\sqrt{2\log (2\mathrm{\mid }A\mathrm{\mid })}$ by step 1.1, since $d(t,{\pi }_m(t))\le {ϵ}_m$. Letting $m\to \mathrm{\infty }$ for this fixed finite $A$ removes the residual. The dyadic sum in step 2.2 is bounded by a universal multiple of the entropy integral: on each interval $[{ϵ}_k\mathrm{/}8,{ϵ}_k\mathrm{/}4]$, monotonicity of $N$ makes the integral at least $({ϵ}_k\mathrm{/}8)\sqrt{\log N({ϵ}_k\mathrm{/}4,T,d)}$. Also, for $0<ϵ<D\mathrm{/}2$, one ball of radius $ϵ$ cannot cover a set of diameter $D$, so $N(ϵ,T,d)\ge 2$ and the entropy integral is at least $(D\mathrm{/}2)\sqrt{\log 2}$; this absorbs the geometric contribution from the added $1$. Hence $\mathbb{E}{\max }_{t\in A}\mathrm{\mid }{X}_t-X_{t_0}\mathrm{\mid }\le C{\int }_0^D\sqrt{\log N(ϵ,T,d)}dϵ\mathrm{.}$ Taking an increasing sequence of finite subsets whose union is $T_0$, [F5] and the separability assumption give the asserted supremum over $T$.

Fix $ϵ>0$ and let ${\mathcal{F}}_0$ be the countable pointwise-dense subclass. Choose a finite $L^1(P)$ bracketing cover of $\mathcal{F}$ with widths at most $ϵ\mathrm{/}2$, which is strictly below $ϵ$; discard brackets not meeting ${\mathcal{F}}_0$. For each retained bracket, choose one member of ${\mathcal{F}}_0$ in it. The envelope and that member imply that clipping its endpoints to $[-F,F]$ preserves every inclusion in the bracket $P$-almost surely, and cannot increase the width. Since only finitely many endpoints remain and each is bounded by the integrable $F$, they are integrable. Countability and [F5] give one probability-one event on which all pointwise-dense-class bracket inclusions hold at every observation.

If $f\in [l_j,u_j]$, then $P_{n}f-Pf\le P_n{u}_j-P{l}_j=(P_n{u}_j-P{u}_j)+P(u_j-l_j)$; likewise $Pf-P_{n}f\le (P{l}_j-P_n{l}_j)+P(u_j-l_j)$. Hence ${\sup }_{f\in {\mathcal{F}}_0}\mathrm{\mid }{P}_{n}f-Pf\mathrm{\mid }\le {\max }_{1\le j\le m}\mathrm{\mid }{P}_n{u}_j-P{u}_j\mathrm{\mid }\vee {\max }_{1\le j\le m}\mathrm{\mid }{P}_n{l}_j-P{l}_j\mathrm{\mid }+ϵ\mathrm{/}2.$ Each endpoint is integrable, so [F3] makes both finite maxima tend to zero almost surely. For arbitrary $f\in \mathcal{F}$, choose pointwise approximants $f_k\in {\mathcal{F}}_0$; [F4] gives $P{f}_k\to Pf$, and the finite empirical averages give $P_n{f}_k\to P_{n}f$ at every sample. Thus the supremum over $\mathcal{F}$ equals the countable supremum over ${\mathcal{F}}_0$ samplewise. Given any target $\eta >0$, take $ϵ=\eta$; the endpoint maxima then imply $P({\sup }_{f\in \mathcal{F}}\mathrm{\mid }{P}_{n}f-Pf\mathrm{\mid }>\eta )\to 0$. No simultaneous choice of brackets across scales is used for this probability-convergence conclusion.

Now assume Countable Choice. For each integer $m\ge 1$, choose one finite bracket family of width at most $1\mathrm{/}(2m)$. Step 2.1 with $ϵ=1\mathrm{/}m$ and [F3] give a probability-one event on which ${\mathrm{lim\hspace{0.17em}sup}}_n{\sup }_f\mathrm{\mid }{P}_{n}f-Pf\mathrm{\mid }\le 1\mathrm{/}(2m)$. By [F5], the countable intersection of these events still has probability one. On it the nonnegative supremum has limsup at most $1\mathrm{/}(2m)$ for every $m$, hence converges to zero. This is strong $P$-Glivenko–Cantelli convergence as defined in Glivenko–Cantelli classes.

Choose a countable pointwise-dense subclass ${\mathcal{F}}_0\subseteq \mathcal{F}$. For $\delta >0$, set ${\mathcal{H}}_{\delta }=\{(f-g)-P(f-g):f,g\in {\mathcal{F}}_0,{\rho }_P(f,g)\le \delta \}$. Every $h\in {\mathcal{H}}_{\delta }$ has $\mathrm{\parallel }h{\mathrm{\parallel }}_{P,2}\le \delta$ and is bounded in absolute value by $H:=2F+2PF$, with $\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}\le 4\mathrm{\parallel }F{\mathrm{\parallel }}_{P,2}$.

If $f$ and $g$ lie in $L^2(P)$ brackets $[l_i,u_i]$ and $[l_j,u_j]$ of width at most $r\mathrm{\parallel }F{\mathrm{\parallel }}_{P,2}$, respectively, then $(f-g)-P(f-g)$ lies in the bracket $[l_i-u_j-P(u_i-l_j),u_i-l_j-P(l_i-u_j)]\mathrm{.}$ Its width is $w_i+w_j+P(w_i+w_j)$, where $w_i=u_i-l_i$ and $w_j=u_j-l_j$; Cauchy–Schwarz gives its $L^2(P)$ norm at most $2(\mathrm{\parallel }{w}_i{\mathrm{\parallel }}_{P,2}+\mathrm{\parallel }{w}_j{\mathrm{\parallel }}_{P,2})\le 4r\mathrm{\parallel }F{\mathrm{\parallel }}_{P,2}$. Thus $N_{[]}(4r\mathrm{\parallel }F{\mathrm{\parallel }}_{P,2},{\mathcal{H}}_{\delta },L^2(P))\le N_{[]}(r\mathrm{\parallel }F{\mathrm{\parallel }}_{P,2},\mathcal{F},L^2(P){)}^2$.

Fix $0<\delta <\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}\mathrm{/}2$ and choose $q_0\ge 1$ with $\delta \mathrm{/}2<2^{-q_0}\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}\le \delta$. For each $q\ge q_0$, take a finite bracketing cover of ${\mathcal{H}}_{\delta }$ at width $2^{-q}\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}$ and partition the class by assigning each function to the first bracket containing it. Refine these finite partitions cumulatively through level $q$; by [A1], the countable family of finite covers and their representatives can be selected. If $b_q$ is the unrefined level-$q$ count, step 1.2 gives $b_q\le N_{[]}(r_q\mathrm{\parallel }F{\mathrm{\parallel }}_{P,2},\mathcal{F},L^2(P){)}^2$ for $r_q=2^{-q}\mathrm{\parallel }H{\mathrm{\parallel }}_{P,2}\mathrm{/}(4\mathrm{\parallel }F{\mathrm{\parallel }}_{P,2})$, and the refined count satisfies $m_q\le {\prod }_{p=q_0}^q{b}_p$. Consequently, using $\sqrt{1+\sum x_p}\le 1+\sum \sqrt{x_p}$ for $x_p\ge 0$ and summing the resulting geometric weights, ${\sum }_{q\ge q_0}{2}^{-q}\sqrt{1+\log (2m_q)}\le C_1{\int }_0^{C_2\delta \mathrm{/}\mathrm{\parallel }F{\mathrm{\parallel }}_{P,2}}\sqrt{1+\log N_{[]}(ϵ\mathrm{\parallel }F{\mathrm{\parallel }}_{P,2},\mathcal{F},L^2(P))}dϵ$ for universal constants $C_1,C_2$: the unrefined entropy terms at scale $r_q$ are bounded by the integrand on the adjacent dyadic interval $[r_q\mathrm{/}2,r_q]$ by monotonicity of bracketing numbers, and cumulative refinement contributes only a geometric sum of earlier terms. The added $1$ contributes a geometric sum of order $2^{-q_0}$, which is also bounded by the displayed integral because its integrand is at least $1$. On each refined cell $C$, define ${\mathrm{\Delta }}_{q,C}={\sup }_{h,h^{\mathrm{\prime }}\in C}\mathrm{\mid }h-h^{\mathrm{\prime }}\mathrm{\mid }$ and choose ${\pi }_q(C)\in C$. Countability makes this pointwise supremum measurable; containment in a level-$q$ bracket gives ${\mathrm{\Delta }}_{q,C}\le u-l$ $P$-almost everywhere, so it has the required $L^2(P)$ bound. Intersecting partitions makes these oscillations nonincreasing on child cells. Thus these partitions and widths satisfy the hypotheses of [F2] when the local maximal inequality is applied.

Apply [F2] to ${\mathcal{H}}_{\delta }$ with envelope $H$ and this nested partition. Its coarse term is at most $C\delta \sqrt{1+\log (2m_{q_0})}$, its dyadic tail is bounded by the right-hand side of step 2.1, and its final envelope-tail term tends to zero as $n\to \mathrm{\infty }$ for this fixed $\delta$: for each fixed $a>0$, $\sqrt{n}P(H{\mathbf{1}}_{\{H>a\sqrt{n}\}})\le a^{-1}P(H^2{\mathbf{1}}_{\{H>a\sqrt{n}\}})\to 0$ by [F4].