Exercise 2.17: Hanson–Wright Inequality

chapter 2

Without loss of generality, assume that \(\sigma = 1\). Let \(Q = U \diag(\lambda_1, \ldots, \lambda_n) U^\T\) be the spectral decomposition of \(Q\). Then \begin{equation} \lra{X, Q X} \disteq \sum_{i=1}^n \lambda_i X_i^2 =: Z. \end{equation} By a calculation, if \(X \sim \Normal(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{equation} (\nu, \alpha) = \parens{ 2 \parens{\textstyle\sum_{i=1}^n \lambda_i^2}^{1/2}, 4 \max_{i \in [n]} \lambda_i } = (2 \norm{Q}_F, 4 \norm{Q}\ss{op}). \end{equation} Hence, by the sub-exponential tail bound, we have that \begin{equation} \P(\lra{X, Q X} \ge \tr Q + t) \le \exp\parens{ -\min\parens{ \frac{t}{2 \alpha}, \frac{t^2}{2 \nu^2} } } = \exp\parens{ -\min\parens{ \frac{t}{8 \norm{Q}\ss{op}}, \frac{t^2}{8 \norm{Q}_F^2} } }. \end{equation}