Skip to content
nonconvexcard

Prove the Hanson–Wright inequality

ProofOlympiad / Extreme⏱ 1 dayHigh-Dim Probabilityhanson-wrightquadratic formsdecouplingconcentration

Problem

Let X=(X1,…,Xn)X = (X_1,\dots,X_n) have independent, mean-zero, sub-Gaussian coordinates with ∥Xi∥ψ2≤K\|X_i\|_{\psi_2} \le K, and let A∈Rn×nA \in \R^{n\times n}. Prove that for every t≥0t \ge 0,

P(∣X⊤AX−EX⊤AX∣≥t) ≤ 2exp⁡[−cmin⁡(t2K4∥A∥F2, tK2∥A∥)],\P\Big(\big|X^\top A X - \E X^\top A X\big| \ge t\Big) \ \le\ 2\exp\left[-c\min\left(\frac{t^2}{K^4\|A\|_F^2},\ \frac{t}{K^2\|A\|}\right)\right],

with cc an absolute constant. Then explain why both norms of AA must appear.

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints

Hints — 0 of 3 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems
SolvedProblemFieldTypeDifficultyTime
Markov and Chebyshev are attainedHigh-Dim ProbabilityProofFoundation15 min
Azuma for a random walk with driftHigh-Dim ProbabilityProofIntermediate30 min
Derive Hoeffding's inequality from Hoeffding's lemmaHigh-Dim ProbabilityProofIntermediate30 min
Distance contrast and the failure of nearest neighboursClassical MLProofIntermediate30 min
From an exponential tail bound to almost sure convergenceProbabilityProofIntermediate30 min