High-Dimensional Probability
Michaelmas Term 2021
Course description [PDF]
Course calendar
Lecture 1: Geometric and probabilistic formulations of concentration of measure and implications between them (see also [Led2, Chapter 1]). Maurey and Pisier's argument for Gaussian concentration [Pis, Section 2] and concentration on the unit cube via transportation.
Lecture 2: Caffarelli’s contraction theorem and concentration for uniformly log-concave measures. Gromov and Milman's theorem for concentration on uniformly convex bodies and their boundaries via the Brunn-Minkowski inequality [AdRBV]. The spherical and Gaussian isoperimetric inequalities. Examples of applications.
Lecture 3: Tensorization and the bounded differences inequality for the variance following [vH, Section 2.1]. Alternative proof of the Efron-Stein inequality on the discrete hypercube via the Walsh expansion and improvement of the constant for even functions.
Lecture 4: Derivation of the sharp Kahane inequality of Latała and Oleszkiewicz [LO]. Generalities on Markov semigroups. The Ornstein-Uhlenbeck process and semigroup. Equivalence of the Poincaré inequality to exponential ergodicity of the Markov semigroup without proof and derivation of the Gaussian Poincaré inequality (see [vH, Sections 2.2-2.3]).
Lecture 5: Proof of the characterization of Poincaré inequalities in terms of the corresponding semigroup (see [vH, Section 2.4]). Gromov and Milman's theorem on exponential concentration under a Poincaré inequality (see [Led2, Section 3.1]). The theorem of Gozlan, Roberto and Samson [GRS] showing that, conversely, dimension-free concentration implies the existence of a spectral gap.
Lecture 6: Chernoff bounds and subgaussian random variables. Hoeffding's lemma and Azuma's martingale inequality (see [vH, Sections 3.1-3.2]). McDiarmid's inequality and concentration of Lipschitz functions on the discrete hypercube.
Lecture 7: Herbst's argument. Tensorization and the bounded differences inequality for the entropy following [vH, Section 3.3].
Lecture 8: Modified log-Sobolev inequalities for Markov semigroups and characterization in terms of exponential entropic ergodicity. The Gaussian log-Sobolev inequality and Gaussian concentration. The modified log-Sobolev inequality implies the Poincaré inequality (see [vH, Section 3.4]). Bobkov and Götze's characterization of subgaussian concentration without proof.
Lecture 9: Proof of the theorem of Bobkov and Götze. Monge-Kantorovich duality and Marton's tensorization theorem (see [vH, Sections 4.1-4.2]). The transportation proof of McDiarmid's inequality.
Lecture 10: Proof of Marton's tensorization theorem. Gozlan's characterization of dimension-free Euclidean subgaussian concentration for Lipschitz functions and Talagrand's transport-entropy inequality (see [vH, Section 4.4] and [Tal]).
Lecture 11: Proof of Talagrand's transport-entropy inequality. The Marton-Talagrand concentration inequality and concentration of convex Lipschitz functions of bounded random variables (see [vH, Section 4.3]). The Gaussian concentration inequality for convex functions of Paouris and Valettas [PV]. Marton's conditional transportation inequality.
Lecture 12: Proof of Marton's conditional transportation inequality and derivation of the Marton-Talagrand concentration inequality.
Lecture 13: Talagrand's convex distance inequality (see [BLM, Section 8.4]). Gross' characterization of log-Sobolev inequalities in terms of hypercontractivity of the underlying Markov semigroup (see [vH, Section 8.2]).
Lecture 14: Hypercontractivity on the Gauss space and the (biased) discrete hypercube. Khintchine inequalities for homogeneous Walsh polynomials. Talagrand's influence inequality (see [vH, Section 8.3]).
Lecture 15: Influences and the Kahn-Kalai-Linial theorem. Bobkov and Ledoux's proof of Talagrand's two-level concentration inequality for the symmetric exponential measure (see [BoL]).
Lecture 16: Bakry and Ledoux's semigroup proof of the Gaussian isoperimetric inequality (see [BaL, Led1]).
Problems [PDF]
References
[AdRBV] J. Arias-de-Reyna, K. Ball and R. Villa, Concentration of the distance in finite-dimensional normed spaces, Mathematika, 1998.
[BaL] D. Bakry and M. Ledoux, Lévy-Gromov's isoperimetric inequality for an infinite-dimensional diffusion generator, Inventiones Mathematicae, 1996.
[BoL] S. Bobkov and M. Ledoux, Poincaré's inequalities and Talagrand's concentration phenomenon for the exponential distribution, Probability Theory and Related Fields, 1997.
[BLM] S. Boucheron, G. Lugosi and P. Massart, Concentration inequalities: a non-asymptotic theory of independence, Oxford University Press, 2013.
[GRS] N. Gozlan, C. Roberto and P. M. Samson, From dimension free concentration to Poincaré inequality, Calculus of Variations and PDE, 2015.
[LO] R. Latała and K. Oleszkiewicz, On the best constant in the Khinchin-Kahane inequality, Studia Mathematica, 1994.
[Led1] M. Ledoux, A short proof of the Gaussian isoperimetric inequality, Birkhäuser, 1998.
[Led2] M. Ledoux, The concentration of measure phenomenon, American Mathematical Society, 2001.
[PV] G. Paouris and P. Valettas, A Gaussian small deviation inequality for convex functions, Annals of Probability, 2018.
[Pis] G. Pisier, Probabilistic methods in the geometry of Banach spaces, Springer, 1986.
[Tal] M. Talagrand, Transportation cost for Gaussian and other product measures, Geometric and Functional Analysis, 1996.
[vH] R. van Handel, Probability in high dimensions, Available at https://web.math.princeton.edu/~rvan/APC550.pdf.
[Ver] R. Vershynin, High-dimensional probability, Cambridge University Press, 2018, also available at https://www.math.uci.edu/~rvershyn/papers/HDP-book/HDP-book.pdf.