188 Learning Theory — Union Bound
188.1 Overview
This module assembles the Johnson–Lindenstrauss lemma from single-vector concentration by a union bound over all ordered pairs of a finite point set \(V \subseteq \mathbb {R}^d\). It introduces the \((1\pm \varepsilon )\) pairwise distortion predicate, the notion of an \(\varepsilon \)-JL embedding, and the “bad pair” event, and then extracts an embedding by the probabilistic method whenever the union-bound failure probability is strictly below \(1\).
188.2 Declarations
Let \(\mu \) be a probability measure on \(\Omega \), let \(A : \Omega \to \mathbb {R}^{k\times d}\) be a measurable random matrix, let \(\varepsilon \in \mathbb {R}\), and let \(V\) be a finite subset of \(\mathbb {R}^d\). Suppose that for every ordered pair \(u, v \in V\) the bad event \(\{ \omega \mid \texttt{BadSingle}\, \varepsilon \, (A\, \omega )\, (u-v)\} \) is measurable and has probability at most \(2\exp (-k\varepsilon ^2/8)\), and that the union-bound failure probability satisfies
Then there exists a linear map \(f : \mathbb {R}^d \to \mathbb {R}^k\) which is an \(\varepsilon \)-JL embedding of \(V\), i.e. \((1-\varepsilon )\| u-v\| ^2 \le \| f u - f v\| ^2 \le (1+\varepsilon )\| u-v\| ^2\) for all \(u, v \in V\).