104 Learning Theory — Bernstein

104.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.

104.2 Declarations

Definition 104.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 104.2 iid closure of the Bernstein MGF condition

✓

Let \(\{ X_i\} _{i \in s}\) be a mutually independent family of measurable real random variables on a probability space, each satisfying \(\texttt{ProbabilityTheory.HasBernsteinMGF}\ (X_i)\ \mu \ c_i\ t_{\max }\) for a common radius \(t_{\max }\). Then the finite sum \(\sum _{i \in s} X_i\) satisfies \(\texttt{ProbabilityTheory.HasBernsteinMGF}\ (\sum _{i\in s} X_i)\ \mu \ (\sum _{i\in s} c_i)\ t_{\max }\).

Lemma 104.3 Upper-tail Bernstein bound

✓

Let \(X\) satisfy \(\texttt{ProbabilityTheory.HasBernsteinMGF}\ X\ \mu \ c\ t_{\max }\) with \(c \gt 0\). For every \(s\) with \(0 \le s \le 2c\, t_{\max }\),

\[ \mu \bigl(\{ \omega \mid s \le X(\omega )\} \bigr) \; \le \; \exp \! \Bigl(-\tfrac {s^2}{4c}\Bigr). \]

The condition \(s \le 2c\, t_{\max }\) ensures that the Chernoff-optimal parameter \(t = s/(2c)\) lies in the validity region \(|t| \le t_{\max }\).

Lemma 104.4 Lower-tail Bernstein bound

✓

Let \(X\) satisfy \(\texttt{ProbabilityTheory.HasBernsteinMGF}\ X\ \mu \ c\ t_{\max }\) with \(c \gt 0\). For every \(s\) with \(0 \le s \le 2c\, t_{\max }\),

\[ \mu \bigl(\{ \omega \mid X(\omega ) \le -s\} \bigr) \; \le \; \exp \! \Bigl(-\tfrac {s^2}{4c}\Bigr). \]

This is the symmetric lower-tail analogue of \(\texttt{ProbabilityTheory.HasBernsteinMGF.measure\_ ge\_ le}\), obtained by applying the upper-tail bound to \(-X\).

Lemma 104.5 Two-sided Bernstein bound

✓

Let \(X\) satisfy \(\texttt{ProbabilityTheory.HasBernsteinMGF}\ X\ \mu \ c\ t_{\max }\) with \(c \gt 0\). For every \(s\) with \(0 \le s \le 2c\, t_{\max }\),

\[ \mu \bigl(\{ \omega \mid s \lt |X(\omega )|\} \bigr) \; \le \; 2\exp \! \Bigl(-\tfrac {s^2}{4c}\Bigr). \]

The bound follows by combining the upper- and lower-tail bounds via a union bound.

Lemma 104.6 Centered squared iid Bernstein tail bound

✓

Let \(\{ Y_i\} _{i \in \iota }\) be a mutually independent, identically distributed family of measurable real random variables on a probability space \((\Omega , \mu )\), where \(|\iota | = n\). Suppose that for each \(i\) the centered square \(Y_i^2 - \sigma ^2\) satisfies \(\texttt{ProbabilityTheory.HasBernsteinMGF}\ (Y_i^2 - \sigma ^2)\ \mu \ c\ t_{\max }\) with \(c \gt 0\). Then for every \(s\) with \(0 \le s \le 2n 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 \! \Bigl(-\tfrac {s^2}{4nc}\Bigr). \]