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


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 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.