1 6 7 A Simple Proof Of Gaussian Concentration

A) Deriving the Concentration Bound (1.9) from Pisier-Maurey inequality (1.10)

1. Conditionally on $Z_1$, the random variable $\langle \nabla F(Z_1) , Z_2 \rangle$ has a Gaussian distribution, as a linear combination of Gaussian random variables. To fully characterise it, one needs to compute its expectation and variance, using the independence of $Z_1$ and $Z_2$:

(1)

\begin{align} \mathbb{E} [\langle \nabla F(Z_1) , Z_2 \rangle | Z_1] = \langle \nabla F(Z_1), \mathbb{E} [Z_2 | Z_1] \rangle = 0 \end{align}

(2)

\begin{align} \mathrm{var} [\langle \nabla F(Z_1) , Z_2 \rangle | Z_1] = (\nabla F(Z_1))^\top \mathrm{var} [Z_2 | Z_1] \, \nabla F(Z_1) = \| \nabla F(Z_1) \|^2 \end{align}

Consequently, the distribution of the random variable $\langle \nabla F(Z_1) , Z_2 \rangle$ conditionally on $Z_1$ is the Gaussian $\mathcal{N}(0, \| \nabla F(Z_1) \|^2)$ distribution.

2. Let us define for $s \geq 0$ and $t \in \mathbb{R}$: $\varphi_s (t) = \exp (st)$ which is convex. We can apply the Pisier-Maurey inequality (1.10) to $\varphi_s$:

(3)

\begin{aligned} \mathbb{E} \left[ \exp \left(s(F(Z) - \mathbb{E} [F(Z)] )\right) \right] &\leq \mathbb{E} \left[ \exp \left( s \frac{\pi}{2} \langle \nabla F(Z_1) , Z_2 \rangle \right) \right] \\ &\leq \mathbb{E} \left[ \mathbb{E} \left[ \exp \left( s \frac{\pi}{2} \langle \nabla F(Z_1) , Z_2 \rangle \right) \Bigm| Z_1 \right] \right] \end{aligned}

We know the formula for the moment-generating function of a Gaussian $\mathcal{N}(0, \sigma^2)$ random variable: for $\lambda \geq 0$, $\mathbb{E} [ \exp (\lambda Z)] = \exp(\frac{\lambda^2 \sigma^2}{2})$, so we apply it on $\langle \nabla F(Z_1) , Z_2 \rangle$ conditionally on $Z_1$ and for $\lambda = s \frac{\pi}{2}$ to prove that:

(4)

\begin{align} \mathbb{E} \left[ \exp \left(s(F(Z) - \mathbb{E} [F(Z)] )\right) \right] \leq \mathbb{E} \left[ \exp \left( (s \pi \| \nabla F(Z_1) \|)^2 / 8 \right) \right] \end{align}

Therefore, since

(5)

\begin{align} \| \nabla F(Z_1) \| \leq 1 \end{align}

we have that:

(6)

\begin{align} \exp \left( (s \pi \| \nabla F(Z_1) \|)^2 / 8 \right) \leq \mathrm{e}^{( s \pi)^2 / 8} \end{align}

and then taking the expectation:

(7)

\begin{align} \mathbb{E} \left[ \exp \left( (s \pi \| \nabla F(Z_1) \|)^2 / 8 \right) \right] \leq \mathrm{e}^{(s \pi)^2 / 8} \end{align}

3. Chernoff lemma writes for all $t \geq 0$:

(8)

\begin{align} \mathbb{P} [ F(Z) - \mathbb{E} [ F(Z) ] \geq t] \leq \exp (- \Lambda^*(t)) \leq \exp (- \tilde{\Lambda}(t)) \end{align}

where the second inequality comes from last question and

(9)

\begin{align} \tilde{\Lambda}(t) = \max_{s \geq 0} \left\{ st - \frac{(s \pi)^2}{8} \right\} = \frac{2 t^2}{\pi^2} \end{align}

by a simple derivative calculation.

B) Proof of Pisier-Maurey Inequality (1.10)

1. Using the derivability of $F \circ W: [0, \frac{\pi}{2}] \rightarrow \mathbb{R}$ and the chain rule we have:

(10)

\begin{aligned} F(Z_1) - F(Z_2) &= F(W \left(\frac{\pi}{2} \right)) - F(W(0)) \\ &= \int_0^{\pi/2} (F \circ W)' (\theta) \, d\theta \\ &= \int_0^{\pi/2} \langle \nabla F(W(\theta)) , W'(\theta) \rangle \, d\theta \end{aligned}

2. In what follows, the very definition of the operators of the form $\mathbb{E}_X$ where $X$ is a random variable rely strongly on the independence of the considered variables.

First inequality: By Jensen inequality, we have:

(11)

\begin{align} \varphi(\mathbb{E}_{Z_2} [ F(Z_1) - F(Z_2) ]) \leq \mathbb{E}_{Z_2} [ \varphi(F(Z_1) - F(Z_2)) ] \end{align}

from which we deduce the first inequality, taking $\mathbb{E}_{Z_1}$ on both sides and the fact that

(12)

\begin{align} F(Z_1) - \mathbb{E}_{Z_2} [ F(Z_2) ]= \mathbb{E}_{Z_2} [ F(Z_1) - F(Z_2) ] \end{align}

Second inequality: We showed before that if $T \sim \mathcal{U} ([0, \frac{\pi}{2}])$ is independent from $(Z_1, Z_2)$ then:

(13)

\begin{align} F(Z_1) - F(Z_2) = \mathbb{E}_T \left[ \frac{\pi}{2} \langle \nabla F(W(T)) , W'(T) \rangle \right] \end{align}

Thus, again by Jensen inequality:

(14)

\begin{align} \varphi(F(Z_1) - F(Z_2)) \leq \mathbb{E}_T \left[ \varphi \left(\frac{\pi}{2} \langle \nabla F(W(T)) , W'(T) \rangle \right) \right] \end{align}

We deduce the second inequality by taking $\mathbb{E}_{Z_1 Z_2}$ and exchanging the integrals using Fubini's theorem.

3. Let us fix $\theta \in [0, \frac{\pi}{2}]$ for now. Then the random variables

(15)

\begin{aligned} W(\theta) &= Z_1 \sin(\theta) + Z_2 \cos(\theta) \\ W'(\theta) &= Z_1 \cos(\theta) - Z_2 \sin(\theta) \end{aligned}

have Gaussian distributions, as linear combinations of Gaussian random variables. Moreover, from the moments of $(Z_1, Z_2)$ we deduce:

(16)

\begin{aligned} \mathbb{E} [W(\theta)] &= \mathbb{E} [W'(\theta)] = 0 \\ \mathrm{var} [W(\theta)] &= \mathrm{var} [W'(\theta)] = (\cos^2 \theta + \sin^2 \theta) I_d = I_d \\ \mathrm{cov} (W(\theta), W'(\theta)) &= \sin \theta \cos \theta \, I_d + (\cos^2 \theta - \sin^2 \theta) \, \mathrm{cov} (Z_1, Z_2) - \sin \theta \cos \theta \, I_d = 0_d \end{aligned}

so $(W(\theta), W'(\theta))$ are two independent Gaussian $\mathcal{N} (0, I_d)$ random variables, i.e.:

(17)

\begin{align} (W(\theta), W'(\theta)) \sim (Z_1, Z_2) \end{align}

The conclusion of the proofs comes from previous question's inequality and the following equalities in expectations:

(18)

\begin{aligned} \mathbb{E}_{Z_1}\left[\varphi\left(F\left(Z_1\right)-\mathbb{E}_{Z_2}\left[F\left(Z_2\right)\right]\right)\right] &= \mathbb{E} \left[\varphi\left(F\left(Z\right)-\mathbb{E} \left[F\left(Z\right)\right]\right)\right] \\ \frac{2}{\pi} \int_0^{\pi / 2} \mathbb{E}_{Z_1, Z_2}\left[\varphi\left(\frac{\pi}{2}\left\langle\nabla F(W(\theta)), W^{\prime}(\theta)\right\rangle\right)\right] d \theta &= \frac{2}{\pi} \int_0^{\pi / 2} \mathbb{E}_{Z_1, Z_2}\left[\varphi\left(\frac{\pi}{2}\left\langle\nabla F(Z_1), Z_2\right\rangle\right)\right] d \theta \\ &= \mathbb{E} \left[\varphi\left(\frac{\pi}{2}\left\langle\nabla F(Z_1), Z_2\right\rangle\right)\right] \end{aligned}