High-Dimensional Probability
Sub-Gaussian and sub-exponential tails, concentration inequalities, nets, and the geometry of random vectors in large dimension.
Level 2 — Advanced
- Sub-Gaussian and Sub-Exponential Random Variables15 min
Orlicz norms, moment generating functions and the equivalent characterisations that make "has a Gaussian-like tail" a usable hypothesis.
Equivalent characterisations of sub-GaussianityThe psi-2 and psi-1 Orlicz normsMoment generating function of a centred Gaussian - Concentration Inequalities27 min
Markov to McDiarmid, each with its hypotheses, a complete proof, an interpretation and the regime in which it is the right tool.
Markov's inequalityChebyshev's inequalityThe Chernoff method - High-Dimensional Geometry and Concentration of the Norm13 min
Why a Gaussian vector lives on a thin shell, why random directions are nearly orthogonal, and why almost all of a sphere's volume sits near any equator.
Concentration of the norm of a sub-Gaussian vectorThe expected norm of a Gaussian vectorRandom directions are nearly orthogonal
Level 3 — Graduate
- Nets, Covering Numbers and Metric Entropy11 min
How to reduce a supremum over an infinite set to a maximum over a finite one, and what that reduction costs.
Nets, covering and packing numbersPacking and covering numbers are equivalentVolumetric bound on covering numbers - The Johnson–Lindenstrauss Lemma13 min
A complete proof that random projection to O(log N / eps^2) dimensions preserves all pairwise distances, with the dimension requirement, the geometry and the limits of the result.
Distributional Johnson–Lindenstrauss lemmaJohnson–Lindenstrauss lemmaOptimality of the dimension bound
Problems (28)
Open in the browser| Solved | Problem | Type | Difficulty | Time |
|---|---|---|---|---|
| Markov and Chebyshev are attained | Proof | 15 min | ||
| Johnson–Lindenstrauss dimension arithmetic | Numerical | 15 min | ||
| The psi-2 norm of a Rademacher sign | Numerical | 15 min | ||
| Volume concentrates near the boundary | Numerical | 15 min | ||
| A variable with all moments finite that is not sub-Gaussian | Proof | 30 min | ||
| Azuma for a random walk with drift | Proof | 30 min | ||
| Derive Hoeffding's inequality from Hoeffding's lemma | Proof | 30 min | ||
| From distance preservation to inner-product preservation | Proof | 30 min | ||
| Implement random projection and measure the distortion run | Coding | 1 hour | ||
| Locating the Bernstein crossover | Numerical | 30 min | ||
| Simulate and compare the concentration inequalities run | Coding | 1 hour | ||
| Simulate the measure of a spherical cap run | Coding | 30 min |