# Jensen’s inequality

Prove the following by using Jensen's inequality:

$$\sum_{i=1}^m \exp(\theta^\top f_i) \geq \exp\left(\theta^\top \sum_{i=1}^m \alpha_i f_i - \sum_{i=1}^m \alpha_i \log \alpha_i\right)$$

where, $\large{\alpha_i = \frac{\exp(\hat{\theta}^\top f_i)}{\sum_{j=1}^m \exp(\hat{\theta}^\top f_j)}}$

I found that $\sum_{i=1}^m \alpha_i = 1$ and exp is a convex function, but should we prove that $\sum_{i=1}^m \alpha_i f_i - \sum_{i=1}^m \alpha_i \log \alpha_i = f_i$, then applying Jensen's inequality? or there is another way?

• It looks like $f_i$ and $\theta$ are vectors but you don't make it very clear what they or $\hat\theta$ are. The term in the exponential on the right looks like a Kullback-Liebler divergence. – Suzu Hirose Nov 15 '14 at 8:36
• Yes $\theta, \hat{\theta}$, and $f_i$ are vectors $\theta$ and $\hat{\theta}$ are just different – Zac Nov 15 '14 at 8:42
• I think it's a straightforward case of rewriting the equation till it looks like Jensen's inequality. – Suzu Hirose Nov 15 '14 at 8:45

Relative entropy is always non-negative (Proof by Jensen), therefore, $$0 \geq \sum_{i = 1}^m \alpha_i\ln\frac{\exp(\theta^{\top}f_i)}{\sum_{j = 1}^m \exp(\theta^{\top}f_j)} - \sum_{i = 1}^m \alpha_i\ln\alpha_i$$ $$0 \geq \sum_{i = 1}^m \alpha_i(\ln\exp(\theta^{\top}f_i) - \ln\sum_{j = 1}^m \exp(\theta^{\top}f_j)) - \sum_{i = 1}^m \alpha_i\ln\alpha_i$$ $$\sum_{i = 1}^m \alpha_i\ln\sum_{j = 1}^m \exp(\theta^{\top}f_j) \geq \sum_{i = 1}^m \alpha_i\theta^{\top}f_i - \sum_{i = 1}^m \alpha_i\ln\alpha_i$$ $$\ln\sum_{j = 1}^m \exp(\theta^{\top}f_j) \geq \sum_{i = 1}^m \alpha_i\theta^{\top}f_i - \sum_{i = 1}^m \alpha_i\ln\alpha_i$$ Taking exp on both sides, $$\sum_{j = 1}^m \exp(\theta^{\top}f_j) \geq \exp\left(\sum_{i = 1}^m \alpha_i\theta^{\top}f_i - \sum_{i = 1}^m \alpha_i\ln\alpha_i\right)$$