Hanson-Wright inequality and sub-gaussian concentration

By Mark Rudelson, Roman Vershynin. 2013

792 citations recorded by the source corpus.

In this expository note, we give a modern proof of Hanson-Wright inequality for quadratic forms in sub-gaussian random variables.We deduce a useful concentration inequality for sub-gaussian random vectors.Two examples are given to illustrate these results: a concentration of distances between random vectors and subspaces, and a bound on the norms of products of random and deterministic matrices.

Subfields: Applied Mathematics, Mathematical Physics, Statistics and Probability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Mathematical Physics

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, background): “1 in Rudelson and Vershynin [2013]), we have for any t ≥ 0,”
Benign overfitting in linear regression (2019, background): “Earlier, r0(Σ 2) was called the ‘stable rank’ [35] and the ‘numerical rank’ [34], although that term has a different meaning in computational linear algebra [23, p261].”
Classification vs regression in overparameterized regimes: Does the loss function matter? (2020, neutral): “Lemma 4 (Hanson-Wright inequality [35]).”
Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics (2016, background): “By Hanson-Wright Inequality (Theorem 1 in Rudelson and Vershynin (2013)),”
On cross-validated Lasso in high dimensions (2016, neutral): “[36] Rudelson, M.”
On the Randomized Complexity of Minimizing a Convex Quadratic Function (2018, methodology): “The bounds now follow from a routine application of the Hanson-Wright inequality (see, e.g. Rudelson et al. [2013]) on the event { γI − W (cid:37) ( λ − 1) 2 } , and noting that u and z are both independent of W .”
Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification (2018, background): “For many systems, including strictly stable systems (e.g. Corollary 2.2), one can show via HansonWright [Rudelson and Vershynin, 2011] that ‖ ∑T t=1XtX > t ‖op concentrates belowO (Tλmax(ΓT )) ≤ O (Tλmax(Γ∞)).”
Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator (2018, neutral): “[22] Mark Rudelson and Roman Vershynin.”
Learning Mixed Membership Community Models in Social Tagging Networks through Tensor Methods (2015, methodology): “We require the Hanson-Wright inequality (Rudelson and Vershynin, 2013).”
Random graph asymptotics for treatment effect estimation under network interference (2020, methodology): “Since the vector Wi − π has independent and mean-zero entries, we can use the Hanson-Wright inequality as stated in Rudelson and Vershynin (2013) to verify that the above term is bounded in probability to order ‖M‖F /n, which in turn is bounded as Op(B/ √ nminiNi).”
Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel (2018, methodology): “Now we can apply Theorem 1.1 of Rudelson et al. [62], using the fact that e i z have sub-Gaussian norm 2 to get for some universal constant c (cid:48) .”
Concentration inequalities for polynomials in α-sub-exponential random variables (2019, background): “Now, as in [29], we use the inequality |z− 1| ≤ min(|z(2) − 1|, |z(2) − 1|), giving for any t ≥ 0 P ( |‖BX‖2 − 1| ≥ t ) ≤ P ( |‖BX‖22 − 1| ≥ max(t, t (2)) ) .”