6
$\begingroup$

Let $P$ be a distribution on a set $U\times V$ with marginal distributions $P_X$ and $P_Y$.

Suppose we have two values $d_x, d_y\in\mathbb R$, and we want to find the distribution $Q$ absolutely continuous with respect to $P$ that minimizes

$$\mathrm{D}(Q\|P)$$

given $\mathrm{D}(Q_X\|P_X) = d_x$ and $\mathrm{D}(Q_Y\|P_Y) = d_y$.

What can we say about $Q$? Do we even know that such a distribution exists? Or can there be an infinite sequence of $Q'$ with respectively smaller $\mathrm{D}(Q'\|P)$? I'm particularly interested in what the marginals of $Q$ look like.

If instead we had fixed $E_P[(X,Y)]$ (assuming now $X,Y\in\mathbb R$), we know from e.g. Corollary 12.1. in Yury Polyanskiy and Yihong Wu that the distribution minimizing $\mathrm{D}(Q\|P)$ given $E_Q[(X,Y)]=E_P[(X,Y)]$ is a titled version of $P$. That is $dQ = \frac{e^{\phi}}{Ee^{\phi}}dP$ where $\phi = \lambda_1 X+\lambda_2 Y$.

I wonder if there is a similar simple family of distributions one might restrict to given my requirement on $Q$?

Below is a visualization belonging to said Corollary 12.1.

enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Here is a related problem: Fix $Q_X$ and $Q_Y$ and ask what coupling $Q$ minimizes $D(Q||P)$. In this case and under mild assumptions, the minimum exists since the set of couplings $\Pi(Q_X,Q_Y)$ is compact in the weak topology and relative entropy is weakly lower semicontinuous. This problem is known as the Schrรถdinger problem. See this survey by Christian Lรฉonard. As you can see, in this case you can't generally expect a simple family of solutions like the one quoted.

Addressing your setting where you now optimize over marginals $Q_X, Q_Y$ satisfying the relative entropy constraints, I don't expect things become any easier. Unlike the situation you quote, these are nonconvex sets of marginals that you are constrained to. Unlike above, it isn't even clear that the desired extremizer exists since these sets are also not closed in general.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Even if there is no simple form, at least it's a tractable convex optimization problem. Minimizing $D(Q\|P)-a D(Q_1\|P_1)-b D(Q_2\|P_2)$ I think is equivalent to finding the hypercontractive norm of a positive matrix, by Lemma 1.1 in thomasahle.com/papers/supermajority.pdf . But that problem appears to possibly be NP hard, though there is no proof afaik. $\endgroup$
    – Thomas Dybdahl Ahle
    Commented Dec 9, 2020 at 13:36
  • $\begingroup$ Or maybe minimizing $\frac{D(Q\|P)}{a D(Q_1\|P_1)+b D(Q_2\|P_2)}$ actually, over all $Q$, so the scaling doesn't matter. $\endgroup$
    – Thomas Dybdahl Ahle
    Commented Dec 9, 2020 at 14:48
  • 1
    $\begingroup$ Regarding your first comment on hypercontractivity, you are mostly correct. This equivalence holds in a general sense. $P$ being $(1/a,1/b)$-hypercontractive is equivalent to the infimum of $๐ท(๐‘„||๐‘ƒ)โˆ’๐‘Ž๐ท(๐‘„1||๐‘ƒ1)โˆ’๐‘๐ท(๐‘„2||๐‘ƒ2)$ over all $Q$ being zero. More generally, the infimum of this problem will be nonzero, which by duality then corresponds to something like hypercontractivity, but with a prefactor in the norm inequality. See, e.g., page 22 here: arxiv.org/pdf/1702.06260.pdf, and references therein (in particular, Carlen and Cordero-Erausquin, 2009). $\endgroup$
    – Tom
    Commented Dec 9, 2020 at 17:46
  • 1
    $\begingroup$ to add to above, this equivalence does not actually make your problem any easier. It just converts from an entropy problem to an equivalent functional one. Except in special cases (e.g., where $P$ is product of rho-correlated Gaussians or Rademachers), a characterization of the extremizers is likely non-explicit. However, if $P$ is a product measure, you can use tensorization of Brascamp--Lieb inequalities (and their entropic equivalents) to conclude that the extremizers will also have product structure. You should also be able to see this directly. $\endgroup$
    – Tom
    Commented Dec 9, 2020 at 18:10
  • $\begingroup$ At this point I would be excited for just computability. Even an exponential time algorithm for the case where $P$ has finite support. $\endgroup$
    – Thomas Dybdahl Ahle
    Commented Dec 10, 2020 at 9:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .