Sub-Exponential Random Variables

Why This Matters

Sub-Gaussian random variables have tails decaying like $e^{-ct^2}$ and give the cleanest concentration bounds. But many quantities in ML are not sub-Gaussian:

• Chi-squared random variables (sums of squared Gaussians)
• Products of sub-Gaussian random variables
• Exponential random variables (waiting times)
• Squared losses in regression with Gaussian noise

These have tails decaying like $e^{-ct}$. exponentially, but with a linear exponent rather than quadratic. The sub-exponential class captures exactly this level of tail behavior, and the Bernstein inequality for sub-exponential sums provides the right concentration bound: sub-Gaussian for small deviations, exponential for large deviations.

Mental Model

The tail decay hierarchy is:

Class	Tail decay	MGF	Example
Sub-Gaussian	$e^{-ct^2}$	Finite for all $\lambda$	Bounded, Gaussian
Sub-exponential	$e^{-ct}$	Finite for $	\lambda
Heavy-tailed	$1/t^p$	May not exist	Cauchy, Pareto

Sub-exponential is the intermediate class. The MGF exists in a neighborhood of zero (not everywhere), which means the Chernoff method works for small $\lambda$ but breaks for large $\lambda$. This produces a concentration bound with two regimes.

Formal Setup and Definitions

Let $X$ be a centered random variable ($\mathbb{E}[X] = 0$).

Definition

Sub-Exponential Random Variable (MGF characterization)

A centered random variable $X$ is sub-exponential with parameters $(\nu^2, b)$ if for all $|\lambda| < 1/b$:

$\mathbb{E}[e^{\lambda X}] \leq \exp\!\left(\frac{\nu^2 \lambda^2}{2}\right)$

The parameter $\nu^2$ plays the role of a "variance proxy" (controlling the sub-Gaussian regime), and $b$ controls the radius where the MGF bound holds.

Definition

Sub-Exponential Norm (Orlicz psi_1 norm)

The sub-exponential norm (or $\psi_1$-norm) of $X$ is:

$\|X\|_{\psi_1} = \inf\{t > 0 : \mathbb{E}[e^{|X|/t}] \leq 2\}$

A random variable is sub-exponential if and only if $\|X\|_{\psi_1} < \infty$.

Compare to the sub-Gaussian norm: $\|X\|_{\psi_2} = \inf\{t > 0 : \mathbb{E}[e^{X^2/t^2}] \leq 2\}$. The $\psi_1$ norm uses $e^{|X|/t}$ (linear in $|X|$) while $\psi_2$ uses $e^{X^2/t^2}$ (quadratic). The linear growth in the exponent is what makes sub-exponential tails heavier than sub-Gaussian.

Definition

Bernstein Condition

A centered random variable $X$ satisfies the Bernstein condition with parameters $(\sigma^2, b)$ if for all integers $k \geq 2$:

$\mathbb{E}[|X|^k] \leq \frac{k!}{2} \sigma^2 b^{k-2}$

This is equivalent (up to constants) to being sub-exponential with parameters $(\sigma^2, b)$. The condition controls all moments: the $k$-th moment grows at most like $k! \cdot b^k$, compared to sub-Gaussian where moments grow like $(C\sqrt{k})^k$.

Equivalent Characterizations

The following are equivalent (up to constants in parameters):

1. MGF condition: $\mathbb{E}[e^{\lambda X}] \leq e^{\nu^2\lambda^2/2}$ for $|\lambda| < 1/b$
2. Tail condition: $\mathbb{P}(|X| \geq t) \leq 2\exp(-t/C_1)$ for all $t > 0$
3. Moment condition: $(\mathbb{E}[|X|^k])^{1/k} \leq C_2 k$ for all $k \geq 1$
4. Orlicz norm: $\|X\|_{\psi_1} \leq C_3$
5. Bernstein condition: $\mathbb{E}[|X|^k] \leq \frac{k!}{2}\sigma^2 b^{k-2}$ for $k \geq 2$

Compare to sub-Gaussian characterization 3: $(\mathbb{E}[|X|^k])^{1/k} \leq C\sqrt{k}$. Sub-exponential moments grow like $k$; sub-Gaussian moments grow like $\sqrt{k}$. The extra factor of $\sqrt{k}$ is the precise difference between the two classes.

Main Theorems

Theorem

Products of Sub-Gaussians are Sub-Exponential

Statement

If $X$ and $Y$ are sub-Gaussian random variables (not necessarily independent), then the product $XY$ is sub-exponential, with:

$\|XY\|_{\psi_1} \leq \|X\|_{\psi_2} \cdot \|Y\|_{\psi_2}$

Intuition

Multiplying two "Gaussian-like" variables produces something "exponential-like." A concrete example: if $Z \sim \mathcal{N}(0, 1)$, then $Z$ is sub-Gaussian, but $Z^2 = Z \cdot Z$ is chi-squared (with 1 degree of freedom) and sub-exponential. The tails get heavier because multiplying two variables that can be large makes the product even larger.

Proof Sketch

For any $t > 0$: $\mathbb{P}(|XY| \geq t) = \mathbb{P}(|X| \cdot |Y| \geq t)$

Split into cases: either $|X| \geq \sqrt{t}$ or $|Y| \geq \sqrt{t}$ (or both). By union bound:

$\mathbb{P}(|XY| \geq t) \leq \mathbb{P}(|X| \geq \sqrt{t}) + \mathbb{P}(|Y| \geq \sqrt{t})$

Since $X$ is sub-Gaussian: $\mathbb{P}(|X| \geq \sqrt{t}) \leq 2e^{-ct}$. Similarly for $Y$. So $\mathbb{P}(|XY| \geq t) \leq 4e^{-c't}$, which is a sub-exponential tail.

For the norm bound, use the identity $|XY| \leq (X^2 + Y^2)/2$ and the relationship between $\psi_1$ and $\psi_2$ norms.

Why It Matters

This explains why chi-squared variables, quadratic forms, and many statistics in learning theory are sub-exponential: they involve products or squares of sub-Gaussian quantities. When you see $X^\top X$ or $\|Xw\|^2$ in a bound, expect sub-exponential concentration, not sub-Gaussian.

Failure Mode

The product of two sub-exponential variables is generally not sub-exponential (it may be even heavier-tailed). Sub-exponential is not closed under multiplication, unlike sub-Gaussian being closed under addition. This limits the composability of sub-exponential bounds.

Theorem

Bernstein Inequality for Sub-Exponential Sums

Statement

Let $X_1, \ldots, X_n$ be independent centered sub-exponential random variables with parameters $(\nu_i^2, b)$. Then for any $t > 0$:

$\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 \nu_i^2},\, \frac{t}{b}\right)\right)$

where $c > 0$ is a universal constant. For i.i.d. variables with common parameter $\nu^2$ and sample mean $\bar{X}_n = \frac{1}{n}\sum_i X_i$:

$\mathbb{P}\!\left(|\bar{X}_n| \geq t\right) \leq 2\exp\!\left(-cn\min\!\left(\frac{t^2}{\nu^2},\, \frac{t}{b}\right)\right)$

Intuition

The bound has two regimes separated by the threshold $t^* = \nu^2/b$:

Small deviations ($t \leq t^*$): The $t^2/\nu^2$ term dominates the minimum. The bound is $\exp(-cnt^2/\nu^2)$. a sub-Gaussian tail. For moderate deviations, the sub-exponential variable behaves as if it were sub-Gaussian.

Large deviations ($t > t^*$): The $t/b$ term dominates. The bound is $\exp(-cnt/b)$. an exponential (not Gaussian) tail. For large deviations, the heavier tails kick in and concentration is weaker.

The transition between regimes is smooth. The sub-Gaussian regime gives the familiar $\sqrt{\log(1/\delta)/n}$ rates for moderate confidence levels.

Proof Sketch

Use the Chernoff method. For $|\lambda| < 1/b$:

$\mathbb{P}\!\left(\sum_i X_i \geq t\right) \leq e^{-\lambda t} \prod_i \mathbb{E}[e^{\lambda X_i}] \leq e^{-\lambda t} \exp\!\left(\frac{\lambda^2 \sum_i \nu_i^2}{2}\right)$

Optimize over $\lambda \in (0, 1/b)$:

• If the unconstrained optimum $\lambda^* = t/\sum_i\nu_i^2$ satisfies $\lambda^* < 1/b$, we are in the sub-Gaussian regime: bound is $\exp(-t^2/(2\sum_i\nu_i^2))$.
• If $\lambda^* \geq 1/b$, set $\lambda = 1/(2b)$ (at the boundary): bound is $\exp(-t/(2b) + \sum_i\nu_i^2/(8b^2))$. For large $t$, this gives $\exp(-ct/b)$.

Taking the minimum of the two cases gives the stated bound.

Why It Matters

This is the correct concentration bound for quantities like $\frac{1}{n}\sum_i (X_i^2 - \mathbb{E}[X_i^2])$ where each $X_i$ is Gaussian. The sub-Gaussian bound does not apply (these are not sub-Gaussian), but the Bernstein bound does. The two-regime behavior is what you actually observe in practice: moderate deviations look Gaussian, but extreme deviations reveal the heavier tails.

Failure Mode

The bound requires knowing (or bounding) both $\nu^2$ and $b$. For the sample variance of Gaussian data, $\nu^2 = O(\sigma^4)$ and $b = O(\sigma^2)$. If these parameters are poorly estimated, the bound may be loose in one or both regimes.

Key Examples of Sub-Exponential Variables

Example

Chi-squared with k degrees of freedom

If $Z_1, \ldots, Z_k \sim \mathcal{N}(0, 1)$ independently, then $W = \sum_{j=1}^k Z_j^2 \sim \chi^2(k)$ with $\mathbb{E}[W] = k$ and $\text{Var}(W) = 2k$.

The centered variable $W - k$ is sub-exponential with parameters $\nu^2 = O(k)$ and $b = O(1)$. It is not sub-Gaussian because each $Z_j^2$ has MGF $\mathbb{E}[e^{\lambda Z_j^2}] = (1 - 2\lambda)^{-1/2}$ which diverges at $\lambda = 1/2$. A sub-Gaussian MGF would be finite for all $\lambda$.

The Bernstein bound gives: $\mathbb{P}(|W - k| \geq t) \leq 2\exp(-c\min(t^2/k, t))$.

Example

Exponential distribution

If $X \sim \text{Exp}(1)$, then $X - 1$ is centered with $\mathbb{E}[e^{\lambda(X-1)}] = e^{-\lambda}/(1 - \lambda)$ for $\lambda < 1$.

This is finite only for $\lambda < 1$, confirming sub-exponential (not sub-Gaussian) behavior. The $\psi_1$ norm is $\|X - 1\|_{\psi_1} = O(1)$.

Example

Product of two independent standard normals

Let $Z_1, Z_2 \sim \mathcal{N}(0, 1)$ independently. The product $Z_1 Z_2$ has $\mathbb{E}[Z_1 Z_2] = 0$ and the tail bound:

$\mathbb{P}(|Z_1 Z_2| \geq t) \leq 4e^{-\sqrt{t}}$

which is sub-exponential (tail $e^{-ct}$ after substitution $s = t$). Indeed $\|Z_1 Z_2\|_{\psi_1} \leq \|Z_1\|_{\psi_2} \|Z_2\|_{\psi_2} = O(1)$.

Sub-Exponential Closure Properties

1. Sum of independents: If $X_1, \ldots, X_n$ are independent sub-exponential, then $\sum_i X_i$ is sub-exponential with $\|\sum_i X_i\|_{\psi_1} \leq C \sum_i \|X_i\|_{\psi_1}$. (Note: unlike sub-Gaussian, the norm adds linearly, not in quadrature.)

2. Scalar multiplication: $\|aX\|_{\psi_1} = |a| \cdot \|X\|_{\psi_1}$.

3. Product of sub-Gaussians: $\|XY\|_{\psi_1} \leq \|X\|_{\psi_2} \|Y\|_{\psi_2}$.

4. Not closed under products: The product of two sub-exponential variables may be heavier than sub-exponential.

Connection to Bernstein's Classical Inequality

The classical Bernstein inequality (from the concentration-inequalities page) for bounded random variables:

$\mathbb{P}\!\left(\sum_i (X_i - \mu_i) \geq t\right) \leq \exp\!\left(-\frac{t^2/2}{\sum_i \sigma_i^2 + Mt/3}\right)$

is a special case of the sub-exponential Bernstein inequality. Bounded random variables are sub-exponential (since they are even sub-Gaussian), and the denominator $\sum\sigma_i^2 + Mt/3$ captures both regimes: sub-Gaussian when $t \ll \sum\sigma_i^2/M$ and exponential when $t \gg \sum\sigma_i^2/M$.

Common Confusions

Watch Out

Sub-exponential is BETWEEN sub-Gaussian and heavy-tailed

Every sub-Gaussian variable is sub-exponential, but not vice versa. Sub-exponential is a weaker condition (allows heavier tails). The hierarchy is: bounded $\subset$ sub-Gaussian $\subset$ sub-exponential $\subset$ finite variance $\subset$ all distributions.

Watch Out

The MGF bound holds only for small lambda

For sub-Gaussian variables, $\mathbb{E}[e^{\lambda X}] \leq e^{C\lambda^2}$ for all $\lambda$. For sub-exponential, the bound holds only for $|\lambda| < 1/b$. Beyond this, the MGF may diverge. This is why the Chernoff method produces two regimes: you can only optimize $\lambda$ up to the boundary $1/b$.

Watch Out

psi_1 norm vs psi_2 norm

$\psi_2$ (sub-Gaussian) uses $e^{X^2/t^2}$ in the definition. the square of $X$ in the exponent. $\psi_1$ (sub-exponential) uses $e^{|X|/t}$. The absolute value of $X$. The square in $\psi_2$ is what forces the tails to be Gaussian-like. Every sub-Gaussian variable is sub-exponential because $e^{|X|/t} \leq 1 + e^{X^2/t^2}$ for appropriate $t$.

Summary

• Sub-exponential tails: $\mathbb{P}(|X| \geq t) \leq 2e^{-ct}$ (linear exponent)
• Sub-Gaussian tails: $\mathbb{P}(|X| \geq t) \leq 2e^{-ct^2}$ (quadratic exponent)
• Products of sub-Gaussians are sub-exponential ($\psi_2 \cdot \psi_2 \to \psi_1$)
• Chi-squared and squared losses are sub-exponential, not sub-Gaussian
• Bernstein bound has two regimes: sub-Gaussian for small $t$, exponential for large $t$
• Threshold between regimes: $t^* = \nu^2/b$
• $\psi_1$ norm adds linearly for sums; $\psi_2$ norm adds in quadrature

Exercises

ExerciseCore

Problem

Show that $X \sim \text{Exp}(1)$ is sub-exponential but not sub-Gaussian. Compute the MGF $\mathbb{E}[e^{\lambda(X-1)}]$ and show it is finite only for $\lambda < 1$.

Hint

Reveal Solution

ExerciseCore

Problem

Let $Z \sim \mathcal{N}(0, 1)$. Show that $Z^2 - 1$ (centered chi-squared with 1 degree of freedom) is sub-exponential by verifying the tail bound $\mathbb{P}(Z^2 - 1 \geq t) \leq e^{-ct}$ for large $t$.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Let $X_1, \ldots, X_n \sim \mathcal{N}(0, \sigma^2)$ independently. Using the Bernstein inequality for sub-exponential variables, bound $\mathbb{P}\!\left(\left|\frac{1}{n}\sum_i X_i^2 - \sigma^2\right| \geq t\right)$. Identify the two regimes.

Hint

Reveal Solution

Related Comparisons

• Sub-Gaussian vs. Sub-Exponential Random Variables

References

Canonical:

• Vershynin, High-Dimensional Probability (2018), Chapter 2.7-2.8
• Boucheron, Lugosi, Massart, Concentration Inequalities (2013), Chapter 2

Current:

• Wainwright, High-Dimensional Statistics (2019), Chapter 2

• Rigollet & Hutter, High-Dimensional Statistics (MIT lecture notes, 2023)

• van Handel, Probability in High Dimension (2016), Chapters 1-3

Next Topics

Building on sub-exponential theory:

• Matrix concentration: extending sub-exponential bounds to matrix-valued random variables
• Epsilon-nets and covering numbers: combining concentration with geometric discretization