Exercise 14.3: Sharper Rates via Entropy Integrals

chapter 14 entropy integral

Note that $f\mapsto \frac{1}{n}\sum _{i=1}^n\epsilon f(x_i)$ is a sub-Gaussian process with respect to the metric $d(f,g)=\Vert f-g{\Vert }_n$. Therefore, $$\begin{array}{}\text{(1)}& \mathbb{E}[\underset{f\in \mathcal{F}}{sup}\frac{1}{n}\sum _{i=1}^n\epsilon f(x_i)]\lesssim \frac{1}{\sqrt{n}}{\int }_0^D\sqrt{\log N(u,\mathcal{F},\Vert \cdot {\Vert }_n)}\text{d}u\end{array}$$ where $$\begin{array}{}\text{(2)}& \mathcal{F}=\{f_{\theta }(x)=⟨\varphi (x),\theta ⟩:\theta \in {\mathbb{R}}^3,\Vert f{\Vert }_{\mathrm{\infty }}\le 1\}\end{array}$$ and $D=\underset{f,g\in \mathcal{F}}{sup}=\Vert f-g{\Vert }_n\le 2$. Note that $\theta \mapsto \varphi (X)\theta$ is an isomorphism between ${\mathbb{R}}^3$ and $\mathrm{col}(\varphi (X))$ with the norm $\Vert \varphi (X)\theta {\Vert }_n=\Vert f{\Vert }_n$. Hence $$\begin{array}{}\text{(3)}& N(u,\mathcal{F},\Vert \cdot {\Vert }_n)& \le N(u,\{\theta \in {\mathbb{R}}^3:\Vert ⟨\varphi (\cdot ),\theta ⟩{\Vert }_{\mathrm{\infty }}\le 1\},\Vert \varphi (X)\cdot {\Vert }_n)\text{(4)}& & \le N(u,\{\theta \in {\mathbb{R}}^3:\Vert \varphi (X)\theta {\Vert }_{\mathrm{\infty }}\le 1\},\Vert \varphi (X)\cdot {\Vert }_n)\text{(5)}& & \le N(u,\{\theta \in {\mathbb{R}}^3:\Vert \varphi (X)\theta {\Vert }_n\le 1\},\Vert \varphi (X)\cdot {\Vert }_n)\text{(6)}& & \le 3\log (1+2/u),\end{array}$$ so the entropy integral is finite and independent of $n$.