Good UPPER bounds for $\log(\sum_{i=1}^n p_ie^{z_i})-\sum_{i=1}^np_iz_i$ where $(p_i)_i$ is a probability vector

Question

Let $x=(z_1,\ldots,z_n)$ be real vector and $(p_1,\ldots,p_n)$ be a probability vector.

Question

$\log(\sum_{i=1}^n p_ie^{z_i})-\sum_{i=1}^np_iz_i \le ???$

Observation

This paper allows us to upper-bound things like $\Delta_f(z,p):=f(\sum_{i}z_i p_i) - \sum_i f(p_iz_i)$, thus providing a kind of reversed Jensen's inequality.

Indeed, it was shown that

If $f$ is concave, $a:=\min_i z_i$ and $b := \max_i z_i$, then $$ \Delta_f(z,p) \le \max_{p,q \ge 0,\;p+q=1} pf(b)+qf(a) - f(pb+qa). $$

I could probably use this with $f=\log$ to bound $\Delta_{\log} (z,p)$.

Answer 1

One answer - subgaussian variables generalize this property.

Let $\mu = \sum_i p_i z_i$, then the distribution is considered $\sigma^2$-subgaussian if for all $\lambda \in \mathbb{R}$,

$$ \log\left(\sum_i p_i e^{\lambda(z_i - \mu)}\right) \leq \frac{\lambda^2 \sigma^2}{2} $$

i.e.

$$ \log\left(e^{-\lambda \mu} \sum_i p_i e^{\lambda z_i}\right) \leq \frac{\lambda^2 \sigma^2}{2} $$

i.e.

$$ \log\left(\sum_i p_i e^{\lambda z_i}\right) - \lambda \mu \leq \frac{\lambda^2 \sigma^2}{2} . $$

Your expression is the case $\lambda=1$.

In a sense this is not an answer, just a definition for when and how your inequality can be satisfied, but hopefully useful because we know ways to show variables are subgaussian:

1. Any random variable bounded in $[a,b]$ is $\left(\frac{b-a}{2}\right)^2$-subgaussian.
2. If $X$ is $\sigma^2$-subgaussian, then $cX$ is $c^2\sigma^2$-subgaussian.
3. If $X$ and $Y$ are independent and $\sigma_1^2,\sigma_2^2$ subgaussian, then $X+Y$ is $\sigma_1^2 + \sigma_2^2$ subgaussian.