Concentration of Lipschitz functionals of Gaussian vector

From ProofWiki
Jump to: navigation, search

Statement

Let $X_{1},...,X_{n}$ be iid N(0,1) and $F:\mathbb{R}^{n}\to \mathbb{R}$ be L-Lipschitz then$$\mathbb{P}[|F(X)-\mathbb{E}[F(X)]|>Lu]\leq exp\{-\frac{u^{2}}{2C}\}.$$


Proof ( The Pisier-Maurey approach)

The goal will be to control bound the Laplace transform $\mathbb{E}[exp\{\lambda(f(X)-\mathbb{E}[f(X)]) \}]\leq exp\{C\frac{(\lambda L)^{2}}{2}\}$. Then by Chernoff's bound $$ \mathbb{P}[|F(X)-\mathbb{E}[F(X)]|>Lu]\leq \inf_{\lambda\geq 0}exp(-\lambda Lu+C\frac{(\lambda L)^{2}}{2})$$ is minimized for $\lambda=\frac{u}{LC}$.

Consider another Gaussian n-vector Y independent of X. Then by Jensen's inequality $$\mathbb{E}[exp\{\lambda(f(X)-\mathbb{E}[f(X)]) \}]\leq \mathbb{E}[exp\{\lambda(f(X)-f(Y)) \}].$$ Next we will estimate the difference $f(X)-f(Y)$. Consider $$X_{\theta}:=cos(\frac{\pi}{2}\theta)X+sin(\frac{\pi}{2}\theta)Y$$ then $$\frac{\pi}{2}Z_{\theta}:=\frac{\partial}{\partial \theta}X_{\theta}=-\frac{\pi}{2}sin(\frac{\pi}{2}\theta)X+\frac{\pi}{2}cos(\frac{\pi}{2}\theta)Y.$$ Because $Cov(\frac{\pi}{2}Z_{\theta},X_{\theta})=0$ we have that $\frac{\pi}{2}Z_{\theta}, X_{\theta}$ are independent. By FTC we have $$f(X)-f(Y)=\int_{0}^{1} \frac{\partial}{\partial \theta} f(X_{\theta})d\theta=\int_{0}^{1} \frac{\pi}{2}Z_{\theta}\cdot\nabla f(X_{\theta})d\theta.$$ By Jensen's we find the bound $$\int_{0}^{1}\mathbb{E}[exp\{\lambda( \frac{\pi}{2}Z_{\theta}\cdot\nabla f(X_{\theta}) ) \}]d\theta.$$ For $v\in \mathbb{R}^{n}$ we have $$\mathbb{E}[exp\{\lambda( \frac{\pi}{2}Z_{\theta}\cdot v) ) \}]=e^{\frac{|v|^{2}}{2}}. $$ Therefore, by independence of $\frac{\pi}{2}Z_{\theta}, X_{\theta}$ we find $$\int_{0}^{1}\mathbb{E}[exp\{\frac{(\lambda \pi/2)^{2}}{2} |\nabla f(X_{\theta}) |^{2} \}]d\theta.$$ By the Lipschitz bound we find the bound $$exp\{\frac{(\lambda \pi/2)^{2}}{2} L^{2} \}. $$



Proof ( The smart path approach)

Proof ( The stochastic calculus approach)

We will need some preparatory lemmas first.

Lemma 1: Let X and Y be independent k-dimensional vectors of centered, unit variance, independent Gaussian variables. If $f,g: \mathbb{R}^{k}\to \mathbb{R}$ are bounded $C^{2}$ functions then $$Cov(f(X),g(X))=\int_{0}^{1}\mathbb{E}[\left \langle \nabla f(X), \nabla g(aX+\sqrt{1-a^{2}}Y) \right \rangle ]da.$$

Proof of lemma 1: Due to the linearity of the statement and approximation results for $C^{2}$, we will prove it for $f(x):=e^{it\cdot x},g(x):=e^{is\cdot x}$. Therefore, $$Cov(f(X),g(X))=\phi(s+t)-\phi(s)\phi(t),$$ where $\phi(t):=e^{\frac{|t|^{2}}{2}}$. On the other hand, we start from the lhs to get the same answer. We have \begin{align} \mathbb{E}[\left \langle \nabla f(X), \nabla g(aX+\sqrt{1-a^{2}}Y) \right \rangle] =&\mathbb{E}[\left \langle (f(X)it_{l})_{l\leq k}, (g(aX+\sqrt{1-a^{2}}Y)ias_{l})_{l\leq k} \right \rangle]\\ =&-at\cdot s\mathbb{E}[f(X)g(aX+\sqrt{1-a^{2}}Y)]\\ =&-at\cdot s\mathbb{E}[exp\{ i(t\cdot X+s\cdot (aX+\sqrt{1-a^{2}}Y) \} ]\\ =&-at\cdot s \mathbb{E} [exp\{i((t+as)\cdot X+\sqrt{1-a^{2}}s\cdot Y\}]\\ =&-at\cdot s exp\{\frac{|t+as|^{2}}{2}+\frac{(1-a^{2})|s|^{2}}{2} \}. \end{align} Therefore, integrating it gives \begin{align} &e^{\frac{|t|^{2}+|s|^{2}}{2}}\int_{0}^{1}-at\cdot s exp\{-\frac{2at\cdot s}{2} \}d a\\ &=e^{\frac{|t+s|^{2}}{2} }-e^{\frac{|t|^{2}+|s|^{2}}{2}}. \end{align} \square