1
$\begingroup$

According to Jensen's Inequality, it is not hard to derive the lower bound for $\log \sum_{i}{u_i \exp(x_i)}$ due to the convexity of $\log(\cdot)$:

$\log \sum_{i}{u_i \exp(x_i)} \geq \sum_{i}{u_i x_i}$.

However, my question is, can we somehow upper bound the quantity. The idea is that the set $\{x_i\}$ is bounded by $\min x_i$ and $\max_i$ and the second-order derivative of $\log(\cdot)$ is also bounded in the interval $[\min x_i, \max x_i]$. Therefore, we can upper bound it but the question is to what simplicity the bound could be.

I have tried some combinations under some numerical test, and found this bound might work:

$\log \sum_{i}{u_i \exp(x_i)} \leq \sum_{i}{u_i x_i}+\frac{1}{8}\Big(\max x_i\Big)^2$.

But I do not have a way to prove it. Any suggestions? Thanks.

$\endgroup$
  • $\begingroup$ Unless you put some constraints on the $u_i, x_i$ your bound obviously does not work: Take $n$ copies with $u_i=1, x_i=-1$ and your bound would imply $$0 \ge \log \left(\sum_{i}{u_i \exp(x_i)}\right) - \sum_{i}{u_i x_i} -\frac{1}{8} \Big(\max x_i\Big)^2 = \log(n) -1 + n - \frac{1}{8} $$ which is wrong for all $n>1.$ $\endgroup$ – gammatester Nov 22 '13 at 8:27
  • $\begingroup$ @gammatester. Excuse me. I meant $\max_i |x_i|$. In other words, the infinite norm $||x||_\infty$, where $x = (x_1, x_2, ..., x_n)$. $\endgroup$ – Strin Nov 24 '13 at 13:49
1
$\begingroup$

Fortunately, there do exists results from mathematical research that give the upper bound. I made some digging on the internet and found the following results. SLAVKO SIMIC [1] shows that for convex mapping $f$ on the interval $[a,b]$, the following bound exists:

$\sum\limits_i{p_i f(x_i)} \leq \sum\limits_i{ f(p_i x_i)}+f(a)+f(b)-f(\frac{a+b}{2})$.

Since $\log(\cdot)$ is a concave function, we should have

$\sum\limits_i{ \log(p_i x_i)} \leq \sum\limits_i{p_i \log(x_i)}+\log(a)+\log(b)+\log(\frac{a+b}{2})$.

Some other upper bounds have also been proposed. For example, in machine learning, Jebara et al. reversed Jensen's inequality for exponential families [2].

In fact, I found the previous guess has the correct form. It is not hard to show with SLAVKO SIMIC's result that

$\log(\sum\limits_{i}{p_i \exp(x_i)}) \leq \sum\limits_{i}{p_i\log( \exp(x_i))}+2 ||x||_{\infty}^2$.

$\endgroup$

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.