Sub-Exponential Variables and Bernstein Bounds

SECTION 01Sub-Exponential Variables

Sub-Gaussianity requires tails to decay at least as fast as a Gaussian tail. This excludes many distributions with slower tail decay, such as an exponential distribution. We therefore relax the condition to allow heavier tails.

We introduce sub-exponential variables, then derive their tail bound using the Chernoff approach. The bound has two regimes: a Gaussian form for smaller deviations and an exponential form for larger deviations.

Definition · Sub-Exponential Variable

A random variable X with mean μ = E[X] is sub-exponential if there are nonnegative parameters (ν, α) such that

E [e^{λ (X - μ)}] \leq e^{\frac{ν^{2} λ^{2}}{2}}, | λ | < \frac{1}{α}

SECTION 02Sub-Exponential Tail Bound

Claim · Sub-Exponential Tail Bound

If X is sub-exponential with parameters (ν, α), then for t ≥ 0,

P (X - μ \geq t) \leq {\begin{cases} e^{- \frac{t^{2}}{2 ν^{2}}} & 0 \leq t \leq \frac{ν^{2}}{α} \\ e^{- \frac{t}{2 α}} & t > \frac{ν^{2}}{α} \end{cases}

Proof of the Sub-Exponential Tail Bound

By centering X, we may assume μ = 0. Applying the Chernoff argument gives

P (X \geq t) \leq e^{- λ t} E [e^{λ X}] \leq e^{- λ t + \frac{ν^{2} λ^{2}}{2}}, 0 \leq λ < \frac{1}{α}

Write the exponent as g(λ, t) = −λt + ν²λ²/2. We minimize it over the allowed interval 0 ≤ λ < 1/α.

(1) For 0 ≤ t < ν²/α, the unconstrained minimizer lies inside this interval:

λ^{*} = \frac{t}{ν^{2}}, g (λ^{*}, t) = - \frac{t^{2}}{2 ν^{2}}

This gives the Gaussian part of the bound.

(2) For t ≥ ν²/α, the unconstrained minimizer is at or beyond the boundary. The exponent decreases throughout the allowed interval, so we take λ ↑ 1/α:

\lim_{λ ↑ \frac{1}{α}} g (λ, t) = - \frac{t}{α} + \frac{ν^{2}}{2 α^{2}} \leq - \frac{t}{2 α}

The last inequality uses t ≥ ν²/α. Exponentiating gives the exponential part of the bound. At t = ν²/α, the two expressions agree.

SECTION 03Independent Sums

Claim · Independent Sums Remain Sub-Exponential

Let X₁, …, Xₙ be independent, with means μₖ and sub-exponential parameters (νₖ, αₖ). Then S = ∑ₖ₌₁ⁿ(Xₖ − μₖ) is sub-exponential with parameters (V, α*), where

V^{2} = \sum_{k = 1}^{n} {ν_{k}}^{2}, α_{*} = max_{k} α_{k}

Proof of the Independent-Sum Claim

Independence lets us factor the MGF. Applying each variable’s MGF bound gives

E [e^{λ S}] = \prod_{k = 1}^{n} E [e^{λ (X_{k} - μ_{k})}]

\prod_{k = 1}^{n} E [e^{λ (X_{k} - μ_{k})}] \leq \prod_{k = 1}^{n} e^{\frac{λ^{2} {ν_{k}}^{2}}{2}} = e^{\frac{λ^{2} V^{2}}{2}}

All these bounds hold simultaneously for |λ| < 1/α*. This is exactly the sub-exponential MGF condition with parameters (V, α*).

Formulation · Tail Bound for the Average

Applying the preceding tail bound to S, with threshold nt, gives

P (\frac{1}{n} \sum_{k = 1}^{n} (X_{k} - μ_{k}) \geq t) \leq {\begin{cases} e^{- \frac{n^{2} t^{2}}{2 V^{2}}} & 0 \leq t \leq \frac{V^{2}}{n α_{*}} \\ e^{- \frac{n t}{2 α_{*}}} & t > \frac{V^{2}}{n α_{*}} \end{cases}

SECTION 04Equivalent Characterizations

Claim · Three Equivalent Ways to Describe Sub-Exponential Variables

For a zero-mean random variable X, the following statements are equivalent.

(1) The MGF has a Gaussian-form upper bound near zero: there are nonnegative parameters (ν, α) such that

E [e^{λ X}] \leq e^{\frac{ν^{2} λ^{2}}{2}}, | λ | < \frac{1}{α}

(2) The MGF is finite near zero: there is a c₀ > 0 such that

E [e^{λ X}] < \infty, | λ | \leq c_{0}

(3) The tail probability decays at least exponentially: there are constants c₁, c₂ > 0 such that

P (| X | \geq t) \leq c_{1} e^{- c_{2} t}, t > 0