Lower bound Renyi divergence between two discrete probability distributions

Question

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$.

Answer 1

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$.

Answer 2

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.