Measure Concentration and Geometric Functional Analysis

Let $X \sim \mathcal{N}(0, I_d)$ and $f: \mathbb{R}^d \to \mathbb{R}$ be $L$-Lipschitz. Then for all $t > 0$:

The function $f(X)$ is sub-Gaussian with parameter $L$.

Each coordinate of $X$ contributes independently to $f(X)$, and the Lipschitz condition limits how much each coordinate can influence the output. The $d$ independent contributions each have bounded effect, and their sum concentrates by the same mechanism as a sum of bounded random variables. The dimension $d$ does not appear in the bound.

This single result has enormous consequences. It implies that the norm $\|X\|$ concentrates around $\sqrt{d}$, inner products $\langle X, Y \rangle$ concentrate around 0, and random projections preserve distances. Most of high-dimensional probability follows from applying this inequality to appropriately chosen Lipschitz functions.

The result requires Gaussianity (or more generally, a distribution satisfying a log-Sobolev inequality). For heavy-tailed distributions, Lipschitz functions do not concentrate at the Gaussian rate. The bound also requires $f$ to be globally Lipschitz; local Lipschitz conditions are not sufficient.

For any set of $n$ points $x_1,\ldots,x_n\in \mathbb{R}^d$ and any $\varepsilon \in (0,1)$, there exists a linear map $A: \mathbb{R}^d \to \mathbb{R}^k$ with

such that for all pairs $i,j$,

The map $A = \frac{1}{\sqrt{k}} \Pi$ where $\Pi$ is a $k \times d$ matrix with i.i.d. $\mathcal{N}(0,1)$ entries works with high probability.

A random projection of a vector $x$ has squared norm that concentrates around $\|x\|^2$. This is because

The sum of $k$ squared Gaussians concentrates around its mean by chi-squared concentration. Taking a union bound over all $\binom{n}{2}$ pairs gives the result.

This lemma says that $n$ points in arbitrarily high dimension can be embedded into $O(\log n/\varepsilon^2)$ dimensions while approximately preserving all pairwise distances. The target dimension depends only on $n$ and $\varepsilon$, not on the original dimension $d$. This is the theoretical foundation for random projection methods in dimensionality reduction, approximate nearest neighbor search, and compressed sensing.

The $O(\log n/\varepsilon^2)$ target dimension is tight: there exist point sets requiring $\Omega(\log n/\varepsilon^2)$ dimensions for any linear map. For $\varepsilon$ very small, the target dimension can still be large. The lemma also only preserves Euclidean distances; other metrics require different techniques.

Let $X$ be uniformly distributed on $S^{d-1}$ and $f: S^{d-1} \to \mathbb{R}$ be $L$-Lipschitz. Let $M_f$ be the median of $f(X)$. Then:

The concentration improves with dimension: higher dimension means tighter concentration.

On a high-dimensional sphere, most of the surface area is concentrated near any equator. A Lipschitz function cannot vary much on this concentrated strip. The effective number of "independent directions" on the sphere is $d-1$, which is why the exponent contains $d-1$.

Levy's lemma makes precise the idea that high-dimensional spheres are "effectively one-dimensional" from the perspective of Lipschitz functions. Any continuous measurement on a high-dimensional sphere will give nearly the same value for almost every point. This is a key ingredient in proofs of the Johnson-Lindenstrauss lemma via spherical projections.

The bound degrades for non-Lipschitz functions. For discontinuous functions or functions with large Lipschitz constant relative to the sphere's radius, the concentration is useless. The bound is also trivial in low ambient dimension: under the convention $X \sim \operatorname{Unif}(S^{d-1})$, the case $d=1$ gives $S^0=\{-1,+1\}$, two points rather than a circle. The circle is $S^1$, corresponding to $d=2$. For $d=2$, the exponent is only

so the bound gives the usual one-dimensional Gaussian tail rate, with no dimensional improvement. The $\exp(-(d-1)t^2/2)$ concentration becomes useful once $d$ is large.