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 STAT 210B at UC Berkeley, taught by Song Mei [15]; High-Dimensional Probability and Introduction to Machine Learning at Peking University, taught by Zhihua Zhang and Lei Wu, respectively [29, 25]; STAT 300B at Stanford University [6]; and CS 839 at UW–Madison [3]. I also referred to the books High-Dimensional Probability: An Introduction with Applications in Data Science [22] and High-Dimensional Statistics: A Non-Asymptotic Viewpoint [24].