HDP KNU+

Lectures (Vershynin): MWF (Monday, Wednesday, Friday) 18:00-19:00 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.

Discussion (Vershynin): 30 minutes after each lecture.

Discussion (Chernova): Tuesdays 14.30-15:15 Kyiv time, by Google Meet. The link has been sent to your email, and can also be found in the first announcement in Google classroom.

Course description: This course will build probabilistic foundations for theoretical research in modern data science. The methods covered in this course form an essential toolbox for anyone looking to do mathematical work in machine learning, theoretical computer science, and signal processing.

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

Textbook: R. Vershynin, High dimensional probability. An introduction with applications in Data Science. Cambridge University Press, 2018. Download the book here.

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 2

  The curse of dimensionality. Probability can help: Monte-Carlo method. Lecture notes. Video recording

• September 5

  Convexity. Caratheodory theorem. Approximate Caratheodory theorem (pages 1-3 of my textbook). Proof by a probabilistic method, the empirical method of Maurey. Lecture notes. Video recording

• September 7

  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 (Corollary 0.0.4 from the book). Lecture notes. Video recording

• September 9

  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 (Proposition 2.1.2 in the book). Lecture notes. Video recording. Homework 1 is due at 23:59; submit it to Google classroom.

• September 12

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

• September 14

  Hoeffding's inequality proved (Section 2.2 of the book). Estimation of the mean: the median-of-means estimator. Lecture notes. Video recording

• September 16

  Variants of Hoeffding's inequality: two-sided and for bounded distributions (Theorems 2.2.5, 2.2.6). Poisson limit theorem (Theorem 1.3.4). Chernoff's inequality (Section 2.3). Lecture notes. Video recording. Homework 2 is due at 23:59; submit it to Google classroom.

• September 19

  Small and large deviations: Gaussian and Poisson regimes (end of Section 2.3). Random graphs as models of networks. Erdos-Renyi model. Phase transitions. Regularity of dense random graphs (Proposition 2.4.1). Lecture notes. Video recording

• September 21

  Irregularity of sparse random graphs (end of Section 2.4). Instance vs. uniform guarantees of probabilistic results. Geometric discrepancy. Lecture notes. Video recording

• September 23

  Proof of the discrepancy theorem. Lecture notes. Video recording. Homework 3 is due at 23:59; submit it to Google classroom.

• September 26

  Spaces of random variables. Normed and Hilbert spaces. Lp spaces. Cauchy-Schwarz, Holder's and Jensen's inequalities. (Sections 1.1, 1.2, 2.7.1 of the book.) Lecture notes. Video recording

• September 28

  Orlicz spaces (Section 2.7.1). Subgaussian properties (beginning of Section 2.5). Lecture notes. Video recording

• September 30

  Equivalence of subgaussian properties (Proposition 2.5.2). Subgaussian distributions and subgaussian norm (Section 2.5.2). Lecture notes. Video recording. Homework 4 is due at 23:59; submit it to Google classroom.

• October 3

  Subgaussian Hoeffding's inequality (Theorem 2.6.2). Subexponential distributions (Section 2.7). Bernstein's inequality (Theorem 2.8.1). Lecture notes. Video recording

• October 5

  The thin shell phenomenon. Dimension reduction with Johnson-Lindenstrauss lemma. Lecture notes. Video recording

• October 7

  Combinatorial optimization. Examples: Ising model, clustering, max-cut. Spectral relaxations. Semidefinite relaxations. Lecture notes. Video recording. Homework 5 is due at 23:59; submit it to Google classroom.

• October 10

  Gram matrices. Semidefinite relaxation of max cut: Goemans-Williamson's agorithm. (Section 3.6.3.) Lecture notes. Video recording

• October 12

  Grothendieck's inequality. Tensor calculus. Krivine's bound. (Section 3.7) Lecture notes. Video recording

• October 14

  A first exposure to machine learning: binary classification. Support vector machine. The kernel trick: kernelizing machine learning algorithms. Radial basis function kernel. Lecture notes. Video recording. Homework 6 is due at 23:59; submit it to Google classroom.

• October 17

  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 notes. Video recording

• October 19

  A refresher in linear algebra: spectral and singular value decompositions; Frobenius norm. Lecture notes. Video recording

• October 21

  The operator norm. Random vectors in high dimensions. Covariance matrix. Normal distribution in high dimensions. Principal component analysis. Lecture notes. Video recording. Homework 7 is due at 23:59; submit it to Google classroom.

• October 24

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

• October 26

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

• October 28: No class

  Homework 8 is due at 23:59; submit it to Google classroom.

• October 31

  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 notes. Video recording

• November 2

  Proof of Marchenko-Pastur law. Lecture notes. Video recording

• November 4

  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 notes. Video recording. Homework 9 is due this Sunday at 23:59; submit it to Google classroom.

• November 7

  Functional calculus. Loewner order. Matrix monotonicity of functions 1/x and log(x). (Section 5.4.1 of the book). Lecture notes. Video recording

• November 9

  Lieb's trace inequality. Matrix Hoeffding inequality. Lecture notes. Video recording

• November 11

  Matrix Bernstein inequality. Applications to networks (started): community detection in stochastic block models. Lecture notes. Video recording. Homework 10 is due this Sunday at 23:59; submit it to Google classroom.

• November 14

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

• November 16

  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 notes. Video recording.

• November 18

  Low-dimensional paradigm. The effective rank and effective dimension. Covariance estimation for low-dimensional data. Lecture notes. Video recording. Homework 11 is due this Sunday at 23:59; submit it to Google classroom.

• November 21

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

• November 23

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

• November 25: No class Thanksgiving in the United States

  Homework 12 is due this Sunday at 23:59; submit it to Google classroom.

• November 28

  VC theory: Pajor's lemma; Sauer-Shelah lemma. Lecture notes. Video recording

• November 30

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

• December 2

  Proof of the uniform law of large numbers: Symmetrization; Rademacher complexity. Applications: Glivenko-Cantelli theorem; VC generalization bound. Lecture notes. Video recording. Homework 13 is due this Sunday at 23:59; submit it to Google classroom.

• December 5

  Gaussian and subgaussian stochastic processes. Dudley's intergral inequality. Lecture notes. Video recording

• December 7

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

• December 9

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