Let $E$ be a closed and convex set of distributions on a finite set $A$. Let $P',Q'\notin E$ and let $P^{\star},Q^{\star}$ be their respective estimates in $E$ with respect to the KLdivergence, i.e., $D(P'\P^{\star})=\min_{P\in E}D(P'\P)$ and similarly for $Q^{\star}$. I am wondering whether $D(P'\Q')\ge D(P^{\star}\Q^{\star})$.

$\begingroup$ Sorry, I'm not familiar with your notation (but I am not a probabilist). Could you explain in more detail? $\endgroup$– Zen HarperAug 1, 2010 at 1:02

$\begingroup$ I've explained everything except $D(P\Q)=\sum_{a\in A}P(a)\log \frac{P(a)}{Q(a)}$. I hope you know what a distribution is! A (probability)distribution on a (finite)set $A$ is a fuction $P:A\to [0,1]$ such that $\sum_{a\in A}P(a)=1$. $\endgroup$– AshokAug 1, 2010 at 5:27

5$\begingroup$ Ashok, I am fairly sure that what Zen was asking for was the definition of KullbackLeibler divergence (en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence) In future you should probably add such definitions to your question (you also assume everyone will know that by "distribution" you mean "probability distribution", rather than in the sense of Laurent Schwarz). $\endgroup$– Yemon ChoiAug 1, 2010 at 7:38

2$\begingroup$ Interesting question...perhaps you can find the answer in Csiszar's "Information Projections Revisited" "Notes on Information Geometry and Statistics" and let us know :) I have copies of those two documents I can email $\endgroup$– Yaroslav BulatovAug 15, 2010 at 3:27

$\begingroup$ I'll second Yemon: with both "pr" and "fa" tags, it was not obvious straight away what "distribution" meant in the context. $\endgroup$– Thierry ZellAug 15, 2010 at 4:30
1 Answer
The inequality $D(P'Q') \ge D(P^\star Q^\star)$ does not need to hold.
Here is an example.
Let $A$ be the set $\{1,2,3,...,n\}$. Let $E$ be the set of measures $P$ on $A$ such that $P(\{1\}) = 0$. Projecting a measure $P$ on $E$ using $D$ is equivalent to conditioning $P$ on $ A \{1\}$. Choose $P'$ and $Q'$ such that they both put equal and nonzero mass on $\{1\}$. By direct computation one sees: $D(P^\star Q^\star) = \frac{1}{1P'(\{1\})} D(P'Q') > D(P'  Q')$.
The details of the above computation are as follows.
For ease of notation set $n=3$. Let $E$ be the set of measures $P$ with $P(\{1\}) =\epsilon$; to obtain the example above, one sets $\epsilon = 0$. Let us parametrize the measures on $\{1,2,3\}$ as follows: $P(\{1\}) = p_1$, $P(\{2\}) =p_2$ and $P(\{3\}) = 1p_1 p_2$. Our problem is: $$ \inf_{ Q \in E}\left[ p_1 \log \frac{p_1}{q_1} + p_2 \log \frac{p_2}{q_2} + (1p_1 p_2) \log\frac{ 1 p_1  p_2}{ 1 q_1  q_2 } \right]. $$ Let $F$ denote the expression after the $\inf$. $F$ is strictly convex in $Q$ and therefore will have a unique optimizer. In the above coordinates, the normal to $E$ is the vector $(1,0)$. Then $$ \frac{\partial F} {\partial q_1} = \frac{p_1}{q_1} + \frac{1p_1p_2}{1q_1q_2} = \lambda $$ and $$ \frac{\partial F} {\partial q_2} = \frac{p_2}{q_2} + \frac{1p_1p_2}{1q_1q_2} = 0. $$ We have the constraint that $Q\in E$, i.e., $q_1 =\epsilon$. From the last two equalities one infers: $$ q_2 = \frac{(1\epsilon) p_2}{ 1p_1}. $$
Going back to the coordinates $(p_1,p_2,p_3)$ to denote a measure on $\{1,2,3\}$, projecting a measure on $E$ using $D$ corresponds to the following map: $$ (p_1,p_2,p_3) \rightarrow \left(\epsilon, (1\epsilon)\frac{p_2}{p_2+p_3}, (1\epsilon)\frac{p_3}{p_2 + p_3}\right). $$ For $\epsilon =0$, this is the same as conditioning $P$ on $\{2,3\}$.
One obtains the expression for the relative entropy given above by directly computing it using this formula for the projections.

$\begingroup$ although the OP probably also wants to know if it's possible that D(P* Q*) is less than D(P' Q'). I wonder if all projections onto convex sets can be expressed as some kind of conditioning, after which one could invoke results like the data processing inequality to conclude that it can't happen. $\endgroup$ Aug 16, 2010 at 8:22

$\begingroup$ Hi, one can slightly modify the above case to generate an example in which projection decreases relative entropy. The main idea appears to be this: conditioning can increase or decrease entropy; depends on what one conditions on. $\endgroup$– has2Aug 17, 2010 at 20:49

$\begingroup$ has2, in your example the projection is not unique; in fact, every member in $E$ is a projection. I hope you may be aware of the fact that projection is unique if Support of $P'$= Support of $E$; otherwise need not be. So, in such a case how did you get $D(P^\star Q^\star) = \frac{1}{1P'(\{1\})} D(P'Q') > D(P'  Q')$? $\endgroup$– AshokAug 18, 2010 at 5:52

$\begingroup$ Relative entropy (KLdivergence) is strictly convex in both of its variables. Therefore, it will always have a unique minimizer over any convex set. I tried to provide the details of the calculations above; they seem to be correct. $\endgroup$– has2Aug 18, 2010 at 8:42

1$\begingroup$ There is a limiting process involved in the case that reduces to conditioning. To get an example without infinite entropy, choose $1>\epsilon>0$ in the answer above. Then $D(P^\starQ^\star)=\frac{1−\epsilon}{1−p'_1}D(P'Q')$ and if one chooses $1>p'_1=q'_1>\epsilon$ and $(p'_2,p'_3)\neq(q'_2,q'_3)$, one gets $D(P^\starQ^\star)> D(P'Q')$ $\endgroup$– has2Aug 19, 2010 at 10:31