High Dimensional Geometry and Concentration I
summary
High-dimensional sets have most of their volume near boundary (shrinking by 1−ε multiplies volume by (1−ε)^n) and Euclidean balls put half their mass inside a band of width about O(1/√n) (cap tails ≈ exp(−n t^2/2)). The lecture proves Brunn–Minkowski (vol(λA+(1−λ)B)^{1/n} ≥ λ vol(A)^{1/n}+(1−λ)vol(B)^{1/n}) via box-union induction and uses it to get concavity of section radii and Grünbaum’s bound (worst cut ≈ (N/(N+1))^N → 1/e). It then states Prékopa–Leindler, giving that marginals and convolutions of log‑concave functions remain log‑concave.
AI-written summary · about
chapters (9)
- 0:00Introduction to high dimensions
- 1:38Structure and tractability
- 5:07Volume near the boundary
- 8:11Concentration of measure
- 14:47Brunn-Minkowski theorem
- 21:41Proof of Brunn-Minkowski
- 33:37Applications of Brunn-Minkowski
- 40:20Grünbaum's theorem
- 50:58Log-concave functions
related talks
01h 34mAlgorithmic High-Dimensional Geometry I
01h 04mHigher-dimensional Expansion of Random Geometric Complexes
01h 11m(Hidden) Symmetries of Computational Problems (continued)
01h 34mAlgorithmic High-Dimensional Geometry II
49mInfluences in Gaussian Space
11mGeometric Methods for Machine Learning and Optimization
01h 12mRecent Progress in High-Dimensional Learning
44mConcentration Inequalites in Learning with Kernels