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 KL-divergence, 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})$.



Question regarding divergence
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}{1-P'(\{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\}) = 1-p\_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} + (1-p\_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{1-p\_1-p\_2}{1-q\_1-q\_2} = \lambda 
$$
and
$$
\frac{\partial F} {\partial q\_2} = -\frac{p\_2}{q\_2} + \frac{1-p\_1-p\_2}{1-q\_1-q\_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}{ 1-p\_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.


