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
    Just to make sure: the square root of logarithm is going to be imaginary, is that okay? – Szeto Aug 10 at 8:33
  • Nope. $\delta \in (0, 1) \implies 1/\delta > 1 \implies \log(1/\delta) > 0$. Agreed ? – dohmatob Aug 10 at 8:35
  • Oh sorry...stupid mistake – Szeto Aug 10 at 8:36
  • No worries. Stuff happens :) – dohmatob Aug 10 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 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} $$


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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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