Using Fisher Information to bound KL divergence 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, pages 26, 27, 28).
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.
 (source)
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
 A: I'm not sure if this is still of interest to you, but I think it is possible to get some reasonable bounds if you are okay with dropping the factor of $\frac{1}{2}$. Here's my work, which can be strengthened and refined.
We start by taking two probability mass functions $p$ and $q$ which we denote as $p_i$ and $q_i$. We define the function $f$ as $f_i= q_i-p_i$. Instead of doing anything fancy, we consider the line segment $p_i(t) = p_i +tf_i$. Since $f$ has total mass zero, the $p_i(t)$ are well defined probability distributions that form a straight line in the probability simplex. We can see that $p_i(0) = p_i$ and $p_i(1) = q_i$
Now we take the Taylor series for the Kullback-Liebler divergence, expanded at $t=0$. This will involve the Fisher metric, but we should expand it out further to get better results.
When we expand out $(p_i + t f_i)\log\left( \frac{p_i + t f_i}{p_i} \right)$, we get the following:
$$f_i t+\frac{f_i^2 t^2}{2 p_i}-\frac{f_i^3 t^3}{6 p_i^2}+\frac{f_i^4 t^4}{12 p_i^3}-\frac{f_i^5 t^5}{20 p_i^4}+\frac{f_i^6 t^6}{30 p_i^5}+O\left(t^7\right)$$
When we sum over $i$, the first term will vanish, and we can factor out a Fisher metric term from all of the others. I will use an integral sign to sum over $i$, as it is suggestive of what should happen in the continuous case.
$$\int f_i t+\frac{f_i^2 t^2}{2 p_i}-\frac{f_i^3 t^3}{6 p_i^2}+\frac{f_i^4 t^4}{12 p_i^3} \ldots \,di = \int \frac{f_i^2 t^2}{ p_i} \left( \frac{1}{2} - \frac{f_i t}{6 p_i} + \frac{f_i^2 t^2}{12 p_i^2}  \ldots \right) di $$
We find that the terms in the parenthesis on the right hand side can be simplified. We set $x_i = \frac{f_i t}{p_i}$ and can derive the following:
$$\left( \frac{1}{2} - \frac{x_i}{6} + \frac{x_i}{12}  \ldots \right) = \sum_{k=0}^\infty \frac{(-1)^k x_i^k}{(k+1)(k+2)} = \frac{(x_i +1)\log(x_i+1)-x_i}{x_i^2}$$
This should not be surprising; it's very closely related to the original formula for the Kullbeck-Liebler divergence. In fact, we didn't need Taylor series except to know to subtract off the pesky $t f_i$ term. Therefore, we don't need to worry about the convergence, this manipulation is valid without the series. Therefore,
$$KL(p(t), p) = \int \frac{f_i^2 t^2}{ p_i} \left(  \frac{( x_i +1)\log(x_i+1)-x_i}{x_i^2} \right) di $$
In order for this to make sense, we need to make sure that $x_i=  \frac{f_i t}{p_i}  \geq -1$. However, $\frac{f_i}{p_i} = \frac{q_i}{p_i} - 1  \geq -1$. Even better, it turns out that $ \frac{( x_i +1)\log(x_i+1)-x_i}{x_i^2}  \leq 1$ on its domain. With this, we are done, because this implies
$$KL(q,p)< I_p(f,f).$$
This implies that we can bound the Kullback-Liebler divergence by the Fisher information metric evaluated on a particular vector $f$. Since the KL-divergence can blow up, it's worthwhile to see what happens in this case. Whenever this happens, the tangent vector $f$ at $p$ is large in the Fisher metric. 
