How to prove this Gaussian Mixture inequality? (Fitting/Overfitting)

Let f[x] be a Gaussian Mixture pdf with n terms of uniform weight, means $\{\mu_{1},...,\mu_{n}\}$, and corresponding variances $\{\sigma_{1},...,\sigma_{n}\}$:

$$f(x)\equiv\frac{1}{n}\sum_{i=1}^{n}\frac{1}{\sqrt{2\pi\sigma_{i}^{2}}}e^{-\frac{(x-\mu_{i})^{2}}{2\sigma_{i}^{2}}}$$

It seems intuitive that the log-liklihood sampled at the n Gaussian centers would be greater than (or equal to) the mean log-liklihood:

$$\frac{1}{n}\sum_{j=1}^{n}ln(f(\mu_{j}))\geq\int f(x)ln(f(x))dx$$

This is obviously true for small variances (each $\mu_{i}$ is on top of a narrow Gaussian) and for very large variances (all the $\mu_{i}$'s are atop one broad Gaussian together), and it's been true for every set of $\mu_i$'s and $\sigma_i$'s I've generated and optimized, but I can't figure how to prove that it's always true. Help?

• You're probably missing an expectation on the l.h.s.? – lacerbi Jun 18 '16 at 3:14
• @lacerbi No, I'm not. Nothing is missing. On the LHS, the $f(x)$ is evaluated at the indexed $x_i$'s – Jerry Guern Jun 18 '16 at 3:16
• Yeah, sorry -- I was too sleepy and I misread the definition. – lacerbi Jun 18 '16 at 13:30

This is more of an extended comment, so take it as such. Define: $$f(x) \equiv \frac{1}{n} \sum_{i = 1}^n \mathcal{N}\left(x | x_i, \sigma_i^2 \right)$$ (I am using the standard notation for Gaussian distributions).

You want to prove that: $$\frac{1}{n} \sum_{i = 1}^n \log f(x_i) - \int f(x) \log f(x) dx \ge 0$$ which is $$\left\{\frac{1}{n} \sum_{i = 1}^n \log f(x_i)\right\} + \mathcal{H}[f] \ge 0.$$

Due to Jensen's inequality (see for example Huber et al., On Entropy Approximation for Gaussian Mixture Random Vectors, 2008), $$\mathcal{H}[f] \ge -\frac{1}{n} \sum_{i = 1}^n \log \int f(x) \mathcal{N}(x | x_i, \sigma_i^2) dx = -\frac{1}{n} \sum_{i = 1}^n \log g_i(x_i)$$ with $g_i(x) \equiv \frac{1}{n} \sum_{j = 1}^n \mathcal{N}\left(x | x_j, \sigma_i^2 + \sigma_j^2 \right)$, which comes from the convolution of two Gaussian densities. So we get: $$\left\{\frac{1}{n} \sum_{i = 1}^n \log f(x_i) \right\} + \mathcal{H}[f] \ge \frac{1}{n} \sum_{i = 1}^n \log \frac{f(x_i)}{g_i(x_i)}.$$ Interestingly, the $g_i$ are still mixtures of Gaussians with component means equal to the ones in $f$, but each component of $g_i$ has a strictly larger variance than its corresponding component in $f$. Can you do anything with this?

• Thank you. It looks like I'd just have prove that final RHS is >=0, which also looks intuitive but tricky to prove, but this is indeed a step in the right direction. I've seen that paper before. – Jerry Guern Jun 19 '16 at 1:38
• It's tempting to think that final RHS is always positive, but I can't actually prove that either. – Jerry Guern Jul 2 '16 at 4:48

I think I got it. It only takes elementary steps, although you need to combine them right.

Let's denote by $f_i$ the density of $i$-th Gaussian, that is $\frac{1}{\sqrt{2\pi \sigma_i^2}}e^{\frac{(x-\mu_i)^2}{2\sigma_i^2}}$

We start off with Jensen's Inequality. The function $g(x) = x log(x)$ is convex, hence we have: $f(x) \log(f(x)) \leq \frac{1}{n}\sum_{i=1}^n f_i(x) \log(f_i(x))$. After integrating we get: $$\int f(x)\log(f(x)) dx \leq \frac{1}{n} \sum_{i=1}^n \int f_i(x) \log(f_i(x)) dx$$ Edit: The inequality below is wrong and so is the solution itself

Now the RHS. For all $i$ we have $f \geq f_i$, so: $$log(f(\mu_i)) \geq log(f_i(\mu_i))$$ Hence: $$\frac{1}{n} \sum_{i=1}^n log(f(\mu_i)) \geq \frac{1}{n}\sum_{i=1}^n log(f_i(\mu_i))$$ We are left to prove: $$\frac{1}{n}\sum_{i=1}^n log(f_i(\mu_i)) \geq \frac{1}{n}\sum_{i=1}^n f_i(x) \log(f_i(x))$$ But we have: $$log(f_i(\mu_i)) = \int f_i(x) log(f_i(\mu_i)) dx \geq \int f_i(x) log(f_i(x)) dx$$ Summing over $i$ and dividing by $n$ we get what we needed

• I'm confused. You defined a g(x) but never used it, and I don't know what your f_i means. – Jerry Guern Jul 1 '16 at 10:31
• I added definition of $f_i$, sorry about that. I use $g$ just for the Jensen inequality, that is $g(\frac{1}{n}\sum_{i=1}^n f_i(x)) \leq \frac{1}{n}\sum_{i=1}^n g(f_i(x))$ – sjm.majewski Jul 1 '16 at 10:51
• You statement that $f>=f_i$ is only correct if the $1/n$ weight is part of the definition of $f_i$ but it's not, and adding it back in messes up the early part of your proof. – Jerry Guern Jul 2 '16 at 4:20
• This statement is not correct: $\frac{1}{n} \sum_{i=1}^n log(f(\mu_i)) \geq \frac{1}{n}\sum_{i=1}^n log(f_i(\mu_i))$ – Jerry Guern Jul 2 '16 at 4:22
• Yeah, I realized it yesterday. Seems like this inequality is quite tough, I'll leave my answer anyway with an edit. – sjm.majewski Jul 2 '16 at 12:27