3
$\begingroup$

I am trying to understand the proof of Lemma 1 in this paper (Section 9.2).

The proof shows that given a discrete probability distribution $P=(p_1,p_2,...,p_k)$ where $p_1 \geq p_2 \geq ... \geq p_k$, and a discrete probability distribution $Q=(q_0,q_0,q_3,q_4...,q_k)$ where $q_0 = q_0 \geq q_3 \geq q_4 \geq ... \geq q_k$. Then for a fixed $P$, and a fixed $\alpha>1$, the minimizer of:

$$\min_{q_0,q_3,...,q_k} p_1(\frac{q_0}{p_1})^\alpha + p_2(\frac{q_0}{p_2})^\alpha + \sum_{i=3}^{k}p_i(\frac{q_i}{p_i})^\alpha$$

$$\text{such that:}\\ 2q_0 + q_3 + ... + q_k = 1\\q_i-q_0\leq 0 \quad i\geq 3\\-q_i\leq 0$$

Is given by $q_0 = (\frac{p_1^{1-\alpha}+p_2^{1-\alpha}}{2})^\frac{1}{1-\alpha}$ and $q_i = \frac{1-2q_0}{1-p_1-p_2}p_i$ for $i\geq 3$. I think I understand how these are found, however they then claim that plugging these quantities into the Renyi divergence formula:

$$D_\alpha := \frac{1}{1-\alpha}\log\bigg[p_1(\frac{q_0}{p_1})^\alpha + p_2(\frac{q_0}{p_2})^\alpha + \sum_{i=3}^{k}p_i(\frac{q_i}{p_i})^\alpha\bigg]$$

gives:

$$-\log\bigg[1-p_1-p_2 + 2(\frac{p_1^{1-\alpha} + p_2^{1-\alpha}}{2})^\frac{1}{1-\alpha}\bigg]\quad\quad\quad[*]$$

Perhaps I have misunderstood but I do not understand how $[*]$ is found. When I plug $q_0$ and $q_i$ into the Renyi divergence formula, I get:

\begin{equation*} \begin{split} D_\alpha &= \frac{1}{1-\alpha}\log\bigg[(p_1^{1-\alpha} + p_2^{1-\alpha})q_0^\alpha + \sum_{i=3}^{k}p_i(\frac{q_i}{p_i})^\alpha\bigg]\\ &= \frac{1}{1-\alpha}\log\bigg[(p_1^{1-\alpha} + p_2^{1-\alpha})(\frac{p_1^{1-\alpha} + p_2^{1-\alpha}}{2})^\frac{\alpha}{1-\alpha} + \sum_{i=3}^{k}p_i(\frac{q_i}{p_i})^\alpha\bigg]\\ &= \frac{1}{1-\alpha}\log\bigg[2(\frac{p_1^{1-\alpha} + p_2^{1-\alpha}}{2})^\frac{1}{1-\alpha} + \sum_{i=3}^{k}p_i(\frac{q_i}{p_i})^\alpha\bigg]\\ &= \frac{1}{1-\alpha}\log\bigg[2(\frac{p_1^{1-\alpha} + p_2^{1-\alpha}}{2})^\frac{1}{1-\alpha} + \sum_{i=3}^{k}p_i(\frac{1-2q_0}{1-p_1-p_2})^\alpha\bigg]\\ &= \frac{1}{1-\alpha}\log\bigg[2(\frac{p_1^{1-\alpha} + p_2^{1-\alpha}}{2})^\frac{1}{1-\alpha} + (1-p_1-p_2)^{1-\alpha}(1-2q_0)^\alpha\bigg]\\ &= \frac{1}{1-\alpha}\log\bigg[2(\frac{p_1^{1-\alpha} + p_2^{1-\alpha}}{2})^\frac{1}{1-\alpha} + (1-p_1-p_2)^{1-\alpha}(1-2(\frac{p_1^{1-\alpha}+p_2^{1-\alpha}}{2})^\frac{1}{1-\alpha})^\alpha\bigg]\quad\quad [!] \end{split} \end{equation*}

How do I get from this to $[*]$ or is there an obvious mistake I am making?

=====

Edit: Looking again at the KKT conditions, I'm not sure now how they arrive at $q_0 = (\frac{p_1^{1-\alpha}+p_2^{1-\alpha}}{2})^\frac{1}{1-\alpha}$ and $q_i = \frac{1-2q_0}{1-p_1-p_2}p_i$ for $i\geq 3$.

Let $Q = (q_0, q_0, q_3)$

Then the Lagrangian is \begin{equation*} \begin{split} L = p_1(\frac{q_0}{p_1})^\alpha + p_2(\frac{q_0}{p_2})^\alpha + p_3(\frac{q_3}{p_3})^\alpha + \mu_1(q_3-q_0) - \mu_2q_0 - \mu_3q_3 + \lambda(2q_0 + q_3 - 1) \end{split} \end{equation*}

Differentiating and setting the slack variables to 0, gives: \begin{equation*} \begin{split} & \lambda = -\alpha(\frac{q_3}{p_3})^{\alpha - 1}\\ & 2\lambda = -\alpha(\frac{q_0}{p_1})^{\alpha - 1} - \alpha(\frac{q_0}{p_2})^{\alpha - 1} \end{split} \end{equation*}

Then $q_0 = (\frac{p_1^{1-\alpha}+p_2^{1-\alpha}}{2})^\frac{1}{1-\alpha} \iff q_3 = p_3$. However, I don't understand why $q_3$ must equal $p_3$.

$\endgroup$

2 Answers 2

3
$\begingroup$

The author is here. We did make a mistake in the formula. $q^*=\left(\frac{p_1^{1-\alpha}+p_2^{1-\alpha}}{2}\right)^{\frac{1}{1-\alpha}}$ is not the minimizer for $q_0$. It should be $\frac{q^*}{1-p_1-p_2+2q^*}$. The corresponding minimizer for $q_i$ should be $\frac{p_i}{1-p_1-p_2+2q^*}$.

I was misled by my code when I wrote the paper. In my code, I obtain the value of $Q$ by replacing $p_1$ and $p_2$ with $q_0$ and renormalize the whole thing. I forgot to reflect the renormalization in the formula.

The correct minimizers should give you the bound we proposed. We apologize for this mistake and will revise our paper. Thank you for pointing it out.

I hope this will also answer why the solver for the KKT conditions seems incorrect. I cannot recall exactly how it was derived, but I remember the key is to realize $q^*/p_i$ is the ratio between $q_0$ and $p_i$ for $i\geq 3$.

$\endgroup$
2
$\begingroup$

Welcome to MathOverflow! The following can be said regarding your post:

  1. In your definition of the Renyi divergence $D_\alpha=D_\alpha(Q||P)$, the factor $\frac1{1-\alpha}$ has to be replaced by $\frac1{\alpha-1}$ -- otherwise, your "Renyi divergence" would be negative.

  2. Even after that replacement, the result claimed in the paper is incorrect. Indeed, for $\alpha=2$, $k=3$, $(p_1,p_2,p_3)=\frac1{16}\,(7,5,4)$, and the corresponding $(q_0,q_0,q_3)$, the value of $D_\alpha(Q||P)$ will be $\ln(589/576)\approx0.022$, which is not the same as the value $\ln(48/47)\approx0.021$ of the expression $[*]$.

You may want to write to the authors of the paper for further clarification.

$\endgroup$
4
  • $\begingroup$ Thank you! Replying to your comments: 1) I copied the paper definition of Renyi divergence (the equation below (9) in the paper), can I assume then their definition is incorrect? 2) Is my deduction of Renyi divergence correct (I have marked this as [!] in the question)? Upto the incorrect $\frac{1}{1-\alpha}$ of course. $\endgroup$ Apr 24, 2019 at 17:19
  • $\begingroup$ 1) That is a typo, I think, in the display after formula (9) in that paper; the (correct) definition of $D_\alpha$ is given in formula (1) there. 2) Asking to check one's calculations or proof is not encouraged on MathOverflow. However, if you want to feel more certain about the correctness of the identity you obtained, you could check it numerically, by substituting specific values for your variables. $\endgroup$ Apr 24, 2019 at 21:35
  • $\begingroup$ Thanks, I'm not sure what the correct etiquette is re: adding a new question on top of the original question. I was working through an example and I don't fully understand the KKT minimization solution they obtain. I've added this as an edit to my question. $\endgroup$ Apr 25, 2019 at 11:59
  • $\begingroup$ Asking multiple questions in one post is not encouraged here either. I think adding questions to the post after the original question has been answered is even less desirable, as it invalidates the answer at least in part. Instead, you can just ask any additional questions separately. $\endgroup$ Apr 25, 2019 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.