Prove the Hanson–Wright inequality
ProofOlympiad / Extreme⏱ 1 dayHigh-Dim Probabilityhanson-wrightquadratic formsdecouplingconcentration
Problem
Let have independent, mean-zero, sub-Gaussian coordinates with , and let . Prove that for every ,
with an absolute constant. Then explain why both norms of 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| Solved | Problem | Field | Type | Difficulty | Time |
|---|---|---|---|---|---|
| Markov and Chebyshev are attained | High-Dim Probability | Proof | 15 min | ||
| Azuma for a random walk with drift | High-Dim Probability | Proof | 30 min | ||
| Derive Hoeffding's inequality from Hoeffding's lemma | High-Dim Probability | Proof | 30 min | ||
| Distance contrast and the failure of nearest neighbours | Classical ML | Proof | 30 min | ||
| From an exponential tail bound to almost sure convergence | Probability | Proof | 30 min |