Bernstein’s Inequality
Concentration, STAT 210B3 minute read
Part of the STAT 210B Results Toolbox: the result as stated in my 210B notes (§2.5 — Prop. 2.30, Prop. 2.35, Cor. 2.36), plus the one proof step to recall to remember why it is true.
Statement
The notes’ headline version is the sub-exponential (\(\psi_1\)) form.
Proposition 2.30 (Bernstein’s inequality). Suppose \(X_1,\dots,X_n\) are independent random variables with \(\mathbb{E}X_i = 0\) and \(\max_i \lVert X_i\rVert_{\psi_1} < \infty\). Then for any \(t>0\),
\[\mathbb{P}\left( \sum_{i=1}^n X_i \ge t \right) \;\le\; \exp\left(-c\cdot\min\left\{ \frac{t^2}{\sum_{i=1}^n \lVert X_i\rVert_{\psi_1}^2},\ \frac{t}{\max_i \lVert X_i\rVert_{\psi_1}} \right\}\right)\]and the two-sided version holds with a factor \(2\) in front, where \(c>0\) is an absolute constant.
The explicit-constant version runs through Bernstein’s assumption (Prop. 2.33): \(X\) with mean \(\mathbb{E}X=\mu\) and variance \(\operatorname{Var}(X)=\sigma^2\) satisfies it with parameters \((\sigma, B)\) if for all \(k\in\mathbb{N}\), \(k\ge2\),
\[\mathbb{E}(X-\mu)^k \;\le\; \tfrac12 k!\,\sigma^2 B^{k-2}.\]Proposition 2.35 (Bernstein’s inequality, \((\sigma,b)\)-form). If \(X_1,\dots,X_n\) are independent zero-mean random variables with variances \((\sigma_1^2,\dots,\sigma_n^2)\) that satisfy Bernstein’s assumption with \((\sigma_i, b)\), then for all \(t>0\),
\[\mathbb{P}\left( \sum_k X_k \ge t \right) \le \exp\left( \frac{-t^2/2}{\sum_k \sigma_k^2 + bt} \right), \qquad \mathbb{P}\left( \Big\lvert \sum_k X_k \Big\rvert \ge t \right) \le 2\exp\left( \frac{-t^2/2}{\sum_k \sigma_k^2 + bt} \right).\]The \(+bt\) part creates the exponential tail part. (The notes defer the proof to a home assignment.)
Corollary 2.36. In particular, when the \(X_i\) are zero mean with \(\operatorname{Var}(X_i)=\sigma^2\) and \(\lvert X_i\rvert \le B\), the bounded-RV-is-Bernstein example (Move 1 below) plus Prop. 2.35 give
\[\mathbb{P}\left( \sum_k X_k \ge t \right) \;\le\; \exp\left( \frac{-t^2/2}{n\sigma^2 + \frac{B}{3}t} \right).\]Solving with respect to \(\delta\) in the Bernoulli case (Example 2.37(2): \(X_i\overset{iid}{\sim}\text{Bern}(p)\), centered, \(B=1\)): with probability \(1-\delta\),
\[\Big\lvert \frac1n\sum_{i=1}^n X_i \Big\rvert \;\le\; \sqrt{\frac{2\log(2/\delta)\,p(1-p)}{n}} + \frac{2\log(2/\delta)}{3n}.\]The \(\frac{2\log(2/\delta)}{3n}\) term corresponds to the \(\frac13 t\) term — if \(p\) is very small you are still not sub-Gaussian, and this term is the price to pay for it; the square-root term corresponds to \(\sum\sigma_i^2\) and is the CLT-style term.
The shape to remember: a Gaussian term driven by the variance plus a faster \(1/n\) term driven by the range. When the variance is small, Bernstein beats Hoeffding, which only sees the range.
The fundamental step
Two moves, both from Example 2.34 in the notes (the only place the expansion is actually carried out — Prop. 2.35’s proof is deferred to homework).
Move 1 — bounded \(\Rightarrow\) Bernstein with \(B = a/3\). For \(\mathbb{E}X=0\), \(\operatorname{Var}(X)=\sigma^2\), \(\lvert X\rvert\le a\):
\[\mathbb{E}X^k \;\le\; \mathbb{E}\big[X^2\lvert X\rvert^{k-2}\big] \;\le\; \sigma^2 a^{k-2}, \qquad \tfrac12 k!\,\sigma^2 (a/3)^{k-2} \;\ge\; \sigma^2 a^{k-2} \ \text{ since } \tfrac{k!}{2\cdot 3^{k-2}} \ge 1,\]so \(X\) is \((\sigma, a/3)\)-Bernstein — this is where the \(/3\) in Cor. 2.36 is born.
Move 2 — the MGF geometric series. Under Bernstein’s assumption, expand and dominate every moment beyond the second:
\[\mathbb{E}\, e^{\lambda X} = 1 + \frac{\mathbb{E}(\lambda^2 X^2)}{2} + \sum_{k\ge3}\frac{\lambda^k \mathbb{E}X^k}{k!} \;\le\; 1 + \frac{\lambda^2\sigma^2}{2} + \frac{\lambda^2\sigma^2}{2}\cdot\frac{B\lvert\lambda\rvert}{1-B\lvert\lambda\rvert} \;\le\; \exp\left(\frac{\lambda^2\sigma^2/2}{1 - B\lvert\lambda\rvert}\right).\]The memory hook: only the second moment matters until \(\lambda B\) is order one; Bernstein’s assumption taxes each higher moment by \(B^{k-2}\), and the geometric series sums to the \(1/(1-B\lvert\lambda\rvert)\) correction. Chernoff with this MGF produces the \(\sum\sigma_k^2 + bt\) denominator; boundedness enters only through Move 1, which is where the \(/3\) comes from.
Where it’s used
- Term (3) of the excess risk decomposition in the STAT 241A day-1 notes: \(\theta^\star\) is deterministic, so a single scalar Bernstein bound controls \(L_n(\theta^\star) - L(\theta^\star)\), no uniformity needed.
- The notes’ own application (Example 2.39, statistical learning in the realizable setting): for ERM over a finite class of size \(M\), \(\operatorname{Var}(Z_i) \le R(f)\) makes Bernstein self-improving on the event \(R_n(\hat f)=0\), yielding the fast rate \(R(\hat f) \le \frac{10}{3}\cdot\frac{\log(2M/\delta)}{n}\).
Leave a Comment