# 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$ ?

• Just to make sure: the square root of logarithm is going to be imaginary, is that okay? – Szeto Aug 10 '18 at 8:33
• Nope. $\delta \in (0, 1) \implies 1/\delta > 1 \implies \log(1/\delta) > 0$. Agreed ? – dohmatob Aug 10 '18 at 8:35
• Oh sorry...stupid mistake – Szeto Aug 10 '18 at 8:36
• No worries. Stuff happens :) – dohmatob Aug 10 '18 at 8:37
• To confirm, the max is at $x=0$ with the value $\exp\left(2\left(\log\left(\frac{1}{a}\right)\right)^{.5}\right)$? – Aaron Quitta Aug 10 '18 at 23:28

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.