* $a_n = \Omega(b_n)$ when there exist $M > 0$ and $(c_n)_{n \in \mathbb{N}} \in [M, +\infty)^{\mathbb{N}}$ such that

$$ \exists n_0 \in \mathbb{N}, \forall n \ge n_0, \quad a_n = c_n b_n . $$

* $a_n = \Theta(b_n)$ when $a_n = \Omega(b_n)$ and $b_n = \Omega(a_n)$.

These notations may be used in addition to other notations of the problem when there is no ambiguity, for instance when $\Theta$ also refers to the parameter space later. All the different parameters are considered as series of $n$, the sample size. For $x \in (0, +\infty)$, $\lceil x \rceil := \inf_{y \in \mathbb{N} \cap [x, +\infty)} y$. For a differentiable $f: E \to \mathbb{R}$ where $E$ is a Euclidean space, $\nabla f(x)$ refers to its gradient at the point $x$. When sub-scripted by a subset of variables, $\nabla_{\theta} f(x)$ refers to the gradient at the point $x$ of $f$ restricted to the variables in $\theta$. We say that a function is $L$-smooth if it is differentiable and if its gradient in $L$-Lipschitz. A function $f: \Theta \to \mathbb{R}$ where $\Theta$ is convex is said to be $\lambda$-strongly convex if

$$ \forall x, y \in \Theta, f(y) \ge f(x) + \nabla f(x)^T (y - x) + \frac{\lambda}{2} \|y - x\|^2 . $$

Furthermore, a function is said to be $\lambda$-strongly concave if its opposite is $\lambda$-strongly convex.

# B Similarity functions

## B.1 The case of $(\epsilon, \delta)$-differential privacy

($\epsilon, \delta$)-differential privacy allows to compare conditional distributions for datasets depending on their Hamming distance. In particular, characterizing the pushforward of a distribution by a private mechanism in not an easy task. We overtake that difficulty with a technique that we call *anchoring*. Informally, an anchor is a function that, given multiple datasets, decides a common dataset to exploit so called *group privacy* of $(\epsilon, \delta)$-DP mechanisms and to give numerically tractable results.

**Fact 6** (($\epsilon, \delta$)-DP Group Privacy). Given $\epsilon \in \mathbb{R}_{+*}$ and $\delta \in [0, 1)$, if a randomized mechanism $\mathfrak{M}: \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ is $(\epsilon, \delta)$-differentially private, then, for all $\mathbf{X}, \mathbf{Y} \in \mathcal{X}^n$ and all measurable $S \subseteq \text{codom}(\mathfrak{M})$, we have

$$ \mathbb{P}_{\mathfrak{M}}(\mathfrak{M}(\mathbf{X}) \in S) \le e^{\epsilon d_{\text{ham}}(\mathbf{X}, \mathbf{Y})} \mathbb{P}_{\mathfrak{M}}(\mathfrak{M}(\mathbf{Y}) \in S) + \delta d_{\text{ham}}(\mathbf{X}, \mathbf{Y}) e^{\epsilon(d_{\text{ham}}(\mathbf{X}, \mathbf{Y})-1)} . $$

### B.1.1 Global Anchoring

The first type of anchor is a global anchor, where all the marginal datasets are compared to the same one.

**Lemma 4** (Global Anchoring). *Consider an $(\epsilon, \delta)$-DP mechanism $\mathfrak{M}$, a test function*

$\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$, and datasets $\mathbf{X}_1, \dots, \mathbf{X}_N \in \mathcal{X}^n$. For any anchor function $\Lambda: (\mathcal{X}^n)^N \to \mathcal{X}^n$, we have

$$ \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}}(\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \ge \frac{N-1}{N} e^{-\epsilon \max_i d_{\text{ham}}(\mathbf{X}_i, \Lambda)} - e^{-\epsilon} \delta \max_i d_{\text{ham}}(\mathbf{X}_i, \Lambda) $$

where $\Lambda$ is a shorthand for $\Lambda(\mathbf{X}_1, \dots, \mathbf{X}_N)$.

*Proof.* By the group privacy property (see Fact 6), we have for each $i \in \{1, \dots, N\}$

$$ \mathbb{P}_{\mathfrak{M}}(\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \ge e^{-\epsilon d_{\text{ham}}(\mathbf{X}_i, \Lambda)} \mathbb{P}_{\mathfrak{M}}(\Psi(\mathfrak{M}(\Lambda)) \neq i) - e^{-\epsilon} \delta d_{\text{ham}}(\mathbf{X}_i, \Lambda) . $$
We then consider the two-point anchor defined in Remark 1 and get using (21) that for every $1 \le i, j \le N$,

$$ \begin{aligned} & \mathbb{P}_{\mathfrak{M}}(\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) + \mathbb{P}_{\mathfrak{M}}(\Psi(\mathfrak{M}(\mathbf{X}_j)) \neq j) \\ & \ge e^{-\epsilon \lceil d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)/2 \rceil} - 2e^{-\epsilon \delta \lceil d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)/2 \rceil}. \end{aligned} $$

□

### B.1.3 The special case of $(\epsilon, 0)$-DP

The following lemma yields a bound on the KL divergence between the output distributions of an $(\epsilon, 0)$-DP mechanism applied to different datasets.

**Lemma 6.** If a randomized mechanism $\mathfrak{M}: \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ is $(\epsilon, 0)$-DP, then

$$ \forall \mathbf{X}, \mathbf{Y} \in \mathcal{X}^n, \quad \frac{d\mathbb{P}_{\mathfrak{M}(\mathbf{X})}}{d\mathbb{P}_{\mathfrak{M}(\mathbf{Y})}} \le e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon}, \quad \mathbb{P}_{\mathfrak{M}(\mathbf{X})} - \text{almost surely} $$

where $\frac{d\mathbb{P}_{\mathfrak{M}(\mathbf{X})}}{d\mathbb{P}_{\mathfrak{M}(\mathbf{Y})}}$ is the Radon-Nikodym density of the distribution of the output of the mechanism with input $\mathbf{X}$, with respect to the distribution of the output of the mechanism with input $\mathbf{Y}$. As a consequence,

$$ \forall \mathbf{X}, \mathbf{Y} \in \mathcal{X}^n, \quad \text{KL}(\mathfrak{M}(\mathbf{X}) \| \mathfrak{M}(\mathbf{Y})) \le \epsilon d_{\text{ham}}(\mathbf{X}, \mathbf{Y}). $$

*Proof.* By the group privacy property (see Fact 6), it is clear that the measurable sets of null measure for $\mathbb{P}_{\mathfrak{M}(\mathbf{X})}$ are exactly the measurable sets of null measure for $\mathbb{P}_{\mathfrak{M}(\mathbf{Y})}$. In particular, $\mathbb{P}_{\mathfrak{M}(\mathbf{X})} \ll \mathbb{P}_{\mathfrak{M}(\mathbf{Y})}$ and hence $p := \frac{d\mathbb{P}_{\mathfrak{M}(\mathbf{X})}}{d\mathbb{P}_{\mathfrak{M}(\mathbf{Y})}}$ exists. By group privacy property again for each measurable set $S \subseteq \text{codom}(\mathfrak{M})$ we have

$$ \begin{aligned} \mathbb{P}_{\mathfrak{M}(\mathbf{Y})}(S) &\ge e^{-\epsilon d_{\text{ham}}(\mathbf{X}, \mathbf{Y})} \mathbb{P}_{\mathfrak{M}(\mathbf{X})}(S) \\ &= e^{-\epsilon d_{\text{ham}}(\mathbf{X}, \mathbf{Y})} \int_S pd\mathbb{P}_{\mathfrak{M}(\mathbf{Y})} \\ &\ge e^{-\epsilon d_{\text{ham}}(\mathbf{X}, \mathbf{Y})} \left( \inf_S p \right) \mathbb{P}_{\mathfrak{M}(\mathbf{Y})}(S). \end{aligned} $$

So, for each measurable set $S$,

$$ \mathbb{P}_{\mathfrak{M}(\mathbf{Y})}(S) > 0 \implies \inf_S p \le e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon}. $$

Furthermore, $p$ is measurable for the Borel $\sigma$-algebra of $\mathbb{R}$. In particular, for any $n \in \mathbb{N}_*$, $p^{-1}([e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon} + \frac{1}{n}, +\infty))$ is measurable. As a consequence,

$$ \forall n \in \mathbb{N}_*, \quad \mathbb{P}_{\mathfrak{M}(\mathbf{Y})} \left( p^{-1} \left( \left[ e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon} + \frac{1}{n}, +\infty \right) \right) \right) = 0 $$

and then

$$ \begin{aligned} \mathbb{P}_{\mathfrak{M}(\mathbf{Y})} \left( p^{-1} \left( \left( e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon}, +\infty \right) \right) \right) &= \mathbb{P}_{\mathfrak{M}(\mathbf{Y})} \left( p^{-1} \left( \bigcup_{n \in \mathbb{N}_*} \left[ e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon} + \frac{1}{n}, +\infty \right) \right) \right) \\ &= \mathbb{P}_{\mathfrak{M}(\mathbf{Y})} \left( \bigcup_{n \in \mathbb{N}_*} p^{-1} \left( \left[ e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon} + \frac{1}{n}, +\infty \right) \right) \right) \\ &\le \sum_{n \in \mathbb{N}_*} \mathbb{P}_{\mathfrak{M}(\mathbf{Y})} \left( p^{-1} \left( \left[ e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon} + \frac{1}{n}, +\infty \right) \right) \right) \\ &= 0 \end{aligned} $$

which proves that $\frac{d\mathbb{P}_{\mathfrak{M}(\mathbf{X})}}{d\mathbb{P}_{\mathfrak{M}(\mathbf{Y})}} \le e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon}$, $\mathbb{P}_{\mathfrak{M}(\mathbf{Y})}$-almost surely, which is also the case $\mathbb{P}_{\mathfrak{M}(\mathbf{X})}$-almost surely, thanks to the first remark of the proof. The result about the KL divergence is a direct consequence of this inequality. □
As a result,

$$
\begin{align*}
& \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\mathbf{X}_i)) \neq i) \\
& \geq \frac{1}{N} \left( \sum_{i=1}^{N} e^{-\epsilon d_{\text{ham}} (\mathbf{X}_i, \Lambda)} \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\Lambda)) \neq i) - e^{-\epsilon} \delta d_{\text{ham}} (\mathbf{X}_i, \Lambda) \right) \\
& \geq \frac{1}{N} \left( e^{-\epsilon \max_i d_{\text{ham}} (\mathbf{X}_i, \Lambda)} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\Lambda)) \neq i) \right. \\
& \qquad \left. - N e^{-\epsilon} \delta \max_i d_{\text{ham}} (\mathbf{X}_i, \Lambda) \right) \\
& = \frac{N-1}{N} e^{-\epsilon \max_i d_{\text{ham}} (\mathbf{X}_i, \Lambda)} - e^{-\epsilon} \delta \max_i d_{\text{ham}} (\mathbf{X}_i, \Lambda) ,
\end{align*}
$$

where we used $\sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\Lambda)) \neq i) = \sum_{i=1}^{N} (1 - \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\Lambda)) = i)) = N - 1$ to get the last equality. $\square$

**Remark 1** ((€, δ)-DP Le Cam Matching). When we have to find an anchor between only two datasets, we can design it optimally. Considering any $\mathbf{X}_1, \mathbf{X}_2 \in \mathcal{X}^n$, by definition these datasets disagree on exactly $d_{\text{ham}} (\mathbf{X}_1, \mathbf{X}_2)$ entries. The projection anchor $\Lambda = \Lambda_j$, $j \in \{1, 2\}$ consists in anchoring both $\mathbf{X}_1$ and $\mathbf{X}_2$ to $\mathbf{X}_j$. Consequently, we have $\max \{d_{\text{ham}} (\mathbf{X}_1, \Lambda), d_{\text{ham}} (\mathbf{X}_2, \Lambda)\} = d_{\text{ham}} (\mathbf{X}_1, \mathbf{X}_2)$. If instead we allocate in the anchor $\Lambda$ half of the disagreeing components to $\mathbf{X}_1$ and the other half to $\mathbf{X}_2$, we get an anchor that satisfies

$$ \max \{d_{\text{ham}}(\mathbf{X}_1, \Lambda), d_{\text{ham}}(\mathbf{X}_2, \Lambda)\} = \lceil d_{\text{ham}}(\mathbf{X}_1, \mathbf{X}_2) / 2 \rceil. $$

Furthermore, one can check that no anchor can achieve a better bound. With this new anchor, the direct application of Lemma 4 yields

$$
\begin{align}
& \frac{1}{2} (\mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\mathbf{X}_1)) \neq 1) + \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\mathbf{X}_2)) \neq 2)) \tag{21} \\
& \geq \frac{1}{2} e^{-\epsilon \lceil d_{\text{ham}} (\mathbf{X}_1, \mathbf{X}_2) / 2 \rceil} - e^{-\epsilon} \delta \lceil d_{\text{ham}} (\mathbf{X}_1, \mathbf{X}_2) / 2 \rceil . \nonumber
\end{align}
$$

### B.1.2 Pairwise Anchoring

The fact that one needs to control the maximum of the hamming distances between a single anchor and the marginals might be prohibitive. We give here a symmetrized version that only requires to control the hamming distances between the pairs of marginals.

**Lemma 5** (Pairwise Anchoring). Under the assumptions of Lemma 4 we have

$$
\begin{align*}
& \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\mathbf{X}_i)) \neq i) \\
& \geq \frac{1}{2N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} \left( e^{-\epsilon \lceil d_{\text{ham}} (\mathbf{X}_i, \mathbf{X}_j) / 2 \rceil} - 2e^{-\epsilon} \delta \lceil d_{\text{ham}} (\mathbf{X}_i, \mathbf{X}_j) / 2 \rceil \right) .
\end{align*}
$$

*Proof.* First we observe that

$$
\begin{align*}
& \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\mathbf{X}_i)) \neq i) \\
& = \frac{1}{2N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} (\mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\mathbf{X}_i)) \neq i) + \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\mathbf{X}_j)) \neq j)) .
\end{align*}
$$
In particular, this result allows us to apply Fano's lemma in order to obtain a similarity function that is based on anchoring the conditional distributions rather than the marginals. I.e., given, $\mathbf{X}_1, \dots, \mathbf{X}_N \in \mathcal{X}^n$, $\mathbb{P}_{\mathfrak{M}(\mathbf{X}_1), \dots, \mathbb{P}_{\mathfrak{M}(\mathbf{X}_N)}$ are anchored to $\frac{1}{N} \sum_{j=1}^N \mathbb{P}_{\mathfrak{M}(\mathbf{X}_j)}$.

**Lemma 7** ((ε, 0)-DP Fano Matching). Let $\mathbf{X}_1, \dots, \mathbf{X}_N \in \mathcal{X}^n$ and $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$,

$$ \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq 1 - \frac{1 + \frac{\epsilon}{N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)}{\ln(N)}. $$

*Proof.* By Fano's lemma (see Fact 2),

$$ \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq 1 - \frac{1 + \frac{1}{N} \sum_{i=1}^{N} \text{KL} \left( \mathbb{P}_{\mathfrak{M}(\mathbf{X}_i)} \| \frac{1}{N} \sum_{j=1}^{N} \mathbb{P}_{\mathfrak{M}(\mathbf{X}_j)} \right)}{\ln(N)}. $$

By convexity of the KL divergence with respect to its second argument (see Van Erven & Harremos (2014, Theorem 12)), it follows that

$$ \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq 1 - \frac{1 + \frac{1}{N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} \text{KL} \left( \mathbb{P}_{\mathfrak{M}(\mathbf{X}_i)} \| \mathbb{P}_{\mathfrak{M}(\mathbf{X}_j)} \right)}{\ln(N)}. \quad (22) $$

An application of Lemma 6 concludes the proof. □

## B.2 The case of $\rho$-zero concentrated differential privacy

For $\rho$-zero concentrated differential privacy, the fact that the definition uses information theoretic quantities makes things easier than with the traditional definition of privacy. In particular, the anchoring technique happens implicitly on the distributions rather than on the marginals (similarly as with the $(\epsilon, 0)$-DP case). Again, the notion of group privacy is central in our proofs.

**Fact 7** ($\rho$-zCDP Group Privacy (Bun & Steinke, 2016, Proposition 27)). Let $\rho \in \mathbb{R}_{+*}$, if a randomized mechanism $\mathfrak{M}: \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ is $\rho$-zero concentrated differentially private, then, for any $\mathbf{X}, \mathbf{Y} \in \mathcal{X}^n$ and for any $\alpha \in (1, \infty)$,

$$ D_{\alpha}(\mathfrak{M}(\mathbf{X}) \| \mathfrak{M}(\mathbf{Y})) \leq \rho d_{\text{ham}}(\mathbf{X}, \mathbf{Y})^2 \alpha. $$

**Lemma 8** ($\rho$-zCDP Le Cam Matching). Consider a $\rho$-zCDP mechanism $\mathfrak{M}$, a test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, 2\}$, and two datasets $\mathbf{X}_1, \mathbf{X}_2 \in \mathcal{X}^n$. We have

$$ \frac{1}{2} \sum_{i=1}^{2} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq \frac{1}{2} \left( 1 - \sqrt{\rho/2} d_{\text{ham}}(\mathbf{X}_1, \mathbf{X}_2) \right). $$

*Proof.* By the Neyman-Pearson lemma (see Fact 1),

$$ \frac{1}{2} \sum_{i=1}^{2} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq \frac{1}{2} (1 - \text{TV}(\mathfrak{M}(\mathbf{X}_1), \mathfrak{M}(\mathbf{X}_2))). $$

By Pinsker's lemma (see Tsybakov (2003, Lemma 2.5)), $\text{TV}(\mathbb{P}, \mathbb{Q}) \leq \sqrt{\text{KL}(\mathbb{P} \| \mathbb{Q})/2}$, and hence

$$ \begin{aligned} \frac{1}{2} \sum_{i=1}^{2} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) &\geq \frac{1}{2} \left( 1 - \sqrt{\text{KL}(\mathfrak{M}(\mathbf{X}_1) \| \mathfrak{M}(\mathbf{X}_2)) / 2} \right) \\ &= \frac{1}{2} \left( 1 - \sqrt{D_1(\mathfrak{M}(\mathbf{X}_1) \| \mathfrak{M}(\mathbf{X}_2)) / 2} \right). \end{aligned} $$
We then consider the two-point anchor defined in Remark 1 and get using (21) that for every $1 \le i, j \le N$,

$$ \begin{aligned} & \mathbb{P}_{\mathfrak{M}}(\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) + \mathbb{P}_{\mathfrak{M}}(\Psi(\mathfrak{M}(\mathbf{X}_j)) \neq j) \\ & \ge e^{-\epsilon \lceil d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)/2 \rceil} - 2e^{-\epsilon} \delta \lceil d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)/2 \rceil. \end{aligned} $$

<figure><img src="image_2.png" /></figure>

### B.1.3 The special case of $(\epsilon, 0)$-DP

The following lemma yields a bound on the KL divergence between the output distributions of an $(\epsilon, 0)$-DP mechanism applied to different datasets.

**Lemma 6.** If a randomized mechanism $\mathfrak{M}: \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ is $(\epsilon, 0)$-DP, then

$$ \forall \mathbf{X}, \mathbf{Y} \in \mathcal{X}^n, \quad \frac{d\mathbb{P}_{\mathfrak{M}(\mathbf{X})}}{d\mathbb{P}_{\mathfrak{M}(\mathbf{Y})}} \le e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon}, \quad \mathbb{P}_{\mathfrak{M}(\mathbf{X})} - \text{almost surely} $$

where $\frac{d\mathbb{P}_{\mathfrak{M}(\mathbf{X})}}{d\mathbb{P}_{\mathfrak{M}(\mathbf{Y})}}$ is the Radon-Nikodym density of the distribution of the output of the mechanism with input $\mathbf{X}$, with respect to the distribution of the output of the mechanism with input $\mathbf{Y}$. As a consequence,

$$ \forall \mathbf{X}, \mathbf{Y} \in \mathcal{X}^n, \quad \text{KL}(\mathfrak{M}(\mathbf{X}) \| \mathfrak{M}(\mathbf{Y})) \le \epsilon d_{\text{ham}}(\mathbf{X}, \mathbf{Y}). $$

*Proof.* By the group privacy property (see Fact 6), it is clear that the measurable sets of null measure for $\mathbb{P}_{\mathfrak{M}(\mathbf{X})}$ are exactly the measurable sets of null measure for $\mathbb{P}_{\mathfrak{M}(\mathbf{Y})}$. In particular, $\mathbb{P}_{\mathfrak{M}(\mathbf{X})} \ll \mathbb{P}_{\mathfrak{M}(\mathbf{Y})}$ and hence $p := \frac{d\mathbb{P}_{\mathfrak{M}(\mathbf{X})}}{d\mathbb{P}_{\mathfrak{M}(\mathbf{Y})}}$ exists. By group privacy property again for each measurable set $S \subseteq \text{codom}(\mathfrak{M})$ we have

$$ \begin{aligned} \mathbb{P}_{\mathfrak{M}(\mathbf{Y})}(S) &\ge e^{-\epsilon d_{\text{ham}}(\mathbf{X}, \mathbf{Y})} \mathbb{P}_{\mathfrak{M}(\mathbf{X})}(S) \\ &= e^{-\epsilon d_{\text{ham}}(\mathbf{X}, \mathbf{Y})} \int_S pd\mathbb{P}_{\mathfrak{M}(\mathbf{Y})} \\ &\ge e^{-\epsilon d_{\text{ham}}(\mathbf{X}, \mathbf{Y})} \left( \inf_S p \right) \mathbb{P}_{\mathfrak{M}(\mathbf{Y})}(S). \end{aligned} $$

So, for each measurable set $S$,

$$ \mathbb{P}_{\mathfrak{M}(\mathbf{Y})}(S) > 0 \implies \inf_S p \le e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon}. $$

Furthermore, $p$ is measurable for the Borel $\sigma$-algebra of $\mathbb{R}$. In particular, for any $n \in \mathbb{N}_*$, $p^{-1}([e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon} + \frac{1}{n}, +\infty))$ is measurable. As a consequence,

$$ \forall n \in \mathbb{N}_*, \quad \mathbb{P}_{\mathfrak{M}(\mathbf{Y})} \left( p^{-1} \left( \left[ e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon} + \frac{1}{n}, +\infty \right) \right) \right) = 0 $$

and then

$$ \begin{aligned} \mathbb{P}_{\mathfrak{M}(\mathbf{Y})} \left( p^{-1} \left( \left( e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon}, +\infty \right) \right) \right) &= \mathbb{P}_{\mathfrak{M}(\mathbf{Y})} \left( p^{-1} \left( \bigcup_{n \in \mathbb{N}_*} \left[ e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon} + \frac{1}{n}, +\infty \right) \right) \right) \\ &= \mathbb{P}_{\mathfrak{M}(\mathbf{Y})} \left( \bigcup_{n \in \mathbb{N}_*} p^{-1} \left( \left[ e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon} + \frac{1}{n}, +\infty \right) \right) \right) \\ &\le \sum_{n \in \mathbb{N}_*} \mathbb{P}_{\mathfrak{M}(\mathbf{Y})} \left( p^{-1} \left( \left[ e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon} + \frac{1}{n}, +\infty \right) \right) \right) \\ &= 0 \end{aligned} $$

which proves that $\frac{d\mathbb{P}_{\mathfrak{M}(\mathbf{X})}}{d\mathbb{P}_{\mathfrak{M}(\mathbf{Y})}} \le e^{d_{\text{ham}}(\mathbf{X}, \mathbf{Y})\epsilon}$, $\mathbb{P}_{\mathfrak{M}(\mathbf{Y})}$-almost surely, which is also the case $\mathbb{P}_{\mathfrak{M}(\mathbf{X})}$-almost surely, thanks to the first remark of the proof. The result about the KL divergence is a direct consequence of this inequality. □

<figure><img src="image_3.png" /></figure>

In particular, this result allows us to apply Fano's lemma in order to obtain a similarity function that is based on anchoring the conditional distributions rather than the marginals. I.e., given, $\mathbf{X}_1, \dots, \mathbf{X}_N \in \mathcal{X}^n$, $\mathbb{P}_{\mathfrak{M}(\mathbf{X}_1)}, \dots, \mathbb{P}_{\mathfrak{M}(\mathbf{X}_N)}$ are anchored to $\frac{1}{N} \sum_{j=1}^N \mathbb{P}_{\mathfrak{M}(\mathbf{X}_j)}$.
Since the Renyi divergence between a given pair of distributions $D_\alpha (\cdot, \cdot)$ is non-decreasing in $\alpha$ (see
Van Erven & Harremos (2014, Theorem 3)), we obtain for any $\alpha \in (1, +\infty)$, s

$$
\frac{1}{2} \sum_{i=1}^{2} \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\mathbf{X}_i)) \neq i) \geq \frac{1}{2} \left( 1 - \sqrt{D_{\alpha} (\mathfrak{M}(\mathbf{X}_1) \| \mathfrak{M}(\mathbf{X}_2)) / 2} \right) .
$$

Eventually, we obtain using group privacy (see Fact 7) that

$$
\frac{1}{2} \sum_{i=1}^{2} \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\mathbf{X}_i)) \neq i) \geq \frac{1}{2} \left( 1 - \sqrt{\rho\alpha/2} d_{\text{ham}} (\mathbf{X}_1, \mathbf{X}_2) \right).
$$

The supremum of the right hand side over $\alpha \in (1, +\infty)$ yields the result. $\square$

We also obtain a zero concentrated DP version of the Fano matching method that we introduced previously
for (ϵ, 0)-DP.

**Lemma 9** (ρ-zCDP Fano Matching). *Consider a ρ-zCDP mechanism *M*, a test function *Ψ* := codom (*M*) → {*1*, ..., *N*}, and datasets **X**<sub>1</sub>, ..., **X**<sub>*N*</sub> ∈ *X*<sup>*n*</sup>. We have

$$
\frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq 1 - \frac{1 + \frac{\rho}{N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} d_{\text{ham}} (\mathbf{X}_i, \mathbf{X}_j)^2}{\ln(N)} .
$$

Proof. By the inequality (22) established in the proof of Lemma 7, and using again the fact that $D_\alpha (\cdot, \cdot)$ is non-decreasing in $\alpha$ (see Van Erven & Harremos (2014, Theorem 3)), as well as the group privacy property (see Fact 7), we obtain that for any $\alpha \in (1, +\infty)$,

$$
\begin{align*}
\frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M}(\mathbf{X}_i)) \neq i) &\ge 1 - \frac{1 + \frac{1}{N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} \mathrm{KL} (\mathbb{P}_{\mathfrak{M}(\mathbf{X}_i)} \| \mathbb{P}_{\mathfrak{M}(\mathbf{X}_j)})}{\ln(N)} \\
&\ge 1 - \frac{1 + \frac{1}{N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} D_{\alpha} (\mathbb{P}_{\mathfrak{M}(\mathbf{X}_i)} \| \mathbb{P}_{\mathfrak{M}(\mathbf{X}_j)})}{\ln(N)} . \\
&\ge 1 - \frac{1 + \frac{\rho \alpha}{N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} d_{\mathrm{ham}} (\mathbf{X}_i, \mathbf{X}_j)^2}{\ln(N)} .
\end{align*}
$$

The supremum of the right-hand side over $\alpha \in (1, +\infty)$ yields the result. $\square$

C Quantitative lower bounds

In this subsection, we finally put the pieces together in order to obtain quantitative lower bounds on (11).
This subsection serves as a joint proof for Theorem 1, Theorem 2, Theorem 3 and Theorem 4.

**Immediate results on the private minimax risk.** A usual estimator (i.e. a measurable function of the samples) $\hat{\theta}$ may be viewed as randomized and almost surely constant to $\hat{\theta}$ (i.e. $\forall \mathbf{X}, \mathfrak{M}(\mathbf{X}) := \hat{\theta}(\mathbf{X})$ almost surely). As a result, it is clear that the private minimax risk is always bigger than the non-private one. For distributional tests, the result is not so obvious, and we give the following general purpose lemma that ensures that Fano's and Le Cam's regular inequalities still hold.

**Lemma 10.** Let $(\mathbb{P}_i)_{i \in \{1, \dots, N\}}$ be a family of probability distributions on $\mathcal{X}^n$ and let $\mathfrak{M}: \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ be a randomized mechanism,

$$
\inf_{\Psi:\text{codom}(\mathfrak{M}) \to \{1,\dots,N\}} \inf_{\Psi:\mathcal{X}^N \to \{1,\dots,N\}} \sum_{i=1}^{N} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \ge \sum_{i=1}^{N} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i} (\Psi(\mathbf{X}) \neq i).
$$

In particular, the inequalities in Le Cam's lemma (see Fact 1) or Fano's lemma (see Fact 2) still hold when
the test function $\Psi$ is fed with an input $\mathfrak{M}(\mathbf{X}) \in \text{codom}(\mathfrak{M})$ instead of an input $\mathbf{X} \in \mathcal{X}^n$.
**Lemma 7** ((ε, 0)-DP Fano Matching). Let $\mathbf{X}_1, \dots, \mathbf{X}_N \in \mathcal{X}^n$ and $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$,

$$ \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq 1 - \frac{1 + \frac{\epsilon}{N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)}{\ln(N)}. $$

*Proof.* By Fano's lemma (see Fact 2),

$$ \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq 1 - \frac{1 + \frac{1}{N} \sum_{i=1}^{N} \text{KL} \left( \mathbb{P}_{\mathfrak{M}(\mathbf{X}_i)} \| \frac{1}{N} \sum_{j=1}^{N} \mathbb{P}_{\mathfrak{M}(\mathbf{X}_j)} \right)}{\ln(N)}. $$

By convexity of the KL divergence with respect to its second argument (see van Erven & Harremoës (2014, Theorem 12)), it follows that

$$ \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq 1 - \frac{1 + \frac{1}{N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} \text{KL} \left( \mathbb{P}_{\mathfrak{M}(\mathbf{X}_i)} \| \mathbb{P}_{\mathfrak{M}(\mathbf{X}_j)} \right)}{\ln(N)}. \quad (22) $$

An application of Lemma 6 concludes the proof. □

## B.2 The case of ρ-zero concentrated differential privacy

For ρ-zero concentrated differential privacy, the fact that the definition uses information theoretic quantities makes things easier than with the traditional definition of privacy. In particular, the anchoring technique happens implicitly on the distributions rather than on the marginals (similarly as with the (ε, 0)-DP case). Again, the notion of group privacy is central in our proofs.

**Fact 7** ($\rho$-zCDP Group Privacy (Bun & Steinke, 2016, Proposition 27)). Let $\rho \in \mathbb{R}_{+*}$, if a randomized mechanism $\mathfrak{M}: \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ is $\rho$-zero concentrated differentially private, then, for any $\mathbf{X}, \mathbf{Y} \in \mathcal{X}^n$ and for any $\alpha \in (1, \infty)$,

$$ D_{\alpha}(\mathfrak{M}(\mathbf{X}) \| \mathfrak{M}(\mathbf{Y})) \leq \rho d_{\text{ham}}(\mathbf{X}, \mathbf{Y})^2 \alpha. $$

**Lemma 8** ($\rho$-zCDP Le Cam Matching). Consider a $\rho$-zCDP mechanism $\mathfrak{M}$, a test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, 2\}$, and two datasets $\mathbf{X}_1, \mathbf{X}_2 \in \mathcal{X}^n$. We have

$$ \frac{1}{2} \sum_{i=1}^{2} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq \frac{1}{2} \left( 1 - \sqrt{\rho/2} d_{\text{ham}}(\mathbf{X}_1, \mathbf{X}_2) \right). $$

*Proof.* By the Neyman-Pearson lemma (see Fact 1),

$$ \frac{1}{2} \sum_{i=1}^{2} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq \frac{1}{2} (1 - \text{TV}(\mathfrak{M}(\mathbf{X}_1), \mathfrak{M}(\mathbf{X}_2))). $$

By Pinsker's lemma (see Tsybakov (2009, Lemma 2.5)), $\text{TV}(\mathbb{P}, \mathbb{Q}) \leq \sqrt{\text{KL}(\mathbb{P} \| \mathbb{Q})/2}$, and hence

$$ \begin{aligned} \frac{1}{2} \sum_{i=1}^{2} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) &\geq \frac{1}{2} \left( 1 - \sqrt{\text{KL}(\mathfrak{M}(\mathbf{X}_1) \| \mathfrak{M}(\mathbf{X}_2))/2} \right) \\ &= \frac{1}{2} \left( 1 - \sqrt{D_1(\mathfrak{M}(\mathbf{X}_1) \| \mathfrak{M}(\mathbf{X}_2))/2} \right). \end{aligned} $$

Since the Renyi divergence between a given pair of distributions $D_{\alpha}(\cdot \| \cdot)$ is non-decreasing in $\alpha$ (see van Erven & Harremoës (2014, Theorem 3)), we obtain for any $\alpha \in (1, +\infty)$, s

$$ \frac{1}{2} \sum_{i=1}^{2} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq \frac{1}{2} \left( 1 - \sqrt{D_{\alpha}(\mathfrak{M}(\mathbf{X}_1) \| \mathfrak{M}(\mathbf{X}_2))/2} \right). $$
Proof. Let $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$ be a test function. Then,

$$
\begin{align*}
\sum_{i=1}^{N} \mathbb{P}_{\mathbf{X} \sim \mathcal{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) &= \sum_{i=1}^{N} \int \mathbb{P}_{\mathbf{X} \sim \mathcal{P}_i} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) d\mathbb{P}_{\mathfrak{M}} \\
&= \int \sum_{i=1}^{N} \mathbb{P}_{\mathbf{X} \sim \mathcal{P}_i} ((\Psi \circ \mathfrak{M})(\mathbf{X}) \neq i) d\mathbb{P}_{\mathfrak{M}} \\
&\geq \int_{\Psi' : \mathcal{X}^N \to \{1, \dots, N\}} \inf_{i=1}^{N} \sum_{\mathbf{X} \sim \mathcal{P}_i} (\Psi'(\mathbf{X}) \neq i) d\mathbb{P}_{\mathfrak{M}} \\
&= \inf_{\Psi' : \mathcal{X}^N \to \{1, \dots, N\}} \sum_{i=1}^{N} \mathbb{P}_{\mathbf{X} \sim \mathcal{P}_i} (\Psi'(\mathbf{X}) \neq i) .
\end{align*}
$$

Taking the infimum over $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$ concludes the proof. $\square$

<figure><img src="image_2.png" /></figure>

**The case of two hypotheses ($N=2$).** At first, we look at the implications of couplings between pairs of distributions. Given $\mathbb{P}_1$ and $\mathbb{P}_2$ distributions on $\mathcal{X}^n$, a direct implication of Lemma 10 and of Le Cam's lemma (see Fact 1) is that independently on the privacy condition $\mathcal{C}$ imposed on $\mathfrak{M}$,

$$
\max_{i \in \{1,2\}} \mathbb{P}_{\mathbf{X} \sim \mathcal{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \geq \frac{1}{2} (1 - \text{TV}(\mathbb{P}_1, \mathbb{P}_2)) .
$$

This is the first ingredient in the proof of Theorem 1 and Theorem 2 that we now detail.

**Proof of Theorem 1:** When $\mathfrak{M}$ is $(\epsilon, \delta)$-DP, the generic bound of Theorem 5 applied with the Le Cam matching technique described in Theorem 6 and the coupling $\pi^{\infty}(\mathbb{P}_1, \mathbb{P}_2)$ leads to

$$
\begin{align*}
\max_{i \in \{1,2\}} \mathbb{P}_{\mathbf{X} \sim \mathcal{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) &\ge \frac{1}{2} \mathbb{E}_{(\mathbf{X}_1, \mathbf{X}_2) \sim \pi^{\infty}(\mathbb{P}_1, \mathbb{P}_2)} \left( e^{-\epsilon d_{\text{ham}}(\mathbf{X}_1, \mathbf{X}_2)} \right) \\
&\phantom{\ge} - e^{-\epsilon} \delta \mathbb{E}_{(\mathbf{X}_1, \mathbf{X}_2) \sim \pi^{\infty}(\mathbb{P}_1, \mathbb{P}_2)} (d_{\text{ham}}(\mathbf{X}_1, \mathbf{X}_2)) \\
&\ge \frac{1}{2} \left(1 - (1 - e^{-n\epsilon}) \Delta_{1,2}\right) - e^{-\epsilon} \delta n \Delta_{1,2} \\
&= \frac{1}{2} \left(1 - (1 - e^{-n\epsilon} + 2ne^{-\epsilon}\delta) \text{TV}(\mathbb{P}_1, \mathbb{P}_2)\right) .
\end{align*}
$$

where in the second line we denote $\Delta_{1,2} := \mathbb{P}_{(\mathbf{X}_1, \mathbf{X}_2) \sim \pi^{\infty}(\mathbb{P}_1, \mathbb{P}_2)} (\mathbf{X}_1 \neq \mathbf{X}_2)$ and in the last line we use that $\Delta_{1,2} = \text{TV}(\mathbb{P}_1, \mathbb{P}_2)$ with the chosen coupling. Similarly, in the case of product distributions, with the same matching but $\pi^{\otimes}(\mathbb{P}_1^{\otimes n}, \mathbb{P}_2^{\otimes n})$ we obtain as a consequence of Lemma 2

$$
\begin{align*}
\max_{i \in \{1,2\}} \mathbb{P}_{\mathbf{X} \sim \mathcal{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) & \\
\geq & \frac{1}{2} \left( (1 - (1 - e^{-\epsilon}) \text{TV}(\mathbb{P}_1, \mathbb{P}_2))^n - 2ne^{-\epsilon} \delta \text{TV}(\mathbb{P}_1, \mathbb{P}_2) \right) .
\end{align*}
$$

**Proof of Theorem 2:** When $\mathfrak{M}$ is $\rho$-DP, the generic bound of Theorem 5 applied with the Le Cam matching technique described in Theorem 7 and the coupling $\pi^{\infty}(\mathbb{P}_1, \mathbb{P}_2)$ leads to

$$
\begin{align*}
\max_{i \in \{1,2\}} \mathbb{P}_{\mathbf{X} \sim \mathcal{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) &\ge \frac{1}{2} \left(1 - \sqrt{\rho/2} \mathbb{E}_{(\mathbf{X}_1, \mathbf{X}_2) \sim \pi^{\infty}(\mathbb{P}_1, \mathbb{P}_2)} (d_{\text{ham}}(\mathbf{X}_1, \mathbf{X}_2))\right) \\
&\ge \frac{1}{2} \frac{1}{2} \left(1 - \sqrt{\rho/2} n \Delta_{1,2}\right) \\
&= \frac{1}{2} \left(1 - n \sqrt{\rho/2} \text{TV}(\mathbb{P}_1, \mathbb{P}_2)\right).
\end{align*}
$$
Eventually, we obtain using group privacy (see Fact 7) that

$$ \frac{1}{2} \sum_{i=1}^{2} \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq \frac{1}{2} \left( 1 - \sqrt{\rho\alpha/2} d_{\text{ham}} (\mathbf{X}_1, \mathbf{X}_2) \right). $$

The supremum of the right hand side over $\alpha \in (1, +\infty)$ yields the result. □

We also obtain a zero concentrated DP version of the Fano matching method that we introduced previously for $(\epsilon, 0)$-DP.

**Lemma 9 (ρ-zCDP Fano Matching).** Consider a ρ-zCDP mechanism $\mathfrak{M}$, a test function $\Psi := \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$, and datasets $\mathbf{X}_1, \dots, \mathbf{X}_N \in \mathcal{X}^n$. We have

$$ \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\mathbf{X}_i)) \neq i) \geq 1 - \frac{1 + \frac{\rho}{N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} d_{\text{ham}} (\mathbf{X}_i, \mathbf{X}_j)^2}{\ln(N)}. $$

*Proof.* By the inequality (22) established in the proof of Lemma 7, and using again the fact that $D_\alpha (\cdot, \cdot)$ is non-decreasing in $\alpha$ (see van Erven & Harremoës (2014, Theorem 3)), as well as the group privacy property (see Fact 7), we obtain that for any $\alpha \in (1, +\infty)$,

$$ \begin{aligned} \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M} (\mathbf{X}_i)) \neq i) &\geq 1 - \frac{1 + \frac{1}{N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} \text{KL} (\mathbb{P}_{\mathfrak{M}(\mathbf{X}_i)} \| \mathbb{P}_{\mathfrak{M}(\mathbf{X}_j)})}{\ln(N)} \\ &\geq 1 - \frac{1 + \frac{1}{N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} D_\alpha (\mathbb{P}_{\mathfrak{M}(\mathbf{X}_i)} \| \mathbb{P}_{\mathfrak{M}(\mathbf{X}_j)})}{\ln(N)} \\ &\geq 1 - \frac{1 + \frac{\rho\alpha}{N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} d_{\text{ham}} (\mathbf{X}_i, \mathbf{X}_j)^2}{\ln(N)}. \end{aligned} $$

The supremum of the right-hand side over $\alpha \in (1, +\infty)$ yields the result. □

## C Quantitative lower bounds

In this subsection, we finally put the pieces together in order to obtain quantitative lower bounds on (11). This subsection serves as a joint proof for Theorem 1, Theorem 2, Theorem 3 and Theorem 4.

**Immediate results on the private minimax risk.** A usual estimator (i.e. a measurable function of the samples) $\hat{\theta}$ may be viewed as randomized and almost surely constant to $\hat{\theta}$ (i.e. $\forall \mathbf{X}, \mathfrak{M}(\mathbf{X}) := \hat{\theta}(\mathbf{X})$ almost surely). As a result, it is clear that the private minimax risk is always bigger than the non-private one. For distributional tests, the result is not so obvious, and we give the following general purpose lemma that ensures that Fano's and Le Cam's regular inequalities still hold.

**Lemma 10.** Let $(\mathbb{P}_i)_{i \in \{1, \dots, N\}}$ be a family of probability distributions on $\mathcal{X}^n$ and let $\mathfrak{M} : \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ be a randomized mechanism,

$$ \inf_{\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}} \sum_{i=1}^{N} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \geq \inf_{\Psi: \mathcal{X}^N \to \{1, \dots, N\}} \sum_{i=1}^{N} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i} (\Psi(\mathbf{X}) \neq i). $$

In particular, the inequalities in Le Cam's lemma (see Fact 1) or Fano's lemma (see Fact 2) still hold when the test function $\Psi$ is fed with an input $\mathfrak{M}(\mathbf{X}) \in \text{codom}(\mathfrak{M})$ instead of an input $\mathbf{X} \in \mathcal{X}^n$.
where in the second line we denote $\Delta_{1,2} := \mathbb{P}(\mathbf{X}_1, \mathbf{X}_2) \sim \pi^{\infty}(\mathbb{P}_1, \mathbb{P}_2) (\mathbf{X}_1 \neq \mathbf{X}_2)$ and in the last line we use that $\Delta_{1,2} = \text{TV}(\mathbb{P}_1, \mathbb{P}_2)$ with the chosen coupling. Similarly, in the case of product distributions, with the same matching but $\pi^{\otimes}(\mathbb{P}_1^{\otimes n}, \mathbb{P}_2^{\otimes n})$ we obtain as a consequence of Lemma 2

$$ \max_{i \in \{1,2\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \geq \frac{1}{2} \left(1 - n\sqrt{\rho/2\text{TV}(\mathbb{P}_1, \mathbb{P}_2)}\right). $$

**The case of arbitrary many hypotheses ($N \geq 2$).** Given $\mathbb{P}_1, \dots, \mathbb{P}_N$ distributions on $\mathcal{X}^n$, a direct implication of Lemma 10 and of Fano's lemma (see Fact 2) is that independently on the privacy condition $\mathcal{C}$ imposed on $\mathfrak{M}$, for any $\mathbb{Q}$ such that $\mathbb{P}_i \ll \mathbb{Q}$ for all $i$,

$$ \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \geq 1 - \frac{1 + \frac{1}{N} \sum_{i=1}^{N} \text{KL}(\mathbb{P}_i \| \mathbb{Q})}{\ln(N)}. $$

Again, this serves as the first ingredient of the proof of Theorem 3 and Theorem 4 that we now detail.

**Proof of Theorem 3:** When $\mathfrak{M}$ is $(\epsilon, \delta)$-DP, the generic bound of Theorem 5 applied with the pairwise anchoring technique described in Theorem 6 and the coupling $\pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N)$ leads to (since $\lceil n/2 \rceil \leq n$ for each integer $n \geq 0$)

$$ \begin{aligned} & \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \\ & \geq \frac{1}{2N^2} \mathbb{E}(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N) \left( \sum_{i=1}^N \sum_{j=1}^N e^{-\epsilon d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)} \right. \\ & \qquad \left. - 2e^{-\epsilon} \delta d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j) \right) \\ & \stackrel{\text{Lemma 1}}{\geq} \frac{1}{2N^2} \left( \sum_{i=1}^N \sum_{j=1}^N (1 - (1 - e^{-n\epsilon}) \Delta_{i,j}) - 2e^{-\epsilon} \delta n \Delta_{i,j} \right) \\ & \geq \frac{1}{2} - \frac{1 - e^{-n\epsilon} + 2ne^{-\epsilon}\delta}{2N^2} \sum_{i,j} \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)} \end{aligned} $$

where in the second line we denote $\Delta_{i,j} := \mathbb{P}(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N) (\mathbf{X}_i \neq \mathbf{X}_j)$ and in the last line we use that $\Delta_{i,j} \leq \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}$ with the chosen coupling. Similarly, in the case of product distributions, with the same matching but the product coupling $\pi^{\otimes}(\mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N^{\otimes n})$ we obtain as a consequence of Lemma 2

$$ \begin{aligned} & \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \\ & \geq \frac{1}{2N^2} \sum_{i,j} \left( \left(1 - (1 - e^{-\epsilon}) \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}\right)^n \right. \\ & \qquad \left. - 2ne^{-\epsilon} \delta \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)} \right). \end{aligned} $$

When $\delta = 0$, the generic bound of Theorem 5 applied with the Fano matching technique described in Theorem 6 and the coupling $\pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N)$ leads to

$$ \begin{aligned} & \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \\ & \geq 1 - \frac{1 + \frac{\epsilon}{N^2} \sum_{i=1}^N \sum_{j=1}^N \mathbb{E}(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N) (d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j))}{\ln N} \\ & \stackrel{\text{Lemma 1}}{\geq} 1 - \frac{1 + \frac{\epsilon}{N^2} \sum_{i=1}^N \sum_{j=1}^N n \Delta_{i,j}}{\ln N} \\ & \geq 1 - \frac{1 + \frac{n\epsilon}{N^2} \sum_{i=1}^N \sum_{j=1}^N \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}}{\ln N} \end{aligned} $$
Proof. Let $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$ be a test function. Then,

$$
\begin{align*}
\sum_{i=1}^{N} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) &= \sum_{i=1}^{N} \int \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) d\mathbb{P}_{\mathfrak{M}} \\
&= \int \sum_{i=1}^{N} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i} ((\Psi \circ \mathfrak{M})(\mathbf{X}) \neq i) d\mathbb{P}_{\mathfrak{M}} \\
&\geq \int_{\Psi': \mathcal{X}^N \to \{1, \dots, N\}} \inf_{i=1}^{N} \sum_{i=1}^{N} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i} (\Psi'(\mathbf{X}) \neq i) d\mathbb{P}_{\mathfrak{M}} \\
&= \inf_{\Psi': \mathcal{X}^N \to \{1, \dots, N\}} \sum_{i=1}^{N} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i} (\Psi'(\mathbf{X}) \neq i) .
\end{align*}
$$

Taking the infimum over $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$ concludes the proof. $\square$

<figure><img src="image_4.png" /></figure>

**The case of two hypotheses ($N=2$).** At first, we look at the implications of couplings between pairs of distributions. Given $\mathbb{P}_1$ and $\mathbb{P}_2$ distributions on $\mathcal{X}^n$, a direct implication of Lemma 10 and of Le Cam's lemma (see Fact 1) is that independently on the privacy condition $\mathcal{C}$ imposed on $\mathfrak{M}$,

$$
\max_{i \in \{1,2\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \geq \frac{1}{2} (1 - \text{TV}(\mathbb{P}_1, \mathbb{P}_2)) .
$$

This is the first ingredient in the proof of Theorem 1 and Theorem 2 that we now detail.

**Proof of Theorem 1:** When $\mathfrak{M}$ is $(\epsilon, \delta)$-DP, the generic bound of Theorem 5 applied with the Le Cam matching technique described in Theorem 6 and the coupling $\pi^{\infty}(\mathbb{P}_1, \mathbb{P}_2)$ leads to

$$
\begin{align*}
\max_{i \in \{1,2\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) &\ge \frac{1}{2} \mathbb{E}_{(\mathbf{X}_1, \mathbf{X}_2) \sim \pi^{\infty}(\mathbb{P}_1, \mathbb{P}_2)} \left( e^{-\epsilon d_{\text{ham}}(\mathbf{X}_1, \mathbf{X}_2)} \right) \\
&\phantom{\ge} - e^{-\epsilon} \delta \mathbb{E}_{(\mathbf{X}_1, \mathbf{X}_2) \sim \pi^{\infty}(\mathbb{P}_1, \mathbb{P}_2)} (d_{\text{ham}}(\mathbf{X}_1, \mathbf{X}_2)) \\
&\ge \frac{1}{2} \left(1 - (1 - e^{-n\epsilon}) \Delta_{1,2}\right) - e^{-\epsilon} \delta n \Delta_{1,2} \\
&= \frac{1}{2} \left(1 - (1 - e^{-n\epsilon} + 2ne^{-\epsilon}\delta) \text{TV}(\mathbb{P}_1, \mathbb{P}_2)\right) .
\end{align*}
$$

where in the second line we denote $\Delta_{1,2} := \mathbb{P}_{(\mathbf{X}_1, \mathbf{X}_2) \sim \pi^{\infty}(\mathbb{P}_1, \mathbb{P}_2)} (\mathbf{X}_1 \neq \mathbf{X}_2)$ and in the last line we use that $\Delta_{1,2} = \text{TV}(\mathbb{P}_1, \mathbb{P}_2)$ with the chosen coupling. Similarly, in the case of product distributions, with the same matching but $\pi^{\otimes}(\mathbb{P}_1^{\otimes n}, \mathbb{P}_2^{\otimes n})$ we obtain as a consequence of Lemma 2

$$
\begin{align*}
\max_{i \in \{1,2\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) & \\
&\geq \frac{1}{2} \left( (1 - (1 - e^{-\epsilon}) \text{TV}(\mathbb{P}_1, \mathbb{P}_2))^n - 2ne^{-\epsilon} \delta \text{TV}(\mathbb{P}_1, \mathbb{P}_2) \right) .
\end{align*}
$$

**Proof of Theorem 2:** When $\mathfrak{M}$ is $\rho$-DP, the generic bound of Theorem 5 applied with the Le Cam matching technique described in Theorem 7 and the coupling $\pi^{\infty}(\mathbb{P}_1, \mathbb{P}_2)$ leads to

$$
\begin{align*}
\max_{i \in \{1,2\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) &\ge \frac{1}{2} \left(1 - \sqrt{\rho/2} \mathbb{E}_{(\mathbf{X}_1, \mathbf{X}_2) \sim \pi^{\infty}(\mathbb{P}_1, \mathbb{P}_2)} (d_{\text{ham}}(\mathbf{X}_1, \mathbf{X}_2))\right) \\
&\ge \frac{1}{2} \frac{1}{2} \left(1 - \sqrt{\rho/2} n \Delta_{1,2}\right) \\
&= \frac{1}{2} \left(1 - n \sqrt{\rho/2} \text{TV}(\mathbb{P}_1, \mathbb{P}_2)\right) .
\end{align*}
$$
where in the second line we denote $\Delta_{i,j} := \mathbb{P}(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N) (\mathbf{X}_i \neq \mathbf{X}_j)$ and in the last line we use
that $\Delta_{i,j} \le \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}$ with the chosen coupling. Similarly, in the case of product distributions, with the
same matching but the coupling $\pi^{\otimes}(\mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N^{\otimes n})$ we obtain as a consequence of Lemma 2

$$
\max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \ge 1 - \frac{1 + \frac{n\epsilon}{N^2} \sum_{i=1}^N \sum_{j=1}^N \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}}{\ln N}.
$$

**Proof of Theorem 4:** When $\mathfrak{M}$ is $\rho$-zCDP, the generic bound of Theorem 5 applied with the Fano matching technique described in Theorem 7 and the coupling $\pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N)$ leads to

$$
\begin{align*}
\max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) & \\
& \ge 1 - \frac{1 + \frac{\rho}{N^2} \sum_{i=1}^N \sum_{j=1}^N \mathbb{E}_{(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N)} (d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)^2)}{\ln N} \\
& \ge \underbrace{1 - \frac{1 + \frac{\rho}{N^2} \sum_{i=1}^N \sum_{j=1}^N n^2 \Delta_{i,j}}{\ln N}}_{\text{Lemma 1}} \\
& \ge \underbrace{1 - \frac{1 + \frac{n^2 \rho}{N^2} \sum_{i=1}^N \sum_{j=1}^N \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}}{\ln N}}
\end{align*}
$$

where in the second line we denote $\Delta_{i,j} := \mathbb{P}(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N) (\mathbf{X}_i \neq \mathbf{X}_j)$ and in the last line we use
that $\Delta_{i,j} \le \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}$ with the chosen coupling. Similarly, in the case of product distributions, with the
same matching but with the product coupling $\pi^{\otimes}(\mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N^{\otimes n})$ we obtain,

$$
\begin{align*}
\max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) & \\
& \ge 1 - \frac{1 + \frac{\rho}{N^2} \sum_{i=1}^N \sum_{j=1}^N \mathbb{E}_{(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \pi^{\otimes}(\mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N^{\otimes n})} (d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)^2)}{\ln N} \\
& \ge \underbrace{1 - \frac{1 + \frac{\rho}{N^2} \sum_{i=1}^N \sum_{j=1}^N \left(n^2 \delta_{i,j}^2 + n \delta_{i,j}\right)}{\ln N}}_{\text{Lemma 2}} \\
& \ge \underbrace{1 - \frac{1 + \frac{n^2 \rho}{N^2} \sum_{i=1}^N \sum_{j=1}^N \left(\left(\frac{2 \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}\right)^2 + \frac{1}{n} \frac{2 \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}\right)}{\ln N}}
\end{align*}
$$

where in the second line we denote $\delta_{i,j} := \mathbb{P}(X_1, \dots, X_N) \sim \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N) (X_i \neq X_j)$ and in the last line we use
that $\delta_{i,j} \le \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}$ with the chosen coupling.

D Examples of applications

This section presents three examples of applications of our lower bounds: The Bernoulli Model, the Gaussian
Model and the Uniform Model.

In the first two applications, we show that the rate at which the privacy parameters vary has an importance.
Namely, we show in both models that if the privacy parameters are too small, the private minimax risk
becomes predominant compared to the non-private one, or to put it simply, we show that under strong
privacy constraints, the performance of estimation *has* to be degraded.

Furthermore, we also show for the first model that above this threshold, the minimax risk is not degraded
by privacy, essentially meaning that we then have privacy "for free".

In contrast, in the last example we prove that the minimax risk is systematically degraded by privacy as
soon as we consider estimation procedures with increasing privacy requirements in the sense that the privacy
parameters decrease as the sample size increases.
where in the second line we denote $\Delta_{1,2} := \mathbb{P}(\mathbf{X}_1, \mathbf{X}_2) \sim \pi^{\infty}(\mathbb{P}_1, \mathbb{P}_2) (\mathbf{X}_1 \neq \mathbf{X}_2)$ and in the last line we use that $\Delta_{1,2} = \text{TV}(\mathbb{P}_1, \mathbb{P}_2)$ with the chosen coupling. Similarly, in the case of product distributions, with the same matching but $\pi^{\otimes}(\mathbb{P}_1^{\otimes n}, \mathbb{P}_2^{\otimes n})$ we obtain as a consequence of Lemma 2

$$ \max_{i \in \{1,2\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \geq \frac{1}{2} \left(1 - n\sqrt{\rho/2\text{TV}(\mathbb{P}_1, \mathbb{P}_2)}\right). $$

**The case of arbitrary many hypotheses ($N \geq 2$).** Given $\mathbb{P}_1, \dots, \mathbb{P}_N$ distributions on $\mathcal{X}^n$, a direct implication of Lemma 10 and of Fano's lemma (see Fact 2) is that independently on the privacy condition $\mathcal{C}$ imposed on $\mathfrak{M}$, for any $\mathbb{Q}$ such that $\mathbb{P}_i \ll \mathbb{Q}$ for all $i$,

$$ \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \geq 1 - \frac{1 + \frac{1}{N} \sum_{i=1}^{N} \text{KL}(\mathbb{P}_i \| \mathbb{Q})}{\ln(N)}. $$

Again, this serves as the first ingredient of the proof of Theorem 3 and Theorem 4 that we now detail.

**Proof of Theorem 3:** When $\mathfrak{M}$ is $(\epsilon, \delta)$-DP, the generic bound of Theorem 5 applied with the pairwise anchoring technique described in Theorem 6 and the coupling $\pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N)$ leads to (since $\lceil n/2 \rceil \leq n$ for each integer $n \geq 0$)

$$ \begin{aligned} \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) & \\ & \geq \frac{1}{2N^2} \mathbb{E}(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N) \left( \sum_{i=1}^N \sum_{j=1}^N e^{-\epsilon d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)} - 2e^{-\epsilon} \delta d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j) \right) \\ & \stackrel{\text{Lemma 1}}{\geq} \frac{1}{2N^2} \left( \sum_{i=1}^N \sum_{j=1}^N (1 - (1 - e^{-n\epsilon}) \Delta_{i,j}) - 2e^{-\epsilon} \delta n \Delta_{i,j} \right) \\ & \geq \frac{1}{2} - \frac{1 - e^{-n\epsilon} + 2ne^{-\epsilon}\delta}{2N^2} \sum_{i,j} \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)} \end{aligned} $$

where in the second line we denote $\Delta_{i,j} := \mathbb{P}(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N) (\mathbf{X}_i \neq \mathbf{X}_j)$ and in the last line we use that $\Delta_{i,j} \leq \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}$ with the chosen coupling. Similarly, in the case of product distributions, with the same matching but the product coupling $\pi^{\otimes}(\mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N^{\otimes n})$ we obtain as a consequence of Lemma 2

$$ \begin{aligned} \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) & \\ & \geq \frac{1}{2N^2} \sum_{i,j} \left( \left(1 - (1 - e^{-\epsilon}) \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}\right)^n - 2ne^{-\epsilon}\delta \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)} \right). \end{aligned} $$

When $\delta = 0$, the generic bound of Theorem 5 applied with the Fano matching technique described in Theorem 6 and the coupling $\pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N)$ leads to

$$ \begin{aligned} \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) & \\ & \geq 1 - \frac{1 + \frac{\epsilon}{N^2} \sum_{i=1}^N \sum_{j=1}^N \mathbb{E}(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N) (d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j))}{\ln N} \\ & \stackrel{\text{Lemma 1}}{\geq} 1 - \frac{1 + \frac{\epsilon}{N^2} \sum_{i=1}^N \sum_{j=1}^N n \Delta_{i,j}}{\ln N} \\ & \geq 1 - \frac{1 + \frac{n\epsilon}{N^2} \sum_{i=1}^N \sum_{j=1}^N \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}}{\ln N} \end{aligned} $$
## D.1 Bernoulli Model

The first application is the estimation of the proportion of a population that satisfies a certain property. It is a prime example of the application of Le Cam's lemma Fact 1 and its private counterparts Theorem 1 and Theorem 2. When we consider the parametric Bernoulli model

$$ (\mathcal{B}(\theta))_{\theta \in \Theta}, \quad \Theta = (0, 1), $$

a classical and simple estimator for estimating the true parameter $\theta^*$ from i.i.d. samples $X_1, \dots, X_n$ drawn according to $\mathcal{B}(\theta^*)$ is via the empirical average

$$ \hat{\theta} := \frac{1}{n} \sum_{i=1}^{n} X_i . $$

The quadratic risk of this estimator is

$$ \mathbb{E}((\theta^* - \hat{\theta})^2) = \frac{\theta^*(1 - \theta^*)}{n} \le \frac{1/4}{n}. $$

In order to find lower bounds on the minimax risk (with or without privacy constraints), let us investigate an $\Omega = \frac{\alpha}{4}$-packing<fnref n="3" /> with $\theta_1 := \frac{1+\alpha}{2}$ and $\theta_2 := \frac{1}{2}$.

**Regular Minimax Risk.** By the master bound (6), Le Cam's lemma (Fact 1) and Pinsker's inequality (see Tsybakov (2003, Lemma 2.5)),

$$ \begin{aligned} \mathfrak{M}_n \left( \left( \mathcal{B}(\theta)^{\otimes n} \right)_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \right) &\ge (\alpha/4)^2 \cdot \frac{1}{2} \left( 1 - \text{TV} \left( \mathcal{B}(\theta_1)^{\otimes n}, \mathcal{B}(\theta_2)^{\otimes n} \right) \right) \\ &\ge \frac{\alpha^2}{32} \left( 1 - \sqrt{\text{KL} \left( \mathcal{B}(\theta_1)^{\otimes n} \| \mathcal{B}(\theta_2)^{\otimes n} \right) / 2} \right) \\ &\ge \frac{\alpha^2}{32} \left( 1 - \sqrt{n \text{KL} \left( \mathcal{B}(\theta_1) \| \mathcal{B}(\theta_2) \right) / 2} \right). \end{aligned} $$

where we used the tensorization property of the KL divergence (see Van Erven & Harremos (2014, Theorem 28)). We can observe that when $\alpha \in [0, 1/2]$,

$$ \text{KL}(\mathcal{B}(\theta_1) \| \mathcal{B}(\theta_2)) \le \alpha^2. $$

Indeed, let us note $g(x) = \frac{1+x}{2} \ln(1+x) + \frac{1-x}{2} \ln(1-x) - x^2$. We have that $\frac{dg(x)}{dx}(x) = \frac{\ln(1+x)+\ln(1-x)}{2} - 2x$ and since $g(0) = 0$ and $x \mapsto \ln(1+x)$ is 2-Lipschitz on $[-1/2, 1/2]$, we have that $g(x) \le 0$, $\forall x \in [0, 1/2]$. In particular, when $\alpha \in [0, 1/2]$,

$$ \begin{aligned} \text{KL}(\mathcal{B}(\theta_1) \| \mathcal{B}(\theta_2)) &= \left( \theta_1 \ln \left( \frac{\theta_1}{\theta_2} \right) + (1 - \theta_1) \ln \left( \frac{1 - \theta_1}{1 - \theta_2} \right) \right) \\ &= \left( \frac{1 + \alpha}{2} \ln(1 + \alpha) + \frac{1 - \alpha}{2} \ln(1 - \alpha) \right) \\ &\le \alpha^2. \end{aligned} $$

So, with $\alpha = \frac{1}{\sqrt{n}}$, as soon as $n \ge 4$, we obtain that

$$ \mathfrak{M}_n \left( \left( \mathcal{B}(\theta)^{\otimes n} \right)_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \right) \ge \frac{\alpha^2}{32} \left( 1 - \sqrt{n\alpha^2/2} \right) = \frac{1/160}{n} = \Omega \left( \frac{1}{n} \right), $$

which concludes that the non-private minimax rate is lower bounded by a quantity of the order of $\frac{1}{n}$ and in particular, that the empirical mean estimator $\hat{\theta}$ is minimax optimal in term of rates of convergence. Furthermore, any private minimax rate also has to be of the order of at least $\frac{1}{n}$.

<footnote n="3">³With $d(\cdot, \cdot) = |\cdot - \cdot|$, see Section 1.3: an $\Omega$-packing must satisfy $d(\theta_i, \theta_j) \ge 2\Omega$, $i \ne j$.</footnote>
where in the second line we denote $\Delta_{i,j} := \mathbb{P}(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N) (\mathbf{X}_i \neq \mathbf{X}_j)$ and in the last line we use that $\Delta_{i,j} \le \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}$ with the chosen coupling. Similarly, in the case of product distributions, with the same matching but the coupling $\pi^{\otimes}(\mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N^{\otimes n})$ we obtain as a consequence of Lemma 2

$$ \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \ge 1 - \frac{1 + \frac{n\epsilon}{N^2} \sum_{i=1}^N \sum_{j=1}^N \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}}{\ln N} $$

**Proof of Theorem 4:** When $\mathfrak{M}$ is $\rho$-zCDP, the generic bound of Theorem 5 applied with the Fano matching technique described in Theorem 7 and the coupling $\pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N)$ leads to

$$ \begin{aligned} & \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \\ & \ge 1 - \frac{1 + \frac{\rho}{N^2} \sum_{i=1}^N \sum_{j=1}^N \mathbb{E}(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N) (d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)^2)}{\ln N} \\ & \stackrel{\text{Lemma 1}}{\ge} 1 - \frac{1 + \frac{\rho}{N^2} \sum_{i=1}^N \sum_{j=1}^N n^2 \Delta_{i,j}}{\ln N} \\ & \ge 1 - \frac{1 + \frac{n^2 \rho}{N^2} \sum_{i=1}^N \sum_{j=1}^N \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}}{\ln N} \end{aligned} $$

where in the second line we denote $\Delta_{i,j} := \mathbb{P}(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N) (\mathbf{X}_i \neq \mathbf{X}_j)$ and in the last line we use that $\Delta_{i,j} \le \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}$ with the chosen coupling. Similarly, in the case of product distributions, with the same matching but with the product coupling $\pi^{\otimes}(\mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N^{\otimes n})$ we obtain,

$$ \begin{aligned} & \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \\ & \ge 1 - \frac{1 + \frac{\rho}{N^2} \sum_{i=1}^N \sum_{j=1}^N \mathbb{E}(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \pi^{\otimes}(\mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N^{\otimes n}) (d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)^2)}{\ln N} \\ & \stackrel{\text{Lemma 2}}{\ge} 1 - \frac{1 + \frac{\rho}{N^2} \sum_{i=1}^N \sum_{j=1}^N (n^2 \delta_{i,j}^2 + n \delta_{i,j})}{\ln N} \\ & \ge 1 - \frac{1 + \frac{n^2 \rho}{N^2} \sum_{i=1}^N \sum_{j=1}^N \left( \left( \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)} \right)^2 + \frac{1}{n} \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)} \right)}{\ln N} \end{aligned} $$

where in the second line we denote $\delta_{i,j} := \mathbb{P}(X_1, \dots, X_N) \sim \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N) (X_i \neq X_j)$ and in the last line we use that $\delta_{i,j} \le \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1+\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}$ with the chosen coupling.

# D Examples of applications

This section presents three examples of applications of our lower bounds: The Bernoulli Model, the Gaussian Model and the Uniform Model.

In the first two applications, we show that the rate at which the privacy parameters vary has an importance. Namely, we show in both models that if the privacy parameters are too small, the private minimax risk becomes predominant compared to the non-private one, or to put it simply, we show that under strong privacy constraints, the performance of estimation *has* to be degraded.

Furthermore, we also show for the first model that above this threshold, the minimax risk is not degraded by privacy, essentially meaning that we then have privacy "for free".

In contrast, in the last example we prove that the minimax risk is systematically degraded by privacy as soon as we consider estimation procedures with increasing privacy requirements in the sense that the privacy parameters decrease as the sample size increases.
**Minimax Risk with $\epsilon$-Differential Privacy.** By the private master lower bound (10) and the product form of Le Cam's lemma for $(\epsilon, 0)$-DP (see Theorem 1) combined with the last inequality in Lemma 2 we obtain

$$ \begin{aligned} \mathfrak{M}_n \left( \epsilon\text{-DP}, (\mathcal{B}(\theta)^{\otimes n})_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \right) &\geq (\alpha/4)^2 \cdot \frac{1}{2} e^{-n\epsilon \text{TV}(\mathcal{B}(\theta_1), \mathcal{B}(\theta_2))} \\ &\geq \frac{\alpha^2}{32} e^{-n\epsilon \sqrt{\text{KL}(\mathcal{B}(\theta_1)\|\mathcal{B}(\theta_2))/2}} \\ &= \frac{\alpha^2}{32} e^{-\sqrt{(n\epsilon)^2 \alpha^2/2}} \end{aligned} $$

where we used again Pinsker's inequality.

So, with $\alpha = \frac{1}{n\epsilon}$, when $n\epsilon \geq 2$, we obtain that

$$ \mathfrak{M}_n \left( \epsilon\text{-DP}, (\mathcal{B}(\theta)^{\otimes n})_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \right) \geq \frac{1/32}{(n\epsilon)^2} e^{-\sqrt{1/2}} \geq \frac{1/80}{(n\epsilon)^2} = \Omega \left( \frac{1}{(n\epsilon)^2} \right). $$

**$\rho$-zero Concentrated Differential Privacy.** Similarly, by the product form of Le Cam's lemma for $\rho$-zCDP (see Theorem 2), we get with $\alpha = \frac{1}{n\sqrt{\rho}}$ when $n\sqrt{\rho} \geq 2$,

$$ \begin{aligned} \mathfrak{M}_n \left( \rho\text{-zCDP}, (\mathcal{B}(\theta)^{\otimes n})_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \right) &\geq \frac{\alpha^2}{32} \left( 1 - n\sqrt{\rho/2} \text{TV}(\mathcal{B}(\theta_1), \mathcal{B}(\theta_2)) \right) \\ &\geq \frac{\alpha^2}{32} \left( 1 - n\sqrt{\rho \text{KL}(\mathcal{B}(\theta_1)\|\mathcal{B}(\theta_2))/4} \right) \\ &= \frac{\alpha^2}{32} \left( 1 - \sqrt{n^2 \rho \alpha^2/4} \right) = \frac{1/64}{n^2 \rho} \\ &= \Omega \left( \frac{1}{n^2 \rho} \right). \end{aligned} $$

**Matching Upper Bounds.** Consider the Laplace mechanism $\mathfrak{M}(\mathbf{X}) := \frac{1}{n} \sum_{i=1}^n X_i + \frac{1}{n\epsilon}\text{Lap}(1)$. It is an $(\epsilon, 0)$-DP estimator $\mathbf{X}$ (Dwork et al., 2014) and its quadratic risk is $O(\frac{1}{n} + \frac{1}{(n\epsilon)^2})$. Likewise, the Gaussian mechanism $\mathfrak{M}(\mathbf{X}) = \frac{1}{n} \sum_{i=1}^n X_i + \frac{2}{n\sqrt{\rho}} \mathcal{N}(0, 1)$ is $\rho$-zCDP (Bun & Steinke, 2016) and its one is $O(\frac{1}{n} + \frac{1}{n^2\rho})$. Combined with the lower bounds established so far and with Lemma 10, this allows to conclude that in fact

$$ \mathfrak{M}_n \left( \epsilon\text{-DP}, (\mathcal{B}(\theta)^{\otimes n})_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \right) = \Theta \left( \max \left\{ \frac{1}{n}, \frac{1}{(n\epsilon)^2} \right\} \right), $$

and that this optimal rate is achieved with the Laplace mechanism, while

$$ \mathfrak{M}_n \left( \rho\text{-zCDP}, (\mathcal{B}(\theta)^{\otimes n})_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \right) = \Theta \left( \max \left\{ \frac{1}{n}, \frac{1}{n^2 \rho} \right\} \right), $$

which is an optimal rate achieved by the Gaussian mechanism.

**The Cost of Privacy.** An interesting observation for both definitions of privacy is that there exist regimes $(\epsilon \ll 1/\sqrt{n}$ or $\rho \ll 1/n)$ for which the minimax rate of convergence is degraded compared to the non private one. In other words, privacy has an unavoidable cost on utility, no matter the mechanism used. Conversely, the order of magnitude of the minimax risk is not degraded otherwise.

## D.2 Gaussian Model

The second application is the estimation of the unknown mean $\theta^* \in \mathbb{R}^d$ of multivariate normally distributed data with fixed covariance matrix $\sigma^2 I_d$. When we consider the parametric model $(\mathcal{N}(\theta, \sigma^2 I_d))_{\theta \in \Theta}, \Theta = \mathbb{R}^d$, a classical and simple estimator for estimating the mean $\theta^*$ from i.i.d. samples $X_1, \dots, X_n$ is the empirical average $\hat{\theta} := \frac{1}{n} \sum_{i=1}^n X_i$. The quadratic risk of this estimator is

$$ \mathbb{E} \left( \|\theta^* - \hat{\theta}\|^2 \right) = \frac{\sigma^2 d}{n}. \qquad (23) $$
## D.1 Bernoulli Model

The first application is the estimation of the proportion of a population that satisfies a certain property. It is a prime example of the application of Le Cam's lemma Fact 1 and its private counterparts Theorem 1 and Theorem 2. When we consider the parametric Bernoulli model

$$ (\mathcal{B}(\theta))_{\theta \in \Theta}, \quad \Theta = (0, 1), $$

a classical and simple estimator for estimating the true parameter $\theta^*$ from i.i.d. samples $X_1, \dots, X_n$ drawn according to $\mathcal{B}(\theta^*)$ is via the empirical average

$$ \hat{\theta} := \frac{1}{n} \sum_{i=1}^{n} X_i . $$

The quadratic risk of this estimator is

$$ \mathbb{E}((\theta^* - \hat{\theta})^2) = \frac{\theta^*(1 - \theta^*)}{n} \le \frac{1/4}{n}. $$

In order to find lower bounds on the minimax risk (with or without privacy constraints), let us investigate an $\Omega = \frac{\alpha}{4}$-packing<fnref n="3" /> with $\theta_1 := \frac{1+\alpha}{2}$ and $\theta_2 := \frac{1}{2}$.

**Regular Minimax Risk.** By the master bound (6), Le Cam's lemma (Fact 1) and Pinsker's inequality (see Tsybakov (2009, Lemma 2.5)),

$$ \begin{aligned} \mathfrak{M}_n \left( \left( \mathcal{B}(\theta)^{\otimes n} \right)_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \right) &\ge (\alpha/4)^2 \cdot \frac{1}{2} \left( 1 - \text{TV} \left( \mathcal{B}(\theta_1)^{\otimes n}, \mathcal{B}(\theta_2)^{\otimes n} \right) \right) \\ &\ge \frac{\alpha^2}{32} \left( 1 - \sqrt{\text{KL} \left( \mathcal{B}(\theta_1)^{\otimes n} \| \mathcal{B}(\theta_2)^{\otimes n} \right) / 2} \right) \\ &= \frac{\alpha^2}{32} \left( 1 - \sqrt{n \text{KL} \left( \mathcal{B}(\theta_1) \| \mathcal{B}(\theta_2) \right) / 2} \right). \end{aligned} $$

where we used the tensorization property of the KL divergence (see van Erven & Harremoës (2014, Theorem 28)). We can observe that when $\alpha \in [0, 1/2]$,

$$ \text{KL}(\mathcal{B}(\theta_1) \| \mathcal{B}(\theta_2)) \le \alpha^2. $$

Indeed, let us note $g(x) = \frac{1+x}{2} \ln(1+x) + \frac{1-x}{2} \ln(1-x) - x^2$. We have that $\frac{dg(x)}{dx}(x) = \frac{\ln(1+x)+\ln(1-x)}{2} - 2x$ and since $g(0) = 0$ and $x \mapsto \ln(1+x)$ is 2-Lipschitz on $[-1/2, 1/2]$, we have that $g(x) \le 0$, $\forall x \in [0, 1/2]$. In particular, when $\alpha \in [0, 1/2]$,

$$ \begin{aligned} \text{KL}(\mathcal{B}(\theta_1) \| \mathcal{B}(\theta_2)) &= \left( \theta_1 \ln \left( \frac{\theta_1}{\theta_2} \right) + (1 - \theta_1) \ln \left( \frac{1 - \theta_1}{1 - \theta_2} \right) \right) \\ &= \left( \frac{1 + \alpha}{2} \ln(1 + \alpha) + \frac{1 - \alpha}{2} \ln(1 - \alpha) \right) \\ &\le \alpha^2. \end{aligned} $$

So, with $\alpha = \frac{1}{\sqrt{n}}$, as soon as $n \ge 4$, we obtain that

$$ \mathfrak{M}_n \left( \left( \mathcal{B}(\theta)^{\otimes n} \right)_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \right) \ge \frac{\alpha^2}{32} \left( 1 - \sqrt{n\alpha^2/2} \right) = \frac{1/160}{n} = \Omega \left( \frac{1}{n} \right), $$

which concludes that the non-private minimax rate is lower bounded by a quantity of the order of $\frac{1}{n}$ and in particular, that the empirical mean estimator $\hat{\theta}$ is minimax optimal in term of rates of convergence. Furthermore, any private minimax rate also has to be of the order of at least $\frac{1}{n}$.

<footnote n="3">³With $d(\cdot, \cdot) = |\cdot - \cdot|$, see Section 1.3: an $\Omega$-packing must satisfy $d(\theta_i, \theta_j) \ge 2\Omega$, $i \ne j$.</footnote>
If we were to apply Le Cam's lemma Fact 1 or its private counterparts Theorem 1 and Theorem 2, the parameter that tunes the dimensionality $d$ would not be captured by the resulting minimax lower bounds which would thus be overly optimistic. This example forces us to use Fano's lemma Fact 2 or its private counterparts Theorem 3 or Theorem 4 in order to have a chance to capture this phenomenon.

The total variation that appears in Fano's inequality is controlled via Pinsker's inequality in terms of a Kullback-Leibler divergence, which in the case of isotropic Gaussians is known to be proportional to the squared Euclidean distance.

$$ \forall \theta_1, \theta_2 \in \Theta, \quad \mathrm{KL}(\mathcal{N}(\theta_1, \sigma^2 I_d) \| \mathcal{N}(\theta_2, \sigma^2 I_d)) = \frac{\|\theta_2 - \theta_1\|^2}{2\sigma^2}. \qquad (24) $$

This enables the use of packing results for the Euclidean norm, and minimax bounds valid in the more general case where the KL divergence is controlled by the Euclidean norm between parameters.

**Packing Choice.** In high dimension, the packing is chosen with an exponential number of hypotheses. A good way to obtain well-spread points is to use Varshamov–Gilbert's theorem

**Fact 8** (Varshamov–Gilbert's theorem (Rigollet & Hütter, 2015, Lemma 5.12)). For any $\zeta \in (0, \frac{1}{2})$ and for every dimension $d \ge 1$ there exist $N \ge e^{\frac{\zeta^2 d}{2}}$ and $w_1, \dots, w_N \in \{0, 1\}^d$ such that,

$$ i \neq j \implies d_{\mathrm{ham}}(w_i, w_j) \ge \left(\frac{1}{2} - \zeta\right) d. $$

**Minimax Lower Bounds.** We obtain the following minimax lower bounds that we factorized in a single result:

**Proposition 1.** Let $(\mathbb{P}_{\theta})_{\theta \in \Theta}$ be a family of probability distributions on the same measurable space and $\Theta$ be a subset of $\mathbb{R}^d$ with $d \ge 66$ that contains a ball of radius $r_0$ for the euclidean distance. Assume that $\gamma > 0$ is such that

$$ \forall \theta_1, \theta_2 \in \Theta, \quad \mathrm{KL}(\mathbb{P}_{\theta_1} \| \mathbb{P}_{\theta_2}) \le \gamma \|\theta_2 - \theta_1\|^2. \qquad (25) $$

Then we have the following results on the minimax rates:

$$ \mathfrak{M}_n \left( (\mathbb{P}_{\theta}^{\otimes n})_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) \ge \frac{\min \left( \frac{r_0}{\sqrt{d}}, \frac{1}{64\sqrt{n\gamma}} \right)^2 d}{32} = \Omega \left( \frac{d}{n\gamma} \right), $$

$$ \begin{aligned} \mathfrak{M}_n \left( \epsilon - DP, (\mathbb{P}_{\theta}^{\otimes n})_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) &\ge \frac{\max \left( \min \left( \frac{r_0}{\sqrt{d}}, \frac{1}{64\sqrt{n\gamma}} \right), \min \left( \frac{r_0}{\sqrt{d}}, \frac{\sqrt{d}}{64^2\sqrt{2n\epsilon\sqrt{\gamma}}} \right) \right)^2 d}{32} \\ &= \Omega \left( \max \left\{ \frac{d}{n\gamma}, \frac{d^2}{(n\epsilon)^2\gamma} \right\} \right), \end{aligned} $$

$$ \begin{aligned} \mathfrak{M}_n \left( \rho - zCDP, (\mathbb{P}_{\theta}^{\otimes n})_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) &\ge \frac{\max \left( \min \left( \frac{r_0}{\sqrt{d}}, \frac{1}{64\sqrt{n\gamma}} \right), \min \left( \frac{r_0}{\sqrt{d}}, \frac{1}{64^2 2\sqrt{2n\sqrt{\rho\gamma}}} \right) \right)^2 d}{32} = \Omega \left( \max \left\{ \frac{d}{n\gamma}, \frac{d}{n^2\rho\gamma} \right\} \right), \end{aligned} $$

when $\rho < 1$. Note that all the asymptotic expressions are taken when $r_0 > C\sqrt{d}$ for a positive constant $C$ i.e. when the parameter space is not "too small".

Note that the constraint $d \ge 66$ can be relaxed to smaller constants by changing the $\zeta$ in the application of Varshamov–Gilbert's theorem at the cost of changing the constants in the minimax lower bounds. Likewise, the constraint $\rho < 1$ can be replaced by $\rho < M$ for any positive constant $M$ at the cost again of worse constants. Since we aim to use this result in high dimension and with high privacy, those hypotheses are natural in order to simplify the expressions. Before giving the proof, we discuss some practical consequences.
**Minimax Risk with $\epsilon$-Differential Privacy.** By the private master lower bound (10) and the product form of Le Cam's lemma for $(\epsilon, 0)$-DP (see Theorem 1) combined with the last inequality in Lemma 2 we obtain

$$ \begin{aligned} \mathfrak{M}_n \left( \epsilon \text{-DP}, (\mathcal{B}(\theta)^{\otimes n})_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \right) &\geq (\alpha/4)^2 \cdot \frac{1}{2} e^{-n\epsilon \text{TV}(\mathcal{B}(\theta_1), \mathcal{B}(\theta_2))} \\ &\geq \frac{\alpha^2}{32} e^{-n\epsilon \sqrt{\text{KL}(\mathcal{B}(\theta_1) \| \mathcal{B}(\theta_2)) / 2}} \\ &= \frac{\alpha^2}{32} e^{-\sqrt{(n\epsilon)^2 \alpha^2 / 2}} \end{aligned} $$

where we used again Pinsker's inequality.

So, with $\alpha = \frac{1}{n\epsilon}$, when $n\epsilon \geq 2$, we obtain that

$$ \mathfrak{M}_n \left( \epsilon \text{-DP}, (\mathcal{B}(\theta)^{\otimes n})_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \right) \geq \frac{1/32}{(n\epsilon)^2} e^{-\sqrt{1/2}} \geq \frac{1/80}{(n\epsilon)^2} = \Omega \left( \frac{1}{(n\epsilon)^2} \right). $$

**$\rho$-zero Concentrated Differential Privacy.** Similarly, by the product form of Le Cam's lemma for $\rho$-zCDP (see Theorem 2), we get with $\alpha = \frac{1}{n\sqrt{\rho}}$ when $n\sqrt{\rho} \geq 2$,

$$ \begin{aligned} \mathfrak{M}_n \left( \rho \text{-zCDP}, (\mathcal{B}(\theta)^{\otimes n})_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \right) &\geq \frac{\alpha^2}{32} \left( 1 - n \sqrt{\rho/2} \text{TV}(\mathcal{B}(\theta_1), \mathcal{B}(\theta_2)) \right) \\ &\geq \frac{\alpha^2}{32} \left( 1 - n \sqrt{\rho \text{KL}(\mathcal{B}(\theta_1) \| \mathcal{B}(\theta_2)) / 4} \right) \\ &= \frac{\alpha^2}{32} \left( 1 - \sqrt{n^2 \rho \alpha^2 / 4} \right) = \frac{1/64}{n^2 \rho} \\ &= \Omega \left( \frac{1}{n^2 \rho} \right). \end{aligned} $$

**Matching Upper Bounds.** Consider the Laplace mechanism $\mathfrak{M}(\mathbf{X}) := \frac{1}{n} \sum_{i=1}^n X_i + \frac{1}{n\epsilon} \text{Lap}(1)$. It is an $(\epsilon, 0)$-DP estimator $\mathbf{X}$ (Dwork & Roth, 2014) and its quadratic risk is $O(\frac{1}{n} + \frac{1}{(n\epsilon)^2})$. Likewise, the Gaussian mechanism $\mathfrak{M}(\mathbf{X}) = \frac{1}{n} \sum_{i=1}^n X_i + \frac{2}{n\sqrt{\rho}} \mathcal{N}(0, 1)$ is $\rho$-zCDP (Bun & Steinke, 2016) and its one is $O(\frac{1}{n} + \frac{1}{n^2\rho})$. Combined with the lower bounds established so far and with Lemma 10, this allows to conclude that in fact

$$ \mathfrak{M}_n \left( \epsilon \text{-DP}, (\mathcal{B}(\theta)^{\otimes n})_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \right) = \Theta \left( \max \left\{ \frac{1}{n}, \frac{1}{(n\epsilon)^2} \right\} \right), $$

and that this optimal rate is achieved with the Laplace mechanism, while

$$ \mathfrak{M}_n \left( \rho \text{-zCDP}, (\mathcal{B}(\theta)^{\otimes n})_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \right) = \Theta \left( \max \left\{ \frac{1}{n}, \frac{1}{n^2 \rho} \right\} \right), $$

which is an optimal rate achieved by the Gaussian mechanism.

**The Cost of Privacy.** An interesting observation for both definitions of privacy is that there exist regimes $(\epsilon \ll 1/\sqrt{n}$ or $\rho \ll 1/n)$ for which the minimax rate of convergence is degraded compared to the non private one. In other words, privacy has an unavoidable cost on utility, no matter the mechanism used. Conversely, the order of magnitude of the minimax risk is not degraded otherwise.

## D.2 Gaussian Model

The second application is the estimation of the unknown mean $\theta^* \in \mathbb{R}^d$ of multivariate normally distributed data with fixed covariance matrix $\sigma^2 I_d$. When we consider the parametric model $(\mathcal{N}(\theta, \sigma^2 I_d))_{\theta \in \Theta}, \Theta = \mathbb{R}^d$, a classical and simple estimator for estimating the mean $\theta^*$ from i.i.d. samples $X_1, \dots, X_n$ is the empirical average $\hat{\theta} := \frac{1}{n} \sum_{i=1}^n X_i$. The quadratic risk of this estimator is

$$ \mathbb{E} \left( \| \theta^* - \hat{\theta} \|^2 \right) = \frac{\sigma^2 d}{n}. \qquad (23) $$
**The Cost of Privacy.** For Gaussians, by (23) and Proposition 1 with $\gamma = \frac{1}{2\sigma^2}$ (cf (24)) the non-private minimax risk is

$$ \mathfrak{M}_n \left( \left( \mathcal{N}(\theta, \sigma^2 I_d) \right)_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) = \Theta \left( \frac{\sigma^2 d}{n} \right), $$

hence Proposition 1 shows that there is a degradation of the private minimax rate over the non-private minimax rate in the regime $\epsilon \ll \sqrt{d/n}$ when working under $\epsilon$-DP. Note that this shift in regime depends on the dimensionality. For $\rho$-zCDP, the minimax rate of convergence is degraded as soon as $\rho \ll \frac{1}{n}$. Compared to $\epsilon$-DP, the rate at which we observe a degradation does not depend on the dimension $d$. We study an upper bound in Section 4.

*Proof of Proposition 1.* Without loss of generality, let us suppose that $0$ is the center of the ball of radius $r_0$ (without loss of generality because we are going to work on a neighborhood of $0$ but it can be translated to any point). Varshamov–Gilbert’s theorem (Fact 8) with $\zeta = \frac{1}{4}$ allows us to consider $N$ and $w_1, \dots, w_N$ and to define a packing of the form $\theta_1 := \alpha w_1, \dots, \theta_N := \alpha w_N$ such that

$$ i \neq j \implies \frac{\alpha^2 d}{4} \leq \|\theta_i - \theta_j\|^2 \leq \alpha^2 d. $$

This yields an $\Omega = \alpha\sqrt{d}/4$-packing with respect to the Euclidean metric. Since $0$ is in the interior of $\Theta$, all the $\theta_i$'s are in $\Theta$ provided that $\alpha$ is small enough. By the (non-private) master lower bound (6) and Fano's lemma (Fact 2),

$$ \begin{aligned} & \mathfrak{M}_n \left( (\mathbb{P}_{\theta}^{\otimes n})_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) \\ & \geq (\alpha \sqrt{d}/4)^2 \cdot \left( 1 - \frac{1 + \frac{1}{N} \sum_i \mathrm{KL} \left( \mathbb{P}_{\theta_i}^{\otimes n} \| \frac{1}{N} \sum_j \mathbb{P}_{\theta_j}^{\otimes n} \right)}{\ln N} \right) \\ & \stackrel{\text{Jensen's inequality}}{\geq} (\alpha \sqrt{d}/4)^2 \cdot \left( 1 - \frac{1 + \frac{1}{N^2} \sum_{i,j} \mathrm{KL} \left( \mathbb{P}_{\theta_i}^{\otimes n} \| \mathbb{P}_{\theta_j}^{\otimes n} \right)}{\ln N} \right) \\ & = (\alpha \sqrt{d}/4)^2 \cdot \left( 1 - \frac{1 + \frac{1}{N^2} \sum_{i,j} n \mathrm{KL} \left( \mathbb{P}_{\theta_i} \| \mathbb{P}_{\theta_j} \right)}{\ln N} \right) \\ & \stackrel{(25)}{\geq} \frac{\alpha^2 d}{16} \cdot \left( 1 - \frac{1 + \frac{1}{N^2} \sum_{i,j} n \gamma \|\theta_i - \theta_j\|^2}{\ln N} \right) \\ & \geq \frac{\alpha^2 d}{16} \cdot \left( 1 - \frac{1 + n \gamma \alpha^2 d}{d/32} \right), \end{aligned} $$

where in the last line we used that $N \geq e^{d/32}$ and $\|\theta_i - \theta_j\|^2 \leq \alpha^2 d$. With $\alpha := \min \left( \frac{r_0}{\sqrt{d}}, \frac{1}{64\sqrt{n\gamma}} \right)$ when $d \geq 66$ leads to

$$ \mathfrak{M}_n \left( (\mathbb{P}_{\theta}^{\otimes n})_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) \geq \frac{\min \left( \frac{r_0}{\sqrt{d}}, \frac{1}{64\sqrt{n\gamma}} \right)^2 d}{32} = \Omega \left( \frac{d}{n\gamma} \right). $$

For $\epsilon$-DP and $\rho$-zCDP, the first term in the max expressed in Proposition 1 is a direct consequence of the above bound and of Lemma 10 so we now concentrate on the other term. By the private master lower bound (10) and Fano's lemma for product distributions and $(\epsilon, 0)$-DP (see Theorem 3), arguments as above
If we were to apply Le Cam's lemma Fact 1 or its private counterparts Theorem 1 and Theorem 2, the parameter that tunes the dimensionality $d$ would not be captured by the resulting minimax lower bounds which would thus be overly optimistic. This example forces us to use Fano's lemma Fact 2 or its private counterparts Theorem 3 or Theorem 4 in order to have a chance to capture this phenomenon.

The total variation that appears in Fano's inequality is controlled via Pinsker's inequality in terms of a Kullback-Leibler divergence, which in the case of isotropic Gaussians is known to be proportional to the squared Euclidean distance.

$$ \forall \theta_1, \theta_2 \in \Theta, \quad \mathrm{KL}(\mathcal{N}(\theta_1, \sigma^2 I_d) \| \mathcal{N}(\theta_2, \sigma^2 I_d)) = \frac{\|\theta_2 - \theta_1\|^2}{2\sigma^2}. \qquad (24) $$

This enables the use of packing results for the Euclidean norm, and minimax bounds valid in the more general case where the KL divergence is controlled by the Euclidean norm between parameters.

**Packing Choice.** In high dimension, the packing is chosen with an exponential number of hypotheses. A good way to obtain well-spread points is to use Varshamov–Gilbert’s theorem

**Fact 8** (Varshamov–Gilbert’s theorem (Rigollet & Hütter, 2015, Lemma 5.12)). For any $\zeta \in (0, \frac{1}{2})$ and for every dimension $d \ge 1$ there exist $N \ge e^{\frac{\zeta^2 d}{2}}$ and $w_1, \dots, w_N \in \{0, 1\}^d$ such that,

$$ i \neq j \implies d_{\mathrm{ham}}(w_i, w_j) \ge \left(\frac{1}{2} - \zeta\right) d. $$

**Minimax Lower Bounds.** We obtain the following minimax lower bounds that we factorized in a single result:

**Proposition 1.** Let $(\mathbb{P}_{\theta})_{\theta \in \Theta}$ be a family of probability distributions on the same measurable space and $\Theta$ be a subset of $\mathbb{R}^d$ with $d \ge 66$ that contains a ball of radius $r_0$ for the euclidean distance. Assume that $\gamma > 0$ is such that

$$ \forall \theta_1, \theta_2 \in \Theta, \quad \mathrm{KL}(\mathbb{P}_{\theta_1} \| \mathbb{P}_{\theta_2}) \le \gamma \|\theta_2 - \theta_1\|^2. \qquad (25) $$

Then we have the following results on the minimax rates:

$$ \mathfrak{M}_n\left(\left(\mathbb{P}_{\theta}^{\otimes n}\right)_{\theta \in \Theta}, \|\cdot - \cdot\|, (\cdot)^2\right) \ge \frac{\min\left(\frac{r_0}{\sqrt{d}}, \frac{1}{64\sqrt{n\gamma}}\right)^2 d}{32} = \Omega\left(\frac{d}{n\gamma}\right), $$

$$ \begin{aligned} \mathfrak{M}_n\left(\epsilon-DP, \left(\mathbb{P}_{\theta}^{\otimes n}\right)_{\theta \in \Theta}, \|\cdot - \cdot\|, (\cdot)^2\right) &\ge \frac{\max\left(\min\left(\frac{r_0}{\sqrt{d}}, \frac{1}{64\sqrt{n\gamma}}\right), \min\left(\frac{r_0}{\sqrt{d}}, \frac{\sqrt{d}}{64^2\sqrt{2n\epsilon\sqrt{\gamma}}}\right)\right)^2 d}{32} \\ &= \Omega\left(\max\left\{\frac{d}{n\gamma}, \frac{d^2}{(n\epsilon)^2\gamma}\right\}\right), \end{aligned} $$

$$ \begin{aligned} \mathfrak{M}_n\left(\rho-zCDP, \left(\mathbb{P}_{\theta}^{\otimes n}\right)_{\theta \in \Theta}, \|\cdot - \cdot\|, (\cdot)^2\right) &\ge \frac{\max\left(\min\left(\frac{r_0}{\sqrt{d}}, \frac{1}{64\sqrt{n\gamma}}\right), \min\left(\frac{r_0}{\sqrt{d}}, \frac{1}{64^2\sqrt{2n\sqrt{\rho\gamma}}}\right)\right)^2 d}{32} = \Omega\left(\max\left\{\frac{d}{n\gamma}, \frac{d}{n^2\rho\gamma}\right\}\right), \end{aligned} $$

when $\rho < 1$. Note that all the asymptotic expressions are taken when $r_0 > C\sqrt{d}$ for a positive constant $C$ i.e. when the parameter space is not "too small".

Note that the constraint $d \ge 66$ can be relaxed to smaller constants by changing the $\zeta$ in the application of Varshamov–Gilbert’s theorem at the cost of changing the constants in the minimax lower bounds. Likewise, the constraint $\rho < 1$ can be replaced by $\rho < M$ for any positive constant $M$ at the cost again of worse constants. Since we aim to use this result in high dimension and with high privacy, those hypotheses are natural in order to simplify the expressions. Before giving the proof, we discuss some practical consequences.
show that

$$
\begin{align*}
\mathfrak{M}_n \left( \epsilon \text{-DP}, \left( \mathbb{P}_\theta^{\otimes n} \right)_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) &\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + \frac{2n\epsilon}{N^2} \sum_{i,j} \text{TV} \left( \mathbb{P}_{\theta_i}, \mathbb{P}_{\theta_j} \right)}{\ln N} \right) \\
&\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + \frac{2n\epsilon}{N^2} \sum_{i,j} \sqrt{\text{KL} \left( \mathbb{P}_{\theta_i} \| \mathbb{P}_{\theta_j} \right) / 2}}{\ln N} \right) \\
&\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + \frac{2n\epsilon}{N^2} \sum_{i,j} \sqrt{\gamma/2} \| \theta_i - \theta_j \|}{\ln N} \right) \\
&\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + 2n\epsilon\alpha \sqrt{\gamma/2} \sqrt{d}}{d/32} \right).
\end{align*}
$$

Again, setting $\alpha := \min \left( \frac{r_0}{\sqrt{d}}, \frac{\sqrt{d}}{64^2 \sqrt{2n\epsilon\sqrt{\gamma}}} \right)$ when $d \ge 66$ allows to conclude that

$$
\begin{align*}
\mathfrak{M}_n \left( \epsilon\text{-DP}, \left( \mathbb{P}_\theta^{\otimes n} \right)_{\theta \in \Theta}, \|\cdot - \cdot\|, (\cdot)^2 \right) &\ge \frac{\min \left( \frac{r_0}{\sqrt{d}}, \frac{\sqrt{d}}{64^2 \sqrt{2n\epsilon\sqrt{\gamma}}} \right)^2 d}{32} \\
&= \Omega \left( \frac{d^2}{(n\epsilon)^2 \gamma} \right).
\end{align*}
$$

Similarly, by Fano's lemma for product distributions and $\rho$-zCDP (see Theorem 4),

$$
\begin{align*}
\mathfrak{M}_n \left( \rho\text{-zCDP}, \left( \mathbb{P}_\theta^{\otimes n} \right)_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) & \\
&\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + \frac{4n^2 \rho}{N^2} \sum_{i,j} \frac{1}{2n} \text{TV} \left( \mathbb{P}_{\theta_i}, \mathbb{P}_{\theta_j} \right) + \text{TV} \left( \mathbb{P}_{\theta_i}, \mathbb{P}_{\theta_j} \right)^2}{\ln N} \right) \\
&\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + \frac{4n^2 \rho}{N^2} \sum_{i,j} \frac{1}{2n} \sqrt{\text{KL} \left( \mathbb{P}_{\theta_i} \| \mathbb{P}_{\theta_j} \right) / 2} + \text{KL} \left( \mathbb{P}_{\theta_i} \| \mathbb{P}_{\theta_j} \right) / 2}{\ln N} \right) \\
&\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + \frac{4n^2 \rho}{N^2} \sum_{i,j} \frac{1}{2n} \sqrt{\gamma/2} \| \theta_i - \theta_j \| + \gamma \| \theta_i - \theta_j \|^2 / 2}{\ln N} \right) \\
&\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + (2\sqrt{2n\rho\alpha}\sqrt{\gamma d} + 2n^2\rho\gamma\alpha^2 d)}{d/32} \right),
\end{align*}
$$

and setting $\alpha := \min \left( \frac{r_0}{\sqrt{d}}, \frac{1}{64^2 2 \sqrt{2n \sqrt{\rho \gamma}}} \right)$ when $d \ge 66$ concludes that (because $\rho \le 1$)

$$
\begin{align*}
\mathfrak{M}_n \left( \rho\text{-zCDP}, \left( \mathbb{P}_\theta^{\otimes n} \right)_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) &\ge \frac{\min \left( \frac{r_0}{\sqrt{d}}, \frac{1}{64^2 2 \sqrt{2n \sqrt{\rho \gamma}}} \right)^2 d}{32} \\
&= \Omega \left( \frac{d}{n^2 \rho \gamma} \right).
\end{align*}
$$

<figure><img src="image_3.png" /></figure>

### D.3 Support of Uniform Distributions

For the last example, we chose to investigate a statistical problem that has a non-private minimax rate faster than $\frac{1}{n}$. We consider the parametric model

$$ (\mathbb{P}_{\theta} := \mathcal{U}([0, \theta]))_{\theta \in \Theta}, \quad \Theta = (0, 1]. $$
**The Cost of Privacy.** For Gaussians, by (23) and Proposition 1 with $\gamma = \frac{1}{2\sigma^2}$ (cf (24)) the non-private minimax risk is

$$ \mathfrak{M}_n \left( \left( \mathcal{N}(\theta, \sigma^2 I_d) \right)_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) = \Theta \left( \frac{\sigma^2 d}{n} \right), $$

hence Proposition 1 shows that there is a degradation of the private minimax rate over the non-private minimax rate in the regime $\epsilon \ll \sqrt{d/n}$ when working under $\epsilon$-DP. Note that this shift in regime depends on the dimensionality. For $\rho$-zCDP, the minimax rate of convergence is degraded as soon as $\rho \ll \frac{1}{n}$. Compared to $\epsilon$-DP, the rate at which we observe a degradation does not depend on the dimension $d$. We study an upper bound in Section 4.

*Proof of Proposition 1.* Without loss of generality, let us suppose that $0$ is the center of the ball of radius $r_0$ (without loss of generality because we are going to work on a neighborhood of $0$ but it can be translated to any point). Varshamov–Gilbert’s theorem (Fact 8) with $\zeta = \frac{1}{4}$ allows us to consider $N$ and $w_1, \dots, w_N$ and to define a packing of the form $\theta_1 := \alpha w_1, \dots, \theta_N := \alpha w_N$ such that

$$ i \neq j \implies \frac{\alpha^2 d}{4} \leq \|\theta_i - \theta_j\|^2 \leq \alpha^2 d. $$

This yields an $\Omega = \alpha\sqrt{d}/4$-packing with respect to the Euclidean metric. Since $0$ is in the interior of $\Theta$, all the $\theta_i$'s are in $\Theta$ provided that $\alpha$ is small enough. By the (non-private) master lower bound (6) and Fano's lemma (Fact 2),

$$ \begin{aligned} & \mathfrak{M}_n \left( (\mathbb{P}_{\theta}^{\otimes n})_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) \\ & \geq (\alpha \sqrt{d}/4)^2 \cdot \left( 1 - \frac{1 + \frac{1}{N} \sum_i \mathrm{KL} \left( \mathbb{P}_{\theta_i}^{\otimes n} \| \frac{1}{N} \sum_j \mathbb{P}_{\theta_j}^{\otimes n} \right)}{\ln N} \right) \\ & \stackrel{\text{Jensen's inequality}}{\geq} (\alpha \sqrt{d}/4)^2 \cdot \left( 1 - \frac{1 + \frac{1}{N^2} \sum_{i,j} \mathrm{KL} \left( \mathbb{P}_{\theta_i}^{\otimes n} \| \mathbb{P}_{\theta_j}^{\otimes n} \right)}{\ln N} \right) \\ & = (\alpha \sqrt{d}/4)^2 \cdot \left( 1 - \frac{1 + \frac{1}{N^2} \sum_{i,j} n \mathrm{KL} \left( \mathbb{P}_{\theta_i} \| \mathbb{P}_{\theta_j} \right)}{\ln N} \right) \\ & \stackrel{(25)}{\geq} \frac{\alpha^2 d}{16} \cdot \left( 1 - \frac{1 + \frac{1}{N^2} \sum_{i,j} n \gamma \|\theta_i - \theta_j\|^2}{\ln N} \right) \\ & \geq \frac{\alpha^2 d}{16} \cdot \left( 1 - \frac{1 + n \gamma \alpha^2 d}{d/32} \right), \end{aligned} $$

where in the last line we used that $N \geq e^{d/32}$ and $\|\theta_i - \theta_j\|^2 \leq \alpha^2 d$. With $\alpha := \min \left( \frac{r_0}{\sqrt{d}}, \frac{1}{64\sqrt{n\gamma}} \right)$ when $d \geq 66$ leads to

$$ \mathfrak{M}_n \left( (\mathbb{P}_{\theta}^{\otimes n})_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) \geq \frac{\min \left( \frac{r_0}{\sqrt{d}}, \frac{1}{64\sqrt{n\gamma}} \right)^2 d}{32} = \Omega \left( \frac{d}{n\gamma} \right). $$

For $\epsilon$-DP and $\rho$-zCDP, the first term in the max expressed in Proposition 1 is a direct consequence of the above bound and of Lemma 10 so we now concentrate on the other term. By the private master lower bound (10) and Fano's lemma for product distributions and $(\epsilon, 0)$-DP (see Theorem 3), arguments as above
To exploit Le Cam's lemma we will need to control the total variation between two distributions. In this model, it can be done explicitly. The total variation between $\mathbb{P}_{\theta_1}^{\otimes n}$ and $\mathbb{P}_{\theta_2}^{\otimes n}$ can be computed as

$$TV(\mathbb{P}_{\theta_1}^{\otimes n}, \mathbb{P}_{\theta_2}^{\otimes n}) = 1 - \int_{[0,1]^n} \min \left( \pi_{\mathbb{P}_{\theta_1}^{\otimes n}}, \pi_{\mathbb{P}_{\theta_2}^{\otimes n}} \right) = 1 - \left( \frac{\min(\theta_1, \theta_2)}{\max(\theta_1, \theta_2)} \right)^n.$$

**Non-Private Minimax Risk.** By the (non-private) master lower bound (6) and Le Cam's lemma (Fact 1), applied to the $\frac{1}{2n}$-packing $\theta_1 = 1 - \frac{1}{n}$ and $\theta_2 = 1$, we have

$$\mathfrak{M}_n \left( (\mathcal{U}([0, \theta]))^{\otimes n} \right)_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \geq \frac{e^{-1}}{8n^2} = \Omega \left( \frac{1}{n^2} \right).$$

where we used that $1 - TV(\mathbb{P}_{\theta_1}^{\otimes n}, \mathbb{P}_{\theta_2}^{\otimes n}) = (1 - \frac{1}{n})^n \geq e^{-1}$. Furthermore, as we now show, the estimator $\max \mathbf{X}$ achieves this rate of convergence when $X_1, \dots, X_n \sim \mathcal{U}([0, \theta^*])$ are independent. Indeed, for any $t \in [0, \theta^*]$,

$$\mathbb{P}(\max \mathbf{X} < t) = \Pi_{i=1}^n \mathbb{P}(X_i < t) = \left(\frac{t}{\theta^*}\right)^n.$$

Hence, $\max \mathbf{X}$ has a density $\pi_{\max \mathbf{X}}$ with respect to the Lebesgue measure where

$$\forall t \in \mathbb{R}, \quad \pi_{\max \mathbf{X}}(t) = 1_{[0, \theta^*]}(t) \frac{nt^{n-1}}{\theta^{*n}},$$

so that

$$\mathbb{E}(\max \mathbf{X}) = \int_0^{\theta^*} t \left( \frac{nt^{n-1}}{\theta^{*n}} \right) dt = \frac{n}{n+1} \theta^*,$$

$$\mathbb{V}(\max \mathbf{X}) = \int_0^{\theta^*} t^2 \left( \frac{nt^{n-1}}{\theta^{*n}} \right) dt - [\mathbb{E}(\max \mathbf{X})]^2 = \theta^{*2} \left( \frac{n}{n+2} - \frac{n^2}{(n+1)^2} \right).$$

By the bias-variance tradeoff, the quadratic risk of $\max \mathbf{X}$ is thus $O(\frac{\theta^{*2}}{n^2})$. In particular, this proves that the non-private minimax rate of convergence is $\Theta(\frac{1}{n^2})$ and that $\max \mathbf{X}$ achieves this minimax rate of convergence.

**Minimax Risk with $\epsilon$-Differential Privacy.** By the private master lower bound (10) and the product form of Le Cam's private lemma for $\epsilon$-DP on product distributions (see Theorem 1 with $\delta = 0$) with the $\frac{1}{2n\epsilon}$-packing $\theta_1 = 1 - \frac{1}{n\epsilon}$ and $\theta_2 = 1$ we have when $n\epsilon > 1$

$$\mathfrak{M}_n \left( \epsilon\text{-DP}, (\mathcal{U}([0, \theta]))^{\otimes n} \right)_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \geq \frac{e^{-1}}{8(n\epsilon)^2} = \Omega \left( \frac{1}{(n\epsilon)^2} \right),$$

In particular, the rate is degraded compared to the non-private one as soon as $\epsilon$ is decreasing.

**Minimax Risk with $\rho$-zero Concentrated Differential Privacy.** Similarly, using the product form of Le Cam's private lemma for $\rho$-zCDP on product distributions (see Theorem 2) and the $\frac{1}{2n\sqrt{\rho}}$-packing $\theta_1 = 1 - \frac{1}{n\sqrt{\rho}}$ and $\theta_2 = 1$ gives that when $n\sqrt{\rho} > 1$,

$$\mathfrak{M}_n \left( \rho\text{-zCDP}, (\mathcal{U}([0, \theta]))^{\otimes n} \right)_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \geq \frac{1 - \frac{1}{\sqrt{2}}}{8n^2\rho} = \Omega \left( \frac{1}{n^2\rho} \right).$$

In particular, the rate is degraded compared to the non-private one as soon as $\rho$ is decreasing.

This example shows that when the stochastic noise due to sampling shrinks too fast (here $\max \mathbf{X}$ has quadratic risk $O(1/n^2)$), then the noise due to privacy becomes predominant. In particular, we do not observe a distinction on the rate at which $\epsilon$ or $\rho$ tends to 0 in order the conclude to a degradation of the minimax risk. It is systematically degraded.
show that

$$
\begin{align*}
\mathfrak{M}_n \left( \epsilon \text{-DP}, \left( \mathbb{P}_\theta^{\otimes n} \right)_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) &\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + \frac{2n\epsilon}{N^2} \sum_{i,j} \text{TV} \left( \mathbb{P}_{\theta_i}, \mathbb{P}_{\theta_j} \right)}{\ln N} \right) \\
&\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + \frac{2n\epsilon}{N^2} \sum_{i,j} \sqrt{\text{KL} \left( \mathbb{P}_{\theta_i} \| \mathbb{P}_{\theta_j} \right) / 2}}{\ln N} \right) \\
&\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + \frac{2n\epsilon}{N^2} \sum_{i,j} \sqrt{\gamma/2} \| \theta_i - \theta_j \|}{\ln N} \right) \\
&\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + 2n\epsilon\alpha \sqrt{\gamma/2} \sqrt{d}}{d/32} \right).
\end{align*}
$$

Again, setting $\alpha := \min \left( \frac{r_0}{\sqrt{d}}, \frac{\sqrt{d}}{64^2 \sqrt{2n\epsilon\sqrt{\gamma}}} \right)$ when $d \ge 66$ allows to conclude that

$$
\begin{align*}
\mathfrak{M}_n \left( \epsilon\text{-DP}, \left( \mathbb{P}_\theta^{\otimes n} \right)_{\theta \in \Theta}, \|\cdot - \cdot\|, (\cdot)^2 \right) &\ge \frac{\min \left( \frac{r_0}{\sqrt{d}}, \frac{\sqrt{d}}{64^2 \sqrt{2n\epsilon\sqrt{\gamma}}} \right)^2 d}{32} \\
&= \Omega \left( \frac{d^2}{(n\epsilon)^2 \gamma} \right).
\end{align*}
$$

Similarly, by Fano's lemma for product distributions and $\rho$-zCDP (see Theorem 4),

$$
\begin{align*}
\mathfrak{M}_n \left( \rho\text{-zCDP}, \left( \mathbb{P}_\theta^{\otimes n} \right)_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) & \\
&\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + \frac{4n^2 \rho}{N^2} \sum_{i,j} \frac{1}{2n} \text{TV} \left( \mathbb{P}_{\theta_i}, \mathbb{P}_{\theta_j} \right) + \text{TV} \left( \mathbb{P}_{\theta_i}, \mathbb{P}_{\theta_j} \right)^2}{\ln N} \right) \\
&\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + \frac{4n^2 \rho}{N^2} \sum_{i,j} \frac{1}{2n} \sqrt{\text{KL} \left( \mathbb{P}_{\theta_i} \| \mathbb{P}_{\theta_j} \right) / 2} + \text{KL} \left( \mathbb{P}_{\theta_i} \| \mathbb{P}_{\theta_j} \right) / 2}{\ln N} \right) \\
&\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + \frac{4n^2 \rho}{N^2} \sum_{i,j} \frac{1}{2n} \sqrt{\gamma/2} \| \theta_i - \theta_j \| + \gamma \| \theta_i - \theta_j \|^2 / 2}{\ln N} \right) \\
&\ge \frac{\alpha^2 d}{16} \left( 1 - \frac{1 + \left( 2\sqrt{2n\rho\alpha\sqrt{\gamma d}} + 2n^2\rho\gamma\alpha^2 d \right)}{d/32} \right),
\end{align*}
$$

and setting $\alpha := \min \left( \frac{r_0}{\sqrt{d}}, \frac{1}{64^2 2 \sqrt{2n \sqrt{\rho \gamma}}} \right)$ when $d \ge 66$ concludes that (because $\rho \le 1$)

$$
\begin{align*}
\mathfrak{M}_n \left( \rho\text{-zCDP}, \left( \mathbb{P}_\theta^{\otimes n} \right)_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) &\ge \frac{\min \left( \frac{r_0}{\sqrt{d}}, \frac{1}{64^2 2 \sqrt{2n \sqrt{\rho \gamma}}} \right)^2 d}{32} \\
&= \Omega \left( \frac{d}{n^2 \rho \gamma} \right).
\end{align*}
$$

<figure><img src="image_5.png" /></figure>

### D.3 Support of Uniform Distributions

For the last example, we chose to investigate a statistical problem that has a non-private minimax rate faster than $\frac{1}{n}$. We consider the parametric model

$$ (\mathbb{P}_{\theta} := \mathcal{U}([0, \theta]))_{\theta \in \Theta}, \quad \Theta = (0, 1]. $$
To exploit Le Cam's lemma we will need to control the total variation between two distributions. In this model, it can be done explicitly. The total variation between $\mathbb{P}_{\theta_1}^{\otimes n}$ and $\mathbb{P}_{\theta_2}^{\otimes n}$ can be computed as

$$TV(\mathbb{P}_{\theta_1}^{\otimes n}, \mathbb{P}_{\theta_2}^{\otimes n}) = 1 - \int_{[0,1]^n} \min \left( \pi_{\mathbb{P}_{\theta_1}^{\otimes n}}, \pi_{\mathbb{P}_{\theta_2}^{\otimes n}} \right) = 1 - \left( \frac{\min(\theta_1, \theta_2)}{\max(\theta_1, \theta_2)} \right)^n.$$

**Non-Private Minimax Risk.** By the (non-private) master lower bound (6) and Le Cam's lemma (Fact 1), applied to the $\frac{1}{2n}$-packing $\theta_1 = 1 - \frac{1}{n}$ and $\theta_2 = 1$, we have

$$\mathfrak{M}_n \left( (\mathcal{U}([0, \theta]))^{\otimes n} \right)_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \geq \frac{e^{-1}}{8n^2} = \Omega \left( \frac{1}{n^2} \right).$$

where we used that $1 - TV(\mathbb{P}_{\theta_1}^{\otimes n}, \mathbb{P}_{\theta_2}^{\otimes n}) = (1 - \frac{1}{n})^n \geq e^{-1}$. Furthermore, as we now show, the estimator $\max \mathbf{X}$ achieves this rate of convergence when $X_1, \dots, X_n \sim \mathcal{U}([0, \theta^*])$ are independent. Indeed, for any $t \in [0, \theta^*]$,

$$\mathbb{P}(\max \mathbf{X} < t) = \prod_{i=1}^{n} \mathbb{P}(X_i < t) = \left(\frac{t}{\theta^*}\right)^n.$$

Hence, $\max \mathbf{X}$ has a density $\pi_{\max} \mathbf{X}$ with respect to the Lebesgue measure where

$$\forall t \in \mathbb{R}, \quad \pi_{\max} \mathbf{X}(t) = 1_{[0, \theta^*]}(t) \frac{nt^{n-1}}{\theta^{*n}},$$

so that

$$\mathbb{E}(\max \mathbf{X}) = \int_{0}^{\theta^*} t \left( \frac{nt^{n-1}}{\theta^{*n}} \right) dt = \frac{n}{n+1} \theta^*,$$

$$\mathbb{V}(\max \mathbf{X}) = \int_{0}^{\theta^*} t^2 \left( \frac{nt^{n-1}}{\theta^{*n}} \right) dt - [\mathbb{E}(\max \mathbf{X})]^2 = \theta^{*2} \left( \frac{n}{n+2} - \frac{n^2}{(n+1)^2} \right).$$

By the bias-variance tradeoff, the quadratic risk of $\max \mathbf{X}$ is thus $O(\frac{\theta^{*2}}{n^2})$. In particular, this proves that the non-private minimax rate of convergence is $\Theta(\frac{1}{n^2})$ and that $\max \mathbf{X}$ achieves this minimax rate of convergence.

**Minimax Risk with $\epsilon$-Differential Privacy.** By the private master lower bound (10) and the product form of Le Cam's private lemma for $\epsilon$-DP on product distributions (see Theorem 1 with $\delta = 0$) with the $\frac{1}{2n\epsilon}$-packing $\theta_1 = 1 - \frac{1}{n\epsilon}$ and $\theta_2 = 1$ we have when $n\epsilon > 1$

$$\mathfrak{M}_n \left( \epsilon\text{-DP}, (\mathcal{U}([0, \theta]))^{\otimes n} \right)_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \geq \frac{e^{-1}}{8(n\epsilon)^2} = \Omega \left( \frac{1}{(n\epsilon)^2} \right),$$

In particular, the rate is degraded compared to the non-private one as soon as $\epsilon$ is decreasing.

**Minimax Risk with $\rho$-zero Concentrated Differential Privacy.** Similarly, using the product form of Le Cam's private lemma for $\rho$-zCDP on product distributions (see Theorem 2) and the $\frac{1}{2n\sqrt{\rho}}$-packing $\theta_1 = 1 - \frac{1}{n\sqrt{\rho}}$ and $\theta_2 = 1$ gives that when $n\sqrt{\rho} > 1$,

$$\mathfrak{M}_n \left( \rho\text{-zCDP}, (\mathcal{U}([0, \theta]))^{\otimes n} \right)_{\theta \in \Theta}, |\cdot - \cdot|, (\cdot)^2 \geq \frac{1 - \frac{1}{\sqrt{2}}}{8n^2\rho} = \Omega \left( \frac{1}{n^2\rho} \right).$$

In particular, the rate is degraded compared to the non-private one as soon as $\rho$ is decreasing.

This example shows that when the stochastic noise due to sampling shrinks too fast (here $\max \mathbf{X}$ has quadratic risk $O(1/n^2)$), then the noise due to privacy becomes predominant. In particular, we do not observe a distinction on the rate at which $\epsilon$ or $\rho$ tends to 0 in order the conclude to a degradation of the minimax risk. It is systematically degraded.
## E A note on Fact 4

This section was added in the latest version of this article after noticing that the use of Poisson point processes in the proof of Fact 4 can make the results presented in this article harder to communicate on than it should. We thus present here a simplified view on the proof of Angel & Spinka (2021).

Let $(\mathcal{X}, \mathcal{B})$ be a measurable space. Let $(\mathbb{P}_i)_{i \in I}$ be a collection of probability measures that are compatible with $(\mathcal{X}, \mathcal{B})$. A coupling between $(\mathbb{P}_i)_{i \in I}$ is a collection of random variables $(X_i)_{i \in I}$ defined on a common probability space (with probability measure $\mathbb{P}$), and with values in $(\mathcal{X}, \mathcal{B})$, such that

$$ \forall i \in I, \quad \mathbb{P}_{X_i} = \mathbb{P}_i. $$

Here, for any $i, \mathbb{P}_{X_i}$ represents the push-forward probability of $\mathbb{P}$ by $X_i$ defined as

$$ \forall B \in \mathcal{B}, \quad \mathbb{P}_{X_i}(B) = \mathbb{P}(X_i \in B). $$

A folklore result Lindvall (2003) states that if $(X_i)_{i \in I}$ is a coupling between $(\mathbb{P}_i)_{i \in I}$, then

$$ \forall i, j \in I, \quad \forall E_{i,j} \in \mathcal{B} \text{ s.t. } X_i(\omega) = X_j(\omega) \quad \forall \omega \in E_{i,j}, \quad \mathbb{P}(E_{i,j}) \le 1 - \text{TV}(\mathbb{P}_i, \mathbb{P}_j), \quad (26) $$

where we recall that $\text{TV}(\cdot, \cdot)$ is the total variation distance on the set on probability measures on $(\mathcal{X}, \mathcal{B})$ defined as

$$ \text{TV}(\mathbb{P}_i, \mathbb{P}_j) = \sup_{B \in \mathcal{B}} |\mathbb{P}_i(B) - \mathbb{P}_j(B)|. $$

Indeed, for any $i, j \in I$, any $E_{i,j} \in \mathcal{B}$ s.t. $X_i(\omega) = X_j(\omega) \quad \forall \omega \in E_{i,j}$, and any $B \in \mathcal{B}$,

$$ \begin{aligned} \mathbb{P}(E_{i,j}) &\le \mathbb{P}((X_i \in B, X_j \in B) \cup (X_i \in \bar{B}, X_j \in \bar{B})) \\ &= \mathbb{P}(X_i \in B, X_j \in B) + \mathbb{P}(X_i \in \bar{B}, X_j \in \bar{B}) \\ &\le \mathbb{P}(X_j \in B) + \mathbb{P}(X_i \in \bar{B}) \\ &= \mathbb{P}_j(B) + 1 - \mathbb{P}_i(B) \\ &= 1 - (\mathbb{P}_i(B) - \mathbb{P}_j(B)), \end{aligned} $$

which gives the result after optimizing over $B$.

Note that in the previous expressions, we looked at events on which random variables are equal without directly referring to the exact sets of equalities between those random variables. This is because without further caution, such sets may not be measurable. However, mild topological hypotheses on $(\mathcal{X}, \mathcal{B})$ are enough to guarantee that for any random variables $X$ and $Y$ defined on a common probability space and taking values in $(\mathcal{X}, \mathcal{B})$ then $(X = Y)$ is measurable. This is for instance the case if $(\mathcal{X}, \mathcal{B})$ is a Polish space equipped with its Borel $\sigma$-algebra, a ubiquitous class of measurable spaces in applied mathematics and in theoretical computer science. Indeed, if $\mathcal{X}$ is a Polish space, by noting $\delta$ its distance (up to homeomorphism) and $D$ its countable dense part, one has that

$$ (X = Y) = \cap_{n \in \mathbb{N}_*} \left( \cup_{d \in D} \left( \delta(X, d) < \frac{1}{n} \right) \cap \left( \delta(Y, d) < \frac{1}{n} \right) \right). $$

## E.1 Related work

A folklore coupling construction Lindvall (2003) states that when $I$ is of cardinality two, i.e. when one is interested in finding a coupling between two marginal distributions only, and when $(\mathcal{X}, \mathcal{B})$ is a Polish space, then the upper-bound (26) is tight, which means that there exists a coupling $(X_1, X_2)$ between $\mathbb{P}_1$ and $\mathbb{P}_2$ such that

$$ \mathbb{P}(X_1 = X_2) = 1 - \text{TV}(\mathbb{P}_1, \mathbb{P}_2). $$

In their article Angel & Spinka (2021), Omer Angel and Yinon Spinka investigate what happens when $I$ is of cardinality bigger than two, and even possibly of infinite (non-countable) cardinality. First, they prove
that as soon as $I$ is of cardinality at least three, the upper-bound (26) is unachievable, which means there exists at least an instance of the problem (i.e. a measurable space and a set of marginal distributions) on which no coupling may match the upper-bound. Then, they provide two different coupling constructions that achieve the following quantitative result : denoting by $(X_i)_{i \in I}$ the coupling between $(\mathbb{P}_i)_{i \in I}$, then

$$ \mathbb{P}(X_i = X_j) \ge 1 - \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)} \ge 1 - 2\text{TV}(\mathbb{P}_i, \mathbb{P}_j), \quad \forall i, j \in I. \qquad (27) $$

In this expression, $(X_i = X_j)$ should be understood in a weak sense (i.e. as a measurable set on which $X_i = X_j$, which may be smaller than the set $(X_i = X_j)$). (26) together with (27) show that the constructions of the authors are optimal up to a factor two. Both of their constructions work under different setups, use different construction tools and are qualitatively different. They can be summarized as follows :

1. (i) Their first construction is the most general, and is the one that is simplified here. It builds on inhomogeneous Poisson point processes and assumes the existence a $\sigma$-finite measure $\mu$ on $(\mathcal{X}, \mathcal{B})$ such that for any $i \in I$, $\mathbb{P}_i$ is absolutely continuous w.r.t. $\mu$. In particular, no assumption is made on the cardinality of $I$.

2. (ii) Their second construction only builds on elementary notions of probability theory but requires $(\mathcal{X}, \mathcal{B})$ being discrete. Note that since on discrete spaces, any probability measure is absolutely continuous w.r.t. the counting measure, the domination assumption in (i) is always satisfied in this setup. Again, no assumption is made on the cardinality of $I$.

## E.2 About this note

This note aims to present a simplification of Angel and Spinka's first coupling construction ((i)), while still relying on the same core interesting idea, that only builds on elementary notions of probability theory, and that is still applicable to continuous distributions (contrary to (ii)).

This simplification will work under the following hypothesis. Let us assume that there exists a distribution of probability $\mathbb{Q}$ on $(\mathcal{X}, \mathcal{B})$ such that there exists a $M > 1$ such that

$$ \forall i \in I, \quad \forall B \in \mathcal{B}, \quad \mathbb{P}_i(B) \le M\mathbb{Q}(B). \qquad (28) $$

In particular, this hypothesis is stronger than the domination one in (i). Even if (28) does not have restrictive implications on the cardinality of $I$, an important observation is that (28) is always satisfied when $I$ is finite. Indeed, one may take $\mathbb{Q}$ as the mixture distribution

$$ \mathbb{Q} = \frac{1}{\#(I)} \sum_{i \in I} \mathbb{P}_i, $$

and $M = \#(I)$.

Under this extra hypothesis, it is possible to present Angel and Spinka's first coupling construction under the light of traditional rejection sampling. In particular, the cornerstone of the construction, which is to add dependence between two marginals proportionally to their common area below their densities, is identical to Angel and Spinka's Poisson construction.

Since it presents Angel and Spinka's coupling construction with only elementary theory, we hope that this note will help communication and diffusion of such results that are interesting for both the theoretical computer science and the machine learning communities Elkin-Koren et al. (2023); Bun et al. (2023); Karbasi et al. (2024); Block et al. (2024); Kalavasis et al. (2023).

## E.3 Coupling construction

Let $Y_1, U_1, Y_2, U_2, \dots, Y_n, U_n, \dots$ be a sequence of independent random variables<fnref n="4" /> such that, for any $i$, $Z_i$ has distribution $\mathbb{Q}$ on $(\mathcal{X}, \mathcal{B})$, and $U_i$ is uniform on $[0, 1]$. Let $(\Omega, \mathcal{T}, \mathbb{P})$ be the probability space supporting this sequence.

<footnote n="4">⁴Formally, it is a stochastic process indexed by $\mathbb{N}$. The independence means that its finite-dimensional distributions are product distributions. Its existence, without topological assumptions of $(\mathcal{X}, \mathcal{B})$, is guaranteed by the Ionescu-Tulcea extension theorem.</footnote>
From the domination assumption on the distributions ((28)), it is immediate that for any $i, \mathbb{P}_i$ is absolutely continuous w.r.t. $\mathbb{Q}$, let $p_i$ denote its Radon-Nikodym density. Let $\perp \notin \mathcal{X}$ be a "fresh" element. For any $i \in I$ and $n \in \mathbb{N}$, let

$$ 
\begin{array}{ll}
Z_n^{(i)}: & \Omega \to \mathcal{X} \cup \{\perp\} \\
\omega & \mapsto Y_n(\omega) & \text{if } U_n(\omega) \in [0, p_i(Y_n(\omega))/M] \\
\omega & \mapsto \perp & \text{otherwise.}
\end{array}
$$

For any $i \in I$, let $X_i := Z_{n_0(i)}^{(i)}$ where $n_0(i)$ is the smallest index $n$ such that $Z_n^{(i)} \neq \perp$. If such an index does not exist, simply assign to $X_i$ a fixed value $d$ in $\mathcal{X}$.

Then, $(X_i)_{i \in I}$ is a coupling between $(\mathbb{P}_i)_{i \in I}$ that satisfies (27). Furthermore, if it is possible to simulate independent sampling from $\mathbb{Q}$ and if it is possible to evaluate $p_i(\cdot) \mathbb{Q}$ almost anywhere for any $i \in I$, then this construction gives a straightforward sampling algorithm for $(X_i)_{i \in I}$.

## E.4 Proof of correctness

### E.4.1 Measurability

As a safety check, we verify the measurability of the different quantities that were introduced.

For any $i \in I$ and $n \in \mathbb{N}$, $Z_n^{(i)}$ is measurable on $\mathcal{X} \cup \{\perp\}$ for the $\sigma$-algebra induced by $\mathcal{B} \cup \{\{\perp\}\}$ (it is thus a random variable). Indeed,

$$ (Z_n^{(i)} = \perp) = \cup_{q \in \mathbb{Q} \cap [0,1]} \left( Y_n \in \left( \frac{p_i}{M} \right)^{-1} ([0, q]) \right) \cap (U_n \in (q, +\infty)), $$

and for any $A \in \mathcal{B}$,

$$ (Z_n^{(i)} \in A) = (Y_n \in A) \cap (Z_n^{(i)} \neq \perp). $$

Here, $\mathbb{Q}$ was locally used to refer to the set of rational numbers instead of the dominating measure.

As a consequence, for any $i$, $X_i$ is measurable on $(\mathcal{X}, \mathcal{B})$ (and is thus also a random variable). Indeed, for any $i \in I$ and $A \in \mathcal{B}$,

$$ (X_i \in A) = \cup_{n \in \mathbb{N}} (Z_0^{(i)} = \dots = Z_{n-1}^{(i)} = \perp) \cap (Z_n^{(i)} \in A) $$

if the default value $d$ is not in $A$, and

$$ (X_i \in A) = (\cap_{n \in \mathbb{N}} (Z_n^{(i)} = \perp)) \cup (\cup_{n \in \mathbb{N}} (Z_0^{(i)} = \dots = Z_{n-1}^{(i)} = \perp) \cap (Z_n^{(i)} \in A)) $$

otherwise.

### E.4.2 $(X_i)_{i \in I}$ is a coupling between $(\mathbb{P}_i)_{i \in I}$

For any $i \in I$, the sequence $Z_1^{(i)}, Z_2^{(i)}, \dots$ is independent$^5$. Finally, for any $i \in I$ and $n \in \mathbb{N}$, and any $A \in \mathcal{B}$, $1_A(Z_n^{(i)})$ is a Bernoulli random variable of probability of success

$$ 
\begin{align} 
\mathbb{P}(Z_n^{(i)} \in A) &= \int_{\mathcal{X} \times [0,1]} 1_A(y) 1_{[0, p_i(y)/M]}(u) du d\mathbb{Q}(y) \nonumber \\
&\stackrel{\text{Fubini}}{=} \frac{1}{M} \int_{\mathcal{X}} 1_A(y) p_i(y) d\mathbb{Q}(y) \nonumber \\
&= \frac{1}{M} \int_{\mathcal{X}} 1_A(y) d\mathbb{P}_i(y) \nonumber \\
&= \frac{\mathbb{P}_i(A)}{M}. \tag{29}
\end{align} 
$$

In particular, for any $i \in I$ and $n \in \mathbb{N}$,

$$ \mathbb{P}(Z_n^{(i)} = \perp) = \left(1 - \frac{1}{M}\right) \tag{30} $$

<footnote>$^5$Again, this must be understood as a stochastic process.</footnote>
For a $A \in \mathcal{B}$, and $i \in I$,

$$ 
\begin{aligned}
(X_i \in A) &\supset (Z_0^{(i)} \in A) \\
&\cup (Z_0^{(i)} = \perp) \cap (Z_1^{(i)} \in A) \\
&\cup (Z_0^{(i)} = Z_1^{(i)} = \perp) \cap (Z_2^{(i)} \in A) \\
&\cup \dots
\end{aligned}
$$

Hence, for any $A \in \mathcal{B}$, and any $i \in I$,

$$ 
\begin{aligned}
\mathbb{P}(X_i \in A) &\geq \sum_{n \in \mathbb{N}} \mathbb{P}((Z_0^{(i)} = \dots = Z_{n-1}^{(i)} = \perp) \cap (Z_n^{(i)} \in A)) \\
&= \sum_{n \in \mathbb{N}} \mathbb{P}(Z_0^{(i)} = \perp) \dots \mathbb{P}(Z_{n-1}^{(i)} = \perp) \mathbb{P}(Z_n^{(i)} \in A) \\
&\stackrel{(29) \& (30)}{=} \sum_{n \in \mathbb{N}} \left(1 - \frac{1}{M}\right)^n \frac{\mathbb{P}_i(A)}{M} \\
&= \mathbb{P}_i(A).
\end{aligned}
$$

Since this is true for any $A \in \mathcal{B}$ and $i \in I$, $\mathbb{P}_{X_i} = \mathbb{P}_i$ for any $i \in I$. Hence, $(X_i)_{i \in I}$ is a coupling between $(\mathbb{P}_i)_{i \in I}$.

**E.4.3** $(X_i)_{i \in I}$ satisfies (27)

For any pair $i, j \in I$, and any $n \in \mathbb{N}$, using the classical equality $1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j) = \int_{\mathcal{X}} (p_i \vee p_j)(y)d\mathbb{Q}(y)$,

$$ 
\begin{aligned}
\mathbb{P}(Z_n^{(i)} = Z_n^{(j)} = \perp) &= \int_{\mathcal{X} \times [0,1]} 1_{((p_i \vee p_j)(y)/M, 1]}(u) du d\mathbb{Q}(y) \\
&= \int_{\mathcal{X} \times [0,1]} 1 - 1_{[0, (p_i \vee p_j)(y)/M]}(u) du d\mathbb{Q}(y) \\
&\stackrel{\text{Fubini}}{=} \int_{\mathcal{X}} 1 - \frac{(p_i \vee p_j)(y)}{M} d\mathbb{Q}(y) \\
&= 1 - \frac{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{M},
\end{aligned}
\quad (31) $$

and using the other classical equality $1 - \text{TV}(\mathbb{P}_i, \mathbb{P}_j) = \int_{\mathcal{X}} (p_i \wedge p_j)(y)d\mathbb{Q}(y)$,

$$ 
\begin{aligned}
\mathbb{P}(Z_n^{(i)} = Z_n^{(j)} \neq \perp) &= \int_{\mathcal{X} \times [0,1]} 1_{[0, (p_i \wedge p_j)(y)/M]}(u) du d\mathbb{Q}(y) \\
&\stackrel{\text{Fubini}}{=} \int_{\mathcal{X}} \frac{(p_i \wedge p_j)(y)}{M} d\mathbb{Q}(y) \\
&= \frac{1 - \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{M}.
\end{aligned}
\quad (32) $$

Finally, for any $i, j \in I$, defining

$$ 
\begin{aligned}
E_{i,j} &= (Z_0^{(i)} = Z_0^{(j)} \neq \perp) \\
&\quad \cup (Z_0^{(i)} = Z_0^{(j)} = \perp) \cap (Z_1^{(i)} = Z_1^{(j)} \neq \perp) \\
&\quad \cup (Z_0^{(i)} = Z_0^{(j)} = \perp) \cap (Z_1^{(i)} = Z_1^{(j)} = \perp) \cap (Z_2^{(i)} = Z_2^{(j)} \neq \perp) \\
&\quad \cup \dots,
\end{aligned}
$$

one has

$$ X_i(\omega) = X_j(\omega), \quad \forall \omega \in E_{i,j} $$
and

$$
\begin{align*}
\mathbb{P}(E_{i,j}) &= \sum_{n \in \mathbb{N}} \mathbb{P} \left( \bigcap_{k=0}^{n-1} (Z_k^{(i)} = Z_k^{(j)} = \perp) \cap (Z_n^{(i)} = Z_n^{(j)} \neq \perp) \right) \\
&= \sum_{n \in \mathbb{N}} \left( \prod_{k=0}^{n-1} \mathbb{P}(Z_k^{(i)} = Z_k^{(j)} = \perp) \right) \mathbb{P}(Z_n^{(i)} = Z_n^{(j)} \neq \perp) \\
&\stackrel{(31) \& (32)}{=} \sum_{n \in \mathbb{N}} \left( 1 - \frac{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{M} \right)^n \frac{1 - \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{M} \\
&= \frac{1 - \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}.
\end{align*}
$$

This concludes the proof.