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.

====== Concentration inequalities and logarithmic Sobolev inequality ======
$\newcommand{\Ent}{\mathrm{Ent}}$

====== Theorem ======

Let $\mu$ be a probability measure on $\mathbb{R}^n$ satisfying the following logarithmic Sobolev inequality:
$$
\forall f \in C_b^\infty(\mathbb{R}^n), \quad \Ent_\mu(f^2) \leq c \, \mathbb{E}_\mu(|\nabla f|^2),
$$
then for every Lipschitz function $F : \mathbb{R}^n \to \mathbb{R}$ with $\|F\|_{\mathrm{Lip}} \leq 1$, and for all $r > 0$, we have:
$$
\mu(F \geq \mathbb{E}_\mu(F) + r) \leq \exp\left(-\frac{r^2}{c}\right), \\
\mu(|F - \mathbb{E}_\mu(F)| \geq r) \leq 2 \exp\left(-\frac{r^2}{c}\right).
$$

===== Proof. =====

We first assume that $F$ is a smooth and bounded function such that $\|F\|_{\mathrm{Lip}} \leq 1$. Consider the Laplace transform of $F$:
$$
H(\lambda) := \mathbb{E}_\mu\left(e^{\lambda F}\right), \quad \lambda > 0.
$$

Apply the logarithmic Sobolev inequality to the function $f = e^{\lambda F / 2}$. Then:
$$
\Ent_\mu(e^{\lambda F}) \leq c \, \mathbb{E}_\mu\left( \left| \nabla e^{\lambda F/2} \right|^2 \right).
$$
Since $\nabla e^{\lambda F / 2} = \frac{\lambda}{2} e^{\lambda F / 2} \nabla F$, we get:
$$
\left| \nabla e^{\lambda F / 2} \right|^2 = \frac{\lambda^2}{4} e^{\lambda F} |\nabla F|^2.
$$
Because $\|\nabla F\|_\infty \leq 1$, it follows that:
$$
\Ent_\mu(e^{\lambda F}) \leq \frac{c \lambda^2}{4} H(\lambda).
$$

Also, we have the identity:
$$
\Ent_\mu(e^{\lambda F}) = \int e^{\lambda F} \log \frac{e^{\lambda F}}{\int e^{\lambda F} \, d\mu} \, d\mu = \lambda H'(\lambda) - H(\lambda) \log H(\lambda),
$$
which gives:
$$
\lambda H'(\lambda) - H(\lambda) \log H(\lambda) \leq \frac{c \lambda^2}{4} H(\lambda).
$$

Dividing by $\lambda^2 H(\lambda)$ (which is valid since $H(\lambda) > 0$), we obtain:
$$
\frac{H'(\lambda)}{\lambda H(\lambda)} - \frac{\log H(\lambda)}{\lambda^2} \leq \frac{c}{4}.
$$

Define:
$$
K(\lambda) := \frac{1}{\lambda} \log H(\lambda), \quad \lambda > 0.
$$

Then we have:
$$
K'(\lambda) \leq \frac{c}{4}.
$$

The function $K$ is continuous on $[0,\infty)$ and differentiable on $(0,\infty)$. Taking the limit as $\lambda \to 0^+$ gives:
$$
\lim_{\lambda \to 0^+} K(\lambda) = \mathbb{E}_\mu(F).
$$

Therefore, for all $\lambda > 0$:
$$
K(\lambda) \leq \mathbb{E}_\mu(F) + \frac{c}{4} \lambda,
$$
that is:
$$
\log H(\lambda) \leq \lambda \mathbb{E}_\mu(F) + \frac{c}{4} \lambda^2,
$$
and hence:
$$
H(\lambda) \leq \exp\left( \lambda \mathbb{E}_\mu(F) + \frac{c}{4} \lambda^2 \right).
$$

Now apply Markov’s inequality:
$$
\mu(F \geq \mathbb{E}_\mu(F) + r) = \mu\left(e^{\lambda F} \geq e^{\lambda (\mathbb{E}_\mu(F) + r)} \right)
\leq \frac{H(\lambda)}{e^{\lambda (\mathbb{E}_\mu(F) + r)}}.
$$

Using the previous bound on $H(\lambda)$, we get:
$$
\mu(F \geq \mathbb{E}_\mu(F) + r) \leq \exp\left( \frac{c}{4} \lambda^2 - \lambda r \right).
$$

Optimizing this upper bound by choosing $\lambda = \frac{2r}{c}$ gives:
$$
\mu(F \geq \mathbb{E}_\mu(F) + r) \leq \exp\left( -\frac{r^2}{c} \right).
$$

This proves the first inequality. The second follows by applying the same bound to $-F$ and combining both tails:
$$
\mu(|F - \mathbb{E}_\mu(F)| \geq r) \leq \mu(F \geq \mathbb{E}_\mu(F) + r) + \mu(F \leq \mathbb{E}_\mu(F) - r) \leq 2 e^{-r^2 / c}.
$$

Finally, the general case where $F$ is only Lipschitz (not smooth and bounded) is obtained by standard mollification (i.e., convolution with a smooth kernel) and a limiting argument using the semicontinuity of the Lipschitz norm and uniform upper bounds.

Please fill all the letters into the box to prove you're human. Y Y C X H Please keep this field empty:

Edit summary

Welcome to Randal Douc's wiki

User Tools

Site Tools

Page Tools