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} \}. $$