Suppose $X$ is a sub-Gaussian random variable with parameter $\sigma > 0$. Let $f(x)$ be a Lipschitz function with Lipschitz constant $L$. It is said that $f(X)$ should be also a sub-Gaussian with parameter of form $cL\sigma$ where $c$ is a constant.
I thought we should first utilize the definition of sub-Gauss dist $\mathbb{P}(|X-\mu|>t)\leq 2\exp(-\frac{t^2}{2\sigma^2})$.
Denote mean of $f(X)$ as $f(\mu')$, then
$$\mathbb{P}(|f(X) – f(\mu')|>t) \leq \mathbb{P}(L|X-\mu'|>t)\\
\leq \mathbb{P}(L|X-\mu'| + L|\mu-\mu'|>t) \\
= \mathbb{P}(L|X-\mu'|>t – L|\mu-\mu'|) \\
\leq 2\exp (-\frac{(t-L|\mu-mu'|)^2}{2\sigma^2L^2})\\
\leq 2\exp (-\frac{t^2}{2\sigma^2L^2}+\frac{|\mu-mu'|^2}{2\sigma^2})$$
So how to continue with the later term in RHS i.e. $\frac{|\mu-mu'|^2}{2\sigma^2}$ to get the form $cL\sigma$?
Thanks!
Best Answer
You can solve the inequality using variable substitution of $E(f(X))$.
Let $Y$ be an i.i.d random variable of $X$. By equivalence of definition of sub-Gaussian, $\exists \sigma>0$ s.t. $\mathbb{E}(e^{\frac{X^2}{\sigma^2}})\leq e$.
$$ \mathbb{E}(\exp{\frac{(f(X)-\mathbb{E}(f(X)))^2}{c^2}}) = \mathbb{E}(\exp{\frac{(f(X)-\mathbb{E}(f(Y)))^2}{(cL\sigma)^2}})\\ = \int_{\mathbb{R}} \mathbb{P}(X=x)\exp{\frac{(f(x)-\mathbb{E}(f(Y)))^2}{(cL\sigma)^2}}dx\\ \leq \int_{\mathbb{R}} \mathbb{P}(X=x)\mathbb{E}\exp{\frac{(f(x)-f(Y))^2}{(cL\sigma)^2}}dx\\ = \mathbb{E}\exp\frac{(f(X)-f(Y))^2}{(cL\sigma)^2}\\ \leq \mathbb{E}\exp\frac{L^2(X-Y)^2}{(cL\sigma)^2}\\ \leq \mathbb{E}\exp\frac{2L^2X^2+2L^2Y^2}{(cL\sigma)^2}\\ = \mathbb{E}\exp\frac{4X^2}{c^2\sigma^2} \leq e\\ $$
Therefore when $c\geq2$, $f(X)$ is sub-Gaussian w.r.t. $cL\sigma$.