VC entropy bound for empirical Rademacher complexity

The loss class $G_H$ is a measurable class of $[0,1]$-valued functions. Its strict subgraphs have the same VC dimension $d$ as $H$: for a point $(z,t)$ with $t<0$ membership is always true and with $t\ge 1$ it is always false, while for $0\le t<1$ membership in the subgraph of $g_h$ is exactly $g_h(z)=1$. For fixed $z=(x,y)$, changing from $h(x)$ to $\mathbf{1}\{h(x)\mathrm{\ne }y\}$ only flips that coordinate when $y=1$, so a shattered set of active coordinates for the loss subgraphs gives a shattered indexed tuple for $H$. Conversely, a shattered $d$-tuple for $H$, placed at $z_i=(x_i,0)$ and height $t_i=1\mathrm{/}2$, is shattered by the loss subgraphs. Thus the loss subgraph index is $V=d+1$.

The trace class $G_H\mathrm{\mid }S=\{(g_h(z_1),\dots ,g_h(z_m)):h\in H\}$ is finite, nonempty, and contained in $\{0,1{\}}^m$. Let $Q_S=m^{-1}{\sum }_i{\delta }_{z_i}$ and use envelope $F\equiv 1$, for which $\mathrm{\parallel }F{\mathrm{\parallel }}_{Q_S,2}=1$. By [F3], for every $k\ge 1$ there is a finite $2^{-k}$-net $T_k$ of the restricted traces with $\mathrm{\mid }{T}_k\mathrm{\mid }\le (A\cdot 2^k{)}^{2A(d+1)}$. Choose one trace $g_0$ and put $T_0=\{g_0\}$. Since the trace class is finite, there is a finite depth $N$ for which $2^{-N}$ is smaller than every positive distance between two distinct traces, so the last approximant can be taken equal to each trace. All choices in this step are finite.

Write $X_u=m^{-1}{\sum }_i{\sigma }_i{u}_i$ for a trace vector $u$. For any pair of trace vectors $u,v$, put $a_i=u_i-v_i$. Rescaling [F4] to the range $[-\mathrm{\mid }{a}_i\mathrm{\mid }\mathrm{/}m,\mathrm{\mid }{a}_i\mathrm{\mid }\mathrm{/}m]$ gives $\mathbb{E}{e}^{\lambda {\sigma }_i{a}_i\mathrm{/}m}\le e^{{\lambda }^2{a}_i^2\mathrm{/}(2m^2)}$. Expanding the uniform finite sign expectation as a product therefore gives ${\mathbb{E}}_{\sigma }{e}^{\lambda (X_u-X_v)}\le \exp ({\lambda }^2{d}_2(u,v{)}^2\mathrm{/}(2m))$, where $d_2(u,v{)}^2=m^{-1}{\sum }_i{a}_i^2$. If $d_2(u,v)\le \mathrm{\Delta }$, the centered increment is therefore sub-Gaussian with variance proxy ${\mathrm{\Delta }}^2\mathrm{/}m$. For $M$ such increments, $e^{\lambda {\max }_j{Y}_j}\le {\sum }_j{e}^{\lambda Y_j}$. On the finite uniform sign space, the two-point convexity inequality [F7] gives $e^{\lambda {\mathbb{E}}_{\sigma }{\max }_j{Y}_j}\le {\mathbb{E}}_{\sigma }{e}^{\lambda {\max }_j{Y}_j}$: its equal-weight finite form follows by induction over its $q=2^m$ outcomes, applying [F7] to the mean of the first $q-1$ values and the last value with weights $(q-1)\mathrm{/}q$ and $1\mathrm{/}q$. Hence [F6] and the increment moment bound give $\lambda \mathbb{E}{\max }_j{Y}_j\le \log M+{\lambda }^2{\mathrm{\Delta }}^2\mathrm{/}(2m)$. Dividing by $\lambda >0$ and minimizing yields $\mathrm{\Delta }\sqrt{2\log M\mathrm{/}m}$, with the value $0$ when $M=1$.

For each $k\ge 1$, the pairs $({\pi }_k(g),{\pi }_{k-1}(g))$ arising from the nets in step 2.1 have distance at most ${\mathrm{\Delta }}_k=2^{-k}+2^{-(k-1)}=3\cdot 2^{-k}$. Their number is at most $\mathrm{\mid }{T}_k\mathrm{\mid }\mathrm{\mid }{T}_{k-1}\mathrm{\mid }$, so [F6] and step 2.1 give $\log (\mathrm{\mid }{T}_k\mathrm{\mid }\mathrm{\mid }{T}_{k-1}\mathrm{\mid })\le 4A(d+1)(\log A+k\log 2)$. Since ${\mathbb{E}}_{\sigma }{X}_{g_0}=0$, telescoping the finite chain from $g_0$ to each trace and applying step 3.1 yields ${\widehat{\mathfrak{R}}}_S(G_H)\le 3\sqrt{\frac{8A(d+1)}{m}}{\sum }_{k=1}^N{2}^{-k}\sqrt{\log A+k\log 2}\mathrm{.}$ Using $\sqrt{a+b}\le \sqrt{a}+\sqrt{b}$, [F5], and $\sqrt{k}\le k$ for $k\ge 1$, the sum is at most $\sqrt{\log A}+2\sqrt{\log 2}$ because ${\sum }_{k=1}^{N}k{2}^{-k}=2-(N+2)2^{-N}\le 2$ (verified by induction on $N$). The stated constant follows.