2
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • $\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
    Commented Nov 5, 2013 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
    Commented Nov 5, 2013 at 15:44

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .