5 Concentration Inequalities

We now turn to the high-dimensional setting, beginning with concentration inequalities. The section is organized as follows:

1.

Basic Concentration Inequalities

2.

Random Vectors

3.

Random Matrices

4.

Concentration of Lipschitz Functions

5.

Gaussian Concentration

This section mainly follows STAT210B (UC Berkeley, taught by Song Mei), High-dimensional probability (PKU, taught by Zhihua Zhang) and Introduction to Machine Learning (PKU, taught by Lei Wu), STAT300B (Stanford), CS839 (U Wisconsin–Madison). I also referred to the book High-dimensional probability: An introduction with applications in data science [5] and the book High-Dimensional Statistics: A Non-Asymptotic Viewpoint [6].