Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is it possible to use Fisher Information at p to get a useful upper bound on KL(q,p)?

KL(q,p) is known as Kullback-Liebler divergence and is defined for discrete distributions over k outcomes as follows:

$$KL(q,p)=\sum_i^k q_i \log \frac{q_i}{p_i}$$

The most obvious approach is to use the fact that 1/2 x' I x is the second order Taylor expansion of KL(p+x,p) where I is Fisher Information Matrix evaluated at p and try to use that as an upper bound (derivation of expansion from Kullback's book, 1,2,3)

If p(x,t) gives probability of observation x in a discrete distribution parameterized by parameter vector t, Fisher Information Matrix is defined as follows

$$I_{ij}(t)=\sum_x p(x,t) (\frac{\partial}{\partial t_i} \log p(x,t)) ( \frac{\partial}{\partial t_j} \log p(x,t)) $$

Where sum is taken over all possible observations.

Below is a visualization of sets of k=3 multinomial distributions for some random p's (marked as black dots) where this bound holds. From plots it seems that this bound works for sets of distributions that are "between" p and the "furthermost" 0 entropy distribution.

Motivation: Sanov's theorem bounds probability of some event in terms of KL-divergence of the most likely outcome...but KL-divergence is unwieldy and it would be nicer to have a simpler bound, especially if it can be easily expressed in terms of parameters of the distribution we are working with

share|improve this question
1  
Here's Mathematica notebook to generate figure above, I always welcome coding suggestions yaroslavvb.com/research/qr/mo-multinomials/mo-fisher-bound.nb –  Yaroslav Bulatov Aug 19 '10 at 21:53
    
Any chance you could either define or give a reference for what you mean by Fisher information and KL(q,p)? –  Deane Yang Aug 19 '10 at 21:55
1  
what does it mean to relate the two ? they are of different "type" - the fisher information is a metric tensor, and the kl-divergence is a distance measure. –  Suresh Venkat Aug 20 '10 at 2:50
    
Second order Taylor expansion of KL uses Fisher information matrix and "relates" to KL. I'm trying to see if that expansion relates to KL in any interesting way outside of neighborhood of the expansion point –  Yaroslav Bulatov Aug 20 '10 at 3:38
    
Here's my motivation for this -- Suppose you plot how the range of possible averages after n coin tosses decreases with n. Use Chernoff bound, but turns out you can't solve for range algebraically because of KL-divergence term. But, suppose coin is fair, use Fisher Information to get quadratic expansion of KL-divergence around 1/2, it forms an upper bound on KL everywhere, and you can use that to bound probability of large deviation, and solve for range explicitly, to get a nice algebraic formula for largest probable deviation that goes down as sqrt(n) –  Yaroslav Bulatov Aug 20 '10 at 4:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.