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!



Set of distributions that minimize KL divergence,
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.


