High-Dim Geometry & Concentration

Concentration of measure quantifies how fast random quantities cluster around their mean, while high-dimensional geometry reveals counter-intuitive facts about $\mathbb{R}^d$. Three core inequalities: Markov (non-negative $X$, $a>0$): $P(X \ge a) \le \frac{\mathbb{E}[X]}{a}$;Chebyshev ($k>0$): $P(|X-\mu| \ge k\sigma) \le \frac{1}{k^2}$;Hoeffding (independent $X_i \in [0,1]$): $P(\bar{X}_n - \mu \ge t) \le e^{-2nt^2}$, decaying exponentially in $n$. Thin shell intuition: the $d$-ball volume scales as $r^d$, and a ball of radius $1-\frac{1}{d}$ holds only about $(1-\frac{1}{d})^d \approx e^{-1} \approx 37\%$ of the volume — roughly 63% lies in a shell of thickness $O(1/d)$; random unit vectors $u,v \in \mathbb{R}^d$ have dot-product variance about $1/d$, i.e. magnitude $O(1/\sqrt{d})$ — high-dimensional vectors are nearly pairwise orthogonal, which is exactly why attention divides by $\sqrt{d_k}$.

proving generalization bounds (ERM uniform convergence, PAC), random projections (Johnson-Lindenstrauss), high-dimensional initialization and gradient variance analysis, differential privacy mechanisms; interview questions like "prove Hoeffding" and "what happens in high dimensions" come from here.

Chebyshev only needs the second moment but is loose ($1/k^2$) and cannot answer how fast convergence in $n$ happens; exponential bounds such as Hoeffding give a provable $e^{-2nt^2}$ decay under independence and boundedness, turning "convergence in probability" into an actionable rate. Markov has the weakest assumptions (non-negativity plus a first moment) and is the source of Chebyshev and all sharper concentration inequalities.

Test Your Knowledge: Practice Questions for "High-Dim Geometry & Concentration"

Single choice pitfall questions with instant feedback and mistake tracking.