11
$\begingroup$

Given $\sigma>0$, let $X\sim N(0,\sigma^2I_d)$ be a normal random variable in $\mathbb R^d$. Prove or disprove: there exists a constant $C$ such that for any 1-Lipschitz function $f:\mathbb R^d\rightarrow\mathbb R$, $$ \log\big(\mathbb E[e^{f(X)}]\big) - \mathbb E[f(X)] \leqslant C\sigma^2. $$ Here, $f$ is 1-Lipschitz means that $f$ is continuous in $\mathbb R^d$ and $|f(x)-f(y)|\leqslant |x-y|$ for any $x,y\in\mathbb R^d$.

This problem comes from the proof of Proposition 3 in this paper, where the authors claimed that the log-Sobolev inequality can be used to prove eq. 25. The problem above can be viewed as a simplified version of eq. 25 of the paper. However, I found it non-trivial to obtain eq. 25 using the log-Sobolev inequality, the log-Harnack inequality, or other functional inequalities I know. It looks more like an inverse type of the Jensen's inequality, which is the reason this problem is so named.

Here are some direct observations of this problem. First of all, by Jensen's inequality, one has $$ \log\big(\mathbb E[e^{f(X)}]\big) - \mathbb E[f(X)] \geqslant 0, $$ which seems no help.

Another idea is to consider the random variable $Y = f(X)$ rather than $X$ itself. Then it may be reasonable to consider $$ \log\big( \mathbb E[e^Y]\big) - \mathbb E[Y] \leqslant \mathrm{Var}(Y). $$ Unfortunately, this inequality does not hold for arbitrary $Y$. Also, the Lipschitz property of $f$ becomes implicit here.

In the case $d=1$, if one chooses $f(x) = x$ directly, it can be verified that $$ \log\big(\mathbb E[e^{X}]\big) - \mathbb E[X] = \frac{\sigma^2}2. $$ This is why the RHS has a square term of $\sigma$.

Any suggestions are appreciated. Even the solution in the case $d=1$ is fine.

$\endgroup$
3
  • $\begingroup$ Nice question! +1 and favourited. I haven't got my hands dirty with the details, but just a small comment: the Lipschitz-1 property implies that a gradient is at most 1. Not sure if this helps, but just something that came to my mind! $\endgroup$
    – Sam OT
    Commented Jul 1, 2022 at 15:18
  • $\begingroup$ May I ask why this question doesn't meet MSE guideline? $\endgroup$
    – PinkyWay
    Commented Jul 1, 2022 at 15:21
  • $\begingroup$ @SummerChild Someone must have clicked it by mistake, because I cannot for the life of me see why this should be closed. This came in the review queue, and I have voted to leave it open. $\endgroup$ Commented Jul 2, 2022 at 6:51

2 Answers 2

2
$\begingroup$

Partial answer; I show the inequality holds for all $d\ge 1$ as long as $\sigma \ge 3$. Moreover, this goes through a bound that is independent of the dimension $d$, which may itself be of interest.

The inequality amounts to an upper bound on $\mathbb{E}[e^{f(X)}]$, which we proceed to obtain as follows: $$\mathbb{E}[e^{f(X)}] = \int_{0}^{\infty} \mathbb{P}(e^{f(X)} \ge t) \, dt = \int_{0}^{\exp(\mathbb{E}f(X))} \mathbb{P}(e^{f(X)} \ge t) \, dt + \int_{\exp(\mathbb{E}f(X))}^{\infty} \mathbb{P}(e^{f(X)} \ge t) \, dt $$ $$\le e^{\mathbb{E}f(X)} + \int_{\exp(\mathbb{E}f(X))}^{\infty} \mathbb{P}(e^{f(X)} \ge t) \, dt $$ Making the change of variables $t = \exp(\mathbb{E}f(X) + s)$, the latter integral is $$\int_{\exp(\mathbb{E}f(X))}^{\infty} \mathbb{P}(e^{f(X)} \ge t) \, dt = e^{\mathbb{E}f(X)} \int_{0}^{\infty} \mathbb{P}(f(X) - \mathbb{E}f(X) \ge s) e^{s} \, ds$$ Using now the Gaussian concentration inequality for $L$-Lipschitz functions (Theorem 5.6 in Boucheron's Concentration inequalities: a nonasymptotic theory of independence), we know that $\mathbb{P}(f(X) - \mathbb{E}f(X) \ge s) \le 2\exp(-t^2/(2\sigma^2))$ and therefore $$\int_{0}^{\infty} \mathbb{P}(f(X) - \mathbb{E}f(X) \ge s) e^{s} \, ds \le 2\int_{0}^{\infty} \exp(s - s^2/(2\sigma^2)) \, ds $$ $$= \sqrt{2\pi\sigma^2} e^{\sigma^2/2} \left(\text{erf}\left(\sqrt{\sigma^2 / 2}\right) + 1 \right) \le C \sigma \exp(\sigma^2 / 2)$$ for absolute constant $C = 2\sqrt{2\pi}$. Putting it together, we have $$\mathbb{E}[e^{f(X)}] \le \left(1 + C\sigma \exp(\sigma^2 / 2) \right) e^{\mathbb{E}f(X)}$$ independently of the dimension $d$. Finally, $1 + C\sigma \exp(\sigma^2 / 2) \le \exp(d\sigma^2)$ for all $d\ge 1$ when $\sigma \ge 3$.

$\endgroup$
2
  • $\begingroup$ Although I personally care more about the case $\sigma$ is close to 0, this is an excellent proof! $\endgroup$
    – Xuda Ye
    Commented Jul 2, 2022 at 7:17
  • $\begingroup$ This result gives another type of upper bound independent of the dimension, might be more useful in the high-dimensional case $d\to\infty$. $\endgroup$
    – Q9y5
    Commented Jul 2, 2022 at 9:42
0
$\begingroup$

Set $d=1$ and borrow the notation given in the post. For fixed $\sigma>0$, I managed to prove the following:

  1. A counter-example for the reverse Jensen inequality as stated.
  2. $\forall\epsilon>0\exists C_\epsilon>0$ such that $\forall\sigma>\epsilon$ the following reverse Jensen inequality is true with $C=C_\epsilon$. I also show that $C_\epsilon\ll\frac{1}{\epsilon^2}$.

Below set $g:=f-\Bbb E[f(X)]$. Then $g:\Bbb R\rightarrow\Bbb R$ is $1$-Lipschitz and the reverse Jensen inequality is equivalent to $\log\Bbb E[e^{g(X)}]\leq C\sigma^2$.

[The proofs for $(*)$, $(**)$ and $(***)$ that are used below will be given at the end of this post.]

1. Counterexample: Set $f(x)=-|x|$. Then $g(x)=-|x|+\sqrt\frac{2}{\pi}\sigma$ and

\begin{align} \log\Bbb E[e^{g(X)}] &=\log\Bbb E[e^{-|X|+\sqrt\frac{2}{\pi}\sigma}]\\ &=\sqrt\frac{2}{\pi}\sigma+\log\Bbb E[e^{-|X|}] \tag{1.1} \end{align} where \begin{align} \Bbb E[e^{-|X|}] &=\frac{1}{\sqrt{2\pi}\sigma}\int_{\Bbb R} e^{-|x|}e^\frac{-x^2}{2\sigma^2}\,dx\\ &=\sqrt\frac{2}{\pi}e^{\sigma^2/2}\int_0^\infty e^{-\frac{(u^2+2\sigma u+\sigma^2)}{2}}\,du\\ &\approx e^{-\sigma^2/2} \end{align} [for small $\sigma$, which is what we care about for the counterexample] using which in $(1.1)$ gives,

\begin{align} \log\Bbb E[e^{g(X)}] &=\sqrt\frac{2}{\pi}\sigma+\log\Bbb E[e^{-|X|}]\\ &\approx\sqrt\frac{2}{\pi}\sigma+\frac{1}{2}\sigma^2 \end{align} The counter-example checks out because of the linear term in the lower bound, which causes issues bounding for $\sigma$ near $0$.

2. Proof:

$$\Bbb E[e^{g(X)-g(0)}]+g(0) = \sum_{n=0}^\infty \frac{1}{(2n)!}\Bbb E[(g(X)-g(0))^{2n}] + \sum_{n=1}^\infty \frac{1}{(2n+1)!}\mathbb [(g(X)-g(0))^{2n+1}] \tag{2.1}$$

where I have used that $\Bbb E[g(X)]=0$. I will need the following moments of the half-normal distribution below: $$ \Bbb E[|X|^{2n}] = \frac{\sigma^{2n}(2n)!}{n!2^n} \text{ and } \Bbb E[|X|^{2n+1} = \sqrt\frac{2}{\pi}\sigma^{2n+1}2^n n! $$

which give

\begin{align} \sum_{n=0}^\infty \frac{1}{(2n)!}\Bbb E[(g(X)-g(0))^{2n}] &\leq \sum_{n=0}^\infty \frac{1}{(2n)!}\Bbb E[|X|^{2n}]\\ &=\sum_{n=0}^\infty \frac{\sigma^{2n}}{n!2^n}=\sum_{n=0}^\infty \frac{(\sigma^{2}/2)^n}{n!}\\ &=e^{\sigma^2/2} \tag{2.2} \end{align}

and

\begin{align} \sum_{n=1}^\infty \frac{1}{(2n+1)!}\mathbb [(g(X)-g(0))^{2n+1}] &\leq \sum_{n=1}^\infty \frac{1}{(2n+1)!}\Bbb E[g(X)^{2n+1}]\\ &=\sum_{n=1}^\infty \sqrt\frac{2}{\pi}\sigma^{2n+1}\frac{2^n n!}{(2n+1)!}\\ &\leq \sqrt\frac{2}{\pi}\sigma\sum_{n=1}^\infty \frac{(\sigma^2/2)^n}{n!} \tag{$*$}\\ &=\sqrt\frac{2}{\pi}\Big[ e^{\sigma^2/2}-1\Big] \tag{2.3} \end{align}

where in $(*)$ I have used that $\forall m\in\Bbb N_0, \frac{2^{2m} m!}{(2m+1)!}\leq\frac{1}{m!}$. I wanted this inequality to be true for the result, and with a little tinkering found that it was!

Finally it can be showed that $$ e^{\sigma^2/2} + \sqrt\frac{2}{\pi}\Big[ e^{\sigma^2/2}-1\Big] \leq e^{\sigma^2}. \tag{$**$}$$

Using $(2.2)$, $(2.3)$ and $(**)$ in $(1)$ gives $$\Bbb E[e^{g(X)-g(0)}] + g(0) \leq e^{\sigma^2}$$ which upon rearrangement reads $$\Bbb E[e^{g(X)}]\leq e^{\sigma^2+g(0)}-g(0)e^{g(0)} \tag{2.4}.$$

We can control $g(0)$ above as follows: $$|g(0)|=\Bbb |f(0)-E[f(X)]|\leq \Bbb E[|X|]=\sqrt\frac{2}{\pi}\sigma \tag{2.5}$$

Using $(2.5)$ in $(2.4)$ gives, \begin{align} \Bbb E[e^{g(X)}] &\leq e^{\sigma^2+\sqrt\frac{2}{\pi}\sigma}+\sqrt\frac{2}{\pi}\sigma e^{\sqrt\frac{2}{\pi}\sigma}\\ \implies \log\Bbb E[e^{g(X)}]&\leq \sqrt\frac{2}{\pi}\sigma+\log\Big(e^{\sigma^2}+\sqrt\frac{2}{\pi}\sigma\Big)\tag{2.6} \end{align}

Note now that $\epsilon<\sigma\iff\sigma<\sigma^2/\epsilon$, and \begin{align} \sqrt\frac{2}{\pi}\sigma+e^{\sigma^2} &\leq 2\sigma+e^{\sigma^2}\\ &\leq e^{\frac{2}{\epsilon}\sigma^2}+e^{\sigma^2}\\ &\leq e^{(\frac{2}{\epsilon}+\frac{\log 2}{\epsilon^2})\sigma^2}. \tag{$***$} \end{align}

Using $(***)$ in $(2.6)$ gives \begin{align} \log\Bbb E[e^{g(X)}] &\leq \Big(\sqrt\frac{2}{\epsilon\pi}+\frac{2}{\epsilon}+\frac{\log 2}{\epsilon^2}\Big)\sigma^2 \end{align} and thus $C_\epsilon=\sqrt\frac{2}{\epsilon\pi}+\frac{2}{\epsilon}+\frac{\log 2}{\epsilon^2}$ suffices.


Proof for $(*)$: \begin{align} \frac{2^{2m}m!}{(2m)!}&=\frac{m!}{1\cdot\frac{2}{2}\cdot\frac{3}{2}\dots\frac{2m}{2}\cdot\frac{2m+1}{2}}\leq\frac{1}{m!} \end{align}

Proof for $(**)$:

Follows from $$e^{-\sigma^2/2} + \sqrt\frac{2}{\pi}\Big[ e^{-\sigma^2/2}-e^{-\sigma^2}\Big]\leq 1$$

Proof for $(***)$:

We want to find $k=k(\epsilon)$ such that $$ e^{\frac{2}{\epsilon}\sigma^2}+e^{\sigma^2}\leq e^{k\sigma^2},$$ which is equivalent to $e^{(\frac{2}{\epsilon}-k)\sigma^2}+e^{(1-k)\sigma^2}\leq 1$, holds true. If $k$ is large, then noting that $\sigma>\epsilon$, the LHS will be largest when $\sigma=\epsilon$. Thus it will suffice to require the following: \begin{align} \epsilon(2-\epsilon k)&\leq\log(1/2)\\ \epsilon^2 (1-k)&\leq\log(1/2) \end{align} from which we see that any $k\geq \frac{\log 2}{\epsilon^2}+\frac{2}{\epsilon}$ suffices.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .