Sub-Gaussian distribution

☆ Save On Wikipedia ↗

In probability theory, a subgaussian distribution, the distribution of a subgaussian random variable, is a probability distribution with strong tail decay. More specifically, the tails of a subgaussian distribution are dominated by (i.e. decay at least as fast as) the tails of a Gaussian. This property gives subgaussian distributions their name.

Often in analysis, we divide an object (such as a random variable) into two parts, a central bulk and a distant tail, then analyze each separately. In probability, this division usually goes like "Everything interesting happens near the center. The tail event is so rare, we may safely ignore that." Subgaussian distributions are worthy of study, because the gaussian distribution is well-understood, and so we can give sharp bounds on the rarity of the tail event. An analogous class, sometimes called subexponential distributions, is also useful; note however that the more established meaning of subexponential is almost the opposite -- that decay is slower than exponential rather than that the tail is lighter than exponential -- and so care must be taken with that term.

Formally, the probability distribution of a random variable X {\displaystyle X} {\displaystyle X} is called subgaussian if there is a positive constant C such that for every t ≥ 0 {\displaystyle t\geq 0} {\displaystyle t\geq 0},

P ⁡ ( | X | ≥ t ) ≤ 2 exp ⁡ ( − t 2 / C 2 ) {\textstyle \operatorname {P} (|X|\geq t)\leq 2\exp {(-t^{2}/C^{2})}} {\textstyle \operatorname {P} (|X|\geq t)\leq 2\exp {(-t^{2}/C^{2})}}.

There are many equivalent definitions. For example, a random variable X {\displaystyle X} {\displaystyle X} is sub-Gaussian iff its distribution function is bounded from above (up to a constant) by the distribution function of a Gaussian:

P ( | X | ≥ t ) ≤ c P ( | Z | ≥ t ) ∀ t > 0 {\displaystyle P(|X|\geq t)\leq cP(|Z|\geq t)\quad \forall t>0} {\displaystyle P(|X|\geq t)\leq cP(|Z|\geq t)\quad \forall t>0}

where c ≥ 0 {\displaystyle c\geq 0} {\displaystyle c\geq 0} is constant and Z {\displaystyle Z} {\displaystyle Z} is a mean zero Gaussian random variable.[1]: Theorem 2.6 

Definitions

Subgaussian norm

The subgaussian norm of X {\displaystyle X} {\displaystyle X}, denoted as ‖ X ‖ ψ 2 {\displaystyle \Vert X\Vert _{\psi _{2}}} {\displaystyle \Vert X\Vert _{\psi _{2}}}, is ‖ X ‖ ψ 2 = inf { c > 0 : E ⁡ [ exp ⁡ ( X 2 c 2 ) ] ≤ 2 } . {\displaystyle \Vert X\Vert _{\psi _{2}}=\inf \left\{c>0:\operatorname {E} \left[\exp {\left({\frac {X^{2}}{c^{2}}}\right)}\right]\leq 2\right\}.} {\displaystyle \Vert X\Vert _{\psi _{2}}=\inf \left\{c>0:\operatorname {E} \left[\exp {\left({\frac {X^{2}}{c^{2}}}\right)}\right]\leq 2\right\}.}In other words, it is the Orlicz norm of X {\displaystyle X} {\displaystyle X} generated by the Orlicz function Φ ( u ) = e u 2 − 1. {\displaystyle \Phi (u)=e^{u^{2}}-1.} {\displaystyle \Phi (u)=e^{u^{2}}-1.} By condition ( 2 ) {\displaystyle (2)} {\displaystyle (2)} below, subgaussian random variables can be characterized as those random variables with finite subgaussian norm.

Variance proxy

If there exists a number s 2 ≥ 0 {\displaystyle s^{2}\geq 0} {\displaystyle s^{2}\geq 0} such that E ⁡ [ e ( X − E ⁡ [ X ] ) t ] ≤ e s 2 t 2 2 {\displaystyle \operatorname {E} [e^{(X-\operatorname {E} [X])t}]\leq e^{\frac {s^{2}t^{2}}{2}}} {\displaystyle \operatorname {E} [e^{(X-\operatorname {E} [X])t}]\leq e^{\frac {s^{2}t^{2}}{2}}} for all t ∈ R {\displaystyle t\in \mathbb {R} } {\displaystyle t\in \mathbb {R} }, then s 2 {\displaystyle s^{2}} {\displaystyle s^{2}} is called a variance proxy. The smallest such s 2 {\displaystyle s^{2}} {\displaystyle s^{2}} is called the optimal variance proxy and denoted by ‖ X ‖ v p 2 {\displaystyle \Vert X\Vert _{\mathrm {vp} }^{2}} {\displaystyle \Vert X\Vert _{\mathrm {vp} }^{2}}.

The optimal variance proxy and the subgaussian norm are related by 3 / 8 ⋅ ‖ X ‖ ψ 2 ≤ ‖ X ‖ v p ≤ log ⁡ 2 ⋅ ‖ X ‖ ψ 2 , {\displaystyle {\sqrt {3/8}}\cdot \Vert X\Vert _{\psi _{2}}\leq \Vert X\Vert _{\mathrm {vp} }\leq {\sqrt {\log 2}}\cdot \Vert X\Vert _{\psi _{2}},} {\displaystyle {\sqrt {3/8}}\cdot \Vert X\Vert _{\psi _{2}}\leq \Vert X\Vert _{\mathrm {vp} }\leq {\sqrt {\log 2}}\cdot \Vert X\Vert _{\psi _{2}},} and both bounds are sharp, attained by the standard Gaussian and Rademacher distributions, respectively.[2]

For a Gaussian random variable X ∼ N ( μ , σ 2 ) {\displaystyle X\sim {\mathcal {N}}(\mu ,\sigma ^{2})} {\displaystyle X\sim {\mathcal {N}}(\mu ,\sigma ^{2})}, one has E ⁡ [ e ( X − E ⁡ [ X ] ) t ] = e σ 2 t 2 2 {\displaystyle \operatorname {E} [e^{(X-\operatorname {E} [X])t}]=e^{\frac {\sigma ^{2}t^{2}}{2}}} {\displaystyle \operatorname {E} [e^{(X-\operatorname {E} [X])t}]=e^{\frac {\sigma ^{2}t^{2}}{2}}}, and therefore ‖ X ‖ v p 2 = σ 2 {\displaystyle \|X\|_{\mathrm {vp} }^{2}=\sigma ^{2}} {\displaystyle \|X\|_{\mathrm {vp} }^{2}=\sigma ^{2}}.

Equivalent definitions

Let X {\displaystyle X} {\displaystyle X} be a random variable with zero mean. Let K 1 , K 2 , K 3 , … {\displaystyle K_{1},K_{2},K_{3},\dots } {\displaystyle K_{1},K_{2},K_{3},\dots } be positive constants. The following conditions are equivalent: (Proposition 2.5.2 [3])

  1. Tail probability bound: P ⁡ ( | X | ≥ t ) ≤ 2 exp ⁡ ( − t 2 / K 1 2 ) {\displaystyle \operatorname {P} (|X|\geq t)\leq 2\exp {(-t^{2}/K_{1}^{2})}} {\displaystyle \operatorname {P} (|X|\geq t)\leq 2\exp {(-t^{2}/K_{1}^{2})}} for all t ≥ 0 {\displaystyle t\geq 0} {\displaystyle t\geq 0};
  2. Finite subgaussian norm: ‖ X ‖ ψ 2 = K 2 < ∞ {\displaystyle \Vert X\Vert _{\psi _{2}}=K_{2}<\infty } {\displaystyle \Vert X\Vert _{\psi _{2}}=K_{2}<\infty };
  3. Moment: E ⁡ | X | p ≤ 2 K 3 p Γ ( p 2 + 1 ) {\displaystyle \operatorname {E} |X|^{p}\leq 2K_{3}^{p}\Gamma \left({\frac {p}{2}}+1\right)} {\displaystyle \operatorname {E} |X|^{p}\leq 2K_{3}^{p}\Gamma \left({\frac {p}{2}}+1\right)} for all p ≥ 1 {\displaystyle p\geq 1} {\displaystyle p\geq 1}, where Γ {\displaystyle \Gamma } {\displaystyle \Gamma } is the Gamma function;
  4. Moment: E ⁡ | X | p ≤ K p p p / 2 {\displaystyle \operatorname {E} |X|^{p}\leq K^{p}p^{p/2}} {\displaystyle \operatorname {E} |X|^{p}\leq K^{p}p^{p/2}} for all p ≥ 1 {\displaystyle p\geq 1} {\displaystyle p\geq 1};
  5. Moment-generating function (of X {\displaystyle X} {\displaystyle X}), or variance proxy[4][5] : E ⁡ [ e ( X − E ⁡ [ X ] ) t ] ≤ e K 2 t 2 2 {\displaystyle \operatorname {E} [e^{(X-\operatorname {E} [X])t}]\leq e^{\frac {K^{2}t^{2}}{2}}} {\displaystyle \operatorname {E} [e^{(X-\operatorname {E} [X])t}]\leq e^{\frac {K^{2}t^{2}}{2}}} for all t {\displaystyle t} {\displaystyle t};
  6. Moment-generating function (of X 2 {\displaystyle X^{2}} {\displaystyle X^{2}}): E ⁡ [ e X 2 t 2 ] ≤ e K 2 t 2 {\displaystyle \operatorname {E} [e^{X^{2}t^{2}}]\leq e^{K^{2}t^{2}}} {\displaystyle \operatorname {E} [e^{X^{2}t^{2}}]\leq e^{K^{2}t^{2}}} for all t ∈ [ − 1 / K , + 1 / K ] {\displaystyle t\in [-1/K,+1/K]} {\displaystyle t\in [-1/K,+1/K]};
  7. Union bound: for some c > 0,   E ⁡ [ max { | X 1 − E ⁡ [ X ] | , … , | X n − E ⁡ [ X ] | } ] ≤ c log ⁡ n {\displaystyle \ \operatorname {E} [\max\{|X_{1}-\operatorname {E} [X]|,\ldots ,|X_{n}-\operatorname {E} [X]|\}]\leq c{\sqrt {\log n}}} {\displaystyle \ \operatorname {E} [\max\{|X_{1}-\operatorname {E} [X]|,\ldots ,|X_{n}-\operatorname {E} [X]|\}]\leq c{\sqrt {\log n}}} for all n > c, where X 1 , … , X n {\displaystyle X_{1},\ldots ,X_{n}} {\displaystyle X_{1},\ldots ,X_{n}} are i.i.d copies of X;
  8. Subexponential: X 2 {\displaystyle X^{2}} {\displaystyle X^{2}} has a subexponential distribution.

Furthermore, the constant K {\displaystyle K} {\displaystyle K} is the same in the definitions (1) to (5), up to an absolute constant. So for example, given a random variable satisfying (1) and (2), the minimal constants K 1 , K 2 {\displaystyle K_{1},K_{2}} {\displaystyle K_{1},K_{2}} in the two definitions satisfy K 1 ≤ c K 2 , K 2 ≤ c ′ K 1 {\displaystyle K_{1}\leq cK_{2},K_{2}\leq c'K_{1}} {\displaystyle K_{1}\leq cK_{2},K_{2}\leq c'K_{1}}, where c , c ′ {\displaystyle c,c'} {\displaystyle c,c'} are constants independent of the random variable.

Proof of equivalence

As an example, the first four definitions are equivalent by the proof below.

Proof. ( 1 ) ⟹ ( 3 ) {\displaystyle (1)\implies (3)} {\displaystyle (1)\implies (3)} By the layer cake representation, E ⁡ | X | p = ∫ 0 ∞ P ⁡ ( | X | p ≥ t ) d t = ∫ 0 ∞ p t p − 1 P ⁡ ( | X | ≥ t ) d t ≤ 2 ∫ 0 ∞ p t p − 1 exp ⁡ ( − t 2 K 1 2 ) d t {\displaystyle {\begin{aligned}\operatorname {E} |X|^{p}&=\int _{0}^{\infty }\operatorname {P} (|X|^{p}\geq t)dt\\&=\int _{0}^{\infty }pt^{p-1}\operatorname {P} (|X|\geq t)dt\\&\leq 2\int _{0}^{\infty }pt^{p-1}\exp \left(-{\frac {t^{2}}{K_{1}^{2}}}\right)dt\\\end{aligned}}} {\displaystyle {\begin{aligned}\operatorname {E} |X|^{p}&=\int _{0}^{\infty }\operatorname {P} (|X|^{p}\geq t)dt\\&=\int _{0}^{\infty }pt^{p-1}\operatorname {P} (|X|\geq t)dt\\&\leq 2\int _{0}^{\infty }pt^{p-1}\exp \left(-{\frac {t^{2}}{K_{1}^{2}}}\right)dt\\\end{aligned}}}


After a change of variables u = t 2 / K 1 2 {\displaystyle u=t^{2}/K_{1}^{2}} {\displaystyle u=t^{2}/K_{1}^{2}}, we find that E ⁡ | X | p ≤ 2 K 1 p p 2 ∫ 0 ∞ u p 2 − 1 e − u d u = 2 K 1 p p 2 Γ ( p 2 ) = 2 K 1 p Γ ( p 2 + 1 ) . {\displaystyle {\begin{aligned}\operatorname {E} |X|^{p}&\leq 2K_{1}^{p}{\frac {p}{2}}\int _{0}^{\infty }u^{{\frac {p}{2}}-1}e^{-u}du\\&=2K_{1}^{p}{\frac {p}{2}}\Gamma \left({\frac {p}{2}}\right)\\&=2K_{1}^{p}\Gamma \left({\frac {p}{2}}+1\right).\end{aligned}}} {\displaystyle {\begin{aligned}\operatorname {E} |X|^{p}&\leq 2K_{1}^{p}{\frac {p}{2}}\int _{0}^{\infty }u^{{\frac {p}{2}}-1}e^{-u}du\\&=2K_{1}^{p}{\frac {p}{2}}\Gamma \left({\frac {p}{2}}\right)\\&=2K_{1}^{p}\Gamma \left({\frac {p}{2}}+1\right).\end{aligned}}} ( 3 ) ⟹ ( 2 ) {\displaystyle (3)\implies (2)} {\displaystyle (3)\implies (2)} By the Taylor series e x = 1 + ∑ p = 1 ∞ x p p ! , {\textstyle e^{x}=1+\sum _{p=1}^{\infty }{\frac {x^{p}}{p!}},} {\textstyle e^{x}=1+\sum _{p=1}^{\infty }{\frac {x^{p}}{p!}},} E ⁡ [ exp ⁡ ( λ X 2 ) ] = 1 + ∑ p = 1 ∞ λ p E ⁡ [ X 2 p ] p ! ≤ 1 + ∑ p = 1 ∞ 2 λ p K 3 2 p Γ ( p + 1 ) p ! = 1 + 2 ∑ p = 1 ∞ λ p K 3 2 p = 2 ∑ p = 0 ∞ λ p K 3 2 p − 1 = 2 1 − λ K 3 2 − 1 for  λ K 3 2 < 1 , {\displaystyle {\begin{aligned}\operatorname {E} [\exp {(\lambda X^{2})}]&=1+\sum _{p=1}^{\infty }{\frac {\lambda ^{p}\operatorname {E} {[X^{2p}]}}{p!}}\\&\leq 1+\sum _{p=1}^{\infty }{\frac {2\lambda ^{p}K_{3}^{2p}\Gamma \left(p+1\right)}{p!}}\\&=1+2\sum _{p=1}^{\infty }\lambda ^{p}K_{3}^{2p}\\&=2\sum _{p=0}^{\infty }\lambda ^{p}K_{3}^{2p}-1\\&={\frac {2}{1-\lambda K_{3}^{2}}}-1\quad {\text{for }}\lambda K_{3}^{2}<1,\end{aligned}}} {\displaystyle {\begin{aligned}\operatorname {E} [\exp {(\lambda X^{2})}]&=1+\sum _{p=1}^{\infty }{\frac {\lambda ^{p}\operatorname {E} {[X^{2p}]}}{p!}}\\&\leq 1+\sum _{p=1}^{\infty }{\frac {2\lambda ^{p}K_{3}^{2p}\Gamma \left(p+1\right)}{p!}}\\&=1+2\sum _{p=1}^{\infty }\lambda ^{p}K_{3}^{2p}\\&=2\sum _{p=0}^{\infty }\lambda ^{p}K_{3}^{2p}-1\\&={\frac {2}{1-\lambda K_{3}^{2}}}-1\quad {\text{for }}\lambda K_{3}^{2}<1,\end{aligned}}}which is less than or equal to 2 {\displaystyle 2} {\displaystyle 2} for λ ≤ 1 3 K 3 2 {\displaystyle \lambda \leq {\frac {1}{3K_{3}^{2}}}} {\displaystyle \lambda \leq {\frac {1}{3K_{3}^{2}}}}. Let K 2 ≥ 3 1 2 K 3 {\displaystyle K_{2}\geq 3^{\frac {1}{2}}K_{3}} {\displaystyle K_{2}\geq 3^{\frac {1}{2}}K_{3}}, then E ⁡ [ exp ⁡ ( X 2 / K 2 2 ) ] ≤ 2. {\textstyle \operatorname {E} [\exp {(X^{2}/K_{2}^{2})}]\leq 2.} {\textstyle \operatorname {E} [\exp {(X^{2}/K_{2}^{2})}]\leq 2.}


( 2 ) ⟹ ( 1 ) {\displaystyle (2)\implies (1)} {\displaystyle (2)\implies (1)} By Markov's inequality, P ⁡ ( | X | ≥ t ) = P ⁡ ( exp ⁡ ( X 2 K 2 2 ) ≥ exp ⁡ ( t 2 K 2 2 ) ) ≤ E ⁡ [ exp ⁡ ( X 2 / K 2 2 ) ] exp ⁡ ( t 2 K 2 2 ) ≤ 2 exp ⁡ ( − t 2 K 2 2 ) . {\displaystyle \operatorname {P} (|X|\geq t)=\operatorname {P} \left(\exp \left({\frac {X^{2}}{K_{2}^{2}}}\right)\geq \exp \left({\frac {t^{2}}{K_{2}^{2}}}\right)\right)\leq {\frac {\operatorname {E} [\exp {(X^{2}/K_{2}^{2})}]}{\exp \left({\frac {t^{2}}{K_{2}^{2}}}\right)}}\leq 2\exp \left(-{\frac {t^{2}}{K_{2}^{2}}}\right).} {\displaystyle \operatorname {P} (|X|\geq t)=\operatorname {P} \left(\exp \left({\frac {X^{2}}{K_{2}^{2}}}\right)\geq \exp \left({\frac {t^{2}}{K_{2}^{2}}}\right)\right)\leq {\frac {\operatorname {E} [\exp {(X^{2}/K_{2}^{2})}]}{\exp \left({\frac {t^{2}}{K_{2}^{2}}}\right)}}\leq 2\exp \left(-{\frac {t^{2}}{K_{2}^{2}}}\right).} ( 3 ) ⟺ ( 4 ) {\displaystyle (3)\iff (4)} {\displaystyle (3)\iff (4)} by asymptotic formula for gamma function: Γ ( p / 2 + 1 ) ∼ π p ( p 2 e ) p / 2 {\displaystyle \Gamma (p/2+1)\sim {\sqrt {\pi p}}\left({\frac {p}{2e}}\right)^{p/2}} {\displaystyle \Gamma (p/2+1)\sim {\sqrt {\pi p}}\left({\frac {p}{2e}}\right)^{p/2}}.

From the proof, we can extract a cycle of three inequalities:

  • If P ⁡ ( | X | ≥ t ) ≤ 2 exp ⁡ ( − t 2 / K 2 ) {\displaystyle \operatorname {P} (|X|\geq t)\leq 2\exp {(-t^{2}/K^{2})}} {\displaystyle \operatorname {P} (|X|\geq t)\leq 2\exp {(-t^{2}/K^{2})}}, then E ⁡ | X | p ≤ 2 K p Γ ( p 2 + 1 ) {\displaystyle \operatorname {E} |X|^{p}\leq 2K^{p}\Gamma \left({\frac {p}{2}}+1\right)} {\displaystyle \operatorname {E} |X|^{p}\leq 2K^{p}\Gamma \left({\frac {p}{2}}+1\right)} for all p ≥ 1 {\displaystyle p\geq 1} {\displaystyle p\geq 1}.
  • If E ⁡ | X | p ≤ 2 K p Γ ( p 2 + 1 ) {\displaystyle \operatorname {E} |X|^{p}\leq 2K^{p}\Gamma \left({\frac {p}{2}}+1\right)} {\displaystyle \operatorname {E} |X|^{p}\leq 2K^{p}\Gamma \left({\frac {p}{2}}+1\right)} for all p ≥ 1 {\displaystyle p\geq 1} {\displaystyle p\geq 1}, then ‖ X ‖ ψ 2 ≤ 3 1 2 K {\displaystyle \|X\|_{\psi _{2}}\leq 3^{\frac {1}{2}}K} {\displaystyle \|X\|_{\psi _{2}}\leq 3^{\frac {1}{2}}K}.
  • If ‖ X ‖ ψ 2 ≤ K {\displaystyle \|X\|_{\psi _{2}}\leq K} {\displaystyle \|X\|_{\psi _{2}}\leq K}, then P ⁡ ( | X | ≥ t ) ≤ 2 exp ⁡ ( − t 2 / K 2 ) {\displaystyle \operatorname {P} (|X|\geq t)\leq 2\exp {(-t^{2}/K^{2})}} {\displaystyle \operatorname {P} (|X|\geq t)\leq 2\exp {(-t^{2}/K^{2})}}.

In particular, the constant K {\displaystyle K} {\displaystyle K} provided by the definitions are the same up to a constant factor, so we can say that the definitions are equivalent up to a constant independent of X {\displaystyle X} {\displaystyle X}.

Similarly, because up to a positive multiplicative constant, Γ ( p / 2 + 1 ) = p p / 2 × ( ( 2 e ) − 1 / 2 p 1 / 2 p ) p {\displaystyle \Gamma (p/2+1)=p^{p/2}\times ((2e)^{-1/2}p^{1/2p})^{p}} {\displaystyle \Gamma (p/2+1)=p^{p/2}\times ((2e)^{-1/2}p^{1/2p})^{p}} for all p ≥ 1 {\displaystyle p\geq 1} {\displaystyle p\geq 1}, the definitions (3) and (4) are also equivalent up to a constant.

Basic properties

Basic properties—* If X {\textstyle X} {\textstyle X} is subgaussian, and k > 0 {\textstyle k>0} {\textstyle k>0}, then ‖ k X ‖ ψ 2 = k ‖ X ‖ ψ 2 {\textstyle \|kX\|_{\psi _{2}}=k\|X\|_{\psi _{2}}} {\textstyle \|kX\|_{\psi _{2}}=k\|X\|_{\psi _{2}}} and ‖ k X ‖ v p = k ‖ X ‖ v p {\textstyle \|kX\|_{vp}=k\|X\|_{vp}} {\textstyle \|kX\|_{vp}=k\|X\|_{vp}}.

  • (Triangle inequality) If X , Y {\textstyle X,Y} {\textstyle X,Y} are subgaussian, then ‖ X + Y ‖ v p 2 ≤ ( ‖ X ‖ v p + ‖ Y ‖ v p ) 2 {\displaystyle \|X+Y\|_{vp}^{2}\leq (\|X\|_{vp}+\|Y\|_{vp})^{2}} {\displaystyle \|X+Y\|_{vp}^{2}\leq (\|X\|_{vp}+\|Y\|_{vp})^{2}}
  • (Chernoff bound) If X {\textstyle X} {\textstyle X} is subgaussian, then P r ( X ≥ t ) ≤ e − t 2 2 ‖ X ‖ v p 2 {\displaystyle Pr(X\geq t)\leq e^{-{\frac {t^{2}}{2\|X\|_{vp}^{2}}}}} {\displaystyle Pr(X\geq t)\leq e^{-{\frac {t^{2}}{2\|X\|_{vp}^{2}}}}} for all t ≥ 0 {\textstyle t\geq 0} {\textstyle t\geq 0}

X ≲ X ′ {\textstyle X\lesssim X'} {\textstyle X\lesssim X'} means that X ≤ C X ′ {\textstyle X\leq CX'} {\textstyle X\leq CX'}, where the positive constant C {\textstyle C} {\textstyle C} is independent of X {\textstyle X} {\textstyle X} and X ′ {\textstyle X'} {\textstyle X'}.

Subgaussian deviation bound—If X {\textstyle X} {\textstyle X} is subgaussian, then ‖ X − E [ X ] ‖ ψ 2 ≲ ‖ X ‖ ψ 2 {\displaystyle \|X-E[X]\|_{\psi _{2}}\lesssim \|X\|_{\psi _{2}}} {\displaystyle \|X-E[X]\|_{\psi _{2}}\lesssim \|X\|_{\psi _{2}}}

Proof

By triangle inequality, ‖ X − E [ X ] ‖ ψ 2 ≤ ‖ X ‖ ψ 2 + ‖ E [ X ] ‖ ψ 2 {\displaystyle \|X-E[X]\|_{\psi _{2}}\leq \|X\|_{\psi _{2}}+\|E[X]\|_{\psi _{2}}} {\displaystyle \|X-E[X]\|_{\psi _{2}}\leq \|X\|_{\psi _{2}}+\|E[X]\|_{\psi _{2}}}. Now we have ‖ E [ X ] ‖ ψ 2 = ln ⁡ 2 | E [ X ] | ≤ ln ⁡ 2 E [ | X | ] ∼ E [ | X | ] {\displaystyle \|E[X]\|_{\psi _{2}}={\sqrt {\ln 2}}|E[X]|\leq {\sqrt {\ln 2}}E[|X|]\sim E[|X|]} {\displaystyle \|E[X]\|_{\psi _{2}}={\sqrt {\ln 2}}|E[X]|\leq {\sqrt {\ln 2}}E[|X|]\sim E[|X|]}. By the equivalence of definitions (2) and (4) of subgaussianity, we have E [ | X | ] ≲ ‖ X ‖ ψ 2 {\displaystyle E[|X|]\lesssim \|X\|_{\psi _{2}}} {\displaystyle E[|X|]\lesssim \|X\|_{\psi _{2}}}.

Independent subgaussian sum bound—If X , Y {\textstyle X,Y} {\textstyle X,Y} are subgaussian and independent, then ‖ X + Y ‖ v p 2 ≤ ‖ X ‖ v p 2 + ‖ Y ‖ v p 2 {\displaystyle \|X+Y\|_{vp}^{2}\leq \|X\|_{vp}^{2}+\|Y\|_{vp}^{2}} {\displaystyle \|X+Y\|_{vp}^{2}\leq \|X\|_{vp}^{2}+\|Y\|_{vp}^{2}}

Proof

If independent, then use that the cumulant of independent random variables is additive. That is, ln ⁡ E ⁡ [ e t ( X + Y ) ] = ln ⁡ E ⁡ [ e t X ] + ln ⁡ E ⁡ [ e t Y ] {\displaystyle \ln \operatorname {E} [e^{t(X+Y)}]=\ln \operatorname {E} [e^{tX}]+\ln \operatorname {E} [e^{tY}]} {\displaystyle \ln \operatorname {E} [e^{t(X+Y)}]=\ln \operatorname {E} [e^{tX}]+\ln \operatorname {E} [e^{tY}]}.

If not independent, then by Hölder's inequality, for any 1 / p + 1 / q = 1 {\displaystyle 1/p+1/q=1} {\displaystyle 1/p+1/q=1} we have E [ e t ( X + Y ) ] = ‖ e t ( X + Y ) ‖ 1 ≤ e 1 2 t 2 ( p ‖ X ‖ v p 2 + q ‖ Y ‖ v p 2 ) {\displaystyle E[e^{t(X+Y)}]=\|e^{t(X+Y)}\|_{1}\leq e^{{\frac {1}{2}}t^{2}(p\|X\|_{vp}^{2}+q\|Y\|_{vp}^{2})}} {\displaystyle E[e^{t(X+Y)}]=\|e^{t(X+Y)}\|_{1}\leq e^{{\frac {1}{2}}t^{2}(p\|X\|_{vp}^{2}+q\|Y\|_{vp}^{2})}} Solving the optimization problem { min p ‖ X ‖ v p 2 + q ‖ Y ‖ v p 2 1 / p + 1 / q = 1 {\displaystyle {\begin{cases}\min p\|X\|_{vp}^{2}+q\|Y\|_{vp}^{2}\\1/p+1/q=1\end{cases}}} {\displaystyle {\begin{cases}\min p\|X\|_{vp}^{2}+q\|Y\|_{vp}^{2}\\1/p+1/q=1\end{cases}}}, we obtain the result.

Corollary—Linear sums of subgaussian random variables are subgaussian.

Partial converse (Matoušek 2008, Lemma 2.4)—If E [ X ] = 0 , E [ X 2 ] = 1 {\textstyle E[X]=0,E[X^{2}]=1} {\textstyle E[X]=0,E[X^{2}]=1}, and − ln ⁡ P r ( X ≥ t ) ≥ 1 2 a t 2 {\textstyle -\ln Pr(X\geq t)\geq {\frac {1}{2}}at^{2}} {\textstyle -\ln Pr(X\geq t)\geq {\frac {1}{2}}at^{2}} for all t > 0 {\textstyle t>0} {\textstyle t>0}, then ln ⁡ E [ e t X ] ≤ C a t 2 {\displaystyle \ln E[e^{tX}]\leq C_{a}t^{2}} {\displaystyle \ln E[e^{tX}]\leq C_{a}t^{2}} where C a > 0 {\textstyle C_{a}>0} {\textstyle C_{a}>0} depends on a {\textstyle a} {\textstyle a} only.

Proof
Proof

Let F ( x ) {\textstyle F(x)} {\textstyle F(x)} be the CDF of X {\textstyle X} {\textstyle X}. The proof splits the integral of MGF to two halves, one with t X > 1 {\textstyle tX>1} {\textstyle tX>1} and one with t X ≤ 1 {\textstyle tX\leq 1} {\textstyle tX\leq 1}, and bound each one respectively.

E [ e t X ] = ∫ R e t x d F ( x ) = ∫ − ∞ 1 / t e t x d F ( x ) + ∫ 1 / t + ∞ e t x d F ( x ) {\displaystyle {\begin{aligned}E[e^{tX}]&=\int _{\mathbb {R} }e^{tx}dF(x)\\&=\int _{-\infty }^{1/t}e^{tx}dF(x)+\int _{1/t}^{+\infty }e^{tx}dF(x)\\\end{aligned}}} {\displaystyle {\begin{aligned}E[e^{tX}]&=\int _{\mathbb {R} }e^{tx}dF(x)\\&=\int _{-\infty }^{1/t}e^{tx}dF(x)+\int _{1/t}^{+\infty }e^{tx}dF(x)\\\end{aligned}}} Since e x ≤ 1 + x + x 2 {\textstyle e^{x}\leq 1+x+x^{2}} {\textstyle e^{x}\leq 1+x+x^{2}} for x ≤ 1 {\textstyle x\leq 1} {\textstyle x\leq 1}, ∫ − ∞ 1 / t e t x d F ( x ) ≤ ∫ − ∞ 1 / t ( 1 + t x + t 2 x 2 ) d F ( x ) ≤ ∫ R ( 1 + t x + t 2 x 2 ) d F ( x ) = 1 + t E [ X ] + t 2 E [ X 2 ] = 1 + t 2 ≤ e t 2 {\displaystyle {\begin{aligned}\int _{-\infty }^{1/t}e^{tx}dF(x)&\leq \int _{-\infty }^{1/t}(1+tx+t^{2}x^{2})dF(x)\\&\leq \int _{\mathbb {R} }(1+tx+t^{2}x^{2})dF(x)\\&=1+tE[X]+t^{2}E[X^{2}]\\&=1+t^{2}\\&\leq e^{t^{2}}\end{aligned}}} {\displaystyle {\begin{aligned}\int _{-\infty }^{1/t}e^{tx}dF(x)&\leq \int _{-\infty }^{1/t}(1+tx+t^{2}x^{2})dF(x)\\&\leq \int _{\mathbb {R} }(1+tx+t^{2}x^{2})dF(x)\\&=1+tE[X]+t^{2}E[X^{2}]\\&=1+t^{2}\\&\leq e^{t^{2}}\end{aligned}}} For the second term, upper bound it by a summation: ∫ 1 / t + ∞ e t x d F ( x ) ≤ e 2 P r ( X ∈ [ 1 / t , 2 / t ] ) + e 3 P r ( X ∈ [ 1 / t , 2 / t ] ) + … ≤ ∑ k = 1 ∞ e k + 1 P r ( X ≥ k / t ) ≤ ∑ k = 1 ∞ e k ( 2 − 1 2 a k / t 2 ) {\displaystyle {\begin{aligned}\int _{1/t}^{+\infty }e^{tx}dF(x)&\leq e^{2}Pr(X\in [1/t,2/t])+e^{3}Pr(X\in [1/t,2/t])+\dots \\&\leq \sum _{k=1}^{\infty }e^{k+1}Pr(X\geq k/t)\\&\leq \sum _{k=1}^{\infty }e^{k(2-{\frac {1}{2}}ak/t^{2})}\end{aligned}}} {\displaystyle {\begin{aligned}\int _{1/t}^{+\infty }e^{tx}dF(x)&\leq e^{2}Pr(X\in [1/t,2/t])+e^{3}Pr(X\in [1/t,2/t])+\dots \\&\leq \sum _{k=1}^{\infty }e^{k+1}Pr(X\geq k/t)\\&\leq \sum _{k=1}^{\infty }e^{k(2-{\frac {1}{2}}ak/t^{2})}\end{aligned}}} When t ≤ a / 8 {\textstyle t\leq {\sqrt {a/8}}} {\textstyle t\leq {\sqrt {a/8}}}, for any k ≥ 1 {\textstyle k\geq 1} {\textstyle k\geq 1}, 2 k − a k 2 2 t 2 ≤ − a k 4 t 2 {\textstyle 2k-{\frac {ak^{2}}{2t^{2}}}\leq -{\frac {ak}{4t^{2}}}} {\textstyle 2k-{\frac {ak^{2}}{2t^{2}}}\leq -{\frac {ak}{4t^{2}}}}, so

≤ 1 e a 4 t 2 − 1 ≤ 4 a t 2 {\displaystyle \leq {\frac {1}{e^{\frac {a}{4t^{2}}}-1}}\leq {\frac {4}{a}}t^{2}} {\displaystyle \leq {\frac {1}{e^{\frac {a}{4t^{2}}}-1}}\leq {\frac {4}{a}}t^{2}} When t > a / 8 {\textstyle t>{\sqrt {a/8}}} {\textstyle t>{\sqrt {a/8}}}, by drawing out the curve of f ( x ) = e − a 2 t 2 x 2 + 2 x {\textstyle f(x)=e^{-{\frac {a}{2t^{2}}}x^{2}+2x}} {\textstyle f(x)=e^{-{\frac {a}{2t^{2}}}x^{2}+2x}}, and plotting out the summation, we find that ∑ k = 1 ∞ e k ( 2 − 1 2 a k / t 2 ) ≤ ∫ R f ( x ) d x + 2 max x f ( x ) = e 2 t 2 a ( 2 π t 2 a + 2 ) < 10 t 2 / a e 2 t 2 a {\displaystyle \sum _{k=1}^{\infty }e^{k(2-{\frac {1}{2}}ak/t^{2})}\leq \int _{\mathbb {R} }f(x)dx+2\max _{x}f(x)=e^{\frac {2t^{2}}{a}}\left({\sqrt {\frac {2\pi t^{2}}{a}}}+2\right)<10{\sqrt {t^{2}/a}}e^{\frac {2t^{2}}{a}}} {\displaystyle \sum _{k=1}^{\infty }e^{k(2-{\frac {1}{2}}ak/t^{2})}\leq \int _{\mathbb {R} }f(x)dx+2\max _{x}f(x)=e^{\frac {2t^{2}}{a}}\left({\sqrt {\frac {2\pi t^{2}}{a}}}+2\right)<10{\sqrt {t^{2}/a}}e^{\frac {2t^{2}}{a}}} Now verify that ln ⁡ 10 + 1 2 ln ⁡ ( t 2 / a ) + 2 a t 2 < C a t 2 {\textstyle \ln 10+{\frac {1}{2}}\ln(t^{2}/a)+{\frac {2}{a}}t^{2}<C_{a}t^{2}} {\textstyle \ln 10+{\frac {1}{2}}\ln(t^{2}/a)+{\frac {2}{a}}t^{2}<C_{a}t^{2}}, where C a {\textstyle C_{a}} {\textstyle C_{a}} depends on a {\textstyle a} {\textstyle a} only.

Corollary (Matoušek 2008, Lemma 2.2)— X 1 , … , X n {\textstyle X_{1},\dots ,X_{n}} {\textstyle X_{1},\dots ,X_{n}} are independent random variables with the same upper subgaussian tail: − ln ⁡ P r ( X i ≥ t ) ≥ 1 2 a t 2 {\displaystyle -\ln Pr(X_{i}\geq t)\geq {\frac {1}{2}}at^{2}} {\displaystyle -\ln Pr(X_{i}\geq t)\geq {\frac {1}{2}}at^{2}} for all t > 0 {\textstyle t>0} {\textstyle t>0}. Also, E [ X i ] = 0 , E [ X i 2 ] = 1 {\textstyle E[X_{i}]=0,E[X_{i}^{2}]=1} {\textstyle E[X_{i}]=0,E[X_{i}^{2}]=1}, then for any unit vector v ∈ R n {\textstyle v\in \mathbb {R} ^{n}} {\textstyle v\in \mathbb {R} ^{n}}, the linear sum ∑ i v i X i {\textstyle \sum _{i}v_{i}X_{i}} {\textstyle \sum _{i}v_{i}X_{i}} has a subgaussian tail:
− ln ⁡ P r ( ∑ i v i X i ≥ t ) ≥ C a t 2 {\displaystyle -\ln Pr\left(\sum _{i}v_{i}X_{i}\geq t\right)\geq C_{a}t^{2}} {\displaystyle -\ln Pr\left(\sum _{i}v_{i}X_{i}\geq t\right)\geq C_{a}t^{2}} where C a > 0 {\textstyle C_{a}>0} {\textstyle C_{a}>0} depends only on a {\textstyle a} {\textstyle a}.


Concentration

Gaussian concentration inequality for Lipschitz functions (Tao 2012, Theorem 2.1.12.)—If f : R n → R {\textstyle f:\mathbb {R} ^{n}\to \mathbb {R} } {\textstyle f:\mathbb {R} ^{n}\to \mathbb {R} } is L {\textstyle L} {\textstyle L}-Lipschitz, and X ∼ N ( 0 , I ) {\textstyle X\sim N(0,I)} {\textstyle X\sim N(0,I)} is a standard gaussian vector, then f ( X ) {\textstyle f(X)} {\textstyle f(X)} concentrates around its expectation at a rate P r ( f ( X ) − E [ f ( X ) ] ≥ t ) ≤ e − 2 π 2 t 2 L 2 {\displaystyle Pr(f(X)-E[f(X)]\geq t)\leq e^{-{\frac {2}{\pi ^{2}}}{\frac {t^{2}}{L^{2}}}}} {\displaystyle Pr(f(X)-E[f(X)]\geq t)\leq e^{-{\frac {2}{\pi ^{2}}}{\frac {t^{2}}{L^{2}}}}} and similarly for the other tail.

Proof
Proof

By shifting and scaling, it suffices to prove the case where L = 1 {\textstyle L=1} {\textstyle L=1}, and E [ f ( X ) ] = 0 {\textstyle E[f(X)]=0} {\textstyle E[f(X)]=0}.

Since every 1-Lipschitz function is uniformly approximable by 1-Lipschitz smooth functions (by convolving with a mollifier), it suffices to prove it for 1-Lipschitz smooth functions.

Now it remains to bound the cumulant generating function.

To exploit the Lipschitzness, we introduce Y {\textstyle Y} {\textstyle Y}, an independent copy of X {\textstyle X} {\textstyle X}, then by Jensen, E [ e t ( X − Y ) ] = E [ e t X ] E [ e − t Y ] ≥ E [ e t X ] e − t E [ Y ] = E [ e t X ] {\displaystyle E[e^{t(X-Y)}]=E[e^{tX}]E[e^{-tY}]\geq E[e^{tX}]e^{-tE[Y]}=E[e^{tX}]} {\displaystyle E[e^{t(X-Y)}]=E[e^{tX}]E[e^{-tY}]\geq E[e^{tX}]e^{-tE[Y]}=E[e^{tX}]}

By the circular symmetry of gaussian variables, we introduce X θ := Y cos ⁡ θ + X sin ⁡ θ {\textstyle X_{\theta }:=Y\cos \theta +X\sin \theta } {\textstyle X_{\theta }:=Y\cos \theta +X\sin \theta }. This has the benefit that its derivative X ′ = − Y sin ⁡ θ + X cos ⁡ θ {\textstyle X'=-Y\sin \theta +X\cos \theta } {\textstyle X'=-Y\sin \theta +X\cos \theta } is independent of it.

e t ( f ( X ) − f ( Y ) ) = e t ( f ( X π / 2 ) − f ( X 0 ) ) = e t ∫ 0 π / 2 ∇ f ( X θ ) ⋅ X θ ′ d θ = e π t / 2 ∫ 0 π / 2 ∇ f ( X θ ) ⋅ X θ ′ d θ π / 2 ≤ ∫ 0 π / 2 e π t / 2 ∇ f ( X θ ) ⋅ X θ ′ d θ π / 2 {\displaystyle {\begin{aligned}e^{t(f(X)-f(Y))}&=e^{t(f(X_{\pi /2})-f(X_{0}))}\\&=e^{t\int _{0}^{\pi /2}\nabla f(X_{\theta })\cdot X_{\theta }'d\theta }\\&=e^{\pi t/2\int _{0}^{\pi /2}\nabla f(X_{\theta })\cdot X_{\theta }'{\frac {d\theta }{\pi /2}}}\\&\leq \int _{0}^{\pi /2}e^{\pi t/2\nabla f(X_{\theta })\cdot X_{\theta }'}{\frac {d\theta }{\pi /2}}\\\end{aligned}}} {\displaystyle {\begin{aligned}e^{t(f(X)-f(Y))}&=e^{t(f(X_{\pi /2})-f(X_{0}))}\\&=e^{t\int _{0}^{\pi /2}\nabla f(X_{\theta })\cdot X_{\theta }'d\theta }\\&=e^{\pi t/2\int _{0}^{\pi /2}\nabla f(X_{\theta })\cdot X_{\theta }'{\frac {d\theta }{\pi /2}}}\\&\leq \int _{0}^{\pi /2}e^{\pi t/2\nabla f(X_{\theta })\cdot X_{\theta }'}{\frac {d\theta }{\pi /2}}\\\end{aligned}}}

Now take its expectation, E [ e t ( f ( X ) − f ( Y ) ) ] ≤ ∫ 0 π / 2 E [ e π t / 2 ∇ f ( X θ ) ⋅ X θ ′ ] d θ π / 2 {\displaystyle E[e^{t(f(X)-f(Y))}]\leq \int _{0}^{\pi /2}E[e^{\pi t/2\nabla f(X_{\theta })\cdot X_{\theta }'}]{\frac {d\theta }{\pi /2}}} {\displaystyle E[e^{t(f(X)-f(Y))}]\leq \int _{0}^{\pi /2}E[e^{\pi t/2\nabla f(X_{\theta })\cdot X_{\theta }'}]{\frac {d\theta }{\pi /2}}} The expectation within the integral is over the joint distribution of X , Y {\textstyle X,Y} {\textstyle X,Y}, but since the joint distribution of X θ , X θ ′ {\textstyle X_{\theta },X_{\theta }'} {\textstyle X_{\theta },X_{\theta }'} is exactly the same, we have

= E X [ E Y [ e π t / 2 ∇ f ( X ) ⋅ Y ] ] {\displaystyle =E_{X}[E_{Y}[e^{\pi t/2\nabla f(X)\cdot Y}]]} {\displaystyle =E_{X}[E_{Y}[e^{\pi t/2\nabla f(X)\cdot Y}]]}

Conditional on X {\textstyle X} {\textstyle X}, the quantity ∇ f ( X ) ⋅ Y {\textstyle \nabla f(X)\cdot Y} {\textstyle \nabla f(X)\cdot Y} is normally distributed, with variance ≤ 1 {\textstyle \leq 1} {\textstyle \leq 1}, so ≤ e 1 2 ( π t / 2 ) 2 = e π 2 8 t 2 {\displaystyle \leq e^{{\frac {1}{2}}(\pi t/2)^{2}}=e^{{\frac {\pi ^{2}}{8}}t^{2}}} {\displaystyle \leq e^{{\frac {1}{2}}(\pi t/2)^{2}}=e^{{\frac {\pi ^{2}}{8}}t^{2}}}

Thus, we have ln ⁡ E [ e t f ( X ) ] ≤ π 2 8 t 2 {\displaystyle \ln E[e^{tf(X)}]\leq {\frac {\pi ^{2}}{8}}t^{2}} {\displaystyle \ln E[e^{tf(X)}]\leq {\frac {\pi ^{2}}{8}}t^{2}}


Strictly subgaussian

Expanding the cumulant generating function: 1 2 s 2 t 2 ≥ ln ⁡ E ⁡ [ e t X ] = 1 2 V a r [ X ] t 2 + κ 3 t 3 + ⋯ {\displaystyle {\frac {1}{2}}s^{2}t^{2}\geq \ln \operatorname {E} [e^{tX}]={\frac {1}{2}}\mathrm {Var} [X]t^{2}+\kappa _{3}t^{3}+\cdots } {\displaystyle {\frac {1}{2}}s^{2}t^{2}\geq \ln \operatorname {E} [e^{tX}]={\frac {1}{2}}\mathrm {Var} [X]t^{2}+\kappa _{3}t^{3}+\cdots }we find that V a r [ X ] ≤ ‖ X ‖ v p 2 {\displaystyle \mathrm {Var} [X]\leq \|X\|_{\mathrm {vp} }^{2}} {\displaystyle \mathrm {Var} [X]\leq \|X\|_{\mathrm {vp} }^{2}}. At the edge of possibility, we define that a random variable X {\displaystyle X} {\displaystyle X} satisfying V a r [ X ] = ‖ X ‖ v p 2 {\displaystyle \mathrm {Var} [X]=\|X\|_{\mathrm {vp} }^{2}} {\displaystyle \mathrm {Var} [X]=\|X\|_{\mathrm {vp} }^{2}} is called strictly subgaussian.

Properties


Theorem.[6] Let X {\displaystyle X} {\displaystyle X} be a subgaussian random variable with mean zero. If all zeros of its characteristic function are real, then X {\displaystyle X} {\displaystyle X} is strictly subgaussian.

Corollary. If X 1 , … , X n {\displaystyle X_{1},\dots ,X_{n}} {\displaystyle X_{1},\dots ,X_{n}} are independent and strictly subgaussian, then any linear sum of them is strictly subgaussian.

Examples

By calculating the characteristic functions, we can show that some distributions are strictly subgaussian: symmetric uniform distribution, symmetric Bernoulli distribution.

Since a symmetric uniform distribution is strictly subgaussian, its convolution with itself is strictly subgaussian. That is, the symmetric triangular distribution is strictly subgaussian.

Since the symmetric Bernoulli distribution is strictly subgaussian, any symmetric Binomial distribution is strictly subgaussian.

Examples

‖ X ‖ ψ 2 {\displaystyle \|X\|_{\psi _{2}}} {\displaystyle \|X\|_{\psi _{2}}} ‖ X ‖ v p 2 {\displaystyle \|X\|_{vp}^{2}} {\displaystyle \|X\|_{vp}^{2}} strictly subgaussian?
gaussian distribution N ( 0 , 1 ) {\displaystyle {\mathcal {N}}(0,1)} {\displaystyle {\mathcal {N}}(0,1)} 8 / 3 {\displaystyle {\sqrt {8/3}}} {\displaystyle {\sqrt {8/3}}} 1 {\displaystyle 1} {\displaystyle 1} Yes
mean-zero Bernoulli distribution p δ q + q δ − p {\displaystyle p\delta _{q}+q\delta _{-p}} {\displaystyle p\delta _{q}+q\delta _{-p}} solution to p e ( q / t ) 2 + q e ( p / t ) 2 = 2 {\displaystyle pe^{(q/t)^{2}}+qe^{(p/t)^{2}}=2} {\displaystyle pe^{(q/t)^{2}}+qe^{(p/t)^{2}}=2} p − q 2 ( log ⁡ p − log ⁡ q ) {\displaystyle {\frac {p-q}{2(\log p-\log q)}}} {\displaystyle {\frac {p-q}{2(\log p-\log q)}}} Iff p = 0 , 1 / 2 , 1 {\displaystyle p=0,1/2,1} {\displaystyle p=0,1/2,1}
symmetric Bernoulli distribution 1 2 δ 1 / 2 + 1 2 δ − 1 / 2 {\displaystyle {\frac {1}{2}}\delta _{1/2}+{\frac {1}{2}}\delta _{-1/2}} {\displaystyle {\frac {1}{2}}\delta _{1/2}+{\frac {1}{2}}\delta _{-1/2}} 1 ln ⁡ 2 {\displaystyle {\frac {1}{\sqrt {\ln 2}}}} {\displaystyle {\frac {1}{\sqrt {\ln 2}}}} 1 {\displaystyle 1} {\displaystyle 1} Yes
uniform distribution U ( 0 , 1 ) {\displaystyle U(0,1)} {\displaystyle U(0,1)} solution to ∫ 0 1 e x 2 / t 2 d x = 2 {\displaystyle \int _{0}^{1}e^{x^{2}/t^{2}}dx=2} {\displaystyle \int _{0}^{1}e^{x^{2}/t^{2}}dx=2}, approximately 0.7727 1 / 3 {\displaystyle 1/3} {\displaystyle 1/3} Yes
arbitrary distribution on interval [ a , b ] {\displaystyle [a,b]} {\displaystyle [a,b]} ≤ ( b − a 2 ) 2 {\displaystyle \leq \left({\frac {b-a}{2}}\right)^{2}} {\displaystyle \leq \left({\frac {b-a}{2}}\right)^{2}}

The optimal variance proxy ‖ X ‖ v p 2 {\displaystyle \Vert X\Vert _{\mathrm {vp} }^{2}} {\displaystyle \Vert X\Vert _{\mathrm {vp} }^{2}} is known for many standard probability distributions, including the beta, Bernoulli, Dirichlet[7], Kumaraswamy, triangular[8], truncated Gaussian, and truncated exponential.[9]

Bernoulli distribution

Let p + q = 1 {\displaystyle p+q=1} {\displaystyle p+q=1} be two positive numbers. Let X {\displaystyle X} {\displaystyle X} be a centered Bernoulli distribution p δ q + q δ − p {\displaystyle p\delta _{q}+q\delta _{-p}} {\displaystyle p\delta _{q}+q\delta _{-p}}, so that it has mean zero, then ‖ X ‖ v p 2 = p − q 2 ( log ⁡ p − log ⁡ q ) {\displaystyle \Vert X\Vert _{\mathrm {vp} }^{2}={\frac {p-q}{2(\log p-\log q)}}} {\displaystyle \Vert X\Vert _{\mathrm {vp} }^{2}={\frac {p-q}{2(\log p-\log q)}}}.[6] Its subgaussian norm is t {\displaystyle t} {\displaystyle t} where t {\displaystyle t} {\displaystyle t} is the unique positive solution to p e ( q / t ) 2 + q e ( p / t ) 2 = 2 {\displaystyle pe^{(q/t)^{2}}+qe^{(p/t)^{2}}=2} {\displaystyle pe^{(q/t)^{2}}+qe^{(p/t)^{2}}=2}.

Let X {\displaystyle X} {\displaystyle X} be a random variable with symmetric Bernoulli distribution (or Rademacher distribution). That is, X {\displaystyle X} {\displaystyle X} takes values − 1 {\displaystyle -1} {\displaystyle -1} and 1 {\displaystyle 1} {\displaystyle 1} with probabilities 1 / 2 {\displaystyle 1/2} {\displaystyle 1/2} each. Since X 2 = 1 {\displaystyle X^{2}=1} {\displaystyle X^{2}=1}, it follows that ‖ X ‖ ψ 2 = inf { c > 0 : E ⁡ [ exp ⁡ ( X 2 c 2 ) ] ≤ 2 } = inf { c > 0 : exp ⁡ ( 1 c 2 ) ≤ 2 } = 1 ln ⁡ 2 , {\displaystyle \Vert X\Vert _{\psi _{2}}=\inf \left\{c>0:\operatorname {E} \left[\exp {\left({\frac {X^{2}}{c^{2}}}\right)}\right]\leq 2\right\}=\inf \left\{c>0:\exp {\left({\frac {1}{c^{2}}}\right)}\leq 2\right\}={\frac {1}{\sqrt {\ln 2}}},} {\displaystyle \Vert X\Vert _{\psi _{2}}=\inf \left\{c>0:\operatorname {E} \left[\exp {\left({\frac {X^{2}}{c^{2}}}\right)}\right]\leq 2\right\}=\inf \left\{c>0:\exp {\left({\frac {1}{c^{2}}}\right)}\leq 2\right\}={\frac {1}{\sqrt {\ln 2}}},}and hence X {\displaystyle X} {\displaystyle X} is a subgaussian random variable.

Bounded distributions

Some commonly used bounded distributions.

Bounded distributions have no tail at all, so clearly they are subgaussian.

If X {\displaystyle X} {\displaystyle X} is bounded within the interval [ a , b ] {\displaystyle [a,b]} {\displaystyle [a,b]}, Hoeffding's lemma states that ‖ X ‖ v p 2 ≤ ( b − a 2 ) 2 {\displaystyle \Vert X\Vert _{\mathrm {vp} }^{2}\leq \left({\frac {b-a}{2}}\right)^{2}} {\displaystyle \Vert X\Vert _{\mathrm {vp} }^{2}\leq \left({\frac {b-a}{2}}\right)^{2}}. Hoeffding's inequality is the Chernoff bound obtained using this fact.

Convolutions

Density of a mixture of three normal distributions (μ = 5, 10, 15, σ = 2) with equal weights. Each component is shown as a weighted density (each integrating to 1/3)

Since the sum of subgaussian random variables is still subgaussian, the convolution of subgaussian distributions is still subgaussian. In particular, any convolution of the normal distribution with any bounded distribution is subgaussian.

Mixtures

Given subgaussian distributions X 1 , X 2 , … , X n {\displaystyle X_{1},X_{2},\dots ,X_{n}} {\displaystyle X_{1},X_{2},\dots ,X_{n}}, we can construct an additive mixture X {\displaystyle X} {\displaystyle X} as follows: first randomly pick a number i ∈ { 1 , 2 , … , n } {\displaystyle i\in \{1,2,\dots ,n\}} {\displaystyle i\in \{1,2,\dots ,n\}}, then pick X i {\displaystyle X_{i}} {\displaystyle X_{i}}.

Since E ⁡ [ exp ⁡ ( X 2 c 2 ) ] = ∑ i p i E ⁡ [ exp ⁡ ( X i 2 c 2 ) ] {\displaystyle \operatorname {E} \left[\exp {\left({\frac {X^{2}}{c^{2}}}\right)}\right]=\sum _{i}p_{i}\operatorname {E} \left[\exp {\left({\frac {X_{i}^{2}}{c^{2}}}\right)}\right]} {\displaystyle \operatorname {E} \left[\exp {\left({\frac {X^{2}}{c^{2}}}\right)}\right]=\sum _{i}p_{i}\operatorname {E} \left[\exp {\left({\frac {X_{i}^{2}}{c^{2}}}\right)}\right]}we have ‖ X ‖ ψ 2 ≤ max i ‖ X i ‖ ψ 2 {\displaystyle \|X\|_{\psi _{2}}\leq \max _{i}\|X_{i}\|_{\psi _{2}}} {\displaystyle \|X\|_{\psi _{2}}\leq \max _{i}\|X_{i}\|_{\psi _{2}}}, and so the mixture is subgaussian.

In particular, any gaussian mixture is subgaussian.

More generally, the mixture of infinitely many subgaussian distributions is also subgaussian, if the subgaussian norm has a finite supremum: ‖ X ‖ ψ 2 ≤ sup i ‖ X i ‖ ψ 2 {\displaystyle \|X\|_{\psi _{2}}\leq \sup _{i}\|X_{i}\|_{\psi _{2}}} {\displaystyle \|X\|_{\psi _{2}}\leq \sup _{i}\|X_{i}\|_{\psi _{2}}}.

Subgaussian random vectors

So far, we have discussed subgaussianity for real-valued random variables. We can also define subgaussianity for random vectors. The purpose of subgaussianity is to make the tails decay fast, so we generalize accordingly: a subgaussian random vector is a random vector where the tail decays fast.

Let X {\displaystyle X} {\displaystyle X} be a random vector taking values in R n {\displaystyle \mathbb {R} ^{n}} {\displaystyle \mathbb {R} ^{n}}.

Define.

  • ‖ X ‖ ψ 2 := sup v ∈ S n − 1 ‖ v T X ‖ ψ 2 {\displaystyle \|X\|_{\psi _{2}}:=\sup _{v\in S^{n-1}}\|v^{T}X\|_{\psi _{2}}} {\displaystyle \|X\|_{\psi _{2}}:=\sup _{v\in S^{n-1}}\|v^{T}X\|_{\psi _{2}}}, where S n − 1 {\displaystyle S^{n-1}} {\displaystyle S^{n-1}} is the unit sphere in R n {\displaystyle \mathbb {R} ^{n}} {\displaystyle \mathbb {R} ^{n}}. Similarly for the variance proxy ‖ X ‖ v p := sup v ∈ S n − 1 ‖ v T X ‖ v p {\displaystyle \|X\|_{vp}:=\sup _{v\in S^{n-1}}\|v^{T}X\|_{vp}} {\displaystyle \|X\|_{vp}:=\sup _{v\in S^{n-1}}\|v^{T}X\|_{vp}}
  • X {\displaystyle X} {\displaystyle X} is subgaussian iff ‖ X ‖ ψ 2 < ∞ {\displaystyle \|X\|_{\psi _{2}}<\infty } {\displaystyle \|X\|_{\psi _{2}}<\infty }.

Theorem. (Theorem 3.4.6 [3]) For any positive integer n {\displaystyle n} {\displaystyle n}, the uniformly distributed random vector X ∼ U ( n S n − 1 ) {\displaystyle X\sim U({\sqrt {n}}S^{n-1})} {\displaystyle X\sim U({\sqrt {n}}S^{n-1})} is subgaussian, with ‖ X ‖ ψ 2 ≲ 1 {\displaystyle \|X\|_{\psi _{2}}\lesssim {}1} {\displaystyle \|X\|_{\psi _{2}}\lesssim {}1}.

This is not so surprising, because as n → ∞ {\displaystyle n\to \infty } {\displaystyle n\to \infty }, the projection of U ( n S n − 1 ) {\displaystyle U({\sqrt {n}}S^{n-1})} {\displaystyle U({\sqrt {n}}S^{n-1})} to the first coordinate converges in distribution to the standard normal distribution.

Maximum inequalities


Theorem—If X 1 , … , X n {\displaystyle X_{1},\dots ,X_{n}} {\displaystyle X_{1},\dots ,X_{n}} are mean-zero subgaussians, with ‖ X i ‖ v p 2 ≤ σ 2 {\displaystyle \|X_{i}\|_{vp}^{2}\leq \sigma ^{2}} {\displaystyle \|X_{i}\|_{vp}^{2}\leq \sigma ^{2}}, then for any δ > 0 {\displaystyle \delta >0} {\displaystyle \delta >0}, we have max ( X 1 , … , X n ) ≤ σ 2 ln ⁡ n δ {\displaystyle \max(X_{1},\dots ,X_{n})\leq \sigma {\sqrt {2\ln {\frac {n}{\delta }}}}} {\displaystyle \max(X_{1},\dots ,X_{n})\leq \sigma {\sqrt {2\ln {\frac {n}{\delta }}}}} with probability ≥ 1 − δ {\displaystyle \geq 1-\delta } {\displaystyle \geq 1-\delta }.

Proof

By the Chernoff bound, Pr ( X i ≥ σ 2 ln ⁡ ( n / δ ) ) ≤ δ / n {\displaystyle \Pr(X_{i}\geq \sigma {\sqrt {2\ln(n/\delta )}})\leq \delta /n} {\displaystyle \Pr(X_{i}\geq \sigma {\sqrt {2\ln(n/\delta )}})\leq \delta /n}. Now apply the union bound.


Theorem (Exercise 2.5.10 [3])—If X 1 , X 2 , … {\displaystyle X_{1},X_{2},\dots } {\displaystyle X_{1},X_{2},\dots } are subgaussians, with ‖ X i ‖ ψ 2 ≤ K {\displaystyle \|X_{i}\|_{\psi _{2}}\leq K} {\displaystyle \|X_{i}\|_{\psi _{2}}\leq K}, then E [ sup n | X n | 1 + ln ⁡ n ] ≲ K , E [ max 1 ≤ n ≤ N | X n | ] ≲ K ln ⁡ N {\displaystyle E\left[\sup _{n}{\frac {|X_{n}|}{\sqrt {1+\ln n}}}\right]\lesssim K,\quad E\left[\max _{1\leq n\leq N}|X_{n}|\right]\lesssim K{\sqrt {\ln N}}} {\displaystyle E\left[\sup _{n}{\frac {|X_{n}|}{\sqrt {1+\ln n}}}\right]\lesssim K,\quad E\left[\max _{1\leq n\leq N}|X_{n}|\right]\lesssim K{\sqrt {\ln N}}}Further, the bound is sharp, since when X 1 , X 2 , … {\displaystyle X_{1},X_{2},\dots } {\displaystyle X_{1},X_{2},\dots } are IID samples of N ( 0 , 1 ) {\displaystyle {\mathcal {N}}(0,1)} {\displaystyle {\mathcal {N}}(0,1)} we have E [ max 1 ≤ n ≤ N | X n | ] ≳ ln ⁡ N {\displaystyle E\left[\max _{1\leq n\leq N}|X_{n}|\right]\gtrsim {\sqrt {\ln N}}} {\displaystyle E\left[\max _{1\leq n\leq N}|X_{n}|\right]\gtrsim {\sqrt {\ln N}}}.[10]


Theorem (over a finite set[11])—If X 1 , … , X n {\displaystyle X_{1},\dots ,X_{n}} {\displaystyle X_{1},\dots ,X_{n}} are subgaussian, with ‖ X i ‖ v p 2 ≤ σ 2 {\displaystyle \|X_{i}\|_{vp}^{2}\leq \sigma ^{2}} {\displaystyle \|X_{i}\|_{vp}^{2}\leq \sigma ^{2}}, then E [ max i ( X i − E [ X i ] ) ] ≤ σ 2 ln ⁡ n , Pr ( max i ( X i − E [ X i ] ) > t ) ≤ n e − t 2 2 σ 2 , E [ max i | X i − E [ X i ] | ] ≤ σ 2 ln ⁡ ( 2 n ) , Pr ( max i | X i − E [ X i ] | > t ) ≤ 2 n e − t 2 2 σ 2 {\displaystyle {\begin{aligned}E[\max _{i}(X_{i}-E[X_{i}])]\leq \sigma {\sqrt {2\ln n}},&\quad \Pr(\max _{i}(X_{i}-E[X_{i}])>t)\leq ne^{-{\frac {t^{2}}{2\sigma ^{2}}}},\\E[\max _{i}|X_{i}-E[X_{i}]|]\leq \sigma {\sqrt {2\ln(2n)}},&\quad \Pr(\max _{i}|X_{i}-E[X_{i}]|>t)\leq 2ne^{-{\frac {t^{2}}{2\sigma ^{2}}}}\end{aligned}}} {\displaystyle {\begin{aligned}E[\max _{i}(X_{i}-E[X_{i}])]\leq \sigma {\sqrt {2\ln n}},&\quad \Pr(\max _{i}(X_{i}-E[X_{i}])>t)\leq ne^{-{\frac {t^{2}}{2\sigma ^{2}}}},\\E[\max _{i}|X_{i}-E[X_{i}]|]\leq \sigma {\sqrt {2\ln(2n)}},&\quad \Pr(\max _{i}|X_{i}-E[X_{i}]|>t)\leq 2ne^{-{\frac {t^{2}}{2\sigma ^{2}}}}\end{aligned}}}

Proof

For any t>0: E [ max 1 ≤ i ≤ n ( X i − E [ X i ] ) ] = 1 t E [ ln ⁡ max i e t ( X i − E [ X i ] ) ] ≤ 1 t ln ⁡ E [ max i e t ( X i − E [ X i ] ) ] by Jensen ≤ 1 t ln ⁡ ∑ i = 1 n E e t ( X i − E [ X i ] ) ≤ 1 t ln ⁡ ∑ i = 1 n e σ 2 t 2 / 2 by def of  ‖ ⋅ ‖ v p = ln ⁡ n t + σ 2 t 2 = t = 2 ln ⁡ n / σ σ 2 ln ⁡ n , {\displaystyle {\begin{aligned}E\!{\bigl [}\max _{1\leq i\leq n}(X_{i}-E[X_{i}]){\bigr ]}&={\frac {1}{t}}\,E\!{\Bigl [}\ln \max _{i}e^{\,t(X_{i}-E[X_{i}])}{\Bigr ]}\\&\leq {\frac {1}{t}}\ln E\!{\Bigl [}\max _{i}e^{\,t(X_{i}-E[X_{i}])}{\Bigr ]}\quad {\text{by Jensen}}\\&\leq {\frac {1}{t}}\ln \sum _{i=1}^{n}Ee^{t(X_{i}-E[X_{i}])}\\&\leq {\frac {1}{t}}\ln \sum _{i=1}^{n}e^{\sigma ^{2}t^{2}/2}\quad {\text{by def of }}\|\cdot \|_{vp}\\&={\frac {\ln n}{t}}+{\frac {\sigma ^{2}t}{2}}\\&{\overset {t={\sqrt {2\ln n}}/\sigma }{=}}\;\sigma {\sqrt {2\ln n}},\end{aligned}}} {\displaystyle {\begin{aligned}E\!{\bigl [}\max _{1\leq i\leq n}(X_{i}-E[X_{i}]){\bigr ]}&={\frac {1}{t}}\,E\!{\Bigl [}\ln \max _{i}e^{\,t(X_{i}-E[X_{i}])}{\Bigr ]}\\&\leq {\frac {1}{t}}\ln E\!{\Bigl [}\max _{i}e^{\,t(X_{i}-E[X_{i}])}{\Bigr ]}\quad {\text{by Jensen}}\\&\leq {\frac {1}{t}}\ln \sum _{i=1}^{n}Ee^{t(X_{i}-E[X_{i}])}\\&\leq {\frac {1}{t}}\ln \sum _{i=1}^{n}e^{\sigma ^{2}t^{2}/2}\quad {\text{by def of }}\|\cdot \|_{vp}\\&={\frac {\ln n}{t}}+{\frac {\sigma ^{2}t}{2}}\\&{\overset {t={\sqrt {2\ln n}}/\sigma }{=}}\;\sigma {\sqrt {2\ln n}},\end{aligned}}}This is a standard proof structure for proving Chernoff-like bounds for sub-Gaussian variables. For the second equation, it suffices to prove the case with one variable and zero mean, then use the union bound. First by Markov, Pr ( X > t ) ≤ Pr ( e s X > e s t ) ≤ e − s t E [ e s X ] {\displaystyle \Pr(X>t)\leq \Pr(e^{sX}>e^{st})\leq e^{-st}E[e^{sX}]} {\displaystyle \Pr(X>t)\leq \Pr(e^{sX}>e^{st})\leq e^{-st}E[e^{sX}]}, then by definition of variance proxy, ≤ e − s t e σ 2 s 2 / 2 {\displaystyle \leq e^{-st}e^{\sigma ^{2}s^{2}/2}} {\displaystyle \leq e^{-st}e^{\sigma ^{2}s^{2}/2}}, and then optimize at s = − t 2 / 2 σ 2 {\displaystyle s=-t^{2}/2\sigma ^{2}} {\displaystyle s=-t^{2}/2\sigma ^{2}}.

Corollary (over a convex polytope)—Fix a finite set of vectors v 1 , … , v n {\displaystyle v_{1},\dots ,v_{n}} {\displaystyle v_{1},\dots ,v_{n}}. If X {\displaystyle X} {\displaystyle X} is a random vector, such that each ‖ v i T X ‖ v p 2 ≤ σ 2 {\displaystyle \|v_{i}^{T}X\|_{vp}^{2}\leq \sigma ^{2}} {\displaystyle \|v_{i}^{T}X\|_{vp}^{2}\leq \sigma ^{2}}, then the above 4 inequalities hold, with max v ∈ c o n v ( v 1 , … , v n ) ( v T X − E [ v T X ] ) {\displaystyle \max _{v\in \mathrm {conv} (v_{1},\dots ,v_{n})}(v^{T}X-E[v^{T}X])} {\displaystyle \max _{v\in \mathrm {conv} (v_{1},\dots ,v_{n})}(v^{T}X-E[v^{T}X])} replacing max i ( X i − E [ X i ] ) {\displaystyle \max _{i}(X_{i}-E[X_{i}])} {\displaystyle \max _{i}(X_{i}-E[X_{i}])}. Here, c o n v ( v 1 , … , v n ) {\displaystyle \mathrm {conv} (v_{1},\dots ,v_{n})} {\displaystyle \mathrm {conv} (v_{1},\dots ,v_{n})} is the convex polytope hulled by the vectors v 1 , … , v n {\displaystyle v_{1},\dots ,v_{n}} {\displaystyle v_{1},\dots ,v_{n}}.

Theorem (subgaussian random vectors)—If X {\displaystyle X} {\displaystyle X} is a random vector in R d {\displaystyle \mathbb {R} ^{d}} {\displaystyle \mathbb {R} ^{d}}, such that ‖ v T X ‖ v p 2 ≤ σ 2 {\displaystyle \|v^{T}X\|_{vp}^{2}\leq \sigma ^{2}} {\displaystyle \|v^{T}X\|_{vp}^{2}\leq \sigma ^{2}} for all v {\displaystyle v} {\displaystyle v} on the unit sphere S {\displaystyle S} {\displaystyle S}, then E [ max v ∈ S v T X ] = E [ max v ∈ S | v T X | ] ≤ 4 σ d {\displaystyle E[\max _{v\in S}v^{T}X]=E[\max _{v\in S}|v^{T}X|]\leq 4\sigma {\sqrt {d}}} {\displaystyle E[\max _{v\in S}v^{T}X]=E[\max _{v\in S}|v^{T}X|]\leq 4\sigma {\sqrt {d}}}For any δ > 0 {\displaystyle \delta >0} {\displaystyle \delta >0}, with probability at least 1 − δ {\displaystyle 1-\delta } {\displaystyle 1-\delta }, max v ∈ S v T X = max v ∈ S | v T X | ≤ 4 σ d + 2 σ 2 log ⁡ ( 1 / δ ) {\displaystyle \max _{v\in S}v^{T}X=\max _{v\in S}|v^{T}X|\leq 4\sigma {\sqrt {d}}+2\sigma {\sqrt {2\log(1/\delta )}}} {\displaystyle \max _{v\in S}v^{T}X=\max _{v\in S}|v^{T}X|\leq 4\sigma {\sqrt {d}}+2\sigma {\sqrt {2\log(1/\delta )}}}

Inequalities

Theorem. (Theorem 2.6.1 [3]) There exists a positive constant C {\displaystyle C} {\displaystyle C} such that given any number of independent mean-zero subgaussian random variables X 1 , … , X n {\displaystyle X_{1},\dots ,X_{n}} {\displaystyle X_{1},\dots ,X_{n}}, ‖ ∑ i = 1 n X i ‖ ψ 2 2 ≤ C ∑ i = 1 n ‖ X i ‖ ψ 2 2 {\displaystyle \left\|\sum _{i=1}^{n}X_{i}\right\|_{\psi _{2}}^{2}\leq C\sum _{i=1}^{n}\left\|X_{i}\right\|_{\psi _{2}}^{2}} {\displaystyle \left\|\sum _{i=1}^{n}X_{i}\right\|_{\psi _{2}}^{2}\leq C\sum _{i=1}^{n}\left\|X_{i}\right\|_{\psi _{2}}^{2}}Theorem. (Hoeffding's inequality) (Theorem 2.6.3 [3]) There exists a positive constant c {\displaystyle c} {\displaystyle c} such that given any number of independent mean-zero subgaussian random variables X 1 , … , X N {\displaystyle X_{1},\dots ,X_{N}} {\displaystyle X_{1},\dots ,X_{N}}, P ( | ∑ i = 1 N X i | ≥ t ) ≤ 2 exp ⁡ ( − c t 2 ∑ i = 1 N ‖ X i ‖ ψ 2 2 ) ∀ t > 0 {\displaystyle \mathbb {P} \left(\left|\sum _{i=1}^{N}X_{i}\right|\geq t\right)\leq 2\exp \left(-{\frac {ct^{2}}{\sum _{i=1}^{N}\left\|X_{i}\right\|_{\psi _{2}}^{2}}}\right)\quad \forall t>0} {\displaystyle \mathbb {P} \left(\left|\sum _{i=1}^{N}X_{i}\right|\geq t\right)\leq 2\exp \left(-{\frac {ct^{2}}{\sum _{i=1}^{N}\left\|X_{i}\right\|_{\psi _{2}}^{2}}}\right)\quad \forall t>0}Theorem. (Bernstein's inequality) (Theorem 2.8.1 [3]) There exists a positive constant c {\displaystyle c} {\displaystyle c} such that given any number of independent mean-zero subexponential random variables X 1 , … , X N {\displaystyle X_{1},\dots ,X_{N}} {\displaystyle X_{1},\dots ,X_{N}}, P ( | ∑ i = 1 N X i | ≥ t ) ≤ 2 exp ⁡ ( − c min ( t 2 ∑ i = 1 N ‖ X i ‖ ψ 1 2 , t max i ‖ X i ‖ ψ 1 ) ) {\displaystyle \mathbb {P} \left(\left|\sum _{i=1}^{N}X_{i}\right|\geq t\right)\leq 2\exp \left(-c\min \left({\frac {t^{2}}{\sum _{i=1}^{N}\left\|X_{i}\right\|_{\psi _{1}}^{2}}},{\frac {t}{\max _{i}\left\|X_{i}\right\|_{\psi _{1}}}}\right)\right)} {\displaystyle \mathbb {P} \left(\left|\sum _{i=1}^{N}X_{i}\right|\geq t\right)\leq 2\exp \left(-c\min \left({\frac {t^{2}}{\sum _{i=1}^{N}\left\|X_{i}\right\|_{\psi _{1}}^{2}}},{\frac {t}{\max _{i}\left\|X_{i}\right\|_{\psi _{1}}}}\right)\right)} Theorem. (Khinchine inequality) (Exercise 2.6.5 [3]) There exists a positive constant C {\displaystyle C} {\displaystyle C} such that given any number of independent mean-zero variance-one subgaussian random variables X 1 , … , X N {\displaystyle X_{1},\dots ,X_{N}} {\displaystyle X_{1},\dots ,X_{N}}, any p ≥ 2 {\displaystyle p\geq 2} {\displaystyle p\geq 2}, and any a 1 , … , a N ∈ R {\displaystyle a_{1},\dots ,a_{N}\in \mathbb {R} } {\displaystyle a_{1},\dots ,a_{N}\in \mathbb {R} }, ( ∑ i = 1 N a i 2 ) 1 / 2 ≤ ‖ ∑ i = 1 N a i X i ‖ L p ≤ C K p ( ∑ i = 1 N a i 2 ) 1 / 2 {\displaystyle \left(\sum _{i=1}^{N}a_{i}^{2}\right)^{1/2}\leq \left\|\sum _{i=1}^{N}a_{i}X_{i}\right\|_{L^{p}}\leq CK{\sqrt {p}}\left(\sum _{i=1}^{N}a_{i}^{2}\right)^{1/2}} {\displaystyle \left(\sum _{i=1}^{N}a_{i}^{2}\right)^{1/2}\leq \left\|\sum _{i=1}^{N}a_{i}X_{i}\right\|_{L^{p}}\leq CK{\sqrt {p}}\left(\sum _{i=1}^{N}a_{i}^{2}\right)^{1/2}}

Hanson-Wright inequality

The Hanson-Wright inequality states that if a random vector X {\displaystyle X} {\displaystyle X} is subgaussian in a certain sense, then any quadratic form A {\displaystyle A} {\displaystyle A} of this vector, X T A X {\displaystyle X^{T}AX} {\displaystyle X^{T}AX}, is also subgaussian/subexponential. Further, the upper bound on the tail of X T A X {\displaystyle X^{T}AX} {\displaystyle X^{T}AX}, is uniform.

A weak version of the following theorem was proved in (Hanson, Wright, 1971).[12] There are many extensions and variants. Much like the central limit theorem, the Hanson-Wright inequality is more a cluster of theorems with the same purpose, than a single theorem. The purpose is to take a subgaussian vector and uniformly bound its quadratic forms.

Theorem.[13][14] There exists a constant c {\displaystyle c} {\displaystyle c}, such that:

Let n {\displaystyle n} {\displaystyle n} be a positive integer. Let X 1 , . . . , X n {\displaystyle X_{1},...,X_{n}} {\displaystyle X_{1},...,X_{n}} be independent random variables, such that each satisfies E [ X i ] = 0 {\displaystyle E[X_{i}]=0} {\displaystyle E[X_{i}]=0}. Combine them into a random vector X = ( X 1 , … , X n ) {\displaystyle X=(X_{1},\dots ,X_{n})} {\displaystyle X=(X_{1},\dots ,X_{n})}. For any n × n {\displaystyle n\times n} {\displaystyle n\times n} matrix A {\displaystyle A} {\displaystyle A}, we have P ( | X T A X − E [ X T A X ] | > t ) ≤ max ( 2 e − c t 2 K 4 ‖ A ‖ F 2 , 2 e − c t K 2 ‖ A ‖ ) = 2 exp ⁡ [ − c min ( t 2 K 4 ‖ A ‖ F 2 , t K 2 ‖ A ‖ ) ] {\displaystyle P(|X^{T}AX-E[X^{T}AX]|>t)\leq \max \left(2e^{-{\frac {ct^{2}}{K^{4}\|A\|_{F}^{2}}}},2e^{-{\frac {ct}{K^{2}\|A\|}}}\right)=2\exp \left[-c\min \left({\frac {t^{2}}{K^{4}\|A\|_{F}^{2}}},{\frac {t}{K^{2}\|A\|}}\right)\right]} {\displaystyle P(|X^{T}AX-E[X^{T}AX]|>t)\leq \max \left(2e^{-{\frac {ct^{2}}{K^{4}\|A\|_{F}^{2}}}},2e^{-{\frac {ct}{K^{2}\|A\|}}}\right)=2\exp \left[-c\min \left({\frac {t^{2}}{K^{4}\|A\|_{F}^{2}}},{\frac {t}{K^{2}\|A\|}}\right)\right]}where K = max i ‖ X i ‖ ψ 2 {\displaystyle K=\max _{i}\|X_{i}\|_{\psi _{2}}} {\displaystyle K=\max _{i}\|X_{i}\|_{\psi _{2}}}, and ‖ A ‖ F = ∑ i j A i j 2 {\displaystyle \|A\|_{F}={\sqrt {\sum _{ij}A_{ij}^{2}}}} {\displaystyle \|A\|_{F}={\sqrt {\sum _{ij}A_{ij}^{2}}}} is the Frobenius norm of the matrix, and ‖ A ‖ = max ‖ x ‖ 2 = 1 ‖ A x ‖ 2 {\displaystyle \|A\|=\max _{\|x\|_{2}=1}\|Ax\|_{2}} {\displaystyle \|A\|=\max _{\|x\|_{2}=1}\|Ax\|_{2}} is the operator norm of the matrix.

In words, the quadratic form X T A X {\displaystyle X^{T}AX} {\displaystyle X^{T}AX} has its tail uniformly bounded by an exponential, or a gaussian, whichever is larger.


In the statement of the theorem, the constant c {\displaystyle c} {\displaystyle c} is an "absolute constant", meaning that it has no dependence on n , X 1 , … , X n , A {\displaystyle n,X_{1},\dots ,X_{n},A} {\displaystyle n,X_{1},\dots ,X_{n},A}. It is a mathematical constant much like pi and e.

Consequences

Theorem (subgaussian concentration).[13] There exists a constant c {\displaystyle c} {\displaystyle c}, such that:

Let n , m {\displaystyle n,m} {\displaystyle n,m} be positive integers. Let X 1 , . . . , X n {\displaystyle X_{1},...,X_{n}} {\displaystyle X_{1},...,X_{n}} be independent random variables, such that each satisfies E [ X i ] = 0 , E [ X i 2 ] = 1 {\displaystyle E[X_{i}]=0,E[X_{i}^{2}]=1} {\displaystyle E[X_{i}]=0,E[X_{i}^{2}]=1}. Combine them into a random vector X = ( X 1 , … , X n ) {\displaystyle X=(X_{1},\dots ,X_{n})} {\displaystyle X=(X_{1},\dots ,X_{n})}. For any m × n {\displaystyle m\times n} {\displaystyle m\times n} matrix A {\displaystyle A} {\displaystyle A}, we have P ( | ‖ A X ‖ 2 − ‖ A ‖ F | > t ) ≤ 2 e − c t 2 K 4 ‖ A ‖ 2 {\displaystyle P(|\|AX\|_{2}-\|A\|_{F}|>t)\leq 2e^{-{\frac {ct^{2}}{K^{4}\|A\|^{2}}}}} {\displaystyle P(|\|AX\|_{2}-\|A\|_{F}|>t)\leq 2e^{-{\frac {ct^{2}}{K^{4}\|A\|^{2}}}}}In words, the random vector A X {\displaystyle AX} {\displaystyle AX} is concentrated on a spherical shell of radius ‖ A ‖ F {\displaystyle \|A\|_{F}} {\displaystyle \|A\|_{F}}, such that ‖ A X ‖ 2 − ‖ A ‖ F {\displaystyle \|AX\|_{2}-\|A\|_{F}} {\displaystyle \|AX\|_{2}-\|A\|_{F}} is subgaussian, with subgaussian norm ≤ 3 / c ‖ A ‖ K 2 {\displaystyle \leq {\sqrt {3/c}}\|A\|K^{2}} {\displaystyle \leq {\sqrt {3/c}}\|A\|K^{2}}.

See also

Notes

  1. Wainwright MJ. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge: Cambridge University Press; 2019. doi:10.1017/9781108627771, ISBN 9781108627771.
  2. Leskelä, Lasse; Zhukov, Matvei (2026). "Sharp constants relating the sub-Gaussian norm and the sub-Gaussian parameter". Electronic Communications in Probability. 31: 1–11. doi:10.1214/26-ECP761.
  3. Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science. Cambridge: Cambridge University Press.
  4. Kahane, J. (1960). "Propriétés locales des fonctions à séries de Fourier aléatoires". Studia Mathematica. 19: 1–25. doi:10.4064/sm-19-1-1-25.
  5. Buldygin, V. V.; Kozachenko, Yu. V. (1980). "Sub-Gaussian random variables". Ukrainian Mathematical Journal. 32 (6): 483–489. doi:10.1007/BF01087176.
  6. Bobkov, S. G.; Chistyakov, G. P.; Götze, F. (2023-08-03). "Strictly subgaussian probability distributions". arXiv:2308.01749 [math.PR].
  7. Marchal, Olivier; Arbel, Julyan (2017). "On the sub-Gaussianity of the Beta and Dirichlet distributions". Electronic Communications in Probability. 22. arXiv:1705.00048. doi:10.1214/17-ECP92.
  8. Arbel, Julyan; Marchal, Olivier; Nguyen, Hien D. (2020). "On strict sub-Gaussianity, optimal proxy variance and symmetry for bounded random variables". Esaim: Probability and Statistics. 24: 39–55. arXiv:1901.09188. doi:10.1051/ps/2019018.
  9. Barreto, Mathias; Marchal, Olivier; Arbel, Julyan (2024). "Optimal sub-Gaussian variance proxy for truncated Gaussian and exponential random variables". arXiv:2403.08628 [math.ST].
  10. Kamath, Gautam. "Bounds on the expectation of the maximum of samples from a gaussian." (2015)
  11. "MIT 18.S997 | Spring 2015 | High-Dimensional Statistics, Chapter 1. Sub-Gaussian Random Variables" (PDF). MIT OpenCourseWare. Retrieved 2024-04-03.
  12. Hanson, D. L.; Wright, F. T. (1971). "A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables". The Annals of Mathematical Statistics. 42 (3): 1079–1083. doi:10.1214/aoms/1177693335. ISSN 0003-4851. JSTOR 2240253.
  13. Rudelson, Mark; Vershynin, Roman (January 2013). "Hanson-Wright inequality and sub-gaussian concentration". Electronic Communications in Probability. 18 (none): 1–9. arXiv:1306.2872. doi:10.1214/ECP.v18-2865. ISSN 1083-589X.
  14. Vershynin, Roman (2018). "6. Quadratic Forms, Symmetrization, and Contraction". High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge: Cambridge University Press. pp. 127–146. doi:10.1017/9781108231596.009. ISBN 978-1-108-41519-4.

References