8
$\begingroup$

This was originally a question on Cross Validated.

Are there any (nontrivial) lower bounds on the Kullback-Leibler divergence $KL(f\Vert g)$ between two measures / densities?

Informally, I am trying to study problems where $f$ is some target density, and I want to show that if $g$ is chosen "poorly", then $KL(f\Vert g)$ must be large. Examples of "poor" behaviour could include different means, moments, etc.

Example: If $f=\sum_ka_kf_k$ and $g=\sum_kb_kg_k$ are two mixture distributions, is there a lower bound on $KL(f\Vert g)$ in terms of $KL(f_k\Vert g_j)$ (and also the convex weights $a_k,b_j$)? Intuitively, we'd like to say that if $\inf_{k\ne j} KL(f_k\Vert g_j)$ is "big", then $KL(f\Vert g)$ cannot be small.

Anything along these lines (for mixtures or arbitrary measures) would be useful. Obviously, you can make assumptions about the quantities involved. Alternatively, references to any papers that study these kinds of problems (either directly or indirectly) would be helpful!

$\endgroup$
  • 1
    $\begingroup$ One place where you might find some estimates in this spirit is information geometry, wherein one considers a smoothly varying family $f_\theta$ of densities parametrized by a smooth manifold. You can check that the first derivatives of $KL(f_\theta, f_{\theta_0})$ at $\theta_0$ vanish, and that the Hessian defines a semi-Riemannian metric on the parameter space. Sometimes it is possible to use tools from geometry (e.g. curvature bounds) to show that the KL-divergence is big for parameters which are "far away" with respect to this metric. $\endgroup$ – Paul Siegel Nov 11 '17 at 21:55
11
$\begingroup$

Pinsker's inequality states that \begin{equation} \text{KL}(f|g)\ge B_P:=\|f-g\|^2/2, \end{equation} where $\|f-g\|:=\int|f-g|$ is the total variation norm of the difference between the distributions with densities $f$ and $g$.

Another lower bound on $\text{KL}(f|g)$ can be given in terms of the Hellinger distance $d_H(f,g):=\frac1{\sqrt2}\|\sqrt f-\sqrt g\|_2$: \begin{equation} \text{KL}(f|g)\ge B_H:=2d_H(f,g)^2=\int(\sqrt f-\sqrt g)^2; \end{equation} see e.g. mathSE.

One may note note that either one of these two lower bounds, $B_P$ and $B_H$, may be better (that is, greater) than the other. E.g., if the densities $f$ and $g$ with respect to the counting measure on the set $\{1,2\}$ are given by the vectors $(1/2,1/2)$ and $(1/2-t,1/2+t)$ for $t\in(0,1/2)$, then $B_P>B_H$ for $t\in(0,t_*)$, and $B_P<B_H$ for $t\in(t_*,1/2)$, where $t=0.495\dots$ is a certain algebraic number.

$\endgroup$
5
$\begingroup$

At least the conjecture implied by the Example is false. Consider the distributions $p_1=p_2=(1/4,3/4)$ and $q_1=q_2=(3/4,1/4)$. Then $KL(p_i||q_j)\approx 0.5493$ while $KL((p_1+q_1)/2||(p_2+q_2)/2)=0$.

UPDATE

My original answer had mixed up the distributions, but it's still false. Take $f_1=(0.8,0.2)$, $f_2=(0.2,0.8)$, $g_1=(0.1,0.9)$, $g_2=(0.9,0.1)$. Define $f=(f_1+f_2)/2$ and $g=(g_1+g_2)/2$. Then $\min_{i,j}KL(f_i||g_j)>0.04$ while $KL(f||g)=0$.

$\endgroup$
  • $\begingroup$ I don't think this works: In my notation, you have $f_1=p_1$, $f_2=q_1$, $g_1=p_2$, and $g_2=q_2$. Thus $KL(f_1,g_1)=KL(p_1,p_2)=0$. $\endgroup$ – JohnA Nov 11 '17 at 22:07
  • 1
    $\begingroup$ UPDATE: Deceptively simple, but a great counterexample. Note that it seems like this can be applied to essentially any nonidentifiable mixture, which suggests that identifiability is crucial. $\endgroup$ – JohnA Nov 13 '17 at 18:07
  • $\begingroup$ Glad to be of help. Feel free to accept :) $\endgroup$ – Aryeh Kontorovich Nov 13 '17 at 18:08

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.