TCSLib

101 Learning Theory — Bernstein

101.1 Overview

This module develops a two-parameter sub-exponential MGF condition, ProbabilityTheory.HasBernsteinMGF, and derives from it one-sided, other-sided, and two-sided Bernstein-type concentration inequalities. The main application is a tail bound for the deviation of \(\sum _i Y_i^2\) from its mean \(n\sigma ^2\) for an independent identically-distributed family, which serves as the central reusable tool for Johnson–Lindenstrauss-style concentration arguments.

101.2 Declarations

Definition 101.1 Bernstein MGF condition
✓
#

\(\texttt{ProbabilityTheory.HasBernsteinMGF}\ X\ \mu \ c\ t_{\max }\) is a predicate on a random variable \(X : \Omega \to \mathbb {R}\), a measure \(\mu \), and real parameters \(c, t_{\max } \ge 0\). It asserts that for every \(t\) with \(|t| \le t_{\max }\), the exponential moment \(e^{tX}\) is \(\mu \)-integrable, and the moment generating function satisfies \(\mathbf{E}_\mu [e^{tX}] \le e^{c t^2}\). The pair \((c, t_{\max })\) parametrizes a “two-parameter sub-exponential” family: \(c\) controls the quadratic growth near zero and \(t_{\max }\) bounds the radius of validity.

Lemma 101.2 Sub-exponential MGF bound for independent sums
✓

Let \((X_i)_{i \in \iota }\) be a family of measurable real random variables on a probability space \((\Omega , \mu )\) that are mutually independent, and let \(s\) be a finite set of indices. Fix a radius \(t_{\max }\), and suppose that for each \(i \in s\) there is a constant \(c_i\) such that \(e^{tX_i}\) is \(\mu \)-integrable and \(\mathbf{E}_\mu [e^{tX_i}] \le e^{c_i t^2}\) for every \(t\) with \(|t| \le t_{\max }\). Then the sum \(\sum _{i \in s} X_i\) satisfies the same two-parameter sub-exponential bound with radius \(t_{\max }\) and constant \(\sum _{i \in s} c_i\): for every \(t\) with \(|t| \le t_{\max }\), the moment \(e^{t \sum _{i \in s} X_i}\) is \(\mu \)-integrable and \(\mathbf{E}_\mu \! \left[e^{t \sum _{i \in s} X_i}\right] \le e^{(\sum _{i \in s} c_i)\, t^2}\).

Lemma 101.3 Upper-tail Bernstein bound
✓

Let \(X : \Omega \to \mathbb {R}\) be a random variable on a finite measure space \((\Omega , \mu )\), and suppose \(X\) satisfies the Bernstein moment-generating-function condition with parameters \(c\) and \(t_{\max }\): for every \(t\) with \(\left\lvert t\right\rvert \le t_{\max }\) the exponential moment \(e^{tX}\) is \(\mu \)-integrable and \(\mathbb {E}_\mu [e^{tX}] \le e^{c t^2}\). If \(c \gt 0\), then for every \(s\) with \(0 \le s \le 2c\, t_{\max }\) the upper tail obeys

\[ \mu \bigl(\{ \omega : s \le X(\omega )\} \bigr) \; \le \; \exp \! \Bigl(-\frac{s^2}{4c}\Bigr). \]
Lemma 101.4 Lower-tail Bernstein bound
✓

Let \(X : \Omega \to \mathbb {R}\) be a random variable on a probability space carrying a finite measure \(\mu \), and suppose \(X\) satisfies the Bernstein moment generating function condition with parameters \(c\) and \(t_{\max }\): for every \(t\) with \(|t| \le t_{\max }\), the exponential moment \(e^{tX}\) is \(\mu \)-integrable and \(\mathbb {E}_\mu [e^{tX}] \le e^{c t^2}\). If \(c \gt 0\), then for every \(s\) with \(0 \le s \le 2 c\, t_{\max }\),

\[ \mu \bigl(\{ \omega \mid X(\omega ) \le -s\} \bigr) \; \le \; \exp \! \Bigl(-\frac{s^2}{4c}\Bigr). \]
Lemma 101.5 Two-sided Bernstein tail bound
✓

Let \(X : \Omega \to \mathbb {R}\) be a random variable on a probability space \((\Omega , \mu )\), and let \(c, t_{\max } \ge 0\) be real parameters such that \(X\) satisfies the Bernstein moment generating function condition with parameters \(c\) and \(t_{\max }\): for every \(t\) with \(\left\lvert t\right\rvert \le t_{\max }\) the exponential moment \(e^{tX}\) is \(\mu \)-integrable and \(\mathbb {E}_\mu [e^{tX}] \le e^{c t^2}\). If \(c \gt 0\), then for every \(s\) with \(0 \le s \le 2 c\, t_{\max }\),

\[ \mu \bigl(\{ \omega \mid s \lt \left\lvert X(\omega )\right\rvert \} \bigr) \; \le \; 2\exp \! \Bigl(-\frac{s^2}{4c}\Bigr). \]
Lemma 101.6 Bernstein tail bound for a sum of centered squares
✓

Let \((Y_i)_{i}\) be a finite family of measurable real random variables on a probability space \((\Omega , \mu )\), indexed by a finite set of cardinality \(n\), and suppose the \(Y_i\) are mutually independent. Fix real numbers \(\sigma ^2\), \(c \gt 0\), and \(t_{\max }\), and suppose that for each \(i\) the centered square \(Y_i^2 - \sigma ^2\) satisfies the Bernstein MGF condition with parameters \(c\) and \(t_{\max }\). Then for every \(s\) with \(0 \le s \le 2 n c\, t_{\max }\),

\[ \mu \! \left(\left\{ \omega \; \middle |\; s \lt \left|\sum _{i} Y_i(\omega )^2 - n\sigma ^2\right|\right\} \right) \; \le \; 2\exp \! \left(-\frac{s^2}{4 n c}\right). \]