Bernstein Bounds for Sums of Sub-Exponential Variables

Why Bernstein Bounds Extend Beyond Bounded Variables

A variance-sensitive concentration bound is useful when fluctuations are moderate: it can be much sharper than a bound based only on a fixed range. Bernstein bounds for bounded sums have this feature, but many variables of interest are unbounded. The sub-exponential MGF condition provides a way to retain a variance-sensitive regime while allowing a linear, rather than quadratic, tail exponent for large deviations.

The essential calculation is to multiply the moment-generating-function bounds for independent summands and then apply Chernoff's inequality. The resulting bound has two regimes. For deviations below a scale determined by the total variance proxy and the largest scale parameter, the exponent is quadratic in the deviation. Beyond that scale, it is linear.

Definition and Parameters

Definition: A random variable $X$ is centered sub-exponential with parameters $(\nu^2,b)$, where $\nu^2>0$ and $b>0$, if $E[X]=0$ and $$ \log E[e^{\lambda X}] \leq \frac{\nu^2\lambda^2}{2} \qquad\text{for every }|\lambda|<\frac{1}{b}. $$ The condition entails that the moment-generating function is finite throughout this open interval. The parameter $\nu^2$ controls the quadratic MGF bound near zero; $b$ limits how far from zero this particular bound is guaranteed.

The parameters are valid bounds, not necessarily unique or optimal. Making either parameter larger preserves validity, although it can weaken the resulting tail estimate. If $X$ has parameters $(\nu^2,b)$ and $c$ is a real constant, then $cX$ has parameters $(c^2\nu^2,|c|b)$ when $c\ne0$: substitute $c\lambda$ into the defining inequality, whose permitted range is $|c\lambda|<1/b$. A zero variable satisfies the MGF inequality for any positive parameters.

This definition uses a pure quadratic upper bound on a restricted interval. It is important not to replace that condition by a different MGF inequality without changing the proof and parameters accordingly. In particular, an upper bound by a larger expression does not imply an upper bound by a smaller one.

Worked Example: Checking Parameters for a Centered Exponential Variable

Let $E$ have the exponential distribution with rate 1, so its density is $e^{-x}$ for $x\geq0$, and let $Y=E-1$. Verify a valid pair of sub-exponential parameters for $Y$.

For $\lambda<1$, direct integration gives $$ E[e^{\lambda Y}] =e^{-\lambda}\int_0^\infty e^{\lambda x}e^{-x}\,dx =\frac{e^{-\lambda}}{1-\lambda}. $$ Since $E[E]=1$, $Y$ is centered, and for $|\lambda|<1$, $$ \log E[e^{\lambda Y}]=-\lambda-\log(1-\lambda) =\sum_{k=2}^{\infty}\frac{\lambda^k}{k}. $$ If $|\lambda|<1/2$, absolute convergence and the triangle inequality imply $$ \log E[e^{\lambda Y}] \leq \sum_{k=2}^{\infty}\frac{|\lambda|^k}{k} \leq \frac{|\lambda|^2}{2}\sum_{j=0}^{\infty}|\lambda|^j =\frac{|\lambda|^2}{2(1-|\lambda|)} \leq |\lambda|^2. $$ Thus the defining inequality holds with $(\nu^2,b)=(2,2)$, because $\nu^2\lambda^2/2=\lambda^2$ and the required domain is $|\lambda|<1/2$.

The smaller-looking pair $(1,1)$ is not justified by this argument. For example, at $\lambda=1/2$, the log-MGF is $\log 2-1/2\approx0.19315$, which exceeds $\lambda^2/2=0.125$. That value of $\lambda$ is the boundary, not part of the interval for $b=1$; however, the strict excess also holds for $\lambda$ just below $1/2$, by continuity. So $(1,1)$ fails the defining inequality on its required open interval. The verified pair $(2,2)$ avoids this error.

Bernstein’s Bound for Independent Sums

For independent summands, the individual MGF bounds combine by multiplication. The following theorem makes the resulting two-regime concentration explicit.

Theorem: Let $X_1,\ldots,X_n$ be independent, centered random variables. Suppose $X_i$ is sub-exponential with parameters $(\nu_i^2,b_i)$. Define $$ S=\sum_{i=1}^n X_i,\qquad V=\sum_{i=1}^n \nu_i^2,\qquad b=\max_{1\leq i\leq n}b_i. $$ Then, for every $t>0$, $$ P(|S|\geq t)\leq 2\exp\left\{-\frac{1}{2}\min\left(\frac{t^2}{V},\frac{t}{b}\right)\right\}. $$

Proof. For $0<\lambda<1/b$, we have $\lambda<1/b_i$ for every $i$. Independence and the individual MGF bounds give $$ \log E[e^{\lambda S}] =\sum_{i=1}^n\log E[e^{\lambda X_i}] \leq \frac{V\lambda^2}{2}. $$ Markov’s inequality applied to $e^{\lambda S}$ therefore yields $$ P(S\geq t)\leq \exp\left(-\lambda t+\frac{V\lambda^2}{2}\right). $$ If $0<t\leq V/b$, choose $\lambda=t/V$, which is positive and at most $1/b$. If equality holds at the boundary, use values increasing to $1/b$, which give the same bound by a limit. Substitution gives the one-sided bound $$ P(S\geq t)\leq \exp\left(-\frac{t^2}{2V}\right). $$ If $t>V/b$, take a sequence of positive $\lambda$ increasing to $1/b$. The Chernoff bound holds for every member of that sequence, so continuity of the expression on its right gives $$ P(S\geq t)\leq \exp\left(-\frac{t}{b}+\frac{V}{2b^2}\right). $$ Here $t>V/b$ implies $V/(2b^2)<t/(2b)$, and consequently $$ P(S\geq t)\leq \exp\left(-\frac{t}{2b}\right). $$ Combining the two cases gives $$ P(S\geq t)\leq \exp\left\{-\frac{1}{2}\min\left(\frac{t^2}{V},\frac{t}{b}\right)\right\}. $$ The variables $-X_i$ obey the same defining MGF inequalities, since those inequalities hold for both positive and negative $\lambda$. Applying the one-sided result to $-S$ bounds $P(S\leq-t)$ by the same expression. The union bound now proves the stated two-sided inequality. $\square$

The crossover is at $t=V/b$: below it, $t^2/V\leq t/b$, so the exponent is quadratic; above it, the linear term $t/b$ is the smaller term. A useful consequence is a single expression often called Bernstein form.

Corollary: Under the theorem’s assumptions, for $t>0$, $$ P(|S|\geq t)\leq 2\exp\left\{-\frac{t^2}{2(V+bt)}\right\}. $$

To verify this form, use $\lambda=t/(V+bt)$, which satisfies $0<\lambda<1/b$. Chernoff’s inequality gives an exponent at most $$ -\lambda t+\frac{V\lambda^2}{2} =-\frac{t^2(V+2bt)}{2(V+bt)^2} \leq -\frac{t^2}{2(V+bt)}. $$ The last inequality follows from $V+2bt\geq V+bt$. Applying the same calculation to $-S$ and using the union bound proves the corollary.

Worked Example: A Sum with Unequal Exponential Scales

Let $E_1,E_2$ be independent exponential variables with rate 1, and set $X_1=E_1-1$ and $X_2=2(E_2-1)$. Find a two-sided bound for $P(|X_1+X_2|\geq10)$.

The preceding calculation gives parameters $(2,2)$ for $X_1$. Scaling by 2 gives parameters $(8,4)$ for $X_2$: its log-MGF at $\lambda$ is that of $E_2-1$ at $2\lambda$, so it is bounded by $(2\lambda)^2=4\lambda^2$ whenever $|2\lambda|<1/2$, that is, $|\lambda|<1/4$. This is exactly the defining bound with $\nu^2=8$ and $b=4$.

Thus $V=2+8=10$, and the common scale is $b=\max(2,4)=4$. At $t=10$, $$ \frac{t^2}{V}=\frac{100}{10}=10,\qquad \frac{t}{b}=\frac{10}{4}=2.5. $$ The linear term is smaller, so the theorem gives $$ P(|X_1+X_2|\geq10)\leq 2e^{-(1/2)(2.5)}=2e^{-1.25}\approx0.573. $$ The numerical bound is valid, though not especially informative at this threshold. A probability bound greater than 1 is still valid but uninformative; here the bound is below 1.

Worked Example: Small and Large Deviations for a Gaussian Sum

Let $G_1,\ldots,G_{100}$ be independent $N(0,1)$ variables and let $S=\sum_{i=1}^{100}G_i$. Determine the bounds at $t=20$ and $t=200$, using $(\nu_i^2,b_i)=(1,1)$ for every term.

The Gaussian log-MGF is $\log E[e^{\lambda G_i}]=\lambda^2/2$ for every real $\lambda$, so the chosen pair is valid. Here $V=100$, $b=1$, and the crossover is $V/b=100$. At $t=20$, the deviation is in the quadratic regime: $$ \frac{t^2}{V}=\frac{400}{100}=4,\qquad \frac{t}{b}=20, \qquad P(|S|\geq20)\leq 2e^{-4/2}=2e^{-2}\approx0.271. $$ At $t=200$, it is in the linear regime: $$ \frac{t^2}{V}=\frac{40000}{100}=400,\qquad \frac{t}{b}=200, \qquad P(|S|\geq200)\leq 2e^{-200/2}=2e^{-100}. $$ The bound is quadratic in the moderate threshold and linear in the very large threshold. Choosing $b=1$ is valid but not essential for a Gaussian; other positive values also give a valid MGF bound, potentially with different usefulness.

Worked Example: Deviations of a Centered Exponential Sum

Let $Y_1,\ldots,Y_{25}$ be independent copies of $E-1$, where $E$ is exponential with rate 1. Use the verified parameters $(2,2)$ to bound deviations of $S=\sum_{i=1}^{25}Y_i$ at $t=10$ and $t=50$.

The aggregate parameters are $V=25(2)=50$ and $b=2$, so the crossover is $V/b=25$. At $t=10$, the quadratic term is smaller: $$ \frac{t^2}{V}=\frac{100}{50}=2,\qquad \frac{t}{b}=5,\qquad P(|S|\geq10)\leq2e^{-2/2}=2e^{-1}\approx0.736. $$ At $t=50$, the linear term is smaller: $$ \frac{t^2}{V}=\frac{2500}{50}=50,\qquad \frac{t}{b}=25,\qquad P(|S|\geq50)\leq2e^{-25/2}=2e^{-12.5}\approx7.45\times10^{-6}. $$ The same theorem handles both thresholds, but the controlling part of its exponent changes at $25$. For the sample mean $S/25$, the corresponding events are deviations of $0.4$ and $2$ from its mean 0, respectively.

How to Apply the Bound Carefully

A reliable application separates the assumptions from the numerical substitution. First verify that each summand is centered and that the variables are independent. Then check the defining MGF inequality on the full interval claimed for its parameters. Only after that check should the parameters be aggregated as $V=\sum_i\nu_i^2$ and $b=\max_i b_i$. Finally, compare $t$ with $V/b$, or directly compare $t^2/V$ with $t/b$, to identify the regime.

Do not infer a tighter MGF bound from a looser one. If a derivation gives an upper bound larger than $\nu^2\lambda^2/2$, it has not proved the required defining inequality.
Use a common scale at least as large as every $b_i$. The product-MGF argument requires $|\lambda|<1/b_i$ for every summand.
Keep the two-sided factor. The factor 2 comes from bounding both $S$ and $-S$; a one-sided bound has no such factor.
Check whether the result is informative. Since probabilities cannot exceed 1, a right-hand side above 1 may be replaced by 1 but offers no useful numerical control.

These bounds are useful when summands are independent and unbounded but have an MGF controlled near zero. They retain a variance-proxy scale for moderate fluctuations without claiming a quadratic exponent indefinitely. The linear regime records the limitation imposed by the finite MGF interval.

Check Your Understanding

Use the defining MGF condition and the theorem to answer the following.

For independent centered summands with $V=36$ and $b=3$, what is the crossover threshold, and which regime controls a deviation $t=6$?
Why does an upper bound on a log-MGF by an expression larger than $\nu^2\lambda^2/2$ fail to verify the sub-exponential definition with parameter $\nu^2$?
If a variable has parameters $(\nu^2,b)$, what parameters are valid for its nonzero rescaling $cX$?
Where does the factor 2 in the two-sided Bernstein bound enter the proof?
For the Bernstein-form bound, verify that $\lambda=t/(V+bt)$ lies inside the permitted MGF interval.