0
$\begingroup$

Let $p(x)$ be a fixed distribution over a discrete space.

Let $A, C > 0$ be constants. Let $\epsilon > 0$. Can we find an example of a distribution $q_{\epsilon}$ such that $\mathrm{KL}(p||q_{\epsilon}) < \epsilon$, but $E[(\log (p(x)/q_\epsilon(x)))^2] \ge A * \epsilon^C$?

$q_{\epsilon}$ should be geometric, if possible (in which case, the discrete space is the natural numbers).

Perhaps I could also get a clue if I knew whether there is a name for the quantity $E[(\log (p(x)/q_\epsilon(x)))^2]$.

All expectations are taken with respect to $p$. So, for example,

$E[(\log (p(x)/q_\epsilon(x)))^2] = \sum_x p(x) \left(\log (p(x)/q_\epsilon(x))\right)^2$

and

$\mathrm{KL}(p||q_{\epsilon}) = \sum_x p(x) \log \frac{p(x)}{q_{\epsilon}(x)}$

I think that the only chance of solving this is by creating a $q_\epsilon$ such that $\log(p/q_\epsilon)$ is either extremely negative or extremely positive. Then, when taking the squares, it would diverge. But I don't see how this could happen when the KL divergence is smaller than $\epsilon$, because, for example, when the KL divergence is exactly 0, $p(x)=q_{\epsilon}(x)$ for all $x$, and we could not have this effect of $\log p(x)/q(x)$ being extremely small or big.

I think I can show that for the geometric case, unfortunately, there is no such construction, but I am not sure. I would be okay with other examples, as long as the space is discrete.

$\endgroup$
4
  • $\begingroup$ $p(x)$ can be part of the construction, not just $q_{\epsilon}(x)$. $\endgroup$
    – rasper
    Oct 13, 2010 at 14:00
  • $\begingroup$ Second moment does not necessarily exist in the first place. So yes, you can find such p and q with arbitrary large A. For example take p to be geometric upto some large $N$ and then $1\over n^3$. $q$ is geometric. Thus as $N\to\infty$ $KL(p||q_\epsilon)\to0$, but the second moment is always $+\infty$ (if you don't like this, cut $p$ at $M\gg N$. $\endgroup$ Oct 13, 2010 at 17:12
  • $\begingroup$ Thanks. That's an interesting case, but does not follow the requirements: $p$ needs to be fixed. It is $q$ that can change depending on $\epsilon$. $\endgroup$
    – rasper
    Oct 13, 2010 at 21:54
  • $\begingroup$ Maybe my wording is not clear. The quantifiers are: Exists P such that For All eps,C,A Exists q_eps such that KL < eps and second moment >= C*eps^A $\endgroup$
    – rasper
    Oct 13, 2010 at 21:56

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.