Exercise 4.9: Proof of Lemma 4.14

chapter 4

Rewrite the expectation as follows: \begin{equation} \E_\e[\,\sup_{a \in A} \lra{a, \e}] \end{equation} where \begin{equation} A = \set{s (f(x_1), \ldots, f(x_n)) / n : s \in \set{-1, 1},\, f \in \F}. \end{equation} By polynomial discrimination of order \(\nu\) of \(\F\), it holds that \(\abs{A} \le 2 (n + 1)^\nu\). Note that \(\lra{a, \e} \in \SG(\norm{a}_2)\), where \(\norm{a}_2 = D(x_{1:n}) / \sqrt{n}\). Therefore, by the expected maximum of sub-Gaussian variables, \begin{equation} \E_\e[\,\sup_{a \in A} \lra{a, \e}] \le 2D(x_{1:n})\sqrt{\frac{\nu \log(n + 1)}{n}}. \end{equation}