A truncated covering integral bounds empirical Rademacher complexity

For $x>0$, put $r(x)=x-\tanh x$. By [F3], $r(0)=0$ and $r^{\mathrm{\prime }}(x)=1-{\mathrm{sech}}^{2}x={\tanh }^{2}x\ge 0$. The mean value theorem [F6] therefore gives $r(x)\ge 0$; at $x=0$ this is equality. Put $q(x)=e^{-x^2\mathrm{/}2}\cosh x$. The derivative rules in [F3] and [F7] give $q^{\mathrm{\prime }}(x)=e^{-x^2\mathrm{/}2}\cosh x(\tanh x-x)\le 0$. Applying [F6] on $[0,x]$ for $x>0$ yields $q(x)\le q(0)=1$, and equality holds at $x=0$. Since $q$ is even, $\cosh x\le e^{x^2\mathrm{/}2}$ for every real $x$.

Choose $g_0\in \mathcal{G}$ and subtract its sample vector $v_0$ from every vector in $\mathcal{G}\mathrm{\mid }S$. The empirical Rademacher average is unchanged because ${\mathbb{E}}_{\epsilon }{\sum }_i{\epsilon }_i{g}_0(z_i)=0$, and translation preserves all Frobenius covering numbers. Write $U:=(\mathcal{G}\mathrm{\mid }S)-v_0$; it contains $0$, and each vector has norm at most $\sqrt{n}$. For any $ϵ>0$, partition $[-1,1{]}^n$ into finitely many boxes of side at most $ϵ\mathrm{/}\sqrt{n}$; from each box meeting $U$ take one member of that intersection. The resulting finite set is a proper $ϵ$-cover, since two points in one box differ in Euclidean norm by at most $ϵ$. Set ${ϵ}_j=\sqrt{n}{2}^{-(j-1)}$. The singleton $V_1=\{0\}$ is a proper ${ϵ}_1$-cover of $U$, so $\mathrm{\mid }{V}_1\mathrm{\mid }=N_F(U,{ϵ}_1)=1$. For each finite truncation $N\ge 2$ and each $2\le j\le N$, choose a proper ${ϵ}_j$-cover $V_j$ of $U$ with the least possible cardinality, so $\mathrm{\mid }{V}_j\mathrm{\mid }=N_F(U,{ϵ}_j)$; such a least cardinality exists because a finite cover exists and cover cardinalities are positive integers. Enumerate each finite cover and map every sample vector to the first center within ${ϵ}_j$.

Let $V$ be a nonempty finite set of vectors in ${\mathbb{R}}^n$ and let $R={\max }_{v\in V}\parallel v{\parallel }_2$. For $T_v={\sum }_i{\epsilon }_i{v}_i$, independence of the signs and step 1.1 give $\mathbb{E}{e}^{\lambda T_v}={\prod }_i\cosh (\lambda v_i)\le e^{{\lambda }^2{R}^2\mathrm{/}2}$. If $R=0$ or $\mathrm{\mid }V\mathrm{\mid }=1$, $\mathbb{E}{\max }_{v\in V}{T}_v=0$. Otherwise, for $\lambda >0$, [F4] and $e^{\lambda {\max }_v{T}_v}\le {\sum }_{v\in V}{e}^{\lambda T_v}$ imply $\mathbb{E}{\max }_v{T}_v\le \log \mathrm{\mid }V\mathrm{\mid }\mathrm{/}\lambda +\lambda R^2\mathrm{/}2$. Choosing $\lambda =\sqrt{2\log \mathrm{\mid }V\mathrm{\mid }}\mathrm{/}R$ gives $\mathbb{E}{\max }_v{T}_v\le R\sqrt{2\log \mathrm{\mid }V\mathrm{\mid }}$.

For any translated sample vector $v\in U$, telescope $v=(v-v_N[v])+{\sum }_{j=1}^{N-1}(v_{j+1}[v]-v_j[v])$, since $v_1[v]=0$. The absolute residual sign sum is at most $\parallel ({\epsilon }_i{)}_i{\parallel }_2\parallel v-v_N[v]{\parallel }_2\le \sqrt{n}{ϵ}_N$ by [F8]. For each $j<N$, use only the paired-center difference set $D_j:=\{v_{j+1}[v]-v_j[v]:v\in U\}$. It is a nonempty subset of $V_{j+1}-V_j$, so its cardinality is at most $\mathrm{\mid }{V}_{j+1}\mathrm{\mid }\mathrm{\mid }{V}_j\mathrm{\mid }\le N_F(\mathcal{G}\mathrm{\mid }S,{ϵ}_{j+1}{)}^2$, because covering numbers are nonincreasing with radius. Each paired difference has norm at most $\parallel v_{j+1}[v]-v{\parallel }_2+\parallel v-v_j[v]{\parallel }_2\le {ϵ}_{j+1}+{ϵ}_j=3{ϵ}_{j+1}$. Step 2.1 applied to $D_j$ therefore bounds its expected maximum sign sum by $6{ϵ}_{j+1}\sqrt{\log N_F(\mathcal{G}\mathrm{\mid }S,{ϵ}_{j+1})}$. Taking the supremum in the telescoping identity, summing these bounds, and dividing by $n$ gives ${\widehat{\mathfrak{R}}}_S(\mathcal{G})\le {ϵ}_N\mathrm{/}\sqrt{n}+(6\mathrm{/}n){\sum }_{j=1}^{N-1}{ϵ}_{j+1}\sqrt{\log N_F(\mathcal{G}\mathrm{\mid }S,{ϵ}_{j+1})}$.

The function $f(ϵ)=\sqrt{\log N_F(\mathcal{G}\mathrm{\mid }S,ϵ)}$ is nonincreasing in $ϵ$. Since ${ϵ}_{j+2}={ϵ}_{j+1}\mathrm{/}2$, each summand obeys ${ϵ}_{j+1}f({ϵ}_{j+1})\le 2{\int }_{{ϵ}_{j+2}}^{{ϵ}_{j+1}}f(ϵ)dϵ$. Therefore step 3.1 gives ${\widehat{\mathfrak{R}}}_S(\mathcal{G})\le {ϵ}_N\mathrm{/}\sqrt{n}+(12\mathrm{/}n){\int }_{{ϵ}_{N+1}}^{\sqrt{n}}f(ϵ)dϵ$.

If $\sqrt{n}\mathrm{/}4\le \alpha \le \sqrt{n}$, each signed average is at most $1$, so ${\widehat{\mathfrak{R}}}_S(\mathcal{G})\le 1\le 4\alpha \mathrm{/}\sqrt{n}$. If $0<\alpha <\sqrt{n}\mathrm{/}4$, choose the largest $N\ge 1$ with ${ϵ}_{N+1}>\alpha$; such an $N$ exists because ${ϵ}_2=\sqrt{n}\mathrm{/}2>\alpha$ and ${ϵ}_j\to 0$. Maximality gives ${ϵ}_{N+2}\le \alpha$, hence ${ϵ}_N=4{ϵ}_{N+2}\le 4\alpha$, and ${\int }_{{ϵ}_{N+1}}^{\sqrt{n}}f\le {\int }_{\alpha }^{\sqrt{n}}f$. Substitution into step 4.1 proves the stated inequality for every $0<\alpha <\sqrt{n}\mathrm{/}4$. Together, the two cases prove it for every $0<\alpha \le \sqrt{n}$.