High-Dimensional Probability

Welcome to my course in high dimensional probability. I am Roman Vershynin, professor of mathematics at the University of California, Irvine, and the author of the textbook "High dimensional probability. An introduction with applications in Data Science."

This course builds probabilistic foundations for theoretical research in modern data science. You will learn some methods that form an essential toolbox for anyone looking to do mathematical work in machine learning, theoretical computer science, theoretical statistics, signal processing, etc.

The course is suitable for students in mathematics, statistics, computer science, and electrical engineering. A solid background in undergraduate linear algebra, real analysis, and probability theory are minimum prerequisites. Some familiarity with metric, Hilbert and normed spaces is a plus, but is not required. Knowledge of measure theory is not required.

The course consists of 41 video lectures and 13 homework sets. It was taught remotely at Kyiv National University in Fall of 2022 and 2023, during the Russian invasion of Ukraine. The unparalleled determination of Ukrainian students to study mathematics despite the hardships of the war was a tremendous source of inspiration for me.

Some parts of this course are loosely based on my book, the draft of which you can download for free.

• Lecture 1 Notes Video

  The curse of dimensionality. Probability can help: the Monte-Carlo method.

• Lecture 2 Notes Video

  Convexity. Caratheodory theorem. Approximate Caratheodory theorem. Proof by a probabilistic method, the empirical method of Maurey.

• Lecture 3 Notes Video

  Applications of Approximate Caratheodory Theorem for financial portfolios and factor analysis. Covering numbers are usually exponential in the dimension. Polytopes with few vertices have small covering numbers.

• Lecture 4 Notes Video Homework 1

  Volumes of polytopes (Carl-Pajor's theorem). Milman's hyperbolic intuition in high dimensions. Concentration inequalities: from 68-95-99.7 rule to general gaussian tails.

• Lecture 5 Notes Video

  Toward concentration of sums of independent random variables: Markov's and Chebyshev's inequalities. The error in the central limit theorem is too large (Berry-Esseen theorem). Hoeffding's inequality stated.

• Lecture 6 Notes Video

  Hoeffding's inequality proved. Estimation of the mean: the median-of-means estimator.

• Lecture 7 Notes Video Homework 2

  Variants of Hoeffding's inequality: two-sided and for bounded distributions. Poisson limit theorem. Chernoff's inequality.

• Lecture 8 Notes Video

  Small and large deviations: Gaussian and Poisson regimes. Random graphs as models of networks. Erdos-Renyi model. Phase transitions. Regularity of dense random graphs.

• Lecture 9 Notes Video

  Irregularity of sparse random graphs. Instance vs. uniform guarantees of probabilistic results. Geometric discrepancy. Lecture notes. Video recording

• Lecture 10 Notes Video Homework 3

  Proof of the discrepancy theorem.

• Lecture 11 Notes Video

  Spaces of random variables. Normed and Hilbert spaces. Lp spaces. Cauchy-Schwarz, Holder's and Jensen's inequalities.

• Lecture 12 Notes Video

  Orlicz spaces. Subgaussian properties.

• Lecture 13 Notes Video Homework 4

  Equivalence of subgaussian properties. Subgaussian distributions and subgaussian norm.

• Lecture 14 Notes Video

  Subgaussian Hoeffding's inequality. Subexponential distributions. Bernstein's inequality.

• Lecture 15 Notes Video

  The thin shell phenomenon. Dimension reduction with Johnson-Lindenstrauss lemma.

• Lecture 16 Notes Video Homework 5

  Combinatorial optimization. Examples: Ising model, clustering, max-cut. Spectral relaxations. Semidefinite relaxations.

• Lecture 17 Notes Video

  Gram matrices. Semidefinite relaxation of max cut: Goemans-Williamson's agorithm.

• Lecture 18 Notes Video

  Grothendieck's inequality. Tensor calculus. Krivine's bound.

• Lecture 19 Notes Video Homework 6

  A first exposure to machine learning: binary classification. Support vector machine. The kernel trick: kernelizing machine learning algorithms. Radial basis function kernel.

• Lecture 20 Notes Video

  The soft-margin SVM and kernel SVM. What functions are kernels? Mercer's condition. Artificial neural networks. Large width limits. Kernels arising from neural networks. Neural tangent kernel.

• Lecture 21 Notes Video

  A refresher in linear algebra: spectral and singular value decompositions; Frobenius norm.

• Lecture 22 Notes Video Homework 7

  The operator norm. Random vectors in high dimensions. Covariance matrix. Normal distribution in high dimensions. Principal component analysis.

• Lecture 23 Notes Video

  The covariance estimation problem. Sample covariance matrix. Reduction to stochastic processes. Brownian motion. Epsilon-nets. Computing the operator norm on an epsilon-net.

• Lecture 24 Notes Video

  Covariance estimation for normal distributions. Spectrum perturbation theory: Weyl's and Davis-Kahan's inequalities. Implications for PCA.

• Lecture 25 Notes Video Homework 8

  Random matrices. Proof of Wigner's semicircle law using the Stieltjes transform approach. The proof we gave in class follows the argument in this paper (p.50).

• Lecture 26 Notes Video

  Proof of Marchenko-Pastur law.

• Lecture 27 Notes Video Homework 9

  Review of fundamental laws of random matrix theory: Semicircle law, Marchenko-Pastur law, circular law, Bai-Yin law, Tracy-Widom law. Spike models. Joint eigenvalue distribution; eigenvalue repulsion. Universality. Connections to physics (Wigner surmise) and number theory (Montgomery's pair correlation conjecture).

• Lecture 28 Notes Video

  Functional calculus. Loewner order. Matrix monotonicity of functions 1/x and log(x).

• Lecture 29 Notes Video

  Lieb's trace inequality. Matrix Hoeffding inequality.

• Lecture 30 Notes Video Homework 10

  Matrix Bernstein inequality. Applications to networks (started): community detection in stochastic block models.

• Lecture 31 Notes Video

  Applications to networks continued. A spectral algorithm for community recovery: guarantees for the stochastic block model.

• Lecture 32 Notes Video

  Recent developments on community detection for the stochastic block model. Modern visualization techniques: MDS, Isomap, t-SNE, UMAP (play with it). What do numbers look like?

• Lecture 33 Notes Video Homework 11

  Low-dimensional paradigm. The effective rank and effective dimension. Covariance estimation for low-dimensional data.

• Lecture 34 Notes Video

  Mathematical foundations of machine learning. Supervised learning. Loss functions. Overfitting problem. Hypothesis space. Risk; empirical risk; empirical risk minimization. Generalization error.

• Lecture 35 Notes Video Homework 12

  A generalization bound. VC dimension. The VC dimension of half-lines, intervals, half-planes, circles, rectangles, linear classifiers, polynomial classifiers, and neural networks.

• Lecture 36 Notes Video

  VC theory: Pajor's lemma; Sauer-Shelah lemma.

• Lecture 37 Notes Video

  Applications of Sauer-Shelah lemma for counting regions in hyperplane arrangements. Empirical processes. The uniform law of large numbers (stated).

• Lecture 38 Notes Video Homework 13

  Proof of the uniform law of large numbers: Symmetrization; Rademacher complexity. Applications: Glivenko-Cantelli theorem; VC generalization bound.

• Lecture 39 Notes Video

  Gaussian and subgaussian stochastic processes. Dudley's intergral inequality.

• Lecture 40 Notes Video

  Application of Dudley's inequality: the uniform law of large numbers for Lipschitz functions. Lipschitz regression.

• Lecture 41 Notes Video

  Isoperimetric inequalities. Concentration of measure for Lipschitz functions via Gaussian isomepimetric inequality.