A tail inequality for quadratic forms of subgaussian random vectors

By Daniel J. Hsu, Sham M. Kakade, Tong Zhang. 2011

447 citations recorded by the source corpus.

This article proves an exponential probability tail inequality for positive semidefinite quadratic forms in a subgaussian random vector. The bound is analogous to one that holds when the vector has independent Gaussian entries.

Subfields: Applied Mathematics, Numerical Analysis, Statistics and Probability

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 Numerical Analysis

In Statistics and Probability

Citations in the corpus

Additive models with trend filtering (2017, positive): “, Theorem 1 in Hsu et al. (2012)), we have, for all c ≥ 2, ‖Πk,n(f̂ − f0)‖(2)n ≤ cσ(2) kd n , (69) on an event Ω1 with probability at least 1− exp(−c/16).”
Few-Shot Learning via Learning the Representation, Provably (2020, methodology): “Similarly, we get that the other term is upper bounded by order of λR/T : q Notice here we used Tr(Σ ) by Proposition 1 of Hsu et al. (2012a).”
Graph Resistance and Learning from Pairwise Comparisons (2019, unknown): “It follows then from Theorem 2.1 of (Hsu et al., 2012) for subgaussian random variables applied to ||(ei − ej)BTL†(F − p)||2 = ||V (F − p)||2(i,j), that for any t ≥ 1 there is a probability at least 1− e−t that ||V (F − p)||2(i,j) ≤ 16b2 k ( tr(M) + 2 √ tr(M2)t+ 2 ||M || t ) ≤ 16b 2 k tr(M)(1 +…”
Assortment Optimization Under General Choice (2011, background): “(2012a,b), Zhang (2011), Kunnumkal and Topaloglu (2008, 2010), van Ryzin and Vulcano (2008), Chaneton and Vulcano (2011).”
A note on the Hanson-Wright inequality for random vectors with dependencies (2014, background): “In particular in [14] a corresponding upper tail inequality is proved for positive definite matrices and sub-Gaussian random vectors X (we recall that a random vector X in R is sub-Gaussian with constant K if for all u ∈ S, and all t > 0, P(|〈X, u〉| ≥ t) ≤ 2 exp(−t2/K2)).”
What are the Statistical Limits of Offline RL with Linear Function Approximation? (2020, unknown): “Note that For all h ∈ [ H ], we have [Hsu et al., 2012a], with probability 1 − δ/ (4 H ), for some constant C (cid:48) , we have Let c > 0 be a large enough constant.”
A modern maximum-likelihood theory for high-dimensional logistic regression (2018, unknown): “Since V has sub-Gaussian tails, by an application of [54] and the union bound, for a(ε) = 2 max{2 √ εH(2 √ ε)}, PV [ max S:|S|=2 √ εn ∑ i∈S V 2 i ≤ C1na( ) ] ≥ 1− e−H(2 √ , (C.”
Bootstrapping and sample splitting for high-dimensional, assumption-lean inference (2016, background): “Since ‖Xi‖ ≤ K √ p and E [ ‖Xi‖2 ] ≤ Up for all i = 1, . . . , n, Proposition 1.2 in Hsu et al. (2012) yields that P ( 1 n ∥∥∥∥∥ n∑ i=1 Xi ∥∥∥∥∥ ≤ √ Up n + √ 8 Up n log n+ 4K √ p 3n log n ) ≥ 1− 1 n .”
Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee (2019, background): “(11) Next, since ε, conditioned onX and y, has independent and subgaussian entries (with parameter σ), by (Hsu et al., 2012), for any symmetric matrixA, with probability at least 1 ́ δ, }Aε} ď σ b”
Online and Differentially-Private Tensor Decomposition (2016, unknown): “Our simulation results and explicit construction of an “adversarial” noise matrix also suggests that our analysis for robust tensor power method with random initializations under random Gaussian noise and existing analysis for worst-case noise in [1] are tight.”