High-Dimensional Probability & Concentration

the sub-Gaussian random variable

A sub-Gaussian random variable is one whose tail is at least as light as a Gaussian's. In a first course you proved Hoeffding's inequality for bounded variables by bounding the moment generating function; high-dimensional probability turns that single trick into a class of variables, the sub-Gaussians, that share the same exponential-square tail decay and for which the whole concentration toolbox works verbatim. Bounded variables, Gaussians, and any variable with tails P(|X| > t) <= 2 e^(-c t^2) all belong to this class, which is exactly broad enough to cover the noise models of statistics and machine learning while staying as well-behaved as a Gaussian.

Four conditions on a mean-zero X turn out to be equivalent up to absolute constants, and any one may be taken as the definition. The tail bound: P(|X| > t) <= 2 e^(-t^2 / K1^2) for all t. The moment growth: (E[|X|^p])^(1/p) <= K2 sqrt(p) for all p >= 1. The moment generating function of the square: E[exp(X^2 / K3^2)] <= 2. And, when E[X] = 0, the MGF bound E[exp(lambda X)] <= exp(K4^2 lambda^2) for all real lambda. The fourth form is the operational one: it says the log-MGF grows no faster than a quadratic, which is precisely the property that drives every Chernoff-style argument. The equivalence means these constants K1, ..., K4 differ only by universal factors, so a variable is sub-Gaussian or it is not, regardless of which definition you started from.

Sub-Gaussianity is the natural hypothesis for clean concentration. A finite sum of independent sub-Gaussians is again sub-Gaussian, with variance proxies adding (the rotation-invariance property), which is why the general Hoeffding inequality holds for them. The price for breadth is honesty about constants: the equivalences hold only up to absolute multiplicative constants, so 'sub-Gaussian' is a qualitative class, and exact constants (as in the sharp Hoeffding bound for [a,b]-bounded variables) require the specific structure. Heavy-tailed variables — anything with a polynomial tail, or even an exponential tail like the Laplace distribution — are not sub-Gaussian; for those one drops to the sub-exponential class.

A Rademacher sign X (+/-1 each with probability 1/2) is sub-Gaussian: E[exp(lambda X)] = cosh(lambda) <= exp(lambda^2 / 2), so its variance proxy is 1. Any bounded variable on [a, b] is sub-Gaussian with proxy (b-a)^2/4, which recovers Hoeffding's lemma; a standard Gaussian N(0,1) has proxy exactly 1.

Bounded, Rademacher, and Gaussian variables are the prototypical sub-Gaussians.

The four definitions are equivalent only up to absolute constants — a sub-Gaussian variable need not have an MGF bound with the exact Gaussian constant. The MGF/tail definitions for the bound on E[exp(lambda X)] presume E[X] = 0; for a nonzero mean, center first.

Also called
subgaussian variable次高斯變數