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
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:
This is the “bad event” whose probability must be controlled by the JL concentration argument.
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
satisfies
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
the centered Gaussian with variance \(c^2 \sigma _0\).
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\).
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 \).
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
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,
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
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\).
For every real number \(s\) with \(\left\lvert s\right\rvert \le 1/4\), one has
Let \(Z\) be a standard Gaussian random variable, \(Z \sim N(0,1)\), and let \(s \in \mathbb {R}\) satisfy \(2s \lt 1\). Then
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\),
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)\).
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
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\).
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\),
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\),
where \(\| A(\omega )\, x\| \) denotes the Euclidean norm of the image \(A(\omega )\, x \in \mathbb {R}^k\).
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 }\),