Exercise 13.6: Local Gaussian Complexity and Adaptivity
Instead of the model from the question, consider the model \begin{equation} y_i = \theta_i + \sigma w_i \end{equation} and the function class $\F_{\ell^1}(\sqrt{n}) = \set{f_\theta \text{ linear} : \norm{\theta}_1 \le \sqrt{n}}$. To account for the scaling by $\sqrt{n}$, we derive rates for $\norm{\hat f - f^*}_n^2 = \norm{\hat \theta - \theta^*}_n^2$ rather than for $\norm{\hat \theta - \theta^*}_2^2$.
We’re a little unsure about this solution. Please let us know what you think in the comments!
(a)
Note that $\F_{\ell^1}^*(\sqrt{n}) \sub \F_{\ell^1}(2 \sqrt{n})$, so \begin{equation} \G_n(\delta; \F_{\ell^1}^*(\sqrt{n})) \le \frac1n \E[\,\sup_\theta\, \abs{\lra{\theta, w}}] \end{equation} where the supremum is over all $\theta$ such that (1) $\norm{\theta}_1 \le 2\sqrt{n}$ and (2) $\norm{\theta}_2 \le \sqrt{n} \delta$. Although the $\ell^2$-ball has a potentially much smaller radius, the Gaussian complexity of $\ell^1$-balls has a much better scaling in the dimensionality. Therefore, estimate $\lra{\theta, w} \le \norm{\theta}_1 \norm{w}_\infty$: \begin{equation} \G_n(\delta; \F_{\ell^1}^*(\sqrt{n})) \lesssim \frac1n \sqrt{n} \sqrt{\log n} = \sqrt{\frac{\log n}{n}}. \end{equation} Setting \begin{equation} \sqrt{\frac{\log n}{n}} \overset{!}{\propto} \frac{1}{\sigma}\delta^2 \end{equation} then yields that \begin{equation} \norm{\hat f - f^*}_n^2 \lesssim \delta^2 \propto \sigma \sqrt{\frac{\log n}{n}}. \end{equation}
(b)
Now consider the Gaussian complexity \begin{equation} \G_n(\delta; \F_{\ell^1}^*(\sqrt{n})) = \frac1n \E[\,\sup_\theta\, \abs{\lra{\theta, w}}] \end{equation} where the supremum is over all $\theta$ such that (1) $\norm{\theta}_1 \le \sqrt{n}$, and (2) $\norm{\theta - \sqrt{n} e_1}_2 \le \sqrt{n} \delta$. Using rotation invariance of $w$, a picture shows that the Gaussian complexity of the above collection is equal to that of the intersection of the $\ell^2$-ball of radius $\sqrt{n} \delta$ and any quadrant, for example all $\theta$ such that $\theta \ge 0$. Another picture shows that that intersection can be upper bounded by the convex hull of $\sqrt{2n} \delta \set{e_1, \ldots, e_n}$. Therefore, using the property of the Gaussian complexity that we can omit the convex hull operator, \begin{equation} \G_n(\delta; \F_{\ell^1}^*(\sqrt{n})) \le \frac1n \E[\,\sup_{\theta \in \sqrt{2n} \delta \set{e_1, \ldots, e_n}} \, \abs{\lra{\theta, w}}] \lesssim \frac{1}{n} \sqrt{n} \delta \sqrt{\log n} \propto \delta \sqrt{\frac{\log(n)}{n}}. \end{equation} Setting \begin{equation} \delta \sqrt{\frac{\log n}{n}} \overset{!}{\propto} \frac{1}{\sigma}\delta^2 \end{equation} then yields that \begin{equation} \norm{\hat f - f^*}_n^2 \lesssim \delta^2 \propto \sigma^2 \frac{\log n}{n}. \end{equation}