Suppose $p$ and $q$ are two discrete distributions. Given a positive constant $\beta\in(0,1)$, we create a new discrete distribution $y$ such that $$ \frac{y\left( x \right)}{p\left( x \right)}=\frac{\left( \frac{q\left( x \right)}{p\left( x \right)} \right) ^{1-\beta}}{\mathbb{E} _{x\sim p}\left[ \left( \frac{q\left( x \right)}{p\left( x \right)} \right) ^{1-\beta} \right]}, $$ or equivalently $$ y\left( x \right) =\frac{q\left( x \right) ^{1-\beta}p\left( x \right) ^{\beta}}{\sum_x{q\left( x \right) ^{1-\beta}p\left( x \right) ^{\beta}}}. $$ Under these conditions, can this inequality $$ \mathrm{KL}\left( y\parallel q \right) \ge \beta\, \mathrm{KL}\left( p\parallel q \right) $$ hold? If not, what's the counter-example?
5
-
1$\begingroup$ Inequalities close to this hold, but I don't have time to check this one. See Annealing Between Distributions by Averaging Moments. They show that the distribution $y$ that minimizes $$f(y) :=(1-\beta)\mathsf{KL}(y||q) +\beta \mathsf{KL}(y||p)$$ takes the form $y\propto q^{1-\beta}p^\beta$. We then have that $$f(q) \geq f(y)\implies \beta \mathsf{KL}(q||p) \geq (1-\beta)\mathsf{KL}(y||q)+\beta\mathsf{KL}(y||p).$$ I don't know if a modified argument can get your inequality. $\endgroup$– Mark Schultz-WuCommented Sep 23, 2023 at 17:05
-
1$\begingroup$ Also note that your KL between a distribution and a geometric mixture has been studied in other places, e.g. here, where it is computed for geometric mixtures of Gaussians. I think the content of that paper is enough to check your inequality for Gaussians. I would recommend doing this (it should be quite quick), as it may be sufficient to produce a quick counterexample to your inequality. $\endgroup$– Mark Schultz-WuCommented Sep 23, 2023 at 17:07
-
$\begingroup$ Couldn't prove it but in case is useful I got that $\mathrm{KL}(y||q)\ge\beta\mathrm{KL}(pq||q)$, Wikipedia list the next form of the Hölder's ineq: $ (\sum_{k=1}^n |x_k|^r|y_k|^s)^{r+s}\le(\sum_{k=1}^n |x_k|^{r+s})^{r}( \sum_{k=1}^n |y_k|^{r+s})^{s}$ for $(r,s)\in\mathbb{R}_+, $ setting $x_k=q(x),y_k=p(x),r=1-\beta,s=\beta$ we get, $ \sum_{x=1}^n q(x)^{1-\beta}p(x)^\beta\le(\sum_{x=1}^n q(x))^{1-\beta}( \sum_{x=1}^n p(x))^{1-\beta}=1\cdot 1=1 \Rightarrow\frac{q(x)^{1-\beta}p(x)^\beta}{\sum_{x=1}^n q(x)^{1-\beta}p(x)^\beta}\ge q(x)^{1-\beta}p(x)^\beta $ Therefore: $\endgroup$– DabedCommented Sep 23, 2023 at 21:23
-
$\begingroup$ $ \mathrm{KL}(y||q)\\ =\sum_{x=1}^n\frac{q(x)^{1-\beta}p(x)^\beta}{\sum_{x=1}^n q(x)^{1-\beta}p(x)^\beta}\ln \frac{q(x)^{1-\beta}p(x)^\beta}{\sum_{x=1}^n q(x)^{1-\beta}p(x)^\beta}\\ \ge \sum_{x=1}^n q(x)^{1-\beta}p(x)^\beta\ln q(x)^{1-\beta}p(x)^\beta\\ \ge \sum_{x=1}^n q(x)p(x)\ln q(x)^{1-\beta}p(x)^\beta\\ =\sum_{x=1}^n (q(x)p(x)\ln p(x)^\beta+(1-\beta)q(x)p(x)\ln q(x))\qquad (q(x)<1\Rightarrow \ln q(x)<0)\\ \ge \sum_{x=1}^n q(x)p(x)\ln p(x)^\beta\\ =\beta\sum_{x=1}^n q(x)p(x)\ln p(x)\\ =\beta\sum_{x=1}^n q(x)p(x)\ln \frac{q(x)p(x)}{q(x)}\\ =\beta\mathrm{KL}(pq||q)\\ $ $\endgroup$– DabedCommented Sep 23, 2023 at 21:23
-
$\begingroup$ Thanks for your help. Here is a counter-example provided by Iosif Pinelis : p=(1/2,1/2) q= (1/100,99/100), \beta=0.1 $\endgroup$– Jiacai LiuCommented Sep 24, 2023 at 5:36
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
The answer is no. E.g., if $p_1=1/2$, $p_2=1/2$, $q_1=1/100$, $q_2=99/100$, and $\beta=1/10$, then the ratio of the left-hand side of the conjectured inequality to its right-hand is $0.00877\ldots<1$.
Jiacai Liu asked if the conjectured inequality holds in the opposite direction. The answer to this is also no. E.g., if $p_1=1/1000$, $p_2=999/1000$, $q_1=9/10$, $q_2=1/10$, and $\beta=6/10$, then the ratio of the left-hand side of the conjectured inequality to its right-hand is $1.5006\ldots>1$.
answered Sep 24, 2023 at 2:05
-
$\begingroup$ Thanks for your counter-example. It's very helpful to me. $\endgroup$ Commented Sep 24, 2023 at 5:28
-
$\begingroup$ I wonder whether this inequality always hold for the inverse direction ? That is KL(y || q ) <= \beta * KL(p || q) $\endgroup$ Commented Sep 24, 2023 at 7:01
-
$\begingroup$ @JiacaiLiu : The answer to this is also no. I have added details on this to the answer. $\endgroup$ Commented Sep 24, 2023 at 13:28
-
$\begingroup$ Thanks for your help. Since the conjectured inequality does not hold in the opposite direction, can we find a function of $\beta$ and replace the $\beta$ in the RHS of the conjectured inequality with it so that the new inequality can hold in the opposite direction ? For example, the new inequality can be $KL(y || q ) \le \sqrt{\beta} * KL(p || q)$ $\endgroup$ Commented Sep 24, 2023 at 15:22
-
$\begingroup$ @JiacaiLiu : I suggest you post your latter question in a separate post. $\endgroup$ Commented Sep 24, 2023 at 15:32