Theorem (Sub-exponential properties). Let X X X K i > 0 K_i > 0 K i > 0
The tails of X X X Pr { ∣ X ∣ ≥ t } ≤ 2 exp ( − t / K 1 ) , ∀ t ≥ 0.
\Pr \{ |X| \ge t \} \le 2 \exp( − t / K_1 ), \quad \forall t \ge 0.
Pr { ∣ X ∣ ≥ t } ≤ 2 exp ( − t / K 1 ) , ∀ t ≥ 0.
The moments of X X X ∥ X ∥ L p = ( E ∣ X ∣ p ) 1 / p ≤ K 1 ⋅ 2 p ⋅ Γ ( p ) p = K 2 p , ∀ p ≥ 1.
\Vert X \Vert_{L_p} = ( \mathbb{E} |X|^p )^{1/p}
\le
K_1 \cdot \sqrt[p]{2 p \cdot \Gamma (p)}
= K_2 p, \quad \forall p \ge 1.
∥ X ∥ L p = ( E ∣ X ∣ p ) 1/ p ≤ K 1 ⋅ p 2 p ⋅ Γ ( p ) = K 2 p , ∀ p ≥ 1.
The MGF of ∣ X ∣ |X| ∣ X ∣ E exp ( λ ∣ X ∣ ) ≤ exp ( K 3 λ ) , ∀ λ , s.t., 0 ≤ λ ≤ 1 / K 3 .
\mathbb{E} \exp( \lambda |X| ) \le \exp( K_3 \lambda ),
\quad
\forall \lambda, \, \text{ s.t., } \, 0 \le \lambda \le 1 / K_3.
E exp ( λ ∣ X ∣ ) ≤ exp ( K 3 λ ) , ∀ λ , s.t., 0 ≤ λ ≤ 1/ K 3 .
The MGF of ∣ X ∣ |X| ∣ X ∣ E exp ( ∣ X ∣ / K 4 ) ≤ 2.
\mathbb{E} \exp( |X| / K_4 ) \le 2.
E exp ( ∣ X ∣/ K 4 ) ≤ 2.
Moreover, if E X = 0 \mathbb{E} X = 0 E X = 0 X X X E exp ( λ X ) ≤ exp ( K 5 2 λ 2 ) , ∀ λ , s.t., ∣ λ ∣ ≤ 1 / K 5 .
\mathbb{E} \exp( \lambda X ) \le \exp( K_5^2 \lambda^2 ),
\quad
\forall \lambda, \, \text{ s.t., } \, | \lambda | \le 1/K_5.
E exp ( λ X ) ≤ exp ( K 5 2 λ 2 ) , ∀ λ , s.t., ∣ λ ∣ ≤ 1/ K 5 .
Proof.
1 → 2 : 1 \rightarrow 2: 1 → 2 :
∥ X ∥ L p p = E ∣ X ∣ p = ∫ 0 ∞ Pr [ ∣ X ∣ p ≥ t ] d t = ∫ 0 ∞ Pr [ ∣ X ∣ ≥ t 1 / p ] d t ≤ ∫ 0 ∞ 2 exp ( − t 1 / p / K 1 ) d t u ≐ t 1 / p / K 1 ≤ ∫ 0 ∞ 2 K 1 p ⋅ p ⋅ u p − 1 exp ( − u ) d u = 2 K 1 p ⋅ p ⋅ Γ ( p ) .
\begin{aligned}
\Vert X \Vert_{L_p}^p
&= \mathbb{E}|X|^p \\
&= \int_{0}^\infty \Pr[ |X|^p \ge t ] \, dt \\
&= \int_{0}^\infty \Pr[ |X| \ge t^{1 / p} ] \, dt \\
&\le \int_{0}^\infty 2 \exp(− t^{1 / p} / K_1) \, dt
& u \doteq t^{1 / p} / K_1 \\
&\le \int_{0}^\infty 2 K_1^p \cdot p \cdot u^{p - 1} \exp(− u ) \, du \\
&= 2 K_1^p \cdot p \cdot \Gamma (p).
\end{aligned}
∥ X ∥ L p p = E ∣ X ∣ p = ∫ 0 ∞ Pr [ ∣ X ∣ p ≥ t ] d t = ∫ 0 ∞ Pr [ ∣ X ∣ ≥ t 1/ p ] d t ≤ ∫ 0 ∞ 2 exp ( − t 1/ p / K 1 ) d t ≤ ∫ 0 ∞ 2 K 1 p ⋅ p ⋅ u p − 1 exp ( − u ) d u = 2 K 1 p ⋅ p ⋅ Γ ( p ) . u ≐ t 1/ p / K 1 Noting that Γ ( p ) ≤ p p \Gamma(p) \le p^p Γ ( p ) ≤ p p
2 → 3 : 2 \rightarrow 3: 2 → 3 :
E exp ( λ ∣ X ∣ ) = E ( ∑ n ∈ N λ n ∣ X ∣ n n ! ) = 1 + ∑ n ∈ N + λ n E ∣ X ∣ n n ! ≤ 1 + ∑ n ∈ N + λ n ⋅ 2 K 1 n ⋅ n ⋅ Γ ( n ) n ! since E ∣ X ∣ n ≤ 2 K 1 n ⋅ n ⋅ Γ ( n ) ≤ 1 + 2 ⋅ ∑ n ∈ N + λ n K 1 n = 1 + 2 λ K 1 1 − λ K 1 provided that λ K 1 < 1 = 1 + λ K 1 1 − λ K 1 ≤ e 3 K 1 λ provided that λ K 1 ∈ [ 0 , 4 / 5 ] .
\begin{aligned}
\mathbb{E} \exp( \lambda |X|)
&= \mathbb{E} \left( \sum_{n \in \mathbb{N}} \frac{\lambda^n |X|^n}{n!}\right) \\
&= 1 + \sum_{n \in \mathbb{N}^+} \frac{\lambda^n \mathbb{E} |X|^n}{n!} \\
&\le 1 + \sum_{n \in \mathbb{N}^+} \frac{\lambda^n \cdot 2 K_1^n \cdot n \cdot \Gamma(n)}{n!}
& \text{ since }\, \mathbb{E} |X|^n \le 2 K_1^n \cdot n \cdot \Gamma(n) \\
&\le 1 + 2 \cdot \sum_{n \in \mathbb{N}^+} \lambda^n K_1^n \\
&= 1 + \frac{2 \lambda K_1}{1 - \lambda K_1}
& \text{ provided that }\, \lambda K_1 < 1 \\
&= \frac{1 + \lambda K_1}{1 - \lambda K_1} \\
&\le e^{ 3 K_1 \lambda }
& \text{ provided that }\, \lambda K_1 \in [0, 4 / 5].
\end{aligned}
E exp ( λ ∣ X ∣ ) = E ( n ∈ N ∑ n ! λ n ∣ X ∣ n ) = 1 + n ∈ N + ∑ n ! λ n E ∣ X ∣ n ≤ 1 + n ∈ N + ∑ n ! λ n ⋅ 2 K 1 n ⋅ n ⋅ Γ ( n ) ≤ 1 + 2 ⋅ n ∈ N + ∑ λ n K 1 n = 1 + 1 − λ K 1 2 λ K 1 = 1 − λ K 1 1 + λ K 1 ≤ e 3 K 1 λ since E ∣ X ∣ n ≤ 2 K 1 n ⋅ n ⋅ Γ ( n ) provided that λ K 1 < 1 provided that λ K 1 ∈ [ 0 , 4/5 ] . 3 → 4 : 3 \rightarrow 4: 3 → 4 :
It is trivial to prove property 4 by setting λ = 1 / K 3 \lambda = 1 / K_3 λ = 1/ K 3
4 → 1 : 4 \rightarrow 1: 4 → 1 :
Pr { ∣ X ∣ ≥ t } = Pr { e ∣ X ∣ / K 4 ≥ e t / K 4 } ≤ E e ∣ X ∣ / K 4 e t / K 4 ≤ 2 exp ( − t / K 4 ) , ∀ t ≥ 0.
\begin{aligned}
\Pr \{ |X| \ge t \}
&= \Pr \{ e^{|X| / K_4} \ge e^{t / K_4} \} \\
&\le \frac{\mathbb{E} e^{|X| / K_4}}{e^{t / K_4}} \\
&\le 2 \exp(−t / K_4),
&\forall t \ge 0.
\end{aligned}
Pr { ∣ X ∣ ≥ t } = Pr { e ∣ X ∣/ K 4 ≥ e t / K 4 } ≤ e t / K 4 E e ∣ X ∣/ K 4 ≤ 2 exp ( − t / K 4 ) , ∀ t ≥ 0. 2 → 5 : 2 \rightarrow 5: 2 → 5 :
E exp ( λ X ) = E ( ∑ n ∈ N λ n X n n ! ) = 1 + E ( λ X ) + E ( ∑ n ∈ N λ n X n n ! ) = 1 + E ( ∑ n ≥ 2 λ n X n n ! ) ≤ 1 + E ( ∑ n ≥ 2 λ n ∣ X ∣ n n ! ) = 1 + ∑ n ≥ 2 λ n E ∣ X ∣ n n ! ≤ 1 + ∑ n ≥ 2 λ n ⋅ 2 K 1 n ⋅ n ⋅ Γ ( n ) n ! since E ∣ X ∣ n ≤ 2 K 1 n ⋅ n ⋅ Γ ( n ) ≤ 1 + 2 ⋅ ∑ n ≥ 2 λ n K 1 n = 1 + 2 λ 2 K 1 2 1 − λ K 1 provided that λ K 1 < 1 = 1 + 4 λ 2 K 1 2 provided that λ K 1 ≤ 1 / 2 ≤ e 4 K 1 2 λ 2 .
\begin{aligned}
\mathbb{E} \exp( \lambda X)
&= \mathbb{E} \left( \sum_{n \in \mathbb{N}} \frac{\lambda^n X^n}{n!}\right) \\
&= 1 + \mathbb{E} (\lambda X) + \mathbb{E} \left( \sum_{n \in \mathbb{N}} \frac{\lambda^n X^n}{n!}\right) \\
&= 1 + \mathbb{E} \left( \sum_{n \ge 2} \frac{\lambda^n X^n}{n!}\right) \\
&\le 1 + \mathbb{E} \left( \sum_{n \ge 2} \frac{\lambda^n |X|^n}{n!}\right) \\
&= 1 + \sum_{n \ge 2} \frac{\lambda^n \mathbb{E} |X|^n}{n!} \\
&\le 1 + \sum_{n \ge 2} \frac{\lambda^n \cdot 2 K_1^n \cdot n \cdot \Gamma(n)}{n!}
& \text{ since }\, \mathbb{E} |X|^n \le 2 K_1^n \cdot n \cdot \Gamma(n) \\
&\le 1 + 2 \cdot \sum_{n \ge 2} \lambda^n K_1^n \\
&= 1 + \frac{2 \lambda^2 K_1^2}{1 - \lambda K_1}
& \text{ provided that }\, \lambda K_1 < 1 \\
&= 1 + 4 \lambda^2 K_1^2
& \text{ provided that }\, \lambda K_1 \le 1 / 2 \\
&\le e^{ 4 K_1^2 \lambda^2 }.
\end{aligned}
E exp ( λ X ) = E ( n ∈ N ∑ n ! λ n X n ) = 1 + E ( λ X ) + E ( n ∈ N ∑ n ! λ n X n ) = 1 + E ( n ≥ 2 ∑ n ! λ n X n ) ≤ 1 + E ( n ≥ 2 ∑ n ! λ n ∣ X ∣ n ) = 1 + n ≥ 2 ∑ n ! λ n E ∣ X ∣ n ≤ 1 + n ≥ 2 ∑ n ! λ n ⋅ 2 K 1 n ⋅ n ⋅ Γ ( n ) ≤ 1 + 2 ⋅ n ≥ 2 ∑ λ n K 1 n = 1 + 1 − λ K 1 2 λ 2 K 1 2 = 1 + 4 λ 2 K 1 2 ≤ e 4 K 1 2 λ 2 . since E ∣ X ∣ n ≤ 2 K 1 n ⋅ n ⋅ Γ ( n ) provided that λ K 1 < 1 provided that λ K 1 ≤ 1/2 5 → 2 : 5 \rightarrow 2: 5 → 2 : λ = 1 / K 5 \lambda = 1 / K_5 λ = 1/ K 5 λ = − 1 / K 5 \lambda = - 1 / K_5 λ = − 1/ K 5
E exp ( X / K 5 ) ≤ exp ( 1 ) , E exp ( − X / K 5 ) ≤ exp ( 1 ) ,
\begin{aligned}
\mathbb{E}\exp( X / K_5 ) \le \exp( 1 ),
\qquad
\mathbb{E}\exp( - X / K_5 ) \le \exp( 1 ),
\end{aligned}
E exp ( X / K 5 ) ≤ exp ( 1 ) , E exp ( − X / K 5 ) ≤ exp ( 1 ) , Further, for each x ∈ R x \in \mathbb{R} x ∈ R p > 0 p > 0 p > 0 ∣ x ∣ / p ≤ 1 + ∣ x / p ∣ ≤ e ∣ x ∣ / p |x| / p \le 1 + |x / p| \le e^{|x| / p} ∣ x ∣/ p ≤ 1 + ∣ x / p ∣ ≤ e ∣ x ∣/ p
∣ x ∣ p / p p ≤ e ∣ x ∣ ≤ e x + e − x , ⟺ ∣ x / K 5 ∣ p / p p ≤ e ∣ x / K 5 ∣ ≤ e x / K 5 + e − x / K 5 .
|x|^p / p^p \le e^{|x|} \le e^x + e^{-x},
\quad
\Longleftrightarrow
\quad
|x / K_5|^p / p^p \le e^{|x / K_5|} \le e^{x / K_5} + e^{- x / K_5}.
∣ x ∣ p / p p ≤ e ∣ x ∣ ≤ e x + e − x , ⟺ ∣ x / K 5 ∣ p / p p ≤ e ∣ x / K 5 ∣ ≤ e x / K 5 + e − x / K 5 . It follows that
E [ ∣ X / K 5 ∣ p / p p ] ≤ E [ e X / K 5 ] + E [ e − X / K 5 ] ≤ 2 ,
\mathbb{E} \left[ |X / K_5|^p / p^p \right]
\le \mathbb{E} \left[ e^{X / K_5} \right]
+ \mathbb{E} \left[ e^{- X / K_5} \right]
\le 2,
E [ ∣ X / K 5 ∣ p / p p ] ≤ E [ e X / K 5 ] + E [ e − X / K 5 ] ≤ 2 , i.e.,
E [ ∣ X ∣ p ] ≤ 2 ⋅ p p ⋅ K 5 p .
\mathbb{E} \left[ |X|^p \right] \le 2 \cdot p^p \cdot K_5^p.
E [ ∣ X ∣ p ] ≤ 2 ⋅ p p ⋅ K 5 p . □ \square □
A random variable X X X sub-exponential random variable
Definition (Sub-Exponential Norm).
The sub-exponential norm of X X X ∥ X ∥ ψ 1 \Vert X \Vert_{\psi_1} ∥ X ∥ ψ 1 K 3 K_3 K 3
∥ X ∥ ψ 1 = inf { t > 0 : E exp ( ∣ X ∣ / t ) ≤ 2 } .
\Vert X \Vert_{\psi_1} = \inf \{t > 0: \mathbb{E}\exp(|X|/t) \le 2 \}.
∥ X ∥ ψ 1 = inf { t > 0 : E exp ( ∣ X ∣/ t ) ≤ 2 } .
Lemma (Sub-gaussian squared is sub-exponential). A random variable X X X X 2 X^2 X 2
∥ X 2 ∥ ψ 1 = ∥ X ∥ ψ 2 2 .
\Vert X^2 \Vert_{\psi_1} = \Vert X \Vert_{\psi_2}^2.
∥ X 2 ∥ ψ 1 = ∥ X ∥ ψ 2 2 .
Proof.
By definition we have
∥ X 2 ∥ ψ 1 ≐ inf { t > 0 : E exp ( ∣ X ∣ 2 / t ) ≤ 2 } . ∥ X ∥ ψ 2 ≐ inf { t > 0 : E exp ( ∣ X ∣ 2 / t 2 ) ≤ 2 } .
\begin{align*}
\Vert X^2 \Vert_{\psi_1}
&\doteq \inf \{t > 0: \mathbb{E}\exp(|X|^2/t) \le 2 \}. \\
\Vert X \Vert_{\psi_2}
&\doteq \inf \{t > 0: \mathbb{E}\exp(|X|^2/t^2) \le 2 \}.
\end{align*}
∥ X 2 ∥ ψ 1 ∥ X ∥ ψ 2 ≐ inf { t > 0 : E exp ( ∣ X ∣ 2 / t ) ≤ 2 } . ≐ inf { t > 0 : E exp ( ∣ X ∣ 2 / t 2 ) ≤ 2 } . Hence the claim follows.
□ \square □
Lemma (The product of sub-gaussians is sub-exponential). Let X X X Y Y Y X Y XY X Y
∥ X Y ∥ ψ 1 ≤ ∥ X ∥ ψ 2 ∥ Y ∥ ψ 2 .
\Vert XY \Vert_{\psi_1} \le \Vert X \Vert_{\psi_2} \Vert Y \Vert_{\psi_2}.
∥ X Y ∥ ψ 1 ≤ ∥ X ∥ ψ 2 ∥ Y ∥ ψ 2 .
Proof.
Assume that ∥ X ∥ ψ 2 = a \Vert X \Vert_{\psi_2} = a ∥ X ∥ ψ 2 = a ∥ Y ∥ ψ 2 = b . \Vert Y \Vert_{\psi_2} = b. ∥ Y ∥ ψ 2 = b .
E exp ( ∣ X ∣ 2 / a 2 ) ≤ 2 , E exp ( ∣ Y ∣ 2 / b 2 ) ≤ 2.
\begin{aligned}
\mathbb{E}\exp( |X|^2 / a^2 ) \le 2, \\
\mathbb{E}\exp( |Y|^2 / b^2 ) \le 2.
\end{aligned}
E exp ( ∣ X ∣ 2 / a 2 ) ≤ 2 , E exp ( ∣ Y ∣ 2 / b 2 ) ≤ 2. Further
E [ exp ( ∣ X Y ∣ / ( a ⋅ b ) ) ] ≤ E [ exp ( 1 2 ⋅ ( X 2 / a 2 + Y 2 / b 2 ) ) ] ≤ E [ exp ( 1 2 ⋅ ( X 2 / a 2 ) ) ⋅ exp ( 1 2 ⋅ ( Y 2 / b 2 ) ) ] ≤ E [ 1 2 ⋅ ( exp ( 1 2 ⋅ ( X 2 / a 2 ) ) ) 2 + 1 2 ⋅ ( exp ( 1 2 ⋅ ( Y 2 / b 2 ) ) ) 2 ] ≤ 1 2 ⋅ ( 2 + 2 ) = 2.
\begin{aligned}
\mathbb{E} \left[
\exp ( | X Y | / (a \cdot b) )
\right]
&\le \mathbb{E} \left[
\exp \bigg( \frac{1}{2} \cdot (X^2 / a^2 + Y^2 / b^2) \bigg)
\right] \\
&\le \mathbb{E} \left[
\exp \bigg( \frac{1}{2} \cdot (X^2 / a^2 ) \bigg)
\cdot
\exp \bigg( \frac{1}{2} \cdot (Y^2 / b^2) \bigg)
\right] \\
&\le \mathbb{E} \left[
\frac{1}{2} \cdot \left( \exp \bigg( \frac{1}{2} \cdot (X^2 / a^2 ) \bigg) \right)^2
+
\frac{1}{2} \cdot \left( \exp \bigg( \frac{1}{2} \cdot (Y^2 / b^2) \bigg) \right)^2
\right] \\
&\le \frac{1}{2} \cdot \left( 2 + 2 \right)
= 2.
\end{aligned}
E [ exp ( ∣ X Y ∣/ ( a ⋅ b )) ] ≤ E [ exp ( 2 1 ⋅ ( X 2 / a 2 + Y 2 / b 2 ) ) ] ≤ E [ exp ( 2 1 ⋅ ( X 2 / a 2 ) ) ⋅ exp ( 2 1 ⋅ ( Y 2 / b 2 ) ) ] ≤ E [ 2 1 ⋅ ( exp ( 2 1 ⋅ ( X 2 / a 2 ) ) ) 2 + 2 1 ⋅ ( exp ( 2 1 ⋅ ( Y 2 / b 2 ) ) ) 2 ] ≤ 2 1 ⋅ ( 2 + 2 ) = 2. □ \square □
Theorem (Centering). Given sub-exponential random variables X X X
∥ X − E X ∥ ψ 1 ≤ C ∥ X ∥ ψ 1 .
\Vert X − \mathbb{E} X \Vert_{\psi_1} \le C \Vert X \Vert_{\psi_1}.
∥ X − E X ∥ ψ 1 ≤ C ∥ X ∥ ψ 1 .
Proof.
Since ∥ ⋅ ∥ ψ 1 \Vert \cdot \Vert_{\psi_1} ∥ ⋅ ∥ ψ 1
∥ X − E X ∥ ψ 1 ≤ ∥ X ∥ ψ 1 + ∥ E X ∥ ψ 1 ,
\begin{aligned}
\Vert X − \mathbb{E} X \Vert_{\psi_1}
&\le \Vert X \Vert_{\psi_1}
+ \Vert \mathbb{E} X \Vert_{\psi_1},
\end{aligned}
∥ X − E X ∥ ψ 1 ≤ ∥ X ∥ ψ 1 + ∥ E X ∥ ψ 1 , it suffices to bound ∥ E X ∥ ψ 1 \Vert \mathbb{E} X \Vert_{\psi_1} ∥ E X ∥ ψ 1 t = ∣ E X ∣ / ln 2 t = |\mathbb{E} X| / \ln 2 t = ∣ E X ∣/ ln 2
E [ exp ( ∣ E X ∣ / t ) ] = E [ exp ( ln 2 ) ] = 2.
\mathbb{E} \left[ \exp \left( |\mathbb{E} X| / t \right) \right]
= \mathbb{E} \left[ \exp \left( \ln 2 \right) \right]
= 2.
E [ exp ( ∣ E X ∣/ t ) ] = E [ exp ( ln 2 ) ] = 2. Therefore,
∥ E X ∥ ψ 1 = 1 ln 2 ⋅ ∣ E X ∣ ≤ 1 ln 2 ⋅ E ∣ X ∣ = ∥ X ∥ ψ 1 ln 2 ⋅ E [ ∣ X ∣ / ∥ X ∥ ψ 1 ] ≤ ∥ X ∥ ψ 1 ln 2 ⋅ ( 1 + E [ ∣ X ∣ ∥ X ∥ ψ 1 ] + 1 2 ! ⋅ E [ ( ∣ X ∣ ∥ X ∥ ψ 1 ) 2 ] + 1 3 ! ⋅ E [ ( ∣ X ∣ ∥ X ∥ ψ 1 ) 3 ] + ⋯ ) = ( a ) 1 ln 2 ⋅ E [ exp ( ∣ X ∣ ∥ X ∥ ψ 1 ) ] = 2 ⋅ ∥ X ∥ ψ 1 ln 2 ,
\begin{aligned}
\Vert \mathbb{E} X \Vert_{\psi_1}
&= \frac{1}{\ln 2} \cdot |\mathbb{E} X | \\
&\le \frac{1}{\ln 2} \cdot \mathbb{E} |X| \\
&= \frac{\Vert X \Vert_{\psi_1}}{\ln 2} \cdot \mathbb{E} \left[ |X| / \Vert X \Vert_{\psi_1} \right] \\
&\le \frac{\Vert X \Vert_{\psi_1}}{\ln 2} \cdot \left(
1 + \mathbb{E} \left[ \frac{|X|}{\Vert X \Vert_{\psi_1}} \right] + \frac{1}{2!} \cdot \mathbb{E} \left[ \left( \frac{|X|}{\Vert X \Vert_{\psi_1}} \right)^2 \right] + \frac{1}{3!} \cdot \mathbb{E} \left[ \left( \frac{|X|}{\Vert X \Vert_{\psi_1}} \right)^3 \right] + \cdots
\right) \\
&\stackrel{(a)}{=} \frac{1}{\ln 2} \cdot \mathbb{E} \left[ \exp \left( \frac{|X|}{\Vert X \Vert_{\psi_1}} \right) \right] \\
&= 2 \cdot \frac{ \Vert X \Vert_{\psi_1} }{\ln 2},
\end{aligned}
∥ E X ∥ ψ 1 = ln 2 1 ⋅ ∣ E X ∣ ≤ ln 2 1 ⋅ E ∣ X ∣ = ln 2 ∥ X ∥ ψ 1 ⋅ E [ ∣ X ∣/∥ X ∥ ψ 1 ] ≤ ln 2 ∥ X ∥ ψ 1 ⋅ ( 1 + E [ ∥ X ∥ ψ 1 ∣ X ∣ ] + 2 ! 1 ⋅ E [ ( ∥ X ∥ ψ 1 ∣ X ∣ ) 2 ] + 3 ! 1 ⋅ E [ ( ∥ X ∥ ψ 1 ∣ X ∣ ) 3 ] + ⋯ ) = ( a ) ln 2 1 ⋅ E [ exp ( ∥ X ∥ ψ 1 ∣ X ∣ ) ] = 2 ⋅ ln 2 ∥ X ∥ ψ 1 , where ( a ) (a) ( a )
□ \square □
Theorem (Bernstein’s Inequality). Let X 1 , … , X n X_1, \ldots, X_n X 1 , … , X n t ≥ 0 t \ge 0 t ≥ 0
Pr [ ∑ i ∈ [ n ] X i ≥ t ] ≤ 2 exp ( − c min ( t 2 ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 , t max i ∈ [ n ] ∥ X i ∥ ψ 1 ) ) ,
\Pr \left[ \sum_{i \in [n]} X_i \ge t \right]
\le 2 \exp \left( − c \min
\left(
\frac{t^2}{\sum_{i \in [n]} \Vert X_i \Vert_{\psi_1}^2},
\frac{t}{\max_{i \in [n]} \Vert X_i \Vert_{\psi_1}}
\right)
\right),
Pr i ∈ [ n ] ∑ X i ≥ t ≤ 2 exp ( − c min ( ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 t 2 , max i ∈ [ n ] ∥ X i ∥ ψ 1 t ) ) , where c > 0 c > 0 c > 0
Proof.
Let λ > 0 \lambda > 0 λ > 0 K i K_i K i c c c
Pr [ ∑ i ∈ [ n ] X i ≥ t ] ≤ ∏ i ∈ [ n ] E exp ( λ ⋅ X i ) exp ( λ ⋅ t ) ≤ exp ( ∑ i ∈ [ n ] λ 2 ⋅ c ∗ ⋅ ∥ X i ∥ ψ 1 2 − λ ⋅ t ) ,
\begin{aligned}
\Pr \left[ \sum_{i \in [n]} X_i \ge t \right]
\le \frac{
\prod_{i \in [n]} \mathbb{E} \exp \left( \lambda \cdot X_i \right)
}{
\exp \left( \lambda \cdot t \right)
}
\le \exp \left( \sum_{i \in [n]} \lambda^2 \cdot c^* \cdot \Vert X_i \Vert_{\psi_1}^2 - \lambda \cdot t \right),
\end{aligned}
Pr i ∈ [ n ] ∑ X i ≥ t ≤ exp ( λ ⋅ t ) ∏ i ∈ [ n ] E exp ( λ ⋅ X i ) ≤ exp i ∈ [ n ] ∑ λ 2 ⋅ c ∗ ⋅ ∥ X i ∥ ψ 1 2 − λ ⋅ t , where c ∗ = 1 / c ′ c^* = 1 / c' c ∗ = 1/ c ′
λ = min { t 2 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 , c ′ max i ∈ [ n ] ∥ X i ∥ ψ 1 } ,
\lambda = \min \left\lbrace
\frac{t}{
2 \cdot c^* \cdot \sum_{i \in [n]} \Vert X_i \Vert_{\psi_1}^2
}
,\quad
\frac{ c' }{ \max_{i \in [n]}
\Vert X_i \Vert_{\psi_1}
}
\right\rbrace,
λ = min { 2 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 t , max i ∈ [ n ] ∥ X i ∥ ψ 1 c ′ } , which gives
Pr [ ∑ i ∈ [ n ] X i ≥ t ] ≤ exp ( ∑ i ∈ [ n ] λ 2 ⋅ c ∗ ⋅ ∥ X i ∥ ψ 1 2 − λ ⋅ t ) .
\begin{aligned}
\Pr \left[ \sum_{i \in [n]} X_i \ge t \right]
\le \exp \left(
\sum_{i \in [n]} \lambda^2 \cdot c^* \cdot \Vert X_i \Vert_{\psi_1}^2 - \lambda \cdot t
\right).
\end{aligned}
Pr i ∈ [ n ] ∑ X i ≥ t ≤ exp i ∈ [ n ] ∑ λ 2 ⋅ c ∗ ⋅ ∥ X i ∥ ψ 1 2 − λ ⋅ t . When
λ = t 2 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 ≤ c ′ max i ∈ [ n ] ∥ X i ∥ ψ 1 , \lambda = \frac{t}{
2 \cdot c^* \cdot \sum_{i \in [n]} \Vert X_i \Vert_{\psi_1}^2
} \le \frac{ c' }{
\max_{i \in [n]} \Vert X_i \Vert_{\psi_1}
},
λ = 2 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 t ≤ m a x i ∈ [ n ] ∥ X i ∥ ψ 1 c ′ ,
∑ i ∈ [ n ] λ 2 ⋅ c ∗ ⋅ ∥ X i ∥ ψ 1 2 − λ ⋅ t = t 2 4 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 − t 2 2 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 = − t 2 4 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 .
\sum_{i \in [n]} \lambda^2 \cdot c^* \cdot \Vert X_i \Vert_{\psi_1}^2 - \lambda \cdot t
= \frac{t^2}{
4 \cdot c^* \cdot \sum_{i \in [n]} \Vert X_i \Vert_{\psi_1}^2
} - \frac{t^2}{
2 \cdot c^* \cdot \sum_{i \in [n]} \Vert X_i \Vert_{\psi_1}^2
}
= - \frac{t^2}{
4 \cdot c^* \cdot \sum_{i \in [n]} \Vert X_i \Vert_{\psi_1}^2
}.
i ∈ [ n ] ∑ λ 2 ⋅ c ∗ ⋅ ∥ X i ∥ ψ 1 2 − λ ⋅ t = 4 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 t 2 − 2 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 t 2 = − 4 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 t 2 . When
λ = c ′ max i ∈ [ n ] ∥ X i ∥ ψ 1 ≤ t 2 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 , \lambda = \frac{ c' }{
\max_{i \in [n]} \Vert X_i \Vert_{\psi_1}
}
\le \frac{t}{
2 \cdot c^* \cdot \sum_{i \in [n]} \Vert X_i \Vert_{\psi_1}^2
},
λ = m a x i ∈ [ n ] ∥ X i ∥ ψ 1 c ′ ≤ 2 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 t ,
∑ i ∈ [ n ] λ 2 ⋅ c ∗ ⋅ ∥ X i ∥ ψ 1 2 − λ ⋅ t = ( c ′ max i ∈ [ n ] ∥ X i ∥ ψ 1 ) 2 ⋅ ∑ i ∈ [ n ] c ∗ ⋅ ∥ X i ∥ ψ 1 2 − ( c ′ max i ∈ [ n ] ∥ X i ∥ ψ 1 ) t ≤ ( c ′ max i ∈ [ n ] ∥ X i ∥ ψ 1 ) ⋅ t 2 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 ⋅ ∑ i ∈ [ n ] c ∗ ⋅ ∥ X i ∥ ψ 1 2 − ( c ′ max i ∈ [ n ] ∥ X i ∥ ψ 1 ) t = − c ′ t 2 ⋅ max i ∈ [ n ] ∥ X i ∥ ψ 1 .
\begin{aligned}
\sum_{i \in [n]} \lambda^2 \cdot c^* \cdot \Vert X_i \Vert_{\psi_1}^2 - \lambda \cdot t
&= \left(
\frac{ c' }{
\max_{i \in [n]} \Vert X_i \Vert_{\psi_1}
}
\right)^2 \cdot \sum_{i \in [n]} c^* \cdot \Vert X_i \Vert_{\psi_1}^2
- \left(
\frac{ c' }{
\max_{i \in [n]} \Vert X_i \Vert_{\psi_1}
}
\right) t \\
&\le \left(
\frac{ c' }{
\max_{i \in [n]} \Vert X_i \Vert_{\psi_1}
}
\right)
\cdot
\frac{t}{
2 \cdot c^* \cdot \sum_{i \in [n]} \Vert X_i \Vert_{\psi_1}^2
}
\cdot \sum_{i \in [n]} c^* \cdot \Vert X_i \Vert_{\psi_1}^2
- \left(
\frac{ c' }{
\max_{i \in [n]} \Vert X_i \Vert_{\psi_1}
}
\right) t \\
&= - \frac{ c' t }{
2 \cdot \max_{i \in [n]} \Vert X_i \Vert_{\psi_1}
}.
\end{aligned}
i ∈ [ n ] ∑ λ 2 ⋅ c ∗ ⋅ ∥ X i ∥ ψ 1 2 − λ ⋅ t = ( max i ∈ [ n ] ∥ X i ∥ ψ 1 c ′ ) 2 ⋅ i ∈ [ n ] ∑ c ∗ ⋅ ∥ X i ∥ ψ 1 2 − ( max i ∈ [ n ] ∥ X i ∥ ψ 1 c ′ ) t ≤ ( max i ∈ [ n ] ∥ X i ∥ ψ 1 c ′ ) ⋅ 2 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 t ⋅ i ∈ [ n ] ∑ c ∗ ⋅ ∥ X i ∥ ψ 1 2 − ( max i ∈ [ n ] ∥ X i ∥ ψ 1 c ′ ) t = − 2 ⋅ max i ∈ [ n ] ∥ X i ∥ ψ 1 c ′ t . It concludes that
Pr [ ∑ i ∈ [ n ] X i ≥ t ] ≤ exp ( max { − t 2 4 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 , − c ′ t 2 ⋅ max i ∈ [ n ] ∥ X i ∥ ψ 1 } ) = exp ( − min { t 2 4 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 , c ′ t 2 ⋅ max i ∈ [ n ] ∥ X i ∥ ψ 1 } ) .
\begin{aligned}
\Pr \left[ \sum_{i \in [n]} X_i \ge t \right]
&\le \exp \left(
\max \left\lbrace
- \frac{t^2}{
4 \cdot c^* \cdot \sum_{i \in [n]} \Vert X_i \Vert_{\psi_1}^2
},
\,
- \frac{ c' t }{
2 \cdot \max_{i \in [n]} \Vert X_i \Vert_{\psi_1}
}
\right\rbrace
\right) \\
&= \exp \left(
- \min \left\lbrace
\frac{t^2}{
4 \cdot c^* \cdot \sum_{i \in [n]} \Vert X_i \Vert_{\psi_1}^2
},
\,
\frac{ c' t }{
2 \cdot \max_{i \in [n]} \Vert X_i \Vert_{\psi_1}
}
\right\rbrace
\right).
\end{aligned}
Pr i ∈ [ n ] ∑ X i ≥ t ≤ exp ( max { − 4 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 t 2 , − 2 ⋅ max i ∈ [ n ] ∥ X i ∥ ψ 1 c ′ t } ) = exp ( − min { 4 ⋅ c ∗ ⋅ ∑ i ∈ [ n ] ∥ X i ∥ ψ 1 2 t 2 , 2 ⋅ max i ∈ [ n ] ∥ X i ∥ ψ 1 c ′ t } ) . □ \square □
Reference
[1] R. Vershynin, "High-Dimensional Probability: An Introduction with Applications in Data Science." in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge: Cambridge University Press, 2018. doi: 10.1017/9781108231596.
← Back to all notes Back to top ↑