TCSLib

102 Learning Theory — Concentration Bound

102.1 Overview

This module proves the single-vector concentration bound for the Johnson–Lindenstrauss random projection. A random matrix \(A\) with i.i.d. \(N(0,1/k)\) entries is shown to preserve the squared norm of any fixed vector \(x\) up to a multiplicative \((1\pm \varepsilon )\) factor, with failure probability at most \(2\exp (-k\varepsilon ^2/8)\). The proof reduces to a centered chi-squared moment-generating-function (MGF) bound obtained via a classical Taylor inequality, then packages the result into the abstract Bernstein-MGF framework so that the same tail machinery applies to other sub-Gaussian random matrix families.

102.2 Declarations

Definition 102.1 Bad distortion event for a single vector
✓
#

For a parameter \(\varepsilon \in \mathbb {R}\), a matrix \(A\), and a vector \(x\in \mathbb {R}^d\), the predicate \(\texttt{BadSingle}\, \varepsilon \, A\, x\) holds when the squared-norm distortion is strictly too large:

\[ \varepsilon \| x\| ^2 \lt \bigl|\, \| Ax\| ^2 - \| x\| ^2\, \bigr|. \]

This is the “bad event” whose probability must be controlled by the JL concentration argument.

Lemma 102.2 Concentration bound at the zero vector
✓
#

Let \(\mu \) be a probability measure on a measurable space \(\Omega \), let \(\omega \mapsto A(\omega )\) be a family of \(k \times d\) real matrices indexed by \(\Omega \), and let \(\varepsilon \in \mathbb {R}\). Then the probability that the zero vector \(0 \in \mathbb {R}^d\) triggers the bad distortion event, namely that

\[ \varepsilon \, \| 0\| ^2 \lt \bigl|\, \| A(\omega )\, 0\| ^2 - \| 0\| ^2\, \bigr|, \]

satisfies

\[ \mu \bigl\{ \omega : \varepsilon \, \| 0\| ^2 \lt \bigl|\, \| A(\omega )\, 0\| ^2 - \| 0\| ^2\, \bigr|\bigr\} \; \le \; 2\exp \! \Bigl(-\tfrac {k\, \varepsilon ^2}{8}\Bigr). \]
Lemma 102.3 Scaling a centered real Gaussian
✓
#

Let \(X\colon \Omega \to \mathbb {R}\) be a measurable random variable on a measure space \((\Omega , \mu )\) whose law is the centered Gaussian \(N(0, \sigma _0)\) with variance \(\sigma _0 \ge 0\). Then for every scalar \(c \in \mathbb {R}\), the scaled variable \(c\, X\) has law

\[ N\! \bigl(0,\; c^2 \sigma _0\bigr), \]

the centered Gaussian with variance \(c^2 \sigma _0\).

Lemma 102.4 Weighted sum of independent Gaussians is Gaussian
✓
#

Let \((\Omega ,\mu )\) be a probability space, and let \((Y_j)_{j}\) be a family of independent, measurable real-valued random variables, each distributed as a centred Gaussian with mean \(0\) and variance \(\sigma _0 \ge 0\). Then for any real coefficients \((x_j)_j\) and any finite index set \(s\), the random variable \(\sum _{j \in s} x_j\, Y_j\) has distribution \(N\! \Bigl(0,\; \bigl(\sum _{j \in s} x_j^2\bigr)\, \sigma _0\Bigr)\); that is, its law is the centred Gaussian on \(\mathbb {R}\) with variance \(\sigma _0 \sum _{j \in s} x_j^2\).

Lemma 102.5 Independence of coordinates of a random matrix–vector product
✓
#

Let \((\Omega ,\mu )\) be a probability space, and let \(A\) be a random \(k\times d\) real matrix, that is, a measurable map assigning to each \(\omega \in \Omega \) a matrix \(A(\omega )\in \mathbb {R}^{k\times d}\). Suppose the rows of \(A\) are mutually independent, meaning the \(k\) random vectors \(\omega \mapsto \bigl(A(\omega )_{i,1},\dots ,A(\omega )_{i,d}\bigr)\in \mathbb {R}^{d}\), for \(i=1,\dots ,k\), are mutually independent under \(\mu \). Then for every fixed \(x\in \mathbb {R}^{d}\) the \(k\) coordinates of the product \(A(\omega )\, x\), namely the real-valued random variables \(\omega \mapsto (A(\omega )\, x)_i=\sum _{j=1}^{d}A(\omega )_{i,j}\, x_j\) for \(i=1,\dots ,k\), are mutually independent under \(\mu \).

Lemma 102.6 Coordinates of a matrix-vector product
✓
#

Let \(A\in \mathbb {R}^{k\times d}\) be a \(k\times d\) real matrix, regarded as the linear map from the Euclidean space \(\mathbb {R}^{d}\) to \(\mathbb {R}^{k}\) that it induces, and let \(x\in \mathbb {R}^{d}\). Then for each index \(i\in \{ 1,\dots ,k\} \), the \(i\)-th coordinate of the image \(Ax\) is given by

\[ (Ax)_i \; =\; \sum _{j} A_{ij}\, x_j . \]
Lemma 102.7 Squared Euclidean norm as a sum of squared coordinates
✓
#

Let \(A\) be a \(k \times d\) real matrix, regarded as the linear map \(x \mapsto Ax\) from the Euclidean space \(\mathbb {R}^d\) to \(\mathbb {R}^k\), and let \(x \in \mathbb {R}^d\). Then the squared Euclidean norm of the image is the sum of the squares of its coordinates,

\[ \lVert Ax\rVert ^2 = \sum _{i=1}^{k} (Ax)_i^2 . \]
Lemma 102.8 Derivative of a Taylor auxiliary function
✓
#

Let \(h \colon \mathbb {R}\to \mathbb {R}\) be the function \(h(x) = x^2 + x + \log (1 - x)\). Then at every point \(u \lt 1\), the function \(h\) is differentiable with derivative

\[ h'(u) = \frac{u(1 - 2u)}{1 - u}. \]
Lemma 102.9 An auxiliary expression vanishes at zero
✓
#

The real-valued expression \(x^2 + x + \log (1 - x)\) takes the value \(0\) at \(x = 0\); that is, \(0^2 + 0 + \log (1 - 0) = 0\).

Lemma 102.10 Taylor bound for the centered chi-squared log-MGF
✓

For every real number \(s\) with \(\left\lvert s\right\rvert \le 1/4\), one has

\[ -s - \tfrac {1}{2}\log (1 - 2s) \; \le \; 2s^2 . \]
Lemma 102.11 Quadratic Gaussian integral
✓
#

Let \(Z\) be a standard Gaussian random variable, \(Z \sim N(0,1)\), and let \(s \in \mathbb {R}\) satisfy \(2s \lt 1\). Then

\[ \mathbb {E}\! \left[e^{s Z^2}\right] = \int _{\mathbb {R}} e^{s z^2}\, \mathrm{d}N(0,1)(z) = \frac{1}{\sqrt{1 - 2s}}. \]
Lemma 102.12 Quadratic exponential integral against a centered Gaussian
✓
#

Let \(v \gt 0\) and write \(N(0,v)\) for the centered Gaussian distribution on \(\mathbb {R}\) with mean \(0\) and variance \(v\). Then for every real number \(t\) with \(2tv \lt 1\),

\[ \int _{\mathbb {R}} e^{t y^2}\, \mathrm{d}N(0,v)(y) = \frac{1}{\sqrt{1 - 2tv}}. \]
Lemma 102.13 Integrability of a Gaussian moment generating integrand
✓
#

Let \(v\) be a nonnegative real number with \(v \ne 0\), and let \(N(0,v)\) denote the centred Gaussian probability measure on \(\mathbb {R}\) with variance \(v\). If \(t \in \mathbb {R}\) satisfies \(2tv \lt 1\), then the function \(y \mapsto e^{t y^2}\) is integrable with respect to \(N(0,v)\).

Theorem 102.14 Centered chi-squared MGF bound
✓

Let \((\Omega ,\mu )\) be a probability space and let \(k\) be a positive natural number. Suppose \(Y:\Omega \to \mathbb {R}\) is measurable and normally distributed with mean \(0\) and variance \(1/k\), that is, its law \(Y_*\mu \) equals \(N(0,1/k)\). Then for every real \(t\) with \(\left\lvert t\right\rvert \le k/4\), the function \(\omega \mapsto \exp \! \bigl(t\, (Y(\omega )^2 - 1/k)\bigr)\) is \(\mu \)-integrable, and the moment generating function of the centered variable \(Y^2 - 1/k\) satisfies

\[ \mathbb {E}_\mu \! \left[e^{t(Y^2 - 1/k)}\right] \; \le \; \exp \! \Bigl(\frac{2t^2}{k^2}\Bigr). \]
Theorem 102.15 Bernstein MGF bound for a centered chi-squared summand
✓

Fix an integer \(k \ge 1\), and let \(Y\) be a real-valued random variable on a probability space \((\Omega , \mu )\) whose law is the centered Gaussian \(\mathcal{N}(0, 1/k)\) of mean \(0\) and variance \(1/k\). Then the centered square \(Y^2 - 1/k\) satisfies the Bernstein MGF condition on \((\Omega , \mu )\) with quadratic-growth parameter \(c = 2/k^2\) and radius \(t_{\max } = k/4\).

Lemma 102.16 Chi-squared tail bound for independent \(N(0,1/k)\) variables
✓

Let \(\mu \) be a probability measure on \(\Omega \), let \(k \ge 1\), and let \(Y_1,\dots ,Y_k : \Omega \to \mathbb {R}\) be independent random variables, each with law \(N(0, 1/k)\). Then for every \(\varepsilon \) with \(0 \lt \varepsilon \lt 1\),

\[ \mu \! \left\{ \omega \; \middle |\; \varepsilon \lt \Bigl|\, \textstyle \sum _{i=1}^{k} Y_i(\omega )^2 - 1\Bigr|\right\} \; \le \; 2\exp \! \Bigl(-\tfrac {k\, \varepsilon ^2}{8}\Bigr). \]
Theorem 102.17 Johnson–Lindenstrauss concentration for a single vector
✓

Let \(k \ge 1\), and let \(A\) be a random \(k \times d\) real matrix on a probability space \((\Omega , \mu )\) whose \(kd\) entries \(A_{ij}\) are jointly independent, each Gaussian with law \(N(0, 1/k)\). Then for every fixed vector \(x \in \mathbb {R}^d\) and every \(\varepsilon \) with \(0 \lt \varepsilon \lt 1\),

\[ \mu \bigl\{ \, \omega : \bigl|\, \| A(\omega )\, x\| ^2 - \| x\| ^2\, \bigr| \gt \varepsilon \, \| x\| ^2 \, \bigr\} \; \le \; 2\exp \! \Bigl(-\frac{k\, \varepsilon ^2}{8}\Bigr), \]

where \(\| A(\omega )\, x\| \) denotes the Euclidean norm of the image \(A(\omega )\, x \in \mathbb {R}^k\).

Theorem 102.18 Distribution-free Johnson–Lindenstrauss concentration via Bernstein tails
✓

Fix an integer \(k \ge 1\), a dimension \(d\), a probability space \((\Omega , \mu )\), and a vector \(x \in \mathbb {R}^d\). Let \(A : \Omega \to \mathbb {R}^{k \times d}\) be a random matrix, and for each outcome \(\omega \) write \(y(\omega ) = A(\omega )\, x \in \mathbb {R}^k\) for the image of \(x\) under the random linear map, with coordinates \(y_1(\omega ), \dots , y_k(\omega )\). Suppose each coordinate \(y_i\) is measurable, the coordinates \(y_1, \dots , y_k\) are independent, and, for some constants \(c \gt 0\) and \(t_{\max }\), each centered squared coordinate \(y_i^2 - \lVert x\rVert ^2/k\) satisfies the Bernstein moment generating function condition with parameters \((c, t_{\max })\). Then for every \(s\) with \(0 \le s \le 2kc\, t_{\max }\),

\[ \mu \bigl\{ \omega \; :\; s \lt \bigl|\, \lVert A(\omega )\, x\rVert ^2 - \lVert x\rVert ^2\, \bigr|\bigr\} \; \le \; 2\exp \! \Bigl(-\frac{s^2}{4kc}\Bigr). \]