Let $p$ and $q$ be the distributions of random variables $x_1$ and $x_2$, and consider $p'$ and $q'$ to be the distributions of $g(x_1)$ and $g(x_2)$.

For an invertible function $g$, it's true that

$$D_{KL}(p||q) = D_{KL}(p'||q')$$

But suppose $g$ is not invertible. Then we have the weaker constraint

$$D_{KL}(p||q) \geq D_{KL}(p'||q')$$

For $g(x) = 0$, the RHS is 0. Are there any constraints weaker than invertibility that we can put on $g$ in order to bound how loose the inequality is?

I'm primarily interested in continuous random variables, although I guess any bounds on discrete variables would also be interesting.

Intuitively, the reason why the inequality points in that direction is that parts of $p$ to which $q$ assigned low probability may be "folded" into the same region as parts of $p$ to which $q$ assigned high probability -- maybe it's possible to add a constraint on the amount of "folding" that happens.

For some motivation, there is a paper on reparameterizing the space of permutation matrices to be differentiable. This is done by transforming a bunch of Gumbel noise using the (non-invertible) Sinkhorn operator. The KL of the transformed result can't be easily computed, so the authors take the KL of the gumbel noise, and use it to lower bound the ELBO.

To make the question more limited, we could say $p$ and $q$ have full support over $\mathbb{R}$ and are infinitely differentiable. I'm not sure how to constrain $g$ to make the problem feasible, but here's one guess at a starting point (i'm open to strengthening or weakening the definition of niceness to get some interesting results):

Let's say $g$ is $c$-nice w.r.t $x \sim p$ if $$\max_{g^{-1}} D_{KL}(x || g^{-1} g(x)) \leq c$$ where $g^{-1}$ is a right inverse of $g$: $g \circ g^{-1} = \text{Id}$. I'm not sure on whether the divergence should go this way or the other way around yet. If both $g$ is $c$-nice wrt $p$ and $q$, can we get a bound? Or maybe just $q$ being $c$-nice is enough?

Intuitively, if $p$ is uniform -1 to 1 and $q$ is uniform 0 to 1, then $g = \text{abs}$ would have been a problem, bringing the KL from infinity to 0. However if say $g$ must be $c$-nice, then such a $g$ is no longer allowed, because $g^{-1}(y) = -y$ would mean $g$ is no longer nice wrt $q$.

  • $\begingroup$ The situation is too broad to permit any useful answer. Could you focus the question by limiting the class of distributions or the class of functions $g$? Fairly severe limitations are needed before the inequality will not be tight. $\endgroup$ – whuber Apr 15 at 12:43
  • $\begingroup$ @whuber well, I was kind of asking "what's the weakest constraint that gives some nontrivial bound on the difference or ratio of the LHS and the RHS of the inequality". i've added one such constraint i came up with which i feel might lead somewhere $\endgroup$ – shimao Apr 15 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.