Is there an inequality to relate the KL divergence of two joint distribution and the sum of the KL divergence of their marginals? Or in particular, is there a proof or a counter example for the following:
$D(q(x,y)\|p(x,y)) \geq D(q(x)\|p(x)) + D(q(y)\|p(y))$.
I don't think the given inequality is true (I am not sure about the reverse inequality). Recall that $$ D_{KL}(q(x,y)\| p(x,y))=\sum_{x\in \mathcal{X}}\sum_{y\in \mathcal{Y}} q(x,y)\log\bigg(\frac{q(x,y)}{p(x,y)}\bigg). $$ Consider non-identical joint distributions $p$ and $q$ over $\mathcal{X}\times\mathcal{X}$ (so $\mathcal{Y}=\mathcal{X}$), with $p(x,y)=q(x,y)=0$ for $y\neq x$ (so the supports of both distributions are on the diagonals). Then \begin{align} D_{KL}(q(x,y)\|p(x,y))&=\sum_{x_1\in \mathcal{X}}\sum_{x_2\in \mathcal{X}}q(x_1,x_2)\log\bigg(\frac{q(x_1,x_2)}{p(x_1,x_2)}\bigg)\\ &=\sum_{x\in \mathcal{X}} q(x)\log\bigg(\frac{q(x)}{p(x)}\bigg)\\ &=D_{KL}(q(x)\|p(x))=D_{KL}(q(y)\|p(y)). \end{align} In general, these are not all zero or infinite, so the stated inequality will not hold.
However, I think one can say that $$ D_{KL}(q(x,y)\|p(x,y))\geq \frac{D_{KL}(q(x)\|p(x))+D_{KL}(q(y)\|p(y))}{2}. $$ This should follow from the Chain Rule: \begin{align} D_{KL}(q(x,y)\|p(x,y))&=D_{KL}(q(x)\|p(x))+D_{KL}(q(y\vert x)\|p(y\vert x))\\ &=D_{KL}(q(y)\|p(y))+D_{KL}(q(x\vert y)\|p(x\vert y)), \end{align} summed twice and then using the nonnegativity of divergence.
