What is a simple upper bound for $\exp\left(-\frac{1}{2}(x-(2\log(1/\delta)^{1/2}))^2\right)$ given $x \ge0$ and $\delta \in (0, 1)$?

122 Views Asked by At

Question

For $x \ge 0$ and small $\delta \in (0, 1)$, what is a "simple" good upper bound for $$u(x,\delta) := \exp\left(-\frac{1}{2}(x-(2\log(1/\delta)^{1/2}))^2\right), $$ that doesn't involve $x$ and $\delta$ in the same exponential expression ?

More general question

Given differentiable strongly-convex function $h: \mathbb R \rightarrow \mathbb R$ and $a \in \mathbb R$, what is a simple upper bound for $exp(-h(x-a))$ in terms of $\exp(-h(-a))$ and things which are not exponential in expressions containing both $x$ and $a$ ?

1

There are 1 best solutions below

0
On

Ok, I stopped being lazy and did some computations. So, if $h: \mathbb R \rightarrow \mathbb R$ is smooth and $\sigma$-strongly convex function, then it is an elementary result in convex optimization that for any $\alpha,\beta \in \mathbb R$, one has

$$ h(\beta) \ge h(\alpha) + (\beta-\alpha)h'(\alpha) + \sigma(\beta-\alpha)^2/2. $$

Thus $e^{-h(\beta)} \ge e^{-h(\alpha)}e^{-(\beta-\alpha)h'(\alpha)}e^{-\sigma(\beta-\alpha)^2/2}$. Now, take $\alpha = a$ and $\beta = x+a$ to get $$ e^{-h(x+a)} \le e^{-h(a)}e^{-xh'(a)}e^{-\sigma x^2/2} \le \begin{cases}e^{-h(a)},&\mbox{ if }x(h'(a)+\sigma x/2) \ge 0,\\e^{-\sigma x^2/2} \ll 1,&\mbox{ if }h'(a)=0 \ne x.\end{cases} $$

In particular, when $h(x):= \frac{1}{2}x^2$ and $a=-\sqrt{2\log(1/\delta)}$, we obtain that

$$ e^{-\frac{1}{2}(x-(2\log(1/\delta))^{1/2})^2} \le \begin{cases}e^{-x^2/2},&\mbox{ if }\delta = 1,\\\delta,&\mbox{ if }\delta \in (0, 1)\text{ and }x \ge 2(2\log(1/\delta))^{1/2}\end{cases} $$

Observation

I haven't tried, but maybe the second branch of the above bound can be improved further.

Moving further

An analogous reasoning with apply for more strong-convexity w.r.t more general Bregman divergences, to obtain more general results.