Minimum KL-divergence on complements of L1balls Academic Article uri icon

abstract

  • Pinsker's widely used inequality upper-bounds the total variation distance $\left\Vert P-Q\right\Vert_{1}$ in terms of the Kullback–Leibler divergence $D(P\Vert Q)$ . Although, in general, a bound in the reverse direction is impossible, in many applications the quantity of interest is actually $D^{\ast}({v},Q)$ —defined, for an arbitrary fixed $Q$ , as the infimum of $D(P\Vert Q)$ over all distributions $P$ that are at least ${v}$ -far away from $Q$ in total variation. We show that $D^{\ast}({v},Q)\leq C{v}^{2}+O({v}^{3})$ , where $C=C(Q)={1}/{2}$ for balanced distributions, thereby providing a kind of reverse Pinsker inequality. Some of the structural results obtained in the course of the proof may be of independent interest. An application to large deviations is given.

publication date

  • January 1, 2014