4 Lower bounds on e-Rényi and e-Chernoff divergences

4.1 Separation lower bound

Lemma 4.1

✓

Let \(a \le b \in [0,1]\). Let \(\mathcal{D}_{\le a} = \{ P \in \mathcal{P}([0,1]) \mid P[\operatorname{id}] \le a\} \) and \(\mathcal{D}_{\ge b} = \{ P \in \mathcal{P}([0,1]) \mid P[\operatorname{id}] \ge b\} \) be sets of distributions on \([0,1]\) with mean constraints. Let \(B_{\le a} = \{ \operatorname{Ber}(p) \mid p \le a\} \) and \(B_{\ge a} = \{ \operatorname{Ber}(p) \mid p \ge a\} \) be sets of Bernoulli distributions with the same constraints. Then

\begin{align*} \operatorname{eR}_{1/2}(\mathcal{D}_{\le a}, \mathcal{D}_{\ge b}) & = \operatorname{eR}_{1/2}(B_{\le a}, B_{\ge b}) \: . \end{align*}

Proof ▶

First, by Lemma 3.3, since \(B_{\le a} \subseteq \mathcal{D}_{\le a}\) and \(B_{\ge b} \subseteq \mathcal{D}_{\ge b}\), we have

\begin{align*} \operatorname{eR}_{1/2}(\mathcal{D}_{\le a}, \mathcal{D}_{\ge b}) & \le \operatorname{eR}_{1/2}(B_{\le a}, B_{\ge b}) \: . \end{align*}

For the reverse inequality, we use the data processing inequality for e-Rényi divergence (Lemma 3.5). Let \(\kappa : [0,1] \rightsquigarrow \{ 0,1\} \) be the Markov kernel defined by \(\kappa (x) = \operatorname{Ber}(x)\) (the Bernoulli distribution with parameter \(x\)). Then for \(P \in \mathcal{P}([0, 1])\), \(\kappa \circ P\) is a Bernoulli distribution with parameter \(P[\operatorname{id}]\), and thus \(\kappa \circ \mathcal{D}_{\le a} = B_{\le a}\) and \(\kappa \circ \mathcal{D}_{\ge b} = B_{\ge b}\). By Lemma 3.5,

\begin{align*} \operatorname{eR}_{1/2}(B_{\le a}, B_{\ge b}) & \le \operatorname{eR}_{1/2}(\mathcal{D}_{\le a}, \mathcal{D}_{\ge b}) \: . \end{align*}

Lemma 4.2

✓

Let \(\delta \in [0,1/2]\) and let \(B_{\le \delta } = \{ \operatorname{Ber}(p) \mid p \le \delta \} \). Then

\begin{align*} \mathcal{E}_{B_{\le \delta }} & = \left\{ f : \{ 0,1\} \to \mathbb {R}_{+, \infty } \text{ measurable} \mid \exists \lambda \in \left[0, \frac{1}{\delta }\right], \: \forall x \in \{ 0, 1\} , \: f(x) \le 1 + \lambda (x - \delta )\right\} \: . \end{align*}

Proof ▶

It is easy to check that the set on the right is included in \(\mathcal{E}_{B_{\le \delta }}\).

The constraint on an e-variable \(f\) for \(B_{\le \delta }\) is that for all \(p \le \delta \),

\begin{align*} (1 - p) f(0) + p f(1) & \le 1 \: . \end{align*}

For \(p=0\) and \(p=\delta \) we thus get the two constraints

\begin{align*} f(0) & \le 1 \: , \\ f(1) & \le 1 + \frac{1 - f(0)}{\delta }(1 - \delta ) \: . \end{align*}

Let \(\lambda = \frac{1 - f(0)}{\delta }\). Then \(\lambda \in [0, \frac{1}{\delta }]\) and the second constraint can be rewritten as \(f(1) \le 1 + \lambda (1 - \delta )\). We need to check that we also have \(f(0) \le 1 + \lambda (0 - \delta )\), but the expression on the right is equal to \(f(0)\) by definition of \(\lambda \).

Lemma 4.3

✓

Let \(\delta \in [0,1/2]\) and let \(B_{\le \delta } = \{ \operatorname{Ber}(p) \mid p \le \delta \} \). Then

\begin{align*} \mathcal{U}_{\log }(\operatorname{Ber}(1/2), B_{\le \delta }) & = \frac{1}{2} \log \frac{1}{4 \delta (1 - \delta )} \: . \end{align*}

Proof ▶

We first compute \(\mathcal{E}_{B_{\le \delta }}\) with Lemma 4.2. We thus know that we can restrict the supremum over \(f \in \mathcal{E}_{B_{\le \delta }}\) to functions of the form \(f(x) = 1 + \lambda (x - \delta )\) for some \(\lambda \in [0, \frac{1}{\delta }]\).

\begin{align*} \mathcal{U}_{\log }(\operatorname{Ber}(1/2), B_{\le \delta }) & = \sup _{\lambda \in [0, \frac{1}{\delta }]} \frac{1}{2} \log (1 + \lambda (0 - \delta )) + \frac{1}{2} \log (1 + \lambda (1 - \delta )) \\ & = \frac{1}{2} \log \sup _{\lambda \in [0, \frac{1}{\delta }]} \left((1 - \lambda \delta )(1 + \lambda (1 - \delta ))\right) \: . \end{align*}

The function \((1 - \lambda \delta )(1 + \lambda (1 - \delta ))\) reaches its maximum at \(\lambda ^* = \frac{1 - 2\delta }{2\delta (1 - \delta )}\) which is in the interval \([0, \frac{1}{\delta }]\) since \(\delta \in [0,1/2]\). Its value at the optimum is \(\frac{1}{4 \delta (1 - \delta )}\).

Lemma 4.4

✓

Let \(\delta \in [0,1/2]\). Let \(B_{\le \delta } = \{ \operatorname{Ber}(p) \mid p \le \delta \} \) and \(B_{\ge 1 - \delta } = \{ \operatorname{Ber}(p) \mid p \ge 1 - \delta \} \) be sets of Bernoulli distributions with mean constraints. Then

\begin{align*} \operatorname{eR}_{1/2}(B_{\le \delta }, B_{\ge 1 - \delta }) & = \log \frac{1}{4 \delta (1 - \delta )} \: . \end{align*}

Proof ▶

By Lemma 3.15 for the map \(\phi : \{ 0,1\} \to \{ 0,1\} \) defined by \(\phi (0) = 1\) and \(\phi (1) = 0\), we have

\begin{align*} \operatorname{eR}_{1/2}(B_{\le \delta }, B_{\ge 1 - \delta }) & = 2 \inf _{R \in \mathcal{P}(\{ 0,1\} ), \: \phi _* R = R} \mathcal{U}_{\log }(R, B_{\le \delta }) \\ & = 2 \mathcal{U}_{\log }\left(\operatorname{Ber}(1/2), B_{\le \delta }\right) \: . \end{align*}

We now use Lemma 4.3 to conclude.

Lemma 4.5

✓

\begin{align*} \operatorname{eC}(B_{\le \delta }, B_{\ge 1 - \delta }) & = \frac{1}{2} \log \frac{1}{4 \delta (1 - \delta )} \: . \end{align*}

Proof ▶

By Lemma 3.17, we have

\begin{align*} \operatorname{eC}(B_{\le \delta }, B_{\ge 1 - \delta }) & = \frac{1}{2} \operatorname{eR}_{1/2}(B_{\le \delta }, B_{\ge 1 - \delta }) \: . \end{align*}

We now use Lemma 4.4 to conclude.

Lemma 4.6

✓

Let \(\delta \in [0,1/2]\). Let \(\mathcal{D}_{\le \delta } = \{ P \in \mathcal{P}([0,1]) \mid P[\operatorname{id}] \le \delta \} \) and \(\mathcal{D}_{\ge 1 - \delta } = \{ P \in \mathcal{P}([0,1]) \mid P[\operatorname{id}] \ge 1 - \delta \} \) be sets of distributions on \([0,1]\) with mean constraints. Then

\begin{align*} \operatorname{eR}_{1/2}(\mathcal{D}_{\le \delta }, \mathcal{D}_{\ge 1 - \delta }) & = \log \frac{1}{4 \delta (1 - \delta )} \: . \end{align*}

Proof ▶

By Lemma 4.1, we have

\begin{align*} \operatorname{eR}_{1/2}(\mathcal{D}_{\le \delta }, \mathcal{D}_{\ge 1 - \delta }) & = \operatorname{eR}_{1/2}(B_{\le \delta }, B_{\ge 1 - \delta }) \: . \end{align*}

We now use Lemma 4.4 to conclude.

Lemma 4.7

✓

\begin{align*} \operatorname{eC}(\mathcal{D}_{\le \delta }, \mathcal{D}_{\ge 1 - \delta }) & = \frac{1}{2} \log \frac{1}{4 \delta (1 - \delta )} \: . \end{align*}

Proof ▶

By Lemma 3.17, we have

\begin{align*} \operatorname{eC}(\mathcal{D}_{\le \delta }, \mathcal{D}_{\ge 1 - \delta }) & = \frac{1}{2} \operatorname{eR}_{1/2}(\mathcal{D}_{\le \delta }, \mathcal{D}_{\ge 1 - \delta }) \: . \end{align*}

We now use Lemma 4.6 to conclude.

Theorem 4.8

✓

Let \(\mathcal{P},\mathcal{Q} \subseteq \mathcal{P}(\mathcal{X})\) be two sets of probability measures. Suppose that there exists a measurable function \(f_0 : \mathcal{X} \to \mathbb {R}_{+,\infty }\) which is less than 1 and \(\delta \in [0,1/2]\) such that

\begin{align*} \forall P \in \mathcal{P}, \: P[f_0] & \le \delta \: , \\ \forall Q \in \mathcal{Q}, \: Q[f_0] & \ge 1 - \delta \: . \end{align*}

Then

\begin{align*} \operatorname{eR}_{1/2}(\mathcal{P}, \mathcal{Q}) & \ge \log \frac{1}{4\delta (1 - \delta )} \: . \end{align*}

Proof ▶

By Lemma 3.6 for the function \(f_0\), we have

\begin{align*} \operatorname{eR}_{1/2}(\mathcal{P}, \mathcal{Q}) & \ge \operatorname{eR}_{1/2}(f_0 \circ \mathcal{P}, f_0 \circ \mathcal{Q}) \: . \end{align*}

\(f_0 \circ \mathcal{P} \subseteq \{ P \in \mathcal{P}([0,1]) \mid P[\operatorname{id}] \le \delta \} \) and \(f_0 \circ \mathcal{Q} \subseteq \{ P \in \mathcal{P}([0,1]) \mid P[\operatorname{id}] \ge 1 - \delta \} \). By Lemma 3.3, we thus have

\begin{align*} \operatorname{eR}_{1/2}(f_0 \circ \mathcal{P}, f_0 \circ \mathcal{Q}) & \ge \operatorname{eR}_{1/2}(\mathcal{D}_{\le \delta }, \mathcal{D}_{\ge 1 - \delta }) \: . \end{align*}

We now use Lemma 4.6 to conclude.

Theorem 4.9

✓

\begin{align*} \forall P \in \mathcal{P}, \: P[f_0] & \le \delta \: , \\ \forall Q \in \mathcal{Q}, \: Q[f_0] & \ge 1 - \delta \: . \end{align*}

Then

\begin{align*} \operatorname{eC}(\mathcal{P}, \mathcal{Q}) & \ge \frac{1}{2} \log \frac{1}{4\delta (1 - \delta )} \: . \end{align*}

Proof ▶

By Lemma 3.8 for the function \(f_0\), we have

\begin{align*} \operatorname{eC}(\mathcal{P}, \mathcal{Q}) & \ge \operatorname{eC}(f_0 \circ \mathcal{P}, f_0 \circ \mathcal{Q}) \: . \end{align*}

\begin{align*} \operatorname{eC}(f_0 \circ \mathcal{P}, f_0 \circ \mathcal{Q}) & \ge \operatorname{eC}(\mathcal{D}_{\le \delta }, \mathcal{D}_{\ge 1 - \delta }) \: . \end{align*}

We now use Lemma 4.7 to conclude.

4.2 Data processing inequality through KL duality

\begin{align*} \sup _{f \in \mathcal{E}_{\mathcal{Q}}} P[\log f] & = \inf _{Q \in \mathcal{Q}_{\operatorname{eff}}} \operatorname{KL}(P, Q) \\ & \ge \inf _{Q \in \mathcal{Q}_{\operatorname{eff}}} \operatorname{KL}(\kappa \circ P, \kappa \circ Q) \\ & = \inf _{Q' \in \kappa \circ \mathcal{Q}_{\operatorname{eff}}} \operatorname{KL}(\kappa \circ P, Q’) \\ & \ge \inf _{Q' \in (\kappa \circ \mathcal{Q})_{\operatorname{eff}}} \operatorname{KL}(\kappa \circ P, Q’) \\ & = \sup _{g \in \mathcal{E}_{\kappa \circ \mathcal{Q}}} (\kappa \circ P)[\log g] \: . \end{align*}

The first inequality is the data processing inequality for KL divergence. The second inequality comes from \(\kappa \circ \mathcal{Q}_{\operatorname{eff}} \subseteq (\kappa \circ \mathcal{Q})_{\operatorname{eff}}\), which we proved in Lemma 2.54.