Sub-Gaussian Random Variables

Why This Matters

Concentration inequalities are the engine of learning theory. Every generalization bound you will encounter. from VC dimension to Rademacher complexity to PAC-Bayes. relies on controlling how far a sample average deviates from its expectation. Sub-Gaussian random variables are the precise class for which this control is as tight as if the variable were Gaussian, even when it is not.

If you understand sub-Gaussianity, you understand why concentration works. If you do not, every bound you see will feel like magic.

Mental Model

A random variable is sub-Gaussian if its tails 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, 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).

Definition

Sub-Gaussian Random Variable (MGF characterization)

A centered random variable $X$ is sub-Gaussian with parameter $\sigma$ if for all $\lambda \in \mathbb{R}$:

$\mathbb{E}[e^{\lambda X}] \leq e^{\sigma^2 \lambda^2 / 2}$

The smallest such $\sigma$ is called the sub-Gaussian parameter (or sub-Gaussian proxy variance) of $X$.

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.

Definition

Sub-Gaussian Norm (Orlicz norm)

The sub-Gaussian norm (or $\psi_2$-norm) of $X$ is:

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

A random variable is sub-Gaussian if and only if $\|X\|_{\psi_2} < \infty$. The sub-Gaussian parameter $\sigma$ and the $\psi_2$-norm are related by $\sigma \asymp \|X\|_{\psi_2}$ (up to universal constants).

Definition

Tail Characterization

An equivalent characterization: $X$ is sub-Gaussian with parameter $\sigma$ if and only if for all $t > 0$:

$\mathbb{P}(|X| \geq t) \leq 2 \exp\!\bigl(-\tfrac{t^2}{2\sigma^2}\bigr)$

This is the form you will use most often in practice.

Equivalent Characterizations

The following conditions are equivalent (up to 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_3 \sqrt{p}$ for all $p \geq 1$
4. Orlicz norm: $\|X\|_{\psi_2} \leq C_4$

The constants $C_1, C_2, C_3, C_4$ differ by at most universal multiplicative factors. This equivalence is what makes the sub-Gaussian class robust: you can verify membership via whichever characterization is most convenient.

Main Theorems

Theorem

Sub-Gaussian MGF Implies Tail Bound

Statement

If $X$ is a centered random variable satisfying $\mathbb{E}[e^{\lambda X}] \leq e^{\sigma^2 \lambda^2/2}$ for all $\lambda \in \mathbb{R}$, then for all $t > 0$:

$\mathbb{P}(X \geq t) \leq \exp\!\bigl(-\tfrac{t^2}{2\sigma^2}\bigr)$

Intuition

The MGF condition is a generating condition. It controls all moments simultaneously. The tail bound is a consequence obtained by the Chernoff method: exponentiate, apply Markov, and optimize over $\lambda$. The quadratic exponent in the MGF translates directly to a quadratic exponent in the tail.

Proof Sketch

For any $\lambda > 0$, by Markov's inequality:

$\mathbb{P}(X \geq t) = \mathbb{P}(e^{\lambda X} \geq e^{\lambda t}) \leq e^{-\lambda t}\,\mathbb{E}[e^{\lambda X}] \leq e^{-\lambda t + \sigma^2 \lambda^2/2}$

Minimize over $\lambda$: set $\lambda^* = t/\sigma^2$ to get $\mathbb{P}(X \geq t) \leq e^{-t^2/(2\sigma^2)}$.

Why It Matters

This is the Chernoff method: the single most important proof technique in concentration. Every time you see an exponential tail bound, this is the engine underneath. Mastering this one argument gives you access to all of sub-Gaussian concentration theory.

Failure Mode

The bound is only tight up to constants. For a true Gaussian, the bound is off by a polynomial factor in $t$ (the exact Gaussian tail has a $1/t$ prefactor). For non-asymptotic purposes this rarely matters.

Lemma

Hoeffding's Lemma

Statement

If $X$ is a centered random variable with $X \in [a, b]$ almost surely, then for all $\lambda \in \mathbb{R}$:

$\mathbb{E}[e^{\lambda X}] \leq \exp\!\bigl(\tfrac{\lambda^2(b-a)^2}{8}\bigr)$

That is, $X$ is sub-Gaussian with parameter $\sigma = (b-a)/2$.

Intuition

Bounded random variables cannot have heavy tails. They literally cannot take values beyond $[a,b]$. Hoeffding's lemma quantifies this: the MGF of any bounded centered variable is dominated by a Gaussian MGF. The factor of $1/8$ comes from a convexity argument applied to $e^{\lambda x}$ on the interval $[a,b]$.

Proof Sketch

Since $X \in [a, b]$, write $X = \alpha b + (1-\alpha) a$ for some random $\alpha \in [0,1]$. By convexity of $e^{\lambda x}$:

$\mathbb{E}[e^{\lambda X}] \leq \mathbb{E}[\alpha e^{\lambda b} + (1-\alpha) e^{\lambda a}]$

Use $\mathbb{E}[X] = 0$ to express $\mathbb{E}[\alpha]$ in terms of $a, b$. Then apply the inequality $\log(pe^s + qe^{-s}) \leq s^2/8$ for $p + q = 1$ (which follows from Taylor expansion and bounding the remainder). Setting $s = \lambda(b-a)/2$ gives the result.

Why It Matters

Hoeffding's lemma is the bridge between "bounded" and "sub-Gaussian." It explains why bounded losses (e.g., 0-1 loss) always yield $O(1/\sqrt{n})$ concentration. which is exactly what appears in ERM generalization bounds for finite hypothesis classes.

Failure Mode

The bound treats all bounded distributions the same: a constant taking value $0$ and a uniform on $[-1, 1]$ get the same sub-Gaussian parameter. For distributions concentrated near $0$, the variance-based Bernstein inequality gives tighter bounds. Hoeffding's lemma is worst-case over the bounded class.

Canonical Examples

Example

Gaussian random variable

If $X \sim \mathcal{N}(0, \sigma^2)$, then $\mathbb{E}[e^{\lambda X}] = e^{\sigma^2 \lambda^2/2}$ exactly. Gaussians are sub-Gaussian with parameter exactly $\sigma$. This is the "prototype". The definition is designed so that Gaussians saturate the bound.

Example

Rademacher random variable

Let $\varepsilon$ be a Rademacher variable: $\mathbb{P}(\varepsilon = +1) = \mathbb{P}(\varepsilon = -1) = 1/2$. Then $\varepsilon \in [-1, 1]$, so by Hoeffding's lemma, $\varepsilon$ is sub-Gaussian with parameter $\sigma = 1$. In fact, the exact MGF is $\mathbb{E}[e^{\lambda \varepsilon}] = \cosh(\lambda) \leq e^{\lambda^2/2}$, confirming sub-Gaussianity directly.

Rademacher variables appear everywhere in symmetrization arguments and Rademacher complexity.

Example

Bounded random variable

If $X \in [a, b]$ almost surely with $\mathbb{E}[X] = 0$, then $X$ is sub-Gaussian with parameter $(b-a)/2$ by Hoeffding's lemma. This covers:

• 0-1 loss: $\sigma = 1/2$
• Any loss bounded in $[0, M]$ (after centering): $\sigma = M/2$
• Features bounded in $[-B, B]$: $\sigma = B$

Example

Sum of independent sub-Gaussians

If $X_1, \ldots, X_n$ are independent, centered, sub-Gaussian with parameters $\sigma_1, \ldots, \sigma_n$, then $S = \sum_{i=1}^n X_i$ is sub-Gaussian with parameter $\sigma = \sqrt{\sigma_1^2 + \cdots + \sigma_n^2}$.

This follows because MGFs multiply under independence: $\mathbb{E}[e^{\lambda S}] = \prod_i \mathbb{E}[e^{\lambda X_i}] \leq \prod_i e^{\sigma_i^2 \lambda^2/2} = e^{\lambda^2 \sum_i \sigma_i^2/2}$.

For the sample mean $\bar{X} = S/n$ with equal $\sigma_i = \sigma$: sub-Gaussian parameter is $\sigma/\sqrt{n}$, giving the familiar $O(1/\sqrt{n})$ concentration.

Common Confusions

Watch Out

Sub-Gaussian parameter is NOT the standard deviation

The sub-Gaussian parameter $\sigma$ is an upper bound on the effective spread, but it is not equal to $\text{Var}(X)^{1/2}$ in general. For a variable supported on $[-1, 1]$ with variance $0.01$, Hoeffding gives $\sigma = 1$, far larger than $\text{sd}(X) = 0.1$. This is why Bernstein inequalities (which use variance information) are sometimes much tighter than Hoeffding-type bounds.

Watch Out

Not all 'nice' distributions are sub-Gaussian

Exponential, Poisson, and chi-squared random variables are not sub-Gaussian . Their tails decay like $e^{-ct}$ rather than $e^{-ct^2}$. These are sub-exponential. The distinction matters: sub-exponential concentration gives $O(1/\sqrt{n})$ rates only for the mean, not for individual deviations, and requires separate treatment of "small $\lambda$" and "large $\lambda$" regimes.

Watch Out

The centering assumption is essential

The MGF condition $\mathbb{E}[e^{\lambda X}] \leq e^{\sigma^2\lambda^2/2}$ implicitly requires $\mathbb{E}[X] = 0$. If $\mathbb{E}[X] = \mu \neq 0$, you apply the definition to $X - \mu$, not to $X$ directly. Failing to center will give you wrong tail bounds.

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:

$L^\infty \subset L_{\psi_2} \subset L_{\psi_1} \subset L^p \quad \text{for all } p < \infty$

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.

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

Distribution	$\|X\|_{\psi_2}$	Sub-Gaussian $\sigma$	Key step
Rademacher $\varepsilon = \pm 1$	$1/\sqrt{\ln 2} \approx 1.20$	$1$	$\varepsilon^2 = 1$ always, so solve $e^{1/t^2} = 2$
Gaussian $Z \sim \mathcal{N}(0,1)$	$c \approx 1.18$	$1$	$\mathbb{E}[e^{Z^2/t^2}] = (1 - 2/t^2)^{-1/2}$, solve $= 2$
Bounded $X \in [a,b]$, centered	$C(b-a)$	$(b-a)/2$	Hoeffding's lemma gives $\sigma = (b-a)/2$
Gaussian $Z \sim \mathcal{N}(0, \sigma^2)$	$C\sigma$	$\sigma$	Homogeneity: $\|\sigma Z\|_{\psi_2} = \sigma \|Z\|_{\psi_2}$

Closure Properties

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

Theorem

Closure Under Independent Sums

Statement

For any $a = (a_1, \ldots, a_n) \in \mathbb{R}^n$:

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

where $C$ is a universal constant.

Intuition

By independence, MGFs multiply: $\mathbb{E}[e^{\lambda \sum a_i X_i}] = \prod_i \mathbb{E}[e^{\lambda a_i X_i}] \leq \prod_i e^{C^2 K^2 \lambda^2 a_i^2 / 2} = e^{C^2 K^2 \lambda^2 \|a\|_2^2 / 2}$. The $\ell_2$ norm of $a$ controls the sub-Gaussian parameter of the sum.

Failure Mode

Without independence, the bound fails. If $X_1 = X_2 = \cdots = X_n = X$, then $\sum X_i = nX$ with $\|nX\|_{\psi_2} = n\|X\|_{\psi_2}$, but the theorem would predict $CK\sqrt{n}$. The gap between $\sqrt{n}$ and $n$ is exactly the cost of perfect correlation.

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

Theorem

Maximum of Sub-Gaussians

Statement

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

Moreover, for any $t \geq 0$:

$\mathbb{P}\!\left(\max_{i \leq n} X_i \geq CK\sqrt{\log n} + t\right) \leq 2e^{-t^2/(C^2 K^2)}$

Intuition

For any $\lambda > 0$: $\mathbb{E}[\max X_i] \leq \frac{1}{\lambda}\log\sum_i \mathbb{E}[e^{\lambda X_i}] \leq \frac{1}{\lambda}(\log n + C^2 K^2 \lambda^2/2)$. Setting $\lambda = \sqrt{2\log n}/(CK)$ gives $CK\sqrt{2\log n}$.

Why It Matters

This is where the $\log|H|$ term in PAC bounds comes from. Bounding $\sup_{h \in H}|R(h) - \hat{R}(h)|$ over a finite hypothesis class $|H| = n$ is bounding the maximum of $n$ sub-Gaussian variables. The $\sqrt{\log n}$ overhead is the price of uniformity.

Failure Mode

For sub-exponential variables, the maximum grows as $\log n$ (not $\sqrt{\log n}$). The heavier tails make the worst case worse. For heavy-tailed variables (polynomial tails), the maximum can grow polynomially in $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} \leq C\|X\|_{\psi_2}^2$.
• 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). The crossover happens at $t \approx \sum\|X_i\|_{\psi_1}/\max\|X_i\|_{\psi_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

ExerciseCore

Problem

Let $X$ be a Rademacher random variable ($\pm 1$ with equal probability). Verify directly that $\mathbb{E}[e^{\lambda X}] = \cosh(\lambda) \leq e^{\lambda^2/2}$ for all $\lambda$.

Hint

Reveal Solution

ExerciseCore

Problem

Let $X_1, \ldots, X_n$ be i.i.d. with $X_i \in [0, 1]$ and $\mathbb{E}[X_i] = \mu$. Using Hoeffding's lemma and the Chernoff method, prove that:

$\mathbb{P}\!\bigl(\bar{X}_n - \mu \geq t\bigr) \leq e^{-2nt^2}$

Hint

Reveal Solution

ExerciseAdvanced

Problem

Show that the exponential distribution $X \sim \text{Exp}(1)$ is not sub-Gaussian. Specifically, show that $\mathbb{E}[e^{\lambda(X-1)}]$ cannot be bounded by $e^{C\lambda^2}$ for any constant $C$ when $\lambda$ is large.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Compute the exact $\psi_2$ norm of a Rademacher variable $\varepsilon = \pm 1$ with equal probability. Then verify that the MGF bound gives $\sigma = 1$ as the sub-Gaussian parameter.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Let $X_1, \ldots, X_n$ be independent sub-Gaussian with $\|X_i\|_{\psi_2} \leq K$. Show that $\mathbb{E}[\max_{i \leq n} X_i] \leq CK\sqrt{\log n}$ using the argument: exponentiate, bound by sum, apply MGF bound, optimize $\lambda$.

Hint

Reveal Solution

Related Comparisons

• Sub-Gaussian vs. Sub-Exponential Random Variables

References

1. Vershynin, High-Dimensional Probability (2018), Chapters 2-3. Definitive modern treatment using the Orlicz norm framework. Proposition 2.5.2 for the equivalence theorem.
2. Boucheron, Lugosi, Massart, Concentration Inequalities (2013), Chapter 2. Uses the entropy method rather than Orlicz norms.
3. Wainwright, High-Dimensional Statistics (2019), Chapter 2. Clear exposition connecting sub-Gaussian theory to statistical applications.
4. van Handel, Probability in High Dimension (2016), Chapters 1-2. Excellent treatment of sub-Gaussian maxima and chaining.
5. Shalev-Shwartz and Ben-David, Understanding Machine Learning (2014), Chapters 26-28. How sub-Gaussian bounds enter learning theory.
6. 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
• Epsilon-nets and covering numbers: combining sub-Gaussian concentration with geometric arguments
• Hanson-Wright inequality: sub-Gaussian concentration for quadratic forms