concentration inequality for magnitude of standard gaussian random vector

Important

This tells us that, with high probability, we have

\begin{align} \lvert \lvert x \rvert \rvert {#2} &= d + {\cal O}(\sqrt{ d }) \\ \implies \lvert \lvert x \rvert \rvert &= \sqrt{ d + {\cal O}(\sqrt{ d }) } \\ &= \sqrt{ d } \cdot \sqrt{ 1+ {\cal O}\left( \frac{1}{\sqrt{ d }} \right)} \\ &= \sqrt{ d }\left( 1+{\cal O}\left( \frac{1}{\sqrt{ d }} \right) \right) \\ &= \sqrt{ d } + {\cal O}(1) \end{align}

ie, the standard gaussian random vector falls close to the spherical shell of width $O (1)$ around the sphere of radius $\sqrt{d}$ .

Proof

Note

This proof uses the Chernoff Method, which is used to prove concentration inequalities like the Chebyshev, Hoeffding, Bernstein, Azuma-Hoeffding, and McDiarmid. It is a more general form of a "nonlinear Markov" inequality

Proof

We deal with only one side of the distribution; the desired inequality is achieved by simply multiplying by 2 to account for the other tail.

Note that $E [x_{i}^{2}] = 1$ , so define $s_{i} = x_{i}^{2} - 1$ . Then

\begin{aligned} P [\sum_{i = 1}^{d} x_{i}^{2} - d \geq t] & = P [\sum_{i - 1}^{d} s_{i} \geq t] \\ = P [\exp (λ \sum_{i = 1}^{d} s_{i}) \geq \exp (λ t)] \\ (*) & \leq \frac{E [\exp (λ \sum s_{i})]}{\exp (λ t)} \\ (* *) & = \frac{E [\exp (λ s_{1})]^{d}}{\exp (λ t)} \\ = \exp (- λ t + d \log (E [\exp (λ s_{1})])) \end{aligned}

Where

$(*)$ is from Markov's Inequality
$(* *)$ is because the $x_{i}$ are independent

Now, define

ψ (λ) := \log (E [\exp (λ s_{1})]) = \log (E [\exp (λ (x_{1}^{2} - 1))])

As the cumulant generating function (wikipedia) of $x_{1}^{2} - 1$ (which has expectation 0). Note that $E [\exp (λ x_{1}^{2})]$ is finite if and only if $λ < \frac{1}{2}$ and in this case

\begin{aligned} E [\exp (λ x_{1}^{2})] & = \frac{1}{\sqrt{1 - 2 λ}} \\ ⟹ ψ (λ) & = - λ + \frac{1}{2} \log (\frac{1}{1 - 2 λ}) \\ (†) & = λ^{2} + O (λ) \end{aligned}

Where we get $(†)$ via Taylor expansion. This yields the bound $ψ (λ) \leq 2 λ^{2}$ for $λ \leq \frac{1}{4}$

Exercise (tedious) - Verify the bound

Can plot $ψ (λ)$ and the bound $2 λ^{2}$ (see notes page 6; figure 1.1)
Verify via algebra that $ψ (λ) \leq 2 λ^{2}$ for all $λ \leq \frac{1}{4}$

Assuming $λ \leq \frac{1}{4}$ , we have

\begin{aligned} P [\sum_{i = 1}^{d} x_{i}^{2} - d \geq t] & \leq \exp (- λ t + d \log (E [\exp (λ s_{1})])) \\ = \exp (- λ t + d ψ (λ)) \\ \leq \exp (- λ t + 2 d λ^{2}) \end{aligned}

Now, $2 d λ^{2} - λ t$ is a convex quadratic function of $λ$ , and is thus minimized at $λ^{*} = \frac{t}{4 d}$ . We want to set $λ = λ^{*}$ , but we must ensure that $λ \leq \frac{1}{4}$ to maintain our desired bound. Thus, we have 2 cases:

If $t \leq d$ , then $λ^{*} \leq \frac{1}{4}$ and we can safely set $λ = λ^{*}$ .

P [\sum_{i = 1}^{d} x_{i}^{2} - d \geq t] \leq \exp (- λ t + 2 d λ^{2}) = \exp (- \frac{t^{2}}{4 d})

If $t \geq d$ , then $\frac{t}{4 d} ≰ \frac{1}{4}$ , so we instead set $λ = \frac{1}{4}$ .

P [\sum_{i = 1}^{d} x_{i}^{2} - d \geq t] \leq \exp (- λ t + 2 d λ^{2}) = \exp (- \frac{t}{4} + \frac{d}{8}) \leq \exp (- \frac{t}{8})

Which is the desired result

\begin{matrix} ◼ \end{matrix}

Remarks

Note

The important part of the proof is finding some $ψ (λ) = O (λ^{2})$ for a bounded $λ$ . This means that the random variance is subexponential (a weaker version of being subgaussian).

This result is characteristic of sums of $d$ iid subexponential random variables. Sums of this type have "Gaussian tails" scaled by $\exp (- \frac{c t^{2}}{d})$ up to a cutoff of $t \sim d$ , after which they have "exponential tails" scaled by $\exp (- c t)$

Bernstein's inequality is general tool for expressing this type of behavior (see notes pg. 7 for more + reference)

concentration inequality for magnitude of standard gaussian random vector

Statement

Proof

Remarks

Similar Results on the Way

References

See Also

Mentions