Gaussian Concentration

SECTION 01Lipschitz Functions of Gaussian Variables

For bounded independent inputs, McDiarmid’s inequality controls fluctuations through the sum of squared coordinate-wise changes. Gaussian inputs allow a different result: concentration controlled by a single Euclidean Lipschitz constant, without an additional dimension factor.

Definition · Euclidean Lipschitz Continuity

A function f: ℝⁿ → ℝ is L-Lipschitz with respect to the Euclidean norm if

| f (x) - f (y) | \leq L {‖ x - y ‖}_{2}, for all x, y ∈ ℝⁿ.

Theorem · Gaussian Concentration

Let X₁, …, Xₙ be independent N(0, 1) variables, and let f be L-Lipschitz with respect to the Euclidean norm. Then f(X) − E[f(X)] is sub-Gaussian with parameter at most L. Consequently,

P (| f (X) - E [f (X)] | \geq t) \leq 2 e^{- \frac{t^{2}}{2 L^{2}}}, t \geq 0

For a fixed L, this bound has no explicit dependence on n. The constant L itself may still depend on n.

An Alternative Route to a Chi-Squared Tail Bound

Let Z₁, …, Zₙ be independent N(0, 1) variables and Y = ∑ₖ₌₁ⁿ Zₖ², so Y ∼ χ²ₙ. We previously controlled Y using sub-exponential concentration. Here we instead apply Gaussian concentration to its square root:

V = \frac{\sqrt{Y}}{\sqrt{n}} = \frac{{‖ (Z_{1}, \dots, Z_{n}) ‖}_{2}}{\sqrt{n}}

The Euclidean norm is 1-Lipschitz, so V is 1/√n-Lipschitz. The one-sided Gaussian bound gives

P (V \geq E [V] + δ) \leq e^{- \frac{n δ^{2}}{2}}

By concavity of the square root and Jensen’s inequality,

E [V] \leq \sqrt{E [V^{2}]} = \sqrt{\frac{1}{n} \sum_{k = 1}^{n} E [{Z_{k}}^{2}]} = 1

Combining these facts yields

P (\frac{Y}{n} \geq {(1 + δ)}^{2}) \leq e^{- \frac{n δ^{2}}{2}}, δ \geq 0

For δ ∈ [0, 1], (1 + δ)² ≤ 1 + 3δ. Setting t = 3δ gives

P (Y \geq n (1 + t)) \leq e^{- \frac{n t^{2}}{18}}, 0 \leq t \leq 3

A Supremum of Gaussian Linear Forms

Let W₁, …, Wₙ be independent N(0, 1) variables. Given a nonempty bounded set A ⊂ ℝⁿ, define

Z = sup_{a \in A} \sum_{k = 1}^{n} a_{k} W_{k} = sup_{a \in A} ⟨ a, W ⟩

As with Rademacher complexity, E[Z] measures the size of A through its alignment with random directions. Here, the random directions are Gaussian.

View Z as f(W), where f(w) = sup_a∈A⟨a, w⟩, and write

D (A) = sup_{a \in A} {‖ a ‖}_{2}

To check Lipschitz continuity, choose a* attaining the supremum at w. Since f(w′) ≥ ⟨a*, w′⟩,

f (w) - f (w^{'}) \leq ⟨ a^{*}, w - w^{'} ⟩ \leq {‖ a^{*} ‖}_{2} {‖ w - w^{'} ‖}_{2} \leq D (A) {‖ w - w^{'} ‖}_{2}

The second inequality is Cauchy–Schwarz. Exchanging w and w′ gives

| f (w) - f (w^{'}) | \leq D (A) {‖ w - w^{'} ‖}_{2}

Thus f is D(A)-Lipschitz, and Gaussian concentration gives

P (| Z - E [Z] | \geq δ) \leq 2 e^{- \frac{δ^{2}}{2 {D (A)}^{2}}}, δ \geq 0

Singular Values of Gaussian Random Matrices

Let X ∈ ℝⁿˣᵈ, with n > d, have independent N(0, 1) entries. Write its singular values in decreasing order:

σ_{1} (X) \geq σ_{2} (X) \geq \dots \geq σ_{d} (X) \geq 0

Weyl’s perturbation inequality gives, for any matrix Y of the same size,

max_{1 \leq k \leq d} | σ_{k} (X) - σ_{k} (Y) | \leq {‖ X - Y ‖}_{2} \leq {‖ X - Y ‖}_{F}

Thus each σₖ(X) is a 1-Lipschitz function of the Gaussian entries. Applying the Gaussian concentration theorem gives, for each k = 1, …, d,

P (| σ_{k} (X) - E [σ_{k} (X)] | \geq δ) \leq 2 e^{- \frac{δ^{2}}{2}}, δ \geq 0

This shows that each singular value concentrates around its own expectation. It does not yet tell us where that expectation lies; Chapter 6 studies this question in more detail.