Exercise 14.7: Uniform Laws and Sparse Eigenvalues
Let $X \in \R^{n \times d}$ be a random matrix with i.i.d.\ $\Normal(0, \Sigma)$ rows. For $s > 0$, define \begin{equation} \F = \set{f_\theta = \lra{\theta, \vardot} : \norm{\theta}_1 \le \sqrt{s} \norm{\theta}_2}. \end{equation} We aim to apply Theorem 14.12, which would directly give the result. To begin with, we verify that $\F\ss{spcone}$ is star-shaped, zero mean, and that the fourth moment condition holds uniformly with $C^2 = 3$ (see Example 14.10 from the book). It remains to choose $n$ large enough to ensure that there exists a $\delta_n \le 1$ satisfying $\overline\Rc_n(\delta, \F) \lesssim \delta^2$. For $f \in \F$, note that $\norm{f}_2 = \lra{\theta, \Sigma \theta} \ge \gamma\ss{min}(\Sigma) \norm{\theta}_2^2$. The conditions on $\theta$ for the supremum within $\overline\Rc_n(\delta, \F)$ therefore imply that $\norm{\theta}_2 \le \delta/\sqrt{\gamma\ss{min}(\Sigma)}$ (from $\norm{f}_2 \le \delta$) and $\norm{\theta}_1 \le \sqrt{s} \norm{\theta}_2 \le \sqrt{s} \delta / \sqrt{\gamma\ss{min}(\Sigma)}$ (from the definition of $\F$). Hence \begin{equation} \overline{\Rc}_n(\delta, \F) \le \frac{\delta}{\sqrt{\gamma\ss{min}(\Sigma)}} \E\sbrac{ \sup_{\norm{\theta}_2 \le 1, \, \norm{\theta_1} \le \sqrt{s}} \abs{ \frac1n \lra{\e, X \theta} } }. \end{equation} Note that $\lra{\e, X \theta} = \lra{\theta, \smash{X^\T} \e}$ where $X^\T \e = \sum_{i=1}^n \e_i x_i \sim \Normal(0, n \Sigma)$, so $\lra{\e, X \theta} \disteq \lra{\theta, \smash{\sqrt{n \Sigma}} w}$ with $w \sim \Normal(0, I_d)$. We can therefore apply Exercise 7.15(a) to find that \begin{equation} \overline{\Rc}_n(\delta, \F) \lesssim \delta\frac{C’}{\sqrt{\gamma\ss{min}(\Sigma)}} \sqrt{\frac{s \log(ed/s)}{n}} \end{equation} where $C’ = \sup_{S \sub [d]} \norm{\sqrt{n \Sigma}_S}_2 / \sqrt{n} \le \sqrt{\gamma\ss{max}(\Sigma)}$. Thus, we can find a $\delta_n$ which satisfies $\overline\Rc_n(\delta, \F) \lesssim \delta^2$ if \begin{equation} n \gtrsim \frac{\gamma\ss{max}(\Sigma)}{\gamma\ss{min}(\Sigma)}s \log \frac{ed}{s}. \end{equation}
The above condition is valid but depends on $\gamma\ss{max}(\Sigma)$ rather than on $\rho^2(\Sigma)$. It is unclear how we can get the required dependence on $\rho^2(\Sigma)$.