Sub-Gaussian Random Variables

Why This Matters

Concentration inequalities are the engine of learning theory. The simplest concentration bounds --- Markov and Chebyshev --- require only finite first or second moments and give polynomial tail decay. The strongest non-asymptotic bounds --- Hoeffding, Chernoff, Bernstein --- require exponential-moment conditions and give exponential tail decay. Sub-Gaussian random variables are the precise class for which exponential-moment conditions are as tight as if the variable were Gaussian, even when it is not. Most Hoeffding-type generalization bounds in VC and Rademacher theory are sub-Gaussian bounds in disguise; the familiar $\sqrt{\log(1/\delta)/n}$ rates come from this class.

If you understand sub-Gaussianity, you understand why exponential-tail concentration works. Heavier tails (sub-exponential, polynomial) need their own machinery.

A standard Gaussian saturates the sub-Gaussian tail bound. Whenever a "sub-Gaussian bound" curve appears distinct from a "Gaussian: $\exp(-t^2/2)$" curve in tail plots, read the sub-Gaussian curve as $\exp(-ct^2)$ with an explicit generic constant $c < 1/2$ corresponding to some $\sigma > 1$. The sub-Gaussian class includes Gaussian tails: a Gaussian variable $Z \sim \mathcal{N}(0,1)$ is itself sub-Gaussian with parameter $\sigma = 1$.

Mental Model

A sub-Gaussian random variable has tails that decay at least as fast as those of a Gaussian. Concretely, the probability of being far from the mean drops like $e^{-ct^2}$, not merely $e^{-ct}$ (sub-exponential) or $1/t^p$ (polynomial). This exponential-squared decay is what gives you the $\sqrt{\log(1/\delta)/n}$ rates in learning theory.

The key insight: many non-Gaussian distributions - bounded random variables, Rademacher random variables, and projections of high-dimensional uniform distributions - all satisfy this same tail behavior. Sub-Gaussianity captures exactly what these distributions have in common.

Formal Setup and Notation

Let $X$ be a real-valued random variable with $\mathbb{E}[X] = 0$ (we center without loss of generality).

This is the workhorse definition. It says the moment generating function of $X$ is dominated by that of a $\mathcal{N}(0, \sigma^2)$ random variable.

Equivalent Characterizations

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

1. MGF condition: $\mathbb{E}[e^{\lambda X}] \leq e^{C_1^2 \lambda^2 / 2}$ for all $\lambda$
2. Tail condition: $\mathbb{P}(|X| \geq t) \leq 2e^{-t^2/(2C_2^2)}$ for all $t > 0$
3. Moment condition: $(\mathbb{E}[|X|^p])^{1/p} \leq C \|X\|_{\psi_2} \sqrt{p}$ for all $p \geq 1$
4. Orlicz norm: $\|X\|_{\psi_2} < \infty$

The constants across these four statements differ by at most universal multiplicative factors. The equivalence is what makes the sub-Gaussian class robust: you can verify membership via whichever characterization is most convenient.

Proof sketches for the harder directions

Tail $\Rightarrow$ MGF (layer cake). Suppose $\mathbb{P}(|X| \geq t) \leq 2e^{-t^2/(2K^2)}$. For $\lambda > 0$, by the layer-cake formula applied to the non-negative random variable $e^{\lambda X} \mathbf{1}\{X \geq 0\}$:

$\mathbb{E}[e^{\lambda X} \mathbf{1}\{X \geq 0\}] = 1 + \int_0^\infty \lambda e^{\lambda t}\,\mathbb{P}(X \geq t)\,dt \leq 1 + 2\int_0^\infty \lambda e^{\lambda t - t^2/(2K^2)}\,dt.$

Complete the square in the exponent: $\lambda t - t^2/(2K^2) = K^2\lambda^2/2 - (t - K^2\lambda)^2/(2K^2)$. The Gaussian integral yields $\mathbb{E}[e^{\lambda X}] \leq e^{cK^2\lambda^2}$ for a universal $c$. The same argument applied to $-X$ handles $\lambda < 0$.

Moment $\Rightarrow$ MGF (Taylor expansion). Suppose $(\mathbb{E}[|X|^p])^{1/p} \leq K\sqrt{p}$ for all $p \geq 1$. Expand the MGF term by term:

$\mathbb{E}[e^{\lambda X}] = 1 + \sum_{k=1}^\infty \frac{\lambda^k \mathbb{E}[X^k]}{k!} \leq 1 + \sum_{k=1}^\infty \frac{|\lambda|^k K^k k^{k/2}}{k!}.$

Stirling's bound $k! \geq (k/e)^k$ gives $k^{k/2}/k! \leq (e/\sqrt{k})^k \cdot k^{-k/2} \leq C^k / k^{k/2}$. For $|\lambda| \leq c/K$ the series converges to something bounded by $e^{cK^2\lambda^2}$. Extend to all $\lambda$ via a separate bound in the large-$\lambda$ regime using the tail equivalence.

Interactive: three views of one definition

Same distribution, three separate tests. Switch the tab to compare the tail, the log-MGF, and the $\psi_2$ expectation side by side. Gaussian, Rademacher, and Uniform$[-1,1]$ pass all three. Laplace and the centered Exponential have only exponential (not Gaussian) tails, so they pass none of the three sub-Gaussian conditions globally. The interactive panel inspects each condition on a finite range, so a distribution may appear to satisfy the tail check inside the visible window while still violating the MGF and $\psi_2$ conditions at large enough $\lambda$ or $p$; that finite-window artifact is what the tab labels are showing. Watching a distribution fail one panel while holding another makes the equivalence concrete: each characterization picks up the same sub-Gaussian tail behavior from a different direction, and any genuinely sub-Gaussian variable passes or fails them together.

Main Theorems

\mathbb{E}[e^{\lambda X}] \leq e^{\sigma^2\lambda^2/2} \Rightarrow \mathbb{P}(X \geq t) \leq \exp\!\left(-\frac{t^2}{2\sigma^2}\right)

\mathbb{E}[e^{\lambda X}] \leq \exp\!\left(\frac{\lambda^2(b-a)^2}{8}\right)

Canonical Examples

Common Confusions

Centered vs Non-Centered Sub-Gaussian

The canonical MGF definition assumes $\mathbb{E}[X] = 0$. For non-centered $X$ with $\mathbb{E}[X] = \mu$ and $X - \mu$ sub-Gaussian with parameter $\sigma$:

$\mathbb{E}[e^{\lambda X}] \leq e^{\lambda \mu + \sigma^2 \lambda^2/2} \quad \text{for all } \lambda \in \mathbb{R}.$

This is the natural non-centered analog. The linear term in the exponent carries the mean; the quadratic term controls the tails. All downstream closure and concentration results go through after the mean shift.

The $\psi_2$-norm, unlike the sub-Gaussian parameter, does not require centering: it is a norm on $X$ itself, since $\psi_2(x) = e^{x^2} - 1$ depends on $|X|$. This is one reason the $\psi_2$ formulation is often cleaner to work with.

Why Sub-Gaussian is the Right Abstraction

Three reasons sub-Gaussianity appears everywhere in ML theory:

1. Closure under summation: sums of independent sub-Gaussians are sub-Gaussian. This is exactly what you need for sample averages.

2. Captures all bounded losses: every bounded loss function produces sub-Gaussian empirical averages. Since most learning theory starts with bounded losses, sub-Gaussianity is the natural first assumption.

3. Tight enough for optimal rates: sub-Gaussian concentration gives $O(1/\sqrt{n})$ deviation bounds for sample means, which matches the CLT rate. You cannot do better in general.

The sub-Gaussian class is the largest class of distributions for which the Chernoff method gives Gaussian-quality tail bounds. Going beyond sub-Gaussian (to sub-exponential, or heavier tails) requires different tools and yields weaker concentration.

The Orlicz Norm Hierarchy

The $\psi_2$ norm makes the set of sub-Gaussian random variables a Banach space $L_{\psi_2}$, sitting in a strict inclusion chain on a probability space:

$L^\infty \subset L_{\psi_2} \subset L_{\psi_1} \subset \bigcap_{p < \infty} L^p$

Bounded $\subset$ Sub-Gaussian $\subset$ Sub-exponential $\subset$ All-moments-finite. Each inclusion is strict: a standard Gaussian is sub-Gaussian but not bounded; an $\text{Exp}(1)$ variable is sub-exponential but not sub-Gaussian.

Recall that on a probability space $L^p$ decreases with $p$, so $L^\infty \subset L^q \subset L^p$ whenever $p \leq q$. Sub-exponential variables have all moments finite: they sit inside every $L^p$ for $p < \infty$.

The $\psi_1$ norm is defined analogously with $\psi_1(x) = e^x - 1$: $\|X\|_{\psi_1} = \inf\{t > 0 : \mathbb{E}[e^{|X|/t}] \leq 2\}$.

Exact $\psi_2$ Norms for Common Distributions

Closure Properties

Sub-Gaussianity is useful precisely because it is preserved under the operations that appear in proofs.

\left\|\sum_i a_i X_i\right\|_{\psi_2} \leq CK\|a\|_2

Other closure properties:

• Scaling: $\|aX\|_{\psi_2} = |a| \cdot \|X\|_{\psi_2}$ (immediate from definition).
• Lipschitz maps: if $f$ is $L$-Lipschitz with $f(0) = 0$, then $\|f(X)\|_{\psi_2} \leq CL \cdot \|X\|_{\psi_2}$.
• Products break sub-Gaussianity: if $X, Y$ are independent sub-Gaussian, then $XY$ is sub-exponential, not sub-Gaussian. In particular, $X^2$ is sub-exponential whenever $X$ is sub-Gaussian. This is exactly why Bernstein's inequality has two regimes.

Sub-Gaussian Maxima

\mathbb{E}\!\left[\max_{i \leq n} X_i\right] \leq CK\sqrt{\log n}

The Sub-Exponential Bridge

The relationship between sub-Gaussian and sub-exponential is precise:

• If $X$ is sub-Gaussian, then $X^2$ is sub-exponential with $\|X^2\|_{\psi_1} = \|X\|_{\psi_2}^2$ (identity, under the standard Orlicz norm convention $\psi_1(x) = e^x - 1$, $\psi_2(x) = e^{x^2} - 1$).
• Conversely, if $X^2$ is sub-exponential, then $X$ is sub-Gaussian.

This explains why Bernstein's inequality for centered sub-exponential variables $\sum X_i$ has two regimes:

$\mathbb{P}\!\left(\left|\sum X_i\right| \geq t\right) \leq 2\exp\!\left(-c \cdot \min\!\left(\frac{t^2}{\sum \|X_i\|_{\psi_1}^2},\; \frac{t}{\max \|X_i\|_{\psi_1}}\right)\right)$

For small $t$, the $t^2$ term dominates (sub-Gaussian regime). For large $t$, the $t$ term dominates (sub-exponential regime, heavier tail). Setting $t^2/\sum\|X_i\|_{\psi_1}^2 = t/\max\|X_i\|_{\psi_1}$ gives the crossover $t^\star = \sum\|X_i\|_{\psi_1}^2 / \max\|X_i\|_{\psi_1}$ (Vershynin Thm 2.9.1).

Proof Checklist

When writing or reading a sub-Gaussian argument:

1. Identify the random variable. What quantity do you want to concentrate? Write it as $Z = g(X_1, \ldots, X_n)$.
2. Center it. Work with $Z - \mathbb{E}[Z]$.
3. Decompose if needed. Express $Z - \mathbb{E}[Z]$ as a sum or martingale difference sequence.
4. Check sub-Gaussianity of each piece. Bounded? Hoeffding gives $\sigma_i$. Lipschitz of Gaussian? Gaussian concentration applies.
5. Propagate. Independent sum: $\sigma^2 = \sum \sigma_i^2$. Martingale: Azuma-Hoeffding. Linear combination: $\|a\|_2$ scaling.
6. Apply tail bound. $\mathbb{P}(|Z - \mathbb{E}[Z]| \geq t) \leq 2e^{-t^2/(2\sigma^2)}$. Invert to get confidence intervals.

Exercises

Related Comparisons

• Sub-Gaussian vs. Sub-Exponential Random Variables

References

• Vershynin, High-Dimensional Probability (2018), Chapters 2-3. Definitive modern treatment using the Orlicz norm framework. Proposition 2.5.2 for the equivalence theorem.
• Boucheron, Lugosi, Massart, Concentration Inequalities (2013), Chapter 2. Uses the entropy method rather than Orlicz norms.
• Wainwright, High-Dimensional Statistics (2019), Chapter 2. Clear exposition connecting sub-Gaussian theory to statistical applications.
• van Handel, Probability in High Dimension (2016), Chapters 1-2. Excellent treatment of sub-Gaussian maxima and chaining.
• Shalev-Shwartz and Ben-David, Understanding Machine Learning (2014), Chapters 26-28. How sub-Gaussian bounds enter learning theory.
• Rigollet and Hutter, High-Dimensional Statistics (MIT lecture notes, 2023), Chapter 1. Concise derivation of all five characterizations with explicit constants.

Next Topics

Natural next steps from sub-Gaussian random variables:

• Sub-exponential random variables: the next distributional class, for heavier tails.
• Hanson-Wright inequality: sub-Gaussian concentration for quadratic forms $X^\top A X$.
• Epsilon-nets and covering numbers: combining sub-Gaussian concentration with geometric arguments. Dudley's chaining integral, developed in empirical processes and chaining, sharpens the $\sqrt{\log n}$ maxima bound when $X_i$ are indexed by a metric space.
• Azuma-Hoeffding inequality via martingale theory: sub-Gaussian concentration for martingale difference sequences, the natural generalization beyond independent sums.
• McDiarmid's inequality: concentration for functions of independent variables with bounded differences. Direct application of sub-Gaussian ideas via a martingale expansion.
• Tsirelson-Ibragimov-Sudakov (Gaussian Lipschitz concentration): for $f : \mathbb{R}^n \to \mathbb{R}$ that is $L$-Lipschitz and $Z \sim \mathcal{N}(0, I_n)$, $f(Z) - \mathbb{E}[f(Z)]$ is sub-Gaussian with parameter $L$. The cleanest statement of sub-Gaussian behavior in high dimension.