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

HAL
open science

# On the Statistical Complexity of Estimation and Testing under Privacy Constraints

Clément Lalanne, Aurélien Garivier, Rémi Gribonval

► To cite this version:

Clément Lalanne, Aurélien Garivier, Rémi Gribonval. On the Statistical Complexity of Estimation and Testing under Privacy Constraints. Transactions on Machine Learning Research Journal, 2023. hal-03794374v3

HAL Id: hal-03794374

https://hal.science/hal-03794374v3

Submitted on 22 Dec 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# On the Statistical Complexity of Estimation and Testing under Privacy Constraints

Clément Lalanne, Aurélien Garivier, Rémi Gribonval

► To cite this version:

Clément Lalanne, Aurélien Garivier, Rémi Gribonval. On the Statistical Complexity of Estimation and Testing under Privacy Constraints. Transactions on Machine Learning Research Journal, 2023. hal-03794374v4

HAL Id: hal-03794374

https://hal.science/hal-03794374v4

Submitted on 12 Sep 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# On the Statistical Complexity of Estimation and Testing under Privacy Constraints

Clément Lalanne

Univ. Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedex 07, France

clement.lalanne@ens-lyon.fr

Aurélien Garivier

Univ. Lyon, ENS Lyon, UMPA UMR 5669, 46 allée d'Italie, F-69364, Lyon cedex 07

aurelien.garivier@ens-lyon.fr

Rémi Gribonval

Univ. Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedex 07, France

remi.gribonval@inria.fr

## Abstract

The challenge of producing accurate statistics while respecting the privacy of the individuals in a sample is an important area of research. We study minimax lower bounds for classes of differentially private estimators. In particular, we show how to characterize the power of a statistical test under differential privacy in a *plug-and-play* fashion by solving an appropriate transport problem. With specific coupling constructions, this observation allows us to derive Le Cam-type and Fano-type inequalities not only for regular definitions of differential privacy but also for those based on Renyi divergence. We then proceed to illustrate our results on three simple, fully worked out examples. In particular, we show that the problem class has a huge importance on the provable degradation of utility due to privacy. In certain scenarios, we show that maintaining privacy results in a noticeable reduction in performance only when the level of privacy protection is very high. Conversely, for other problems, even a modest level of privacy protection can lead to a significant decrease in performance. Finally, we demonstrate that the DP-SGLD algorithm, a private convex solver, can be employed for maximum likelihood estimation with a high degree of confidence, as it provides near-optimal results with respect to both the size of the sample and the level of privacy protection. This algorithm is applicable to a broad range of parametric estimation procedures, including exponential families.

## 1 Introduction

The ever-increasing data collection on individuals and their sometimes hazardous use has led to numerous threats to privacy and serious concerns have emerged (Narayanan & Shmatikov, 2006; Backstrom et al., 2007; Fredrikson et al., 2015; Dinur & Nissim, 2003; Homer et al., 2008; Loukides et al., 2010; Narayanan & Shmatikov, 2008; Sweeney, 2000; Wagner & Eckhoff, 2018; Sweeney, 2002). *Differential privacy* (Dwork et al., 2014) offers a future-proof solution to this problem by ensuring that individuals are protected from the result of an estimation procedure. It enables the inference of global statistics on a dataset while bounding each sample's influence and ensuring that the presence or absence of an individual in the dataset cannot be deduced from the result. In the last decade, research results have multiplied and nowadays, it is possible to build complex data pipelines under privacy constraints (Dwork et al., 2006; Kairouz et al., 2015; Dong et al., 2019; 2020; Abadi et al., 2016). Notably, differential privacy is now used in production by the US Census Bureau (Abowd, 2018), Google (Erlingsson et al., 2014), Apple (Thakurta et al., 2017) and Microsoft (Ding et al., 2017) among others. Differential privacy constrains the class of usable *stochastic* functions defined on a dataset and as a result it degrades the utility of an estimation. To quantify the loss due to privacy, many *utility bounds* are often used (McSherry & Talwar, 2007; McSherry, 2009). When the target of the estimation is not the pointwise evaluation of a function on a given dataset but rather a hidden quantity defined “at the scale of the population”, i.e., of the underlying data distribution, statistical problems arise and an important topic is to quantify the utility of private estimators (Dwork & Lei,
# On the Statistical Complexity of Estimation and Testing under Privacy Constraints

Clément Lalanne

Univ. Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedex 07, France

clement.lalanne@ens-lyon.fr

Aurélien Garivier

Univ. Lyon, ENS Lyon, UMPA UMR 5669, 46 allée d'Italie, F-69364, Lyon cedex 07

aurelien.garivier@ens-lyon.fr

Rémi Gribonval

Univ. Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedex 07, France

remi.gribonval@inria.fr

## Abstract

The challenge of producing accurate statistics while respecting the privacy of the individuals in a sample is an important area of research. We study minimax lower bounds for classes of differentially private estimators. In particular, we show how to characterize the power of a statistical test under differential privacy in a *plug-and-play* fashion by solving an appropriate transport problem. With specific coupling constructions, this observation allows us to derive Le Cam-type and Fano-type inequalities not only for regular definitions of differential privacy but also for those based on Renyi divergence. We then proceed to illustrate our results on three simple, fully worked out examples. In particular, we show that the problem class has a huge importance on the provable degradation of utility due to privacy. In certain scenarios, we show that maintaining privacy results in a noticeable reduction in performance only when the level of privacy protection is very high. Conversely, for other problems, even a modest level of privacy protection can lead to a significant decrease in performance. Finally, we demonstrate that the DP-SGLD algorithm, a private convex solver, can be employed for maximum likelihood estimation with a high degree of confidence, as it provides near-optimal results with respect to both the size of the sample and the level of privacy protection. This algorithm is applicable to a broad range of parametric estimation procedures, including exponential families.

## 1 Introduction

The ever-increasing data collection on individuals and their sometimes hazardous use has led to numerous threats to privacy and serious concerns have emerged (Narayanan & Shmatikov, 2006; Backstrom et al., 2007; Fredrikson et al., 2015; Dinur & Nissim, 2003; Homer et al., 2008; Loukides et al., 2010; Narayanan & Shmatikov, 2008; Sweeney, 2000; Wagner & Eckhoff, 2018; Sweeney, 2002). *Differential privacy* (Dwork & Roth, 2014) offers a future-proof solution to this problem by ensuring that individuals are protected from the result of an estimation procedure. It enables the inference of global statistics on a dataset while bounding each sample's influence and ensuring that the presence or absence of an individual in the dataset cannot be deduced from the result. In the last decade, research results have multiplied and nowadays, it is possible to build complex data pipelines under privacy constraints (Dwork et al., 2006; Kairouz et al., 2015; Dong et al., 2019; 2020; Abadi et al., 2016). Notably, differential privacy is now used in production by the US Census Bureau (Abowd, 2018), Google (Erlingsson et al., 2014), Apple (Thakurta et al., 2017) and Microsoft (Ding et al., 2017) among others. Differential privacy constrains the class of usable *stochastic* functions defined on a dataset and as a result it degrades the utility of an estimation. To quantify the loss due to privacy, many *utility bounds* are often used (McSherry & Talwar, 2007; McSherry, 2010). When the target of the estimation is not the pointwise evaluation of a function on a given dataset but rather a hidden quantity defined “at the scale of the population”, i.e., of the underlying data distribution, statistical problems arise and an important topic is to quantify the utility of private estimators (Dwork & Lei,
2009; Wasserman & Zhou, 2010; Hall et al., 2011; Smith, 2011; Chaudhuri et al., 2011; Rubinstein et al., 2009; Lalanne et al., 2022; Ryffel et al., 2022; Karwa & Vadhan, 2017; Du et al., 2020; Biswas et al., 2020; Diakonikolas et al., 2015; Bun et al., 2019; Bun & Steinke, 2019; Ben-Eliezer et al., 2022).

Part of the privacy literature focuses on lower bounds (Asi & Duchi, 2020a;b; Farhadi et al., 2022; Tao et al., 2022), i.e. bounds for which we know we "cannot" do better under certain hypotheses. Most of them are problem-specific and are to be understood as a worst case among all instances of a given problem. Some others, such as the ones based on the theory of *inverse sensitivity* (Asi & Duchi, 2020a;b), only consider a "local" worst case and thus give tighter results. In contrast, in statistics, it is possible to measure the probabilities of occurrence of each instance of a problem. It is then natural to consider lower bounds that are probabilistic in nature (i.e. with a certain probability or in expectation). In particular, the classical *minimax* theory looks at the best uniform risk of convergence of the estimators in order to estimate a quantity defined at the scale of a population and has a vast literature on lower bounds (Assouad, 1983; Ibragimov & Has' Minskii, 2013; Bickel & Ritov, 1988; Giraud, 2021; Devroye, 1987; Verdú et al., 1994; Thomas & Joy, 2006; Scarlett & Cevher, 2019; Rigolli & Hütter, 2015; Tsybakov, 2003; Györfi et al., 2002). Under privacy conditions, some work is still to be done on the minimax risk, both on lower bounds and on some matching upper bounds. Our work sits in this line of research.

At the time of writing, to the best of our knowledge, two series of work have already met some success in this task. The first one is due to Duchi et al. (2013a;b) and looks at so-called *local* privacy (Bebensee, 2019; Yang et al., 2020; Cormode et al., 2018) which is a stronger definition of privacy than the ones that will be investigated in this article. To put it simply, it requires that *each piece of data is anonymized before collection*, whereas *global* privacy only requires *the aggregation* to be private. It paved the way for a consequent line of work on estimation under local privacy or more generally under communication constraints (Acharya et al., 2021c;b;d;a; Barnes et al., 2020a;b; 2019). The second one is due to Acharya et al. (2021e; 2018). It adapts Le Cam's, Fano's and Assouard's methods to differential privacy. Their work will be our main point of comparison, since we believe that our work nicely complements theirs by providing a somewhat *plug-and-play* framework, notably allowing to establish results for other types of privacy.

Indeed, the present work extends classical techniques like Le Cam and Fano for proving minimax lower bounds to the setting where the estimator must additionally be differentially private. While this was previously done by Acharya et al. (2021e; 2018) in the specific context of $(\epsilon, \delta)$-differential privacy, our contribution improves upon that work by getting quantitative bounds that are both tighter (e.g. by large constants in the exponent) and somewhat *plug-and-play* in that they apply to a variety of differential privacy variants, and notably to the setting of *zero-concentrated differential privacy* (*zCDP*), bridging the theoretical gap with very recent work in that field (Kamath et al., 2022). As applications, we extend known rates for estimating the parameter of a Bernoulli distribution and for estimating the mean of a high-dimensional spherical Gaussian to the zCDP setting. We also show that for the problem of estimating the support of a uniform distribution over an unknown interval inside $[0,1]$, the minimax risk is *uniformly degraded* by the privacy constraint. This constrasts with Bernoulli and Gaussian mean estimation, and is perhaps somewhat surprising, as one usually expects bounds for which there are parameter regimes under which the non-private minimax risk dominates.

Lastly, we show a private minimax lower bound for maximum likelihood estimation, when the log likelihood is concave and smooth in the parameter being estimated and satisfies some additional non-degeneracy assumptions, and show that private SGLD qualitatively matches this lower bound in terms of sample size and privacy parameter dependence.

## 1.1 The Minimax Risk and Private Estimators

We start by defining the minimax risk. Given $n \in \mathbb{N}_*$ and a feature space $\mathcal{X}$, $\mathcal{X}^n$ may be viewed as a set of datasets containing $n$ elements from $\mathcal{X}$. We consider a family of probability distributions $(\mathbb{P}_\theta)_{\theta \in \Theta}$ on $\mathcal{X}^n$ where $\Theta$ is equipped with a semi-metric<fnref n="1" /> $d_\Theta: \Theta^2 \to \mathbb{R}_+$. Often, for all $\theta \in \Theta$, $\mathbb{P}_\theta = \mathbb{P}_{\theta^n}$ where $(\mathbb{P}_\theta)_{\theta \in \Theta}$ is a family of probability distributions on $\mathcal{X}$. This corresponds to the classical statistical setup where we observe $n$ i.i.d. random variables. The general setup allows capturing phenomena that are not i.i.d., for instance Markov processes. Given an estimator $\hat{\theta}: \mathcal{X}^n \to \Theta$ one might look at its uniform risk of estimation over $\Theta$

<footnote n="1">¹i.e. that is positive, symmetric, that satisfies the triangular inequality and $d_\Theta(\theta, \theta) = 0, \forall \theta \in \Theta$</footnote>
2009; Wasserman & Zhou, 2010; Hall et al., 2011; Smith, 2011; Chaudhuri et al., 2011; Rubinstein et al., 2012; Lalanne et al., 2022; Ryffel et al., 2022; Karwa & Vadhan, 2018; Du et al., 2020; Biswas et al., 2020; Diakonikolas et al., 2015; Bun et al., 2019; Bun & Steinke, 2019; Ben-Eliezer et al., 2022).

Part of the privacy literature focuses on lower bounds (Asi & Duchi, 2020a;b; Farhadi et al., 2022; Tao et al., 2022), i.e. bounds for which we know we "cannot" do better under certain hypotheses. Most of them are problem-specific and are to be understood as a worst case among all instances of a given problem. Some others, such as the ones based on the theory of *inverse sensitivity* (Asi & Duchi, 2020a;b), only consider a "local" worst case and thus give tighter results. In contrast, in statistics, it is possible to measure the probabilities of occurrence of each instance of a problem. It is then natural to consider lower bounds that are probabilistic in nature (i.e. with a certain probability or in expectation). In particular, the classical *minimax* theory looks at the best uniform risk of convergence of the estimators in order to estimate a quantity defined at the scale of a population and has a vast literature on lower bounds (Assouad, 1983; Ibragimov & Khasminskii, 1981; Bickel & Ritov, 1988; Giraud, 2021; Devroye, 1987; Han & Verdú, 1994; Cover & Thomas, 2006; Scarlett & Cevher, 2019; Rigollet & Hütter, 2015; Tsybakov, 2009; Györfi et al., 2002). Under privacy conditions, some work is still to be done on the minimax risk, both on lower bounds and on some matching upper bounds. Our work sits in this line of research.

At the time of writing, to the best of our knowledge, two series of work have already met some success in this task. The first one is due to Duchi et al. (2013; 2014) and looks at so-called *local* privacy (Bebensee, 2019; Yang et al., 2020; Cormode et al., 2018) which is a stronger definition of privacy than the ones that will be investigated in this article. To put it simply, it requires that *each piece of data is anonymized before collection*, whereas *global* privacy only requires *the aggregation* to be private. It paved the way for a consequent line of work on estimation under local privacy or more generally under communication constraints (Acharya et al., 2021a;b;c;d; Barnes et al., 2020a;b; 2019). The second one is due to Acharya et al. (2021e; 2018). It adapts Le Cam's, Fano's and Assouard's methods to differential privacy. Their work will be our main point of comparison, since we believe that our work nicely complements theirs by providing a somewhat *plug-and-play* framework, notably allowing to establish results for other types of privacy.

Indeed, the present work extends classical techniques like Le Cam and Fano for proving minimax lower bounds to the setting where the estimator must additionally be differentially private. While this was previously done by Acharya et al. (2021e; 2018) in the specific context of $(\epsilon, \delta)$-differential privacy, our contribution improves upon that work by getting quantitative bounds that are both tighter (e.g. by large constants in the exponent) and somewhat *plug-and-play* in that they apply to a variety of differential privacy variants, and notably to the setting of *zero-concentrated differential privacy (zCDP)*, bridging the theoretical gap with very recent work in that field (Kamath et al., 2022). As applications, we extend known rates for estimating the parameter of a Bernoulli distribution and for estimating the mean of a high-dimensional spherical Gaussian to the zCDP setting. We also show that for the problem of estimating the support of a uniform distribution over an unknown interval inside $[0,1]$, the minimax risk is *uniformly degraded* by the privacy constraint. This constrasts with Bernoulli and Gaussian mean estimation, and is perhaps somewhat surprising, as one usually expects bounds for which there are parameter regimes under which the non-private minimax risk dominates.

Lastly, we show a private minimax lower bound for maximum likelihood estimation, when the log likelihood is concave and smooth in the parameter being estimated and satisfies some additional non-degeneracy assumptions, and show that private SGLD qualitatively matches this lower bound in terms of sample size and privacy parameter dependence.

## 1.1 The Minimax Risk and Private Estimators

We start by defining the minimax risk. Given $n \in \mathbb{N}_*$ and a Polish feature space $\mathcal{X}$, $\mathcal{X}^n$ may be viewed as a set of datasets containing $n$ elements from $\mathcal{X}$. We consider a family of probability distributions $(\mathbb{P}_{\theta})_{\theta \in \Theta}$ on $\mathcal{X}^n$ where $\Theta$ is equipped with a semi-metric<fnref n="1" /> $d_{\Theta}: \Theta^2 \rightarrow \mathbb{R}_+$. Often, for all $\theta \in \Theta$, $\mathbb{P}_{\theta} = \mathbb{P}_{\theta}^{\otimes n}$ where $(\mathbb{P}_{\theta})_{\theta \in \Theta}$ is a family of probability distributions on $\mathcal{X}$. This corresponds to the classical statistical setup where we observe $n$ i.i.d. random variables. The general setup allows capturing phenomena that are not i.i.d., for instance Markov processes. Given an estimator $\hat{\theta}: \mathcal{X}^n \rightarrow \Theta$ one might look at its uniform risk of estimation

<footnote n="1">¹i.e. that is positive, symmetric, that satisfies the triangular inequality and $d_{\Theta}(\theta, \theta) = 0, \forall \theta \in \Theta$</footnote>
for a loss function $\Phi: [0, +\infty) \to [0, +\infty)$ that is non-decreasing and such that $\Phi(0) = 0$ which is

$$ \sup_{\theta \in \Theta} \int_{\mathcal{X}^n} \Phi(d_{\Theta}(\hat{\theta}(\mathbf{X}), \theta)) d\mathbb{P}_{\theta}(\mathbf{X}). $$

The best achievable uniform risk defines what is called the minimax risk

$$ \mathfrak{M}_n ((\mathbb{P}_{\theta})_{\theta \in \Theta}, d_{\Theta}, \Phi) := \inf_{\hat{\theta}} \sup_{\theta \in \Theta} \int_{\mathcal{X}^n} \Phi(d_{\Theta}(\hat{\theta}(\mathbf{X}), \theta)) d\mathbb{P}_{\theta}(\mathbf{X}). \quad (1) $$

Here, the infimum over $\hat{\theta}$ is taken among all possible measurable functions of the samples.

When an estimator $\hat{\theta} = \hat{\theta}(\mathbf{X})$ is to be made public or is to be shared with some untrustworthy agents and when the records of $\mathbf{X}$ are sensitive (on a privacy standpoint), the disclosure of $\hat{\theta}$ may reveal a lot of information about the records of $\mathbf{X}$. Against this background, differential privacy (Dwork et al., 2006) offers strong privacy guarantees. Given a (randomized) mechanism $\mathfrak{M}$, dom($\mathfrak{M}$) refers to its domain (i.e. the set of admissible inputs) and codom($\mathfrak{M}$) refers to its codomain (i.e. the set of admissible outputs). A differentially private mechanism $\mathfrak{M}: \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ ensures that limited information can be inferred on the records of $\mathbf{X} \in \mathcal{X}^n$ from the sole observation of the output $\mathfrak{M}(\mathbf{X})$. Given $\epsilon \in \mathbb{R}_{+*}$ and $\delta \in [0, 1)$, a randomized mechanism $\mathfrak{M}: \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ is $(\epsilon, \delta)$-differentially private (or $(\epsilon, \delta)$-DP) if for all $\mathbf{X}, \mathbf{Y} \in \mathcal{X}^n$ and all measurable $S \subseteq \text{codom}(\mathfrak{M})$ we have

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

Note that $d_{\text{ham}}(\cdot, \cdot)$ denotes the Hamming distance on $\mathcal{X}^n$. There is however no consensus yet on the "correct" definition of privacy and a few other useful definitions have emerged. For instance, more recent definitions of privacy are due to the need to sharply count the privacy of a composition of many Gaussian mechanisms. At first it was done implicitly via the so-called moment accountant method (Abadi et al., 2016) before being formalized under the name of Renyi differential privacy (Mironov, 2017). Nowadays, it seems that all these notions tend to converge towards the definition of zero concentrated differential privacy (Dwork & Rothblum, 2016; Bun & Steinke, 2016). This is the one that we will investigate in this article in addition to the $(\epsilon, \delta)$-differential privacy, but the results and the proofs can easily be adapted to other definitions that are based on Renyi divergences. Given $\rho \in (0, +\infty)$, a randomized mechanism $\mathfrak{M}: \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ is $\rho$-zero concentrated differentially private ($\rho$-zCDP) if for all $\mathbf{X}, \mathbf{Y} \in \mathcal{X}^n$,

$$ d_{\text{ham}}(\mathbf{X}, \mathbf{Y}) \le 1 \implies D_{\alpha}(\mathfrak{M}(\mathbf{X}) \| \mathfrak{M}(\mathbf{Y})) \le \rho\alpha, \forall 1 < \alpha < +\infty. $$

The Renyi divergence of level $\alpha$, $D_{\alpha}(\cdot \| \cdot)$, is properly defined in Appendix A. There exist links between $(\epsilon, \delta)$-DP and $\rho$-zCDP. For instance, Bun & Steinke (2016, Proposition 3) states that if a mechanism is $\rho$-zCDP, it is $(\epsilon, \delta)$-DP for a collection of $(\epsilon, \delta)$'s that depend on $\rho$. In particular, finding minimax lower bounds for $\rho$-zCDP mechanisms can be done by taking the supremum of lower bounds on $(\epsilon, \delta)$-DP mechanisms. But as we will see later, we can do better directly. Conversely, if a mechanism is $(\epsilon, 0)$-DP, it is also $\epsilon^2/2$-zCDP (see Bun & Steinke (2016, Proposition 4)).

In order to factorize the results, we will use the abstract formulation that a randomized mechanism $\mathfrak{M}: \mathcal{X}^n \to \Theta$ satisfies a certain condition $\mathcal{C}$ rather than fixing the class in which it belongs. We define the private minimax risk as the best achievable uniform risk with mechanisms that satisfy the privacy condition $\mathcal{C}$ (using the set convention, $\mathcal{C}$ can alternatively refer to the set of estimators that satisfy this condition)

$$ \mathfrak{M}_n (\mathcal{C}, (\mathbb{P}_{\theta})_{\theta \in \Theta}, d_{\Theta}, \Phi) := \inf_{\mathfrak{M} \in \mathcal{C}} \sup_{\theta \in \Theta} \int_{\mathcal{X}^n} \mathbb{E}_{\mathbb{P}_{\mathfrak{M}}} (\Phi(d_{\Theta}(\mathfrak{M}(\mathbf{X}), \theta))) d\mathbb{P}_{\theta}(\mathbf{X}). \quad (2) $$

Because of their similarities, we use $\mathfrak{M}_n$ to refer to both the non-private minimax risk and its private counterpart. With four arguments, $\mathfrak{M}_n$ should be understood as the private minimax risk and when equipped with three arguments it is simply the regular minimax risk.
over $\Theta$ for a loss function $\Phi: [0, +\infty) \to [0, +\infty)$ that is non-decreasing and such that $\Phi(0) = 0$ which is

$$ \sup_{\theta \in \Theta} \int_{\mathcal{X}^n} \Phi(d_{\Theta}(\hat{\theta}(\mathbf{X}), \theta)) d\mathbb{P}_{\theta}(\mathbf{X}). $$

The best achievable uniform risk defines what is called the minimax risk

$$ \mathfrak{M}_n ((\mathbb{P}_{\theta})_{\theta \in \Theta}, d_{\Theta}, \Phi) := \inf_{\hat{\theta}} \sup_{\theta \in \Theta} \int_{\mathcal{X}^n} \Phi(d_{\Theta}(\hat{\theta}(\mathbf{X}), \theta)) d\mathbb{P}_{\theta}(\mathbf{X}). \quad (1) $$

Here, the infimum over $\hat{\theta}$ is taken among all possible measurable functions of the samples.

When an estimator $\hat{\theta} = \hat{\theta}(\mathbf{X})$ is to be made public or is to be shared with some untrustworthy agents and when the records of $\mathbf{X}$ are sensitive (on a privacy standpoint), the disclosure of $\hat{\theta}$ may reveal a lot of information about the records of $\mathbf{X}$. Against this background, differential privacy (Dwork et al., 2006) offers strong privacy guarantees. Given a (randomized) mechanism $\mathfrak{M}$, dom($\mathfrak{M}$) refers to its domain (i.e. the set of admissible inputs) and codom($\mathfrak{M}$) refers to its codomain (i.e. the set of admissible outputs). A differentially private mechanism $\mathfrak{M}: \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ ensures that limited information can be inferred on the records of $\mathbf{X} \in \mathcal{X}^n$ from the sole observation of the output $\mathfrak{M}(\mathbf{X})$. Given $\epsilon \in \mathbb{R}_{+*}$ and $\delta \in [0, 1)$, a randomized mechanism $\mathfrak{M}: \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ is $(\epsilon, \delta)$-differentially private (or $(\epsilon, \delta)$-DP) if for all $\mathbf{X}, \mathbf{Y} \in \mathcal{X}^n$ and all measurable $S \subseteq \text{codom}(\mathfrak{M})$ we have

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

Note that $d_{\text{ham}}(\cdot, \cdot)$ denotes the Hamming distance on $\mathcal{X}^n$. There is however no consensus yet on the "correct" definition of privacy and a few other useful definitions have emerged. For instance, more recent definitions of privacy are due to the need to sharply count the privacy of a composition of many Gaussian mechanisms. At first it was done implicitly via the so-called moment accountant method (Abadi et al., 2016) before being formalized under the name of Renyi differential privacy (Mironov, 2017). Nowadays, it seems that all these notions tend to converge towards the definition of zero concentrated differential privacy (Dwork & Rothblum, 2016; Bun & Steinke, 2016). This is the one that we will investigate in this article in addition to the $(\epsilon, \delta)$-differential privacy, but the results and the proofs can easily be adapted to other definitions that are based on Renyi divergences. Given $\rho \in (0, +\infty)$, a randomized mechanism $\mathfrak{M}: \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ is $\rho$-zero concentrated differentially private ($\rho$-zCDP) if for all $\mathbf{X}, \mathbf{Y} \in \mathcal{X}^n$,

$$ d_{\text{ham}}(\mathbf{X}, \mathbf{Y}) \le 1 \implies D_{\alpha}(\mathfrak{M}(\mathbf{X}) \| \mathfrak{M}(\mathbf{Y})) \le \rho\alpha, \forall 1 < \alpha < +\infty. $$

The Renyi divergence of level $\alpha$, $D_{\alpha}(\cdot \| \cdot)$, is properly defined in Appendix A. There exist links between $(\epsilon, \delta)$-DP and $\rho$-zCDP. For instance, Bun & Steinke (2016, Proposition 3) states that if a mechanism is $\rho$-zCDP, it is $(\epsilon, \delta)$-DP for a collection of $(\epsilon, \delta)$'s that depend on $\rho$. In particular, finding minimax lower bounds for $\rho$-zCDP mechanisms can be done by taking the supremum of lower bounds on $(\epsilon, \delta)$-DP mechanisms. But as we will see later, we can do better directly. Conversely, if a mechanism is $(\epsilon, 0)$-DP, it is also $\epsilon^2/2$-zCDP (see Bun & Steinke (2016, Proposition 4)).

In order to factorize the results, we will use the abstract formulation that a randomized mechanism $\mathfrak{M}: \mathcal{X}^n \to \Theta$ satisfies a certain condition $C$ rather than fixing the class in which it belongs. We define the private minimax risk as the best achievable uniform risk with mechanisms that satisfy the privacy condition $C$ (using the set convention, $C$ can alternatively refer to the set of estimators that satisfy this condition)

$$ \mathfrak{M}_n (C, (\mathbb{P}_{\theta})_{\theta \in \Theta}, d_{\Theta}, \Phi) := \inf_{\mathfrak{M} \in C} \sup_{\theta \in \Theta} \int_{\mathcal{X}^n} \mathbb{E}_{\mathbb{P}_{\mathfrak{M}}} (\Phi(d_{\Theta}(\mathfrak{M}(\mathbf{X}), \theta))) d\mathbb{P}_{\theta}(\mathbf{X}). \quad (2) $$

Because of their similarities, we use $\mathfrak{M}_n$ to refer to both the non-private minimax risk and its private counterpart. With four arguments, $\mathfrak{M}_n$ should be understood as the private minimax risk and when equipped with three arguments it is simply the regular minimax risk.
## 1.2 Introducing example

As a warmup we discuss here the simplest possible example on which we can present the questions that this article addresses and the flavor of the developed approaches. Let $p_1 < p_2$ be two parameters in $(0, 1)$ and let $U_1, \dots, U_n$, $n$ be independent and identically distributed uniform random variables on $[0, 1]$. The random variables $Z_i := (X_i^{(1)}, X_i^{(2)}) \in \mathbb{R}^2$, $1 \le i \le n$, defined by

$$ (X_i^{(1)}, X_i^{(2)}) = (1_{[0,p_1]}(U_i), 1_{[0,p_2]}(U_i)) $$

are independent and identically distributed with marginal distributions Bernoulli $\mathcal{B}(p_1)$ and $\mathcal{B}(p_2)$. In the sequel we note $\mathbf{X}^{(j)} = (X_1^{(j)}, \dots, X_n^{(j)})$, $j = 1, 2$, $\mathbf{U} = (U_1, \dots, U_n)$, $S_1 := [0, (p_1 + p_2)/2)$, and $S_2 := [(p_1 + p_2)/2, 1]$. Given any $(\epsilon, 0)$-DP mechanism $\mathfrak{M}: [0, 1]^n \to [0, 1]$ (where $\epsilon > 0$) to estimate the Bernoulli parameter, the risk satisfies

$$ \begin{aligned} & \sup_{p \in [0,1]} \mathbb{E}_{\mathbf{X} \sim \mathcal{B}(p)^{\otimes n}} \left( (\mathfrak{M}(\mathbf{X}) - p)^2 \right) \\ & \geq \left( \mathbb{E}_{\mathbf{X} \sim \mathcal{B}(p_1)^{\otimes n}} \left( (\mathfrak{M}(\mathbf{X}) - p_1)^2 \right) + \mathbb{E}_{\mathbf{X} \sim \mathcal{B}(p_2)^{\otimes n}} \left( (\mathfrak{M}(\mathbf{X}) - p_2)^2 \right) \right) / 2 \\ & \stackrel{\text{Coupling}}{=} \left( \mathbb{E}_{\mathbf{U}, \mathfrak{M}} \left( (\mathfrak{M}(\mathbf{X}^{(1)}) - p_1)^2 \right) + \mathbb{E}_{\mathbf{U}, \mathfrak{M}} \left( (\mathfrak{M}(\mathbf{X}^{(2)}) - p_2)^2 \right) \right) / 2 \\ & \stackrel{\text{Conditioning}}{=} \mathbb{E}_{\mathbf{U}} \left( \mathbb{E}_{\mathfrak{M}} \left( (\mathfrak{M}(\mathbf{X}^{(1)}) - p_1)^2 \right) + \mathbb{E}_{\mathfrak{M}} \left( (\mathfrak{M}(\mathbf{X}^{(2)}) - p_2)^2 \right) \right) / 2 \\ & \geq \left( \frac{p_2 - p_1}{2} \right)^2 \mathbb{E}_{\mathbf{U}} \left( \mathbb{P}_{\mathfrak{M}} \left( \mathfrak{M}(\mathbf{X}^{(1)}) \in S_2 \right) + \mathbb{P}_{\mathfrak{M}} \left( \mathfrak{M}(\mathbf{X}^{(2)}) \in S_1 \right) \right) / 2. \end{aligned} \quad (3) $$

This is where the DP property yields a lower bound on the second factor as

$$ \begin{aligned} & \mathbb{E}_{\mathbf{U}} \left( e^{-\epsilon d_{\text{ham}}(\mathbf{X}^{(1)}, \mathbf{X}^{(2)})} \mathbb{P}_{\mathfrak{M}} \left( \mathfrak{M}(\mathbf{X}^{(2)}) \in S_2 \right) + \mathbb{P}_{\mathfrak{M}} \left( \mathfrak{M}(\mathbf{X}^{(2)}) \in S_1 \right) \right) \\ & \stackrel{d_{\text{ham}}(\cdot, \cdot) \ge 0}{\ge} \mathbb{E}_{\mathbf{U}} \left( e^{-\epsilon d_{\text{ham}}(\mathbf{X}^{(1)}, \mathbf{X}^{(2)})} \left( \mathbb{P}_{\mathfrak{M}} \left( \mathfrak{M}(\mathbf{X}^{(2)}) \in S_2 \right) + \mathbb{P}_{\mathfrak{M}} \left( \mathfrak{M}(\mathbf{X}^{(2)}) \in S_1 \right) \right) \right) \quad (4) \\ & = \mathbb{E}_{\mathbf{U}} \left( e^{-\epsilon d_{\text{ham}}(\mathbf{X}^{(1)}, \mathbf{X}^{(2)})} \right) \stackrel{\text{Jensen}}{\ge} e^{-n\epsilon|p_2 - p_1|}, \end{aligned} $$

which overall yields the lower bound $(\frac{p_2 - p_1}{8})^2 e^{-n\epsilon|p_2 - p_1|}$. A good lower bound on the minimax risk is then provided by optimizing over $p_1$ and $p_2$. For instance, when $n \ge \frac{2}{\epsilon}$, $p_1 = \frac{1}{2}$ and $p_2 = \frac{1}{2} + \frac{1}{n\epsilon}$ leads to

$$ \sup_{p \in [0,1]} \mathbb{E}_{\mathbf{X} \sim \mathcal{B}(p)^{\otimes n}} \left( (\mathfrak{M}(\mathbf{X}) - p)^2 \right) \geq \frac{1}{8} \frac{1}{(n\epsilon)^2}. $$

The idea behind the first inequality in (3) is classical in the minimax literature and is recalled in Section 1.3 using the notion of packing. The coupling construction can be generalized and tailored to other settings and has a critical impact on the deduced lower bounds, as we present in Section 3. The minoration involving differential privacy is a special case of the techniques that we formalize under the notion of admissible similarity functions in Section 2, which are adapted to various types of privacy constraints. Practical implications of such generalizations are described in Section 1.4.

## 1.3 From Minimax Lower Bounds to Hypothesis Testing

A classical technique (see Duchi et al. (2013a)) for finding lower bounds on $\mathfrak{M}_n((\mathbb{P}_{\theta})_{\theta \in \Theta}, d_{\Theta}, \Phi)$ is to replace the parameter set $\Theta$ by a much “simpler” set $\Theta' \subseteq \Theta$ and to use the trivial lower bound

$$ \mathfrak{M}_n((\mathbb{P}_{\theta})_{\theta \in \Theta}, d_{\Theta}, \Phi) \geq \inf_{\theta} \sup_{\theta' \in \Theta'} \int_{\mathcal{X}^n} \Phi(d_{\Theta}(\hat{\theta}(\mathbf{X}), \theta)) d\mathbb{P}_{\theta}(\mathbf{X}). $$

Usually $\Theta'$ is chosen as an $\Omega$-packing of $\Theta$, for some real number $\Omega > 0$: it is a countable family $\Theta' := \{\theta_i, i \in \mathbb{N}_*\}$ ($\theta_i$)$_{i \in \mathbb{N}_*}$ (and most of the time, including in this article, it is taken to be finite) such that: a) $\theta_i \in \Theta$ for all $i$; b) $i \neq j \Rightarrow d_{\Theta}(\theta_i, \theta_j) \ge 2\Omega$; and c) there is a well-defined function $\Psi_{\Theta'}$ satisfying

$$ \Psi_{\Theta'}(\theta) \in \arg \min_{i \ge 1} d_{\Theta}(\theta_i, \theta) $$
## 1.2 Introducing example

As a warmup we discuss here the simplest possible example on which we can present the questions that this article addresses and the flavor of the developed approaches. Let $p_1 < p_2$ be two parameters in $(0, 1)$ and let $U_1, \dots, U_n$, $n$ be independent and identically distributed uniform random variables on $[0, 1]$. The random variables $Z_i := (X_i^{(1)}, X_i^{(2)}) \in \mathbb{R}^2$, $1 \le i \le n$, defined by

$$ (X_i^{(1)}, X_i^{(2)}) = (1_{[0,p_1]}(U_i), 1_{[0,p_2]}(U_i)) $$

are independent and identically distributed with marginal distributions Bernoulli $\mathcal{B}(p_1)$ and $\mathcal{B}(p_2)$. In the sequel we note $\mathbf{X}^{(j)} = (X_1^{(j)}, \dots, X_n^{(j)})$, $j = 1, 2$, $\mathbf{U} = (U_1, \dots, U_n)$, $S_1 := [0, (p_1 + p_2)/2)$, and $S_2 := [(p_1 + p_2)/2, 1]$. Given any $(\epsilon, 0)$-DP mechanism $\mathfrak{M}: [0, 1]^n \to [0, 1]$ (where $\epsilon > 0$) to estimate the Bernoulli parameter, the risk satisfies

$$ \begin{aligned} & \sup_{p \in [0,1]} \mathbb{E}_{\mathbf{X} \sim \mathcal{B}(p)^{\otimes n}} \left( (\mathfrak{M}(\mathbf{X}) - p)^2 \right) \\ & \geq \left( \mathbb{E}_{\mathbf{X} \sim \mathcal{B}(p_1)^{\otimes n}} \left( (\mathfrak{M}(\mathbf{X}) - p_1)^2 \right) + \mathbb{E}_{\mathbf{X} \sim \mathcal{B}(p_2)^{\otimes n}} \left( (\mathfrak{M}(\mathbf{X}) - p_2)^2 \right) \right) / 2 \\ & \stackrel{\text{Coupling}}{=} \left( \mathbb{E}_{\mathbf{U}, \mathfrak{M}} \left( (\mathfrak{M}(\mathbf{X}^{(1)}) - p_1)^2 \right) + \mathbb{E}_{\mathbf{U}, \mathfrak{M}} \left( (\mathfrak{M}(\mathbf{X}^{(2)}) - p_2)^2 \right) \right) / 2 \\ & \stackrel{\text{Conditioning}}{=} \mathbb{E}_{\mathbf{U}} \left( \mathbb{E}_{\mathfrak{M}} \left( (\mathfrak{M}(\mathbf{X}^{(1)}) - p_1)^2 \right) + \mathbb{E}_{\mathfrak{M}} \left( (\mathfrak{M}(\mathbf{X}^{(2)}) - p_2)^2 \right) \right) / 2 \\ & \geq \left( \frac{p_2 - p_1}{2} \right)^2 \mathbb{E}_{\mathbf{U}} \left( \mathbb{P}_{\mathfrak{M}} \left( \mathfrak{M}(\mathbf{X}^{(1)}) \in S_2 \right) + \mathbb{P}_{\mathfrak{M}} \left( \mathfrak{M}(\mathbf{X}^{(2)}) \in S_1 \right) \right) / 2. \end{aligned} \quad (3) $$

This is where the DP property yields a lower bound on the second factor as

$$ \begin{aligned} & \mathbb{E}_{\mathbf{U}} \left( e^{-\epsilon d_{\text{ham}}(\mathbf{X}^{(1)}, \mathbf{X}^{(2)})} \mathbb{P}_{\mathfrak{M}} \left( \mathfrak{M}(\mathbf{X}^{(2)}) \in S_2 \right) + \mathbb{P}_{\mathfrak{M}} \left( \mathfrak{M}(\mathbf{X}^{(2)}) \in S_1 \right) \right) \\ & \stackrel{d_{\text{ham}}(\cdot, \cdot) \ge 0}{\ge} \mathbb{E}_{\mathbf{U}} \left( e^{-\epsilon d_{\text{ham}}(\mathbf{X}^{(1)}, \mathbf{X}^{(2)})} \left( \mathbb{P}_{\mathfrak{M}} \left( \mathfrak{M}(\mathbf{X}^{(2)}) \in S_2 \right) + \mathbb{P}_{\mathfrak{M}} \left( \mathfrak{M}(\mathbf{X}^{(2)}) \in S_1 \right) \right) \right) \quad (4) \\ & = \mathbb{E}_{\mathbf{U}} \left( e^{-\epsilon d_{\text{ham}}(\mathbf{X}^{(1)}, \mathbf{X}^{(2)})} \right) \stackrel{\text{Jensen}}{\ge} e^{-n\epsilon|p_2 - p_1|}, \end{aligned} $$

which overall yields the lower bound $\frac{(p_2 - p_1)^2}{8}e^{-n\epsilon|p_2 - p_1|}$. A good lower bound on the minimax risk is then provided by optimizing over $p_1$ and $p_2$. For instance, when $n \ge \frac{2}{\epsilon}$, $p_1 = \frac{1}{2}$ and $p_2 = \frac{1}{2} + \frac{1}{n\epsilon}$ leads to

$$ \sup_{p \in [0,1]} \mathbb{E}_{\mathbf{X} \sim \mathcal{B}(p)^{\otimes n}} \left( (\mathfrak{M}(\mathbf{X}) - p)^2 \right) \geq \frac{1}{8} \frac{1}{(n\epsilon)^2}. $$

The idea behind the first inequality in (3) is classical in the minimax literature and is recalled in Section 1.3 using the notion of packing. The coupling construction can be generalized and tailored to other settings and has a critical impact on the deduced lower bounds, as we present in Section 3. The minoration involving differential privacy is a special case of the techniques that we formalize under the notion of admissible similarity functions in Section 2, which are adapted to various types of privacy constraints. Practical implications of such generalizations are described in Section 1.4.

## 1.3 From Minimax Lower Bounds to Hypothesis Testing

A classical technique (see Duchi et al. (2013)) for finding lower bounds on $\mathfrak{M}_n((\mathbb{P}_{\theta})_{\theta \in \Theta}, d_{\Theta}, \Phi)$ is to replace the parameter set $\Theta$ by a much “simpler” set $\Theta' \subseteq \Theta$ and to use the trivial lower bound

$$ \mathfrak{M}_n((\mathbb{P}_{\theta})_{\theta \in \Theta}, d_{\Theta}, \Phi) \geq \inf_{\theta} \sup_{\theta' \in \Theta'} \int_{\mathcal{X}^n} \Phi(d_{\Theta}(\hat{\theta}(\mathbf{X}), \theta)) d\mathbb{P}_{\theta}(\mathbf{X}). $$

Usually $\Theta'$ is chosen as an $\Omega$-packing of $\Theta$, for some real number $\Omega > 0$: it is a countable family $\Theta' := \{\theta_i, i \in \mathbb{N}_*\}$ ($\theta_i$)$_{i \in \mathbb{N}_*}$ (and most of the time, including in this article, it is taken to be finite) such that: a) $\theta_i \in \Theta$ for all $i$; b) $i \neq j \Rightarrow d_{\Theta}(\theta_i, \theta_j) \ge 2\Omega$; and c) there is a well-defined function $\Psi_{\Theta'}$ satisfying

$$ \Psi_{\Theta'}(\theta) \in \arg \min_{i \ge 1} d_{\Theta}(\theta_i, \theta) $$
for each $\theta \in \Theta$. Under such hypotheses, any estimator $\hat{\theta}$ satisfies (Duchi et al., 2013a)

$$ \sup_{\theta \in \Theta'} \int_{\mathcal{X}^n} \Phi(d_{\Theta}(\hat{\theta}(\mathbf{X}), \theta)) d\mathbb{P}_{\Theta}(\mathbf{X}) \geq \Phi(\Omega) \sup_{i \in \{1, \dots, \#(\Theta')\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_{\Theta_i}} (\Psi_{\Theta'}(\hat{\theta}(\mathbf{X})) \neq i). \quad (5) $$

The mapping $\hat{\Psi} := \Psi_{\Theta'} \circ \hat{\theta} : \mathcal{X}^n \to \{1, \dots, \#(\Theta')\}$ may be viewed as a test function (that selects the model number) and thus

$$ \mathfrak{M}_n((\mathbb{P}_{\Theta})_{\theta \in \Theta}, d_{\Theta}, \Phi) \geq \Phi(\Omega) \inf_{\Psi: \mathcal{X}^n \to \{1, \dots, \#(\Theta')\}} \sup_{i \in \{1, \dots, \#(\Theta')\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_{\Theta_i}} (\Psi(\mathbf{X}) \neq i). \quad (6) $$

Finding minimax lower bounds is thus done by finding a suitable $\Omega$-packing of the parameter space and then by providing lower bounds on

$$ \inf_{\Psi: \mathcal{X}^n \to \{1, \dots, \#(\Theta')\}} \sup_{i \in \{1, \dots, \#(\Theta')\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_{\Theta_i}} (\Psi(\mathbf{X}) \neq i). \quad (7) $$

Two powerful tools to find such lower bounds come from information theory: Le Cam's lemma (see Fact 1) can be used when $\Theta'$ only contains two elements, while Fano's lemma (see Fact 2) is applicable when $\Theta'$ contains $N \geq 2$ elements.

**Fact 1** (Neyman-Pearson & Le Cam's lemma (Rigollet & Hütter, 2015, Lemma 5.3)). Let $\mathbb{P}_1$, $\mathbb{P}_2$ be two probability distributions on a measure space $\mathcal{E}$, then

$$ \begin{aligned} \inf_{\Psi: \mathcal{E} \to \{1, 2\}} \max_{i \in \{1, 2\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i} (\Psi(\mathbf{X}) \neq i) &\geq \frac{1}{2} \inf_{\Psi: \mathcal{E} \to \{1, 2\}} \sum_{i=1}^{2} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i} (\Psi(\mathbf{X}) \neq i) \\ &= \frac{1}{2} (1 - \text{TV}(\mathbb{P}_1, \mathbb{P}_2)). \end{aligned} \quad (8) $$

The Total Variation (TV) is rigorously defined in Appendix A.

**Fact 2** (Fano's lemma (Giraud, 2021, Theorem 3.1)). Let $(\mathbb{P}_i)_{i \in \{1, \dots, N\}}$ be a family of probability distributions on a measure space $\mathcal{E}$. For any probability distribution $\mathbb{Q}$ on $\mathcal{E}$ such that $\mathbb{P}_i \ll \mathbb{Q}$ for all $i$, and for any test function $\Psi: \mathcal{X}^n \to \{1, \dots, N\}$,

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

The KL divergence and the absolute continuity ($\ll$) are rigorously defined in Appendix A. Often $\mathbb{Q}$ is set to $\frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_i$.

With the same reasoning used (Duchi et al., 2013a) to establish (5), with $\Theta' = (\theta_i)_{i \in \{1, \dots, \#(\Theta')\}}$ an $\Omega$-packing of $\Theta$, we can lower-bound the private minimax risk:

$$ \begin{aligned} \mathfrak{M}_n(C, (\mathbb{P}_{\Theta})_{\theta \in \Theta}, d_{\Theta}, \Phi) &\geq \Phi(\Omega) \inf_{\mathfrak{M} \in \mathcal{C}} \inf_{\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, \#(\Theta')\}} \sup_{i \in \{1, \dots, \#(\Theta')\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_{\Theta_i}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i). \end{aligned} \quad (10) $$

Consequently, finding private minimax lower bounds is done analogously to the non-private setting by finding an appropriate $\Omega$-packing and a lower bound on

$$ \inf_{\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, \#(\Theta')\}} \sup_{i \in \{1, \dots, \#(\Theta')\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_{\Theta_i}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \quad (11) $$

that is independent on the mechanism $\mathfrak{M}$ but only depends on the privacy condition $\mathcal{C}$.
for each $\theta \in \Theta$. Under such hypotheses, any estimator $\hat{\theta}$ satisfies (Duchi et al., 2013)

$$ \sup_{\theta \in \Theta'} \int_{\mathcal{X}^n} \Phi(d_{\Theta}(\hat{\theta}(\mathbf{X}), \theta)) d\mathbb{P}_{\theta}(\mathbf{X}) \geq \Phi(\Omega) \sup_{i \in \{1, \dots, \#(\Theta')\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_{\theta_i}} (\Psi_{\Theta'}(\hat{\theta}(\mathbf{X})) \neq i). \quad (5) $$

The mapping $\hat{\Psi} := \Psi_{\Theta'} \circ \hat{\theta} : \mathcal{X}^n \to \{1, \dots, \#(\Theta')\}$ may be viewed as a test function (that selects the model number) and thus

$$ \mathfrak{M}_n((\mathbb{P}_{\theta})_{\theta \in \Theta}, d_{\Theta}, \Phi) \geq \Phi(\Omega) \inf_{\Psi: \mathcal{X}^n \to \{1, \dots, \#(\Theta')\}} \sup_{i \in \{1, \dots, \#(\Theta')\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_{\theta_i}} (\Psi(\mathbf{X}) \neq i). \quad (6) $$

Finding minimax lower bounds is thus done by finding a suitable $\Omega$-packing of the parameter space and then by providing lower bounds on

$$ \inf_{\Psi: \mathcal{X}^n \to \{1, \dots, \#(\Theta')\}} \sup_{i \in \{1, \dots, \#(\Theta')\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_{\theta_i}} (\Psi(\mathbf{X}) \neq i). \quad (7) $$

Two powerful tools to find such lower bounds come from information theory: Le Cam's lemma (see Fact 1) can be used when $\Theta'$ only contains two elements, while Fano's lemma (see Fact 2) is applicable when $\Theta'$ contains $N \geq 2$ elements.

**Fact 1** (Neyman-Pearson & Le Cam's lemma (Rigollet & Hütter, 2015, Lemma 5.3)). Let $\mathbb{P}_1, \mathbb{P}_2$ be two probability distributions on a measure space $\mathcal{E}$, then

$$ \begin{aligned} \inf_{\Psi: \mathcal{E} \to \{1, 2\}} \max_{i \in \{1, 2\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i} (\Psi(\mathbf{X}) \neq i) &\geq \frac{1}{2} \inf_{\Psi: \mathcal{E} \to \{1, 2\}} \sum_{i=1}^{2} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i} (\Psi(\mathbf{X}) \neq i) \\ &= \frac{1}{2} (1 - \text{TV}(\mathbb{P}_1, \mathbb{P}_2)). \end{aligned} \quad (8) $$

The Total Variation (TV) is rigorously defined in Appendix A.

**Fact 2** (Fano's lemma (Giraud, 2021, Theorem 3.1)). Let $(\mathbb{P}_i)_{i \in \{1, \dots, N\}}$ be a family of probability distributions on a measure space $\mathcal{E}$. For any probability distribution $\mathbb{Q}$ on $\mathcal{E}$ such that $\mathbb{P}_i \ll \mathbb{Q}$ for all $i$, and for any test function $\Psi : \mathcal{X}^n \to \{1, \dots, N\}$,

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

The KL divergence and the absolute continuity ($\ll$) are rigorously defined in Appendix A. Often $\mathbb{Q}$ is set to $\frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_i$.

With the same reasoning used (Duchi et al., 2013) to establish (5), with $\Theta' = (\theta_i)_{i \in \{1, \dots, \#(\Theta')\}}$ an $\Omega$-packing of $\Theta$, we can lower-bound the private minimax risk:

$$ \mathfrak{M}_n(\mathcal{C}, (\mathbb{P}_{\theta})_{\theta \in \Theta}, d_{\Theta}, \Phi) \geq \Phi(\Omega) \inf_{\mathfrak{M} \in \mathcal{C}} \inf_{\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, \#(\Theta')\}} \sup_{i \in \{1, \dots, \#(\Theta')\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_{\theta_i}, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i). \quad (10) $$

Consequently, finding private minimax lower bounds is done analogously to the non-private setting by finding an appropriate $\Omega$-packing and a lower bound on

$$ \inf_{\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, \#(\Theta')\}} \sup_{i \in \{1, \dots, \#(\Theta')\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_{\theta_i}, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i). \quad (11) $$

that is independent on the mechanism $\mathfrak{M}$ but only depends on the privacy condition $\mathcal{C}$.
## 1.4 Contributions

The main contribution of this work, presented in Section 2, is to propose a generic framework for the derivation of lower bounds on the minimax risk under various privacy conditions. Here and in the sequel, the symbols $o(\cdot)$, $O(\cdot)$, $\Theta(\cdot)$ and $\Omega(\cdot)$ are used without ambiguity as classical comparison operators for sequences, as recalled in Appendix A. Technically, the techniques of Le Cam and Fano are extended to the private context, reducing the distributional test problem (11) to a Kantorovich problem (Santambrogio, 2015; Peyré et al., 2019) of the form

$$ \sup_{Q \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)} \int_{(\mathcal{X}^n)^N} s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) d\mathbb{Q}(\mathbf{X}_1, \dots, \mathbf{X}_N) . \quad (12) $$

Here, $\Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$ is the set of couplings between the considered distributions and $s_C$ is an admissible similarity function depending on the nature of the constraint $C$ and the number of hypotheses (Theorem 6 and Theorem 7). For instance, regarding $(\epsilon, \delta)$-differential privacy, similarity functions are obtained by comparing datasets to a common anchor. This result is summarized in Theorem 5.

Unlike the prior work of Acharya et al. (2021e), the proposed framework allows us to consider joint couplings across all instances rather than just pairwise couplings. Additionally, the level of generality of our proofs leaves room for subsequent work to build upon this framework.

The general idea behind the proofs is as follows. In classical Fano's, one considers the decoding error probability: on average over a family of instances, what is the probability that the estimator, given samples from a given instance, fails to identify that the samples came from that instance. In place of Fano's inequality, the present work lower bounds this by noting that, given datasets $\mathbf{X}_1, \dots, \mathbf{X}_N$ coming from each instance, as well as an "anchor" dataset $\Lambda$ (or alternatively an anchor distribution), differential privacy implies that the probability that the estimator decides $\mathbf{X}_i$ comes from instance $i$ cannot differ by much from the probability it decides $\Lambda$ comes from instance $i$, provided $\Lambda$ and $\mathbf{X}_i$ are similar. The decoding error probability can thus be lower bounded in terms of the maximum distance between $\Lambda$ and any of $\mathbf{X}_1, \dots, \mathbf{X}_N$, averaged over the randomness of $\mathbf{X}_1, \dots, \mathbf{X}_N$, where there is freedom in choosing how to couple this randomness.

Section 3 includes various coupling constructions yielding quantitative lower bounds for the Kantorovich formulation (12). These constructions only depend on the number of hypotheses $N$, the sample size $n$, the privacy parameters $\epsilon, \delta, \rho$, and information theoretic quantities such as the pairwise total variations or KL divergences between the distributions.

Those results will be presented in Section 2 and in Section 3. We showcase now useful consequences, starting with the case $N = 2$: similarly to Acharya et al. (2021e), we extend Le Cam's lemma to the $(\epsilon, \delta)$-differentially private setting:

**Theorem 1 (Le Cam for $(\epsilon, \delta)$-DP).** If a randomized mechanism $\mathfrak{M}$ satisfies $(\epsilon, \delta)$-DP, then for any test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, 2\}$ and any probability distributions $\mathbb{P}_1$ and $\mathbb{P}_2$ on $\mathcal{X}^n$ we have

$$ \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} \max \left\{ 1 - \text{TV}(\mathbb{P}_1, \mathbb{P}_2), \right. \\ \left. 1 - (1 - e^{-n\epsilon} + 2ne^{-\epsilon\delta}) \text{TV}(\mathbb{P}_1, \mathbb{P}_2) \right\}. $$

Furthermore, when $\mathbb{P}_1 = \mathbb{P}_1^{\otimes n}$ and $\mathbb{P}_2 = \mathbb{P}_2^{\otimes n}$ are product distributions,

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

The proof can be found in Appendix C. The classical lower bound of Le Cam (8) allows for a tunable testing difficulty depending on TV($\mathbb{P}_1, \mathbb{P}_2$). However, in the regime $\epsilon, \delta = o(1/n)$, the private lower bound is $\Omega(1)$: it becomes arbitrarily hard to distinguish between any pair of distributions.
## 1.4 Contributions

The main contribution of this work, presented in Section 2, is to propose a generic framework for the derivation of lower bounds on the minimax risk under various privacy conditions. Here and in the sequel, the symbols $o(\cdot)$, $O(\cdot)$, $\Theta(\cdot)$ and $\Omega(\cdot)$ are used without ambiguity as classical comparison operators for sequences, as recalled in Appendix A. Technically, the techniques of Le Cam and Fano are extended to the private context, reducing the distributional test problem (11) to a Kantorovich problem (Santambrogio, 2016; Peyré & Cuturi, 2019) of the form

$$ \sup_{Q \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)} \int_{(\mathcal{X}^n)^N} s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) d\mathbb{Q}(\mathbf{X}_1, \dots, \mathbf{X}_N) . \quad (12) $$

Here, $\Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$ is the set of couplings between the considered distributions and $s_C$ is an admissible similarity function depending on the nature of the constraint $C$ and the number of hypotheses (Theorem 6 and Theorem 7). For instance, regarding $(\epsilon, \delta)$-differential privacy, similarity functions are obtained by comparing datasets to a common anchor. This result is summarized in Theorem 5.

Unlike the prior work of Acharya et al. (2021e), the proposed framework allows us to consider joint couplings across all instances rather than just pairwise couplings. Additionally, the level of generality of our proofs leaves room for subsequent work to build upon this framework.

The general idea behind the proofs is as follows. In classical Fano's, one considers the decoding error probability: on average over a family of instances, what is the probability that the estimator, given samples from a given instance, fails to identify that the samples came from that instance. In place of Fano's inequality, the present work lower bounds this by noting that, given datasets $\mathbf{X}_1, \dots, \mathbf{X}_N$ coming from each instance, as well as an "anchor" dataset $\Lambda$ (or alternatively an anchor distribution), differential privacy implies that the probability that the estimator decides $\mathbf{X}_i$ comes from instance $i$ cannot differ by much from the probability it decides $\Lambda$ comes from instance $i$, provided $\Lambda$ and $\mathbf{X}_i$ are similar. The decoding error probability can thus be lower bounded in terms of the maximum distance between $\Lambda$ and any of $\mathbf{X}_1, \dots, \mathbf{X}_N$, averaged over the randomness of $\mathbf{X}_1, \dots, \mathbf{X}_N$, where there is freedom in choosing how to couple this randomness.

Section 3 includes various coupling constructions yielding quantitative lower bounds for the Kantorovich formulation (12). These constructions only depend on the number of hypotheses $N$, the sample size $n$, the privacy parameters $\epsilon, \delta, \rho$, and information theoretic quantities such as the pairwise total variations or KL divergences between the distributions.

Those results will be presented in Section 2 and in Section 3. We showcase now useful consequences, starting with the case $N = 2$: similarly to Acharya et al. (2021e), we extend Le Cam's lemma to the $(\epsilon, \delta)$-differentially private setting:

**Theorem 1** (Le Cam for $(\epsilon, \delta)$-DP). If a randomized mechanism $\mathfrak{M}$ satisfies $(\epsilon, \delta)$-DP, then for any test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, 2\}$ and any probability distributions $\mathbb{P}_1$ and $\mathbb{P}_2$ on $\mathcal{X}^n$ we have

$$ \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} \max \left\{ 1 - \text{TV}(\mathbb{P}_1, \mathbb{P}_2), \right. \\ \left. 1 - (1 - e^{-n\epsilon} + 2ne^{-\epsilon\delta}) \text{TV}(\mathbb{P}_1, \mathbb{P}_2) \right\}. $$

Furthermore, when $\mathbb{P}_1 = \mathbb{P}_1^{\otimes n}$ and $\mathbb{P}_2 = \mathbb{P}_2^{\otimes n}$ are product distributions,

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

The proof can be found in Appendix C. The classical lower bound of Le Cam (8) allows for a tunable testing difficulty depending on TV($\mathbb{P}_1, \mathbb{P}_2$). However, in the regime $\epsilon, \delta = o(1/n)$, the private lower bound is $\Omega(1)$: it becomes arbitrarily hard to distinguish between any pair of distributions.
For i.i.d. observations ($\mathbb{P}_i = \mathbb{P}_i^{\otimes n}$), it follows by convexity that for any $(\epsilon, \delta)$-DP mechanism $\mathfrak{M}$ and test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, 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( e^{-\epsilon n \text{TV}(\mathbb{P}_1, \mathbb{P}_2)} - 2e^{-\epsilon} \delta n \text{TV}(\mathbb{P}_1, \mathbb{P}_2) \right). $$

This is to be compared to the state of the art lower bound of Acharya et al. (2021e, Theorem 1):

$$ \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( 0.9e^{-10\epsilon n \text{TV}(\mathbb{P}_1, \mathbb{P}_2)} - 10\delta n \text{TV}(\mathbb{P}_1, \mathbb{P}_2) \right). $$

Theorem 1 gives tighter results with better constants, notably thanks to a different proof technique avoiding some convexity and concentration inequalities, but also because Acharya et al. (2021e) did not optimize the constants. Indeed, qualitative results and rates of convergence do usually not depend on them.

We also prove an equivalent for so-called $\rho$-zero concentrated differential privacy (or in short $\rho$-zCDP), which is, to the best of our knowledge, the first successful attempt at doing so.

**Theorem 2** (Le Cam for $\rho$-zCDP). If a randomized mechanism $\mathfrak{M}$ satisfies $\rho$-zCDP, then for any test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$ and any probability distributions $\mathbb{P}_1$ and $\mathbb{P}_2$ on $\mathcal{X}^n$,

$$ \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} \max \left\{ 1 - \text{TV}(\mathbb{P}_1, \mathbb{P}_2), \right. \\ \left. 1 - n \sqrt{\rho/2} \text{TV}(\mathbb{P}_1, \mathbb{P}_2) \right\}. $$

Furthermore, when $\mathbb{P}_1 = \mathbb{P}_1^{\otimes n}$ and $\mathbb{P}_2 = \mathbb{P}_2^{\otimes n}$ are product distributions,

$$ \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 proof of this result can be found in Appendix C. As above, any two distributions can no longer be distinguished in the regime $\rho \ll 1/n^2$. For more than two hypotheses and $(\epsilon, \delta)$-DP, we also get a private version of Fano's lemma.

**Theorem 3** (Multiple Distributional Tests for $(\epsilon, \delta)$-DP). If a randomized mechanism $\mathfrak{M}$ satisfies $(\epsilon, \delta)$-DP, then for any test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$, any family of probability distributions $(\mathbb{P}_i)_{i \in \{1, \dots, N\}}$ on $\mathcal{X}^n$ and 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 \max \left\{ 1 - \frac{1 + \frac{1}{N} \sum_{i=1}^N \text{KL}(\mathbb{P}_i \| \mathbb{Q})}{\ln(N)}, \right. \\ \left. \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)}, \right. \\ \left. 1_{\delta=0} \times \left( 1 - \frac{1 + \frac{n\epsilon}{N^2} \sum_{i,j} \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}}{\ln(N)} \right) \right\}. $$

Furthermore, when $\mathbb{P}_1 = \mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N = \mathbb{P}_N^{\otimes n}$ are product distributions,

$$ \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \geq \max \left\{ \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), \right. \\ \left. 1_{\delta=0} \times \left( 1 - \frac{1 + \frac{n\epsilon}{N^2} \sum_{i,j} \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}}{\ln(N)} \right) \right\}. $$
For i.i.d. observations ($\mathbb{P}_i = \mathbb{P}_i^{\otimes n}$), it follows by convexity that for any $(\epsilon, \delta)$-DP mechanism $\mathfrak{M}$ and test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, 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( e^{-\epsilon n \text{TV}(\mathbb{P}_1, \mathbb{P}_2)} - 2e^{-\epsilon} \delta n \text{TV}(\mathbb{P}_1, \mathbb{P}_2) \right). $$

This is to be compared to the state of the art lower bound of Acharya et al. (2021e, Theorem 1):

$$ \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( 0.9e^{-10\epsilon n \text{TV}(\mathbb{P}_1, \mathbb{P}_2)} - 10\delta n \text{TV}(\mathbb{P}_1, \mathbb{P}_2) \right). $$

Theorem 1 gives tighter results with better constants, notably thanks to a different proof technique avoiding some convexity and concentration inequalities, but also because Acharya et al. (2021e) did not optimize the constants. Indeed, qualitative results and rates of convergence do usually not depend on them.

We also prove an equivalent for so-called $\rho$-zero concentrated differential privacy (or in short $\rho$-zCDP), which is, to the best of our knowledge, the first successful attempt at doing so.

**Theorem 2** (Le Cam for $\rho$-zCDP). If a randomized mechanism $\mathfrak{M}$ satisfies $\rho$-zCDP, then for any test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$ and any probability distributions $\mathbb{P}_1$ and $\mathbb{P}_2$ on $\mathcal{X}^n$,

$$ \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} \max \left\{ 1 - \text{TV}(\mathbb{P}_1, \mathbb{P}_2), \right. \\ \left. 1 - n\sqrt{\rho/2\text{TV}(\mathbb{P}_1, \mathbb{P}_2)} \right\}. $$

Furthermore, when $\mathbb{P}_1 = \mathbb{P}_1^{\otimes n}$ and $\mathbb{P}_2 = \mathbb{P}_2^{\otimes n}$ are product distributions,

$$ \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 proof of this result can be found in Appendix C. As above, any two distributions can no longer be distinguished in the regime $\rho \ll 1/n^2$. For more than two hypotheses and $(\epsilon, \delta)$-DP, we also get a private version of Fano's lemma.

**Theorem 3** (Multiple Distributional Tests for $(\epsilon, \delta)$-DP). If a randomized mechanism $\mathfrak{M}$ satisfies $(\epsilon, \delta)$-DP, then for any test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$, any family of probability distributions $(\mathbb{P}_i)_{i \in \{1, \dots, N\}}$ on $\mathcal{X}^n$ and 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 \max \left\{ 1 - \frac{1 + \frac{1}{N} \sum_{i=1}^N \text{KL}(\mathbb{P}_i \| \mathbb{Q})}{\ln(N)}, \right. \\ \left. \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)}, \right. \\ \left. 1_{\delta=0} \times \left( 1 - \frac{1 + \frac{n\epsilon}{N^2} \sum_{i,j} \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}}{\ln(N)} \right) \right\}. $$

Furthermore, when $\mathbb{P}_1 = \mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N = \mathbb{P}_N^{\otimes n}$ are product distributions,

$$ \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \geq \max \left\{ \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), \right. \\ \left. 1_{\delta=0} \times \left( 1 - \frac{1 + \frac{n\epsilon}{N^2} \sum_{i,j} \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}}{\ln(N)} \right) \right\}. $$
The proof is given in Appendix C. When dealing with product distributions, the quantity

$$D := \frac{n}{N^2} \sum_{i,j} \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}$$

can roughly be seen as an averaged hamming distance between pairs of marginals. An implication of Theorem 3 is then that

$$\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_{\delta=0} \times \left(1 - \frac{1 + \epsilon D}{\ln(N)}\right).$$

As the bound of Acharya et al. (2021e, Theorem 2)

$$\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_{\delta=0} \times 0.9 \times \min \left\{ 1, \frac{N}{e^{10\epsilon D}} \right\}, \quad (13)$$

the lower bound is $\Omega(1)$ in the regime $D = o(\ln(N)/\epsilon)$. In particular, both inequalities are expected to yield similar qualitative results for a broad range of applications. However, the quantitative consequences of Theorem 3 can again be orders of magnitude better. Another improvement of our result is that, contrary to previous work, our bound allows to handle asymmetric hypotheses. Indeed, prior work is based on a uniform upper-bound on the family $(\text{TV}(\mathbb{P}_i, \mathbb{P}_j))_{i,j}$ whereas our work uses only their mean value. As an illustration, if a statistician was to discriminate between a set of $N$ distributions with for instance $N-1$ distributions close to each other in total variation distance and one outlier far from all the others, the results of Acharya et al. (2021e) only tell that the problem will be at least as hard as discriminating distributions that are far from one another (which is easy). In contrast, our Theorem 3 shows that the true testing difficulty lies in discriminating the distributions that are similar (the outlier vanishes), thus resulting in lower bounds that are less over-optimistic.

Similarly, we obtain results for multiple hypotheses under $\rho$-zCDP.

**Theorem 4 (Multiple Distributional Tests for $\rho$-zCDP).** If a randomized mechanism $\mathfrak{M}$ satisfies $\rho$-zCDP, then for any test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$, any family of probability distributions $(\mathbb{P}_i)_{i \in \{1, \dots, N\}}$ on $\mathcal{X}^n$ and 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 \max \left\{ 1 - \frac{1 + \frac{1}{N} \sum_{i=1}^{N} \text{KL}(\mathbb{P}_i \| \mathbb{Q})}{\ln(N)}, \right. \\ \left. 1 - \frac{1 + \frac{n^2 \rho}{N^2} \sum_{i,j} \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}}{\ln(N)} \right\}.$$

Furthermore, when $\mathbb{P}_1 = \mathbb{P}_1^{\otimes n}$, ..., $\mathbb{P}_N = \mathbb{P}_N^{\otimes n}$ are product distributions,

$$\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{n^2 \rho}{N^2} \sum_{i,j} \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)} + \left(\frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}\right)^2}{\ln(N)}.$$

The proof is to be found in Appendix C. This result recovers a recently published result in Kamath et al. (2022), with the advantage again of better handling asymmetrical hypotheses (i.e. with possible outliers). Another interesting observation is that our framework unifies the proofs of lower bounds under a general technique based on multiple marginals coupling and similarity functions.

A more detailed discussion about the different privacy regimes is less direct compared to Le Cam's method and is postponed to Appendix D, where we discuss three specific examples, recovering known facts and uncovering novel results.

**Bernoulli model.** We first recover that the classical minimax rate $\Theta(1/n)$ for the squared error on the estimation of the parameter of a Bernoulli distribution becomes $\Theta(\max\left\{\frac{1}{n}, \frac{1}{(n\epsilon)^2}\right\})$ under $\epsilon$-differential privacy. Furthermore, we exhibit a new rate in the case of $\rho$-zero concentrated differential privacy : $\Theta(\max\left\{\frac{1}{n}, \frac{1}{n^2\rho}\right\})$.
The proof is given in Appendix C. When dealing with product distributions, the quantity

$$D := \frac{n}{N^2} \sum_{i,j} \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}$$

can roughly be seen as an averaged hamming distance between pairs of marginals. An implication of Theorem 3 is then that

$$\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_{\delta=0} \times \left(1 - \frac{1 + \epsilon D}{\ln(N)}\right).$$

As the bound of Acharya et al. (2021e, Theorem 2)

$$\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_{\delta=0} \times 0.9 \times \min \left\{ 1, \frac{N}{e^{10\epsilon D}} \right\}, \quad (13)$$

the lower bound is $\Omega(1)$ in the regime $D = o(\ln(N)/\epsilon)$. In particular, both inequalities are expected to yield similar qualitative results for a broad range of applications. However, the quantitative consequences of Theorem 3 can again be orders of magnitude better. Another improvement of our result is that, contrary to previous work, our bound allows to handle asymmetric hypotheses. Indeed, prior work is based on a uniform upper-bound on the family $(\text{TV}(\mathbb{P}_i, \mathbb{P}_j))_{i,j}$ whereas our work uses only their mean value. As an illustration, if a statistician was to discriminate between a set of $N$ distributions with for instance $N-1$ distributions close to each other in total variation distance and one outlier far from all the others, the results of Acharya et al. (2021e) only tell that the problem will be at least as hard as discriminating distributions that are far from one another (which is easy). In contrast, our Theorem 3 shows that the true testing difficulty lies in discriminating the distributions that are similar (the outlier vanishes), thus resulting in lower bounds that are less over-optimistic.

Similarly, we obtain results for multiple hypotheses under $\rho$-zCDP.

**Theorem 4 (Multiple Distributional Tests for $\rho$-zCDP).** If a randomized mechanism $\mathfrak{M}$ satisfies $\rho$-zCDP, then for any test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$, any family of probability distributions $(\mathbb{P}_i)_{i \in \{1, \dots, N\}}$ on $\mathcal{X}^n$ and 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 \max \left\{ 1 - \frac{1 + \frac{1}{N} \sum_{i=1}^{N} \text{KL}(\mathbb{P}_i \| \mathbb{Q})}{\ln(N)}, \right. \\ \left. 1 - \frac{1 + \frac{n^2 \rho}{N^2} \sum_{i,j} \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}}{\ln(N)} \right\}.$$

Furthermore, when $\mathbb{P}_1 = \mathbb{P}_1^{\otimes n}$, ..., $\mathbb{P}_N = \mathbb{P}_N^{\otimes n}$ are product distributions,

$$\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{n^2 \rho}{N^2} \sum_{i,j} \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)} + \left(\frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}\right)^2}{\ln(N)}.$$

The proof is to be found in Appendix C. This result recovers a recently published result in Kamath et al. (2022), with the advantage again of better handling asymmetrical hypotheses (i.e. with possible outliers). Another interesting observation is that our framework unifies the proofs of lower bounds under a general technique based on multiple marginals coupling and similarity functions.

A more detailed discussion about the different privacy regimes is less direct compared to Le Cam's method and is postponed to Appendix D, where we discuss three specific examples, recovering known facts and uncovering novel results.

**Bernoulli model.** We first recover that the classical minimax rate $\Theta(1/n)$ for the squared error on the estimation of the parameter of a Bernoulli distribution becomes $\Theta(\max\left\{\frac{1}{n}, \frac{1}{(n\epsilon)^2}\right\})$ under $\epsilon$-differential privacy. Furthermore, we exhibit a new rate in the case of $\rho$-zero concentrated differential privacy : $\Theta(\max\left\{\frac{1}{n}, \frac{1}{n^2\rho}\right\})$.
**Gaussian Model.** We allow each piece of data to have dimensionality $d$ (the dimension of $\mathcal{X}$). We again recover that the minimax risk $\Theta(\frac{\sigma^2 d}{n})$ (see Rigollet & Hütter (2015, Corollary 5.13)) becomes $\Omega(\max\{\frac{\sigma^2 d}{n}, \frac{\sigma^2 d^2}{(n\epsilon)^2}\})$ under $\epsilon$-DP, and we prove that it becomes $\Omega(\max\{\frac{\sigma^2 d}{n}, \frac{\sigma^2 d}{n^2\rho}\})$ under $\rho$-zCDP.

**Uniform model.** This example allows us to exhibit a new behavior under privacy. Indeed, we show that the usual minimax risk $\Theta(\frac{1}{n^2})$ becomes $\Omega(\max(\frac{1}{n^2}, \frac{1}{(n\epsilon)^2}))$ under $\epsilon$-DP and $\Omega(\max(\frac{1}{n^2}, \frac{1}{n^2\rho}))$ under $\rho$-zCDP, proving a systematic degradation of utility due to privacy that in particular does not depend on a disjunction on the rates at which the privacy-tuning parameters decrease.

Finally, in Section 4, we study the private parametric estimation of distributions that are log-concave with respect to the parameter. In particular, under some mild hypotheses, we exhibit some lower bounds on the minimax risk of estimation. We then show, based on existing upper bounds, that under mild hypotheses, Differentially Private Stochastic Gradient Langevin Dynamics (DP-SGLD, see Ryffel et al. (2022)), a private optimization solver, is near-minimax optimal when used to perform private maximum likelihood estimation in this class of distributions. Here "near-minimax optimal" means that the ratio between the risk of private estimation and the private minimax risk is upper-bounded by a quantity that only depends on the regularity of the log-likelihood, such as the eigenvalues of its Hessian. In particular, it is independent of the sample size $n$ or of the constants that tune the privacy.

## 2 From Testing to a Transport Problem

This section presents our main theorem, which states that finding lower bounds on (11) can be done by solving a transport problem (Santambrogio, 2015; Peyré et al., 2019). In some sense, this view is close to the coupling of Acharya et al. (2021e) which considers couplings between pairs of marginals and controls the variations of the hamming distance compared to its expected value with Markov's inequality. However, the high level view that our result allows to obtain numerically sharper results because it allows to skip approximations such as those involving Jensen or Markov inequalities and more importantly, it allows handling divergence-based definitions of privacy which do not fit in the framework of Acharya et al. (2021e). Furthermore, a key difference is that the theory of Acharya et al. (2021e) only requires to build couplings between pairs of marginals, whereas our theory requires building couplings between all the marginals at the same time. This is both a drawback because it requires to use more complex coupling constructions, and an advantage because it allows to give results that are easier to use when there are more than two hypotheses.

Our analysis is based on the notion of similarity functions.

**Definition 1.** Given a condition $C$, we say that a similarity function $s_C : (\mathcal{X}^n)^N \to \mathbb{R}$ is admissible for $C$ if for any mechanism $\mathfrak{M}: \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ that satisfies $C$, for any test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$, and for any $\mathbf{X}_1, \dots, \mathbf{X}_N \in \mathcal{X}^n$, the following inequality holds:

$$ \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}}(\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq s_C(\mathbf{X}_1, \dots, \mathbf{X}_N). $$

**Theorem 5.** If a randomized mechanism $\mathfrak{M}: \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ satisfies the privacy condition $C$, for any $N \geq 2$, if $s_C : (\mathcal{X}^n)^N \to \mathbb{R}$ is an admissible similarity function for $C$, for any distributions $\mathbb{P}_1, \dots, \mathbb{P}_N$ over $\mathcal{X}^n$ we have

$$ \begin{aligned} & \inf_{\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}} \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \\ & \geq \sup_{Q \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)} \int_{(\mathcal{X}^n)^N} s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) dQ(\mathbf{X}_1, \dots, \mathbf{X}_N). \end{aligned} \quad (14) $$
**Gaussian Model.** We allow each piece of data to have dimensionality $d$ (the dimension of $\mathcal{X}$). We again recover that the minimax risk $\Theta(\frac{\sigma^2 d}{n})$ (see Rigollet & Hütter (2015, Corollary 5.13)) becomes $\Omega(\max\{\frac{\sigma^2 d}{n}, \frac{\sigma^2 d^2}{(n\epsilon)^2}\})$ under $\epsilon$-DP, and we prove that it becomes $\Omega(\max\{\frac{\sigma^2 d}{n}, \frac{\sigma^2 d}{n^2\rho}\})$ under $\rho$-zCDP.

**Uniform model.** This example allows us to exhibit a new behavior under privacy. Indeed, we show that the usual minimax risk $\Theta(\frac{1}{n^2})$ becomes $\Omega(\max(\frac{1}{n^2}, \frac{1}{(n\epsilon)^2}))$ under $\epsilon$-DP and $\Omega(\max(\frac{1}{n^2}, \frac{1}{n^2\rho}))$ under $\rho$-zCDP, proving a systematic degradation of utility due to privacy that in particular does not depend on a disjunction on the rates at which the privacy-tuning parameters decrease.

Finally, in Section 4, we study the private parametric estimation of distributions that are log-concave with respect to the parameter. In particular, under some mild hypotheses, we exhibit some lower bounds on the minimax risk of estimation. We then show, based on existing upper bounds, that under mild hypotheses, Differentially Private Stochastic Gradient Langevin Dynamics (DP-SGLD, see Ryffel et al. (2022)), a private optimization solver, is near-minimax optimal when used to perform private maximum likelihood estimation in this class of distributions. Here "near-minimax optimal" means that the ratio between the risk of private estimation and the private minimax risk is upper-bounded by a quantity that only depends on the regularity of the log-likelihood, such as the eigenvalues of its Hessian. In particular, it is independent of the sample size $n$ or of the constants that tune the privacy.

## 2 From Testing to a Transport Problem

This section presents our main theorem, which states that finding lower bounds on (11) can be done by solving a transport problem (Santambrogio, 2016; Peyré & Cuturi, 2019). In some sense, this view is close to the coupling of Acharya et al. (2021e) which considers couplings between pairs of marginals and controls the variations of the hamming distance compared to its expected value with Markov's inequality. However, the high level view that our result allows to obtain numerically sharper results because it allows to skip approximations such as those involving Jensen or Markov inequalities and more importantly, it allows handling divergence-based definitions of privacy which do not fit in the framework of Acharya et al. (2021e). Furthermore, a key difference is that the theory of Acharya et al. (2021e) only requires to build couplings between pairs of marginals, whereas our theory requires building couplings between all the marginals at the same time. This is both a drawback because it requires to use more complex coupling constructions, and an advantage because it allows to give results that are easier to use when there are more than two hypotheses.

Our analysis is based on the notion of similarity functions.

**Definition 1.** Given a condition $C$, we say that a similarity function $s_C : (\mathcal{X}^n)^N \to \mathbb{R}$ is admissible for $C$ if for any mechanism $\mathfrak{M} : \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ that satisfies $C$, for any test function $\Psi : \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$, and for any $\mathbf{X}_1, \dots, \mathbf{X}_N \in \mathcal{X}^n$, the following inequality holds:

$$ \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}}(\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) \geq s_C(\mathbf{X}_1, \dots, \mathbf{X}_N). $$

**Theorem 5.** If a randomized mechanism $\mathfrak{M} : \mathcal{X}^n \to \text{codom}(\mathfrak{M})$ satisfies the privacy condition $C$, for any $N \geq 2$, if $s_C : (\mathcal{X}^n)^N \to \mathbb{R}$ is an admissible similarity function for $C$, for any distributions $\mathbb{P}_1, \dots, \mathbb{P}_N$ over $\mathcal{X}^n$ we have

$$ \begin{aligned} & \inf_{\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}} \max_{i \in \{1, \dots, N\}} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \\ & \geq \sup_{Q \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)} \int_{(\mathcal{X}^n)^N} s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) dQ(\mathbf{X}_1, \dots, \mathbf{X}_N). \end{aligned} \quad (14) $$
Proof. Given a test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$ and a coupling $\mathbb{Q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$,

$$ 
\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}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \\
&= \int_{(\mathcal{X}^n)^N} \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) d\mathbb{Q}(\mathbf{X}_1, \dots, \mathbf{X}_N) \\
&\geq \int_{(\mathcal{X}^n)^N} s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) d\mathbb{Q}(\mathbf{X}_1, \dots, \mathbf{X}_N) .
\end{aligned}
$$

□

In particular, under $(\epsilon, \delta)$-DP, similarity functions are built using a technique that we call *anchoring* which will be introduced in Appendix B.1, where the proof of the following theorem is given.

**Theorem 6 (Admissible similarity functions for $(\epsilon, \delta)$-DP).** When $C$ is $(\epsilon, \delta)$-differential privacy, the following approaches yield admissible similarity functions.

* **Global anchoring.** Consider any anchor function $\Lambda: (\mathcal{X}^n)^N \to \mathcal{X}^n$, and define the admissible similarity function as

$$ s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) := \frac{N-1}{N} e^{-\epsilon \max_i (d_{\text{ham}}(\mathbf{X}_i, \Lambda(\mathbf{X}_1, \dots, \mathbf{X}_N)))} - e^{-\epsilon} \delta \max_i (d_{\text{ham}}(\mathbf{X}_i, \Lambda(\mathbf{X}_1, \dots, \mathbf{X}_N))) . $$

* **Projection anchoring.** In particular, for any $j \in \{1, \dots, N\}$, consider the projection anchor $\Lambda_j(\mathbf{X}_1, \dots, \mathbf{X}_N) := \mathbf{X}_j$, and define the corresponding admissible similarity function

$$ s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) := \frac{N-1}{N} e^{-\epsilon \max_i (d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j))} - e^{-\epsilon} \delta \max_i (d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)) $$

* $(\epsilon, \delta)$-DP Le Cam matching. When $N=2$, there is a global anchor function yielding the admissible similarity function

$$ s_C(\mathbf{X}_1, \mathbf{X}_2) := \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 . $$

* **Pairwise anchoring.** An admissible similarity function is

$$ s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) := \frac{1}{2N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} 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 . $$

* $(\epsilon, 0)$-DP Fano matching. When $\delta=0$, an admissible similarity function is

$$ s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) := 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)} . $$

When working under $\rho$-zCDP, admissible similarity functions are built using classical information theoretic inequalities directly. It can be seen as a form of anchoring on the distributions rather than on the observed random variables (i.e. all the distributions are compared to a common distribution directly that is not necessarily a pushforward by $\mathfrak{M}$). The following result is proved in Appendix B.2.

**Theorem 7 (Admissible similarity functions for $\rho$-zCDP).** When $C$ is the $\rho$-zero concentrated-differential privacy, the two following quantities are admissible similarity functions:
Proof. Given a test function $\Psi: \text{codom}(\mathfrak{M}) \to \{1, \dots, N\}$ and a coupling $\mathbb{Q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$,

$$ \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 \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathbf{X} \sim \mathbb{P}_i, \mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X})) \neq i) \\ &= \int_{(\mathcal{X}^n)^N} \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_{\mathfrak{M}} (\Psi(\mathfrak{M}(\mathbf{X}_i)) \neq i) d\mathbb{Q}(\mathbf{X}_1, \dots, \mathbf{X}_N) \\ &\ge \int_{(\mathcal{X}^n)^N} s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) d\mathbb{Q}(\mathbf{X}_1, \dots, \mathbf{X}_N) . \end{aligned} $$

□

In particular, under $(\epsilon, \delta)$-DP, similarity functions are built using a technique that we call *anchoring* which will be introduced in Appendix B.1, where the proof of the following theorem is given.

**Theorem 6** (Admissible similarity functions for $(\epsilon, \delta)$-DP). *When $C$ is $(\epsilon, \delta)$-differential privacy, the following approaches yield admissible similarity functions.*

* **Global anchoring.** Consider any anchor function $\Lambda: (\mathcal{X}^n)^N \to \mathcal{X}^n$, and define the admissible similarity function as

$$ s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) := \frac{N-1}{N} e^{-\epsilon \max_i (d_{\text{ham}}(\mathbf{X}_i, \Lambda(\mathbf{X}_1, \dots, \mathbf{X}_N)))} - e^{-\epsilon} \delta \max_i (d_{\text{ham}}(\mathbf{X}_i, \Lambda(\mathbf{X}_1, \dots, \mathbf{X}_N))) . $$

* **Projection anchoring.** In particular, for any $j \in \{1, \dots, N\}$, consider the projection anchor $\Lambda_j(\mathbf{X}_1, \dots, \mathbf{X}_N) := \mathbf{X}_j$, and define the corresponding admissible similarity function

$$ s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) := \frac{N-1}{N} e^{-\epsilon \max_i (d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j))} - e^{-\epsilon} \delta \max_i (d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)) $$

* $(\epsilon, \delta)$-DP Le Cam matching. When $N=2$, there is a global anchor function yielding the admissible similarity function

$$ s_C(\mathbf{X}_1, \mathbf{X}_2) := \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 . $$

* **Pairwise anchoring.** An admissible similarity function is

$$ s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) := \frac{1}{2N^2} \sum_{i=1}^{N} \sum_{j=1}^{N} 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 . $$

* $(\epsilon, 0)$-DP Fano matching. When $\delta=0$, an admissible similarity function is

$$ s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) := 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)} . $$

When working under $\rho$-zCDP, admissible similarity functions are built using classical information theoretic inequalities directly. It can be seen as a form of anchoring on the distributions rather than on the observed random variables (i.e. all the distributions are compared to a common distribution directly that is not necessarily a pushforward by $\mathfrak{M}$). The following result is proved in Appendix B.2.

**Theorem 7** (Admissible similarity functions for $\rho$-zCDP). *When $C$ is the $\rho$-zero concentrated-differential privacy, the two following quantities are admissible similarity functions:*
• ρ-zCDP Fano matching

$$s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) := 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)}.$$

• ρ-zCDP Le Cam matching When $N = 2$

$$s_C(\mathbf{X}_1, \mathbf{X}_2) := \frac{1}{2} \left( 1 - \sqrt{\rho/2} d_{\text{ham}}(\mathbf{X}_1, \mathbf{X}_2) \right).$$

Note that similarity functions can also be easily built for the more general notion of $(\xi, \rho)$- concentrated differential privacy by swapping the group privacy property for its correct variant (see Bun & Steinke (2016)). We do not include the results about $(\xi, \rho)$-concentrated differential in this article because our objective is more to illustrate the versatility of our framework rather than to build a complete catalogue.

## 3 Lower Bound via Couplings

The transport problem (12) can be studied either theoretically (Santambrogio, 2015) or numerically (Peyré et al., 2019) in order to give the best lower bounds that our technique permits. However, identifying an optimal coupling is out of the scope of this article. We here provide coupling constructions that are sufficient to exhibit useful lower bounds.

Most of the similarity functions expressed in Theorem 5 yield lower bounds that are based on or further lower-bounded by expressions involving the quantities

$$\mathbb{E}_{(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \mathbb{Q}} (g(d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)))$$

for a coupling $\mathbb{Q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$ where $g$ is a fixed non-increasing function. Hence, finding reasonably good lower bounds can be achieved by finding a coupling that *minimizes* the expected pairwise Hamming distance between the marginals.

As a proxy, we first aim at maximizing the probabilities of pairwise equalities between all the marginals simultaneously. We then control the Hamming distance by observing that when $\mathbf{X}_i = \mathbf{X}_j$, $d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j) = 0$ and otherwise, $d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j) \le n$. It is known (Lindvall, 2002) that if $\mathbb{Q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$, the disagreement probabilities (i.e. the probability that two marginal random variables are not equal) between the marginals satisfy

$$\forall i, j, \quad \text{TV}(\mathbb{P}_i, \mathbb{P}_j) \le \mathbb{P}_{(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \mathbb{Q}}(\mathbf{X}_i \ne \mathbf{X}_j). \qquad (15)$$

A natural question is whether this lower bound is achievable by a coupling simultaneously for all pairs of marginals. When there are only two marginals (i.e. $N = 2$), a classical construction (see Lindvall (2002)) answers this question positively:

**Fact 3 (Maximal coupling).** Let $\mathbb{P}_1$ and $\mathbb{P}_2$ be two probability distributions on $\mathcal{X}^n$ that share the same $\sigma$-algebra. There exists a coupling $\pi^\infty(\mathbb{P}_1, \mathbb{P}_2) \in \Pi(\mathbb{P}_1, \mathbb{P}_2)$ (which is a distribution on $(\mathcal{X}^n)^2$), called a maximal coupling, such that

$$\begin{align*}
\mathbb{P}_{(X_1, X_2) \sim \pi^\infty(\mathbb{P}_1, \mathbb{P}_2)}(X_1 \neq X_2) &= \text{TV}(\mathbb{P}_1, \mathbb{P}_2), \\
\forall S \text{ measurable, } \mathbb{P}_{(X_1, X_2) \sim \pi^\infty(\mathbb{P}_1, \mathbb{P}_2)}(X_1 \in S) &= \mathbb{P}_1(X_1 \in S), \\
\forall S \text{ measurable, } \mathbb{P}_{(X_1, X_2) \sim \pi^\infty(\mathbb{P}_1, \mathbb{P}_2)}(X_2 \in S) &= \mathbb{P}_2(X_2 \in S).
\end{align*}$$

This construction unfortunately does not generically scale to more than two marginals, even though on simple examples, couplings can be built that still match the lower bound (15) for any pair of marginals.

**Example 1 (Bernoulli optimal coupling).** Given $\mathbb{P}_i = \mathcal{B}(p_i)$, $1 \le i \le N$ a family of Bernoulli distributions and $U \sim \mathcal{U}([0, 1])$ a uniformly distributed variable on $[0, 1]$, the random vector $(X_1, \dots, X_N)$ defined by $X_i := 1_{[0, p_i)}(U)$ is distributed according to a coupling $\mathbb{Q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$, and for every $i, j$

$$\mathbb{P}(X_i \neq X_j) = |p_i - p_j| = \text{TV}(\mathcal{B}(p_i), \mathcal{B}(p_j)).$$
• ρ-zCDP Fano matching

$$s_C(\mathbf{X}_1, \dots, \mathbf{X}_N) := 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)}.$$

• ρ-zCDP Le Cam matching When $N = 2$

$$s_C(\mathbf{X}_1, \mathbf{X}_2) := \frac{1}{2} \left( 1 - \sqrt{\rho/2} d_{\text{ham}}(\mathbf{X}_1, \mathbf{X}_2) \right).$$

Note that similarity functions can also be easily built for the more general notion of $(\xi, \rho)$- concentrated differential privacy by swapping the group privacy property for its correct variant (see Bun & Steinke (2016)). We do not include the results about $(\xi, \rho)$-concentrated differential in this article because our objective is more to illustrate the versatility of our framework rather than to build a complete catalogue.

## 3 Lower Bound via Couplings

The transport problem (12) can be studied either theoretically (Santambrogio, 2016) or numerically (Peyré & Cuturi, 2019) in order to give the best lower bounds that our technique permits. However, identifying an optimal coupling is out of the scope of this article. We here provide coupling constructions that are sufficient to exhibit useful lower bounds.

Most of the similarity functions expressed in Theorem 5 yield lower bounds that are based on or further lower-bounded by expressions involving the quantities

$$\mathbb{E}_{(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \mathcal{Q}} (g(d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)))$$

for a coupling $\mathcal{Q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$ where $g$ is a fixed non-increasing function. Hence, finding reasonably good lower bounds can be achieved by finding a coupling that *minimizes* the expected pairwise Hamming distance between the marginals.

As a proxy, we first aim at maximizing the probabilities of pairwise equalities between all the marginals simultaneously. We then control the Hamming distance by observing that when $\mathbf{X}_i = \mathbf{X}_j$, $d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j) = 0$ and otherwise, $d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j) \le n$. It is known (Lindvall, 2003) that if $\mathcal{Q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$, the disagreement probabilities (i.e. the probability that two marginal random variables are not equal) between the marginals satisfy

$$\forall i, j, \quad \text{TV}(\mathbb{P}_i, \mathbb{P}_j) \le \mathbb{P}_{(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \mathcal{Q}}(\mathbf{X}_i \ne \mathbf{X}_j). \qquad (15)$$

A natural question is whether this lower bound is achievable by a coupling simultaneously for all pairs of marginals. When there are only two marginals (i.e. $N = 2$), a classical construction (see Lindvall (2003)) answers this question positively:

**Fact 3 (Maximal coupling).** Let $\mathbb{P}_1$ and $\mathbb{P}_2$ be two probability distributions on $\mathcal{X}^n$ that share the same $\sigma$-algebra. There exists a coupling $\pi^\infty(\mathbb{P}_1, \mathbb{P}_2) \in \Pi(\mathbb{P}_1, \mathbb{P}_2)$ (which is a distribution on $(\mathcal{X}^n)^2$), called a maximal coupling, such that

$$\begin{align*}
\mathbb{P}_{(X_1, X_2) \sim \pi^\infty(\mathbb{P}_1, \mathbb{P}_2)}(X_1 \neq X_2) &= \text{TV}(\mathbb{P}_1, \mathbb{P}_2), \\
\forall S \text{ measurable, } \mathbb{P}_{(X_1, X_2) \sim \pi^\infty(\mathbb{P}_1, \mathbb{P}_2)}(X_1 \in S) &= \mathbb{P}_1(X_1 \in S), \\
\forall S \text{ measurable, } \mathbb{P}_{(X_1, X_2) \sim \pi^\infty(\mathbb{P}_1, \mathbb{P}_2)}(X_2 \in S) &= \mathbb{P}_2(X_2 \in S).
\end{align*}$$

This construction unfortunately does not generically scale to more than two marginals, even though on simple examples, couplings can be built that still match the lower bound (15) for any pair of marginals.

**Example 1 (Bernoulli optimal coupling).** Given $\mathbb{P}_i = \mathcal{B}(p_i)$, $1 \le i \le N$ a family of Bernoulli distributions and $U \sim \mathcal{U}([0, 1])$ a uniformly distributed variable on $[0, 1]$, the random vector $(X_1, \dots, X_N)$ defined by $X_i := 1_{[0, p_i]}(U)$ is distributed according to a coupling $\mathcal{Q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$, and for every $i, j$

$$\mathbb{P}(X_i \neq X_j) = |p_i - p_j| = \text{TV}(\mathcal{B}(p_i), \mathcal{B}(p_j)).$$
There are however examples for which it is provably impossible to build couplings that match the lower bound (15) for any pair of marginals.

**Example 2** (A counterexample). Let $X_1 \sim \mathcal{U}(\{-1, 0\})$, $X_2 \sim \mathcal{U}(\{0, 1\})$ and $X_3 \sim \mathcal{U}(\{1, -1\})$, and let $\mathbb{P}$ be a coupling between $X_1$, $X_2$ and $X_3$. We have that,

$$1_{X_1 \neq X_2} + 1_{X_2 \neq X_3} + 1_{X_3 \neq X_1} \geq 2$$

and as a consequence on $\mathbb{P}$,

$$\mathbb{P}(X_1 \neq X_2) + \mathbb{P}(X_2 \neq X_3) + \mathbb{P}(X_3 \neq X_1) \geq 2 \\ > \text{TV}(X_1, X_2) + \text{TV}(X_2, X_3) + \text{TV}(X_3, X_1),$$

which proves that at least one of the disagreement probabilities is strictly bigger than the corresponding total variation.

Recent constructions based on Poisson point processes allow in general, for any number of marginals $N$, to match the lower bound (15) up to a factor 2.

**Fact 4** (Near optimal coupling of multiple distributions (Angel & Spinka, 2019)). Let $\mathbb{P}_1, \dots, \mathbb{P}_N$ be $N$ distributions on the same measurable set. There exists a coupling $\mathbb{Q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$ such that

$$\forall i, j \in \{1, \dots, N\}, \quad \mathbb{P}(X_1, \dots, X_N) \sim \mathbb{Q} (X_i \neq X_j) \leq \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}.$$

In the rest of this article, the notation $\pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N)$ refers to a coupling that satisfies this condition. When there are only two distributions, it refers to the construction of Fact 3. This factor 2 is not a problem for minimax theory, since it is a common practice to overlook the constants by looking at rates of convergence. However, for some more precise applications, working on more specific couplings may improve our results. With either coupling constructions, the lower bounds of Theorem 5 can be controlled with the following straightforward lemma:

**Lemma 1.** Let $\mathbb{P}_1, \dots, \mathbb{P}_N$ be $N$ distributions on $\mathcal{X}^n$ and $\mathbb{Q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$. Consider $1 \leq i, j \leq N$ and denote $\Delta_{i,j} := \mathbb{P}(\mathbf{x}_1, \dots, \mathbf{x}_N) \sim \mathbb{Q} (\mathbf{x}_i \neq \mathbf{x}_j)$. We have

$$\begin{align*}
\mathbb{E}_{(\mathbf{x}_1, \dots, \mathbf{x}_N) \sim \mathbb{Q}} (d_{\text{ham}}(\mathbf{x}_i, \mathbf{x}_j)) &\leq n \Delta_{i,j} \\
\mathbb{E}_{(\mathbf{x}_1, \dots, \mathbf{x}_N) \sim \mathbb{Q}} (d_{\text{ham}}(\mathbf{x}_i, \mathbf{x}_j)^2) &\leq n^2 \Delta_{i,j} \\
\mathbb{E}_{(\mathbf{x}_1, \dots, \mathbf{x}_N) \sim \mathbb{Q}} (e^{-\epsilon d_{\text{ham}}(\mathbf{x}_i, \mathbf{x}_j)}) &\geq 1 - (1 - e^{-n\epsilon}) \Delta_{i,j}.
\end{align*}$$

Note that $\Delta_{i,j}$ directly depends on the coupling construction, but that with any of the ones presented above, we always have $\forall i, j, \Delta_{i,j} \leq 2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)$.

When the distributions that we are trying to couple are product distributions (i.e. $\mathbb{P}_1 = \mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N = \mathbb{P}_N^{\otimes n}$), we can notice that any coupling $\mathbb{q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$ induces a coupling $\mathbb{q}^{\otimes n} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$. Under this coupling, the Hamming distances between the pairs of marginals follow binomial distributions. For the rest of this article, we define the product (near) optimal coupling

$$\pi^{\otimes}(\mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N^{\otimes n}) := \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N)^{\otimes n}.$$

Straightforward computations yield the following lemma.

**Lemma 2.** Let $\mathbb{P}_1 = \mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N = \mathbb{P}_N^{\otimes n}$ be $N$ product distributions on $\mathcal{X}^n$ and $\mathbb{q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$. Consider any $1 \leq i, j \leq N$ and denote $\delta_{i,j} := \mathbb{P}(X_1, \dots, X_N) \sim \mathbb{q} (X_i \neq X_j)$. We have:

$$\begin{align*}
\mathbb{E}_{(\mathbf{x}_1, \dots, \mathbf{x}_N) \sim \mathbb{q}^{\otimes n}} (d_{\text{ham}}(\mathbf{x}_i, \mathbf{x}_j)) &= n\delta_{i,j} \\
\mathbb{E}_{(\mathbf{x}_1, \dots, \mathbf{x}_N) \sim \mathbb{q}^{\otimes n}} (d_{\text{ham}}(\mathbf{x}_i, \mathbf{x}_j)^2) &= n^2\delta_{i,j}^2 + n\delta_{i,j}(1 - \delta_{i,j}) \leq n^2\delta_{i,j}^2 + n\delta_{i,j} \\
\mathbb{E}_{(\mathbf{x}_1, \dots, \mathbf{x}_N) \sim \mathbb{q}^{\otimes n}} (e^{-\epsilon d_{\text{ham}}(\mathbf{x}_i, \mathbf{x}_j)}) &= (1 - (1 - e^{-\epsilon})\delta_{i,j})^n \geq e^{-n\epsilon\delta_{i,j}}.
\end{align*}$$

<footnote n="2">²not to be confused with the Kronecker symbol.</footnote>
There are however examples for which it is provably impossible to build couplings that match the lower bound (15) for any pair of marginals.

**Example 2** (A counterexample). Let $X_1 \sim \mathcal{U}(\{-1, 0\})$, $X_2 \sim \mathcal{U}(\{0, 1\})$ and $X_3 \sim \mathcal{U}(\{1, -1\})$, and let $\mathbb{P}$ be a coupling between $X_1, X_2$ and $X_3$. We have that,

$$1_{X_1 \neq X_2} + 1_{X_2 \neq X_3} + 1_{X_3 \neq X_1} \geq 2$$

and as a consequence on $\mathbb{P}$,

$$\mathbb{P}(X_1 \neq X_2) + \mathbb{P}(X_2 \neq X_3) + \mathbb{P}(X_3 \neq X_1) \geq 2 \\ > \text{TV}(X_1, X_2) + \text{TV}(X_2, X_3) + \text{TV}(X_3, X_1),$$

which proves that at least one of the disagreement probabilities is strictly bigger than the corresponding total variation.

Recent constructions based on Poisson point processes allow in general, for any number of marginals $N$, to match the lower bound (15) up to a factor 2.

**Fact 4** (Near optimal coupling of multiple distributions (Angel & Spinka, 2021)). Let $\mathbb{P}_1, \dots, \mathbb{P}_N$ be $N$ distributions on the same measurable set. There exists a coupling $\mathbb{Q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$ such that

$$\forall i, j \in \{1, \dots, N\}, \quad \mathbb{P}_{(X_1, \dots, X_N) \sim \mathbb{Q}}(X_i \neq X_j) \leq \frac{2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)}{1 + \text{TV}(\mathbb{P}_i, \mathbb{P}_j)}.$$

We give a small note about this coupling in Appendix E that presents a simplified view on its construction.

In the rest of this article, the notation $\pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N)$ refers to a coupling that satisfies this condition. When there are only two distributions, it refers to the construction of Fact 3. This factor 2 is not a problem for minimax theory, since it is a common practice to overlook the constants by looking at rates of convergence. However, for some more precise applications, working on more specific couplings may improve our results. With either coupling constructions, the lower bounds of Theorem 5 can be controlled with the following straightforward lemma:

**Lemma 1.** Let $\mathbb{P}_1, \dots, \mathbb{P}_N$ be $N$ distributions on $\mathcal{X}^n$ and $\mathbb{Q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$. Consider $1 \leq i, j \leq N$ and denote $\Delta_{i,j} := \mathbb{P}_{(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \mathbb{Q}}(\mathbf{X}_i \neq \mathbf{X}_j)$. We have

$$\begin{align*}
\mathbb{E}_{(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \mathbb{Q}} (d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)) &\leq n \Delta_{i,j} \\
\mathbb{E}_{(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \mathbb{Q}} (d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)^2) &\leq n^2 \Delta_{i,j} \\
\mathbb{E}_{(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \mathbb{Q}} (e^{-\epsilon d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)}) &\geq 1 - (1 - e^{-n\epsilon}) \Delta_{i,j}.
\end{align*}$$

Note that $\Delta_{i,j}$ directly depends on the coupling construction, but that with any of the ones presented above, we always have $\forall i, j, \Delta_{i,j} \leq 2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)$.

When the distributions that we are trying to couple are product distributions (i.e. $\mathbb{P}_1 = \mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N = \mathbb{P}_N^{\otimes n}$), we can notice that any coupling $\mathbb{q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$ induces a coupling $\mathbb{q}^{\otimes n} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$. Under this coupling, the Hamming distances between the pairs of marginals follow binomial distributions. For the rest of this article, we define the product (near) optimal coupling

$$\pi^{\otimes}(\mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N^{\otimes n}) := \pi^{\infty}(\mathbb{P}_1, \dots, \mathbb{P}_N)^{\otimes n}.$$

Straightforward computations yield the following lemma.

**Lemma 2.** Let $\mathbb{P}_1 = \mathbb{P}_1^{\otimes n}, \dots, \mathbb{P}_N = \mathbb{P}_N^{\otimes n}$ be $N$ product distributions on $\mathcal{X}^n$ and $\mathbb{q} \in \Pi(\mathbb{P}_1, \dots, \mathbb{P}_N)$. Consider any $1 \leq i, j \leq N$ and denote $\delta_{i,j} := \mathbb{P}_{(X_1, \dots, X_N) \sim \mathbb{q}}(X_i \neq X_j)$. We have:

$$\begin{align*}
\mathbb{E}_{(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \mathbb{q}^{\otimes n}} (d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)) &= n\delta_{i,j} \\
\mathbb{E}_{(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \mathbb{q}^{\otimes n}} (d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)^2) &= n^2\delta_{i,j}^2 + n\delta_{i,j}(1 - \delta_{i,j}) \leq n^2\delta_{i,j}^2 + n\delta_{i,j} \\
\mathbb{E}_{(\mathbf{X}_1, \dots, \mathbf{X}_N) \sim \mathbb{q}^{\otimes n}} (e^{-\epsilon d_{\text{ham}}(\mathbf{X}_i, \mathbf{X}_j)}) &= (1 - (1 - e^{-\epsilon})\delta_{i,j})^n \geq e^{-n\epsilon\delta_{i,j}}.
\end{align*}$$

<footnote n="2">²not to be confused with the Kronecker symbol.</footnote>
Note that $\delta_{i,j}$ directly depends on the coupling construction, but that with any of the ones presented above (applied to $\mathbb{P}_1, \dots, \mathbb{P}_N$), we always have $\forall i, j, \delta_{i,j} \le 2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)$.

**Putting the pieces together.** Each of the coupling constructions presented above has its own merits and can be used to establish the quantitative lower-bounds establishing Theorem 1, Theorem 2, Theorem 3 and Theorem 4 (see details in Appendix C) as well as the fully worked-out examples given at the end of the introduction (see details in Appendix D, including a discussion on different regimes where privacy induces an estimation overhead).

**Discussion: beyond the i.i.d. structure?** Note that the techniques presented in this article can be used in non i.i.d. setups as well, by emulating the structure of the probability space in the coupling construction. For instance, consider an $m \times m$ stochastic matrix $K$, the kernel of a Markov chain kernel $K$ on $m$ states $\{1, \dots, m\}$. The column $i$ represents the vector $P(\cdot|i)$ that gives the conditional probabilities of ending in the different states, knowing that the current state is $i$. We assume that initial distribution of the chain is uniform on the states. The objective is to build a differentially private test of $K$ based on the observation $(X_t)_{1\le t\le n+1}$, $X_t \in \{1, \dots, m\}$ of a trajectory of length $n+1$. Let us illustrate this with $m=2$: consider the two kernels $K = \begin{pmatrix} k_{1,1} & k_{1,2} \\ k_{2,1} & k_{2,2} \end{pmatrix}$ and $L = \begin{pmatrix} l_{1,1} & l_{1,2} \\ l_{2,1} & l_{2,2} \end{pmatrix}$, and their associated Markov chains $M_K$ and $M_L$. We build a Markov kernel $Q$ on the set of pairs of states of $M_K$ and $M_L$, such that for any $x_K$ state of $M_K$ and any $x_L$ state of $M_L$, $Q((\cdot, \cdot)|(x_K, x_L))$ is a coupling between $K(\cdot|x_K)$ and $L(\cdot|x_L)$. Let us take $Q((1,1)|(x_K, x_L)) = \min(k_{1,x_K}, l_{1,x_L})$, $Q((2,2)|(x_K, x_L)) = \min(k_{2,x_K}, l_{2,x_L})$, $Q((1,2)|(x_K, x_L)) = k_{1,x_K} - l_{1,x_L}$ if $k_{1,x_K} > l_{1,x_L}$ or 0 otherwise, and $Q((2,1)|(x_K, x_L)) = l_{1,x_L} - k_{1,x_K}$ if $l_{1,x_K} > k_{1,x_L}$ or 0 otherwise. We consider $M_Q$, the Markov chain that starts with the uniform distribution on the pairs of states of $M_K$ and $M_L$, and has transition kernel $Q$. We observe that the probability distribution over pairs of sequences of length $n+1$ generated by $M_Q$ is a coupling between the corresponding distributions over single sequences associated to $M_1$ and $M_2$. Furthermore, in general, the structure of the probability space is Markovian and is not a product one (meaning that the generated trajectories are not i.i.d.).

By integrating Le Cam matching similarity function (Theorem 6 and Theorem 7) against this distribution on the pairs of trajectories, we obtain the fowling lower-bounds: Any $\epsilon$-DP test that tries to discriminate $M_K$ from $M_L$ must have a type 1 or a type 2 error at least equal to $\frac{1}{2}(1 - (1 - e^{-\epsilon})\alpha)^n$, where $\alpha = \max\{|k_{1,1} - l_{1,1}|, |k_{1,1} - l_{1,2}|, |k_{2,1} - l_{1,1}|, |k_{2,1} - l_{2,1}|\}$. Similarly, any $\rho$-zCDP test that tries to discriminate $M_L$ from $M_L$ must have a type 1 or a type 2 error at least equal to $\frac{1}{2}(1 - n\alpha\sqrt{\rho/2})$.

When there are more than two Markov chains to test (say $N$), a similar coupling can be built by building a Markov chain on the $N$-tuples of states of the different Markov chains. The technicality is that one has to use Fact 4 instead of Fact 3 for coupling the transition probabilities. When there are more than two states, the construction is the same. The expressions of the total variations between the pairs of transition probabilities can however be more difficult.

# 4 Near Optimal Private Maximum Likelihood

In the different models presented in Appendix D and for many other parametric models, the statistician typically would like to consider the maximum likelihood estimator. Given $X_1, \dots, X_n$ i.i.d. random variables of distribution $\mathbb{P}_{\theta^*}$, the maximum likelihood estimator has value

$$ \hat{\theta}_{\text{ML}} \in \arg\max_{\theta \in \Theta} \left\{ l(\theta) := \frac{1}{n} \sum_{i=1}^{n} f(X_i, \theta) \right\}, \quad (16) $$

where $f$ is the log-likelihood. The parametric model with respect to a reference measure $\mu$ is thus

$$ \forall X, \quad \frac{d\mathbb{P}_{\theta}}{d\mu}(X) := e^{f(X, \theta)}, \quad \theta \in \Theta, $$

where $\frac{d\mathbb{P}_{\theta}}{d\mu}$ is the Radon-Nikodym density of $\mathbb{P}_{\theta}$ with respect to $\mu$ and $\Theta$ is often a closed, convex subset of $\mathbb{R}^d$ with nonempty interior. This setup covers, in particular, exponential families (Van der Vaart, 2000) with $f(X, \theta) = \theta^T T(X) - \ln(Z(\theta))$ associated with some statistic $T$ and normalization factor $Z(\theta)$. This section
Note that $\delta_{i,j}$ directly depends on the coupling construction, but that with any of the ones presented above (applied to $\mathbb{P}_1, \dots, \mathbb{P}_N$), we always have $\forall i, j, \delta_{i,j} \le 2\text{TV}(\mathbb{P}_i, \mathbb{P}_j)$.

**Putting the pieces together.** Each of the coupling constructions presented above has its own merits and can be used to establish the quantitative lower-bounds establishing Theorem 1, Theorem 2, Theorem 3 and Theorem 4 (see details in Appendix C) as well as the fully worked-out examples given at the end of the introduction (see details in Appendix D, including a discussion on different regimes where privacy induces an estimation overhead).

**Discussion: beyond the i.i.d. structure?** Note that the techniques presented in this article can be used in non i.i.d. setups as well, by emulating the structure of the probability space in the coupling construction. For instance, consider an $m \times m$ stochastic matrix $K$, the kernel of a Markov chain kernel $K$ on $m$ states $\{1, \dots, m\}$. The column $i$ represents the vector $P(\cdot|i)$ that gives the conditional probabilities of ending in the different states, knowing that the current state is $i$. We assume that initial distribution of the chain is uniform on the states. The objective is to build a differentially private test of $K$ based on the observation $(X_t)_{1\le t\le n+1}$, $X_t \in \{1, \dots, m\}$ of a trajectory of length $n+1$. Let us illustrate this with $m=2$: consider the two kernels $K = \begin{pmatrix} k_{1,1} & k_{1,2} \\ k_{2,1} & k_{2,2} \end{pmatrix}$ and $L = \begin{pmatrix} l_{1,1} & l_{1,2} \\ l_{2,1} & l_{2,2} \end{pmatrix}$, and their associated Markov chains $M_K$ and $M_L$. We build a Markov kernel $Q$ on the set of pairs of states of $M_K$ and $M_L$, such that for any $x_K$ state of $M_K$ and any $x_L$ state of $M_L$, $Q((\cdot, \cdot)|(x_K, x_L))$ is a coupling between $K(\cdot|x_K)$ and $L(\cdot|x_L)$. Let us take $Q((1,1)|(x_K, x_L)) = \min(k_{1,x_K}, l_{1,x_L})$, $Q((2,2)|(x_K, x_L)) = \min(k_{2,x_K}, l_{2,x_L})$, $Q((1,2)|(x_K, x_L)) = k_{1,x_K} - l_{1,x_L}$ if $k_{1,x_K} > l_{1,x_L}$ or 0 otherwise, and $Q((2,1)|(x_K, x_L)) = l_{1,x_L} - k_{1,x_K}$ if $l_{1,x_K} > k_{1,x_L}$ or 0 otherwise. We consider $M_Q$, the Markov chain that starts with the uniform distribution on the pairs of states of $M_K$ and $M_L$, and has transition kernel $Q$. We observe that the probability distribution over pairs of sequences of length $n+1$ generated by $M_Q$ is a coupling between the corresponding distributions over single sequences associated to $M_1$ and $M_2$. Furthermore, in general, the structure of the probability space is Markovian and is not a product one (meaning that the generated trajectories are not i.i.d.).

By integrating Le Cam matching similarity function (Theorem 6 and Theorem 7) against this distribution on the pairs of trajectories, we obtain the fowling lower-bounds: Any $\epsilon$-DP test that tries to discriminate $M_K$ from $M_L$ must have a type 1 or a type 2 error at least equal to $\frac{1}{2}(1 - (1 - e^{-\epsilon})\alpha)^n$, where $\alpha = \max\{|k_{1,1} - l_{1,1}|, |k_{1,1} - l_{1,2}|, |k_{2,1} - l_{1,1}|, |k_{2,1} - l_{2,1}|\}$. Similarly, any $\rho$-zCDP test that tries to discriminate $M_L$ from $M_L$ must have a type 1 or a type 2 error at least equal to $\frac{1}{2}(1 - n\alpha\sqrt{\rho/2})$.

When there are more than two Markov chains to test (say $N$), a similar coupling can be built by building a Markov chain on the $N$-tuples of states of the different Markov chains. The technicality is that one has to use Fact 4 instead of Fact 3 for coupling the transition probabilities. When there are more than two states, the construction is the same. The expressions of the total variations between the pairs of transition probabilities can however be more difficult.

# 4 Near Optimal Private Maximum Likelihood

In the different models presented in Appendix D and for many other parametric models, the statistician typically would like to consider the maximum likelihood estimator. Given $X_1, \dots, X_n$ i.i.d. random variables of distribution $\mathbb{P}_{\theta^*}$, the maximum likelihood estimator has value

$$ \hat{\theta}_{\text{ML}} \in \arg\max_{\theta \in \Theta} \left\{ l(\theta) := \frac{1}{n} \sum_{i=1}^{n} f(X_i, \theta) \right\}, \qquad (16) $$

where $f$ is the log-likelihood. The parametric model with respect to a reference measure $\mu$ is thus

$$ \forall X, \quad \frac{d\mathbb{P}_{\theta}}{d\mu}(X) := e^{f(X, \theta)}, \quad \theta \in \Theta, $$

where $\frac{d\mathbb{P}_{\theta}}{d\mu}$ is the Radon-Nikodym density of $\mathbb{P}_{\theta}$ with respect to $\mu$ and $\Theta$ is often a closed, convex subset of $\mathbb{R}^d$ with nonempty interior. This setup covers, in particular, exponential families (Van der Vaart, 1998) with $f(X, \theta) = \theta^T T(X) - \ln(Z(\theta))$ associated with some statistic $T$ and normalization factor $Z(\theta)$. This section
first presents a lower bound on the minimax risk for the private estimation in such parametric models and then studies the optimality properties of the Differentially Private Stochastic Gradient Langevin Dynamics (DP-SGLD) of Ryffel et al. (2022) for this specific task based on the existing upper bounds for this private convex optimizer.

## 4.1 On the regularity of $f$ and the estimation complexity

First, we may assume that the parametric model is not degenerate in the sense that $f$ satisfies

$$ \forall \theta \in \Theta, \quad \int \nabla_{\theta} f(X, \theta) d\mathbb{P}_{\theta}(X) = 0. \qquad (17) $$

This hypothesis is for instance satisfied in the Gaussian model presented previously. Indeed, in this case $\forall X, \nabla_{\theta} f(\theta + X, \theta) + \nabla_{\theta} f(\theta - X, \theta) = 0$ and $\forall X, \frac{d\mathbb{P}_{\theta}}{d\mu}(\theta + X) = \frac{d\mathbb{P}_{\theta}}{d\mu}(\theta - X)$. This hypothesis is more generally satisfied in the broader model of the exponential families (see Boucheron et al. (2019, Théorème 4.10)). Under such hypothesis, we have the following lemma which will allow to leverage Proposition 1:

**Lemma 3.** If $(\mathbb{P}_{\theta})_{\theta \in \Theta}$ satisfies the property (17) and if $f$ is concave and $\beta$-smooth in its second argument, then

$$ \forall \theta_1, \theta_2 \in \Theta, \text{KL}(\mathbb{P}_{\theta_1} \| \mathbb{P}_{\theta_2}) \le \frac{\beta}{2} \|\theta_2 - \theta_1\|^2. $$

Note that the family $(\mathbb{P}_{\theta})_{\theta \in \Theta}$ directly depends on $f$. In particular, for the Gaussian Model, $\beta = \frac{1}{\sigma^2}$, we recover the classical upper bound on the KL divergence between multivariate normal distributions, which is fact in this case, an equality.

*Proof.* Because of concavity in the second argument of $f$ and the fact that it is $\beta$-smooth, we have the following result:

$$ \forall \theta_1, \theta_2 \in \Theta, \forall x, \quad f(x, \theta_1) + \nabla_{\theta} f(x, \theta_1)^T (\theta_2 - \theta_1) \le f(x, \theta_2) + \frac{\beta}{2} \|\theta_1 - \theta_2\|^2. $$

As a consequence,

$$ \begin{align*} \text{KL}(\mathbb{P}_{\theta_1} \| \mathbb{P}_{\theta_2}) &= \int \ln \left( \frac{d\mathbb{P}_{\theta_1}}{d\mathbb{P}_{\theta_2}} \right) d\mathbb{P}_{\theta_1} = \int (f(X, \theta_1) - f(X, \theta_2)) d\mathbb{P}_{\theta_1}(X) \\ &\le \int \left( -\nabla_{\theta} f(X, \theta_1)^T (\theta_2 - \theta_1) + \frac{\beta}{2} \|\theta_1 - \theta_2\|^2 \right) d\mathbb{P}_{\theta_1}(X) \\ &\stackrel{(17)}{=} \int \frac{\beta}{2} \|\theta_1 - \theta_2\|^2 d\mathbb{P}_{\theta_1}(X) = \frac{\beta}{2} \|\theta_1 - \theta_2\|^2. \end{align*} $$

□

We may apply Proposition 1 with $\gamma = \beta/2$ and we obtain that

$$ \mathfrak{M}_n \left( \rho\text{-zCDP}, \left( \mathbb{P}_{\theta}^{\otimes n} \right)_{\theta \in \Theta}, \| \cdot - \cdot \|, (\cdot)^2 \right) = \Omega \left( \max \left\{ \frac{d}{n^2 \beta \rho}, \frac{d}{n \beta} \right\} \right) \qquad (18) $$

Under the hypotheses of Proposition 1: $d$ is big enough, $\rho$ is small enough and the interior of the parameter space is big enough. In particular, this gives us a lower bound to compare any private estimator to.

## 4.2 Private maximum likelihood

In general, $\hat{\theta}_{\text{ML}}$ has no closed form formula. Even when it has some, the closed form formula usually does not respect differential privacy.

The problem (16) is typically addressed via numerical optimization: instead of considering its explicit maximum, a provably converging sequence is constructed. This requires some assumptions on the log-likelihood $f$. A convenient combination of hypotheses is that $f$ is $\lambda$-strongly concave, $\beta$-smooth and $L$-Lipschitz in its
first presents a lower bound on the minimax risk for the private estimation in such parametric models and then studies the optimality properties of the Differentially Private Stochastic Gradient Langevin Dynamics (DP-SGLD) of Ryffel et al. (2022) for this specific task based on the existing upper bounds for this private convex optimizer.

## 4.1 On the regularity of $f$ and the estimation complexity

First, we may assume that the parametric model is not degenerate in the sense that $f$ satisfies

$$ \forall \theta \in \Theta, \quad \int \nabla_{\theta} f(X, \theta) d\mathbb{P}_{\theta}(X) = 0. \qquad (17) $$

This hypothesis is for instance satisfied in the Gaussian model presented previously. Indeed, in this case $\forall X, \nabla_{\theta} f(\theta + X, \theta) + \nabla_{\theta} f(\theta - X, \theta) = 0$ and $\forall X, \frac{d\mathbb{P}_{\theta}}{d\mu}(\theta + X) = \frac{d\mathbb{P}_{\theta}}{d\mu}(\theta - X)$. This hypothesis is more generally satisfied in the broader model of the exponential families (see Boucheron et al. (2019, Théorème 4.10)). Under such hypothesis, we have the following lemma which will allow to leverage Proposition 1:

**Lemma 3.** If $(\mathbb{P}_{\theta})_{\theta \in \Theta}$ satisfies the property (17) and if $f$ is concave and $\beta$-smooth in its second argument, then

$$ \forall \theta_1, \theta_2 \in \Theta, \mathrm{KL}(\mathbb{P}_{\theta_1} \| \mathbb{P}_{\theta_2}) \le \frac{\beta}{2} \|\theta_2 - \theta_1\|^2. $$

Note that the family $(\mathbb{P}_{\theta})_{\theta \in \Theta}$ directly depends on $f$. In particular, for the Gaussian Model, $\beta = \frac{1}{\sigma^2}$, we recover the classical upper bound on the KL divergence between multivariate normal distributions, which is fact in this case, an equality.

*Proof.* Because of concavity in the second argument of $f$ and the fact that it is $\beta$-smooth, we have the following result:

$$ \forall \theta_1, \theta_2 \in \Theta, \forall x, \quad f(x, \theta_1) + \nabla_{\theta} f(x, \theta_1)^T (\theta_2 - \theta_1) \le f(x, \theta_2) + \frac{\beta}{2} \|\theta_1 - \theta_2\|^2. $$

As a consequence,

$$ \begin{align*} \mathrm{KL}(\mathbb{P}_{\theta_1} \| \mathbb{P}_{\theta_2}) &= \int \ln \left( \frac{d\mathbb{P}_{\theta_1}}{d\mathbb{P}_{\theta_2}} \right) d\mathbb{P}_{\theta_1} = \int (f(X, \theta_1) - f(X, \theta_2)) d\mathbb{P}_{\theta_1}(X) \\ &\le \int \left( -\nabla_{\theta} f(X, \theta_1)^T (\theta_2 - \theta_1) + \frac{\beta}{2} \|\theta_1 - \theta_2\|^2 \right) d\mathbb{P}_{\theta_1}(X) \\ &\stackrel{(17)}{=} \int \frac{\beta}{2} \|\theta_1 - \theta_2\|^2 d\mathbb{P}_{\theta_1}(X) = \frac{\beta}{2} \|\theta_1 - \theta_2\|^2. \end{align*} $$

□

We may apply Proposition 1 with $\gamma = \beta/2$ and we obtain that

$$ \mathfrak{M}_n (\rho\text{-zCDP}, (\mathbb{P}_{\theta}^{\otimes n})_{\theta \in \Theta}, \|\cdot - \cdot\|, (\cdot)^2) = \Omega \left( \max \left\{ \frac{d}{n^2 \beta \rho}, \frac{d}{n \beta} \right\} \right) \qquad (18) $$

Under the hypotheses of Proposition 1: $d$ is big enough, $\rho$ is small enough and the interior of the parameter space is big enough. In particular, this gives us a lower bound to compare any private estimator to.

## 4.2 Private maximum likelihood

In general, $\hat{\theta}_{\mathrm{ML}}$ has no closed form formula. Even when it has some, the closed form formula usually does not respect differential privacy.

The problem (16) is typically addressed via numerical optimization: instead of considering its explicit maximum, a provably converging sequence is constructed. This requires some assumptions on the log-likelihood $f$. A convenient combination of hypotheses is that $f$ is $\lambda$-strongly concave, $\beta$-smooth and $L$-Lipschitz in its
second argument: then, the stochastic gradient ascend algorithm converges rapidly to $\hat{\theta}_{\text{ML}}$ (Beck, 2017). Exponential families typically obey those requirements with $\beta := \sup_{\theta \in \Theta} \lambda_{\text{max}}(C_{\theta})$ and, $\lambda := \inf_{\theta \in \Theta} \lambda_{\text{min}}(C_{\theta})$ where $C_{\theta} := \text{Cov}_{X \sim \mathcal{P}_{\theta}}(T(X))$ and $\lambda_{\text{min}}(C)$ (resp. $\lambda_{\text{max}}(C)$) denotes the smallest (resp. largest) eigenvalue of a matrix $C$ (see Boucheron et al. (2019, Théorème 4.10)).

The issue of privacy can be addressed directly in the optimization procedure. DP-SGD (Abadi et al., 2016) is an adaptation of the Stochastic Gradient Descent method where the gradient is first clipped and then noised. The privacy guarantees are based on the moment accountant method or on the composition of Renyi differential privacy (Mironov, 2017). The results are obtained under very general hypotheses on the objective function, but are based on a pessimistic scenario where an adversary may observe every gradient in the optimizer. Recent work based on Langevin diffusion (Chourasia et al., 2021; Ryffel et al., 2022) has adapted the Gradient Descent algorithm and the Stochastic Gradient Descent algorithm in order to have privacy guarantees with tighter utility bounds at the price of stronger hypotheses on the objective function which is required to have a compact domain and to be strongly convex.

Building on DP-SGLD by Ryffel et al. (2022), we consider its adaptation for maximum likelihood DP-SGML (Algorithm 1). For a batch $\mathcal{B} \subseteq \{1, \dots, n\}$, the batch log-likelihood is defined as

$$l_{\mathcal{B}}(\theta) := \frac{1}{\#(\mathcal{B})} \sum_{i \in \mathcal{B}} f(X_i, \theta).$$

For a closed convex set $\Theta$, $\Pi_{\Theta}$ refers to the projection onto $\Theta$.

**Data:** $X_1, \dots, X_n$, $f$, step sizes $(\eta_k)_{k \ge 0}$, batch size $m$, noise variance $\sigma^2$, initial parameter $\theta_0$, stopping time $K$.

for $k = 0, \dots, K-1$ do

Sample batch $\mathcal{B}_k$ from $X_1, \dots, X_n$ with replacement of size $m$;

Compute $\nabla l_{\mathcal{B}_k}(\theta_k) = \frac{1}{\#(\mathcal{B}_k)} \sum_{i \in \mathcal{B}_k} \nabla_{\theta_k} f(X_i, \theta_k)$;

Update parameter $\theta_{k+1} = \Pi_{\Theta}(\theta_k + \eta_k \nabla l_{\mathcal{B}_k}(\theta_k) + \sqrt{2\eta_k} \mathcal{N}(0, \sigma^2 I_d))$.

end

return $\theta_K$

**Algorithm 1:** DP-SGML: Differentially Private Stochastic Gradient Maximum Likelihood

A choice of the parameters $(\eta_k)_{k \ge 0}$, $\sigma^2$, $\theta_0$ and $K$ is suggested by the privacy-utility theorem Fact 5 which is a direct corollary of Ryffel et al. (2022).

**Fact 5** (Utility and Privacy of Algorithm 1, Fixed Step Size). Assume that $f$ is $\lambda$-strongly concave, $\beta$-smooth and $L$-Lipschitz in its second argument on $\Theta$. Consider any $\rho > 0$, an integer $n \ge 1$, a batch size $m$ and set

$$\sigma^2 := \frac{4L^2}{\rho\lambda n^2}, \quad K := \frac{2\beta}{\lambda} \ln \left( \frac{\rho n^2}{d} \right), \quad \xi^2 := \mathbb{E}_{\mathcal{B}} \left( \| \nabla l_{\mathcal{B}}(\theta_{\text{ML}}) \|^2 \right)$$

Given a collection $\mathbf{X}$ of $n$ arbitrary samples, consider $\mathfrak{M}(\mathbf{X}) = \theta_K$ obtained using DP-SGML with $\theta_0 \sim \Pi_{\Theta}(\mathcal{N}(0, \frac{2\sigma^2}{\lambda} I_d))$ and constant step size $\eta = \frac{1}{2\beta}$. This mechanism satisfies $\rho$-zCDP. Moreover, if $\mathbf{X}$ is such that the solution $\theta_{\text{ML}}$ of (16) is in the interior of $\Theta$, then

$$\mathbb{E} \left( \| \theta_{\text{ML}} - \theta_K \|^2 \right) = O \left( \frac{\beta d L^2}{\rho \lambda^3 n^2} \right) + \frac{\xi^2}{2\lambda^2}$$

where the expectation is with respect to initialization, random batch sampling, and noise addition in the parameter update step.

Indeed, the direct application of (Ryffel et al., 2022, Theorem 4.1) gives the privacy guarantee, and that

$$\mathbb{E} (l(\theta_{\text{ML}}) - l(\theta_K)) = O \left( \frac{\beta d L^2}{\rho \lambda^2 n^2} \right) + \frac{\xi^2}{4\lambda}.$$
second argument: then, the stochastic gradient ascend algorithm converges rapidly to $\hat{\theta}_{\text{ML}}$ (Beck, 2017). Exponential families typically obey those requirements with $\beta := \sup_{\theta \in \Theta} \lambda_{\text{max}}(C_{\theta})$ and, $\lambda := \inf_{\theta \in \Theta} \lambda_{\text{min}}(C_{\theta})$ where $C_{\theta} := \text{Cov}_{X \sim \mathcal{P}_{\theta}}(T(X))$ and $\lambda_{\text{min}}(C)$ (resp. $\lambda_{\text{max}}(C)$) denotes the smallest (resp. largest) eigenvalue of a matrix $C$ (see Boucheron et al. (2019, Théorème 4.10)).

The issue of privacy can be addressed directly in the optimization procedure. DP-SGD (Abadi et al., 2016) is an adaptation of the Stochastic Gradient Descent method where the gradient is first clipped and then noised. The privacy guarantees are based on the moment accountant method or on the composition of Renyi differential privacy (Mironov, 2017). The results are obtained under very general hypotheses on the objective function, but are based on a pessimistic scenario where an adversary may observe every gradient in the optimizer. Recent work based on Langevin diffusion (Chourasia et al., 2021; Ryffel et al., 2022) has adapted the Gradient Descent algorithm and the Stochastic Gradient Descent algorithm in order to have privacy guarantees with tighter utility bounds at the price of stronger hypotheses on the objective function which is required to have a compact domain and to be strongly convex.

Building on DP-SGLD by Ryffel et al. (2022), we consider its adaptation for maximum likelihood DP-SGML (Algorithm 1). For a batch $\mathcal{B} \subseteq \{1, \dots, n\}$, the batch log-likelihood is defined as

$$l_{\mathcal{B}}(\theta) := \frac{1}{\#(\mathcal{B})} \sum_{i \in \mathcal{B}} f(X_i, \theta).$$

For a closed convex set $\Theta$, $\Pi_{\Theta}$ refers to the projection onto $\Theta$.

**Data:** $X_1, \dots, X_n, f$, step sizes $(\eta_k)_{k \ge 0}$, batch size $m$, noise variance $\sigma^2$, initial parameter $\theta_0$, stopping time $K$.

for $k = 0, \dots, K-1$ do

Sample batch $\mathcal{B}_k$ from $X_1, \dots, X_n$ with replacement of size $m$;

Compute $\nabla l_{\mathcal{B}_k}(\theta_k) = \frac{1}{\#(\mathcal{B}_k)} \sum_{i \in \mathcal{B}_k} \nabla_{\theta} f(X_i, \theta_k)$;

Update parameter $\theta_{k+1} = \Pi_{\Theta}(\theta_k + \eta_k \nabla l_{\mathcal{B}_k}(\theta_k) + \sqrt{2\eta_k} \mathcal{N}(0, \sigma^2 I_d))$.

end

return $\theta_K$

**Algorithm 1:** DP-SGML: Differentially Private Stochastic Gradient Maximum Likelihood

A choice of the parameters $(\eta_k)_{k \ge 0}$, $\sigma^2$, $\theta_0$ and $K$ is suggested by the privacy-utility theorem Fact 5 which is a direct corollary of Ryffel et al. (2022).

**Fact 5** (Utility and Privacy of Algorithm 1, Fixed Step Size). Assume that $f$ is $\lambda$-strongly concave, $\beta$-smooth and $L$-Lipschitz in its second argument on $\Theta$. Consider any $\rho > 0$, an integer $n \ge 1$, a batch size $m$ and set

$$\sigma^2 := \frac{4L^2}{\rho\lambda n^2}, \quad K := \frac{2\beta}{\lambda} \ln \left( \frac{\rho n^2}{d} \right), \quad \xi^2 := \mathbb{E}_{\mathcal{B}} \left( \| \nabla l_{\mathcal{B}}(\theta_{\text{ML}}) \|^2 \right)$$

Given a collection $\mathbf{X}$ of $n$ arbitrary samples, consider $\mathfrak{M}(\mathbf{X}) = \theta_K$ obtained using DP-SGML with $\theta_0 \sim \Pi_{\Theta}(\mathcal{N}(0, \frac{2\sigma^2}{\lambda}I_d))$ and constant step size $\eta = \frac{1}{2\beta}$. This mechanism satisfies $\rho$-zCDP. Moreover, if $\mathbf{X}$ is such that the solution $\theta_{\text{ML}}$ of (16) is in the interior of $\Theta$, then

$$\mathbb{E} \left( \| \theta_{\text{ML}} - \theta_K \|^2 \right) = O \left( \frac{\beta d L^2}{\rho \lambda^3 n^2} \right) + \frac{\xi^2}{2\lambda^2}$$

where the expectation is with respect to initialization, random batch sampling, and noise addition in the parameter update step.

Indeed, the direct application of (Ryffel et al., 2022, Theorem 4.1) gives the privacy guarantee, and that

$$\mathbb{E} (l(\theta_{\text{ML}}) - l(\theta_K)) = O \left( \frac{\beta d L^2}{\rho \lambda^2 n^2} \right) + \frac{\xi^2}{4\lambda}.$$
Furthermore, by $\lambda$-strong concavity of $l$,

$$l(\theta_{\text{ML}}) - l(\theta_{K}) \geq \nabla l(\theta_{\text{ML}})(\theta_{K} - \theta_{\text{ML}}) + \frac{\lambda}{2} \|\theta_{L} - \theta_{\text{ML}}\|^{2}$$

and since $\theta_{\text{ML}}$ is in the interior of $\Theta$, $\nabla l(\theta_{\text{ML}}) = 0$ which concludes the proof. The term $\xi^2 := \mathbb{E}_B (\|\nabla l_B(\theta_{\text{ML}})\|^2)$ is due to the stochastic noise of the batch sampling. Indeed, even though $\nabla l(\theta_{\text{ML}}) = 0$, this is not necessarily the case when working on batches. This term depends on the batch size $m$ and can be made arbitrarily small by choosing $m$ large enough.

### 4.3 About minimax optimality

The quadratic risk of any (private or not) solver $\mathfrak{M}$ can be decomposed (by the triangle inequality and since $(a+b)^2 \leq 2a^2 + 2b^2, \forall a, b \geq 0$) as:

$$\mathbb{E} (\|\theta^* - \mathfrak{M}(\mathbf{X})\|^2) \leq 2 \left( \mathbb{E} (\|\theta^* - \theta_{\text{ML}}\|^2) + \mathbb{E} (\|\theta_{\text{ML}} - \mathfrak{M}(\mathbf{X})\|^2) \right) \quad (19)$$

where the expectation is over the draw of $\mathbf{X}$ and, in the case of a private solver, on the intrinsic randomness of $\mathfrak{M}$.

The first term in the right hand side of (19) only depends on the properties of the “ideal” maximum likelihood estimator in this parametric model. Under mild assumptions, it is asymptotically normal – for example, in exponential families (see Van der Vaart (2000, Theorem 4.6)): we have

$$\sqrt{n}(\theta^* - \theta_{\text{ML}}) \rightsquigarrow \mathcal{N}(0, C_{\theta^*}^{-1}),$$

where $\rightsquigarrow$ refers to the convergence in distribution, and

$$\mathbb{E} (\|\theta^* - \theta_{\text{ML}}\|^2) = O \left( \frac{d}{n\lambda} \right). \quad (20)$$

The second term in (19) depends on the solver, which here can be controlled with Fact 5. As a consequence, the ratio between the error of estimation and the minimax risk which is lower-bounded in (18) can be bounded as follows:

$$\frac{\mathbb{E} (\|\theta^* - \mathfrak{M}(\mathbf{X})\|^2)}{\mathfrak{M}_n (\rho\text{-zCDP}, (\mathbb{P}_{\theta}^{\otimes n})_{\theta \in \Theta}, \|\cdot - \cdot\|, (\cdot)^2)} \\ \stackrel{(19)\& (18)}{=} O \left( \frac{\mathbb{E} (\|\theta^* - \theta_{\text{ML}}\|^2) + \mathbb{E} (\|\theta_{\text{ML}} - \mathfrak{M}(\mathbf{X})\|^2)}{\max \left\{ \frac{d}{n^2 \beta \rho}, \frac{d}{n \beta} \right\}} \right) \\ = O \left( \frac{n \beta}{d} \mathbb{E} (\|\theta^* - \theta_{\text{ML}}\|^2) + \frac{n^2 \beta \rho}{d} \mathbb{E} (\|\theta_{\text{ML}} - \mathfrak{M}(\mathbf{X})\|^2) \right).$$

In particular, for the fixed step-size (see Fact 5), when $\theta_{\text{ML}}$ is in the interior of $\Theta$ and when the variance term due to the clipped gradient is negligible (i.e., when the batch size is big enough to have $\frac{\xi^2}{4\lambda} = O(\frac{\beta d L^2}{\rho \lambda^2 n^2})$), the second term is $O(\frac{\beta^2 L^2}{\lambda^3})$.

All in all, the ratio between the risk of DP-SGML for maximum likelihood in exponential families when the maximum likelihood estimator is in the interior of the search set is

$$\frac{\mathbb{E} (\|\theta^* - \mathfrak{M}(\mathbf{X})\|^2)}{\mathfrak{M}_n (\rho\text{-zCDP}, (\mathbb{P}_{\theta}^{\otimes n})_{\theta \in \Theta}, \|\cdot - \cdot\|, (\cdot)^2)} = O \left( \frac{\beta}{\lambda} + \frac{\beta^2 L^2}{\lambda^3} \right).$$

DP-SGML optimally captures the variation in the sample size $n$, in the privacy parameter $\rho$, and to some extent, in the dimensionality $d$ (to some extent because even if $d$ vanishes in the expressions, $L$, $\beta$ and $\lambda$ may vary with $d$). This proves what we call the near-minimax optimality of DP-SG(L)D for performing inference via maximum likelihood in a broad class of parametric models.
Furthermore, by $\lambda$-strong concavity of $l$,

$$l(\theta_{\text{ML}}) - l(\theta_K) \geq \nabla l(\theta_{\text{ML}})(\theta_K - \theta_{\text{ML}}) + \frac{\lambda}{2} \|\theta_L - \theta_{\text{ML}}\|^2$$

and since $\theta_{\text{ML}}$ is in the interior of $\Theta$, $\nabla l(\theta_{\text{ML}}) = 0$ which concludes the proof. The term $\xi^2 := \mathbb{E}_B (\|\nabla l_B(\theta_{\text{ML}})\|^2)$ is due to the stochastic noise of the batch sampling. Indeed, even though $\nabla l(\theta_{\text{ML}}) = 0$, this is not necessarily the case when working on batches. This term depends on the batch size $m$ and can be made arbitrarily small by choosing $m$ large enough.

## 4.3 About minimax optimality

The quadratic risk of any (private or not) solver $\mathfrak{M}$ can be decomposed (by the triangle inequality and since $(a+b)^2 \leq 2a^2 + 2b^2, \forall a, b \geq 0)$ as:

$$\mathbb{E} (\|\theta^* - \mathfrak{M}(\mathbf{X})\|^2) \leq 2 \left( \mathbb{E} (\|\theta^* - \theta_{\text{ML}}\|^2) + \mathbb{E} (\|\theta_{\text{ML}} - \mathfrak{M}(\mathbf{X})\|^2) \right) \quad (19)$$

where the expectation is over the draw of $\mathbf{X}$ and, in the case of a private solver, on the intrinsic randomness of $\mathfrak{M}$.

The first term in the right hand side of (19) only depends on the properties of the “ideal” maximum likelihood estimator in this parametric model. Under mild assumptions, it is asymptotically normal – for example, in exponential families (see Van der Vaart (1998, Theorem 4.6)): we have

$$\sqrt{n}(\theta^* - \theta_{\text{ML}}) \rightsquigarrow \mathcal{N}(0, C_{\theta^*}^{-1}),$$

where $\rightsquigarrow$ refers to the convergence in distribution, and

$$\mathbb{E} (\|\theta^* - \theta_{\text{ML}}\|^2) = O \left( \frac{d}{n\lambda} \right). \quad (20)$$

The second term in (19) depends on the solver, which here can be controlled with Fact 5. As a consequence, the ratio between the error of estimation and the minimax risk which is lower-bounded in (18) can be bounded as follows:

$$\frac{\mathbb{E} (\|\theta^* - \mathfrak{M}(\mathbf{X})\|^2)}{\mathfrak{M}_n (\rho\text{-zCDP}, (\mathbb{P}_{\theta}^{\otimes n})_{\theta \in \Theta}, \|\cdot - \cdot\|, (\cdot)^2)} \\ \stackrel{(19)\& (18)}{=} O \left( \frac{\mathbb{E} (\|\theta^* - \theta_{\text{ML}}\|^2) + \mathbb{E} (\|\theta_{\text{ML}} - \mathfrak{M}(\mathbf{X})\|^2)}{\max \left\{ \frac{d}{n^2 \beta \rho}, \frac{d}{n \beta} \right\}} \right) \\ = O \left( \frac{n \beta}{d} \mathbb{E} (\|\theta^* - \theta_{\text{ML}}\|^2) + \frac{n^2 \beta \rho}{d} \mathbb{E} (\|\theta_{\text{ML}} - \mathfrak{M}(\mathbf{X})\|^2) \right).$$

In particular, for the fixed step-size (see Fact 5), when $\theta_{\text{ML}}$ is in the interior of $\Theta$ and when the variance term due to the clipped gradient is negligible (i.e., when the batch size is big enough to have $\frac{\xi^2}{4\lambda} = O(\frac{\beta d L^2}{\rho \lambda^2 n^2})$), the second term is $O(\frac{\beta^2 L^2}{\lambda^3})$.

All in all, the ratio between the risk of DP-SGML for maximum likelihood in exponential families when the maximum likelihood estimator is in the interior of the search set is

$$\frac{\mathbb{E} (\|\theta^* - \mathfrak{M}(\mathbf{X})\|^2)}{\mathfrak{M}_n (\rho\text{-zCDP}, (\mathbb{P}_{\theta}^{\otimes n})_{\theta \in \Theta}, \|\cdot - \cdot\|, (\cdot)^2)} = O \left( \frac{\beta}{\lambda} + \frac{\beta^2 L^2}{\lambda^3} \right).$$

DP-SGML optimally captures the variation in the sample size $n$, in the privacy parameter $\rho$, and to some extent, in the dimensionality $d$ (to some extent because even if $d$ vanishes in the expressions, $L$, $\beta$ and $\lambda$ may vary with $d$). This proves what we call the near-minimax optimality of DP-SG(L)D for performing inference via maximum likelihood in a broad class of parametric models.
## Acknowledgement

Aurélien Garivier acknowledges the support of the Project IDEXLYON of the University of Lyon, in the framework of the Programme Investissements d'Avenir (ANR-16-IDEX-0005), and Chaire SeqALO (ANR-20-CHIA-0020-01). This project was supported in part by the AllegroAssai ANR project ANR-19-CHIA-0009. Additionally, we thank the anonymous reviewers for their precious inputs and suggestions.

## References

Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In *Proceedings of the 2016 ACM SIGSAC conference on computer and communications security*, pp. 308–318, 2016.

John M Abowd. The us census bureau adopts differential privacy. In *Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining*, pp. 2867–2867, 2018.

Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private testing of identity and closeness of discrete distributions. *Advances in Neural Information Processing Systems*, 31, 2018.

Jayadev Acharya, Clément L. Canonne, Cody Freitag, Ziteng Sun, and Himanshu Tyagi. Inference under information constraints III: local privacy constraints. *IEEE J. Sel. Areas Inf. Theory*, 2(1):253–267, 2021a.

Jayadev Acharya, Clément L. Canonne, Prathamesh Mayekar, and Himanshu Tyagi. Information-constrained optimization: can adaptive processing of gradients help? *CoRR*, abs/2104.00979, 2021b.

Jayadev Acharya, Clément L. Canonne, Aditya Vikram Singh, and Himanshu Tyagi. Optimal rates for nonparametric density estimation under communication constraints. *CoRR*, abs/2107.10078, 2021c.

Jayadev Acharya, Clément L. Canonne, Zuteng Sun, and Himanshu Tyagi. Unified lower bounds for interactive high-dimensional estimation under information constraints. *CoRR*, abs/2010.06562, 2021d.

Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. In *Algorithmic Learning Theory*, pp. 48–78. PMLR, 2021e.

Omer Angel and Yinon Spinka. Pairwise optimal coupling of multiple random variables. *arXiv preprint arXiv:1903.00632*, 2019.

Hilal Asi and John C Duchi. Near instance-optimality in differential privacy. *arXiv preprint arXiv:2005.10630*, 2020a.

Hilal Asi and John C Duchi. Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), *Advances in Neural Information Processing Systems*, volume 33, pp. 14106–14117. Curran Associates, Inc., 2020b.

Patrice Assouad. Deux remarques sur l'estimation. *Comptes rendus des séances de l'Académie des sciences. Série 1, Mathématique*, 296(23):1021–1024, 1983.

Lars Backstrom, Cynthia Dwork, and Jon Kleinberg. Wherefore art thou r3579x? anonymized social networks, hidden patterns, and structural steganography. In *Proceedings of the 16th international conference on World Wide Web*, pp. 181–190, 2007.

Leighton P. Barnes, Yanjun Han, and Ayfer Özgür. Fisher information for distributed estimation under a blackboard communication protocol. In *ISIT*, pp. 2704–2708. IEEE, 2019.

Leighton Pate Barnes, Wei-Ning Chen, and Ayfer Özgür. Fisher information under local differential privacy. *IEEE J. Sel. Areas Inf. Theory*, 1(3):645–659, 2020a.

Leighton Pate Barnes, Yanjun Han, and Ayfer Özgür. Lower bounds for learning distributions under communication constraints via fisher information. *J. Mach. Learn. Res.*, 21:Paper No. 236, 30, 2020b. ISSN 1532-4435.
## Acknowledgement

Aurélien Garivier acknowledges the support of the Project IDEXLYON of the University of Lyon, in the framework of the Programme Investissements d'Avenir (ANR-16-IDEX-0005), and Chaire SeqALO (ANR-20-CHIA-0020-01). This project was supported in part by the AllegroAssai ANR project ANR-19-CHIA-0009. Additionally, we thank the anonymous reviewers for their precious inputs and suggestions.

## References

* Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In *Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi (eds.), Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016*, pp. 308–318. ACM, 2016. doi: 10.1145/2976749.2978318. URL https://doi.org/10.1145/2976749.2978318.

* John M Abowd. The us census bureau adopts differential privacy. In *Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining*, pp. 2867–2867, 2018.

* Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private testing of identity and closeness of discrete distributions. In *Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada*, pp. 6879–6891, 2018. URL https://proceedings.neurips.cc/paper/2018/hash/7de32147a4f1055bed9e4faf3485a84d-Abstract.html.

* Jayadev Acharya, Clement Canonne, Aditya Vikram Singh, and Himanshu Tyagi. Optimal rates for nonparametric density estimation under communication constraints. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), *Advances in Neural Information Processing Systems*, volume 34, pp. 26754–26766. Curran Associates, Inc., 2021a. URL https://proceedings.neurips.cc/paper_files/paper/2021/file/e1021d43911ca2c1845910d84f40aeae-Paper.pdf.

* Jayadev Acharya, Clément L. Canonne, Prathamesh Mayekar, and Himanshu Tyagi. Information-constrained optimization: can adaptive processing of gradients help? *CoRR*, abs/2104.00979, 2021b. URL https://arxiv.org/abs/2104.00979.

* Jayadev Acharya, Clément L. Canonne, Ziteng Sun, and Himanshu Tyagi. Unified lower bounds for interactive high-dimensional estimation under information constraints. *CoRR*, abs/2010.06562, 2021c. URL https://arxiv.org/abs/2010.06562.

* Jayadev Acharya, Clément L. Canonne, Cody Freitag, Ziteng Sun, and Himanshu Tyagi. Inference under information constraints iii: Local privacy constraints. *IEEE Journal on Selected Areas in Information Theory*, 2(1):253–267, 2021d. doi: 10.1109/JSAIT.2021.3053569. URL https://doi.org/10.1109/JSAIT.2021.3053569.

* Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato (eds.), *Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide*, volume 132 of *Proceedings of Machine Learning Research*, pp. 48–78. PMLR, 2021e. URL http://proceedings.mlr.press/v132/acharya21a.html.

* Omer Angel and Yinon Spinka. Pairwise optimal coupling of multiple random variables, 2021. URL https://arxiv.org/pdf/1903.00632.pdf.

* Hilal Asi and John C. Duchi. Near instance-optimality in differential privacy. *CoRR*, abs/2005.10630, 2020a. URL https://arxiv.org/abs/2005.10630.

* Hilal Asi and John C. Duchi. Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), *Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual*, 2020b. URL https://proceedings.neurips.cc/paper/2020/hash/a267f936e54d7c10a2bb70dbe6ad7a89-Abstract.html.
Björn Bebensee. Local differential privacy: a tutorial. *arXiv preprint arXiv:1907.11908*, 2019.

Amir Beck. *First-order methods in optimization*. SIAM, 2017.

Omri Ben-Eliezer, Dan Mikulincer, and Ilias Zadik. Archimedes meets privacy: On privately estimating quantiles in high dimensions under minimal assumptions. *arXiv preprint arXiv:2208.07438*, 2022.

Peter J Bickel and Yaacov Ritov. Estimating integrated squared density derivatives: sharp best order of convergence estimates. *Sankhyā: The Indian Journal of Statistics, Series A*, pp. 381–393, 1988.

Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman. Coinpress: Practical private mean and covariance estimation. *Advances in Neural Information Processing Systems*, 33:14475–14485, 2020.

Boucheron, Boyer, and Ryder. Cours de statistiques, ens ulm, fimfa ens. 2019.

Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In *Theory of Cryptography Conference*, pp. 635–658. Springer, 2016.

Mark Bun and Thomas Steinke. Average-case averages: Private algorithms for smooth sensitivity and mean estimation. *Advances in Neural Information Processing Systems*, 32, 2019.

Mark Bun, Gautam Kamath, Thomas Steinke, and Steven Z Wu. Private hypothesis selection. *Advances in Neural Information Processing Systems*, 32, 2019.

Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. *Journal of Machine Learning Research*, 12(3), 2011.

Rishav Chourasia, Jiayuan Ye, and Reza Shokri. Differential privacy dynamics of langevin diffusion and noisy gradient descent. *Advances in Neural Information Processing Systems*, 34:14771–14781, 2021.

Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang. Privacy at scale: Local differential privacy in practice. In *Proceedings of the 2018 International Conference on Management of Data*, pp. 1655–1658, 2018.

Luc Devroye. *A course in density estimation*. Birkhauser Boston Inc., 1987.

Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. Differentially private learning of structured discrete distributions. *Advances in Neural Information Processing Systems*, 28, 2015.

Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. *arXiv preprint arXiv:1712.01524*, 2017.

Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In *Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems*, pp. 202–210, 2003.

Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. *arXiv preprint arXiv:1905.02383*, 2019.

Jinshuo Dong, David Durfee, and Ryan Rogers. Optimal differential privacy composition for exponential mechanisms. In *International Conference on Machine Learning*, pp. 2597–2606. PMLR, 2020.

Wenxin Du, Canyon Foot, Monica Moniot, Andrew Bray, and Adam Groce. Differentially private confidence intervals. *arXiv preprint arXiv:2001.02285*, 2020.

John C Duchi, Michael I Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In *2013 IEEE 54th Annual Symposium on Foundations of Computer Science*, pp. 429–438. IEEE, 2013a.

John C Duchi, Michael I Jordan, and Martin J Wainwright. Local privacy, data processing inequalities, and minimax rates. *arXiv preprint arXiv:1302.3203*, 2013b.
Patrice Assouad. Deux remarques sur l'estimation. *Comptes rendus des séances de l'Académie des sciences.*
Série 1, Mathématique, 296(23):1021-1024, 1983.

Lars Backstrom, Cynthia Dwork, and Jon M. Kleinberg. Wherefore art thou r3579x?: anonymized social
networks, hidden patterns, and structural steganography. In Carey L. Williamson, Mary Ellen Zurko,
Peter F. Patel-Schneider, and Prashant J. Shenoy (eds.), *Proceedings of the 16th International Conference
on World Wide Web, WWW 2007, Banff, Alberta, Canada, May 8-12, 2007*, pp. 181–190. ACM, 2007.
doi: 10.1145/1242572.1242598. URL https://doi.org/10.1145/1242572.1242598.

Leighton Pate Barnes, Yanjun Han, and Ayfer Ozgur. Fisher information for distributed estimation under a blackboard communication protocol. In *2019 IEEE International Symposium on Information Theory (ISIT)*, pp. 2704–2708, 2019. doi: 10.1109/ISIT.2019.8849821.

Leighton Pate Barnes, Wei-Ning Chen, and Ayfer Ozgur. Fisher information under local differential privacy.
*IEEE Journal on Selected Areas in Information Theory*, 1(3):645–659, 2020a. doi: 10.1109/JSAIT.2020.
3039461. URL https://doi.org/10.1109/JSAIT.2020.3039461.

Leighton Pate Barnes, Yanjun Han, and Ayfer Özgür. Lower bounds for learning distributions under communication constraints via fisher information. *Journal of Machine Learning Research*, 21:Paper No. 236, 30, 2020b. ISSN 1532-4435. URL https://jmlr.csail.mit.edu/papers/volume21/19-737/19-737.pdf.

Björn Bebensee. Local differential privacy: a tutorial. arXiv preprint arXiv:1907.11908, 2019.

Amir Beck. *First-Order Methods in Optimization*. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2017. doi: 10.1137/1.9781611974997. URL https://epubs.siam.org/doi/abs/10.1137/1.9781611974997.

Omri Ben-Eliezer, Dan Mikulincer, and Ilias Zadik. Archimedes meets privacy: On privately estimating quantiles in high dimensions under minimal assumptions. arXiv preprint arXiv:2208.07438, 2022.

Peter J Bickel and Yaacov Ritov. Estimating integrated squared density derivatives: sharp best order of convergence estimates. *Sankhyā: The Indian Journal of Statistics, Series A*, pp. 381–393, 1988.

Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan R. Ullman. Coinpress: Practical private mean and covariance estimation. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), *Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual*, 2020. URL https://proceedings.neurips.cc/paper/2020/hash/a684eceee76fc522773286a895bc8436-Abstract.html.

Adam Block, Ali Jadbabaie, Daniel Pfrommer, Max Simchowitz, and Russ Tedrake. Provable guarantees for generative behavior cloning: Bridging low-level stability and high-level behavior. *Advances in Neural Information Processing Systems*, 36, 2024.

Boucheron, Boyer, and Ryder. Cours de statistiques, ens ulm, fimfa ens. *Lectures at the École Normale Supérieure*, 2019. URL https://stephane-v-boucheron.fr/files/stats/notes-17-18.pdf.

Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam D. Smith (eds.), *Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part I*, volume 9985 of *Lecture Notes in Computer Science*, pp. 635–658, 2016. doi: 10.1007/978-3-662-53641-4\_24. URL https://doi.org/10.1007/978-3-662-53641-4_24.

Mark Bun and Thomas Steinke. Average-case averages: Private algorithms for smooth sensitivity and mean estimation. *Advances in Neural Information Processing Systems*, 32, 2019.

Mark Bun, Gautam Kamath, Thomas Steinke, and Steven Z Wu. Private hypothesis selection. *Advances in Neural Information Processing Systems*, 32, 2019.
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In *Proceedings of the forty-first annual ACM symposium on Theory of computing*, pp. 371–380, 2009.

Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. *arXiv preprint arXiv:1603.01887*, 2016.

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In *Theory of cryptography conference*, pp. 265–284. Springer, 2006.

Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. *Foundations and Trends in Theoretical Computer Science*, 9(3-4):211–407, 2014.

Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preserving ordinal response. In *Proceedings of the 2014 ACM SIGSAC conference on computer and communications security*, pp. 1054–1067, 2014.

Alireza Farhadi, Mohammadtaghi Hajiaghai, and Elaine Shi. Differentially private densest subgraph. In *International Conference on Artificial Intelligence and Statistics*, pp. 11581–11597. PMLR, 2022.

Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In *Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security*, pp. 1322–1333, 2015.

Christophe Giraud. *Introduction to high-dimensional statistics*. Chapman and Hall/CRC, 2021.

László Györfi, Michael Kohler, Adam Krzyzak, Harro Walk, et al. *A distribution-free theory of nonparametric regression*, volume 1. Springer, 2002.

Rob Hall, Alessandro Rinaldo, and Larry Wasserman. Random differential privacy. *arXiv preprint arXiv:1112.2680*, 2011.

Nils Homer, Szabolcs Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill Muehling, John V Pearson, Dietrich A Stephan, Stanley F Nelson, and David W Craig. Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density snp genotyping microarrays. *PLoS Genet*, 4(8):e1000167, 2008.

Il'dar Abdulovich Ibragimov and Rafail Zalmanovich Has' Minskii. *Statistical estimation: asymptotic theory*, volume 16. Springer Science & Business Media, 2013.

Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In *International conference on machine learning*, pp. 1376–1385. PMLR, 2015.

Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. In *International Conference on Machine Learning*, pp. 10633–10660. PMLR, 2022.

Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. *arXiv preprint arXiv:1711.03908*, 2017.

Clément Lalanne, Clément Gastaud, Nicolas Grislain, Aurélien Garivier, and Rémi Gribonval. Private quantiles estimation in the presence of atoms. *arXiv preprint arXiv:2202.08969*, 2022.

Torgny Lindvall. *Lectures on the coupling method*. Courier Corporation, 2002.

Grigorios Loukides, Joshua C Denny, and Bradley Malin. The disclosure of diagnosis codes can breach research participants' privacy. *Journal of the American Medical Informatics Association*, 17(3):322–327, 2010.

Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In *48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)*, pp. 94–103. IEEE, 2007.
Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In *Proceedings of the 55th Annual ACM Symposium on Theory of Computing*, pp. 520–527, 2023.

Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. *J. Mach. Learn. Res.*, 12:1069–1109, 2011. doi: 10.5555/1953048.2021036. URL https://dl.acm.org/doi/10.5555/1953048.2021036.

Rishav Chourasia, Jiayuan Ye, and Reza Shokri. Differential privacy dynamics of langevin diffusion and noisy gradient descent. *Advances in Neural Information Processing Systems*, 34:14771–14781, 2021.

Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang. Privacy at scale: Local differential privacy in practice. In *Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein (eds.), Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018*, pp. 1655–1658. ACM, 2018. doi: 10.1145/3183713.3197390. URL https://doi.org/10.1145/3183713.3197390.

Thomas M. Cover and Joy A. Thomas. *Elements of information theory (2. ed.)*. Wiley, 2006. ISBN 978-0-471-24195-9. URL http://www.elementsofinformationtheory.com/.

Luc Devroye. *A course in density estimation*. Birkhauser Boston Inc., 1987.

Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. Differentially private learning of structured discrete distributions. In *Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada*, pp. 2566–2574, 2015. URL https://proceedings.neurips.cc/paper/2015/hash/2b3bf3eee2475e03885a110e9acaab61-Abstract.html.

Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In *Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA*, pp. 3571–3580, 2017. URL https://proceedings.neurips.cc/paper/2017/hash/253614bbac999b38b5b60cae531c4969-Abstract.html.

Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In *Frank Neven, Catriel Beeri, and Tova Milo (eds.), Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA*, pp. 202–210. ACM, 2003. doi: 10.1145/773153.773173. URL https://doi.org/10.1145/773153.773173.

Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. *CoRR*, abs/1905.02383, 2019. URL http://arxiv.org/abs/1905.02383.

Jinshuo Dong, David Durfee, and Ryan Rogers. Optimal differential privacy composition for exponential mechanisms. In *Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event*, volume 119 of *Proceedings of Machine Learning Research*, pp. 2597–2606. PMLR, 2020. URL http://proceedings.mlr.press/v119/dong20a.html.

Wenxin Du, Canyon Foot, Monica Moniot, Andrew Bray, and Adam Groce. Differentially private confidence intervals. *CoRR*, abs/2001.02285, 2020. URL http://arxiv.org/abs/2001.02285.

John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Local privacy and statistical minimax rates. In *51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013, Allerton Park & Retreat Center, Monticello, IL, USA, October 2-4, 2013*, pp. 1592. IEEE, 2013. doi: 10.1109/Allerton.2013.6736718. URL https://doi.org/10.1109/Allerton.2013.6736718.

John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Local privacy, data processing inequalities, and statistical minimax rates, 2014. URL https://arxiv.org/abs/1302.3203.
Frank D McSherry. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In *Proceedings of the 2009 ACM SIGMOD International Conference on Management of data*, pp. 19–30, 2009.

Ilya Mironov. Rényi differential privacy. In *2017 IEEE 30th Computer Security Foundations Symposium (CSF)*, pp. 263–275. IEEE, 2017.

Arvind Narayanan and Vitaly Shmatikov. How to break anonymity of the netflix prize dataset. *arXiv preprint cs/0610105*, 2006.

Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large sparse datasets. In *2008 IEEE Symposium on Security and Privacy (sp 2008)*, pp. 111–125. IEEE, 2008.

Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. *Foundations and Trends in Machine Learning*, 11(5-6):355–607, 2019.

Phillippe Rigollet and Jan-Christian Hütter. High dimensional statistics. *Lecture notes for course 18S997*, 813(814):46, 2015.

Benjamin IP Rubinstein, Peter L Bartlett, Ling Huang, and Nina Taft. Learning in a large function space: Privacy-preserving mechanisms for svm learning. *arXiv preprint arXiv:0911.5708*, 2009.

Théo Ryffel, Francis Bach, and David Pointcheval. Differential privacy guarantees for stochastic gradient langevin dynamics. *arXiv preprint arXiv:2201.11980*, 2022.

Filippo Santambrogio. Optimal transport for applied mathematicians. *Birkhäuser, NY*, 55(58-63):94, 2015.

Jonathan Scarlett and Volkan Cevher. An introductory guide to fano's inequality with applications in statistical estimation. *arXiv preprint arXiv:1901.00555*, 2019.

Adam Smith. Privacy-preserving statistical estimation with optimal convergence rates. In *Proceedings of the forty-third annual ACM symposium on Theory of computing*, pp. 813–822, 2011.

Latanya Sweeney. Simple demographics often identify people uniquely. *Health (San Francisco)*, 671(2000): 1–34, 2000.

Latanya Sweeney. k-anonymity: A model for protecting privacy. *International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems*, 10(05):557–570, 2002.

Youming Tao, Yulian Wu, Peng Zhao, and Di Wang. Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits. In *International Conference on Artificial Intelligence and Statistics*, pp. 1546–1574. PMLR, 2022.

Abhradeep Guha Thakurta, Andrew H Vyrros, Umesh S Vaishampayan, Gaurav Kapoor, Julien Freudiger, Vivek Rangarajan Sridhar, and Doug Davidson. Learning new words. *Granted US Patents*, 9594741, 2017.

MTCAJ Thomas and A Thomas Joy. *Elements of information theory*. Wiley-Interscience, 2006.

Alexandre B Tsybakov. *Introduction à l'estimation non paramétrique*, volume 41. Springer Science & Business Media, 2003.

Aad W Van der Vaart. *Asymptotic statistics*, volume 3. Cambridge university press, 2000.

Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. *IEEE Transactions on Information Theory*, 60(7):3797–3820, 2014.

Sergio Verdú et al. Generalizing the fano inequality. *IEEE Transactions on Information Theory*, 40(4): 1247–1251, 1994.

Isabel Wagner and David Eckhoff. Technical privacy metrics: a systematic survey. *ACM Computing Surveys (CSUR)*, 51(3):1–38, 2018.
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Michael Mitzenmacher (ed.), *Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009*, Bethesda, MD, USA, May 31 - June 2, 2009, pp. 371-380. ACM, 2009. doi: 10.1145/1536414.1536466. URL https://doi.org/10.1145/1536414.1536466.

Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. *Found. Trends Theor. Comput. Sci.*, 9(3-4):211-407, 2014. doi: 10.1561/0400000042. URL https://doi.org/10.1561/0400000042.

Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. *arXiv preprint arXiv:1603.01887*, 2016.

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin (eds.), *Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings*, volume 3876 of *Lecture Notes in Computer Science*, pp. 265-284. Springer, 2006. doi: 10.1007/11681878\_14. URL https://doi.org/10.1007/11681878_14.

Niva Elkin-Koren, Uri Hacohen, Roi Livni, and Shay Moran. Can copyright be reduced to privacy? *arXiv preprint arXiv:2305.14822*, 2023.

Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: randomized aggregatable privacy-preserving ordinal response. In Gail-Joon Ahn, Moti Yung, and Ninghui Li (eds.), *Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA, November 3-7, 2014*, pp. 1054-1067. ACM, 2014. doi: 10.1145/2660267.2660348. URL https://doi.org/10.1145/2660267.2660348.

Alireza Farhadi, Mohammad Taghi Hajiaghayi, and Elaine Shi. Differentially private densest sub-graph. In Gustav Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera (eds.), *International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event*, volume 151 of *Proceedings of Machine Learning Research*, pp. 11581-11597. PMLR, 2022. URL https://proceedings.mlr.press/v151/farhadi22a.html.

Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Indrajit Ray, Ninghui Li, and Christopher Kruegel (eds.), *Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12-16, 2015*, pp. 1322-1333. ACM, 2015. doi: 10.1145/2810103.2813677. URL https://doi.org/10.1145/2810103.2813677.

Christophe Giraud. *Introduction to high-dimensional statistics*. Chapman and Hall/CRC, 2021. ISBN 9781003158745. doi: 10.1201/9781003158745.

László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. *A Distribution-Free Theory of Nonparametric Regression*. Springer series in statistics. Springer, 2002. ISBN 978-0-387-95441-7. doi: 10.1007/b97848. URL https://doi.org/10.1007/b97848.

Rob Hall, Alessandro Rinaldo, and Larry A. Wasserman. Random differential privacy. *CoRR*, abs/1112.2680, 2011. URL http://arxiv.org/abs/1112.2680.

Te Sun Han and Sergio Verdú. Generalizing the fano inequality. *IEEE Trans. Inf. Theory*, 40(4):1247-1251, 1994. doi: 10.1109/18.335943. URL https://doi.org/10.1109/18.335943.

Nils Homer, Szabolcs Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill Muehling, John V Pearson, Dietrich A Stephan, Stanley F Nelson, and David W Craig. Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density snp genotyping microarrays. *PLoS Genet*, 4(8):e1000167, 2008.

I. A. Ibragimov and R. Z. Khasminskii. *Statistical estimation : asymptotic theory* / I. A. Ibragimov, R. Z. Hasminskii ; translated by Samuel Kotz. Springer-Verlag New York, 1981. ISBN 3540905235 0387905235.
Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. *Journal of the American Statistical Association*, 105(489):375–389, 2010.

Mengmeng Yang, Lingjuan Lyu, Jun Zhao, Tianqing Zhu, and Kwok-Yan Lam. Local differential privacy and its applications: A comprehensive survey. *arXiv preprint arXiv:2008.03686*, 2020.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In Francis R. Bach and David M. Blei (eds.), *Proceedings of the 32nd International Conference on Machine Learning*, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 1376–1385. JMLR.org, 2015. URL http://proceedings.mlr.press/v37/kairouz15.html.

Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistinguishability of learning algorithms. In *International Conference on Machine Learning*, pp. 15586–15622. PMLR, 2023.

Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), *International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA*, volume 162 of *Proceedings of Machine Learning Research*, pp. 10633–10660. PMLR, 2022. URL https://proceedings.mlr.press/v162/kamath22a.html.

Amin Karbasi, Grigoris Velegkas, Lin Yang, and Felix Zhou. Replicability in reinforcement learning. *Advances in Neural Information Processing Systems*, 36, 2024.

Vishesh Karwa and Salil P. Vadhan. Finite sample differentially private confidence intervals. In Anna R. Karlin (ed.), *9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA*, volume 94 of *LIPIcs*, pp. 44:1–44:9. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. doi: 10.4230/LIPIcs.ITCS.2018.44. URL https://doi.org/10.4230/LIPIcs.ITCS.2018.44.

Clément Lalanne, Clément Gastaud, Nicolas Grislain, Aurélien Garivier, and Rémi Gribonval. Private quantiles estimation in the presence of atoms. *CoRR*, abs/2202.08969, 2022. URL https://arxiv.org/abs/2202.08969.

Torgny Lindvall. *Lectures on the Coupling Method*. Dover Publications Inc., 2003. ISBN 978-0486421452.

Grigorios Loukides, Joshua C. Denny, and Bradley A. Malin. The disclosure of diagnosis codes can breach research participants’ privacy. *J. Am. Medical Informatics Assoc.*, 17(3):322–327, 2010. doi: 10.1136/jamia.2009.002725. URL https://doi.org/10.1136/jamia.2009.002725.

Frank McSherry. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. *Commun. ACM*, 53(9):89–97, 2010. doi: 10.1145/1810891.1810916. URL https://doi.org/10.1145/1810891.1810916.

Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In *48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings*, pp. 94–103. IEEE Computer Society, 2007. doi: 10.1109/FOCS.2007.41. URL https://doi.org/10.1109/FOCS.2007.41.

Ilya Mironov. Rényi differential privacy. In *30th IEEE Computer Security Foundations Symposium, CSF 2017, Santa Barbara, CA, USA, August 21-25, 2017*, pp. 263–275. IEEE Computer Society, 2017. doi: 10.1109/CSF.2017.11. URL https://doi.org/10.1109/CSF.2017.11.

Arvind Narayanan and Vitaly Shmatikov. How to break anonymity of the netflix prize dataset. *CoRR*, abs/cs/0610105, 2006. URL http://arxiv.org/abs/cs/0610105.

Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large sparse datasets. In *2008 IEEE Symposium on Security and Privacy (S&P 2008), 18-21 May 2008, Oakland, California, USA*, pp. 111–125. IEEE Computer Society, 2008. doi: 10.1109/SP.2008.33. URL https://doi.org/10.1109/SP.2008.33.

Gabriel Peyré and Marco Cuturi. Computational optimal transport: With applications to data science. *Foundations and Trends® in Machine Learning*, 11(5-6):355–607, 2019. ISSN 1935-8237. doi: 10.1561/2200000073. URL http://dx.doi.org/10.1561/2200000073.

Phillippe Rigollet and Jan-Christian Hütter. High dimensional statistics. *MIT lecture notes for course 18S997*, 2015. URL https://math.mit.edu/~rigollet/PDFs/RigNotes17.pdf.
A Notation

In this article, the term *Fact* will be reserved for results that are directly borrowed from the literature. In contrast, *Lemma*, *Proposition*, *Theorem* and *Corollary* will be used as soon as the result requires some work from the existing literature. $\mathbb{N}$ is the set of natural numbers starting at 0. $\#(S) \in \mathbb{N} \cup \{+\infty\}$ refers to the cardinality of a set $S$. Bold letters will be used for vectors, and their non-bold counterparts with $i \in \mathbb{N} \setminus \{0\}$ as subscript will refer to their $i$-th entry. For instance, $\mathbf{X} = (X_1, \dots, X_n)$. Considering any set $\mathcal{X}$ and $n \in \mathbb{N} \setminus \{0\}$, $d_{\text{ham}}(.,.) : \mathcal{X}^n \times \mathcal{X}^n \to \mathbb{N}$ is the Hamming distance defined as

$$d_{\text{ham}}((X_1, \dots, X_n), (Y_1, \dots, Y_n)) := \sum_{i=1}^{n} 1_{X_i \neq Y_i}.$$

The notation $\Pi(\mathbb{P}_1, \dots, \mathbb{P}_n)$ is used to refer to the set of distributions that have $\mathbb{P}_1, \dots, \mathbb{P}_n$ as their marginals. Any such distribution is called a *coupling* between/of $\mathbb{P}_1, \dots, \mathbb{P}_n$. For two distributions $\mathbb{P}_1, \mathbb{P}_2$, the notation $\mathbb{P}_1 \ll \mathbb{P}_2$ means that $\mathbb{P}_1$ is absolutely continuous with respect to $\mathbb{P}_2$, i.e. that for any $S$ measurable,

$$\mathbb{P}_2(S) = 0 \implies \mathbb{P}_1(S) = 0.$$

For two probability distributions $\mathbb{P}$ and $\mathbb{Q}$ on the same space, the total variation between $\mathbb{P}$ and $\mathbb{Q}$ is

$$\text{TV}(\mathbb{P}, \mathbb{Q}) := \sup_{S \text{ measurable}} \mathbb{P}(S) - \mathbb{Q}(S).$$

Note that it is a symmetric function of $\mathbb{P}$ and $\mathbb{Q}$. For two probability distributions $\mathbb{P}$ and $\mathbb{Q}$ on the same space with $\mathbb{P}$ that is absolutely continuous with respect to $\mathbb{Q}$, the KL divergence between $\mathbb{P}$ and $\mathbb{Q}$ is

$$\text{KL}(\mathbb{P}\|\mathbb{Q}) := \int \ln\left(\frac{d\mathbb{P}}{d\mathbb{Q}}\right) d\mathbb{P}.$$

It is always positive but may be infinite. Furthermore, whenever we have access to a $\sigma$-finite measure $\mu$ such that $\mathbb{Q}$ is absolutely continuous with respect to $\mu$ (for instance $\mu = \mathbb{P} + \mathbb{Q}$), if we note $\pi_{\mathbb{P}}$ and $\pi_{\mathbb{Q}}$ the Radon-Nikodym densities of $\mathbb{P}$ and $\mathbb{Q}$ respectively with respect to $\mu$, then

$$\text{KL}(\mathbb{P}\|\mathbb{Q}) = \int \ln\left(\frac{\pi_{\mathbb{P}}}{\pi_{\mathbb{Q}}}\right) \pi_{\mathbb{P}} d\mu.$$

For two probability distributions $\mathbb{P}$ and $\mathbb{Q}$ on the same space with $\mathbb{P}$ that is absolutely continuous with respect to $\mathbb{Q}$, and $\alpha \in [1, +\infty)$, the R\'enyi divergence of level $\alpha$ between $\mathbb{P}$ and $\mathbb{Q}$ is $D_{\alpha}(\mathbb{P}\|\mathbb{Q}) := \text{KL}(\mathbb{P}\|\mathbb{Q})$ if $\alpha = 1$ or

$$D_{\alpha}(\mathbb{P}\|\mathbb{Q}) := \frac{1}{\alpha-1} \ln \int \left(\frac{d\mathbb{P}}{d\mathbb{Q}}\right)^{\alpha-1} d\mathbb{Q}$$

when $\alpha > 1$. Furthermore, whenever we have access to a $\sigma$-finite measure $\mu$ such that $\mathbb{Q}$ is absolutely continuous with respect to $\mu$ (for instance $\mu = \mathbb{P} + \mathbb{Q}$), if we note $\pi_{\mathbb{P}}$ and $\pi_{\mathbb{Q}}$ the Radon-Nikodym densities of $\mathbb{P}$ and $\mathbb{Q}$ respectively with respect to $\mu$,

$$D_{\alpha}(\mathbb{P}\|\mathbb{Q}) = \frac{1}{\alpha-1} \ln \int \left(\frac{\pi_{\mathbb{P}}}{\pi_{\mathbb{Q}}}\right)^{\alpha-1} \pi_{\mathbb{Q}} d\mu$$

when $\alpha > 1$. For brevity of notations, when applied to random variables, information theoretic quantities such as $\text{TV}(.,.)$, $\text{KL}(.,.)$, $\dots$ are to be understood as applied to the *probability distributions* of these random variables. For two series $(a_n)_{n \in \mathbb{N}} \in \mathbb{R}^\mathbb{N}$ and $(b_n)_{n \in \mathbb{N}} \in \mathbb{R}^\mathbb{N}$, we use the following notations for asymptotic comparisons:

* $a_n = o(b_n)$ or equivalently $a_n \ll b_n$ when there exists $(c_n)_{n \in \mathbb{N}} \in \mathbb{R}_{+,*}^\mathbb{N}$ such that $c_n \xrightarrow{n \to +\infty} 0$ and

$$\exists n_0 \in \mathbb{N}, \forall n \ge n_0, \quad a_n = c_n b_n.$$
Benjamin I. P. Rubinstein, Peter L. Bartlett, Ling Huang, and Nina Taft. Learning in a large function space: Privacy-preserving mechanisms for SVM learning. *J. Priv. Confidentiality*, 4(1), 2012. doi: 10.29012/jpc.v4i1.612. URL https://doi.org/10.29012/jpc.v4i1.612.

Théo Ryffel, Francis R. Bach, and David Pointcheval. Differential privacy guarantees for stochastic gradient langevin dynamics. *CoRR*, abs/2201.11980, 2022. URL https://arxiv.org/abs/2201.11980.

Filippo Santambrogio. *Optimal Transport for Applied Mathematicians*. Birkhäuser Cham/Springer, 2016. doi: 10.1007/978-3-319-20828-2.

Jonathan Scarlett and Volkan Cevher. An introductory guide to fano's inequality with applications in statistical estimation. CoRR, abs/1901.00555, 2019. URL http://arxiv.org/abs/1901.00555.

Adam D. Smith. Privacy-preserving statistical estimation with optimal convergence rates. In Lance Fortnow and Salil P. Vadhan (eds.), *Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011*, pp. 813–822. ACM, 2011. doi: 10.1145/1993636.1993743. URL https://doi.org/10.1145/1993636.1993743.

Latanya Sweeney. Simple demographics often identify people uniquely. *Health (San Francisco)*, 671(2000): 1–34, 2000.

Latanya Sweeney. k-anonymity: A model for protecting privacy. *Int. J. Uncertain. Fuzzi-ness Knowl. Based Syst.*, 10(5):557–570, 2002. doi: 10.1142/S0218488502001648. URL https://doi.org/10.1142/S0218488502001648.

Youming Tao, Yulian Wu, Peng Zhao, and Di Wang. Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera (eds.), *International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event*, volume 151 of *Proceedings of Machine Learning Research*, pp. 1546–1574. PMLR, 2022. URL https://proceedings.mlr.press/v151/tao22a.html.

Abhradeep Guha Thakurta, Andrew H Vyrros, Umesh S Vaishampayan, Gaurav Kapoor, Julien Freudiger, Vivek Rangarajan Sridhar, and Doug Davidson. Learning new words. *Granted US Patents*, 9594741, 2017.

Alexandre B. Tsybakov. *Introduction to Nonparametric Estimation*. Springer series in statistics. Springer, 2009. ISBN 978-0-387-79051-0. doi: 10.1007/b13794. URL https://doi.org/10.1007/b13794.

A. W. Van der Vaart. *Asymptotic Statistics*. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998. doi: 10.1017/CBO9780511802256.

Tim van Erven and Peter Harremoës. Rényi divergence and kullback-leibler divergence. *IEEE Trans. Inf. Theory*, 60(7):3797–3820, 2014. doi: 10.1109/TIT.2014.2320500. URL https://doi.org/10.1109/TIT.2014.2320500.

Isabel Wagner and David Eckhoff. Technical privacy metrics: A systematic survey. *ACM Comput. Surv.*, 51 (3):57:1–57:38, 2018. doi: 10.1145/3168389. URL https://doi.org/10.1145/3168389.

Larry A. Wasserman and Shuheng Zhou. A statistical framework for differential privacy. *Journal of the American Statistical Association*, 105(489):375–389, 2010. doi: 10.1198/jasa.2009 tm08651. URL https://doi.org/10.1198/jasa.2009.tm08651.

Mengmeng Yang, Lingjuan Lyu, Jun Zhao, Tianqing Zhu, and Kwok-Yan Lam. Local differential privacy and its applications: A comprehensive survey. CoRR, abs/2008.03686, 2020. URL https://arxiv.org/abs/2008.03686.
* $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$ 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) . $$
A Notation

In this article, the term *Fact* will be reserved for results that are directly borrowed from the literature. In contrast, *Lemma*, *Proposition*, *Theorem* and *Corollary* will be used as soon as the result requires some work from the existing literature. $\mathbb{N}$ is the set of natural numbers starting at 0. $\#(S) \in \mathbb{N} \cup \{+\infty\}$ refers to the cardinality of a set $S$. Bold letters will be used for vectors, and their non-bold counterparts with $i \in \mathbb{N} \setminus \{0\}$ as subscript will refer to their $i$-th entry. For instance, $\mathbf{X} = (X_1, \dots, X_n)$. Considering any set $\mathcal{X}$ and $n \in \mathbb{N} \setminus \{0\}$, $d_{\text{ham}}(.,.) : \mathcal{X}^n \times \mathcal{X}^n \to \mathbb{N}$ is the Hamming distance defined as

$$d_{\text{ham}}((X_1, \dots, X_n), (Y_1, \dots, Y_n)) := \sum_{i=1}^{n} 1_{X_i \neq Y_i}.$$

The notation $\Pi(\mathbb{P}_1, \dots, \mathbb{P}_n)$ is used to refer to the set of distributions that have $\mathbb{P}_1, \dots, \mathbb{P}_n$ as their marginals. Any such distribution is called a *coupling* between/of $\mathbb{P}_1, \dots, \mathbb{P}_n$. For two distributions $\mathbb{P}_1, \mathbb{P}_2$, the notation $\mathbb{P}_1 \ll \mathbb{P}_2$ means that $\mathbb{P}_1$ is absolutely continuous with respect to $\mathbb{P}_2$, i.e. that for any $S$ measurable,

$$\mathbb{P}_2(S) = 0 \implies \mathbb{P}_1(S) = 0.$$

For two probability distributions $\mathbb{P}$ and $\mathbb{Q}$ on the same space, the total variation between $\mathbb{P}$ and $\mathbb{Q}$ is

$$\text{TV}(\mathbb{P}, \mathbb{Q}) := \sup_{S \text{ measurable}} \mathbb{P}(S) - \mathbb{Q}(S).$$

Note that it is a symmetric function of $\mathbb{P}$ and $\mathbb{Q}$. For two probability distributions $\mathbb{P}$ and $\mathbb{Q}$ on the same space with $\mathbb{P}$ that is absolutely continuous with respect to $\mathbb{Q}$, the KL divergence between $\mathbb{P}$ and $\mathbb{Q}$ is

$$\text{KL}(\mathbb{P}\|\mathbb{Q}) := \int \ln\left(\frac{d\mathbb{P}}{d\mathbb{Q}}\right) d\mathbb{P}.$$

It is always positive but may be infinite. Furthermore, whenever we have access to a $\sigma$-finite measure $\mu$ such that $\mathbb{Q}$ is absolutely continuous with respect to $\mu$ (for instance $\mu = \mathbb{P} + \mathbb{Q}$), if we note $\pi_{\mathbb{P}}$ and $\pi_{\mathbb{Q}}$ the Radon-Nikodym densities of $\mathbb{P}$ and $\mathbb{Q}$ respectively with respect to $\mu$, then

$$\text{KL}(\mathbb{P}\|\mathbb{Q}) = \int \ln\left(\frac{\pi_{\mathbb{P}}}{\pi_{\mathbb{Q}}}\right) \pi_{\mathbb{P}} d\mu.$$

For two probability distributions $\mathbb{P}$ and $\mathbb{Q}$ on the same space with $\mathbb{P}$ that is absolutely continuous with respect to $\mathbb{Q}$, and $\alpha \in [1, +\infty)$, the R\'enyi divergence of level $\alpha$ between $\mathbb{P}$ and $\mathbb{Q}$ is $D_{\alpha}(\mathbb{P}\|\mathbb{Q}) := \text{KL}(\mathbb{P}\|\mathbb{Q})$ if $\alpha = 1$ or

$$D_{\alpha}(\mathbb{P}\|\mathbb{Q}) := \frac{1}{\alpha-1} \ln \int \left(\frac{d\mathbb{P}}{d\mathbb{Q}}\right)^{\alpha-1} d\mathbb{Q}$$

when $\alpha > 1$. Furthermore, whenever we have access to a $\sigma$-finite measure $\mu$ such that $\mathbb{Q}$ is absolutely continuous with respect to $\mu$ (for instance $\mu = \mathbb{P} + \mathbb{Q}$), if we note $\pi_{\mathbb{P}}$ and $\pi_{\mathbb{Q}}$ the Radon-Nikodym densities of $\mathbb{P}$ and $\mathbb{Q}$ respectively with respect to $\mu$,

$$D_{\alpha}(\mathbb{P}\|\mathbb{Q}) = \frac{1}{\alpha-1} \ln \int \left(\frac{\pi_{\mathbb{P}}}{\pi_{\mathbb{Q}}}\right)^{\alpha-1} \pi_{\mathbb{Q}} d\mu$$

when $\alpha > 1$. For brevity of notations, when applied to random variables, information theoretic quantities such as $\text{TV}(.,.)$, $\text{KL}(.,.)$, $\dots$ are to be understood as applied to the *probability distributions* of these random variables. For two series $(a_n)_{n \in \mathbb{N}} \in \mathbb{R}^\mathbb{N}$ and $(b_n)_{n \in \mathbb{N}} \in \mathbb{R}^\mathbb{N}$, we use the following notations for asymptotic comparisons:

* $a_n = o(b_n)$ or equivalently $a_n \ll b_n$ when there exists $(c_n)_{n \in \mathbb{N}} \in \mathbb{R}^\mathbb{N}_{+,*}$ such that $c_n \xrightarrow{n \to +\infty} 0$ and

$$\exists n_0 \in \mathbb{N}, \forall n \ge n_0, \quad a_n = c_n b_n.$$
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} \left( \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M}(\mathbf{X}_1)) \neq 1) + \mathbb{P}_{\mathfrak{M}} (\Psi (\mathfrak{M}(\mathbf{X}_2)) \neq 2) \right) \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*}
$$