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!

Improve this question
$\endgroup$
1
  • 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, 2017 at 21:55

2 Answers 2

Reset to default
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.

Improve this answer
$\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$.

Improve this answer
$\endgroup$
3
  • $\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, 2017 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, 2017 at 18:07
  • $\begingroup$ Glad to be of help. Feel free to accept :) $\endgroup$
    – Aryeh Kontorovich
    Nov 13, 2017 at 18:08

You must log in to answer this question.

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