Exercise 5.6: Gaussian Complexity for $\ell_q$-Balls
(a)
Take \(p\) to be the Hölder conjugate of \(q\) (i.e., \(\frac{1}{p} = 1 -\frac{1}{q}\)), and observe \begin{align} \mathcal{G} (B_q^d (1)) &\overset{\text{(i)}}{\leq} \E [\| w \|_p] \newline &= d^{1/p} \E \bigl[ \bigl( \tfrac{1}{d} {\textstyle \sum_{i=1}^d} |w_i|^p \bigr)^{1/p} \bigr] \newline &\overset{\text{(ii)}}{\leq} d^{1/p} \bigl[\E |w_1|^p\bigr]^{1/p} \overset{\text{(ii)}}{<} \infty \, , \end{align} where (i) is by Hölder’s inequality and \(w_1 \overset{\text{iid}}{\sim} \gauss(0, 1)\), (ii) by the Jensen’s inequality, and (iii) by standard properties of Gaussian random variables. Setting \(c_q = [\E |w_1|^p]^{1/p}\) yields the upper bound.
For the lower bound, \(\theta = (\pm d^{-1/q}, \ldots, \pm d^{-1/q}) \in B_q^d(1)\) for any choice of the plus and minus signs, implying \begin{align} \E [\sup_{\| \theta \|_q \leq 1} \langle \theta , w \rangle] &\geq d^{-1/q} \sum_{i=1}^d \E | w_i | = d^{1/p} \sqrt{\frac{2}{\pi}} \, , \end{align} where the last equality is again a known result for Gaussian random variables.
(b)
Since \(\theta_i w_i\) which is maximised by \(\theta_i = \sign(w_i)\) over \(\theta_i \in [-1, 1]\), we have \(\sup_{\| \theta \|_\infty \leq 1} \langle \theta, w \rangle = \| w \|_1\). Hence \begin{align} \mathcal{G}(B_\infty^d (1)) = d \E | w_1 | = d \sqrt{\frac{2}{\pi}} \, . \end{align} The lower bound from (a) is therefore tight.