Bernstein's Inequality and the Sub-Exponential / Bennett Regime

Intuition Beginner

Hoeffding's inequality, which you met for sums of bounded random pieces, treats every piece as if it could swing across its whole range. That is honest but wasteful. If each piece almost always sits near its average and only rarely makes a big move, the sum hugs its mean far more tightly than Hoeffding admits. Bernstein's and Bennett's inequalities are the upgrade that notices this: they let the typical spread of each piece — its variance — set the scale, instead of the worst case.

The picture has two zones. For small deviations from the mean, the sum behaves like a bell curve: the chance of straying by an amount $t$ drops off like the Gaussian $e^{-t^2/(2v)}$, where $v$ is the total variance. This is the regime where many small wiggles add up and partly cancel. For large deviations, that bell-curve story breaks: a really big total can only happen if one or two pieces make rare, oversized jumps, and the cost of that is a gentler, straight-line-in-the-exponent decay $e^{-t/(2b)}$, set by the largest a single piece can be.

So one inequality carries two stories. Near the mean the variance rules and the tail is Gaussian; far out the per-piece size limit rules and the tail is exponential. The crossover sits where the deviation $t$ becomes comparable to variance-over-size. When variances are small, the Gaussian zone stretches much further than Hoeffding's blunt bound would let you claim, and that extra reach is exactly what learning theory and high-dimensional statistics need.

Visual Beginner

Picture the chance of a large total, plotted against how big a deviation $t$ you ask for, on a log scale so that a straight line means exponential decay. Two regimes appear, joined at a knee.

 log(tail probability)
   0 +___
     |   \__            small t:  parabola  (Gaussian, set by variance v)
     |      \_
     |        \__
     |           \__
     |              \____           knee at t ~ v/b
     |                   \------     large t:  straight line
     |                          \--- (exponential, set by max size b)
     +------------------------------- deviation t
        Gaussian zone | exponential zone

Deviation size	Which feature rules	Tail behaviour
small ($t\lesssim v/b$)	total variance $v$	Gaussian: $e^{-t^2/(2v)}$
large ($t\gtrsim v/b$)	max piece size $b$	exponential: $e^{-t/(2b)}$

The single Bernstein curve tracks the lower of the two; Hoeffding's curve floats above it whenever the variance is smaller than the worst-case range allows.

Worked example Beginner

Take $n=100$ independent fair-coin scores, each $+1$ for heads and $-1$ for tails, and look at how far the running total $S$ can drift from its mean of $0$. Each score has size at most $b=1$ and variance $1$, so the total variance is $v=100$.

Step 1. The Gaussian zone. For a small deviation, the variance controls the tail: the chance of $S\ge t$ is at most $e^{-t^2/(2v)}=e^{-t^2/200}$. For $t=20$ this gives $e^{-400/200}=e^{-2}\approx 0.135$.

Step 2. Where the knee sits. The crossover is near $t=v/b=100/1=100$. Below that, the Gaussian story is the right one; far above it, the exponential story takes over. A deviation of $20$ is well inside the Gaussian zone.

Step 3. Compare with the full Bernstein bound. Bernstein writes the tail as $\exp (-t^2/(2(v+bt/3)))$. For $t=20$: the denominator is $2(100+20/3)=2\times 106.67=213.3$, so the bound is $e^{-400/213.3}=e^{-1.876}\approx 0.153$. Close to the pure Gaussian $0.135$, because the correction $bt/3$ is small here.

Step 4. Now make the variance small. Suppose instead each score is $+1$ with chance $1/100$ and $0$ otherwise, so $b=1$ but the variance per score is about $0.0099$, giving $v\approx 0.99$. Hoeffding still uses the range and reports $e^{-t^2/(2\times 100/4)}=e^{-t^2/50}$, but Bernstein uses the tiny $v$: for $t=5$, Bernstein gives $\exp (-25/(2(0.99+5/3)))=\exp (-25/5.31)=e^{-4.7}\approx 0.009$, far below Hoeffding's $e^{-25/50}=e^{-0.5}\approx 0.607$.

What this tells us: when the pieces rarely move, the variance-aware bound is dramatically tighter — orders of magnitude — exactly where Hoeffding is blind.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $X,X_1,\dots ,X_n$ are real random variables on a common probability space, and ${\psi }_X(\lambda )=\log \mathbb{E}{e}^{\lambda (X-\mathbb{E}X)}$ denotes the centred cumulant generating function. The Chernoff/Markov machinery — the bound $\mathrm{Pr}(X-\mathbb{E}X\ge t)\le e^{-\lambda t+{\psi }_X(\lambda )}$ optimised over $\lambda \ge 0$ — is imported from the large-deviations spine 37.07.02 and applied here under finite-MGF hypotheses guaranteed by the classes below; the analytic control of $\lambda \mapsto \mathbb{E}{e}^{\lambda X}$ near the origin is the moment-generating-function theory of 37.03.01.

Definition (sub-Gaussian variable). A centred random variable $X$ is sub-Gaussian with proxy ${\sigma }^2$ if ${\psi }_X(\lambda )\le {\sigma }^2{\lambda }^2/2$ for all $\lambda \in \mathbb{R}$. The bounded variables of Hoeffding's lemma 40.07.05 are sub-Gaussian with ${\sigma }^2=(b-a{)}^2/4$ for support $[a,b]$. The class is also characterised by Gaussian tail decay $\mathrm{Pr}(|X|\ge t)\le 2e^{-t^2/(2{\sigma }^2)}$, by the moment growth $\Vert X{\Vert }_{L^p}\le C\sigma \sqrt{p}$, and by finiteness of the Orlicz norm

$$\Vert X{\Vert }_{{\psi }_2}=\inf \{t>0:\mathbb{E}{e}^{X^2/t^2}\le 2\},$$

all four being equivalent up to absolute constants ^{[Vershynin 2018]}.

Definition (sub-exponential variable). A centred random variable $X$ is sub-exponential with parameters $({\nu }^2,b)$, written $X\in \mathrm{SE}({\nu }^2,b)$, if

$${\psi }_X(\lambda )\le \frac{{\nu }^2{\lambda }^2}{2}\text{for all }|\lambda |<\frac{1}{b}.$$

The defining feature is that the quadratic cgf bound holds only in a neighbourhood of the origin $|\lambda |<1/b$, not on all of $\mathbb{R}$; outside that neighbourhood the cgf may be infinite. The class is characterised equivalently by exponential tail decay $\mathrm{Pr}(|X|\ge t)\le 2e^{-t/K_1}$, by linear moment growth $\Vert X{\Vert }_{L^p}\le K_{2}p$, by finiteness of the MGF of $|X|$ in a neighbourhood of $0$, and by finiteness of the Orlicz norm

$$\Vert X{\Vert }_{{\psi }_1}=\inf \{t>0:\mathbb{E}{e}^{|X|/t}\le 2\},$$

the parameters in any one bounding the parameters in the others up to absolute constants ^{[Vershynin 2018]}. The product of two sub-Gaussian variables is sub-exponential: $\Vert XY{\Vert }_{{\psi }_1}\le \Vert X{\Vert }_{{\psi }_2}\Vert Y{\Vert }_{{\psi }_2}$, so squares of sub-Gaussian variables — and hence centred chi-squared summands — are sub-exponential.

Definition (Bernstein condition). A random variable $X$ with mean $\mu$ satisfies the Bernstein condition with parameters $({\sigma }^2,b)$ if its centred moments obey

$$|\mathbb{E}(X-\mu {)}^k|\le \frac{1}{2}k!{\sigma }^2{b}^{k-2}\text{for all integers }k\ge 2.$$

Bounded variables with $|X-\mu |\le b$ and variance ${\sigma }^2$ satisfy it; so do sub-exponential variables. Summing the geometric series produced by these moment bounds yields the cgf control ${\psi }_X(\lambda )\le \frac{{\sigma }^2{\lambda }^2}{2(1-b|\lambda |)}$ for $|\lambda |<1/b$, identifying $X$ as $\mathrm{SE}({\sigma }^2/(1-b|\lambda |),b)$-type with ${\nu }^2={\sigma }^2$ near the origin ^{[Wainwright 2019]}.

Counterexamples to common slips Intermediate+

• "Sub-exponential is just sub-Gaussian with worse constants." No: the qualitative difference is the domain of the cgf bound. A sub-Gaussian variable has ${\psi }_X(\lambda )\le {\sigma }^2{\lambda }^2/2$ for all $\lambda$; a sub-exponential one only for $|\lambda |<1/b$. This is why sub-Gaussian tails are $e^{-t^2}$ everywhere while sub-exponential tails turn over to $e^{-t}$.

• "The chi-squared variable $Z^2$ is sub-Gaussian because $Z$ is." The square of a standard Gaussian is sub-exponential, not sub-Gaussian: its MGF $\mathbb{E}{e}^{\lambda Z^2}=(1-2\lambda {)}^{-1/2}$ blows up at $\lambda =1/2$, so the cgf is finite only for $\lambda <1/2$ — the signature of $\mathrm{SE}$, with parameter $b=2$.

• "Bernstein always beats Hoeffding." Only when the variance is genuinely smaller than the range-based proxy. For a centred variable taking $\pm b$ with equal probability, ${\sigma }^2=b^2$, and Bernstein and Hoeffding give the same Gaussian-zone rate; the gain appears strictly when ${\sigma }^2\ll b^2$.

• "The two regimes are different inequalities." They are one inequality, $\exp (-t^2/(2(v+bt/3)))$, read in two asymptotic limits. The single bound interpolates; the regimes are not glued from separate estimates.

Key theorem with proof Intermediate+

The signature result is Bernstein's inequality: a sum of independent variables satisfying the Bernstein condition concentrates with a tail that is Gaussian for small deviations and exponential for large ones, governed by the total variance and the per-summand size bound. The proof is the Chernoff/MGF method of 37.07.02 applied to the variance-aware cgf bound, in place of the variance-blind Hoeffding bound of 40.07.05.

Theorem (Bernstein's inequality). Let $X_1,\dots ,X_n$ be independent with $\mathbb{E}{X}_i=0$, each satisfying the Bernstein condition with parameters $({\sigma }_i^2,b)$ for a common $b$, and set $v={\sum }_{i=1}^n{\sigma }_i^2$. Then for every $t>0$,

$$\mathrm{Pr}(\sum _{i=1}^n{X}_i\ge t)\le \exp \left(\frac{-t^2}{2(v+bt)}\right),$$

and the two-sided bound holds with a factor $2$. Equivalently,

$$\mathrm{Pr}(\sum _i{X}_i\ge t)\le \{\begin{array}{ll}\exp (-t^2/(4v)),& t\le v/b,\\ \exp (-t/(4b)),& t>v/b.\end{array}$$

^{[Bennett 1962]}

Proof. Each summand satisfies the cgf bound ${\psi }_{X_i}(\lambda )=\log \mathbb{E}{e}^{\lambda X_i}\le \frac{{\sigma }_i^2{\lambda }^2}{2(1-b\lambda )}$ for $0\le \lambda <1/b$, obtained from the Bernstein moment condition by expanding the exponential and summing the geometric series:

$$\mathbb{E}{e}^{\lambda X_i}=1+\sum _{k\ge 2}\frac{{\lambda }^k\mathbb{E}{X}_i^k}{k!}\le 1+\frac{{\sigma }_i^2{\lambda }^2}{2}\sum _{k\ge 2}(b\lambda {)}^{k-2}=1+\frac{{\sigma }_i^2{\lambda }^2}{2(1-b\lambda )}\le \exp (\frac{{\sigma }_i^2{\lambda }^2}{2(1-b\lambda )}),$$

the last step from $1+u\le e^u$. By independence the cgf of the sum adds: with $S={\sum }_i{X}_i$,

$${\psi }_S(\lambda )=\sum _{i=1}^n{\psi }_{X_i}(\lambda )\le \frac{v{\lambda }^2}{2(1-b\lambda )},0\le \lambda <\frac{1}{b}.$$

The Chernoff bound of 37.07.02 gives $\mathrm{Pr}(S\ge t)\le \exp (-\lambda t+{\psi }_S(\lambda ))\le \exp (-\lambda t+\frac{v{\lambda }^2}{2(1-b\lambda )})$ for any admissible $\lambda$. Choosing $\lambda =\frac{t}{v+bt}\in [0,1/b)$ — the value that balances the linear gain against the quadratic cost — gives $1-b\lambda =v/(v+bt)$ and, after substitution,

$$-\lambda t+\frac{v{\lambda }^2}{2(1-b\lambda )}=-\frac{t^2}{v+bt}+\frac{t^2}{2(v+bt)}=-\frac{t^2}{2(v+bt)},$$

which is the stated bound. The two-regime form follows by comparing $v$ and $bt$ in the denominator: for $t\le v/b$ the term $bt\le v$, so $v+bt\le 2v$ and the exponent is at most $-t^2/(4v)$; for $t>v/b$ the term $bt>v$, so $v+bt\le 2bt$ and the exponent is at most $-t/(4b)$. The two-sided bound applies the one-sided estimate to $-S$. $\square$

Corollary (Bennett's inequality). Under the same hypotheses with each $X_i\le b$ almost surely, the sharper bound $\mathrm{Pr}(S\ge t)\le \exp (-\frac{v}{b^2}h(bt/v))$ holds, where $h(u)=(1+u)\log (1+u)-u$. Proof. Using $X_i\le b$, the per-summand cgf obeys ${\psi }_{X_i}(\lambda )\le \frac{{\sigma }_i^2}{b^2}(e^{\lambda b}-1-\lambda b)$ from the inequality $e^{\lambda x}-1-\lambda x\le \frac{x^2}{b^2}(e^{\lambda b}-1-\lambda b)$ for $x\le b$; summing and Chernoff-optimising at $\lambda =\frac{1}{b}\log (1+bt/v)$ produces $-\frac{v}{b^2}h(bt/v)$, with $h(u)=(1+u)\log (1+u)-u\ge \frac{u^2}{2(1+u/3)}$, the last estimate recovering Bernstein from Bennett ^{[Bennett 1962]}. $\square$

Bridge. Bernstein's inequality is the foundational reason that variance-aware concentration interpolates between two worlds: the Chernoff method converts the variance-controlled cgf bound ${\psi }_S(\lambda )\le v{\lambda }^2/(2(1-b\lambda ))$ — quadratic near the origin, with a pole at $\lambda =1/b$ — into a tail that is Gaussian for $t\lesssim v/b$ and exponential for $t\gtrsim v/b$, and this is exactly the analytic fingerprint of the sub-exponential class, where the cgf is quadratic only on a neighbourhood of $0$. The construction builds toward the chi-squared and sample-variance tails of the Advanced results, where the squared-Gaussian summands are sub-exponential with $b=2$, and the same Bernstein template appears again in covariance estimation, the restricted-eigenvalue conditions of high-dimensional regression, and the deviation bounds of statistical learning theory. This generalises Hoeffding 40.07.05, whose variance-blind proxy ${\sigma }^2=b^2/4$ is recovered as the special case $v=n{b}^2/4$ where variance equals the worst-case range; putting these together, Bernstein and Hoeffding are the same Chernoff argument run against a sharper and a cruder cgf bound, and the bridge is that both are Cramér-type estimates 37.07.02, one keeping the variance term that the other discards.

Exercises Intermediate+

Advanced results Master

The Bernstein/Bennett tail is the variance-aware core of the concentration toolkit, and it extends along three axes: the sub-gamma reformulation that makes the two-regime structure intrinsic, the entropy-method derivation that sharpens constants and reaches functionals, and the matrix lift that drives high-dimensional statistics.

Theorem 1 (sub-gamma characterisation). A centred variable $X$ is sub-gamma with variance factor $v$ and scale $b$, written ${\Gamma }_{+}(v,b)$, if ${\psi }_X(\lambda )\le \frac{v{\lambda }^2}{2(1-b\lambda )}$ for $0\le \lambda <1/b$. This is equivalent, up to absolute constants, to sub-exponentiality, and the Cramér transform of the sub-gamma cgf bound is exactly the Bernstein rate: ${\psi }_X^{\ast }(t)\ge \frac{t^2}{2(v+bt)}$, equivalently ${\psi }_X^{\ast }(t)=\frac{v}{b^2}h(bt/v)$ with the Bennett rate $h(u)=(1+u)\log (1+u)-u$ ^{[Boucheron Lugosi Massart 2013]}. The sub-gamma class is closed under independent sums with additive $v$ and constant $b$, so the whole theory is the statement that the empirical mean of ${\Gamma }_{+}(v,b)$ variables is ${\Gamma }_{+}(v/n,b/n)$ — the Bernstein tail is the fixed point of this convolution semigroup. The Cramér rate function machinery 37.07.02 supplies the conjugate: where Cramér extracts the exact rate ${\Lambda }^{\ast }$ for a specific law, Bernstein settles for the upper envelope $h$ that holds across the entire sub-gamma class.

Theorem 2 (entropy method and self-bounding refinement). The Bernstein bound is recovered, with improved constants, by the entropy (modified log-Sobolev) method: for $S={\sum }_i{X}_i$ the entropy functional $\mathrm{Ent}(e^{\lambda S})=\mathbb{E}[\lambda S{e}^{\lambda S}]-\mathbb{E}[e^{\lambda S}]\log \mathbb{E}[e^{\lambda S}]$ tensorises across independent coordinates, and a single one-coordinate inequality integrates up to the cgf bound ^{[Boucheron Lugosi Massart 2013]}. For a self-bounding functional $Z=f(X_1,\dots ,X_n)$ — one with $0\le Z-Z_i\le 1$ and ${\sum }_i(Z-Z_i)\le Z$, where $Z_i$ omits coordinate $i$ — the method yields $\mathrm{Pr}(Z\ge \mathbb{E}Z+t)\le \exp (-t^2/(2(\mathbb{E}Z+t/3)))$, a Bernstein tail with variance proxy $\mathbb{E}Z$ itself. This is the sharpest route to the configuration-function, empirical-process-supremum, and Rademacher-complexity deviation bounds of statistical learning theory, where the bounded-difference family of 40.07.05 gives only the variance-blind $\sqrt{n}$ scale.

Theorem 3 (matrix Bernstein inequality). Let $X_1,\dots ,X_n$ be independent self-adjoint random matrices in ${\mathbb{C}}^{d\times d}$ with $\mathbb{E}{X}_i=0$, ${\lambda }_{\max }(X_i)\le b$ almost surely, and matrix variance ${\sigma }^2=\Vert {\sum }_i\mathbb{E}{X}_i^2{\Vert }_{\mathrm{op}}$. Then

$$\mathrm{Pr}\left({\lambda }_{\max }\right(\sum _i{X}_i)\ge t)\le d\exp \left(\frac{-t^2}{2({\sigma }^2+bt/3)}\right),$$

the scalar Bernstein bound times the ambient dimension $d$ ^{[Wainwright 2019]}. The proof replaces the scalar MGF by the matrix MGF $\mathbb{E}\mathrm{tr}{e}^{\lambda {\sum }_i{X}_i}$ and the multiplicativity of $\mathbb{E}{e}^{\lambda X}$ by the Lieb-concavity-based subadditivity of matrix cumulants (Ahlswede-Winter, Tropp). The dimensional factor $d$ enters through the trace bound ${\lambda }_{\max }\le \mathrm{tr}$; for covariance estimation this is the result that controls $\Vert \hat{\Sigma }-\Sigma {\Vert }_{\mathrm{op}}$ at rate $\sqrt{(d+\log (1/\delta ))/n}$ for sub-Gaussian rows.

Theorem 4 (Bernstein for sub-exponential sums, Vershynin form). For independent centred sub-exponential $X_i$ with $\Vert X_i{\Vert }_{{\psi }_1}\le K$,

$$\mathrm{Pr}\left(\right|\sum _{i=1}^n{X}_i|\ge t)\le 2\exp (-c\min (\frac{t^2}{n{K}^2},\frac{t}{K}\left)\right)$$

for an absolute constant $c>0$ ^{[Vershynin 2018]}. The $\min$ of a quadratic and a linear term is the explicit form of the two-regime interpolation: the quadratic dominates for $t\le nK$ (Gaussian zone) and the linear for $t>nK$ (exponential zone). Specialising to the centred chi-squared $X_i=Z_i^2-1$ with $\Vert X_i{\Vert }_{{\psi }_1}=O(1)$ recovers $\mathrm{Pr}(|\frac{1}{n}\sum (Z_i^2-1)|\ge t)\le 2\exp (-cn\min (t^2,t))$, the workhorse tail for sample-variance, Johnson-Lindenstrauss, and restricted-isometry estimates.

Synthesis. Bernstein's inequality is one Chernoff argument carrying a variance term the cruder bounds discard, and the foundational reason it interpolates is the analytic shape of the sub-exponential cgf: quadratic near the origin with a pole at $\lambda =1/b$, so its Cramér conjugate is Gaussian for small $t$ and linear for large $t$. This is exactly the sub-gamma fixed point — the empirical mean of ${\Gamma }_{+}(v,b)$ variables stays ${\Gamma }_{+}$ — and it generalises Hoeffding 40.07.05, whose variance-blind proxy is the worst-case special case where variance equals range; putting these together, Hoeffding, Bennett, and Bernstein are a single Chernoff estimate read against cgf bounds of decreasing crudeness, all of them Cramér-type 37.07.02 surrogates for the exact rate. The central insight is that the variance term is what statistics needs: it keeps the small-deviation tail Gaussian, so a union bound over $d$ or $d^2$ events costs only $\sqrt{\log d}$, the mechanism that makes covariance estimation, sparse regression, and learning-theory generalisation bounds work in high dimensions, where products of sub-Gaussian coordinates are sub-exponential and Hoeffding is simply unavailable. The entropy method is dual to the Chernoff route — tensorising a single coordinate inequality rather than multiplying cgfs — and it sharpens the constants and reaches self-bounding functionals the martingale and MGF arguments cannot; the matrix lift, finally, shows the whole structure survives non-commutativity at the cost of one dimensional factor, and the bridge upward at every level is the same: keep the variance, pay only for the rare large jump.

Full proof set Master

Proposition 1 (sub-gamma cgf bound from the Bernstein condition). If a centred $X$ satisfies $|\mathbb{E}{X}^k|\le \frac{1}{2}k!{\sigma }^2{b}^{k-2}$ for all $k\ge 2$, then ${\psi }_X(\lambda )\le {\sigma }^2{\lambda }^2/(2(1-b\lambda ))$ for $0\le \lambda <1/b$.

Proof. Expanding the MGF and using $\mathbb{E}X=0$, $\mathbb{E}{e}^{\lambda X}=1+{\sum }_{k\ge 2}\frac{{\lambda }^k}{k!}\mathbb{E}{X}^k$. The moment bound gives $\frac{{\lambda }^k}{k!}|\mathbb{E}{X}^k|\le \frac{1}{2}{\sigma }^2{\lambda }^2(b\lambda {)}^{k-2}$, so summing the geometric series for $|b\lambda |<1$,

$$\mathbb{E}{e}^{\lambda X}\le 1+\frac{1}{2}{\sigma }^2{\lambda }^2\sum _{j\ge 0}(b\lambda {)}^j=1+\frac{{\sigma }^2{\lambda }^2}{2(1-b\lambda )}\le \exp (\frac{{\sigma }^2{\lambda }^2}{2(1-b\lambda )}),$$

using $1+u\le e^u$. Taking logarithms gives the cgf bound. $\square$

Proposition 2 (Bernstein's inequality). Let $X_1,\dots ,X_n$ be independent centred variables each satisfying the Bernstein condition with $({\sigma }_i^2,b)$, and $v={\sum }_i{\sigma }_i^2$. Then $\mathrm{Pr}({\sum }_i{X}_i\ge t)\le \exp (-t^2/(2(v+bt)))$.

Proof. By Proposition 1 and independence, the cgf of $S={\sum }_i{X}_i$ obeys ${\psi }_S(\lambda )={\sum }_i{\psi }_{X_i}(\lambda )\le v{\lambda }^2/(2(1-b\lambda ))$ for $0\le \lambda <1/b$. The Chernoff bound 37.07.02 gives $\mathrm{Pr}(S\ge t)\le \exp (-\lambda t+v{\lambda }^2/(2(1-b\lambda )))$. Set $\lambda =t/(v+bt)$, admissible since $t/(v+bt)<1/b$; then $1-b\lambda =v/(v+bt)$ and

$$-\lambda t+\frac{v{\lambda }^2}{2(1-b\lambda )}=-\frac{t^2}{v+bt}+\frac{t^2}{2(v+bt)}=-\frac{t^2}{2(v+bt)}.\square$$

Proposition 3 (Bennett's inequality). Let $X_1,\dots ,X_n$ be independent centred with $X_i\le b$ almost surely and $v={\sum }_i\mathbb{E}{X}_i^2$. Then $\mathrm{Pr}({\sum }_i{X}_i\ge t)\le \exp (-\frac{v}{b^2}h(bt/v))$, $h(u)=(1+u)\log (1+u)-u$.

Proof. For $x\le b$ and $\lambda \ge 0$ the function $\varphi (x)=(e^{\lambda x}-1-\lambda x)/x^2$ (extended by ${\lambda }^2/2$ at $0$) is non-decreasing, so $\varphi (x)\le \varphi (b)$, giving $e^{\lambda x}-1-\lambda x\le \frac{x^2}{b^2}(e^{\lambda b}-1-\lambda b)$. Taking expectations of $e^{\lambda X_i}=1+\lambda X_i+(e^{\lambda X_i}-1-\lambda X_i)$ and using $\mathbb{E}{X}_i=0$,

$$\mathbb{E}{e}^{\lambda X_i}\le 1+\frac{\mathbb{E}{X}_i^2}{b^2}(e^{\lambda b}-1-\lambda b)\le \exp (\frac{{\sigma }_i^2}{b^2}(e^{\lambda b}-1-\lambda b)).$$

Summing the cgfs, ${\psi }_S(\lambda )\le \frac{v}{b^2}(e^{\lambda b}-1-\lambda b)$. The Chernoff bound is $\exp (-\lambda t+\frac{v}{b^2}(e^{\lambda b}-1-\lambda b))$; minimising over $\lambda \ge 0$ at $\lambda =\frac{1}{b}\log (1+bt/v)$ (where the derivative $-t+\frac{v}{b}(e^{\lambda b}-1)=0$) substitutes to $-\frac{v}{b^2}h(bt/v)$ after simplification. $\square$

Proposition 4 (Bennett implies Bernstein). For all $u\ge 0$, $h(u)=(1+u)\log (1+u)-u\ge \frac{u^2}{2(1+u/3)}=\frac{u^2/2}{1+u/3}$, so Bennett's bound implies $\mathrm{Pr}(S\ge t)\le \exp (-t^2/(2(v+bt/3)))$.

Proof. Let $g(u)=h(u)(1+u/3)-u^2/2$; then $g(0)=0$, and differentiating, $g^{\prime }(u)=(1+u/3)\log (1+u)+\frac{1}{3}h(u)-u$, with $g^{\prime }(0)=0$, and $g^{\prime \prime }(u)=\frac{1}{3}\log (1+u)+(1+u/3)/(1+u)+\frac{1}{3}\log (1+u)-1=\frac{2}{3}\log (1+u)+\frac{1+u/3}{1+u}-1$. The term $\frac{1+u/3}{1+u}=1-\frac{2u/3}{1+u}$, so $g^{\prime \prime }(u)=\frac{2}{3}\log (1+u)-\frac{2u/3}{1+u}=\frac{2}{3}(\log (1+u)-\frac{u}{1+u})\ge 0$ since $\log (1+u)\ge u/(1+u)$. Hence $g^{\prime }$ is non-decreasing from $0$, so $g^{\prime }\ge 0$, so $g$ is non-decreasing from $0$, so $g\ge 0$, which is the claimed inequality. Substituting $u=bt/v$ into Bennett's bound, $\frac{v}{b^2}h(bt/v)\ge \frac{v}{b^2}\cdot \frac{(bt/v{)}^2/2}{1+bt/(3v)}=\frac{t^2/2}{v+bt/3}=\frac{t^2}{2(v+bt/3)}$. $\square$

Proposition 5 (centred chi-squared is sub-gamma with ${\nu }^2=2$, $b=2$). For $Z$ standard Gaussian, $Y=Z^2-1$ satisfies ${\psi }_Y(\lambda )\le {\lambda }^2/(1-2\lambda )$ for $0\le \lambda <1/2$, hence $Y\in {\Gamma }_{+}(2,2)$.

Proof. The MGF of $Z^2$ is $\mathbb{E}{e}^{\lambda Z^2}=(1-2\lambda {)}^{-1/2}$ for $\lambda <1/2$ (Gaussian integral), so ${\psi }_Y(\lambda )=\log \mathbb{E}{e}^{\lambda (Z^2-1)}=-\lambda -\frac{1}{2}\log (1-2\lambda )$. Using $-\frac{1}{2}\log (1-2\lambda )=\frac{1}{2}{\sum }_{k\ge 1}\frac{(2\lambda {)}^k}{k}=\lambda +{\sum }_{k\ge 2}\frac{(2\lambda {)}^k}{2k}$, the linear terms cancel and

$${\psi }_Y(\lambda )=\sum _{k\ge 2}\frac{(2\lambda {)}^k}{2k}\le \sum _{k\ge 2}\frac{(2\lambda {)}^k}{2\cdot 2}=\frac{(2\lambda {)}^2}{4}\sum _{j\ge 0}(2\lambda {)}^j=\frac{{\lambda }^2}{1-2\lambda },$$

matching ${\nu }^2{\lambda }^2/(2(1-b\lambda ))$ with ${\nu }^2=2$, $b=2$. Applying Proposition 2 to $S_n={\sum }_i{Y}_i$ with $v=2n$ gives $\mathrm{Pr}(S_n\ge t)\le \exp (-t^2/(2(2n+2t)))$, the chi-squared tail. $\square$

Connections Master

• This unit is the variance-aware completion of the bounded-difference concentration family of 40.07.05: Hoeffding/Azuma/McDiarmid keep only the worst-case range, while Bernstein and Bennett keep the variance, and the foundational reason both live in the same theory is that all are Chernoff/MGF estimates — Hoeffding's lemma is the special case of the Bernstein cgf bound where the variance proxy is maximal, so the bounded-difference inequalities are recovered by discarding the variance term proved here.

• The Chernoff-and-conjugate machinery is imported wholesale from the Cramér large-deviations spine 37.07.02: where Cramér extracts the exact rate ${\Lambda }^{\ast }$ for a fixed law by matching an upper Chernoff bound to a lower tilting bound, Bernstein settles for the universal upper rate $t^2/(2(v+bt))$ that holds across the entire sub-gamma class, so the Bennett rate function $h$ is precisely the Cramér conjugate of the sub-gamma cgf envelope rather than of any single $\Lambda$.

• The analytic substrate — finiteness and convexity of $\lambda \mapsto \log \mathbb{E}{e}^{\lambda X}$ near the origin, which is exactly what fails for heavy tails and holds for the sub-exponential class — is the moment-generating-function theory of 37.03.01; the sub-exponential / sub-Gaussian dichotomy is the statement about where in the complex-$\lambda$ plane the MGF is analytic, sub-Gaussian meaning entire-order-two growth and sub-exponential meaning a finite radius of convergence $1/b$.

• The chi-squared and sample-variance tails proved here are the entry point to the high-dimensional-statistics chapter and to statistical learning theory: covariance-matrix estimation, Johnson-Lindenstrauss dimension reduction, restricted-isometry and restricted-eigenvalue conditions for sparse regression, and Rademacher/empirical-process generalisation bounds all reduce to Bernstein-type control of sums of sub-exponential products, where the variance term is what keeps a union bound over $d$ events at the $\sqrt{\log d}$ cost that makes high-dimensional inference tractable.

Historical & philosophical context Master

The variance-aware exponential inequality originates with Sergei Bernstein in the 1920s ^{[Bernstein 1924]}, who, working in the Russian probability tradition of Chebyshev and Markov, established exponential tail bounds for sums of independent variables that retained the variance rather than collapsing to the range — sharpening the Chebyshev second-moment bound to an exponential one under the moment condition that now bears his name. The bound for bounded summands was given its modern clean form by George Bennett in 1962 ^{[Bennett 1962]} in the Journal of the American Statistical Association, who derived the rate function $h(u)=(1+u)\log (1+u)-u$ and showed it dominates the Hoeffding and Chebyshev estimates; the same year Hoeffding published his variance-blind bound, and the relationship between the two has structured the concentration literature since.

The recasting of these inequalities through the sub-Gaussian and sub-exponential Orlicz-norm framework, and the systematic non-asymptotic viewpoint, is the work of Boucheron, Lugosi, and Massart ^{[Boucheron Lugosi Massart 2013]}, who connected Bernstein's bound to the entropy method and the self-bounding refinements, and of Vershynin ^{[Vershynin 2018]} and Wainwright ^{[Wainwright 2019]}, whose texts established the sub-Gaussian/sub-exponential dichotomy as the organising vocabulary of high-dimensional probability and statistics. The matrix lift is due to Ahlswede and Winter and to Tropp, building on Lieb's concavity theorem, completing the transfer of the scalar Bernstein argument to the non-commutative setting that covariance estimation requires.

Bibliography Master

@article{bernstein1924,
  author  = {Bernstein, Sergei N.},
  title   = {On a modification of Chebyshev's inequality and on the error in Laplace's formula},
  journal = {Uchen. Zapiski Nauchno-Issled. Kafedr Ukrainy, Otd. Mat.},
  volume  = {1},
  pages   = {38--49},
  year    = {1924},
  note    = {In Russian; reprinted in Bernstein, Collected Works, vol. IV}
}

@article{bennett1962,
  author  = {Bennett, George},
  title   = {Probability inequalities for the sum of independent random variables},
  journal = {Journal of the American Statistical Association},
  volume  = {57},
  number  = {297},
  pages   = {33--45},
  year    = {1962}
}

@article{hoeffding1963bernstein,
  author  = {Hoeffding, Wassily},
  title   = {Probability inequalities for sums of bounded random variables},
  journal = {Journal of the American Statistical Association},
  volume  = {58},
  number  = {301},
  pages   = {13--30},
  year    = {1963}
}

@book{boucheronlugosimassart2013bern,
  author    = {Boucheron, St\'{e}phane and Lugosi, G\'{a}bor and Massart, Pascal},
  title     = {Concentration Inequalities: A Nonasymptotic Theory of Independence},
  publisher = {Oxford University Press},
  year      = {2013}
}

@book{vershynin2018hdp,
  author    = {Vershynin, Roman},
  title     = {High-Dimensional Probability: An Introduction with Applications in Data Science},
  publisher = {Cambridge University Press},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  year      = {2018}
}

@book{wainwright2019hds,
  author    = {Wainwright, Martin J.},
  title     = {High-Dimensional Statistics: A Non-Asymptotic Viewpoint},
  publisher = {Cambridge University Press},
  series    = {Cambridge Series in Statistical and Probabilistic Mathematics},
  year      = {2019}
}

@article{tropp2012matrix,
  author  = {Tropp, Joel A.},
  title   = {User-friendly tail bounds for sums of random matrices},
  journal = {Foundations of Computational Mathematics},
  volume  = {12},
  number  = {4},
  pages   = {389--434},
  year    = {2012}
}

@article{ahlswedewinter2002,
  author  = {Ahlswede, Rudolf and Winter, Andreas},
  title   = {Strong converse for identification via quantum channels},
  journal = {IEEE Transactions on Information Theory},
  volume  = {48},
  number  = {3},
  pages   = {569--579},
  year    = {2002}
}