# Set of distributions that minimize KL divergence,

Assuming that $p,q$ are probability distributions defined on the same support $\{x_i\}_{0 \leq i \leq n}$, $\epsilon$ a small real number, and $D_{KL}$ the Kullback-Leibler divergence,

is there a method or an algorithm to find the set $\mathcal{P}_{q, \epsilon}$ defined as :

$\mathcal{P}_{q, \epsilon}= \{\ p\ |\ D_{KL}(p||q) \leq \epsilon\ \}$

Thank you!

• In what context do you come across this? If it arises in problems like minimising $\mathbb{E}_p[X]$ subject to $p\in \mathcal{P}_{q,\epsilon}$, there is some duality which would help solving the problem. – Ashok Nov 5 '13 at 5:04
• Doesn't it make more sense to look at $\{q | D_{KL}(p||q) \leq \epsilon \}$? This would be a set of distributions that approximate $p$ well whereas you're looking at a set for which $q$ is a good approximation. – Arthur B Nov 5 '13 at 15:44

The cross-entropy method will easily allow you to approximate $\mathcal{P}_{q,\epsilon}$ as an ellipsoid, which is likely reasonable if $\epsilon$ is small enough ($q$ is a global minimum so the hessian is semi definite positive around $q$)
The idea is to iteratively find a multivariate normal distribution that minimizes its KL-divergence to the distribution $\mathbf{1}_{\mathcal{P}_{q,\epsilon}}$. This will then allow you to efficiently generate random samples from $\mathcal{P}_{q,\epsilon}$.