Exercise 13.5: Lower Bounds on the Critical Inequality
(a)
Since $f^* = 0$, $\F^* = \F$. Using Cauchy–Schwarz, \begin{equation} n\, \G_n(\delta; \F^*) = \E_w[ \sup_{\norm{g}_n \le \delta} \abs{\lra{w, g(x)}} ] \le \sqrt{n}\, \E_w[ \sup_{\norm{g}_n \le \delta}\norm{w}_2 \norm{g}_n ] \le n \delta. \end{equation} Therefore, equating \begin{equation} \delta \overset{!}{=} \frac{1}{2 \sigma} \delta^2 \end{equation} gives that $\delta^2 = 4 \sigma^2$.
(b)
Assume that $0 \in \F$, so $\F^* = \F$ by convexity of $\F$. Let $\delta \in (0, 1]$. Since $\F$ is star-shaped and $\delta \in [0, 1]$, $1 \in \F$ implies that $\delta \in \F$. Therefore, \begin{equation} \G_n(\delta; \F^*) \ge \frac{\delta}{n}\, \E\sbrac{\abs{\sum_{i=1}^n w_i}} = \sqrt{\frac2\pi}\frac{\delta}{\sqrt{n}}. \end{equation} If $\delta$ satisfies the critical inequality, then \begin{equation} \sqrt{\frac2\pi}\frac{\delta}{\sqrt{n}} \le \frac{1}{2 \sigma} \delta^2 \implies \frac{8}{\pi} \frac{\sigma^2}{n} \le \delta^2. \end{equation} Since, by assumption, $\delta \in (0, 1]$, the conclusion follows.