High-Dimensional Probability & Concentration

the sub-exponential random variable

A sub-exponential random variable has a tail that decays at least exponentially, P(|X| > t) <= 2 e^(-c t) for large t — heavier than a Gaussian but still light enough for sharp concentration. The class arises forcibly the moment you multiply: the square of a sub-Gaussian, or the product of two sub-Gaussians, is sub-exponential, not sub-Gaussian. Since chi-squared variables, sample variances, and quadratic forms (which power covariance estimation) are exactly such squares, sub-exponential concentration is the workhorse one actually needs in high-dimensional statistics, even when the inputs are Gaussian.

As with sub-Gaussians, several conditions are equivalent up to absolute constants: the exponential tail above; the moment growth (E[|X|^p])^(1/p) <= K p (linear in p, versus sqrt(p) for sub-Gaussian); E[exp(|X| / K)] <= 2; and, for centered X, a one-sided MGF bound that holds only in a neighbourhood of the origin: E[exp(lambda X)] <= exp(K^2 lambda^2 / 2) for all |lambda| <= 1/K. That last restriction |lambda| <= 1/K is the whole difference from the sub-Gaussian case, where the quadratic MGF bound holds for every lambda. Because the MGF is controlled only near 0, the resulting concentration has two regimes, and a sub-exponential variable need not even have a finite MGF far from the origin.

The two-regime structure is the signature of the sub-exponential world. Bernstein's inequality for sums of independent centered sub-exponentials reads P(|sum| >= t) <= 2 exp(-c min(t^2 / sigma^2, t / b)), where sigma^2 is the sum of sub-exponential variances and b is the maximal scale. For small deviations t the Gaussian term t^2/sigma^2 dominates (sub-Gaussian behaviour); for large t the linear exponential term t/b takes over, reflecting the heavier tail. A sub-Gaussian variable is exactly a sub-exponential variable whose two regimes never separate (b can be taken proportional to sigma). The product characterization is the cleanest mnemonic: X is sub-exponential iff X = YZ for sub-Gaussian Y and Z (heuristically), and ||X||_psi1 <= ||Y||_psi2 ||Z||_psi2.

If g ~ N(0,1), then X = g^2 - 1 (a centered chi-squared term) is sub-exponential, not sub-Gaussian: its MGF E[exp(lambda(g^2-1))] = exp(-lambda)/sqrt(1-2lambda) is finite only for lambda < 1/2 and blows up at lambda = 1/2. Summing n such terms and applying Bernstein gives P(|sum (g_i^2 - 1)| >= n eps) <= 2 exp(-c n min(eps^2, eps)).

Squares of Gaussians are sub-exponential: the MGF exists only near the origin.

Crucial difference from sub-Gaussian: the quadratic MGF bound holds only for |lambda| <= 1/K, not all lambda. This is exactly why Bernstein has two regimes and why you cannot just push lambda to infinity in the Chernoff optimization.

Also called
subexponential variable次指數變數