Lecture Notes: High-Dimensional Probability

with Applications in Data Science

Autumn 2024

Haotian Jiang
 Abstract

Advances in modern data science, computer science, statistics, and many other areas of science and
engineering call for the need to understand probability in high dimension. The large dimensions
of the objects involved result in the “curse of dimensionality”, rendering our common probabilistic
intuition incorrect and traditional algorithmic methods extremely inefficient. Consequently, typical
graduate probability or statistics courses are often not sufficient for beginner researchers to acquire
the mathematical background for studying theoretical questions in these areas.
The intention of this course is to introduce a set of probabilistic methods and results to partially
bridge this gap. We discuss theoretical tools surrounding concentration inequalities, random vec-
tors, random matrices, stochastic processes and chaining, and isoperimetric inequalities. Alongside
the development of theoretical foundations, we present various applications to data science.
The topic of high dimensional probability is extraordinarily broad and deep, and in this course, we
are only able to scratch the surface of this fast growing area. Nevertheless, in introducing some of
the most basic and fundamental techniques and results in this area, and in putting the theory into
action with a view towards data science applications, I hope this course can help you begin your
journey on utilizing high dimensional probability as an important toolkit in your research.
This course is based on the excellent textbook “High-Dimensional Probability: An Introduction
with Applications in Data Science” by Roman Vershynin, and part of his lecture notes. We also
point to the relevant but more advanced lecture notes on “Probability in High Dimension” by
Ramon van Handel.
Contents

1 Introduction to High Dimensional Probability 3

1.1 Challenges in the Era of Big Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Example: Numerical Integration and Monte-Carlo Method . . . . . . . . . . . . . . . 3
1.3 Counterintuitive Pheonomena in High Dimensions . . . . . . . . . . . . . . . . . . . 4
1.4 Example: Approximate Caratheodory . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Applications of Approximate Caratheodory . . . . . . . . . . . . . . . . . . . . . . . 7

2 Concentration Inequalities for Independent Random Variables 10

2.1 Gaussian Tail Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 CLT Does Not Suffice for Nonasymptotic Concentration . . . . . . . . . . . . . . . . 11
2.3 Markov’s Inequality and Chebyshev’s Inequality . . . . . . . . . . . . . . . . . . . . . 12
2.4 Hoeffding’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5 Application: The Median Trick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.6 Hoeffding’s Inequality for Bounded Random Variables . . . . . . . . . . . . . . . . . 16
2.7 Chernoff’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.8 Two Types of Deviation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.9 Bernstein’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.10 Application: Regularity of Random Graphs . . . . . . . . . . . . . . . . . . . . . . . 19

3 Subgaussian and Subexponential Random Variables 21

3.1 Subgaussian Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 The Subgaussian Norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Subexponential Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Bernstein’s Inequality for Subexponential Random Variables . . . . . . . . . . . . . . 28

1
 3.5 Looking Forward: Subexponentail and Subgaussian in High Dimensional Probability 28

4 The Thin Shell Phenomenon and High Dimensional Distributions 29

4.1 Concentration of the Norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 Dimension Reduction: Johnson-Lindenstrauss Lemma . . . . . . . . . . . . . . . . . 30
4.3 Subgaussian Distribution in High Dimensions . . . . . . . . . . . . . . . . . . . . . . 31
4.4 Subexponential Distribution in High Dimensions? . . . . . . . . . . . . . . . . . . . . 33

5 Random Matrices 34
5.1 Tool 1: The ε-Net Argument . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2 A Stronger ε-Net Argument . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.3 Application: Covariance Estimation of Gaussian Distribution . . . . . . . . . . . . . 39
5.4 Classical Laws of Random Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.5 Tool 2: The Stieltjes Transformation Method . . . . . . . . . . . . . . . . . . . . . . 42
5.6 Tool 3: The Moment Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.7 Tool 4: Matrix Concentration Inequalities . . . . . . . . . . . . . . . . . . . . . . . . 46
5.8 Background on Matrix Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.9 Proof of Matrix Hoeffding’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.10 Application: Covariance Estimation for Approximately Low Dimensional Distributions 52
5.11 Tool 5: The Stochastic Process Method . . . . . . . . . . . . . . . . . . . . . . . . . 54

6 Stochastic Processes 56
6.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.2 Gaussian Comparison Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.3 Application: Sharp Bounds on Gaussian Matrices . . . . . . . . . . . . . . . . . . . . 61
6.4 Sudakov Minorzation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.5 Gaussian Width: A Geometric Measure . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.6 Examples of Gaussian Width . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

7 The Chaining Method 67

7.1 Union Bound and the ε-Net Argument . . . . . . . . . . . . . . . . . . . . . . . . . . 67
7.2 Dudley’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

2
Chapter 1

Introduction to High Dimensional

Probability

1.1 Challenges in the Era of Big Data

In the era of big data, researchers in data science and machine learning are often faced with data
that have the following features:

1. The data set is comprised of a large number of samples;

2. Each sample is high dimensional, i.e., it is consisted of a huge number of coordinates.

For example, in image recognition, a data set is consisted of millions of images, each is represented
by a vector of pixels; a genome data set includes the DNA information of millions of people, and
each data point consists of a person’s full DNA sequence.
Classical statistics and probabilistic tools provide an excellent ground for dealing with a large
number of samples. For instance, central limit theorem states that the (properly scaled) sample
mean of i.i.d.1 observations converges to the standard Normal distribution. Many statistical
methods can be applied to understand the error of statistic estimators.
Dealing with high dimensional data turns out to be a much more challenging matter. The main
reason is that there is way more space in higher dimensions – exponentially more in the dimension.
For example, a cube of edge length 2 has volume 2d of that of a cube with unit edge length. This
exponential growth in space leads to the so-called “curse of dimensionality”, making many of our
usual probabilistic intuition incorrect and algorithmic tools inefficient in high dimensions.

1.2 Example: Numerical Integration and Monte-Carlo Method

Why are problems “exponentially harder” in higher dimensions, when there is exponentially more
space? Let us look at the classical example of numerical integration.
1
I.i.d. stands for independent and identically distributed (random variables).

3
In practice, one often needs to compute the integration of a function f over some domain. It is
almost always impossible to exactly compute it, so one often turns to numerical methods. After
proper transformation, the domain can be taken as [0, 1]d and one wants to compute [0,1]d f (x)dx,
R

for f : [0, 1]d → [0, 1]. For d = 1, a simple idea is to divide the interval [0, 1] into a 1-d grid with
resolution ε, where ε > 0 is a small number, and approximate compute (here n = 1/ε)
Z 1 n
X
f (x)dx ≈ f (iε).
0 i=1

Does this work in higher dimensions? Unfortunately, in higher dimensions, taking a grid point of
resolution ε means computing the function at (1/ε)d points. This exponential growth of evaluation
points with dimension makes the algorithm too inefficient to use in high dimensions, and this is an
excellent demonstration of the “curse of dimensionality”.

Probability to the Rescue. There turns out to be a remarkablyRsimple solution to this problem.
Simply take n i.i.d. samples x1 , · · · , xn ∈ [0, 1]d and approximate [0,1]d f (x)dx by the quantity

n
1X
f (X) := f (xi ).
n
i=1

How good is this approximation? Note that now the samples x1 , · · · , xn are no longer “regular” –
they can be all over the place. Nevertheless, this estimation is unbiased:
n Z
1X
E[f (X)] = E[f (xi )] = f (x)dx.
n [0,1]d
i=1

We can also compute its variance as

n n
1 X
1 X 1
Var(f (X)) = · Var f (x i ) = · Var(f (xi )) ≤ ,
n2 n2 n
i=1 i=1

where the last inequality uses that f (xi ) ∈ [0, 1]. Consequently, the error of using random samples
√
scales as 1/ n, regardless of the dimension!
This remarkably simple idea is known as the Monte Carlo algorithm, and is among the most
important algorithm of the 21st century. It beautifully bypasses the curse of dimensionality, and
its simplicity makes it extremely flexible to use in practice. This is the type of algorithms that is
feasible for handling high dimensional data – they are either dimension independent, or depends at
most polynomially on the dimenision (but not exponentially)! We will see several other (but more
involved) examples of such algorithms in the rest of this course.

1.3 Counterintuitive Pheonomena in High Dimensions

High dimensional problems are not only hard due to the “curse of dimensionality”, they are also
hard because it is often difficult to correctly reason about them. Many geometric and probabilistic

4
intuitions we have in our 3-dimensional world turn out to be incorrect when the dimension becomes
higher. Let us mention a few such examples without diving into the maths. Understanding some
of these pheonomena rigorously is one of the central objectives of this course.

The “Vanishing” Unit Ball. How large is the unit Euclidean ball, denoted B2d , in high dimen-
sions? It turns out its volume goes to 0 as the dimension increases! Yes, the unit ball vanishes
when dimension goes to infinity.

The “Thin Shell” Phenomenon. A uniformly random point in the ball B2d would be more likely
close to the surface of the ball. As dimension gets higher, most of the mass in the ball are located
in a “thin shell” near the surface. Such a “thin shell” behaviour not only holds for balls, but for
many other high dimensional distributions too.

The d
√ “Thin Slab” Phenomenon. A uniformly random point in the ball B2 would be roughly
1/ d in the x-axis. This means when dimension becomes higher, most of the mass in the ball
lies very close to the “vertical slab” {z ∈ Rd : zi ≈ 0}. If you think about it, this sounds quite
contradictory to the “thin shell” phenomenon, right?

“Escaping the Cube”. Imagine placing a unit ball at each one of the 2d vertices of the cube
[−1, 1]d , and then place a (scaled) ball B at the center of the cube, touching all of the 2d unit balls.
How large is the ball B?
If you sit down and draw a picture on a paper, you might think that the ball B is very tiny. It
turns out that this intuition is wrong in higher dimensions. In fact, the ball B exceeds the cube
already in 10-d, and it “escapes” the cube more and more as the dimension grows!
More counterintuitive phenomena in high dimensions can be found on this webpage.

1.4 Example: Approximate Caratheodory

Now we discuss another important example of how probability can help in high dimensions. Before
that, we need to introduce a few notions related to convexity.

Definition 1.4.1 (Convexity). A set T ⊂ Rd is convex if ∀x, y ∈ T , the segment connecting x and
y is contained in T .

Definition 1.4.2 (Convex hull). The convex hull of a set T ⊂ Rd , denoted as conv(T ), is the
smallest convex set containing T .

Here is a useful fact about convex hulls.

Fact 1.4.3. Any point z ∈ conv(T ) can be expressed as

m
X
z= λ i zi , (1.1)
i=1
Pm
where each zi ∈ T , all λi ≥ 0 and i=1 λi = 1.

5
In (1.1), we express z as a convex combination of z1 , · · · , zm . Such a representation is not unique,
so it is natural to ask how large m needs to be. This is answered in the following famous theorem
of Caratheodory’s.

Theorem 1.4.4 (Caratheodory’s theorem). Any point z ∈ conv(T ) ⊂ Rd can be expressed as a

convex combination of at most d + 1 points from T .

We will not prove this theorem, but let us demonstrate it with an example in 2-d.

Example 1.4.5. Checking the map, you will see that Chicago ∈ conv{Minneapolis, [Link], Detroit}.
And there is no way to express Chicago as a convex combination of only two of these cities.

This example shows that d + 1 in Theorem 1.4.4 is not improvable. Nonetheless, if one allows
for approximations, then one can significantly improve on the number of points in the convex
combination.

Theorem 1.4.6 (Approximate Caratheodory). Let T ⊂ Rd with diameter diam(T ) ≤ 1. Then for
any x ∈ conv(T ) and k ∈ N, there exists x1 , · · · , xk ∈ T such that
k
1X 1
x− xi 2
≤√ .
k 2k
i=1

Again, the approximation error here only depends on the number of points but not on the dimension.
Many different proofs of Theorem 1.4.6 is known. Here we give a classical proof via the probabilistic
method, known as the “empirical method of B. Maurey”.

Proof of Theorem 1.4.6. We start from an arbitrary convex combination of x given by

m
X
x= λ i zi ,
i=1
Pm
where zi ∈ T , λi ≥ 0 and i=1 λi = 1. Here, m can be large (by Caratheodory’s theorem, m can be
as large as d + 1). Now consider a random vector Z ∈ {z1 , · · · , zm }, where Z = zi with probability
λi . Then note that
m
X
E[Z] = λi zi = x.
i=1

Sample x1 , · · · , xk as i.i.d. copies of Z. It follows from linearity of expectation that

k
1 X 
E xi = x.
k
i=1

Let x′i be an independent copy of xi . The error of this approximation can be computed as
k k
1X 2 1X 2
E x− xi 2
=E (x − xi ) 2
k k
i=1 i=1

6
 k
1 X
= 2 E∥xi − E[xi ]∥22
k
i=1
(why?) k
1 X 1
≤ 2
E∥xi − x′i ∥22 ≤ ,
2k 2k
i=1

where the last inequality uses that diam(T ) ≤ 1. The last bound above means that there exists a
1
realization of x1 , · · · , xk that achieves squared error 2k . This proves the theorem.

Computational aspect. We also note that the proof of Theorem 1.4.6 also gives a very efficient
randomized algorithm for finding the points x1 , · · · , xk . Once we express x as a convex combination
of points z1 , · · · , zm , we can transform it to a solution to Theorem 1.4.6 by simply doing random
sampling.

1.5 Applications of Approximate Caratheodory

In this section, we discuss two applications of the approximate Caratheodory theorem.

Portfolio Building. Data scientists working in finance might be interested in creating a new
mutual fund (or simply building one’s investment portfolio) with a target combination of stocks by
combining the mutual funds that are available on the market.
To see the connection of this problem to approximate Caratheodory, we view each company’s stock
as a coordinate and any mutual fund as a vector of the stocks that form it. To build a target
portfolio, one simply tries to approximate a target vector of stocks by the vectors corresponding to
available mutual funds on the market.

Covering Numbers and Volume of Polytopes with Small Number of Vertices. We give
another geometric application of approximate Caratheodory, which is related to some of the topics
we are going to discuss later in the course.

Definition 1.5.1 (Covering number). Let T ⊂ Rd and ε > 0. The covering number of T at scale
ε > 0, denoted as N (T, ε), is the smallest number of Euclidean balls of radius ε needed to cover T .
Formally, N (T, ε) is the smallest N ∈ N such that there exists x1 , · · · , xN ∈ Rd satisfying
[
xi + εB2d .


T ⊆
i∈[N ]

Covering numbers measure both the size and complexity of T . It gives an immediate upper bound
on the volume vol(T ) ≤ N (T, ε) · vol(εB2d ).
Covering numbers suffer from the curse of dimensionality. For example, for the unit Euclidean ball
B2d , by a volume argument one can prove

N (B2d , 1/2) ≥ 2d .

Generally, covering numbers are exponential in the dimension.

7
But not always! The following theorem states that the covering numbers of a polytope with a small
number of vertices is dimension independent.

Theorem 1.5.2 (Covering numbers of polytopes with few vertices). Let P ⊂ Rd be a polytope with
1
m vertices and diam(P ) ≤ 1, and ε ∈ (0, 1). Then N (P, ε) ≤ m 2ε2 .

This is in stark contrast to the covering number of B2d which is exponential in dimension.
Before proving Theorem 1.5.2, we first note an important corollary.

Corollary 1.5.3 (Volume of polytopes with few vertices). Let P ⊂ Rd be a polytope with m vertices
and diam(P ) ≤ 1, then for some constant C > 0,

C log m
d/2
vol(P ) ≤ vol(B2d ) · .
d

This corollary can be derived from Theorem 1.5.2 and optimizing over ε. We leave this as a
homework. We should remark that the bound in Corollary 1.5.3 is almost the best possible – the
correct bound (up to the constant C) is:

C log(1 + m/d)
d/2

vol(P ) ≤ vol(B2d ) · ,
d
which is a classical work by Carl and Pajor in 1988. It is remarkable that we are able to come so
close to the right answer using a simple machinery. Now let us prove Theorem 1.5.2.

Proof of Theorem 1.5.2. Let T be the set of vertices of P , which satisfies P = conv(T ) and |T | = m
by assumption. Now we consider all possible averages of k = 2ε12 points from T . There are at most
 
m 1
≤ mk = m 2ε2
k

such averages. Now by approximate Caratheodory, each point x ∈ P is at Euclidean distance

√1 = ε from one of the averages. Consequently, the set of all averages give a cover of P at scale
2k2
ε. This proves the theorem.

Milman’s Hyperbolic Intuition. Before moving on, let us stare at Theorem 1.5.2 and Corol-
lary 1.5.3 once more. These results say that a polytope P ⊂ B2d withq
a small number of vertices is
much smaller than B2d – it essentially has volume of δB2d , where δ = C log
d
m
. So the picture of P
actually looks like this (even though it violates convexity):
q
In particular, P has a dense but tiny “core” of radius δ ≈ logdm , with m spikes reaching out to
constant radius. This is Milman’s famous “hyperbolic intuition”. We will come back to this picture
at various points later in this course.

8
Figure 1.1: Milman’s hyperbolic intuition for a polytope with small number of vertices. There is a tiny
core and a few spikes. The picture violates convexity, but “correctly” captures the measure distribution.

9
Chapter 2

Concentration Inequalities for

Independent Random Variables

2.1 Gaussian Tail Bound

Arguably one of the most important phenomena in high dimensional probability is the so-called
“concentration of measure”. In a simplified form, concentration refers to a variable X satisfying
X ≈ E[X], and concentration inequalities capture how large X can deviate from its mean.
As a typical example, a Gaussian random variable X ∼ N (µ, σ 2 ) concentrates around its mean. In
particular, it is well-known that a Gaussian random variable has 99.7% chance of staying within
3σ deviation from its mean µ, i.e.

P(|X − µ| > 3σ) < 0.3%.

This type of inequality is called a “tail bound”. The following proposition gives a more general
bound on the Gaussian tail, the proof of which is left as homework.

Proposition 2.1.1 (Gaussian tail bound). Let g ∼ N (0, 1), then for all t > 0,
1 1
1 2 1 1 2
− 3 · √ e−t /2 ≤ P(g ≥ t) ≤ · √ e−t /2 .
t t 2π t 2π

One can similarly obtain tail bounds for general Gaussian random variables after proper translation
and scaling. The following simpler bound (than Proposition 2.1.1) often suffices for our purposes.
2 /2
P(g ≥ t) ≤ e−t for all t ≥ 1.

As we will see later, in a sense, Gaussian-type tail bound, i.e. one that scales as exp(−Ct2 ) for
constant C > 0, is the “most ideal” kind of tail bound. Random variables satisfying this type of
tail bound is called subgaussian, and will be defined and discussed formally later in this chapter.

10
2.2 CLT Does Not Suffice for Nonasymptotic Concentration

Let us consider a concrete question.

Question 2.2.1 (Fair coin tosses). Suppose we toss a fair coin N times, what is the probability
that we see at least 3N
4 heads?

Of course, we are expected to see N2 coins, so here we need to quantitatively bound the deviation
from the expectation by more than N4 .

A Natural First Attempt. One of the most classical results we have learned in an undergrad
probability course is the central limit theorem (CLT). It states that if X1 , · · · , XN are i.i.d. samples
with variance σ 2 , then
N
1 X d
√ (Xi − E[Xi ]) → N (0, 1) as N → ∞. (2.1)
σ N i=1

In the context of Question 2.2.1, let us define

(
1 if the ith toss is head
Xi := ,
0 otherwise
PN
satisfies √ 1 N


then CLT states that the number of heads SN = i=1 Xi SN − 2 → N (0, 1) as
N/4
N → ∞. This looks very promising because we have seen in the previous
q section that Gaussian
N N
random variables admits concentration. In particular, if SN − 2 ≈ 4 · g were true, where
g ∼ N (0, 1), then we would obtain the tail bound
 3N   N N r N N N

P SN ≥ = P SN − ≥ ≈P ·g ≥ ≤ exp − .
4 2 4 4 4 8
Such a tail bound would be amazing for answering Question 2.2.1, except that... it is incorrect...,
at least the argument we used to derive it.

The Failure of CLT. The problem with the above argument is that the convergence in (2.1) turns
out to be too slow for what we need. For instance, for N i.i.d. fair coin tosses,
 

−N 2N 1
P exactly N/2 heads = P(SN = N/2) = 2 · ≈√ .
N N
On√the other hand, P(g√= 0) = 0, so the non-asymptotic error in the convergence (2.1) is at least
1/ N . This error of 1/ N turns out to be on the correct order by the following quantitative CLT.

Theorem 2.2.2 (Berry-Essen Theorem). Let X1 , · · · , XN be i.i.d. random variables with mean 0
and variance 1, and g ∼ N (0, 1). Denote ρ = E|Xi |3 , then for any t ∈ R,
N
1 X
ρ
P √ Xi ≥ t − P(g ≥ t) ≤ √ .
N i=1 N

11
Going back to our motivating Question 2.2.1. Although the asymptotic limit of √1N SN − N2 is

a standard Gaussian, we cannot really use this limit

to compute the tail bound as we did before.
Because of the error of √CN between √1N SN − N2 and a standard Gaussian, the best tail bound
we can derive out of (quantitative) CLT is √1 + exp(− N8 ).
N
So what should we do? Are we still able to derive an exponentially decreasing tail bound for
Question 2.2.1 as we had hoped for? To answer this question, we need a different machinery, one
that can be directly applied to the non-asymptotic quantity SN − N2 .

2.3 Markov’s Inequality and Chebyshev’s Inequality

Let us recall two basic inequalities from probability theorem, Markov’s inequality and Chebyshev’s
inequality. You have seen these inequalities when reading Chapter 1 of Vershynin’s textbook, so I
only remind you of their statements here.

Proposition 2.3.1 (Markov’s inequality). For any non-negative random variable X and t > 0,

E[X]
P X≥t ≤ .
t
Lemma 2.3.2 (Chebyshev’s inequality). Let X be a random variable with mean µ and variance
σ 2 . Then, for any t > 0, we have

σ2
P |X − µ| ≥ t ≤ 2 .
t

Note that Chebyshev’s inequality implies, for Question 2.2.1, the bound

3N
Var(SN ) N/4 4
P SN ≥ ≤ 2
= 2 = .
4 N /16 N /16 N

This is already better than the bound of roughly √1N from (quantitative) CLT, but it is still only
(inverse) polynomial, instead of exponentially small.

2.4 Hoeffding’s Inequality

We derive an exponential tail bound for Question 2.2.1 in this section. The main result we prove
is known as Hoeffding’s inequality (for symmetric Bernoullis).

Theorem 2.4.1 (Hoeffding’s inequality, symmetric Bernoullis). Let X1 , · · · , XN be i.i.d symmetric

Bernoulli random variables, i.e. P(Xi = 1) = P(Xi = −1) = 12 . Then for all t ≥ 0, we have

N
1 X
t2

P √ Xi ≥ t ≤ exp − .
N i=1 2

This inequality is the best possible (at least up to a constant factor in the exponent on the RHS).

12
Remark 2.4.2. A two-sided bound immediately follows from taking a union bound:
N
1 X
t2

P √ Xi ≥ t ≤ 2 exp − .
N i=1 2

Remark 2.4.3. Before proving Theorem 2.4.1, we remark that it implies the bound

3N
t2

P at least heads ≤ exp −
4 8
in Question 2.2.1. Note this is exactly what we had hoped for (using the asymptotic limits in CLT).
We leave deriving this bound as an exercise.

Proof of Theorem 2.4.1. The proof uses the following method of moment generating functions,
which is extremely useful in deriving exponential tail bounds. Let λ ≥ 0 be a parameter, then
N N √ 
1 X
 X

P √ Xi ≥ t = P exp λ Xi ≥ exp(λt N )
N i=1 i=1
√ N
X

≤ exp(−λt N ) · E exp λ Xi
i=1
√ N √
Y
N
= exp(−λt N ) · E exp(λXi ) = exp(−λt N ) · E exp(λX1 ) ,
i=1

where the second line uses Markov’s inequality, and the last line uses that Xi ’s are i.i.d. random
variables. Note that X1 is symmetric Bernoulli, so we have
1 1
E exp(λX1 ) = eλ + e−λ ≤ exp(λ2 /2),
2 2
where the last inequality follows from comparing the terms in the Taylor expansion on both sides.
Plug the above bound on the MGF of X1 to the bound above gives
N √
1 X
Xi ≥ t ≤ exp(−λt N + N λ2 /2).


P √
N i=1
√
Optimizing over λ, the best choice is λ = t/ N . This implies the theorem.

2.5 Application: The Median Trick

Let us consider the following mean estimation problem.

Question 2.5.1 (Mean estimation). Estimate the mean µ of a distribution (with unit variance)
from i.i.d. samples X1 , · · · , XN .

13
The classical estimator of this problem is the sample average, i.e.
N
1 X
µ
b := Xi .
N
i=1

Indeed, by Chebyshev’s inequality Lemma 2.3.2, one has the deviation bound

t
Var(b
µ) 1/N 1
µ − µ| ≥ √
P |b ≤ 2 = 2 = 2. (2.2)
N t /N t /N t

Ideally, we would like an exponential tail bound, e.g. if Xi are Gaussian N (µ, 1), then µ
b ∼
N (µ, 1/N ). By Gaussian tail bound Proposition 2.1.1, its deviation satisfies
t

µ − µ| ≥ √
P |b ≤ exp(−t2 /2).
N
Is it possible to get an exponential bound for the deviation of the estimator for general distributions?

Failure of Sample Average. For the sample average estimator, no. Let us consider the following
distribution X:
(
− √10N1 2 −1 1
with probability 1 − 10N 2
X= √ 1
.
2
10N − 1 with probability 10N 2

This is a very “skewed” distribution in the sense that it takes a super large value with super tiny
probability. Many counter-examples that prevent us from proving strong concentration inequalities
looks like this.
Back
√ to our question of whether we can get an exponential tail bound for deviation more than
t/ N , let us first verify that µ = E[X] = 0, and
1
1 1
Var(X) = E[X 2 ] = 1 − 2
· + · (10N 2 − 1) = 1.
10N 10N − 1 10N 2
2

√
So this distribution indeed satisfy the assumptions of our problem. Let us consider t = N . What
µ − µ| ≥ √tN = 1?
is the probability that |b
√
Note that whenever one of the Xi ’s takes the large value 10N 2 − 1, we would have that
N
1 X p 1
µ
b= Xi ≥ 10N 2 − 1 − (N − 1) · √ ≥ 2.
N 10N 2 − 1
i=1

1 1 1 that one of the X take the large value. This

But there is roughly N · 10N 2 ≈ 10N probability i
means that we would have the deviation bound
t
1 1
µ − µ| ≥ √
P |b ≈ = .
N 10N 10t2
1
Formally, the probability that at least one of the random variables Xi take large values is 1 − (1 − 1
10N 2
)N but
1
this is approximately 10N .

14
To summarize, up to a constant, the tail bound from Chebyshev’s inequality in (2.2) is not improv-
able in general, and exponential tail bound cannot be proved for the sample average estimator.

The “Median-of-Mean” Estimator. But surprisingly, there is a different estimator that can
achieve such an exponential deviation bound.

Theorem 2.5.2 (Median-of-mean estimator). There exists an estimator µ e(X1 , · · · , XN ) that

e=µ
satisfies, for some universal constant C > 0,
t

µ − µ| ≥ √
P |e ≤ 2 exp(−Ct2 ).
N

What is the idea behind this theorem? If we look at Chebyshev’s inequality again, we note that
O(N/t2 ) samples already allows us to provide a (small) constant tail bound. The fact that we are
using N samples (so basically, O(t2 ) times that for achieving constant tail bound) only boosts the
probability by another O(1/t2 ) factor. So really the question here is: can we boost it much faster?
Indeed you can, but by using the median instead of the mean. Here’s the formal proof.

Proof. We divide our samples into k = t2 /4 blocks [N ] = B1 ∪ · · · ∪ Bk , each of size N/k = 4N/t2 .
Let us denote the mean of the jth block of samples as µ bj , i.e.

1 X
µ
bj := · Xi .
N/k
i∈Bj

Our final estimator µ

e would be the median of the mean, i.e.

µ µ1 , · · · , µ
e := Med(b bk ).

Why is the median useful at all? To begin with, let’s first verify what we “noted” in the intuition,
that each block of 4N/t2 samples gives a constant tail bound. By Chebyshev’s inequality,
√
Var(b µj ) k/N 1
P |b
µj − µ| ≥ t/ N ≤ 2 = 2 = ,
t /N t /N 4
√
by our choice of k = t2 /4. √Now we think of each µ bj lies in [µ ± t/ N ] as throwing a biased coin
bj ∈ [µ ± t/ N ], and tail if not. Then the above bound says that this biased coin
– it is head if µ
comes to head with probability at least 3/4.
√
What must happen if the median-of-mean estimator µ interval [µ ± t/ N ]? It must
e lies outside the√
be that at least k/2 of the mean estimators µ bj lie outside of [µ ± t/ N ], i.e. at least k/2 of the
biased coin flips come out tail.
This looks very similar to the leading question we studied in earlier sections Question 2.2.1. There,
we are interested in the probability of seeing 3N/4 heads for N fair coin tosses, while here we are
interested in seeing k/2 tails for biased coin tosses (where the probability of head is at least 3/4).
The tail probability should be roughly the same – exponentially small. This can be proved by
simply plugging in Hoeffding’s inequality.

15
More Generally: The Median Trick. If you look carefully, the argument above only uses
that each µ
bj has small deviation with constant probability, and it has nothing to do with the fact
that these are the means of random samples. Consequently, taking the median of estimators (with
constant tail probability) works much more generally beyond the above setting. This is called the
median trick, and is one of the most important techniques for boosting the success probability.
Here’s one more type of problems where the median trick is extremely useful. Suppose you want
to carry out a statistical test, or if you are a computer scientist thinking about complexity theory,
outputting “yes” or “no” for the input as a member of a language (e.g. you are given an instance
of a 3-SAT problem and want to determine if it’s satisfiable or not). Often you may come up with
some algorithm that “succeeds” (or approximately so in a suitable sense) with constant probability.
Then you can boost the success probability of the algorithm to 1 − δ by repeatedly running the
algorithm O(log δ) times and take the majority vote. This is an example of the median trick, by
thinking of “yes” as 1 and “no” as 0. Then the majority vote is nothing but taking the median of
the output.
It is always good to keep in mind of the median trick when you want to boost the success probability
of some algorithm.

2.6 Hoeffding’s Inequality for Bounded Random Variables

It is possible to generalize Theorem 2.4.1 to arbitrary bounded random variables.

Theorem 2.6.1 (Hoeffding’s inequality, bounded r.v.s). Let X1 , · · · , XN be independent r.v.s such
that Xi ∈ [ai , bi ] for all i ∈ [N ]. Then,
N
X   2t2 
P (Xi − EXi ) ≥ t ≤ exp − PN .
(b − a ) 2
i=1 i=1 i i

We leave it as a simple exercise to verify that Theorem 2.6.1 generalizes Theorem 2.4.1. The proof
of Theorem 2.6.1 is similar to that of Theorem 2.4.1, and is left as a homework problem.

2.7 Chernoff ’s Inequality

Shortcomings of Hoeffding’s Inequality. It is important to note the shortcoming of Hoeffding’s

inequality. Hoeffding’s inequality only captures the extreme behaviour of Xi , but not the average
spread. It is optimal (up to constants) if X is “uniformly large and small”, e.g. the symmetric
Bernoulli case we’ve seen in Theorem 2.4.1, or if Xi is uniform in [ai , bi ].
It is very much not tight if Xi is “skewed”, just like the counter-example for the sample mean
estimator in Section 2.5. The problem here is the denominator of the bound in Theorem 2.6.1,
2
P
i.e. i i − ai ) , roughly corresponds
(b pP to the
variance
P(think about it as roughly saying one gets
2 2
constant tail bound for t = O i (bi − ai ) ). But i (bi − ai ) is not a correct estimation of the
variance if Xi is “skewed”. The variance is much smaller in that case.

16
Poisson Limit Theorem. Take the example of Xi ∼ Ber(p), and consider p → 0. Concentration
should get better as p becomes smaller, but this is not captured by Theorem 2.6.1 – Hoeffding’s
inequality does not depend on p at all.
What should N λ
P
i=1 Xi look like in this case? Let us take p = N with N → ∞. In this case, we
cannot use CLT because the r.v.s depend on their number. But we can use Poisson limit theorem
that we’ve seen in the first reading assignment.
(N ) (N )
Theorem 2.7.1 (Poisson limit theorem, special case). Let X1 , · · · , XN ∼ Ber Nλ be indepen-


(N )
dent r.v.s. Then N
P
i=1 Xi → Pois(λ), where we recall if X ∼ Pois(λ) then

λk
P(X = k) = e−λ · for all k ∈ N.
k!

The tail of a Pois(λ) r.v. is given by: for all t ≥ 0,

X λk eλ
t
P X ≥ t = e−λ ≤ e−λ ·


. (2.3)
k! t
k≥t

We leave this as an exercise to verify yourself (e.g. using Stirling’s formula)2 . In light of Poisson
(N )
limit theorem, we should expect that N
P
i=1 Xi to have a similar tail as in (2.3). But just as
how CLT fails for concentration inequalities, the error in Poisson limit theorem cannot be ignored.
Luckily, we can prove such a tail bound directly.

PN PNLet Xi ∼ Ber(pi ) be independent Bernoulli r.v.s., SN :=

Theorem 2.7.2 (Chernoff’s Inequality).
X
i=1 i their sum, and µ := E[S N ] = i=1 pi its mean. Then, for any t > µ,

eµ
t
P SN ≥ t ≤ e−µ ·


.
t
Remark 2.7.3. Three remarks are in order. First, Chernoff ’s inequality in the form of Theo-
rem 2.7.2 only holds for Bernoulli r.v.s.
Secondly, Chernoff bound is optimal for Bernoulli random variables (even i.i.d. ones). In particu-
lar, when Xi are i.i.d. Ber(µ/N ), then one can prove the lower bound
µ
t
P SN ≥ t ≥ e−µ ·


. (2.4)
t

Finally, unlike how we usually bound the deviation of SN from its mean µ, the bound in The-
orem 2.7.2 is one-sided (only the upper tail). Nonetheless, it is possible to modify the proof of
Chernoff ’s inequality to prove the corresponding lower tail bound of P(SN ≤ t) ≤ e−µ (eµ/t)t . We
leave this as an exercise for the reader to check.

Proof of Theorem 2.7.2. We again use the moment generating function method to write
Y 
P SN ≥ t ≤ e−λt · EeλS = e−λt · E eλXi .



i∈[N ]

2
This can also be derived from what we are going to discuss next.

17
Now we bound each individual MGF as

E eλXi = pi · eλ + (1 − pi ) = 1 + (eλ − 1)pi ≤ exp((eλ − 1)pi ).

 

Plug this into the bound above, we get

 N
X 
P SN ≥ t ≤ e−λt · exp (eλ − 1) pi = e−λt · exp (eλ − 1)µ .

i=1

Optimizing over λ ≥ 0 by choosing λ = ln(t/µ), one obtains the desired bound.

2.8 Two Types of Deviation

We note two distinct behaviours for the tail bound in Chernoff’s inequality:
eµ
t
P SN ≥ t ≤ e−µ ·


.
t

Large deviations. When t is large, the tail is roughly t−t ≈ exp(−t log t). This is a “Poisson
tail”, which is heavier than a Gaussian tail.

Small deviations. When t is small, say t = (1 + δ)µ for δ ≥ 0, we can compute

eµ
t e
(1+δ)µ  eδ µ
e−µ · = e−µ · = .
t 1+δ (1 + δ)1+δ
2δ
This is called the multiplicative Chernoff bound. We can now use log(1 + δ) ≥ 2+δ to obtain



P SN ≥ (1 + δ)µ ≤ exp µ δ − (1 + δ) log(1 + δ)
 2δ(1 + δ)

≤ exp µ δ −
2+δ
 µδ 2 
= exp − .
2+δ

For 0 ≤ δ ≤ 1, this is a Gaussian tail of at most exp(−µδ 2 /3)!

One can similarly obtain a bound for the lower tail by plugging in t = (1 − δ)µ in Remark 2.7.3.
Of course this only makes sense when 0 ≤ δ ≤ 1, in which case the bound is also Gaussian:

P SN ≤ (1 − δ)µ ≤ exp(−µδ 2 /2).

Combining the above, we get a two sided Gaussian tail bound in the “small deviation” regime:

P |SN − µ| ≥ δµ ≤ 2 exp(−µδ 2 /3) for all 0 ≤ δ ≤ 1.

18
2.9 Bernstein’s Inequality

Chernoff’s inequality is very powerful, and characterizes the two types of distinct behaviours in
the small and large deviation regimes. Unfortunately, it only holds for Bernoulli random variables.
Can we hope for a similar type of behaviour for more general random variables?
It turns out we can, for any bounded random variables.

Theorem 2.9.1 (Berstein’s inequality, bounded r.v.). Let X1 , · · · XN be independent, mean-zero

random variables such that |Xi | ≤ K almost surely for all i ∈ [N ]. Then, for every t ≥ 0, we have
N
 X   t2 /2 
P Xi ≥ t ≤ 2 exp − ,
σ 2 + Kt/3
i=1
PN
where σ 2 = 2
i=1 E[Xi ] is the variance of the sum.

There is a further strengthening of Bernstein’s inequality called Bennett’s inequality which we will
not state here. The bound in Bennett’s inequality is harder to compute, and in many applications
Bernstein’s inequality is sufficient. The proof of Bernstein’s also uses the moment generating
function method. We leave it as a homework problem.

Two Types of Deviation, Again! Note the two types of tail behaviors in Bernstein’s inequality,
just like in Chernoff’s inequality. What is different is that the two behaviours are now (more
delicately) captured by different parameters of the random variables, on which the distinction
between “small” and “large” deviations depends.
In Bernstein’s inequality, the Gaussian tail is captured by the variance σ 2 , while the exponential
tail behavior is controlled by the worst deviation K of a single random variable. The transition
from small (Gaussian tail) and large (exponential tail) deviation happens around t ≈ 3σ 2 /K.
It is interesting to note that in the large deviation regime, the exponential tail in Bernstein’s
inequality is heavier than the t−t type of tail in Chernoff’s inequality (so it is weaker than Chernoff).
This is because we are assuming less in Bernstein’s inequality.

2.10 Application: Regularity of Random Graphs

A classical model for random graphs is the Erdös-Renyi model.

Definition 2.10.1 (Erdös-Renyi model). Given n ∈ Z+ and 0 < p < 1, the random graph G(n, p)
is defined by fixing n vertices and independently connecting each pair of vertices with probability p.

Let us denote d := E[degG(n,p) (i)] = (n − 1)p the expected degree of a vertex. The following phase
transition phenomenon is known:

1. d ≈ 1: giant component;

2. d ≈ log n: connectivity of the graph G(n, P );

19
 3. d ≈ log n: regularity of the graph G(n, p) (see definition below).

See this Wikipedia page. We will discuss the phase transition for regularity in this lecture.

Definition 2.10.2 (Regularity). A graph G is regular if degG (i) is the same for all i.

We will show the phase transition that when d ≫ log n, then G(n, p) is approximately regular;
when d ≪ log n, the G(n, p) is far from regular.

Regularity of Dense Random Graphs. We begin with the dense case.

Theorem 2.10.3 (Regularity of Dense Random Graphs). There is an absolute constant C > 0
such that for d ≥ C log n, the degree of each vertex of G(n, p) is between [0.9d, 1.1d].

Proof. Homework.

Irregularity of Sparse Random Graphs. We now show that sparse random graphs are not
almost regular.

Theorem 2.10.4 (Regularity of Dense Random Graphs). There is an absolute constant c > 0 s.t.
if d ≤ c log n, then with probability at least 0.9, G(n, p) has a vertex with degree at least 10d.

This follows from the tightness of Chernoff’s inequality in (2.4), and will not be proved in class.

20
Chapter 3

Subgaussian and Subexponential

Random Variables

We have seen two types of tail behaviours: the Gaussian tail behaviour in Hoeffding’s inequality or
the small deviation regime of Bernstein’s inequality, and an exponential tail behaviour in the large
deviation regime of Bernstein’s inequality. It turns out that these two types of tail behaviour is
extremely common in the study of high dimensional probability. We define them formally in this
chapter.

3.1 Subgaussian Random Variables

Recall that in Hoeffding’s inequality (Theorems 2.4.1 and 2.6.1), if Xi are i.i.d symmetric Bernoullis,
one has the (Gaussian) tail bound
 1 X N 
P √ Xi ≥ t ≤ exp(−t2 /2). (3.1)
N i=1

Similar tail bounds hold when Xi are i.i.d. standard Gaussians or bounded between [−1/2, 1/2].
It is natural to ask, is there a general class of random variables for which a subgaussian tail bound
as in (3.1) holds?
Note that for N = 1, the tail bound in (3.2) states that X1 must satisfy

P |X1 | ≥ t ≤ exp(−t2 /2).

(3.2)

We show that Hoeffding’s inequality holds whenever the independent random variables satisfying
the bound in (3.2), so it is also a sufficient condition. Such random variables are called subgaussian.
In a sense, subgaussian random variables are “at least as good as a Gaussian”.

Properties of Gaussians. To characterize subgaussian random variables, let us first summarize

what we know for a standard Gaussian random variable g ∼ N (0, 1).

1. Tails: P(|g| ≥ t) ≤ 2 exp(−t2 /2), for all t ≥ 0;

21
 √
2. Moments: ∥g∥p = (E[|g|p ])1/p ≤ p, for all p ≥ 1. (Homework.)
R∞ 2 2
3. Moment generating function: E[exp(λg)] = √12π −∞ eλx−x /2 dx = eλ /2 , for all λ ∈ R.
2 /4 R∞ x2 /4 2 /2
4. MGF for g 2 : E[eg ]= √1
2π −∞ e · e−x dx ≤ 2.

It turns out that these four conditions are all equivalent for any distribution, up to universal
constant factors. These conditions characterize subgaussian random variables.
Lemma 3.1.1 (Subgaussian properties). Let X be a random variable. Then the following properties
are equivalent: the parameters Ki appearing in these properties differ from each other by at most
an absolute constant factor.1

(i) The tails of X satisfy

P |X| ≥ t ≤ 2 exp(−t2 /K12 ) for all t ≥ 0.

(ii) The moments of X satisfy

1/p √
∥X∥Lp = E|X|p ≤ K2 p for all p ≥ 1.

(iii) The MGF of X 2 is bounded at some point, namely

E exp(X 2 /K32 ) ≤ 2.

Moreover, if EX = 0 then the above properties are also equivalent to:

(iv) The MGF of X satisfies

E exp(λX) ≤ exp(K42 λ2 ) for all λ ∈ R.

The proof of this lemma is based on the identity that for any non-negative random variable X,
Z ∞
EX = P(X ≥ t)dt.
0

Proof of Lemma 3.1.1. We decompose the proof into the following implications.

(i) ⇒ (ii). By rescaling, we can assume wlog that K1 = 1. Then we can write
Z ∞
p
P |X|p ≥ u du


E|X| =
Z0 ∞
P |X| ≥ t ptp−1 dt


=
Z0 ∞
2
≤ 2e−t ptp−1 dt
0
1
The precise meaning of this equivalence is the following. There exists an absolute constant C such that property
i implies property j with parameter Kj ≤ CKi for any two properties i and j.

22
 Z ∞
t2 √ √
= 2p e− 2 (t/ 2)p−1 d(t/ 2)
√ 0
2πp √
= p/2 · E|g|p−1 ≤ 2π(p/2)p/2 ,
2
where g ∼ N (0, 1) and the last inequality uses the bound on Gaussian moments from the homework.
Taking the pth root of teh above gives the desired bound.

(ii) ⇒ (iii). Assume property (ii) holds with K2 = 1. Let us pick K3 = 10. Then we can use
Taylor expansion to obtain
∞
h X (X 2 /100)p i
E exp(X 2 /100) = E 1 +
p!
p=0
∞
X ·E[X 2p ]
=1+
100p · p!
p=1
∞
X (2p)p
≤1+
100p · (p/e)p
p=1
∞
X
= (e/50)p ≤ 2.
p=0

(iii) ⇒ (iv). Again, wlog that K3 = 1.

2
First consider the case where |λ| ≤ 1. Use the inequality ex ≤ x + ex for all x ∈ R, we get
2 2
EeλX ≤ E[λX] + Eeλ X
2
λ2
h i
= E eX
2
λ2 2 2
≤ EeX ≤ 2λ = eλ ·log 2 ,

where the first inequality in the last line is by Jensen’s inequality.

Now we consider |λ| ≥ 1. In this case, we can write
λ2 2 λ2


+ X2 log 2+ 21 λ2
EeλX ≤ Ee 2 ≤e 2
+log 2
≤e .

(iv) ⇒ (i). Wlog assume K4 = 1. Then we can use the MGF method to obtain (λ = t/2 > 0
below)

P(X ≥ t) = P eλX ≥ eλt

2 2 /4
e−λt+λ = e−t .

The same bound holds by considering −X instead.

It is also possible to use the same kind of MGF argument to go from (iii) to (i), therefore completing
the loop of implications even when X is not mean-zero. We refer to the proof of Proposition 2.5.2
in Vershynin’s Book for details.

23
3.2 The Subgaussian Norm

Since the constants in the equivalent conditions in Lemma 3.1.1 are all the same up to constants,
it gives a quantitative way to measure the size of subgaussian random variables – by the constants
in these properties!
In particular, define the subgaussian norm of a random variable X using (iii) as

∥X∥ψ2 := inf{t > 0 : E exp(X 2 /t2 ) ≤ 2}.

This turns out to be a norm on the space of random variables. The proof of this fact is left as a
homework. There is actually a more general way of defining norms on random variables using
Orlicz spaces, and the subgaussian norm is just one member of this family. Other members of this
family include Lp -norm and subexponential norm (which we will see later).
Definition 3.2.1 (Orlicz function). A function ψ : R+ → R+ is called an Orlicz function if it is
convex, increasing, and (
0 as X → 0,
ψ(x) →
∞ as X → ∞.

2
Examples of Orlicz functions include ψ(x) = xp , or ψ1 (x) = ex − 1, or ψ2 (x) = ex − 1.
Definition 3.2.2 (Orlicz norm). For a given Orlicz function ψ, the corresponding Orlicz norm of
a random variable X is defined as
 
∥X∥ψ := inf{t > 0 : E ψ(|X|/t) ≤ 1}.

The Orlicz space is defined as

Lψ := {random variables X such that ∥X∥ψ < ∞}.

We leave it as a homework to verify that ∥X∥ is indeed a norm on Lψ . Note that Orlicz norm
2
captures subgaussian norm by choosing ψ2 (x) = ex − 1. Orlicz norm also captures the Lp norm of
random variables by the choice ψ(x) = xp .

Rewriting Subgaussian Lemma via Subgaussian Norm. Given the subgaussian norm ∥X∥ψ2 <
∞ of a random variable X, one can write the other equivalent conditions in Lemma 3.1.1 as

(i) Tails: P(|X| ≥ t) ≤ 2 exp t2 /C∥X∥2ψ2 , for all t ≥ 0.

√
(ii) Moments: ∥X∥Lp ≤ C p · ∥X∥ψ2 , for all p ≥ 1.

(iv) MGF: Moreover, if EX = 0, then E exp λX) ≤ exp(C∥X∥2ψ2 λ2 , for all λ ∈ R.

Examples of Subgaussian Random Variables. The following are some typical examples of
subgaussian random variables (all having ∥X∥ψ2 bounded by some constant).

1. Standard Gaussian: X ∼ N (0, 1).

24
 2. Bernoulli: X ∼ Ber(p).

3. Uniform: X ∼ Unif([0, 1]).

4. Bounded: |X| ≤ C almost surely, for some constant C > 0.

Since subgaussian norm is a norm, it trivially satisfies the following triangular inequality.

Lemma 3.2.3 (Subgassian triangular inequality). Let X1 , · · · , XN be subgaussian random variables

(not necessarily independent), then we have
N
X N
X
Xi ≤ ∥Xi ∥ψ2 .
ψ2
i=1 i=1

But when the random subgaussian random variables are independent and mean-zero, a much
stronger bound holds, where the subgaussian norm acts like the standard deviation.

Lemma 3.2.4 (Sums of independent mean-zero subgaussians). Let X1 , · · · , XN be independent,

mean-zero, subgaussian random variables, then
N N
X 2 X
Xi ≤C ∥Xi ∥2ψ2 ,
ψ2
i=1 i=1

where C > 0 is a universal constant.

PN
Proof. We prove this lemma by using property (iv) in Lemma 3.1.1. Note that i=1 Xi is also
mean-zero. So we can bound
N
X N
Y  N
X 
exp(λXi ) ≤ exp Cλ2 ∥Xi ∥2ψ2 .


E exp λ Xi = E
i=1 i=1 i=1

This by Lemma 3.1.1 implies the lemma statement.

PN
PN
Recall that Var i=1 Xi = i=1 Var(Xi ) for independent random variables Xi , the above lemma
suggests that subgaussian norm square captures the variance in some sense.
Lemma 3.2.4 actually implies the following more general version of Hoeffding’s inequality (which
we recall was our initial motivation at looking at the class of subgaussian random variables).

Theorem 3.2.5 (Subgaussian Hoeffding’s inequality). Let X1 , · · · , XN be indepndent, mean-zero,

subgaussian random variables, then
N
 X  Ct2

P Xi ≥ t ≤ 2 exp − 2 ,
σ
i=1
PN
where C > 0 is a universal constant, and σ 2 = 2
i=1 ∥Xi ∥ψ2 .

Proof. This theorem is an immediate corollary of Lemma 3.2.4 together with property (i) in
Lemma 3.1.1.

25
It is instructive to see how Theorem 3.2.5 generalizes Theorems 2.4.1 and 2.6.1 (up to constants
in the exponent). For example, when X1 , · · · , XN are symmetric Bernoulli random variables, then
each ∥Xi ∥ψ2 ≤ 1 and then the RHS in Theorem 3.2.5 becomes 2 exp(−Ct2 /n).
Moreover, say we have Xi ∼ N (0, σi2 ), then we know that X ∼ N (0, σ 2 ), with σ 2 = N 2
P
i=1 σi . We
know from Proposition 2.1.1 that

P(|X| ≥ t) ≤ 2 exp(−t2 /2σ 2 ),

which is exactly the bound in Theorem 3.2.5 (up to constants in the exponent). Consequently,
Theorem 3.2.5 indeed captures behaviours of Gaussian-like random variables accurately.

Centering. Note that our definition of subgaussian random variables in Lemma 3.1.1 does not
require them to be mean-zero, while Lemma 3.2.4 and theorem 3.2.5 all have the mean-zero re-
quirement. This is not a problem because of the following lemma.

Lemma 3.2.6 (Centering for subgaussian). If X is a subgaussian random variable, then X − EX

is subgaussian with
∥X − EX∥ψ2 ≤ C∥X∥ψ2 ,
for a universal constant C.

Proof. Note that |EX| ≤ E|X| ≤ C1 ∥X∥ψ2 using Property (ii) in Lemma 3.1.1. It follows that

∥X − EX∥ψ2 ≤ ∥X∥ψ2 + ∥EX∥ψ2 ≤ ∥X∥ψ2 + 2|EX| ≤ C∥X∥ψ2 .

3.3 Subexponential Random Variables

Despite being extremely powerful, subgaussian random variables are not universal. For example, a
two-sided exponential random variable X has tail of the form P(X ≥ t) ≤ exp(−t) which is much
heavier than a Gaussian tail.
As another example, consider a standard Gaussian g ∼ N (0, 1). √ We know g is O(1)-subgaussian,
but is g 2 also subgaussian? Note that P(|g 2 | ≥ t) = P(|g| ≥ t) ≤ 2 exp(−t/2), which is almost
tight. This is again an exponential tail, so g 2 is not subgaussian.
Random variables with such an exponential tail are common (as we will see). We call them subex-
ponential random variables. Similar to the subgaussian case, there are many equivalent definitions.

Lemma 3.3.1 (Subexponential properties). Let X be a random variable. Then the following
properties are equivalent: the parameters Ki appearing in these properties differ from each other by
at most an absolute constant factor.

(i) The tails of X satisfy

P |X| ≥ t ≤ 2 exp(−t/K1 ) for all t ≥ 0.

26
 (ii) The moments of X satisfy

1/p
∥X∥Lp = E|X|p ≤ K2 p for all p ≥ 1.

(iii) The MGF of |X| is bounded at some point, namely

E exp(|X|/K3 ) ≤ 2.

Moreover, if EX = 0 then the above properties are also equivalent to:

(iv) The MGF of X satisfies

1
E exp(λX) ≤ exp(K42 λ2 ) for all |λ| ≤ .
K4

The proof of these equivalences is similar to the subgaussian case and will be omitted here. We
similarly define the exponential norm as the smallest parameter K3 :

∥X∥ψ1 := inf{t > 0 : exp(|X|/t) ≤ 2}.

This is again a special case of the Orlicz norm by taking ψ1 = ex − 1.

As in the subgaussian case, one can also center a subexponential random variable without blowing
up its subexponential norm.
Lemma 3.3.2 (Centering for subexponential). If X is a subexponential random variable, then
X − EX is subexponential with
∥X − EX∥ψ1 ≤ C∥X∥ψ1 ,
for a universal constant C.

The proof of this lemma is almost identical to that of Lemma 3.2.6 and we omit it here.

Connection to Subgaussian Random Variables. You might already notice the similarity of
the properties in Lemma 3.3.1 and Lemma 3.1.1. Indeed, subexponential random variables are
subgaussian random variables are intimately connected.
First, any subgaussian random variables is also subexponential. This can be easily seen from
comparing property (ii) in Lemmas 3.1.1 and 3.3.1. This says that the subgaussian property is
more stringent than subexponential.
Moreover, we have the following stronger relationship between the two.
Proposition 3.3.3 (Subexponential is Subgaussian Square). A random variable X is subgaussian
iff X 2 is subexponential. Moreover, ∥X 2 ∥ψ1 = ∥X∥2ψ2 .

Proof. This follows immediately from the definition of the two norms.

Examples of Subexponential but Not Subgaussian Random Variables. Besides the square
of subgaussian random variables, there are also natural examples of random variables that are
subexponential but not subgaussian.

27
 1. Exponential: X ∼ Exp(1) (or its symmetric version). Note that in this case,
Z ∞
E[eλX ] = eλx e−x dx,
0
which is only finite when λ < 1. Thus the restriction on λ in (iv) in Lemma 3.1.1 is crucial.
2. Poisson: we’ve seen that a random variable X ∼ Pois(1) has tail t−t , which is subexponential
but not subgaussian.

3.4 Bernstein’s Inequality for Subexponential Random Variables

As we’ve already discussed, subgaussian tail is necessary for Hoeffding’s inequality. Consequently,
we cannot hope that subexponential random variables also satisfy Hoeffding’s inequality. In par-
ticular, for N = 1, let K := ∥X1 ∥ψ1 , the subexponential tail bound gives
 Ct 
P(|X| ≥ t) ≤ exp − ,
K
and this is heavier than the Gaussian tail bound in Hoeffding’s inequality.
Surprisingly, N = 1 is the only obstruction. One can prove the following general Bernstein’s
inequality that is a mixture of the Gaussian tail in Hoeffding’s inequality with the exponential tail
bound for N = 1.
Theorem 3.4.1 (Subexponential Bernstein’s Inequality). Let X1 , · · · , XN be independent, mean-
zero, subexponential random variables. Then, for every t ≥ 0, we have
N
 X    t2 t 
P Xi ≥ t ≤ 2 exp − C min PN , ,
i=1 ∥X i ∥ 2
ψ
maxi ∥Xi ∥ψ1
i=1 1

where C > 0 is a universal constant.

The proof of this theorem is similar to the proof of Theorem 3.2.5. We refer to the proof of Theorem
2.8.1 in Vershynin’s book for details.
Note that the same type of large and small deviations phenomenon also appears in Theorem 3.4.1:
in the small deviation regime one has a Gaussian tail, while for large t one has an exponential
N
∥Xi ∥2ψ
P
i=1
decay. The transition happens at roughly t ≈ maxi ∥Xi ∥ψi .
1
If all ∥Xi ∥ψ1 = K are all the same, the
point of transition simplifies to t ≈ N K.

3.5 Looking Forward: Subexponentail and Subgaussian in High

Dimensional Probability

Certainly, subgaussian and subexponential distributions don’t capture everything that appears in
applications. Nonetheless, they are the most common type of behaviours when studying high
dimensional probability, and in many cases it is a mixture of the two (as in Bernstein’s inequality).
Often times, the whole problem is to determine if certain type of concentration phenomenon leads
to a subgaussian or an subexponential tail. We will see more examples in later chapters.

28
Chapter 4

The Thin Shell Phenomenon and

High Dimensional Distributions

In this chapter, we discuss the thin shell phenomenon more formally via the concentration of norm.
We discuss examples of high dimensional distributions, e.g. how a (properly scaled) standard
Gaussian in high dimensions look like the uniform distribution over the sphere. We also discuss
applications to dimensionality reduction.

4.1 Concentration of the Norm

Let X = (X1 , · · · , Xn ) be a random vector in Rn , where each coordinate Xi are independent

random variables with E[Xi2 ] = 1. Note that
n
X
E∥X∥22 = Xi2 = n.
i=1
√ √
We should expect that ∥X∥2 ≈ n. But how closely does ∥X∥2 concentrates around n? This is
the content of the following theorem.
Theorem 4.1.1 (Concentration of the norm). Let X = (X1 , · · · , Xn ) ∈ Rn be a random vector
with independent, subgaussian coordinates Xi that satisfy ∥Xi ∥ψ2 ≤ 1 and EXi2 = 1. Then
√
∥X∥2 − n ≤ C,
ψ2

for a universal constant C.

√
Why should ∥X∥2 − n be typically on the order of a constant? Here is a simple intuition. The
norm square ∥X∥22 is a sum of independent (subexponential) random variables, so we should expect
√ √
∥X∥22 ≈ n + C n. Taking the square root of this gives ∥X∥2 ≈ n + C ′ .

The Thin Shell Phenomenon. To further illustrate this theorem, note that for a standard
Gaussian vector g ∼ N (0, In ) ∈ Rn , Theorem 4.1.1 implies that for some universal constant c > 0,
√ √

P 0.99 n ≤ ∥g∥2 ≤ 1.01 n ≥ 1 − 2 exp(−cn). (4.1)

29
 √
So the Euclidean length of a standard Gaussian vector concentrates closely around n. Moreover,
we can write g = ∥g∥2 · u, where u ∈ Sn−1 is a uniformly random direction, and ∥g∥2 and u are
√
independent. As ∥g∥2 concentrates around n, this says that √1n g is very close to u, a uniformly
random vector from the unit sphere.
Generally when working with high dimensional probability problem, one can intuitively think of the
√
following as equivalent: (1) a standard Gaussian vector divided by n, (2) the uniform distribution
over the unit sphere Sn−1 , and (3) the uniform distribution over the unit Euclidean ball B2n .
Gaussians are particularly nice to work with because their coordinates are independent. But we
should also note that this equivalence is just for intuition, not for a rigorous proof. We will
(hopefully have time to) introduce more formal tools to deal with concentration on unit sphere or
unit ball towards the end of the course.
We will only prove the simpler inequality (4.1) in class. The proof of Theorem 4.1.1 can be found
in the Section 3.1 of Vershynin’s book.

Proof of (4.1). The main difficulty behind the proof is that the norm ∥g∥2 is not a sum of inde-
pendent random variables.
But the norm square is! Note that ∥g∥22 − n = ni=1 (gi2 − 1), where the gi2 − 1 are i.i.d. mean-zero
P
random variables such that

∥gi2 − 1∥ψ1 ≤ C1 · ∥gi2 ∥ψ1 = C1 · ∥gi ∥2ψ2 ≤ C.

So we may apply Bernstein’s inequality to obtain

 n2 n

P ∥g∥22 − n ≥ 0.0001n ≤ 2 · exp − C2 · min 2 ,


,
σ K
where σ 2 = ni=1 ∥gi2 − 1∥2ψ1 ≤ C 2 n and K = maxi ∥gi2 − 1∥ψ1 ≤ C. So the probability bound above
P
is at most 2 exp(−cn).
Then taking the square root, it follows that with probability at least 1 − exp(−cn), we have
√ √
0.99 n ≤ ∥g∥2 ≤ 1.01 n. This proves (4.1).

4.2 Dimension Reduction: Johnson-Lindenstrauss Lemma

In data science, we often deal with data of very high dimensions, e.g. texts, images, DNA, etc. Say
we are given data points x1 , · · · , xN ∈ Rd with d very large. Storing the d-dimensional data set
costs a lot of space, and running algorithms directly on them might be very slow. It is natural to
ask if we can reduce the dimension of the data points while preserving key properties of the data?
It turns out we can reduce the dimension to n = O(log N ), while preserving the geometry of the
data points. More formally:

Theorem 4.2.1 (Johnson-Lindenstrauss lemma). Given vectors x1 , · · · , xN ∈ Rd , there exists a

linear map T : Rd → Rn with n ≤ C log N such that for all i, j = 1, · · · , N ,

0.99∥xi − xj ∥2 ≤ ∥T (xi ) − T (xj )∥2 ≤ 1.01∥xi − xj ∥2 .

30
Proof. The idea is to pick a Gaussian random matrix G ∈ Rn×d with i.i.d. entries Gi,j ∼ N (0, 1),
and let T (x) = √1n Gx.

Note that for any fixed unit vector z ∈ Rd , we have

(Gz)i = Gi,j zj ∼ N (0, 1).

Therefore, concentration of norm in (4.1) states that

P 0.99 ≤ ∥T (z)∥2 ≤ 1.01 ≥ 1 − 2 exp(−cn).

To prove that T approximately preserves the pair-wise distance between points, let us fix i ̸= j ∈
x −x
[N ], and plug in z = ∥xii−xjj∥2 . Using that T is a linear map, we obtain


P 0.99∥xi − xj ∥2 ≤ ∥T (xi ) − T (xj )∥2 ≤ 1.01∥xi − xj ∥2 ≥ 1 − 2 exp(−cn).

Now since there are at most N 2 pairs of such (i, j), we can choose n such that cn = 10 log n. Then
union bound over all N 2 pairs, we obtain that with probability at least 1 − n17 , the random linear
map T satisfies the theorem statement.

A few remarks are in order. First, note that the dimension in JL depends (logarithmically) on the
number N of data points. This does not make sense if the set of points is infinite. Nonetheless,
there is a more general version of JL that works for infinite sets, which characterizes the distortion
of distances by the Gaussian width of the point set. See Section 9.3 of Vershynin’s book for details.
Second, naively, JL takes time O(nd) to compute the image of each data point, which is a matrix-
vector product. In applications, d is usually very large, so it is desirable to obtain runtime of the
form O(d + poly(n)). Such type of “fast JL” has been studied in the literature.

4.3 Subgaussian Distribution in High Dimensions

The concept of subgaussian distributions in Lemma 3.3.1 can be extended naturally to higher
dimensions. Recall that for the standard Gaussian vector g ∼ N (0, In ) in Rn , every marginal
⟨g, u⟩ is a standard Gaussian random variable for all u ∈ Sn−1 . We similarly characterizes a high
dimensional subgaussian distribution by the subgaussianity of its marginals.

Definition 4.3.1 (Subgaussian random vector). A random vector X ∈ Rn is called subgaussian

if the one-dimensional marginals ⟨X, u⟩ are subgaussian random variables for all u ∈ Rn . The
subgaussian norm of X is defined as

∥X∥ψ2 := sup ⟨X, u⟩ ψ2

.
u∈Sn−1

Of course, such a definition is vacant if not properly justified by examples. We give a few below.

Random Vector with Independent Subgaussian Coordinates. This is the canonical example
of a subgaussian vector, and the primary reason of defining them in the first place.

31
Lemma 4.3.2 (Subgaussian random vector with independent coordinates). Let X = (X1 , · · · , Xn ) ∈
Rn be a random vector with independent, mean-zero, subgaussian coordinates Xi . Then X is sub-
gaussian with norm
∥X∥ψ2 ≤ C max ∥Xi ∥ψ2 .
i∈[n]

Proof. This lemma follows from Lemma 3.2.4. For any u ∈ Sn−1 , by Lemma 3.2.4, we have
n n
2
X 2 X 2
⟨X, u⟩ ψ2
= ui Xi ≤C u2i Xi ψ2
≤ C max ∥Xi ∥2ψ2 ,
ψ2 i∈[n]
i=1 i=1
Pn 2
where the last inequality follows because i=1 ui = 1. This proves the lemma.

We remark that the independence assumption in Lemma 4.3.2 is central. When the coordinates
are not independent, it is possible that ∥X∥ψ2 ≫ maxi∈[n] ∥Xi ∥ψ2 . You will be asked to come up
with such an example in the homework.

Multivariate Gaussian and Bernoulli. As already noted, a standard Gaussian vector X ∼

N (0, In ) is subgaussian with norm
∥X∥ψ2 ≤ C.
A multivariate symmetric Bernoulli distribution X = (X1 , · · · , Xn ), with Xi are i.i.d. symmetric
Bernoullis is subgaussian with ∥X∥ψ2 ≤ C (by Lemma 4.3.2).

Uniform Distribution on the Sphere and Ball. As examples of subgaussian random vectors
where coordinates are not independent, the uniform distributions over the (scaled) sphere or (scaled)
Euclidean ball are subgaussian.
Theorem 4.3.3 (Uniform distribution on spheres and balls are subgaussian). Let X be a random
√
vector uniformly drawn from either the (scaled) sphere n · Sn−1 or the (scaled) Euclidean ball
√
n · B2n , then X is subgaussian and
∥X∥ψ2 ≤ C.

This theorem can be proved using the concentration of norm in Theorem 4.1.1 together with the
observation that a uniformly random vector from Sn−1 can be viewed as g/∥g∥2 , where g ∼ N (0, 1).
We omit the details here and refer to the proof of Theroem 3.4.6 in Vershynin’s book.

Uniform Distribution on Convex Bodies. Consider a convex body1 K ⊆ Rn , so that a

uniformly random vector X over K satisfies E[X] = 0 and E[XX ⊤ ] = In . Such a convex body is
√
called isotropic. For example, nB2n is an isotropic convex body.
√
For isotropic convex bodies like nB2n or a proper scaling of the unit cube [−1, 1]n , a uniformly
random vector X over them satisfies ∥X∥ψ2 ≤ C. Is this always true for any isotropic convex body?
In the homework, you will see that this is not the case for a proper scaling of the ℓ1 -ball. Namely,
there exists isotropic convex bodies for which the uniform distribution over them have subgaussian
norm NOT bounded by any universal constant.2
1
A convex body is a compact convex set with a non-empty interior.
2
Rigorously speaking, according to the definition of subgaussian random vectors in Definition 4.3.1, these distri-
butions are still subgaussian, but now with subgaussian norms now depending on the dimension.

32
4.4 Subexponential Distribution in High Dimensions?

Although uniformly random distribution over certain isotropic convex sets might not have constant
subgaussian norm, their subexponential norm is always bounded by a constant.

Theorem 4.4.1 (Uniform distribution over isotropic convex sets). Let X ∼ Unif(K), where K ⊆
Rn is an isotropic convex body. Then for all unit vector u ∈ Sn−1 ,

⟨X, u⟩ ψ1
≤ C.

This is a deeper result (about convexity) and will not be proved here. Properties of uniform
distribution over high dimensional convex bodies are the topics of study in an area called asymptotic
convex geometry, and is still an area with lots of active research going on.
We end this chapter with a natural question.

Question 4.4.2. Is there also a high dimensional analog of subexponential distribution?

Answer. In principle, analogous to the definition of subgaussian vector in Definition 4.3.1, one can
define a subexponential random vector via marginals. For instance, Theorem 4.4.1 states that the
uniform distribution over an isotropic convex body is C-subexponential.
Nonetheless, such a definition is perhaps not as useful as subgaussian random vector because of a
lack of analog of Lemma 4.3.2 for subexponential random variables. For instance, a random vector
X whose coordinates Xi are independent subexponential random variables with ∥Xi ∥ψ1 does NOT
always satisfy ∥X∥ψ1 ≤ O(1).

33
Chapter 5

Random Matrices

In this chapter we discuss the theory of random matrices, objects that arise in many applications
such as covariance estimation, community detection, spectral clustering, etc. We will primarily
focus on studying the spectral properties of random matrices. This chapter assumes familiarity
with the basic linear algebraic definitions and properties related to matrices, such as singular value
decomposition and norms (e.g. Frobenius norm, operator norm) of matrices.

Some Background. The history of random matrices started from physics, where Eugene Wigner
used them to model the nuclei of heavy atoms in the 1950s. Over the years, random matrix theory
has become such a useful tool that appears in a large spectrum of applications, such as quantum
computing, high dimensional statistics, graph sparsification, coding theory, etc.
As an example, suppose we can access samples of a high dimensional Gaussian distribution N (0, Σ)
and we want to estimate the (unknown) covariance matrix Σ. A natural strategy would be to sample
i.i.d. X1 , · · · , Xn ∼ N (0, Σ) and use the empirical covariance
n
1X
Σn := Xi Xi⊤
n
i=1

as an estimator for Σ. Surely this is an unbiased estimator, but the question is what is its deviation
and how many samples do we need in order to achieve certain error (aka sample complexity)?
This question involves understanding the behaviour of the random matrix Σn , and we will introduce
various tools to understand random matrices like this.

5.1 Tool 1: The ε-Net Argument

We begin our study of random matrix theory by looking at the simplest possible example: a random
matrix with i.i.d. standard Gaussian entries.
We will develop a basic but very powerful method, called ε-net argument, for bounding the operator
norm of such matrices. To do so, we need to introduce a few concepts.

34
ε-Nets and Coverings. We introduce the notion of ε-nets for general metric spaces. It is
important to keep in mind of the special case of Euclidean spaces for intuition.
Definition 5.1.1 (ε-net). Let (T, d) be a metric space, a set K ⊂ T , and ε > 0. A subset N ⊂ K
is called an ε-net of K if every point in K is within a distance ε of some point of N , i.e.

∀x ∈ K, ∃x0 ∈ N such that d(x, x0 ) ≤ ε.

ε-nets are closely related to the notion of covering numbers we defined earlier. In particular, N is
an ε-net of K iff K can be covered by balls with centers in N and radii ε.
If you are not used thinking about general metric spaces, the following picture shows what an ε-net
(or cover) looks like in Euclidean space (the centers of the balls form an ε-net).

Figure 5.1: An ε-covering of a set. The centers of the balls form an ε-net.

Definition 5.1.2 (Covering numbers). The smallest possible cardinality of an ε-net of K is called
the covering number of K and is denoted N (K, d, ε). Equivalently, N (K, d, ε) is the smallest number
of closed balls with centers in K and radii ε whose union covers K.

If d is the Euclidean norm, we simply write N (K, d, ε) as N (K, ε). For Euclidean spaces, covering
numbers can be bounded in terms of volumes as follows.
Proposition 5.1.3 (Covering numbers and volumes). Let K be a subset of Rn and ε > 0, then
|K| |(K + (ε/2)B2n )|
n ≤ N (K, ε) ≤ ,
|εB2 | |(ε/2)B2n |
where A + B := {a + b : a ∈ A, b ∈ B} denotes the Minkowski sum.

Proof. The lower bound is a trivial volume argument and has been discussed before. To prove the
upper bound, we use the following standard “packing to covering” argument.
Pick a maximal set of points x1 , · · · , xN ∈ K such that the (ε/2)-radii Euclidean balls centered at
each xi are disjoint, i.e. ∥xi −xj ∥2 > ε for all i ̸= j ∈ [N ].1 We claim that x1 , · · · , xN forms an ε-net
1
Such a set of points x1 , · · · , xN is called an ε/2-packing, but we will not formalize this notion here.

35
of K. Assuming that this is not the case, then there must exist y ∈ K such that d(xi , y) > ε for all
i ∈ [N ]. But then such a point y can be added to x1 , · · · , xN , and this violates the maximality of
the set x1 , · · · , xN . Consequently, this implies that N (K, ε) ≤ N .
So it remains to derive an upper bound on N . We consider the set of disjoint (ε/2)-radii ball
centered at each xi . All these balls lie inside K + (ε/2)B2n and they are disjoint. Therefore, by a
volume counting argument, we have

|(K + (ε/2)B2n )|
N≤ .
|(ε/2)B2n |

This proves the proposition.

As an immediate corollary, we derive the following covering number bounds for the Euclidean ball
w.r.t. the Euclidean norm, by simply calculate the bounds in Proposition 5.1.3.

Corollary 5.1.4 (Covering numbers of the Euclidean ball). For any ε > 0, we have
 1 n 2 n
≤ N (B2n , ε) ≤ +1 .
ε ε

Bounding Operator Norms on ε-Nets. The notion of ε-nets allow us to discretize infinite high
dimensional sets. Recall that the operator norm of a matrix A ∈ Rm×n is defined as

∥A∥ := sup ∥Ax∥2 .

x∈Sn−1

Thus, to evaluate ∥A∥ one needs to control ∥Ax∥2 uniformly over the entire sphere. It turns out
we just need to control it over an ε-net of Sn−1 .

Lemma 5.1.5 (Computing operator norm on a net). Let A ∈ Rm×n and ε ∈ [0, 1). Then for any
ε-net N of the sphere Sn−1 , we have
1
sup ∥Ax∥2 ≤ ∥A∥ ≤ · sup ∥Ax∥2 .
x∈N 1 − ε x∈N

Proof. The lower bound is trivial. For the upper bound, suppose x∗ ∈ Sn−1 maximizes ∥Ax∥2 over
the sphere. Let z ∈ N be the closest point in the net to x∗ , which satisfies ∥z − x∗ ∥2 ≤ ε. Then,

∥A∥ = ∥Ax∗ ∥2 ≤ ∥Az∥2 + ∥A(z − x∗ )∥2 ≤ ∥Az∥2 + ε · ∥A∥.

The upper bound can be obtained by rearranging the above.

Alternatively, the operator norm of a matrix A ∈ Rm×n can also be computed as the supremum of
a quadratic form:
∥A∥ = sup ⟨Ax, y⟩.
x∈Sn−1 ,y∈Sm−1

For symmetric matrices one can take x = y in the above formula. Similar to Lemma 5.1.5, one can
also control this quadratic form over ε-nets.

36
Lemma 5.1.6 (Quadratic form on nets). Let A ∈ Rm×n and ε ∈ [0, 1/2). Then for any ε-net N
of Sn−1 and any ε-net M of Sm−1 , we have
1
sup ⟨Ax, y⟩ ≤ ∥A∥ ≤ · sup ⟨Ax, y⟩.
x∈N ,y∈M 1 − 2ε x∈N ,y∈M
Moreover, if A is symmetric (and thus m = n), we have
1
sup |⟨Ax, x⟩| ≤ ∥A∥ ≤ · sup |⟨Ax, x⟩|.
x∈N 1 − 2ε x∈N

The proof of this lemma is left as a homework problem.

The ε-Net Argument. We now show an example of a simple ε-net argument to bound the
operator norm of a random matrix with independent subgaussian entries.
Theorem 5.1.7 (Norm of matrices with subgaussian entries). Let A be an m × n random matrix
whose entries Aij are independent, mean-zero, subgaussian random variables with ∥Aij ∥ψ2 ≤ 1.
Then for any t > 0, we have
 √ √ 
P ∥A∥ > C( m + n + t) ≤ 2 exp(−t2 ).
√ √
Equivalently, this means that ∥A∥ − C1 ( m + n) ψ2 ≤ C2 .

Proof. We break the proof into multiple steps.

Step 1: Approximation. Let ε = 1/4. By Corollary 5.1.4, we can choose an ε-net N for Sn−1
and M for Sm−1 of size
|N | ≤ 9n and |M| ≤ 9m .
Then Lemma 5.1.6 implies that
∥A∥ = sup ⟨Ax, y⟩ ≤ 2 sup ⟨Ax, y⟩.
x∈Sn−1 ,y∈Sm−1 x∈N ,y∈M

Step 2: Concentration. Fix x ∈ N and y ∈ M. Then the quadratic form

n X
X m
⟨Ax, y⟩ = Aij xi yj
i=1 j=1

is a sum of independent, subgaussian random variables. By Lemma 3.2.4 and ∥Aij ∥ ≤ 1, we have
n X
m n X
m
2
X X
⟨Ax, y⟩ ψ2
≤C ∥Aij xi yj ∥2ψ2 ≤ C x2i yj2 ≤ C,
i=1 j=1 i=1 j=1

where the last inequality uses that x and y are unit vectors. It follows from Lemma 3.1.1 that
P ⟨Ax, y⟩ ≥ u ≤ 2 exp(−cu2 ).


√ √
Step 3: Union Bound. We choose u = C( n + m + t) above, for large enough C. Since there
are at most 9m+n choices of x and y, we union bound over them to obtain
 
P max ⟨Ax, y⟩ ≥ u ≤ 9m+n · 2 exp(−cu2 ) ≤ 9m+n · 2 exp(−3(m + n) − t2 ≤ 2 exp(−t2 ).
x∈N ,y∈M

This completes the proof of the theorem.

37
We will see various strengthening of Theorem 5.1.7 below. The purpose of presenting the proof of
this weaker theorem is mainly to demonstrate a basic ε-net argument.

5.2 A Stronger ε-Net Argument

In this section, we prove a much stronger statement than Theorem 5.1.7, where we will relax the
independent entries assumption to just the independence of the rows of A, and also provide a
corresponding lower bound on the smallest singular value of A. We again use an ε-net argument,
but this time we do it more carefully than in the previous section.
Theorem 5.2.1 (Two-sided bound on subgaussian matrices). Let A be an m × n matrix whose
rows Ai are independent, mean-zero, 1-subgaussian, isotropic, random vectors in Rn , and t ≥ 0.
Then with probability at least 1 − 2 exp(−t2 ), we have

1 ⊤ r n t 
2
A A − In ≤ max(δ, δ ) where δ = C +√ . (5.1)
m m m
In particular, this implies that the singular values of A satisfy
√ √ √ √
m − C( n + t) ≤ sn (A) ≤ s1 (A) ≤ m + C( n + t).

Let us parse the guarantee of Theorem 5.2.1 as it may look scarier than what we have seen before.
1 ⊤
The guarantee in (5.1) states that m A A is an approximate isometry, in the sense that all its
singular values are within 1 ± δ for error δ ′ = max(δ, δ 2 ).
′

We will again only prove a special case of this theorem, where m = C1 n for a large enough constant
C1 , and the error is a constant. In particular, we prove with probability at least 1 − 2 exp(−C2 n),
1 ⊤
A A − In ≤ 0.1, (5.2)
m
which implies that the singular values of A all fall in [0.9m, 1.1m]. See the proof of Theorem 4.6.1
in Vershynin’s book for the proof of Theorem 5.2.1.

Proof of (5.2). We follow the same set of steps as in the previous section.

Step 1: Approximation. Find a 14 -net N of Sn−1 of cardinality |N | ≤ 9n . Using Lemma 5.1.6,

1 ⊤ D 1  E 1
A A − In ≤ 2 max A⊤ A − In x, x = 2 max ∥Ax∥22 − 1 .
m x∈N m x∈N m

Then to prove (5.2), all we need to show is

1
max ∥Ax∥22 − 1 ≤ 0.05.
x∈N m
Step 2: Concentration. Fix x ∈ N . We note that
m
X m
X
∥Ax∥22 = 2
⟨Ai , x⟩ =: Xi2 ,
i=1 i=1

38
where we define the random vector X ∈ Rm with independent coordinates Xi := ⟨Ai , x⟩. You may
already note that things look very similar to a concentration of norm. Indeed, since Ai is isotropic,

EXi2 = Ex⊤ Ai A⊤ ⊤
i x = Ex x = 1.

Moreover, Xi is O(1)-subgaussian for all i ∈ [m] as each Ai is 1-subgaussian. Consequently, we

may apply concentration of norm (either Theorem 4.1.1 or the weaker bound in (4.1)) to obtain
 1 
∥Ax∥22 − 1 ≤ 0.05 = P ∥X∥22 ∈ [0.95m, 1.05m] ≥ 1 − 2 exp(−cm).


P
m
Step 3: Union Bound. Now we can take a union bound over x ∈ N to obtain
 1 
P sup ∥Ax∥22 − 1 ≤ 0.05 ≥ 1 − 2 · 9n · exp(−cm).
x∈N m

By picking m = C1 n for large enough C1 , the bound above becomes 1 − 2 exp(−C2 n).

5.3 Application: Covariance Estimation of Gaussian Distribution

The result in Theorem 5.2.1 is very powerful. Let us give an application of it in this section to the
problem of estimating the covariance of a Gaussian distribution N (0, Σ), where Σ ∈ Rn×n is PSD.
Let us recall that a natural strategy is to choose i.i.d. samples X1 , · · · , Xm ∼ N (0, Σ), and use the
sample covariance
n
1 X
Σm := Xi Xi⊤
m
i=1

as an estimator of Σ. Using (5.2), we can bound the error of this estimation as follows.

Theorem 5.3.1 (Covariance estimation for Gaussians). Given i.i.d. samples X1 , · · · , Xm ∼

N (0, Σ) and m ≥ Cn, then
∥Σm − Σ∥ ≤ 0.1∥Σ∥
with probability at least 1 − 2 exp(−cn).

Proof. By applying the linear transformation Σ−1/2 to the vectors, we may assume wlog that
1 ⊤
Σ = In . Let A ∈ Rm×n be the matrix with rows X1 , · · · , Xm . Then Σm = m A A. Consequently,
we can directly use (5.2) to obtain the bound in the theorem statement.

We should point out that using Theorem 5.2.1 in its full generality, we can prove that
r n n
E∥Σm − Σ∥ ≤ C + · ∥Σ∥. (5.3)
m m

We may also obtain a tail bound on ∥Σm − Σ∥ from Theorem 5.2.1 if we like to. These bounds can
also be generalized to arbitrary subgaussian distributions. The details for these general bounds are
omitted. They can be found in Section 4.7 of Vershynin’s book.

39
Remark 5.3.2 (Sample complexity). The smallest number of samples to achieve certain error
guarantees for an estimation problem is called its sample complexity. This is a central concept and
question that has been studied extensively in different settings.
Theorem 5.3.1 states that the sample complexity for achieving constant error is linear, i.e. O(n).
It is easy to see that one needs at least n samples, just to guarantee that Σm has full rank. Conse-
quently, for estimating covariance of a Gaussian, we achieved the best possible result up to constant
factors. It is also worth noting that more generally, the statement in (5.3) shows that the sample
complexity for achieving ε (multiplicative) error is O(n/ε2 ).

Remark 5.3.3 (Low dimensional data). The result in Theorem 5.3.1 makes no assumption on
the data distribution beyond subgaussianity. Suppose we know ahead of time that the data lie on
an (approximately) r-dimensional subspace with r ≪ n. Can we achieve a much better sample
complexity (than linear in n) in this case?
It turns out that we can! In fact, O(r) samples suffice. We will see a result of this flavor after dis-
cussing matrix Bernstein inequality in Sections 5.7 and 5.10. The strengthening of Theorem 5.3.1
for approximate low-dimensional subgaussian distribution can be found in Theorem 9.2.4 of Ver-
shynin’s book, which requires more advanced tools than what we can cover in this course.

5.4 Classical Laws of Random Matrices

So far we have discussed the ε-net argument and upper bounds on the operator norm of random
matrices with independent subgaussian entries or rows, which are tight up to constant factors. In
this section and the next, we will discuss more accurate estimates on the spectrum for more specific
types of random matrices. Here we survey a set of classical laws for various random matrix models.
We remark that an important difference here is that these more accurate estimates are asymptotic
behaviors (i.e. the limiting behaviour when the dimension goes to infinity). In applications, we
often have to work in large (but finite) dimensions, which makes these laws not quite applicable.
They nevertheless provide useful insights into what we might hope for (just like CLT gives us insight
into a Gaussian tail which we then have developed a non-asymptotic theory for).

Wigner Semi-Circular Law. This law was named after the physicist Eugene Wigner who proved
it in 1955. Let Wn be an n × n symmetric random matrix whose entries on and above diagonal are
i.i.d. mean-zero, unit-variance random variables. Then as n → ∞, the empirical distribution (or
histogram) over the eigenvalues of √1n Wn converges to the “semi-circular density”:

1 p
ρsc (x) = 4 − x2 on [−2, 2].
2π
See Figure 5.2. We will prove this result via Stieltjes transformation method in the next section.

Marchenko-Pastur Law. This law was named after is named after mathematicians Volodymyr
1 Pm ⊤
Marchenko and Leonid Pastur who proved this result in 1967. Let Σm := m i=1 Xi Xi , where
Xi ∼ N (0, In ) be the sample covariance matrix of a standard Gaussian distribution. Then assuming
d, n → ∞ and n/m → r ∈ (0, 1) (i.e. the dimension and number of samples goes to infinity

40
 Figure 5.2: The Wigner semi-circular law for symmetric Wigner matrices.

proportionally), then the empirical distribution over the eigenvalues of Σm converges to the density
1 p
ρMP (x) = (x − a)(b − x) on [a, b],
2πrx
√ √
where a = (1 − r)2 and b = (1 + r)2 . See Figure 5.3 for an illustration.

Figure 5.3: The Marchenko-Pastur law for the empirical covariance of a standard Gaussian distribution.

Circular Law. The circular law was established in the 1960s by Jean Ginibre. Let A be an n × n
matrix with i.i.d. N (0, 1) entries (note the difference from Wigner matrices is there is no symmetry
here). Then as n → ∞, the empirical distribution of √1n A converges to the uniform density of the
unit disc (on the complex plane). See Figure 5.4 for an illustration.

Figure 5.4: The circular law for Ginibre emsembles.

The three laws above discuss the empricial distribution over the eigenvalues, but say nothing
about the extreme eigenvalues themselves. But there are another set of laws which talk about the
asymptotic bahaviour of extreme eivenvalues. We only mention one of them here as an example.

41
Bai-Yin Law. This law was proved by Zhi Dong Bai and Yong Quan Yin in 1988. It states
that for symmetric Wigner matrices (as in the semi-circular law), the operator norm satisfies
√ √
lim supn→∞ ∥Wn ∥/ n = 2. So the eigenvalues of Wn is almost surely (2 + o(1)) n asymptotically.

Universality Law. Finally, we mention the very fundamental law of universality, which states
(or emphasizes) that these laws above hold not only for Gaussian matrices, but for more general
mean-zero unit-variance distributions.

5.5 Tool 2: The Stieltjes Transformation Method

In this section, we introduce Stieltjes transformation and prove the Wigner semi-circular law. This
book (Section 2.4) by Terry Tao contains full details of this proof (and alternative proofs). Here,
we follow the presentation in Vershynin’s lecture notes.

Linear Algebraic Background. To describe the Stieltjes transformation method, let us first
recall a few standard facts about the trace of matrices.
Proposition 5.5.1 (Trace). Given matrix M ∈ Rn×n , its trace, defined as Tr(M ) = ni=1 Mii ,
P
satisfies the following properties:
Pn
(1) Sum of eigenvalues: Tr(M ) = i=1 λi (M ).

(2) Cyclic property: Tr(AB) = Tr(BA).

(3) Gaussian quadratic form: Tr(M ) = Eg ⊤ M g, where g ∼ N (0, 1).

We also use the following facts about the inverse of matrices.

Proposition 5.5.2 (Matrix inverse). The inverse of a matrix M ∈ Rn×n satisfies the following:
1
(1) λi (M ) = λi (M ) and λi (M − zIn ) = λi (M ) − z for any z ∈ R.

(2) Write matrix M in a block form (where a ∈ R, b ∈ Rn−1 , and D ∈ R(n−1)×(n−1) ):

a b⊤
 
M= .
b D
−1 1
Then M11 = a−b⊤ D−1 b
(assuming D is invertible).

The quantity in property (2) of Proposition 5.5.2 is also known as the Schur complement.

Stieltjes Transformation Observes Matrix Spectrum. Given a matrix A ∈ Rn×n with

eigenvalues λ1 , · · · , λn , let us consider the following function (for z ∈ C)
n
1 1X 1
fA (z) := Tr(A − zIn )−1 = , (5.4)
n n λi − z
i=1

where the last equality uses Propositions 5.5.1 and 5.5.2. This quantity is exactly the Stieltjes
transformation of the (discrete) uniform distribution over the eigenvalues λ1 , · · · , λn .

42
Definition 5.5.3 (Stieltjes transformation). The Stieltjes transformation of a r.v. X is given by
 1 
sX (z) := E , for all z ∈ C.
X −z

Let us first demonstrate this transformation with a few examples.

Example 5.5.4 (Stieltjes transformation). As examples of Stieltjes transformation:

1 Pn 1
(1) Let X ∼ Unif{λ1 , · · · , λn }, then sX (z) = n i=1 λi −z , which is exactly as in (5.4).
R ρ(x)
(2) If X is a continuous r.v. with PDF ρ(x), then sX (z) = x−z dx.

1
√
(3) For the semi-circular distribution, i.e. ρ(x) = ρsc (x) = 2π 4 − x2 on [−2, 2], we have
2
√ √
4 − x2 −z + z 2 − 4
Z
1
ssc (z) = dx = . (5.5)
2π −2 x−z 2

Let us try to prove (5.5) slightly later. We first need the following proposition.

Proposition 5.5.5 (Uniqueness of Stieltjes transformation). Stieltjes transformation sX (z) for all
z ∈ C uniquely determines the distribution of X. In particular, if X has PDF ρ(x), then we have

sX (z + iε) − sX (z − iε)
ρ(z) = lim .
ε→0+ 2πi
Proof of Proposition 5.5.5. We may write out the quantity inside the limit as

sX (x + iε) − sX (x − iε)
Z Z
1  p(x) p(x) 
= dx − dx
2πi 2πi x − (z + iε) x − (z − iε)
x − z + iε x − z − iε
Z Z
1  
= · p(x)dx − · p(x)dx
2πi ε2 + (x − z)2 ε2 + (x − z)2
Z
1 ε
= · p(x)dx
π ε + (x − z)2
2
Z
1 ε
= · p(x + z)dx.
π ε2 + x 2
ε
As ε → 0+ , the Poisson kernel π(ε2 +x2 )
converges to the Dirac delta function δ(x). Therefore,

sX (z + iε) − sX (z − iε)
Z
lim = δ(x)p(x + z)dx = p(z).
ε→0+ 2πi
This proves the proposition.

Proof of (5.5). Instead of computing the integration to prove (5.5), we cheat here and derive the
PDF corresponding to ssc (z) using Proposition 5.5.5 as follows.

sX (z + iε) − sX (z − iε)
ρ(z) = lim
ε→0+ 2πi

43
 p
p

− (z + iε) +(z + iε)2 − 4 − − (z − iε) + (z − iε)2 − 4
= lim
ε→0+ 4πi
p p
2 2
(z + iε) − 4 − (z − iε) − 4
= lim
ε→0 + 4πi
It looks on the surface that when ε → 0+ the two formula in the numerator becomes the same, so
the limit should be 0. But this is incorrect, as in the numerator we are taking the square root of a
complex function. In particular,

(z + iε)2 − 4 = (z 2 − 4 − ε2 ) + 2zεi.

When z > 2, note that z 2 − 4 − ε2 > 0 and thus the argument pof it is almost 0.
p Then, taking the
square root gives another argument close to 0. Consequently, (z + iε) 2 − 4− (z − iε)2 − 4 → 0
p
as ε → 0+ . When z < 2, the argument p of the complex
√ number (z + iε)2 − 4 is close to π.
Consequently, in this case, one has (z + iε) − 4 ≈ 4 − z 2 · i, and thus
2

p p
(z + iε)2 − 4 − (z − iε)2 − 4 1 p
lim = 4 − z2,
ε→0+ 4πi 2π
which is exactly ρsc (z). This proves the formula.

From (5.4) and (5.5), to prove the semi-circular law, all we have to do is to show that for the matrix
√1 Wn , the function value sn (z) := f √1
n Wn (z) → ssc (z) as n → ∞.
n

Computing the Stieltjes Transformation for Wigner Matrices. Let us compute sn (z) as
follows. For notational convenience, we denote W = Wn in this paragraph. Note that
n
1X  1
−1 
sn (z) = λi √ W − zI .
n n
i=1

Let us denote the matrix M := √1 W − zI. Then the above can be written as
n

n n
1X 1 1 X −1
sn (z) = λi (M −1 ) = · Tr(M −1 ) = Mii . (5.6)
n n n
i=1 i=1

So it remains to understand Mii−1 . Let us start with i = 1. We can write W and M as

"W #
W11 g ⊤ √11 − z √1 g ⊤
 
1 n n
W = and M = √ W − zI = .
g W n √1 g M
n

Then using (2) in Proposition 5.5.2, we have that

−1 1
M11 = −1 . (5.7)
W
√11
n
− z − n1 g ⊤ M g
W1
Let us inspect the formula in the denominator above. As n → ∞, we have √
n
→ 0. By concentra-
tion, we should expect
1 ⊤ −1 1  −1  1 −1
g M g ≈ E g ⊤ M g = Tr(M ).
n n n

44
Note that M has exactly the same form as M , but with one dimension lower! As n → ∞, this
difference in one dimension does not matter. Consequently, we have
1 ⊤ −1 1
g M g ≈ · Tr(M −1 ) = sn (z).
n n
Plug these into the formula into (5.7), we find that as n → ∞,

−1 1
M11 ≈ .
−z − sn (z)

The same formula actually holds for all Mii−1 , by applying the same permutation to the rows and
columns of M . Therefore, it follows from Equation (5.6) that
n
1 X −1 1
sn (z) = Mii ≈ .
n −z − sn (z)
i=1

Solving this quadratic formula, we obtain the solutions

√
−z ± z 2 − 4 2
sn (z) = =− √ .
2 z ± z2 − 4
To figure out which solution is the correct one, note that as z → ∞, we have

1 + o(1)
sn (z) = − .
z
Consequently, the correct branch of solution should be
√
2 −z + z 2 − 4
sn (z) = − √ = .
z + z2 − 4 2

This is the same as the Stieltjes transformation of the semi-circular distribution ρsc (x). By unique-
ness of Stieltjes transformation in Proposition 5.5.5, we conclude that the limit of the uniform
distribution over the eigenvalues of Wn is the semi-circular distribution.

5.6 Tool 3: The Moment Method

For the Stieltjes transformation method, one often needs to make clever observations to calculate
it, e.g., to prove the semi-circular law, one uses the recursive structure of Wigner matrices.
There is an alternative approach to the semi-circular law, called the moment method, that is more
straightforward and widely applicable. We only discuss the principles of this method in this section
and omit the details (which can be found in Section 2.3.4 and 2.4.2 of Terry Tao’s Book).
In the moment method, one looks at a different proxy of the spectrum of the matrix A:
n
1 1X k
Tr(Ak ) = λi .
n n
i=1

45
Thus the (average) trace moments of A corresponds to the moments of the uniform distribution
over {λ1 , · · · , λn }. One can perform a direct (combinatorial) computation for the trace moments
to prove that it converges to that of the semi-circular distribution. As the moments of a random
variable is also unique, this can again be used to establish the semi-circular law.
The moment method is a very general method for studying random matrices. It is often the most
straightforward way, but perhaps with some heavy calculations to compute the moments.

5.7 Tool 4: Matrix Concentration Inequalities

So far, we have been working with random matrices whose entries (at least the rows) are indepen-
dent. This is a very strong assumption and often does not hold in applications. In this section and
the next, we study more general models of random matrices and derive a powerful set of results,
known as matrix concentration inequalities.
Pn
Here, we will consider sums of independent random matrices of the form X = i=1 Xi , where
Xi ∈ R d×d are independent matrices. Let us start with the special case of Bernoulli series.

Theorem 5.7.1 (Matrix Hoeffding’s inequality). Let ε1 , · · · , εn be i.i.d. symmetric Bernoullis and
A1 , · · · , An be d × d symmetric random matrices. Then for any t ≥ 0,
n
 X  t2

P εi Ai ≥ t ≤ 2d · exp − 2 ,
2σ
i=1
Pn
where σ 2 := 2
i=1 Ai .

This theorem looks very similar to Hoeffding’s inequality given in Theorem 2.4.1, the
√ main difference
being the loss of a factor of d on the RHS. This factor of d only translates to a log d factor:
n
X p
E εi Ai ≤ Cσ log d.
i=1

Analogously, we also have the following matrix analog of Bernstein’s inequality (Theorem 2.9.1).

Theorem 5.7.2 (Matrix Bernstein’s inequality). Let X1 , · · · , Xn be independent, mean-zero, d × d

symmetric random matrices, such that each ∥Xi ∥ ≤ K a.s.. Then for every t ≥ 0, we have
n
 X  t2 /2

P Xi ≥ t ≤ 2d · exp − 2
,
2σ + Kt/3
i=1
Pn
where σ 2 := 2
i=1 EXi is the matrix variance.

We focus on the proof of Theorem 5.7.1 in these lecture notes, since the same proof strategies work
for Theorem 5.7.2. See Section 5.4 of Vershynin’s book for the proof of Theorem 5.7.2.

46
Remark 5.7.3 (Different proofs). There have been several different known (and simple) proofs of
these matrix concentration inequalities. For Theorem 5.7.1, we will see a proof, due to Tropp, using
Lieb’s trace inequality. Another proof of Theorem 5.7.1 based on the Golden-Thompson inequality
will be left as a homework problem.
There is an alternative approach to matrix concentration, known as the non-commutative Khint-
chine inequality, which is based on the moment method. This approach is historically earlier than
the approaches above. We will not present it here.

5.8 Background on Matrix Calculus

The similarity between matrix concentration inequalities and their scalar counterpart is not co-
incidental. The wisdom of matrix concentration inequalities is that one can essentially treat the
matrices as if they were scalars. We draw this comparison between matrices and scalars below.
Consider a symmetric matrix A ∈ Rd×d . To what extent does a matrix look like a number? Well,
when we add or subtract matrices they do act like numbers, but not so much when we multiple or
divide them. In particular, one of the biggest problems in terms of treating matrices as numbers
is that matrices don’t generally commute, i.e. AB ̸= BA. Moreover, while it is always possible to
compare numbers, e.g. a ≤ b, it is not clear how to do so for matrices.

Matrix Calculus. Matrix calculus give us a way to bypass these issues. In particular, we will
develop a set of tools to reason about “which matrix is larger”.
Let us consider a symmetric matrix A ∈ Rd×d with Peigenvalues λi and eigen vectors ui , i.e. A =
P d ⊤ . Recall that its A2 is given by A2 = d 2 u u⊤ and its inverse is given by A−1 =
λ u u
i i i λ
i=1 i i i
Pi=1
d −1 ⊤ . Following these calculations, for any polynomial p : R → R, we have
λ
i=1 i ui ui

d
X
p(A) = p(λi )ui u⊤
i .
i=1

Can we generalize these facts to other functions for matrices? It turns out we can.

Definition 5.8.1 (Functions of matrices). Consider function f : R → R and symmetric matrix

X ∈ Rd×d with spectrum decomposition X = di=1 λi ui u⊤
P
i . Then define

d
X
f (X) := f (λi )ui u⊤
i .
i=1

As an example, let us consider what eA means. By Definition 5.8.1, we have

d d
X X λ2i 1 2
eA := eλi ui u⊤ + · · · ui u⊤


i = 1 + λi + i =I +A+ A + ··· .
2! 2!
i=1 i=1

This is exactly the Taylor series when A is a scalar, matching our intuition of “treating matrices
like scalars”.

47
Löwner Order. Recall that A is PSD, iff u⊤ Au ≥ 0 for all u ∈ Rn , which is further equivalent to
eigenvalues of A being all non-negative.

Definition 5.8.2 (Löwner order). Given symmetric matrices A, B ∈ Rd×d , we denote A ⪰ 0 iff A
is PSD. We denote A ⪰ B iff A − B ⪰ 0. Similarly, we denote A ⪯ B iff B − A ⪰ 0.

Löwner order is a partial order on the set of d × d symmetric matrices. For example, the following
matrix is neither ⪰ 0 nor ⪯ 0:  
1 0
.
0 −1
We leave verifying the following properties as an exercise.

Proposition 5.8.3 (Properties of Löwner order). The Löwner order on d × d symmetric matrices
satisfy the following.

1. Reflexivity: X ⪯ X.

2. Antisymmetry: X ⪯ Y and Y ⪯ X implies X = Y .

3. Transitivity: X ⪯ Y and Y ⪯ Z implies X ⪯ Z.

Now we come back to the question of non-commutativity. Generally XY ̸= Y X, but they are equal
if X and Y are diagonalizable by the same orthogonal matrix, i.e.

X = Q⊤ ΛX Q and Y = Q⊤ ΛY Q.

This is because in this case XY = Q⊤ ΛX ΛY Q = Q⊤ ΛY ΛX Q. It turns out that this is also a

sufficient condition, i.e., XY = Y X iff they are simultaneously diagonalizable.
As we mentioned, non-commutativity causes problem in thinking about matrices as scalars, and
here is a simple example. It is obvious that if x, y ≥ 0 then xy ≥ 0. This is unfortunately not true
for non-commutative matrices: X ⪰ 0 and Y ⪰ 0 do not imply XY ≥ 0 in general, for the simple
reason that XY might not even be symmetric.
This problem can be avoided by multiplying the matrices on both sides. In particular, it is not
hard to verify that if X, Y ⪰ 0, then X 1/2 Y X 1/2 ⪰ 0. Also if X ⪰ Y , then A⊤ XA ⪰ A⊤ Y A for
any matrix A (with proper dimension).
Eigenvalues and Löwner Order. We have thus far discussed functions on matrices (which act
on eigenvalues) and a partial order on matrices. It’s time to bring these together. What does it
mean for the eigenvalues when A ⪰ B?

Proposition 5.8.4 (Eigenvalues and Löwner order). Let X, Y ∈ Rd×d be symmetric matrices. If
X ⪯ Y , then λi (X) ≤ λi (Y ) for all i ∈ [d], where λi (·) denotes the ith largest eigenvalue. The
converse is not true in general (but it holds for commutative matrices).

We leave the proof of this proposition as a homework problem. An important corollary of Propo-
sition 5.8.4 is the following trace monotonicity.

48
Corollary 5.8.5 (Trace monotonicity). Let X, Y ∈ Rd×d be symmetric matrices and f : R → R be
an increasing function. Then X ⪯ Y implies that Trf (X) ≤ Trf (Y ).

Proof. Note that f (X) has eigenvalues f (λ1 (X)), · · · , f (λd (X)). Thus,
d
X d
X d
X
Trf (X) = λi (f (X)) = f (λi (X)) ≥ f (λi (Y )) = Tr(f (Y )),
i=1 i=1 i=1

where the first inequality uses Proposition 5.8.4 together with the monotonicity of f .

Given this corollary, it is tempting to ask if the following stronger property holds: X ⪯ Y implies
f (X) ⪯ f (Y ) for monotonically increasing function f . Indeed, if this were true, then a monotone
function f would also be “monotone” under the Löwner order for matrices, which would achieve
our goal of “comparing matrices”.

Operator Monotonicity. Unfortunately, this stronger property holds for some monotone func-
tions, but not all of them. The functions that have this property are called operator monotone.

Definition 5.8.6 (Operator monotonicity). A function f : R → R is operator monotone increasing

if f (X) ⪯ f (Y ) whenever X ⪯ Y , for any symmetric matrices X, Y ∈ Rd×d . Operator monotone
decreasing is defined in a similar manner.
√
For example, the function f (x) = x is operator monotone increasing, but this is not the case
for f (x) = x2 or f (x) = ex (although they are all monotone functions). We leave these proofs as
homework.
More generally, we have the following characterization. This is not required for our study of matrix
concentration inequalities, but it is a nice tool to know.

Theorem 5.8.7 (Löwner-Heinz theorem). The function f (x) = xp is (1) not operator monotone
if |p| > 1, (2) operator monotone increasing when 0 ≤ p ≤ 1, (3) operator monotone decreasing if
−1 ≤ p ≤ 0.

Let us at least verify a simple case of this theorem: the case of p = −1 (matrix inverse).

Proposition 5.8.8 (Matrix inverse is operator monotone decreasing). If X, Y are symmetric in-
vertible matrices such that 0 ⪯ X ⪯ Y , then X −1 ⪰ Y −1 ⪰ 0.

Proof. Since X ⪯ Y , multiplying Y −1/2 on both sides give 0 ⪯ Y −1/2 XY −1/2 ⪯ I. This means that
the matrix Y −1/2 XY −1/2 have eigenvalues between (0, 1] (since it is also invertible, there cannot
be eigenvalue at 0). Consequently, the eigenvalues of (Y −1/2 XY −1/2 )−1 = Y 1/2 X −1 Y 1/2 are all at
least 1. Consequently, Y 1/2 X −1 Y 1/2 ⪰ I. Multiplying both sides by Y −1/2 gives X −1 ⪰ Y −1 .

In our proof of Theorem 5.7.1, we crucially rely on the operator monotonicity of log x.

Proposition 5.8.9 (log x is operator monotone increasing). If X, Y ∈ Rd×d are invertible sym-
metric matrices with 0 ⪯ X ⪯ Y , then log X ⪯ log Y .

49
Proof. We prove this proposition using the following scalar identity for all x > 0.
Z ∞
1 1

log x = − dt.
0 1+t x+t

Let us derive the corresponding formula for matrices. Note that

Z ∞
1 1

log λi = − dt.
0 1 + t λi + t
Pd ⊤
Thus given the spectral decomposition X = i=1 λi ui ui , we have
d Z d
∞X Z ∞
X 1 1
⊤ I 1

log X = (log λi )ui u⊤
i = − ui ui dt = − dt.
0 1 + t λi + t 0 1 + t X + tI
i=1 i=1

Now since X ⪯ Y , we have X +tI ⪯ Y +tI, which by Proposition 5.8.8 further implies (X +tI)−1 ⪰
(Y + tI)−1 . Plug this into the formula above shows that log X ⪯ log Y .

The following table summarizes a comparison between scalars and matrices.

Scalars (Symmetric) Matrices

0, 1 0, I
+, − +, −
×, ÷ Non-commutativity (AB ̸= BA): A1/2 BA1/2 and A−1/2 BA−1/2
|a| ∥A∥ (operator norm)
Function f (a) Matrix function f (A)
Comparison ≤ Löwner order A ⪯ B
Monotonicity of functions Operator monotonicity (only for some monotone functions),
trace monotonicity (for all monotone functions)
Random variables Random matrices

Table 5.1: Comparison between scalars and matrices. They look similar in many ways, but have
some crucial differences, e.g. non-commutativity, operator norms, monotonicity of functions.

5.9 Proof of Matrix Hoeffding’s Inequality

Now we have all the tools needed to prove Theorem 5.7.1, which we restate below.

Theorem 5.7.1 (Matrix Hoeffding’s inequality). Let ε1 , · · · , εn be i.i.d. symmetric Bernoullis and
A1 , · · · , An be d × d symmetric random matrices. Then for any t ≥ 0,
n
 X  t2

P εi Ai ≥ t ≤ 2d · exp − 2 ,
2σ
i=1
Pn
where σ 2 := 2
i=1 Ai .

50
 Pk
A First Attempt. Let us denote Sk := i=1 εi Ai . We prove the following one-sided tail bound

P(λmax (Sn ) ≥ t) ≤ d · exp(−t2 /2σ 2 ). (5.8)

The theorem then follows by replacing the matrices Ai by −Ai and applying a union bound. To
prove (5.8), we mimic the proof of Hoeffding’s inequality. For any λ > 0,

P(λmax (Sn ) ≥ t) = P eλ·λmax (Sn ) ≥ eλt ≤ e−λt · Eeλ·λmax (Sn )

= e−λt · λmax EeλSn ≤ e−λt · Tr EeλSn = e−λt · ETr exp(λSn ),

(5.9)

where the last inequality uses that EeλSn ⪯ 0, so its maximum eigenvalue is bounded by its sum
of eigenvalues (i.e., its trace). This replacement costs one at most a factor of d, but will be crucial
for our proof later on.
Now, ideally, we would like to follow exactly the same argument as in the scalar case:

(?)  Y 
Tr EeλSn = Tr Eeλεi Ai ,
i∈[n]

but this equality is unfortunately incorrect. In particular, for non-commutative matrices AB ̸= BA,
generally we have eA+B ̸= eA eB .

A Sprinkle of Magic. Nevertheless, the tools we introduced in Section 5.8 allow us to bypass
this issue. We follow the idea of Tropp that uses Lieb’s trace inequality here. In the homework,
you will see an alternative proof based on Golden-Thompson’s inequality.

Theorem 5.9.1 (Lieb’s trace inequality). Let H ∈ Rd×d be a symmetric matrix. Then the function

f (X) := Tr exp(H + log X)

is concave on the set of PSD matrices. Equivalently, this means that f (λX + (1 − λ)Y ) ≥ λf (X) +
(1 − λ)f (Y ) for all X, Y ⪰ 0 and λ ∈ [0, 1].

For scalar x > 0, note that f (x) = eH x is linear (so also concave). But for general matrix X, it is
not always true that f (X) = eH X (unless H and X commute).
For random matrix X ⪰ 0, applying Jensen’s inequality (Ef (X) ≤ f (EX) for concave f ) to
Theorem 5.9.1 gives
ETr exp(H + log X) ≤ Tr exp(H + log EX).
Substituting X = eZ (i.e., Z = log X) gives that for any (not necessarily PSD) random matrix Z,

ETr exp(H + Z) ≤ Tr exp H + log EeZ .

(5.10)

As an immediate corollary, we obtain the following bound for the RHS of (5.9).

Corollary 5.9.2. Let X1 , · · · , Xn be independent symmetric random matrices. Then,

n
X n
X 
log EeXi .


ETr exp Xi ≤ Tr exp
i=1 i=1

51
 Pn
Proof. Denote Sn := i=1 Xi . Then we can write

ETr exp(Sn ) = ETr exp(Sn−1 + Xn ) ≤ ETr exp Sn−1 + log EeXn ,

where the last inequality uses (5.10). Then recursively opening up Sn−1 proves the corollary.

We are now ready to finish the proof of matrix Hoeffding’s inequality.

Proof of Theorem 5.7.1. Applying Corollary 5.9.2 to the RHS of (5.9) gives
n
X 
ETr exp(λSn ) ≤ Tr exp log Eeλεi Ai .
i=1

Recall when proving Hoeffding’s inequality, we have previously shown that for scalar ai ,
1 1 2 2
E exp(λεi ai ) = eλai + e−λai ≤ eλ ai /2 .
2 2
Since functions act on matrix eigenvalues, we also have

E exp(λεi Ai ) ⪯ exp(λ2 A2i /2).

By the operator monotonicity of the function log in Proposition 5.8.9, we have

n n
X
λεi Ai λ2 X 2
log Ee ⪯ Ai .
2
i=1 i=1

Taking Tr exp(·) on both sides above and use trace monotonicity in Corollary 5.8.5, we get
n
 λ2 X   n
 λ2 X 
ETr exp(λSn ) ≤ Tr exp A2i ≤ d · λmax exp A2i = d exp(λ2 σ 2 /2).
2 2
i=1 i=1

Plug this into (5.9) gives the following bound

P(λmax (Sn ) ≥ t) ≤ d exp(−λt + λ2 σ 2 /2).

The bound on the RHS should look familiar because it is essentially the same as the scalar case up
to the factor of d in front. Finally optimizing λ = t/σ 2 gives the desired bound of

t2

P(λmax (Sn ) ≥ t) ≤ d exp − .
2σ 2
This completes the proof of the matrix Hoeffding’s inequality.

5.10 Application: Covariance Estimation for Approximately Low

Dimensional Distributions

In this section, we give an application of matrix concentration inequalities to covariance estimation

for approximately low dimensional data. We use matrix Bernstein’s inequality, restated below.

52
Theorem 5.7.2 (Matrix Bernstein’s inequality). Let X1 , · · · , Xn be independent, mean-zero, d × d
symmetric random matrices, such that each ∥Xi ∥ ≤ K a.s.. Then for every t ≥ 0, we have
n
 X  t2 /2

P Xi ≥ t ≤ 2d · exp − 2
,
2σ + Kt/3
i=1
Pn
where σ 2 := 2
i=1 EXi is the matrix variance.

We actually only need the following corollary, which can be obtained by a tail integration.

Corollary 5.10.1 (Matrix Bernstein inequality, expectation). Let X1 , · · · , Xn be independent,

mean-zero, d × d symmetric random matrices, such that each ∥Xi ∥ ≤ K a.s.. Then,
n
X p
E Xi ≲ σ 1 + log d + K(1 + log d),
i=1
Pn
where σ 2 := 2
i=1 EXi is the matrix variance.

Approximately Low Dimensional Distribution. Before formalizing the application, let us first
discuss what it means for a distribution to be approximately low dimensional. Let X be a random
vector with covariance matrix Σ. Of course, if X is distributed on an r-dimensional subspace, then
Σ will have rank r.
But generally, it is too wishful (and not robust) to expect a distribution to be exactly lying on
an r-dimensional subspace. In many applications, the distribution of X will be of full rank, but
in many directions the distribution might be very small. In these cases, the notion of intrinsic
dimension captures the low dimensional structures of a distribution.

Definition 5.10.2 (Intrinsic dimension). Given a random vector X with covariance Σ ∈ Rd×d , its
intrinsic dimension is defined as r(Σ) := tr(Σ)/∥Σ∥.

We prove the following covariance estimation bound for approximately low dimensional data.

Theorem 5.10.3 (Covariance estimation for approximately low dimensional data). Let X ∈ Rd
be a random vector whose covariance matrix Σ has intrinsic dimension r. Assume that

∥X∥2 ≤ K(E∥X∥22 )1/2 almost surely

for some constant K > 0. Then for any m ≥ 0, we have for some constant C (depending on c),
r
 K 2 r log d K 2 r log d 
E∥Σm − Σ∥ ≤ C + · ∥Σ∥.
m m

This theorem is considerably stronger than the previous Theorem 5.3.1 in two ways. First of all,
it does not assume that the distribution is subgaussian. Moreover, to achieve error ε, the number
of samples needed is m ≍ r log d/ε2 . This sample complexity is now nearly linear in the intrinsic
dimension r, which can be much smaller than d.

53
Proof of Theorem 5.10.3. Note that E∥X∥22 = Tr(Σ), thus the assumption can be rewritten as

∥X∥22 ≤ K 2 Tr(Σ) almost surely. (5.11)

1 Pm ⊤
Since Σm − Σ = m i=1 (Xi Xi − Σ) is a sum of i.i.d. mean-zero random matrices, Corollary 5.10.1
implies that
1 p

E∥Σm − Σ∥ ≲ σ log n + M log n ,
m
where σ 2 and M are such that
m
X
σ2 = E(Xi Xi⊤ − Σ)2 = m E(XX ⊤ − Σ)2
i=1
∥XX ⊤ − Σ∥ ≤ M almost surely.

Let us first bound σ 2 as follows. Note that

E(XX ⊤ − Σ)2 = E(XX ⊤ )2 − Σ2 ⪯ E(XX ⊤ )2 .

From here, the assumption in (5.11) gives

(XX ⊤ )2 = ∥X∥22 · XX ⊤ ≤ K 2 Tr(Σ) · XX ⊤ .

Consequently, we obtain that

σ 2 ≤ m E(XX ⊤ )2 ≤ K 2 mTr(Σ)∥Σ∥.

M can be bounded similarly as

∥XX ⊤ − Σ∥ ≤ ∥X∥22 + ∥Σ∥ ≤ K 2 Tr(Σ) + ∥Σ∥ ≤ 2K 2 Tr(Σ) =: M.

Plug the bounds on σ 2 and M into the above gives

1 p 2 
E∥Σm − Σ∥ ≲ K mTr(Σ)∥Σ∥ log d + 2K 2 Tr(Σ) log d
m
1 p 2 
= K mr∥Σ∥2 log d + 2K 2 r∥Σ∥ log d
mr
 K 2 r log d 2K 2 r log d 
= + · ∥Σ∥.
m m
This completes the proof of the theorem.

5.11 Tool 5: The Stochastic Process Method

Pn d×d
Let us recall the setting of matrix concentration inequalities: X = i=1 Xi , where Xi ∈ R
are independent, mean-zero, symmetric random matrices. In matrix concentration inequalities, we
have tried to work with the matrices as if they were scalars and developed tools to bypass the issue
of non-commutativity.

54
But here is a rather different, and arguably more fundamental, view of the problem of understanding
the operator norm of the symmetric random matrix X (let’s just focus on its expectation):

E∥X∥ = E sup v ⊤ Xv =: E sup Xv ,

v∈B2d v∈B2d

where Xv := v ⊤ Xv is a random variable. The collection of random variables (Xv )v∈B d is called a
2
stochastic process.

Definition 5.11.1 (Stochastic process). A stochastic process is a collection of random variables

(Xt )t∈T on the same probability space, which are indexed by elements t of some set T .

This definition by itself might seem too general to be useful. Nonetheless, the general view from
stochastic process allows us to build a different set of tools which might shed new light into the
study of random matrix theory. This is the topic of the next chapter.

55
Chapter 6

Stochastic Processes

We start our exploration of stochastic processes in this chapter. Our goal of this chapter and the
next is to understand the supremum of a stochastic process (Xt )t∈T :

E sup Xt .
t∈T

We focus on (sub)gaussian processes, where the increments of the random variables (Xt )t∈T are all
(sub)gaussian. The study of these stochastic processes allow us to apply a geometric view towards
probability. We follow the presentation in Chapter 7 and 8 of Vershynin’s book.

6.1 Basic Concepts

As an example, a random vector X ∈ Rn can be viewed as a stochastic process with T = {1, · · · , n}.
In more complicated examples, such as random walks or a Brownian motion, T represents time
and Xt might be the position of an object at time t. In these cases, although one can in principle
view a stochastic process as a (possibly infinite) dimensional vector, but the progression with time
might be more crucial to understand the process.

Covariance and Increments. Let us focus on a mean-zero stochastic process, i.e., EXt = 0 for
all t ∈ T . The covariance function of the process is defined as

Σ(t, s) := Cov(Xt , Xs ) = EXt Xs , ∀t, s ∈ T.

Similarly, we also define the increments of the random process as

1/2
d(t, s) := ∥Xt − Xs ∥L2 = E(Xt − Xs )2 , ∀t, s ∈ T.

Obviously, the covariance and increments can be represented by each other together (by using the
variance E[Xt2 ]).

Gaussian Processes. An important family of stochastic processes is called Gaussian processes.

56
Definition 6.1.1 (Gaussian processes). A stochastic process (Xt )t∈T is called a Gaussian process
if for any finite T0 ⊂ T , the random vector (Xt )t∈T0 has a Gaussian
P distribution. Equivalently,
(Xt )t∈T is a Gaussian process if every finite linear combination t∈T0 at Xt is a Gaussian r.v..

In the same way that the covariance determines a mean-zero Gaussian distribution, covariance (or
increments) uniquely determines a Gaussian process.

Definition 6.1.2 (Canonical Gaussian process). Let T ⊂ Rn . Consider a standard Gaussian vector
g ∼ N (0, In ) and define the stochastic process Xt := ⟨g, t⟩ for all t ∈ T . Then (Xt )t∈T is a Gaussian
process, called canonical Gaussian process, with increments given by the Euclidean distance:

∥Xt − Xs ∥L2 = ∥t − s∥2 , for all t, s ∈ T.

It turns out that any Gaussian process can be realized as a canonical Gaussian process. This follows
from the following lemma (by taking the dimension to infinity).

Lemma 6.1.3 (Canonical Gaussian process is universal). Let Y ∈ Rn be a mean-zero Gaussian

random vector. Then there exists points t1 , · · · , tn ∈ Rn such that

Y ∼ (⟨g, ti ⟩)ni=1 , where g ∼ N (0, In ).

Proof. Let Σ = Cov(Y ), then it is easy to see that Y ∼ Σ1/2 g (since same covariance).

This notion of canonical Gaussian process brings together probability and geometry. In particular,
any Gaussian process is uniquely determined by its covariance or increments, which is then uniquely
determined by the Euclidean geometry of the index set for its corresponding canonical realization.

6.2 Gaussian Comparison Inequalities

In this section, we introduce the powerful tool of Gaussian comparison inequalities. In particular,
if the increments of a Gaussian process is bounded by another, then its supremum is also bounded
by the supremum of the other Gaussian process. We first state a weaker form of this result.

Theorem 6.2.1 (Slepian’s inequality). Let (Xt )t∈T and (Yt )t∈T be two mean-zero Gaussian pro-
cesses. Assume that for all t, s ∈ T , we have

EXt2 = EYt2 and E(Xt − Xs )2 ≤ E(Yt − Ys )2 .

Then supt∈T Xt is stochastically dominated by supt∈T Yt , i.e. for all τ ∈ R,

   
P sup Xt ≥ τ ≤ P sup Yt ≥ τ .
t∈T t∈T

In particular, this implies that E supt∈T Xt ≤ E supt∈T Yt .

The proof of the theorem uses a powerful technique called Gaussian interpolation.

57
Gaussian Interpolation. Wlog assume that T is finite and say T = [n]. The idea is to define a
Gaussian random vector Z(u) that continuously interpolates between X and Y as
√ √
Z(u) := uX + 1 − uY.

Note that Z(0) = Y and Z(1) = X. As long as one can show that P(maxi Z(u)i < τ ) monotonically
increases, then we are immediately done because P(maxi Z(1)i < τ ) ≥ P(maxi Z(0)i < τ ). Gaussian
interpolation provides a machinery to show such a monotonicity.

Lemma 6.2.2 (Gaussian integration by parts). Let X ∼ N (0, σ 2 ). Then for any differentiable
function f : R → R we have
σ 2 E[f ′ (X)] = E[Xf (X)].

Proof. Let p(x) = √ 1 exp(−x2 /2σ 2 ) be the density of X. We can write the LHS out as
2πσ 2
Z Z Z
1 1
E[f ′ (X)] = f ′ (x)p(x)dx = − f (x)p′ (x) = xf (x)p(x)dx = E[Xf (X)].
R R σ2 R σ2

The preceding lemma can be generalized quite naturally to higher dimensions.

Lemma 6.2.3 (Multivariate Gaussian integration by parts). Let X ∼ N (0, Σ), Then for any
differentiable function f : Rn → R we have

Σ · E[∇f (X)] = E[Xf (X)].

Equivalently, for all entry i ∈ [n], we have

n
X  ∂f 
Σij E (X) = E[Xi f (X)].
∂xj
j=1

This more general lemma can be proved in essentially the same way as the above (but with more
involved calculations). We leave it as an exercise to verify it.

Lemma 6.2.4 (Gaussian interpolation). Consider two independent Gaussian random vectors X ∼
N (0, ΣX ) and Y ∼ N (0, ΣY ). Define the interpolation Gaussian vector
√ √
Z(u) := uX + 1 − uY, u ∈ [0, 1].

Then for any twice-differentiable function f : Rn → R, we have

n h ∂2f
d 1 X X i
E[f (Z(u))] = (Σij − ΣYij )E (Z(u)) .
du 2 ∂xi ∂xj
i,j=1

Proof. We can compute the LHS as

n n
d X ∂f dZi 1 X ∂f X
i Yi 
E[f (Z(u))] = E (Z(u)) · = E (Z(u)) · √ − √ .
du ∂xi du 2 ∂xi u 1 − u
i=1 i=1

58
Let us first consider the term for Xi . We condition on Y and compute
n n
1 X ∂f 1 X
√ EXi (Z(u)) = √ EXi gi (X),
u ∂xi u
i=1 i=1
∂f √ √
where we define the function gi (X) := ∂xi ( uX + 1 − uY ). Using Lemma 6.2.3, we obtain
n n
X ∂gi X ∂2f √
EXi gi (X) = ΣX
ij E (X) = ΣX
ij E (Z(u)) · u.
∂xj ∂xi ∂xj
j=1 j=1

Summing this up over i ∈ [n] gives that

n n
1 X ∂f X ∂2f
√ EXi (Z(u)) = ΣX
ij E (Z(u)).
u ∂xi ∂xi ∂xj
i=1 i,j=1

The second term (for Y ) can be computed similarly. We omit the details.

Proof of Slepian’s Inequality. We first prove a functional form of Slepian’s inequality, and then
deduce Theorem 6.2.1 from it.
Lemma 6.2.5 (Slepian’s inequality, functional form). Let X, Y ∈ Rn be two mean-zero Gaussian
random vectors. Assume that for all i, j ∈ [n], we have
EXi2 = EYi2 and E(Xi − Xj )2 ≤ E(Yi − Yj )2 .
Then for any twice differentiable function f : Rn → R such that
∂2f
≥0 for all i ̸= j.
∂xi ∂xj
Then we have E[f (X)] ≥ E[f (Y )].
√ √
Proof. Define Z(u) := uX + 1 − uY for u ∈ [0, 1]. Then Lemma 6.2.4 gives
n h ∂2f
d 1 X X i
E[f (Z(u))] = (Σij − ΣYij )E (Z(u)) .
du 2 ∂xi ∂xj
i,j=1

Note that ΣX Y X Y
ii = Σii and for i ̸= j Σij ≥ Σij . Correspondingly, each term in the summation above is
non-negative. Thus E[f (Z(u))] is monotonically non-decreasing, and thus E[f (X)] = E[f (Z(1))] ≥
E[f (Z(0))] = E[f (Y )]. This proves the lemma.

Now we are ready to prove Slepian’s inequality, which is restated below.

Theorem 6.2.1 (Slepian’s inequality). Let (Xt )t∈T and (Yt )t∈T be two mean-zero Gaussian pro-
cesses. Assume that for all t, s ∈ T , we have
EXt2 = EYt2 and E(Xt − Xs )2 ≤ E(Yt − Ys )2 .
Then supt∈T Xt is stochastically dominated by supt∈T Yt , i.e. for all τ ∈ R,
   
P sup Xt ≥ τ ≤ P sup Yt ≥ τ .
t∈T t∈T

In particular, this implies that E supt∈T Xt ≤ E supt∈T Yt .

59
Proof of Theorem 6.2.1. Assume wlog that T = [n]. Let us consider the function
Y
f (X) = 1(max Xi < τ ) = 1(Xi < τ ).
i∈[n]
i∈[n]

Note that this function satisfies that P(maxi Xi < τ ) = Ef (X). Thus to prove the statement of
the theorem, it suffices to show that E[f (X)] ≥ E[f (Y )]. This looks exactly like the conclusion of
Lemma 6.2.5, except for the technical issue that the function f as defined is not twice differentiable.
Nonetheless, since we can approximate 1(x < τ ) as a limit of aQ
sequence of smooth non-increasing
non-negative functions, i.e. 1(x < τ ) ≈ h(x), we have f (x) ≈ i∈[n] h(xi ). A possible choice of h
is given below (picture taken from Vershynin’s book).

Since h is non-negative and non-increasing, for any i ̸= j, under the above approximation,

∂2f  Y 
≈ h(xk ) h′ (xi )h′ (xj ) ≥ 0.
∂xi ∂xj
k̸=i,j

Then using Lemma 6.2.5 proves the theorem.

It turns out that to derive an expectation inequality, one can further remove the equal variance
assumption in Theorem 6.2.1, thus making it a more flexible tool to use.

Theorem 6.2.6 (Sudakov-Fernique’s inequality). Let (Xt )t∈T and (Yt )t∈T be two mean-zero Gaus-
sian processes. Assume that for all t, s ∈ T , we have

E(Xt − Xs )2 ≤ E(Yt − Ys )2 .

Then,
E sup Xt ≤ E sup Yt .
t∈T t∈T

We remark that it is unfortunately not possible to show a tail comparison inequality (as in Theo-
rem 6.2.1) under this weaker set of conditions.
The proof of Theorem 6.2.6 can also be proved using Gaussian interpolation, but in a more careful
way. We leave its proof as a homework problem.

60
6.3 Application: Sharp Bounds on Gaussian Matrices

We give an application of Gaussian comparison inequalities to random matrix theory, as promised

at the end of the previous chapter. This will wrap up our discussion of random matrix theory.
We revisit the independence entry model from Section 5.1. Recall that in Theorem 5.2.1, we showed
√ √
that given a matrix A ∈ Rm×n with independent subgaussian entries, then E∥A∥ ≤ m + C n.
Here, we show a sharp bound when A has i.i.d. standard Gaussian entries.
Theorem 6.3.1 (Gaussian random matrices). Let A ∈ Rm×n have i.i.d. N (0, 1) entries. Then
√ √
E∥A∥ ≤ m + n.

Proof. Let us view E∥A∥ as the supremum of a Gaussian process as follows:

E∥A∥ = sup ⟨Au, v⟩ = max Xuv ,

u∈Sn−1 ,v∈Sm−1 (u,v)∈T

where T = Sn−1 × Sm−1 and Xuv = ⟨Au, v⟩ ∼ N (0, 1).

Now we would like to apply Sudakov-Fernique (Theorem 6.2.6) to compare Xuv with a different
Gaussian process Yuv . To do so, we need to bound the increments of (Xuv )(u,v)∈T . Since Aij ’s are
i.i.d. standard Gaussians, for any (u, v), (w, z) ∈ T , we have
X 2
E(Xuv − Xwz )2 = E(⟨Au, v⟩ − ⟨Aw, z⟩)2 = E Aij (ui vj − wi zj )
i,j
X
= (ui vj − wi zj ) = ∥uv − wz ⊤ ∥2F = ∥u(v − z)⊤ − (w − u)z ⊤ ∥2F
2 ⊤

i,j

⊤

= Tr u(v − z)⊤ − (w − u)z ⊤ u(v − z)⊤ − (w − u)z ⊤
= ∥v − z∥22 + ∥w − u∥22 − 2(w − u)⊤ u(v − z)⊤ z
= ∥v − z∥22 + ∥w − u∥22 − 2(w⊤ u − 1)(v ⊤ z − 1)
≤ ∥v − z∥22 + ∥w − u∥22 ,

where the last inequality follows because w⊤ u ≤ 1 and z ⊤ v ≤ 1, since all of them are unit vectors.
Now we define our comparison Gaussian process (Yuv )(u,v)∈T as

Yuv := ⟨g, u⟩ + ⟨h, v⟩, (u, v) ∈ T,

where g ∼ N (0, In ) and h ∼ N (0, Im ) are independent standard Gaussian vectors. Then

2
E(Yuv − Ywz )2 = E ⟨g, u − w⟩ + ⟨h, v − z⟩
= E⟨g, u − w⟩2 + E⟨h, v − z⟩2
= ∥v − z∥22 + ∥w − u∥22 ≥ E(Xuv − Xwz )2 .

Consequently, Sudakov-Fernique Theorem 6.2.6 implies that

E∥A∥ = E sup Xuv ≤ E sup Yuv

(u,v)∈T (u,v)∈T

61
 =E sup ⟨g, u⟩ + ⟨h, v⟩
u∈Sn−1 ,v∈Sm−1

= E∥g∥2 + E∥h∥2
√ √
≤ (E∥g∥22 )1/2 + (E∥h∥22 )1/2 ≤ m+ n,

where the last line uses Jensen’s inequality. This completes the proof of the theorem.

6.4 Sudakov Minorzation

In previous sections, we discussed comparison between Gaussian processes. Starting from this
section, we begin our study of the supremum of Gaussian processes.
Recall that given a mean-zero Gaussian process (Xt )t∈T , the increments

d(t, s) := ∥Xt − Xs ∥L2 = (E(Xt − Xs )2 )1/2 (6.1)

defines a metric on the index set T . We call this metric space the canonical metric. In particular, for
a canonical Gaussian process (⟨g, t⟩)t∈T for T ⊂ Rn , then d(t, s) is exactly the Euclidean distance
on T . Further recall that the canonical metric d uniquely determines the Gaussian process (since
the covariance matrix uniquely determines a mean-zero Gaussian random vector).
Given the correspondence of Gaussian processes and the underlying metric space (T, d), it is a
natural and fundamental question to ask:

Can we evaluate the supremum of the process (Xt )t∈T in terms of the geometry of (T, d)?

We aim at answering this question throughout the rest of this chapter.

Let us recall from Definition 5.1.2 that for a metric space (T, d) and scale ε > 0, the covering number
N (T, d, ε) is the smallest cardinality of an ε net of T in metric d. The logarithm of covering number
(in base 2), i.e. log N (T, d, ε), is usually called the metric entropy of T .

Theorem 6.4.1 (Sudakov’s minorization inequality). Let (Xt )t∈T be a mean-zero Gaussian process.
Then for any ε > 0, we have p
E sup Xt ≥ cε log N (T, d, ε),
t∈T

where d is the canonical metric define in (6.1).

Since every Gaussian process can be realized as a canonical Gaussian process on a set T ⊂ Rn ,
and the canonical metric becomes the Euclidean metric in this case, we can reformulate Sudakov’s
minorization inequality as follows.

Corollary 6.4.2 (Sudakov’s minorization inequality). Let T ⊂ Rn . Then for any ε > 0, we have
p
E sup⟨g, t⟩ ≥ cε log N (T, ε).
t∈T

62
Proof of Theorem 6.4.1. We prove Sudakov’s minorization inequality using Sudakov-Fernique. De-
note N := N (T, d, ε) (we may assume it is finite, as otherwise E supt∈T Xt is also infinite). Let N
be a maximal ε-separated subset of T . Then N is an ε-net of T and thus |N | ≥ N .
Our goal is to establish p
E sup Xt ≥ cε log N ,
t∈N

which implies the theorem as the LHS above is a trivial lower bound for E supt∈T Xt . We prove the
above by defining a simpler Gaussian process (Yt )t∈N as
ε
Yt = √ gt ,
2
where gt are i.i.d. standard Gaussian random variables. Note that
ε ε
2
E(Yt − Ys )2 = E √ gt − √ gs = ε2 ≤ E(Xt − Xs )2 .
2 2
Consequently, Sudakov-Fernique Theorem 6.2.6 implies that
ε p
E sup Xt ≥ E sup Yt = E max gt ≥ cε log N .
t∈N t∈N 2 t∈N

This completes the proof of the theorem.

Application to Covering Numbers of Polytopes. Let us give an application of Sudakov’s

minorization inequality to bounding the covering numbers of polytopes, a question we discussed
back in Section 1.5. Recall that there we used the approximate Caratheodory theorem to prove the
following covering number estimates.

Theorem 6.4.3 (Covering numbers of polytopes with few vertices). Let P ⊂ Rd be a polytope with
2
N vertices and diam(P ) ≤ 1, and ε ∈ (0, 1). Then N (P, ε) ≤ N C/ε .

Proof. Assume wlog that P ⊆ B2d . Denote x1 , · · · , xN the vertices of P . Then by Corollary 6.4.2,
p p
cε log N (P, ε) ≤ E sup⟨g, t⟩ = E sup⟨g, xi ⟩ ≤ C log N .
t∈P i≤N

This implies the theorem.

6.5 Gaussian Width: A Geometric Measure

As hinted by the application to covering numbers, the quantity E supt∈T ⟨g, t⟩ contains important
geometric information about the set T ⊂ Rn . This quantity is called its Gaussian width.

Definition 6.5.1 (Gaussian width). The Gaussian width of a subset T ⊂ Rn is defined as

w(T ) := E sup⟨g, x⟩ where g ∼ N (0, In ).

x∈T

63
Gaussian width is one of the basic geometric quantities associated with subsets T ⊂ Rn , alongside
volume, surface area, etc. There are a few (almost) equivalent variants of Gaussian width:

1/2
E sup |⟨g, x⟩|, E sup⟨g, x⟩2 , E sup ⟨g, x − y⟩.
x∈T x∈T x,y∈T

These are the Gaussian complexity, squared version of Gaussian width, and the Gaussian width of
T − T . You will see some of these in the homework and Section 7.6 of Vershynin’s book.
Proposition 6.5.2 (Properties of Gaussian width). Gaussian width has the following properties:

(a) w(T ) is finite iff T is bounded.

(b) Gaussian width is invariant under affine unitary transformations, i.e., for any unitary matrix
U and any vector y, we have
w(U T + y) = w(T ).

(c) Gaussian width is invariant under taking convex hulls, i.e. w(conv(T )) = w(T ).

(d) Gaussian width respects Minkowski sum and scaling, i.e., for T, S ⊂ Rn and a ∈ R, we have

w(T + S) = w(T ) + w(S) and w(aT ) = |a|w(T ).

(e) We have w(T ) = 12 w(T − T ) = 1

2 supx,y∈T ⟨g, x − y⟩.
√
√1 n
(f ) We have 2π
· diam(T ) ≤ w(T ) ≤ 2 · diam(T ).

Proof. (a)-(d) are straightforward. For (e), note that

1
1
1
w(T ) = w(T ) + w(T ) = w(T ) − w(T ) = w(T − T ).
2 2 2
For (f), for the LHS, let x, y ∈ T be such that ∥x − y∥2 = diam(T ). Then
1 1

w(T ) = w(T − T ) ≥ max ⟨y − x, g⟩ + ⟨x − y, g⟩
2 2
1 1
= |⟨x − y, g⟩| = √ · diam(T ),
2 2π
where the last equality is because ⟨x − y, g⟩ ∼ N (0, ∥x − y∥2 ). To prove the RHS, note that

w(T − T ) = E sup ⟨g, x − y⟩ ≤ E sup ∥g∥2 · ∥x − y∥2

x,y∈T x,y∈T
√
≤ diam(T ) · E∥g∥2 ≤ diam(T ) · (E∥g∥22 )1/2 = n · diam(T ).

This proves the theorem.

Geometric Meaning of Gaussian Width. Gaussian width w(T ) is closely related to the geo-
metric width of the set T . The geometric width of T in the direction of a unit vector θ ∈ Sn−1 is
given by supx,y∈T ⟨θ, x − y⟩ (see Figure 6.1). The average of geometric width over unit directions
θ ∈ Sn−1 is called its spherical width.

64
 Figure 6.1: The geometric width of a set T ⊂ Rn in the direction of a unit vector θ.

Definition 6.5.3 (Spherical width). The spherical width (or mean width) of T ⊂ Rn is defined as
ws (T ) := E sup⟨θ, x⟩ where θ ∼ Unif(Sn−1 ).
x∈T

√
Since we have concentration of norm for g ∼ N (0, In ), the Gaussian width is approximately a n
scaling of the spherical width.
Lemma 6.5.4 (Gaussian vs. spherical width). We have
√ √
( n − C)ws (T ) ≤ w(T ) ≤ nws (T ).
Proof. We write g = ∥g∥2 · θ, where note that ∥g∥2 and θ ∈ Sn−1 are independent. Consequently,
w(T ) = E sup⟨g, t⟩ = E∥g∥2 · ws (T ).
t∈T
√ √
The lemma then follows as n − C ≤ E∥g∥2 ≤ n.

6.6 Examples of Gaussian Width

We calculate the Gaussian width for some examples.

√
1. B2n and Sn−1 (Euclidean ball and sphere): w(B2n ) = w(Sn−1 ) = E∥g∥2 = n ± C.
Pn q
n (unit cube): w(B n ) = E 2
2. B∞ ∞ i=1 |gi | = π · n.
√
3. B1n (ℓ1 ball): w(B1n ) = E∥g∥∞ = E maxi≤n |gi | ≍ log n.

From these examples, we see a different behavior for B1n from B2n and B∞ n , analogous to what we

have seen before. Let us summarize their differences, for the scaled version of these balls: B∞ n ,
√ n √ n √
nB2 and nB1 , all of which have diameter n.
√
1. Volume (or mass distribution): The volume of nB2n and B∞ n are both 2Θ(n) , while the
√ n  q
log n
 n
volume of nB1 is n . Recall Milman’s ellipsoid intuition from Figure 1.1, that ℓ1
q
balls have very tiny “cores” of radius logn n of their radii and 2n long “spikes”.

65
 √ n n are O(√n),
2. Spherical width (or Gaussian width): the
√ spherical widths of both nB 2 and B ∞
√
but the spherical width of nB1n is O( log n). Spherical width is determined by the “core”
of the volume, which has a similar behavior to the volume or mas distribution.

3. Subgaussian constant. The subgaussian constants of B∞ n , √nB n , and √nB n are all O(1).
√ 2 1
This might be counter-intuitive since we argued above that nB1n has volume much smaller
than B∞ n and √nB n . But recall that subgaussian constant is not really determined by the
2
“core” – it is mostly determined by the “spikes”. In the coordinate directions, the long spikes
√
of nB2n blows up its subgaussian constant.

66
Chapter 7

The Chaining Method

Recall that in the previous chapter, Sudakov’s minorization inequality gives a lower bound of the
supremum of a Gaussian process in terms of its covering numbers. In this chapter, we derive an
upper bound using a powerful and generic technique known as chaining.

7.1 Union Bound and the ε-Net Argument

Consider a Gaussian process (Xt )t∈T . For simplicity, let’s even think of it as a canonical Gaussian
process for T ⊂ Rn , i.e. Xt = ⟨g, t⟩, with 0 ∈ T . We will develop the theory of chaining in much
larger generality without these assumptions, but for now, it is helpful to keep them in mind for
intuitions. Our goal is to bound E supt∈T Xt .

The Union Bound. If the set T is finite with radius rad(T ), then each Xt is a Gaussian random
variable with variance at most rad(T )2 . Consequently, union bound over all t ∈ T gives
p
E sup Xt ≲ rad(T ) log |T |.
t∈T

ε-Net Argument. Of course, it is often the case that T is not finite (recall the operator norm of a
Gaussian random matrix is supx∈Sn−1 ,y∈Sm−1 ⟨Ax, y⟩). In these cases, we cannot union bound over
an infinite number of events. A standard trick (that we have seen before) is the ε-net argument.
Recall the idea is to pick an ε-net of N of T in the canonical distance d(t, s) = (E(Xt − Xs )2 )1/2
(which is just the Euclidean distance for canonical Gaussian processes). For each t ∈ T , let π(t) ∈ N
be the closest point in the net from t. Then we may write


E sup Xt = E sup (Xt − Xπ(t) ) + Xπ(t)
t∈T t∈T
p
≤ E sup Xt + E sup(Xt − Xπ(t) ) ≲ rad(T ) log |N | + E sup(Xt − Xπ(t) ),
t∈N t∈T t∈T

where in the last inequality we used the union bound over the finite number of points t ∈ N .
While we generally don’t have an explicit formula for the second term E supt∈T (Xt − Xπ(t) ), the
observation is that it is on a much smaller scale as d(t, π(t)) ≤ ε.

67
In some cases, we have much better control over the second term, e.g., for the operator norm of a
Gaussian random matrix, for ε nets N of Sn−1 and M of Sm−1 , we have
1
sup ⟨Ax, y⟩ ≤ sup ⟨Ax, y⟩.
x∈Sn−1 ,y∈Sm−1 1 − 2ε x∈N ,y∈M
In these cases, the ε-net is a reasonable strategy to “discretize” the infinite index set T .

Limitations of ε-net Arguments. But as we will see in later examples, ε-net arguments are
sometimes too course to give a precise estimate of the supremum of Gaussian processes. The
problem is that this argument only uses the size of an ε-net and requires that the net points to be
on roughly the same distance from the origin (as otherwise the estimation on those net points are
pessimistic), and it does not leverage the more fine-grained geometric structure of T . The method
of chaining that we will develop below is aimed at bypassing this issue.

7.2 Dudley’s Inequality

We work with the more general setting of subgaussian processes.

Definition 7.2.1 (Subgaussian increments). Consider a random process (Xt )t∈T on a metric space
(T, d). We say that the process has subgaussian increments if there exists K ≥ 0 such that
∥Xt − Xs ∥ψ2 ≤ Kd(t, s) for all t, s ∈ T.

It is easy to see that any Gaussian process is a subgaussian process with K = O(1). This is because
Xt − Xs is a mean-zero Gaussian with standard deviation d(t, s).
Dudley’s (entropy integral) inequality gives an upper bound for the expected supremum of any
subgaussian processes in terms of the metric entropy log N (T, d, ε).
Theorem 7.2.2 (Dudley’s integral inequality). Let (Xt )t∈T be a mean-zero stochastic process on
a metric space (T, d) with subgaussian increments with parameter K > 0. Then
Z ∞p
E sup Xt ≤ CK log N (T, d, ε)dε.
t∈T 0

The following Figure 7.1 compares the upper bound in Dudley’s integral inequality (Theorem 7.2.2)
and the lower bound in Sudakov’s minorization inequality (Theorem 6.4.1). The main difference is
that Dudley’s bound is multi-scale and this is also reflected in the proof.
One can discretize Dudley’s integral inequality to obtain the following version of Dudley’s bound
(it is not hard to verify that the two versions are equivalent up to constant factors).
Theorem 7.2.3 (Discrete Dudley’s inequality). Let (Xt )t∈T be a mean-zero stochastic process on
a matric space (T, d) with subgaussian increments with parameter K > 0. Then
X q
−k
E sup Xt ≤ CK 2 log N (T, d, 2−k ).
t∈T k∈Z

For the proof of this theorem and related discussion, we refer to Section 8.1 in Vershynin’s book.

68
Figure 7.1: Comparison between Dudley’s inequality and Sudakov’s minorization inequality. Pic-
ture from Vershynin’s book.

69