7.1 Concentration of measure for sub-gaussian random variables

Sub-Gaussian distributions have a close relationship to the concentration of measure phenomenon [link] . To illustrate this, we note that we can combine Lemma 2 and Theorem 1 from "Sub-Gaussian random variables" to obtain deviation bounds for weighted sums of sub-Gaussian random variables. For our purposes, however, it will be more enlightening to study the norm of a vector of sub-Gaussian random variables. In particular, if $X$ is a vector where each $X_i$ is i.i.d. with $X_i\sim \mathrm{Sub}\left(c\right)$ , then we would like to know how ${\parallel X\parallel }_2$ deviates from its mean.

In order to establish the result, we will make use of Markov's inequality for nonnegative random variables.

(markov's inequality)

For any nonnegative random variable $X$ and $t>0$ ,

Let $f\left(x\right)$ denote the probability density function for $X$ .

In addition, we will require the following bound on the exponential moment of a sub-Gaussian random variable.

Suppose $X\sim \mathrm{Sub}\left(c^2\right)$ . Then

for any $\lambda \in [0,1)$ .

First, observe that if $\lambda =0$ , then the lemma holds trivially. Thus, suppose that $\lambda \in (0,1)$ . Let $f\left(x\right)$ denote the probability density function for $X$ . Since $X$ is sub-Gaussian, we have by definition that

for any $t\in \mathbb{R}$ . If we multiply by $exp(-c^2{t}^2/2\lambda )$ , then we obtain

Now, integrating both sides with respect to $t$ , we obtain

which reduces to

This simplifies to prove the lemma.

We now state our main theorem, which generalizes the results of [link] and uses substantially the same proof technique.

Suppose that $X=[X_1,X_2,...,X_M]$ , where each $X_i$ is i.i.d. with $X_i\sim \mathrm{Sub}\left(c^2\right)$ and $\mathbb{E}\left(X_i^2\right)={\sigma }^2$ . Then

Moreover, for any $\alpha \in (0,1)$ and for any $\beta \in [c^2/{\sigma }^2,{\beta }_{\max }]$ , there exists a constant ${\kappa }^{*}\ge 4$ depending only on ${\beta }_{\max }$ and the ratio ${\sigma }^2/c^2$ such that

and

Since the $X_i$ are independent, we obtain

and hence [link] holds. We now turn to [link] and [link] . Let us first consider [link] . We begin by applying Markov's inequality:

Since $X_i\sim \mathrm{Sub}\left(c^2\right)$ , we have from [link] that

Thus,

and hence

By setting the derivative to zero and solving for $\lambda$ , one can show that the optimal $\lambda$ is

Plugging this in we obtain

Similarly,

In order to combine and simplify these inequalities, note that if we define

then we have that for any $\gamma \in [0,{\beta }_{\max }{\sigma }^2/c]$ we have the bound

and hence

By setting $\gamma =\alpha {\sigma }^2/c^2$ , [link] reduces to yield [link] . Similarly, setting $\gamma =\beta {\sigma }^2/c^2$ establishes [link] .

This result tells us that given a vector with entries drawn according to a sub-Gaussian distribution, we can expect the norm of the vector to concentrate around its expected value of $M{\sigma }^2$ with exponentially high probability as $M$ grows. Note, however, that the range of allowable choices for $\beta$ in [link] is limited to $\beta \ge c^2/{\sigma }^2\ge 1$ . Thus, for a general sub-Gaussian distribution, we may be unable to achieve an arbitrarily tight concentration. However, recall that for strictly sub-Gaussian distributions we have that $c^2={\sigma }^2$ , in which there is no such restriction. Moreover, for strictly sub-Gaussian distributions we also have the following useful corollary. [link] exploits the strictness in the strictly sub-Gaussian distribution twice — first to ensure that $\beta \in (1,2]$ is an admissible range for $\beta$ and then to simplify the computation of ${\kappa }^{*}$ . One could easily establish a different version of this corollary for non-strictly sub-Gaussian vectors but for which we consider a more restricted range of $ϵ$ provided that $c^2/{\sigma }^2<2$ . However, since most of the distributions of interest in this thesis are indeed strictly sub-Gaussian, we do not pursue this route. Note also that if one is interested in very small $ϵ$ , then there is considerable room for improvement in the constant $C^{*}$ .

Suppose that $X=[X_1,X_2,...,X_M]$ , where each $X_i$ is i.i.d. with $X_i\sim \mathrm{SSub}\left({\sigma }^2\right)$ . Then

and for any $ϵ>0$ ,

with ${\kappa }^{*}=2/(1-log\left(2\right))\approx 6.52$ .

Since each $X_i\sim \mathrm{SSub}\left({\sigma }^2\right)$ , we have that $X_i\sim \mathrm{Sub}\left({\sigma }^2\right)$ and $\mathbb{E}\left(X_i^2\right)={\sigma }^2$ , in which case we may apply [link] with $\alpha =1-ϵ$ and $\beta =1+ϵ$ . This allows us to simplify and combine the bounds in [link] and [link] to obtain [link] . The value of ${\kappa }^{*}$ follows from the observation that $1+ϵ\le 2$ so that we can set ${\beta }_{\max }=2$ .

Finally, from [link] we also have the following additional useful corollary. This result generalizes the main results of [link] to the broader family of general strictly sub-Gaussian distributions via a much simpler proof.

Suppose that $\Phi$ is an $M\times N$ matrix whose entries ${\phi }_{ij}$ are i.i.d. with ${\phi }_{ij}\sim \mathrm{SSub}(1/M)$ . Let $Y=\Phi x$ for $x\in {\mathbb{R}}^N$ . Then for any $ϵ>0$ , and any $x\in {\mathbb{R}}^N$ ,

and

with ${\kappa }^{*}=2/(1-log\left(2\right))\approx 6.52$ .

Let ${\phi }_i$ denote the $i^{\mathrm{th}}$ row of $\Phi$ . Observe that if $Y_i$ denotes the first element of $Y$ , then $Y_i=⟨{\phi }_i,x⟩$ , and thus by Lemma 2 from "Sub-Gaussian random variables" , $Y_i\sim \mathrm{SSub}\left({\parallel x\parallel }_2^2,/,M\right)$ . Applying [link] to the $M$ -dimensional random vector $Y$ , we obtain [link] .