Empirical-Process Complexity — Examples

By [F1], $\mathrm{\Omega }$ is uncountable. The empty set is at most countable, and complementation exchanges the countable and cocountable alternatives, so $\mathcal{A}$ contains the empty set and is complement-closed. For a sequence $(A_n)$ in $\mathcal{A}$, if every $A_n$ is countable then [A1] makes their union countable; otherwise some $A_j$ is cocountable, and $\mathrm{\Omega }\setminus {\bigcup }_n{A}_n\subseteq \mathrm{\Omega }\setminus A_j$ is countable by [F2]. Thus the union lies in $\mathcal{A}$ in either case, proving all sigma-algebra axioms in [F5]. The assignment $P$ is well-defined: a set and its complement cannot both be countable, since their union would make $\mathrm{\Omega }$ countable.

Let $(A_n)$ be pairwise disjoint members of $\mathcal{A}$. If every $A_n$ is countable, [A1] makes their union countable; then $P({\bigcup }_n{A}_n)=0={\sum }_{n}P(A_n)$. Otherwise choose $j$ with $A_j$ cocountable. For $n\mathrm{\ne }j$, disjointness gives $A_n\subseteq \mathrm{\Omega }\setminus A_j$, a countable set, so [F2] makes $A_n$ countable. The union is cocountable and its measure is $1=P(A_j)+{\sum }_{n\mathrm{\ne }j}P(A_n)$. Also $P(\mathrm{\Omega })=1$ and $P$ is nonnegative, so [F3] shows that $P$ is a probability measure.

Regard $(\mathrm{\Omega },\mathcal{A},P)$ as the observation space and let $Z$ be its identity random element, which has law $P$. For each $t\in U$, the singleton $\{t\}$ is in $\mathcal{A}$ by [F2], so $f_t={\mathbf{1}}_{\{t\}}$ is measurable and $P{f}_t=P(\{t\})=0$. If $s\mathrm{\ne }t$, then $f_s(s)=1$ and $f_t(s)=0$, so $t\mapsto f_t$ is injective; since $U$ is uncountable by [F1], $\mathcal{F}$ is uncountable.

For any $\omega \in \mathrm{\Omega }$, if $\omega \in U$ then the index $t=\omega$ gives $f_t(\omega )=1$, while if $\omega \mathrm{\notin }U$ every $t\in U$ differs from $\omega$ and all the function values are zero. Hence the displayed supremum equals ${\mathbf{1}}_U(\omega )$. Both $U$ and $\mathrm{\Omega }\setminus U$ contain a nondegenerate interval and are uncountable by [F1]; therefore $U\mathrm{\notin }\mathcal{A}$, so the supremum is nonmeasurable.

The real-power definition gives ${16}^1=\exp (\log 16)=16$. Its exponent law gives ${16}^{j+1}={16}^{j}16$ for every natural $j$, so induction identifies the real power ${16}^m$ with the natural product defining $N$. By [F3], $N^{-1\mathrm{/}m}=({16}^m{)}^{-1\mathrm{/}m}={16}^{-1}=1\mathrm{/}16.$

The subgraphs $C_{f_k}=\{(i,t):t<f_k(i)\}$ are nested in increasing $k$. A point $(1,1\mathrm{/}2)$ belongs to $C_{f_N}$ and not to $C_{f_0}$, so a singleton is shattered. No two-point set is shattered by a nested family, since shattering would require both opposite singleton traces, which nested sets cannot realize. Therefore the VC-subgraph dimension is exactly one and its index is $V=2$.

For $k\mathrm{\ne }\mathrm{\ell }$, the functions differ on exactly $\mathrm{\mid }k-\mathrm{\ell }\mathrm{\mid }$ atoms. By [F2] and [F4], $\mathrm{\parallel }{f}_k-f_{\mathrm{\ell }}{\mathrm{\parallel }}_{Q_m,m}={\left(\frac{\mathrm{\mid }k-\mathrm{\ell }\mathrm{\mid }}{N}\right)}^{1\mathrm{/}m}\ge N^{-1\mathrm{/}m}=1\mathrm{/}16.$

Since $1\mathrm{/}16>2ϵ=1\mathrm{/}32$, a closed $L^m(Q_m)$ ball of radius $ϵ$ centered at a class member cannot contain two distinct class members: the triangle inequality would make their distance at most $2ϵ$. Thus every cover needs at least $N+1$ centers; taking each member as its own center gives a cover with $N+1$. This proves the exact covering number.

Fix any proposed finite right side that depends only on $ϵ$, the VC index, and constants independent of $r$. At $ϵ=1\mathrm{/}64$ and $V=2$ it is a fixed finite number. By [F5], choose $m$ so large that ${16}^m+1$ exceeds that number. Step 3.1 then contradicts the proposed bound, so this family rules out a VC covering bound whose right-hand side is independent of $r$.

Direct evaluation gives $P{f}_0=0$, $P{f}_1=1\mathrm{/}2$, $P_1{f}_0=0$, and $P_1{f}_1=Z$. Hence ${\sup }_{f\in \mathcal{F}}\mathrm{\mid }{P}_{1}f-Pf\mathrm{\mid }=\mathrm{\mid }Z-1\mathrm{/}2\mathrm{\mid }=1\mathrm{/}2$ for both possible observations.

If $Z=0$, then ${\sup }_f\sigma f(Z)=0$ for either sign. If $Z=1$, then ${\sup }_f\sigma f(Z)=\max (0,\sigma )$, whose uniform-sign expectation is $1\mathrm{/}2$. Thus ${\widehat{\mathfrak{R}}}_{(Z)}(\mathcal{F})=Z\mathrm{/}2$ and its expectation over the sample is $1\mathrm{/}4$.

Applying [F3] with $n=1$ and $\mathrm{\mid }\mathcal{F}\mathrm{\mid }=2$ gives $P({\sup }_{f\in \mathcal{F}}\mathrm{\mid }{P}_{1}f-Pf\mathrm{\mid }\ge ϵ)\le 4e^{-2{ϵ}^2}$ for every $ϵ>0$. At $ϵ=1\mathrm{/}2$ the event has probability one by step 1.1, and the displayed estimate is the stated finite-class guarantee for this class.