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!

  • $\begingroup$ 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. $\endgroup$ – Ashok Nov 5 '13 at 5:04
  • $\begingroup$ 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. $\endgroup$ – 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}$.

Note that the C.E method uses KL-divergence, but it has nothing to do with the fact that the problem is about KL-divergence. The answer would be similar for many other types of balls.


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.