Given $x \sim N(0, I)$ and $f : \mathbb{R}^{n} \longrightarrow \mathbb{R}$ which is $L$-Lipschitz, we have that $f - \mathbb{E}f$ is a sub-Gaussian random variable, specifically that $$ \| f(x) - \mathbb{E} f(x) \|_{\psi_2} \leq C L \:. $$

I want to show that if in addition $f \geq 0$, then for all $p > 0$, the more general statement $$ \| f(x) - (\mathbb{E} f(x)^p)^{1/p} \|_{\psi_2} \leq C_p L $$ holds, where $C_p$ is a constant which depends on $p$. This is Exercise 5.2.5 from Vershynin's book: http://www-personal.umich.edu/~romanv/teaching/2015-16/626/HDP-book.pdf (and the notation above is using his notation).

Using the fact that if $X$ is sub-gaussian then $$ \| X\|_p \leq C \|X\|_{\psi_2} \sqrt{p} \:, \:\: p \geq 1 \:, $$ (Eq 2.16 in Vershynin's HDP book), I was able to show that (just by triangle inequality) $$ \| X - \|X\|_p \|_{\psi_2} \leq (C_1 + C_2 \sqrt{p}) \| X \|_{\psi_2} \:. $$

I wanted then to apply this fact to the sub-Gaussian r.v. $Z := f(x) - \mathbb{E} f(x)$, but this doesn't work for $p \leq 1$ since the constant does not come out of the $p$-th moment of $Z$, so I don't think this approach is correct. Furthermore, it only applies when $p \geq 1$.

Any other hints/suggestions?


Ok here is a partial solution when $p \geq 1$ is an integer.

It uses the fact that if $X$ is sub-Gaussian, then every $p$-th moment is controlled as follows: $$ (\mathbb{E} |X|^p)^{1/p} \leq C_1 \| X \|_{\psi_2} \sqrt{p} \:. $$

Now let $\mu := \mathbb{E} f(x)$. Suppose that $f$ is 1-Lipschitz (this is wlog by scaling) and $f \geq 0$. Then, $$ \mathbb{E} f^p = \mathbb{E} (f - \mu + \mu)^p = \sum_{k=0}^{p} {p \choose k} \mu^{p-k} \mathbb{E}(f-\mu)^k \leq \sum_{k=0}^{p} {p \choose k} \mu^{p-k} \mathbb{E}|f-\mu|^k \:. $$ We know that $\|f - \mu\|_{\psi_2} \leq C_2$, and hence $\mathbb{E}| f - \mu|^k \leq C_3^k k^{k/2}$ for all $k \geq 0$. Hence, $$ \mathbb{E} f^p \leq \sum_{k=0}^{p} {p \choose k} \mu^{p-k} (C_3 \sqrt{k})^k \leq \sum_{k=0}^{p} {p \choose k} \mu^{p-k} (C_3 \sqrt{p})^k = (\mu + C_3 \sqrt{p})^p \:. $$ Taking the $p$-th root of both sides, we conclude that $$ (\mathbb{E} f^p)^{1/p} \leq \mu + C_3 \sqrt{p} \:. $$ Now we can make some progress. Using this inequality, for $t \geq 0$, $$ f(x) - (\mathbb{E} f^p)^{1/p} \leq - C_3 \sqrt{p} - t \Longrightarrow f(x) - \mu \leq - t \:. $$ Hence, we have established the lower tail $$ \mathbb{P}\left\{ f(x) - (\mathbb{E} f^p)^{1/p} \leq - C_3 \sqrt{p} - t \right\} \leq e^{-t^2/2} \:. $$ On the other hand, since $\mu \leq (\mathbb{E} f^p)^{1/p}$ by Jensen's inequality, we have $$ f(x) - (\mathbb{E} f^p)^{1/p} \geq C_3 \sqrt{p} + t \Longrightarrow f(x) - \mu \geq t \:. $$ Therefore, $$ \mathbb{P}\left\{ |f(x) - (\mathbb{E} f^p)^{1/p}| \geq C_3 \sqrt{p} + t \right\} \leq 2 e^{-t^2/2} \:. $$ This is not quite a sub-Gaussian tail, since when $t \leq C_3 \sqrt{p}$ it provides no information.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.