Welcome to Randal Douc's wiki

You've loaded an old revision of the document! If you save it, you will create a new version with this data.

====== Gaussian concentration inequality for Lipschitz functions ======
 
This is an interesting application of a symmetrisation argument. This article is almost directly taken from {{https://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/|Terrence Tao's webpage (Theorem 8)}} (see also Theorem 2.1.12 in "Topics in Random Matrix Theory" by Terrence Tao).

<WRAP center round box 80%>
__**Theorem**__ 
Let $(X_i)_{i\in [1:n]}$ be iid such that $X_i \sim N(0,\sigma^2)$ and set $X=(X_1,\ldots,X_n)$. Let $F: \rset^n \rightarrow \rset$ be a $1$-Lipschitz function wrt to the euclidian distance $\|\cdot\|$ on $\rset^n$, i.e., $|F(x)-F(y)| \leq \|x-y\|$ for all $x,y \in \rset^n$. Then for every $\lambda>0$,
\begin{equation} \label{eq:fond}
\PP( |F(X) - \PE[F(X)]| \geq \lambda ) \leq 2 \exp(-2\lambda^2/(\sigma \pi)^2 )
\end{equation}
</WRAP>

==== Proof ====

The original argument was given by Maurey and Pisier. We only prove the assertion under the more restrictive assumption $\|\nabla F(x)\|\leq 1$. Let $Y$ an independent copy of $X$, then for every $t>0$, 
$$
\PP( F(X) - \PE[F(Y)]\geq \lambda ) \leq \rme^{-\lambda t} \PE[\rme^{t (F(X)- \PE[F(Y)])}] \leq \rme^{-\lambda t} \PE[\rme^{t (F(X)-F(Y))}]
$$
where the last inequality follows from the Jensen inequality. We can see that the symmetrisation argument comes from a Jensen inequality and this now allows to use an infinitesimal writing of the difference $F(X) - F(Y)$,  
$$
F(X) - F(Y) = \int_0^{\pi/2} \frac{d}{d\theta} F(Y \cos \theta + X \sin \theta)\ \rmd\theta=\int_0^{\pi/2} \nabla F(U_\theta) \cdot V_\theta\ \rmd\theta,
$$
where $U_\theta=Y \cos \theta + X \sin \theta$ and $V_\theta=-Y \sin \theta + X \cos \theta$ are standard Gaussian r.v. and independent!!!! This is an amazing trick, we don't use the classical interpolation $F(Y(1-t) + X t)$ but a "polar" interpolation and this allows to get the product of uncorrelated terms (and therefore independent since we are in the context of Gaussian vectors). We again make use of Jensen's inequality in order to let appear, with a tower property, a term of the form $\PE[\rme^W]$ where $W$ is Gaussian, 
$$
\PE[\rme^{t (F(X)-F(Y))}] \leq \frac{2}{\pi} \int_0^{\pi/2} \PE[ \rme^{\frac{\pi t}{2} \nabla F(U_\theta ) \cdot V_\theta }]\rmd\theta=  \frac{2}{\pi} \int_0^{\pi/2} \PE[\rme^{\frac{(\sigma \pi t)^2}{8} \|\nabla F(U_\theta )\|^2}]\rmd\theta \leq \rme^{\frac{(\sigma \pi t)^2}{8}}.
$$
The rest of the proof is now standard. This proves that for every $t>0$
$$
\PP( F(X) - \PE[F(Y)]\geq \lambda ) \leq \rme^{-\lambda t+\frac{(\sigma \pi t)^2}{8}} 
$$
Choosing now $t$ such that $\frac{\rmd }{\rmd t} (-\lambda t+\frac{(\sigma \pi t)^2}{8})=0$ yields $t=4\lambda/(\sigma \pi)^2$ and  
\begin{equation} \label{eq:two}
\PP( F(X) - \PE[F(Y)]\geq \lambda ) \leq \rme^{-2\lambda^2/(\sigma \pi )^2}
\end{equation}
Applying the previous inequality with $F$ replaced by $-F$ and using $\PP( |A|\geq \lambda )=\PP( A\geq \lambda )+\PP( -A\geq \lambda )$ finishes the proof.

==== Consequences ====

We can see  \eqref{eq:two} as $H\geq G$ where $H$ is the cumulative distribution function of $F(X)-\PE[F(X)]$ and $G(\lambda)=1-\rme^{-2\lambda^2/(\sigma \pi)^2}$. Then, for all $U \sim \unif[0,1]$, we have 
$$
H^{\leftarrow}(U) \leq G^{\leftarrow}(U)
$$
where $H^{\leftarrow}$ is the generalized inverse of the function $H$. Therefore, there exists an exponential random variable $V$ such that 
$$
F(X)-\PE[F(X)] \leq \sigma \pi \sqrt{\frac{V}{2}}
$$
We can improve this bound with some more intricate proof, see Thm B.6, Introduction to high dimensional statistics, C. Giraud, which shows that 
$$
\PP( |F(X) - \PE[F(X)]| \geq \lambda ) \leq 2 \exp(-\lambda^2/(2\sigma^2) )
$$

Please fill all the letters into the box to prove you're human. M W U P J Please keep this field empty:

Edit summary

Welcome to Randal Douc's wiki

User Tools

Site Tools

Page Tools