Exercise 2.17: Hanson–Wright Inequality

chapter 2

Without loss of generality, assume that $\sigma =1$. Let $Q=U\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_n)U^{\mathsf{\text{T}}}$ be the spectral decomposition of $Q$. Then $$\begin{array}{}\text{(1)}& ⟨X,QX⟩\stackrel{\text{d}}{=}\sum _{i=1}^n{\lambda }_i{X}_i^2=:Z.\end{array}$$ By a calculation, if $X\sim \mathcal{N}(0,1)$, it follows that $X^2$ is sub-exponential with parameters $(\nu ,\alpha )=(2,4)$. Therefore, ${\lambda }_i{X}_i^2$ is sub-exponential with parameters $(\nu ,\alpha )=(2{\lambda }_i,4{\lambda }_i)$, which means that $Z$ is sub-exponential with parameters $$\begin{array}{}\text{(2)}& (\nu ,\alpha )=(2{\left(\sum _{i=1}^n{\lambda }_i^2\right)}^{1/2},4\underset{i\in [n]}{max}{\lambda }_i)=(2\Vert Q{\Vert }_F,4\Vert Q{\Vert }_{\text{op}}).\end{array}$$ Hence, by the sub-exponential tail bound, we have that $$\begin{array}{}\text{(3)}& \mathbb{P}(⟨X,QX⟩\ge \mathrm{tr}Q+t)\le \exp (-min(\frac{t}{2\alpha },\frac{t^2}{2{\nu }^2}))=\exp (-min(\frac{t}{8\Vert Q{\Vert }_{\text{op}}},\frac{t^2}{8\Vert Q{\Vert }_F^2})).\end{array}$$