Graduate course in High-Dimensional Probability
Georgia Institute of Technology, Spring 2024
Contact: glivshyts6@math.gatech.edu or stop by Skiles 108C.
Location and time: Mondays/Wednesdays 9:30-10:45am at Skiles 006
January 8 through April 22.
As a back up (for someone who gets sick, for example), the lectures will be broadcast via Zoom, but students are generally expected to attend in person.
Office hours: Friday at 9-11am online via Zoom or in-person by appointment.
Description: In this course, we shall learn about High-Dimensional Probability, a rich and interesting area of Mathematics with connections to many subjects such as Statistics, Computer Science, Engeneering and Analysis. We will discuss how concentration phenomenon stems from independence as well as from convexity, and study various useful methods to harness high-dimensional phenomena. More specifically, the topics with links to resources are listed here (to be modified slightly throughout the semester):
Grading: The course grade was based on a) scribing at least 1 lecture (preferably 2) and b) completion of 7 points out of the before the end of the semester (this file shall be updated throughout the semester, and more and more problems will be added. Each problem is weighed with several points.) Those interested are encouraged to complete more problems. Turn home work in anytime during the semester, any number of times, in pdf via Canvas.
For more details, see the course syllabus. In addition, we were running a competetion for the highest number of home work points earned throughout the course.
The course has finished.
A list of a few relevant books (some of which are mentioned on the schedule already):
1. Vershynin, High-Dimensional Probability, 2018.
2. Bakry, Ledoux, Gentil, Analysis and Geometry of Markov Diffusion Operators, 2014.
3. Figalli, Glaudo, An Invitation to Optimal Transport, Wasserstein Distances, and Gradient Flows.
4. Klartag, Lecture notes in Convex Localization and Optimal Transport.
5. Van Handel, Lecture notes in High-dimensional Probability.
6. Artstein-Avidan, Giannopoulos, Milman, Asymptotic Geometric Analysis part 2, 2022.
7. Artstein-Avidan, Giannopoulos, Milman, Asymptotic Geometric Analysis part 1, 2015.
8. Bobkov, Chistyakov, Gotze, Concentration and Gaussian Approximation for randomized sums, 2023.
9. Bogachev, Gaussian measures, 1998.
10. Milman, Schechtman, Asymptotic Theory of Finite-Dimensional Normed Spaces, 1986.
11. Pisier, The Volume of Convex Bodies and Banach Space Geometry, 1989.
12. Brazitikos, Giannopoulos, Valettas, Vritsiou, Geometry of Isotropic Convex Bodies, 2014.
13. Ledoux, The Concentration of Measure Phenomenon, 2001.
14. Villani, Topics in Optimal Transportation, 2003.
(a very rough file, to be significantly proofread, corrected and updated)
Class whiteboard:
Lectures 1-3: Introduction, preliminaries, notation, probabilistic method, random rounding, a cool fact about the cube, Caratheodory theorem, Randomized Caratheodory theorem and its proof, covering of polytopes, standard epsilon-net argument, lattice covering, comparison between the two nets, an efficient net for matix multiplication via the Hilbert-Schmidt norm; how to approximate a one-dimensional projection on the sphere and not lose anything.
Lectures 4-6: 1) High-dimensions are weird (the funny picture with the ball and the cube); high dimensions are well ordered and predictable (central limit theorem, its geometric interpretation, a mention of the CLT for convex sets); high dimensions are well ordered and predictable II (the uniform random vector on the unit ball has length about 1 with high probability)
2) Preliminaries from probability: Markov’s inequality, convex functions, Jensen’s inequality, Minkowski inequality, Cauchy inequality, Holder’s inequality.
3) Concept of a concentration inequality, Chebychev’s inequality; Quantitative Law of large numbers — good concentration for sums of independent random variables; Hoeffding’s inequality for symmetric Bernoullis and its geometric meaning, and its proof, two-sided version, Chernoff’s inequality, small deviations version, an application to random G(n,p) graphs: any vertex degree is likely close to the average; sub-Gaussian random variables (equivalent definitions) and the proof of the equivalence of the 5 sub-Gaussian properties; sub-Gaussian norm; examples of Sub-Gaussian and non-sub-Gaussian random variables; sub-additivity of the square of the sub-Gaussian norm and the general Hoeffding inequality; Khinchine’s inequality.
Lectures 7-8: Centering trick, sub-exponential random variables and their five equivalent definitions, the psi-1 norm, sub-exponential is equivalent to a squared sub-Gaussian, product of sub-Gaussians is sub-exponential, Bernstein’s inequality and its consequences; Concentration of the Euclidean norm of a random vector with independent sub-Gaussian coordinates, sub-Gaussian random vectors and their examples, random vectors with sub-Gaussian coordinates (independent or not), uniform distribution on the sphere is sub-Gaussian, Grothendick’s inequality.
Lectures 9-10: Correction to the proof of Grothendick’s inequality in which I made an error last time; Random Matrices — a general discussion; norm of an i.i.d. Mean zero sub-Gaussian random matrix; two-sided bounds on all the singular values of tall matrices with independent mean zero isotropic sub-Gaussian rows; Matrix Bernstein inequality.
Lectures 11-13: Estimating from below the smallest singular value — a general discussion; review of the net based on random rounding; small ball (anticoncentration) assumption and the tensorization lemma for it; the smallest singular value of the tall random matrix with independent uniformly anticoncentrated rows and a bounded average second moment of an entry; upgrading the smallest singular estimate to an estimate with high probability rather than an estimate on average: one needs to make the net work with high probability. The net theorem which works with high probability for random matrices with independent columns; a discussion about the difficulties in applying a net argument to a square case; the Rudelson-Vershynin sphere decomposition; the Rudelson-Vershynin theorem about the smallest singular value of square random matrices (statement and comments).
Lectures 14-15: Continuing survey of results concerning the smallest singular value of square random matrices: results of Rebrova-Tikhomirov; Livshyts; Livshyts, Tikhomirov, Vershynin. A brief discussion about the arbitrary aspect ratio case. Part of the proof of the small ball probability estimate for the smallest singular value of square matrices with a polynomial error: the case of compressible vectors; the study of the incompressible vectors — ``the incompressible vectors are spread’’ and ``invertibility via distance’’; Small ball probability for the distance from an incompressible vector to a hyperplane spanned by independent vectors whose coordinates are UAC independent with a polynomial bound, via Rogozin’s theorem; random normal is incompressible; conclusion of the proof of the lower bound on the smallest singular value of a square random matrix under appropriate assumptions. Random processes, Gaussian random vectors, covariance matrices and functions, Gaussian random processes, a GRP is determined by the covariance function; Slepian’s inequality (statement).
Lectures 16-17: Proof of Slepian’s inequality; the Sudakov-Fernique inequality; Applying Sudakov-Fernique inequality to study the expected value of the norm of the standard Gaussian random matrix (with a sharp constant); a few words about Dudley’s inequality and sub-Gaussian random processes; the semigroup method — introduction: review of conditional probability, conditional expectation, Markov processes, stationary measure.
Lectures 18-21:Continuing the semigroup method: basic properties of the semigroup, variance decreases along the semigroup, the generator of the semigroup and the alternative definition of a semigroup; examples: the finite state space, the heat semigroup and the heat semigroup on the circle; the Ornstein-Uhlenbeck semigroup; Green’s formula and the Gaussian integration by parts; reversibility, ergodicity, Dirichlet form of a Markov semigroup; an abstract equivalence of the Poincare inequality and hypercontractivity and other properties of a generic semigroup -- statement; the Ornstein-Uhlenbeck semigroup -- two equivalent definitions, properties, hypercontractivity, the Gaussian Poincare inequality via the smeigroup method, a discussion on the equality cases; Poincare inequalities — general discussion, relation to the first eigenvalue of a linear second order operator, Poincare inequality on the circle for periodic functions via Harmonic Analysis; proof of the “generalized Poincare inequality” for a stationary measure of an ergodic reversible Markov semigroup; a discussion about Phi-Sobolev inequalities; the Gross Log-Sobolev inequality via the semi-group method, and a discussion about it; Beckner inequalities; a remark about the -2-Beckner inequality on the circle; the isoperimetric inequality and the Gaussian isoperimetric inequality; the Gaussian isoperiemtric profile.
Lectures 22-23:Bobkov’s inequality, from Bobkov to Gaussian Isoperimetric inequality, Ledoux’s proof of Bobkov’s inequality via the semigroup method; from Gaussian Isoperimetry to sharp Gaussian concentration; Concentration on the sphere via the Gaussian concentration; concentration for Lipschitz functions; Johnson-Lindenstrauss Lemma; the Milman-Dvoretzky theorem (statement).
Lectures 24-26:Milman-Dvoretzki theorem proof sketch; mass transport — basic definitions and examples; A Lipshitz map from Gaussian to the uniform measure on the cube; useful consequences of having a Lipschitz map between measures; useful facts about the uniform measure on the cube, including the isoperimetry estimate; Vaaler’s theorem about the central sections of the cube; optimal transport with respect to quadratic cost; Brenier’s theorem and discussion around it, with examples; concept of sub-gradient; proof of the easy direction of the discrete version of Brenier; Coupling, Monge problem vs Kantorovich problem, optimal coupling and existence, cyclic monotonicity, Rockafellar’s theorem, Legendre transform, Kantorovich duality; the equivalence of the optimality of a coupling, cyclic monotonicity of its support and its support being a subset of a sub-differential of a convex map.
Lectures 27-28:Proof of Brenier’s theorem, Brunn-Minkowski inequality and its equivalent formulations, Proof of the isoperimetric inequality via Brunn-Minkowski, Mass transport proof of Brunn-Minkowski (Ball-style), Borell’s theorem and Prekopa-Leindler inequality (statement, discussion), Caffarelli theorem and applications, proof via maximum principle; Talagrand’s transport inequality via Brenier.
In the Fall 2023 I taught a related Topics course about Concentration of measure phenomena.