Concentration of Lipschitz Functionals of Gaussian Vector

This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

Theorem

Let $X_1, \dots, X_n$ be continuous random variables with a standard Gaussian distribution $\Gaussian 0 1$.

Let $F: \R^n \to \R$ be L-Lipschitz.

Then:

$\map \Pr {\size {\map F X - \expect {\map F X} } > L u} \le \map \exp {-\dfrac {u^2} {2 C} }$

where:

$\Pr$ denotes the probability function

$\expect {\, \cdot \,}$ denotes expectation.

Proof (The Pisier-Maurey approach)

The goal will be to control bound the Laplace transform:

$\expect {\map \exp {\lambda \paren {\map f X - \expect {\map f X} } } } \le \map \exp {C \dfrac {\paren {\lambda L}^2} 2}$

Then by Chernoff's bound:

$\map \Pr {\size {\map F X - \expect {\map F X} } > L u} \le \inf_{\lambda \mathop \ge 0} \map \exp {-\lambda L u + C \dfrac {\paren {\lambda L}^2} 2}$

is minimized for $\lambda = \dfrac u {L C}$.

Consider another Gaussian $n$-vector $Y$ independent of $X$.

Then by Jensen's inequality:

$\expect {\map \exp {\lambda(\map f X - \expect {\map f X}) } } \leq \expect {\map \exp {\lambda(\map f X - \map f Y) } }$

Next we will estimate the difference $\map f X - \map f Y$.

Consider:

$X_\theta := \map \cos {\dfrac \pi 2 \theta} X + \map \sin {\dfrac \pi 2 \theta} Y$

Then:

$\dfrac \pi 2 Z_\theta := \dfrac \partial {\partial \theta} X_\theta = -\dfrac \pi 2 \map \sin {\dfrac \pi 2 \theta} X + \dfrac \pi 2 \map \cos {\dfrac \pi 2 \theta} Y$

Because $\cov {\dfrac \pi 2 Z_\theta, X_\theta} = 0$ we have that $\dfrac \pi 2 Z_\theta, X_\theta$ are independent.

By FTC we have:

$\ds \map f X - \map f Y = \int_0^1 \dfrac \partial {\partial \theta} \map f {X_\theta} \rd \theta = \int_0^1 \dfrac \pi 2 Z_\theta \cdot \nabla \map f {X_\theta} \rd \theta$

By Jensen's we find the bound:

$\ds \int_0^1 \expect {\map \exp {\lambda \paren {\dfrac \pi 2 Z_\theta \cdot \nabla \map f {X_\theta} } } } \rd \theta$

For $v \in \R^n$ we have:

$\expect {\map \exp {\lambda \paren {\dfrac \pi 2 Z_\theta \cdot v} } } = \map \exp {\dfrac {\size v^2} 2}$

Therefore, by independence of $\dfrac \pi 2 Z_\theta, X_\theta$ we find:

$\ds \int_0^1 \expect {\map \exp {\dfrac {\paren {\lambda \pi/2}^2} 2 \size {\nabla \map f {X_\theta} }^2} } \rd \theta$

By the Lipschitz bound we find the bound:

$\map \exp {\dfrac {\paren {\lambda \pi/2}^2} 2 L^2}$