Lectures (Vershynin): Mondays, Wednesdays 18:00-19:15 Kyiv time, by Zoom. The permanent Zoom link has been sent to your email. The link can also be found in the first announcement in Google classroom.

Consultation/Practice (Chernova): TBA, by Google Meet. The link has been sent to your email, and can also be found in the first announcement in Google classroom.

Description: Welcome to the course in high dimensional probability. It builds 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. This course are loosely based on my book, the draft of which you can download for free.

Prerequisites: One semester of probability theory, and a course in linear algebra.

The grade will be determined by the homework. One homework set will be assigned every week. It is due each Sunday by 23:59, submitted to Google classroom. You can write the solutions in English or Ukrainian. Late homework will not be accepted.

• September 4 Lecture 1 Video Homework 1 due September 10 at 23:59

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

• September 6 Lecture 2 Video Homework 2 due September 17 at 23:59

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

• September 11 Lecture 3 Video

  Covering numbers are usually exponential in the dimension. Polytopes with few vertices have small covering numbers and small volume. (Carl-Pajor's theorem). Milman's hyperbolic intuition in high dimensions.

• September 13 Lecture 4 Video Homework 3 due September 24 at 23:59

  Concentration inequalities: from 68-95-99.7 rule to general gaussian tails. Markov's and Chebyshev's inequalities. The error in the central limit theorem is too large (Berry-Esseen theorem).

• September 18 Lecture 5 Video

  Hoeffding's inequality. The median-of-means estimator.

• September 20 Lecture 6 Video Homework 4 due October 1 at 23:59

  Geometric discrepancy. An epsilon-net method.

• September 25 Lecture 7 Video

  Poisson limit theorem. Chernoff's inequality. Small and large deviations: Gaussian and Poisson regimes.

• September 27 Lecture 8 Video Homework 5 due October 8 at 23:59

  Random graphs as models of networks. Erdos-Renyi model. Phase transitions. Regularity of dense random graphs.

• October 2 Lecture 9 Video

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

• October 4 Lecture 10 Video Homework 6 due October 15 at 23:59

  Orlicz spaces. Subgaussian properties.

• October 9 Lecture 11 Video

  Subgaussian Hoeffding's inequality. Subexponential distributions. Bernstein's inequality. The thin shell phenomenon.

• October 11 Lecture 12 Video Homework 7 due October 22 at 23:59

  Dimension reduction with Johnson-Lindenstrauss lemma. Combinatorial optimization. Example: Ising model.

• October 16 Lecture 13 Video

  Clustering, Max cut. Spectral relaxations. Semidefinite relaxations. Gram matrices. Semidefinite relaxation of max cut: Goemans-Williamson's algorithm.

• October 18 Lecture 14 Video Homework 8 due October 30 at 23:59

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

• October 23 Lecture 15 Video

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

• October 25 Lecture 16 Video Homework 9 due November 6 at 23:59

  What functions are kernels? Mercer's condition. Artificial neural networks. Large width limits. Kernels arising from neural networks. Neural tangent kernel. A refresher in linear algebra: spectral decomposition of symmetric matrices.

• October 30 Lecture 17 Video

  Singular value decomposition. Frobenius norm.

• November 1 Lecture 18 Video Homework 10 due November 13 at 23:59

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

• November 6 Lecture 19 Video

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

• November 8 Lecture 20 Video Homework 11 due November 20 at 23:59

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

• November 13 Lecture 21 Video

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

• November 15 Lecture 22 Video Homework 12 due November 27 at 23:59

  Matrix Hoeffding and Matrix Bernstein inequalities.

• November 20 Lecture 23 Video

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

• November 22 Lecture 24 Video Homework 13 due December 4 at 23:59

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

• November 27 Lecture 25 Video

  A generalization bound for finite hypothesis classes. VC dimension. The VC dimension of half-lines, intervals, and half-planes.

• November 29 Lecture 26 Video

  VC dimension of circles, rectangles, linear classifiers, polynomial classifiers, and neural networks. VC theory: Pajor's lemma and Sauer-Shelah lemma.

• December 4 Lecture 27 Video

  The uniform law of large numbers for empirical processes. Proof using symmetrization, Rademacher complexity, Hoeffding's inequality, and Sauer-Shelah lemma.

• December 6 Lecture 28 Video

  Applications: Glivenko-Cantelli theorem; VC generalization bound.