On the Statistical Complexity of Estimation and Testing under Privacy Constraints
Authors: Clément Lalanne
Aurélien Garivier
Rémi Gribonval
Venue: Accepted by TMLR ()

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.

Published in Transactions on Machine Learning Research (04/2023)
On the Statistical Complexity of Estimation and Testing un- der Privacy Constraints
Clément Lalanne
clementtalannne@enn--gooo..
Unio. Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedex 07, Prance
Aurélien Garivier
nurelien.-prroeerrreesss-..g..
Unio. Lyon, ENS Lyon, UMPA UMR 5669, 46 allée d'Iaaie, F-69364, Lyon cedex 07
Rémi Gribonval
rema.gribonou/@irria..
Unio. Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedez 07, Prance
Reviewed on OpenReview:
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 statistical test under differential privacy in a plug-and: 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 procoed 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 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 very high. Conversely, for other problems, even a modest level of privacy protection can lead to significant decrease in performance. Finally, demonstrate that the DP-SGLD algorithm, private convex solver, can be employed for maximum likelihood estimation with 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 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 mumerous 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
& Shinaikkv 2008: Sweeney 2000 Wagner & Eckhoff 2018 Sweeney 2002). Differential privacy @work
eet al. 2014) offers a future-proof solution to this problem by ensuring that individuals are protected from the result of an estimation procedure. enables the inference of global statistics on a dataset while bounding each sample's '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 al. 2019 2020; Abadi et al. 2016). Notably, differential privacy is now used in production by the US Consus Bureau (Abowd 2018), Google (Erlingsson et al. 2014), Apple (Thakurta et al. (017)) 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. degrades the utility of an ostimation. To quantify the loss due privacy, many utility bounds are often used (MeSherry & Talwar 20007] McSherry] 2009). When the target of the estimation is not the pointwise evaluation of function on given dataset but rather hidden quantity

---

Published in Transactions on Machine Learning Research (04/2023)
defined "at the scale of the population", i.c., of the underlying data distribution, statistical problems arise
and an important topic is to quantify the utility of private estimators (Dwork & Tei
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 ct al.
2015
Bun et al. 2019 Bun & Steinke 2019
Ben-Fliezer et al. 2022
Part of the privacy literature focuses on lower bounds (Asi & Duchi 2020a bj Farhadi et al. 2022: Tao et al. 2022), i.c 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
"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 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 minimar 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
lbragimov & Has' Minskil, 2013 Bickel & Ritov 1988] Giraud 2021
Devroye
1987: Verdú et al., 1994
Thomas& & Joy 2006 Scarlett& & Cevher 2019 Rigollet & Hütter 2015 Tsybakov 2003 Györfi et al.,
2002)
Under privacy conditions, some work is still to be done the minimax risk, both on lower bounds and on
some matching upper bounds. Our work sits in this line of rescarch.
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 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 anongmized 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 bl a. Barnes et al.] 2020a 2019). The second one is due to Acharya et al. (2021e) 2018). It adapts Le Cam's, 's, Fano's and Assouard's '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 somewhat plug- aaag-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 AAharra et all (2021e) Le 2018) in the specific context of (e, difffrrenti privacy, our contribution improves upon that work by getting quantitative bounds that are both tighter (c.g. by large constants in the exponent) and somewhat frug-and-pp play in that they apply to 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.] (002)). 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 uniform distribution over 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- non-private minimax risk dominates.
Lastly, we show 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 as- sumptions, 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 E N, and a feature space X, x may be viewed as a set of datasets containing n elements from X. We consider a family of probability distributions (Po)aee on X" where θ is equipped with a semi-met [ dg O - R4. Often, for all 0 E θ, Pa p where (pe) is a family of probability distributions on X. This corresponds to the classical statistical setup where we observe
L.e. that positive, symmetric, that satisfies the triangular inequality and de (0, 0) = 0, e
2

---

Published in Transactions on Machine Learning Research (04/2023)
i.dd. random variables. The general setup allows capturing phenomena that not ii.d., for instance Markov processes. Given an estimator 0: x - @ one might look at its uniform risk of estimation over θ for loss function Φ : [0, +o0) + [0, +00) that is non-decreasing and such that (0) = 0 which is
sup / ege x"
The best achievable uniform risk defines what is called the minimar risk
/ 6 ege
Mn ((Po)eEe de, D) == inf sup
(1)
Here, the infimum over 0 is taken among all possible measurable functions of the samples.
When an estimator 0- 0 (X) is to be made public or is to be shared with some untrustworthy agents and when the records of X are sensilive (on a privacy standpoint), the disclosure of Ô may reveal a lot of information about the records of X. Against this background, differential privacy (Dwork et al.) 2006) offers strong privacy guarantees. Given (randomized) mechanism 2I, dom (2I) refers to its domain (i.e. the set of admissible inputs) and codom (2I) refers to its codomain (i.c. the set of admissible outputs). A differentially privale mechanism W1 : x + codom (2It) ensures that limited information can be inferred on the records of X E X" from the sole observation of the output ()).. Given E R4+ and å E [0. 1), randomized mechanism M1 : X - codom (2I) is (c, diifferrnnnt private (or (c,6)-DP) if for all X, Y E X and all measurable S C codom (II) we have
dram Y) 11= = Pan (DI(X) E E) S PoP (DR(Y) E +
Note that diam (--)) denotes the Hammmingg distance on X". 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 mochanisms. 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, seems that all these notions tend 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 privacy, but the results and the proofs can casily be adapted to other definitions
to the (c,d)-differentte that are based on Renyi divergences. Given p E (0, +oc), a randomized mechanism M : X -> codom (W)) is p-zero concentrated differentially private (p-zCDP) if for all X, Y E X",
dham (X, Y) = Da (XI() ()) S pa, vI<a<+o
The Renyi divergence of level a, Da (-]) -), is properly defined in Appendix A There exist links between (c, 8)- DP and p=2CDP. For instance, Bun & Steinke (016 Proposition 3) states that if a mechanism is p>xCDP it is (c,D)-D for a collection of 5)'s that depend on p. In particular, finding minimax lower bounds for pzCDP mechanisms can be done by taking the supremum of lower bounds on (e, 6DP mechanisms. But as we will see later, we can do better directly. Conversely, if mechanism is (c. DP, it is also e² 2/2-zCDP (see Bun & Steinke (2016 Proposition 4)).
In order to factorize the results, will use the abstract formulation that a randomized mechanism M x + θ satisfies a certain condition C rather than fixing the class in which it belongs. We define the private minimar 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)
Mr (c, (Po) de, Φ) == inf sup / Er (#(de 0)) dP (X)
(2)
ME 6e x
Because of their similaritios, we use Mr to refer to both the non-private minimax risk and its private counterpart. With four arguments, M., should be understood as the private minimax risk and when equipped with three arguments it is simply the regular minimax risk.
3

---

Published in Transactions on Machine Learning Research (04/2023)
1.2 Introducing example
As warmuu 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 < P2 be two parameters in (0, 1) and let UI,...,Ue be independent and identically distributed uniform random variables on [0, 1]. The random
variables Z4 (x!1) x E ER², isis n, defined by
.x (U.)))) (o.))))
are independent and identically distributed with marginal distributions Bernoulli B(pr) and B(p2)- In the sequel we note X (x.,,...""""
1,2, U "i....,Un)) Si := [0, (pi p2)/2). and S2 [(p + p2)/2, 1]. Given any (c, O) mechanism 21: [0, 1|" [0, 1] (where 0) to estimate the Bernoulli parameter, the risk satisfies
,...,
sup ex~ (( p) pE[0.1]
(Ex~B(pi)on ((9((X) - p1) + x xx~B(p=) ((9N(X) - p2)²)) /2
Coupling
Luuon
(2I(X(11) - -D1)² LU,. (9)(X(()) - p2)2) 12
(3)
Conditioning
(IDI(X()) - p1)²) + Emn (DI((((3) p2)²) /2
Eu
Egmt
P2 P1
2 Fu
Pax
(D((X())) E S22 + Pon ( E S )) /2.
This is where the DP property yields a lower bound on the second factor as
Eu Eur(e cdham (xx)
P Pan (2)(X(22) S2) + Pan (2)(x(22)) E E:)))
dram (:)20
EU echam (xii)amm((xxx) x(1)) (aan (Dn(X E S2) + Pan (XI(((22) ESI) ))
(4)
= =Eu (e edeam (x(() (x())x()))
x(11))
Jensen -
which overall yiclds the lower bound (Ps (Po-Pi)' nelpp-pp eme A good lower bound on the minimax risk then provided by optimizing over pl and p2. For instance, when n 2 2 c, Pı = and pa = 1/2 + 1 leads to
8
nc
sup Ex~B(p)on ((DI(X) - -p) > 8 (nc)2 pE(0.1]
The idea behind the first inequality in 3 is classical in the minimax literature and is recalled in Section L.3 using the notion of packing. The coupling construction can be generalized and tailored to other settings and has critical impact on the deduced lower bounds, as we present in Section 3 The minoration involving differential privacy is 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 (sce Duchi et al. (2013a) for finding lower bounds M, ((Po) de, D) is to replace the parameter set θ by much "simpler" set O' C θ and to use the trivial lower bound
de, 4) 2 inf sup /
nr
((d)
0 Be@r X
Usually O' is chosen as an Ω- O-packing of θ for some real number Ω > it is a countable family O' (0,, e N.} (0t)en, (and most of the time, including in this article, it is taken to be finite) such that: a) 0, θ for all 6; b) 8. 3 = (0, 0g)) 2 2Ω; and c) there is a well-defined function Warr satisfying
y (8) E arg min de (9,,
121
4

---

Published in Transactions on Machine Learning Research (04/2023)
for each 0 E @. Under such hypotheses, any estimator 0 satisfies
Duchi et al. 2013a
sup / ae x
(dd)()(X), (X) ((2)
sup
Px-Po. (ver (o(X)) # #1)
(5)
iE #())))
The mapping v v : xm - .I...., (0') may be viewed as a test function (that selects the model number) and thus
Mrn (PPoloe de. )) ((2)
inf
sup Px-Po, (V +
(6)
v:x- - (1... (0")) (e()....*(0)))
Finding minimax lower bounds is thus done by finding suitable L-packing of the parameter space and then by providing lower bounds on
inf
sup PX-PE ( (X) *
v:X -1. ((0)) ((e)....(e)))
Two power powerful tools to find such lower bounds come from information theory: Le Cam's lemma (see
Fact [ can be used when O' only contains two elements, while Fano's lemma (see Fact 2 applicable when O' contains N 2 2 elements.
Fact 1 Eieyman-Peearsee & Le Cam's lemma (Rigollet & Hütter 2015 Lemma 5.3)). Let P P2 be two probability distributions measure space E, then
inf max Px~P, (V (X) + W.8 + (1.2) iE(1.2)
inf (1,2)
Px~P: ( (X) +
(8)
1 (1 TV (11
The Total Variation (TV) is rigorously defined in Appendir
A
Fact (Fano's 's lemma Girand 2021 Theorem 3.1)). Let (P (P.).g be a family of probability distributions
on measure space E. For any probability distribution Q on & such that IP; < Q for all i, and for any test function V X + NJ,
PX~P, (X) :E(I....,N)
+
Σ
P Px-P. P. ( (X) + i)
(9)
1 1 1-1
KL (P. Q)
(n(N)
The KL divergence and the absolute continuity (<) are rigorously defined in Appendix Often is set to N DNNP, P..
With the same reasoning used (Duchi et al. 2013a) to establish (5) with O' ((1))e(1.... an l2-aacking of O, we can lower-bound the privale minmax risk:
(C, (Pe)ace de, +) ((?) inf
inf
sup
PX~Po, on (v (2T()) *
(10)
MeE (:codom -1 (1..... (er)) (e())e()))) ((9)
Consequently, finding private minimax lower bounds done analogously to the non-private setting by finding an appropriate Ω2- l-packing and a lower bound on
inf
sup
Px~F,, on (v (X) # +
(11)
Vicodom (R) -1 (e()....
that is independent the mechanism 2R but only depends the privacy condition C.
5

---

Published in Transactions on Machine Learning Research (04/2023)
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(-), O()), (-)) and Ω(-) 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 [1 to a Kantorovich problem (Santambrogio) 2015 Peyré al. 2019) of the form
sup DE...F......PAA Janny se (XI...., Xx) dQ (XI,..... X,)
(12)
Here, 11 (P......, PN) is the set of couplings between the considered distributions and se an admissible similority function depending the nature of the constraint C and the number of hypotheses (Theorem G and Theorem For instance, regarding (c, dddifferrent 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. (021e), 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 X1, x....., XN coming from each instance, well as an 'anchor" dataset A (or alternatively an anchor distribution), differential privacy implies that the probability that the estimator decides X, comes from instance i cannot differ by much from the probability it decides A comes from instance i, provided A and X, are similar. The decoding error probability can thus be lower bounded in terms the maximum distance between A and any of XI..., X..,,,,, averaged over the randommess of XI,...;X, XN, where there is freedom in choosing how to couple this randommess.
Section 3 includes various coupling constructions yielding quantitative lower bounds for the Kantorovich formulation 12 These constructions only depend the number of hypotheses N, the sample size n, the privacy parameters e, o, Ps and information theoretic quantities such the pairwise total variations KT. divergences between the distributions.
We showcase now useful consequences, starting with the case == 2: similarly to Acharya et al. 2021e). we extend Le Cam's 's lemma to the (r, -)diffferenntilll private setting:
Those results will be presented in Section 2 and in Section 3
Theorem (Le Cam for (e, ()D)) If a randomized mechanism M salisfies (c. DDD,, then for any test function v : codom (WI) + [1,2] and any probability distributions P1 and P2 on X we have
max Px~P,, (V (M (X)) #1) max {1 TV (2), (E(1
c1-e- + 2ne (8) 28)
TV (P,, P2)
Furthermore, when P1 10th and P2 p000" are product distributions,
max Px om ( (X)) +) (1.2))
1 (1 - (1 TV (p1, 2ne C8TV
2
The proof can be found in Appendix C The classical lower bound of Le Cam
( allows for a tunable testing
difficulty depending on TV (P,, P2). However, in the regime e, 8 = o(1/n), the private lower bound 2(11:
it becomes arbitrarily hard to distinguish between any pair of distributions.

---

Published in Transactions on Machine Learning Research (04/2023)
For ii.d. observations (P, ") it follows by convexity that for any (c,8)-DP mechanism M2 and test
function V. codom (D > {1
1 (VTTTV(P) - -2 2e-TT (pI,
max Px~P, an (v (D (X)) * 1) 2 2 (E(1,2)
This is to be compared to the state of the art lower bound of Acharya et al.
2021e Theorem 1):
max Px~P,,0 (V (M (X)) * i) 2 2 (0.9c (0enT((PP 106nTV (P1, (pI.P2) :E(1.)
Theorem gives lighter results with better constants, notably thanks to different proof technique avoiding some convexity and concentration inequalities, but also because Acharya et al. (2021e) did not optimize the constants. Indoed, qualitative results and rates convergence do usually not depend on them.
We also prove an equivalent for so-called p-zero concentrated differential privacy (or short p-xCDP), which is, the best of our knowledge, the first successful attempt doing so.
Theorem 2 (Le Cam for p-zCDP). If randomized mechanism 22 satisfies p-2CDP, then for any test function V codom (I + [1....,N] N} and any probabilily distribulions PI and P2 on Xn
2 max { TV
max P Px~P.mm (V/ (MR (X)) + 2 (E(1.)
1 DV (P1, P2))
Furthermore, when P p and P2 P @n
product distributions,
1 (1 P/ (pI. 2
Px-P, (V (M (X)) + iE(1.2
The proof of this result can be found in Appendix As above, any two distributions can no longer be distinguished in the regime p < 1/n². For more than two hypotheses and (e, DDD,, we also get private version of Fano's lemma.
Theorem 3 (Multiple Distributional Tests for (c, ()DD). any family of probability distributions (P:))e((.....)))
If randomized mechanism M satisfies (c,5)-DP,
then for any test function V codom (D + on X and any Q such that P, & Q for all i,
KL (P.1l Q)
max PX-P,. (V (II(X)) + 2 max ie N)
N
Di=1
In(N)
e
+ 2ne
8
2TV (P,, P,, TV (P,, P2))
2
2N2
+ me N
En, IFIV(F..P.)
2TV(P.PP))
18=0 X
In(N)
Furthermore, when P, P1
PN P are product distributions,
(1- -
2TV (pi, Pj)
max Px-P, (V (X)(X) + i) 2 max (E(L...,N)
2N2
TV (p. p;))
2TV (p.. Pj).
-2ne 8
+ TV (pi, P;)
1+ ms
Eij
2TV(p...)
No
[+TV(p(.)g)
18-0 x
1
In(N)

---

Published in Transactions on Machine Learning Research (04/2023)
The proof is given in Appendix C
When dealing with product distributions, the quantity
2TV (pix P2))
Σ
= N
TV (P:.P;)
can roughly be seen as an averaged hamming distance between pairs of marginals. An implication of Theo- rem g is then that
I Px~P. (V (XI( + 18=0 x (1- InttND)
cD) In(N)
max [)
As the bound of Acharya et al.
2021e
Theorem 2)
max Px on (V (X)( + 18=0 x 0.9 x min {1, ie (I,.,N
N 2I0eD
(13)
the lower bound is (11 in the regime D o(In(NV/cc. In particular, both incqualitics are expected yield similar qualitative results for a broad range of applications. However, the quantilative consequences of Theorem 3 can again be orders of magnitude better. Another improvement of our result is that, contrary to previous work, bound allows to handle asymmetric hypotheses. Indeed, prior work is based on uniform upper-bound on the family (TV (p;. Pý)),, 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 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 p-zCDP.
Theorem (Multiple Distributional Tests for p-zCDP). If a randomized mechamism M satisfies p-2CDP, then for any lest function V codom (It) + {1,..., N}, any family of probubility distributions (P:) on X and any such that P, < Q for all i,
1+ 1
KL (P;l EN 1
max Px~P,.on (V (IN(X)) + 2 max i NJ....
In(N)
n² N
2TV(P.FF,) Eis I+TV(P.,E)
In(N)
Furthermore, when PI =p0" ... PN px are product distributions,
max Px~p,.on (V (X) # 1 1+ N Σis KE(D...NN
2TV(EOP))
2TV(p..)) I+TV(paPs)
I+TV(PLP))
In(N)
The proof is to be found in Appendix C This result recovers a recently published result in Kamath el al. 22022, with the advantage again better handling asymetrical 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 ((1/n) for the squared error on the estimation of the parameter of a Bernoulli distribution becomes maxx 1
(meys under e-differential privacy. Furthermore, exhibit new rate in the case of p-zero concentrated differential privacy e max 12 n )):
8

---

Published in Transactions on Machine Learning Research (04/2023)
Gaussian Model. We allow each piece of data to have dimensionality d (the dimension of X).. We again recover that the minimax risk θ o²d (scc Rigollet & Hütter (0015
Corollary 5.13)) becomes
Ω maxx ddd o² (fff)) under e-DP, and prove that it becomes Q max o'd
o'd under p-zCDP.
Uniform model. This example allows us to exhibit a new behavior under privacy. Indeed, we show that the usual minimax risk (+.²) becomes ? [aax( +. (mbje)) under e-DP and
Q [max( I xt)) under p-2CDP, proving systematic degradation of utility due to privacy that in particular does not depend disjunction the rates at which the privacy-tunnng parameters decrease.
Finally, in Section we study the private parametric estimation of distributions that are log-concave with respect to the parameter. In particular, under some mild hypothescs, we exhibit some lower bounds on the minimax risk of estimonio 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)). ). private optimization solver, is near-minimax optimal when used to perform private maximum likelihood estimation in this class of distributions. Here nnaar-iiimmax optimal' means that the ratio between the risk of private est imattonion and the private minimax risk is upper-bounded by quantity that only depends on the regularity of the log- liellikl,,oodd, 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 main theorem, which states that finding lower bounds
11 can be done by solving transport problem (Santambrogio, 2015 Peyré et al.) 2019). In some sense, this view is close to the coupling of AAcaary et al. (2021e) which considers couplings between pairs of marginals and controls the variations the hamming distance compared to its expected value with Markov's inequality. However, the high level view that our result permits allows to obtain numerically sharper results because allows 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. (2021c). Furthermore, key difference is that the theory of Accharya et al. (222ee) 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 becanse it allows to give results that are casier to use when there are more than two hypothescs.
Our analysis is based the notion of similarity functions.
Definition 1. Given a condition C, we say that a similarity function se (X - R is admissible for C if for any mechanism W n - codom (Ml) that satisfies C, for any test function V codom (20) - (1...., N), and for any X XI...., N E X", , the following inequality holds:
N
Σ
P m (V (MI (X,)) #1) se
N
Theorem 5. If randomized mechanism 21 x - codom (M satisfies the privacy condition C, for any N 2 2, if se: (2mNN RR an admissible similarity function for C, for any distributions Pi,..., PN N over x have
max Vicodom (202) (01))110 N) ie iE(l..,,) Px~P,,on (X)) # i)
inf
(14)
sup QETT(F
se (X Xx) dQQ (X....., .,N,)
( (xoyoN
9

---

Published in Transactions on Machine Learning Research (04/2023)
Proof. Given test function v codom (2I) - M) and coupling (P
max .x ( (X)) # 1) 16 16(2...,N)
P Px (v (2I (X)) * t)
y v (201 (X,)) + 1) dQ (X.,...,XX) Xx)
(N22N N
(X se (X Xx) dQ (X1,.... XN)
In particular, under (e, 0)-DP, similarity functions built using technique that we call anchoring which will be introduced in Appendix B.T where the proof of the following theorem is given.
Theorem 6 (Admissible similarity functions for (c,8)-DP). When C is (c, -idfffferettial privacy, the follow- ing approaches yield admissible similarity functions.
Consider any anchor function A (2"DN + X", and define the admissible similarity function as
Global anchoring.
N --1 max: (daum (Xi,A(I..... Xx)))
SC (X
XN)
N
2 max (dham (X,, A (Xi,..., :x)))
Projection anchoring. In particular, for any j N),, consider the projection anchor A5 (XI....,XX, ......,,)>=== X,, and define the corresponding admissible similarity function
N - (dham (x.),)) = max (tham (X,, X;)
sc (X X
N
(c,8)-DP Le Cam matching. When 2, there is a global anchor function yielding the admis- sible similarity function
sc X1, X2) = dham X2)/2) 5 5 ( (x) /27.
Pairwise anchoring.
An admissible similarity function is
N N
se (X
XN)
- (x. 25 [Tddam (X, /2)
2N
O) Fano matching. When 0, admissible similarity function is
1+ N
1= Σ ===1 dham (X,, X,)
8C (X XN)
In(N)
When working under p>CDP, admissible similarity functions are built using classical information thcoretic 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 M... The following result is proved in Appendix B.2
Theorem (Admissible similarity functions for p-zCDP). When C is the p-zero didcentrutddddfffeeettt privacy, the two following quantilies admissibbe similarity functions:
10

---

Published in Transactions on Machine Learning Research (04/2023)
p-zCDP Fano matching
se XX XN) = 1+ N
Di=1 2i=1 dnam (X,, Xz)²
In(N)
p>CCDP Le Cam matching When N =2
1 (1 (1-Vp/2dam (X1, X2)
sc (X x2) == 2
Note that similarity functions can also be easily built for the more general notion of (5. concentrated differential privacy by swapping the group privacy property for its correct variant (see Bun & Steinke (2016)).
We do not include the results about (S, cooneetrtal different ial in this article because our objective is more illustrate the versatility of our framework rather than to build complete catalogue.
3 Lower Bound via Couplings
The transport problem (2) can be studied either theoretically (Santambrogio 2015 or numerically (Peyré et al.) 2019) in order 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 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
[(X (g (dham (X,,X)))
for coupling Q E II(P....... PN) where g is fixed non-increasing function. Hence, finding reasonably good lower bounds can be achieved by finding 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 X, = X,, dnam (X,, and otherwise, drom (X,, X,) S n. It known (Lindvall 2002) that if Q E II(P,.... Pw),, the disagroement probabilities (i.e. the probability that two marginal random variables are not equal) between the marginals satisfy
Vi,j, TV (P,, s ((x.....X))_... (X: xX))
(15)
A natural question is whether this lower bound is achievable by a coupling simullaneously for all pairs of marginals. When there are only two marginals (i.e. 2), classical construction (see Lindvall (2002) answers this question positively:
Fact 3 (Maxinal coupling). Let Pi and P2 be two probabilily distributions on X that share the same algebra. There erists coupling 20 (P P2) E ITP),Pp) (which is distribution (Xm73), ) called maximal coupling, such that
AS measurable.
PIXI.K)) (X E EX)
VS measurable, P(XIXX)) (P..P) (X2 E 5) P2(X2
This construction unfortunately does not generically scale to more than two marginals, even though simple examples, couplings can be built that still match the lower bound 15) for any pair of marginals.
Example 1 (Bernoulli optimal coupling). Given P, = =B(p.), 1 1 a family of Bernoulli distributions and U ~ u((01)) 1]) a uniformly distributed variable on [0, 1], the random vector (XI....,X, defined by X; = 1== (U) distribuled according to coupling Q [T(P,..... .N), and for every i,j
P(X; # X,) 1p: py} = TV (B(pi),B(p,))
11

---

Published in Transactions on Machine Learning Research (04/2023)
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 X1 ~ u((),,0)) X2 ~ 1)) and X3 ~ u((1,-111) and let P be a coupling between X2 and X3. We have that,
1xix,, + +xxxXX + +xxxxx 22
and as a consequence on P. P(Xi I X2) # + X1) 22
> TV (x) - TV X3) + +TV (X,
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 factor 2.
Fact 4 (Near optimal coupling of multiple distributions (Angel & Spinka 2019)). ). Let Pi...., Py be N distributions on the same measurable set. There erists a coupling Q E II (Pi,..., PN) such that
2TV (P,, P2)
Vi,j E (L.....,), N}. P(X (X, x,) < + TV (P,,
In the rest of this article, the notation x (PI,... Py) refers to coupling that satisfies this condition. When there are only two distributions, it refers to the construction of Fact 3 This factor 2 is not 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 can be controlled with the following straighforward lemma:
Lemma 1. Let PI,.... ......,Prrr PN be N distributions on x and Q E denote Dig == P(x (X, # X))). We have
Consider S iigj N and
E(Xi...NN>Q (dham (X,, X,), < nAiij
xx)=a dram (x, S n² n
E(x, (x, 2 1 (1 e
Note that Aij directly depends the coupling construction, but that with any of the ones presented above, always have Vi,j. An, s 2TV (PP,, Py).
When the distributions that we are trying to couple are product distributions (i.e. P = p ..... PN = ))²), we can notice that any coupling q E IT (pI...., Pwv) induces a coupling q E (P,, PP)). 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
6m
@ (pf"
&n) n (PI.... pN)
Straightforward computations yield the following lemma.
Lemma 2. Let PP pp" PN PN Sn be N product distributions on X and E M(p..... PN). Consider any < i.j < N and denote 8 = Xx). (X: & X,). We have:
F F(x,,...Xx/ Xx (dnam (x,X,)) ndij
E [x)....xx) dham X,)) n????, + inoig(1 (155))) n² n22r, + nó.
E Xx)age -edeamm (X.1)) = (1 (1 e (88.5)) nndus
2nt confused with the Kronecker symbol.
12

---

Published in Transactions on Machine Learning Research (04/2023)
Note that dig directly depends on the coupling construction, but that with any of the ones presented above (applied to pI....,PN), PN), we always have Vi,j. ô., S 2TV (pr, Pj).
Putting the pieces together. Each of the coupling constructions presented above has its own merits and can be used to establish the quantitalive lower-bounds establishing Theorem | Theorem 2 Theorem 3 and Theorem (see details in Appendix C as well as the fully worked-out examples given at the end of the introduction (sce details in Appendix D including a discussion on different regimes where privacy induces an estimation overhead).
beyond the i...d. structure? Note that the techniques presented in this article can be used in non i.... setups as well, by emmlating the structure of the probability space in the coupling construction. For instance, consider an m x m stochastic matrix K; the kernel of Markov chain kernel К on m states m.). The column i represents the vector P(.li) 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 stales. The objective to build a differentially privale test of K based on the observation (Xt)sstn+t,, X2 E {l,...,m} of a trajectory of length n + 1. Let us illustrate this with n 2: consider the two kernels K
Discussion:
(111 [1.2 and their associated Markov [k1, k1.2) and L - -(k) (2,1 12,2/"
1221 k2.2
chains Mx and ML. We build a Markov kernel Q on the set of pairs of states of Mx and M,, such that for any zk state of Mx and any σL state of Mt, Q(G..))(<< xI)) is a coupling between K K(IÆk) and [((xz)) Let us take Q((1, 1) (II, = min (11=11 1,,)), Q((2, 2){( xL)) =
22.2). ai - l1 if ki,zx > 11 or otherwise, and (( 1)](<k, x1)) = 1,,,, - 1a, if 1, 11 or otherwise. We consider Mq. the Markov chain that starts with the uniform distribution on the pairs of states of Mr and M,, and has transition kernel Q. We observe that the probability distribution over pairs of sequences of length n + 1 generated by Mq is a coupling between the corresponding distributions over single sequences associated to M1 and M2. 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.).
((K,
By integrating Le Cam matching similarity function (Theorem G and Theorem 7 against this distribution on the pairs of trajectorics, we obtaín the fowling lower-bounds Any cDDP test that trics to discriminate Mx from M,, must have a type or a type 2 error at least equal to { (1 -e "a))"" where a max - 1,,,, | 122, h, | 1). Similarly, any p>CDPP test that tries to discriminate Mr from Mr must have a type 1 or type error at least equal ] - /ppp/)).
When there are more than two Markov chains to test (say N), a similar coupling can be built. by building Markov chain on the N-tuples of states of the different Markov chains. The technicality is that one has to use Fact f instcad 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 XI,...,,,, i.i.d. random variables of distribution p the maximum likelihood estimator has value
{ ((0) (10)
m 110)= = ni _
0M arg max BEe
(16)
where f is the log- liglliiel The parametric model with respect to reference measure is thus
VX, dpe (xxx==e(xxa du
OEO,
where dpe is the Radon-Nikodym density of Po with respect to y and θ is often a closed, convex subset of Rd with nonempty interior. This sctup covers, in particular, exponential families (Van der Vaart 2000) with ((x,0) Tx) In()(0) associated with some statistic T and normalization factor Z(0). This section
13

---

Published in Transactions on Machine Learning Research (04/2023)
first presents 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, may assume that the parametric model is not degenerate in the sense that f satisfies
vO E θ, / (adx(X =0.
(17)
This hypothesis is for instance satisfied in the Gaussian model presented previously. Indeed, in this case VX, +X) satisfied in the broader model of the exponential families (sce Boucheron al. (2019) Théorème 4.10)).
X, 0) 0 and VX, dpw du (X+ dp= (0 X). This hypothesis is more generally da
Under such hypothesis, we have the following lemma which will allow to leverage Proposition [
Lemma 3. If (Po)oce satisfies the property and if is concave and B-smooth in its sccond argument, Ihen
8 |00 0111
v01,02 02 E KL (po, pe.) - 2
Note that the family (Pe)ege directly depends on f. In particular, for the Gaussian Model, 8 = A we recover the classical upper bound on the KL divergence between multivariate normal distributions, which is is fact in this case, an equality.
Proof. Because of concavity in the second argument of f and the fact that it is 8-smooth, we have the following result:
8 20 02l1?
E, fl.8))+ 01) s f(z, 02)
2
As consequence,
f In
dp81
KT. (po, (oo))
dpo,
(f(x,0)) - -(X, (2), dpo, (X)
dlP 0g
Vol(X,01) (02 -01) + 01 02
dpa (X)
B 100 02112 (X) _ 01 02112
B
2
We may apply Proposition 1 with = =3/2 and we obtain that
Mr (p-2CDP, (p) 6m ) || - (l. = max n23p' n3 })
(18)
Under the hypotheses of Proposition I d is big enough, p is small enough and the interior of the parameter space big enough. In particular, this gives us lower bound to compare any private estimator to.
4.2 Private maximum likelihood
In general, 0M, has no closed form formula. Even when it has some, the closed form formula usually does not respect differential privacy.
typically addressod via numerical optimization: instcad of considering its explicit max- imum, provably converging sequence is constructed. This requires some assumptions on the likeliool f. A convenient combination of hepot is that f is X-strongly concave, 3-smoooh and I-Lipschitz in its
The problem 16
14

---

Published in Transactions on Machine Learning Research (04/2023)
second argument: then, the stochastic gradient ascend algorithm converges rapidly to lML (Beck 2017 Ex- ponential families typically obey those requirements with / == supace Amax (Co) and, À == inl infoce Amin (Co) where Cg := Cov (T(X)) and Amin (C") (resp. {max(C)) denotes the smallest (resp. largest) eigenvalue of a matrix C' (sce Boucheron et al. (2019 Théorème 4.10)).
The issue 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 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 obtained under very general hypotheses the objective function, but are based on a pessimistic scenario where 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 hypothescs 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-SGMI. (Algorithm D. For batch B {I,..., n). the batch log-likelihood is defined
1s(0) (B)
Σ S(X:,0)
SEB
For closed convex set O Th refers to the projection onto O.
Data: XI,...,X,, S step sizes (nz)220; batch size m, noise variance o², initial parameter Oo. stopping time K.
for h == =00....; K -1-1 do Sample batch By from XI...., Xn with replacement of size Compute Vlg, (6x) #(B.) Eies, Vof(X,, 0k); Update parameter 0u+1 = To (0x + Vls, (0x) (0,
end
return 0K Algorithm 1: DP-SGML: Differentially Private Stochastic Gradient Maximum Likelihood
A choice of the parameters (70).00 0², 0, and K is suggested by the privacy-utility theorem Fact is a direct corollary Ryffel et al. 2022).
5 which
Fact 5 (Utility and Privacy of Algorithm ] Fixed Step Size). Assume that f is A-strongly concave, 8-smooth and L-Lipschitz in its second argument on θ Consider any p > O, an integer n 2 1, a batch size m and set
2/3 In pmn k: A d
41,
pn?
o² =
e² = Es E (IIVl(((xu)11)
Given collection X of arbitrary samples, consider 2XXX) 0x obtained using DP-SGML with to Ie (N(0, 2 la)) and constant step size r 23. This mechanism satisfies p-zCDP, Moreover, if X is such that the solution ONI. of 16) is the interior of θ then
3dL2
g²
[I - 0x11)= 0
+
n2
2xa
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
E (1(0m)) - 1(0x)) = =0 3dL2
?
4X
15

---

Published in Transactions on Machine Learning Research (04/2023)
Furthermore, by >-strong concavity of
1(0ML) - 1(0x)) VI(OML)(Ox OML)) " 21102 1M
and since MLL is in the interior of θ vi((mL)) o which concludes the proof. The term g² = Es (I)V)s())))))))) is due to the stochastic noise of the batch sampling. Indeed, even though V((OmL) = 0, this is not necessarily the case when working on batches. This term depends on the batch size m and can made arbitrarily small by choosing m large enough.
4.3 About minimax optimality
The quadratic risk of any (private or not) solver Di can be decomposed (by the triangle inequality and since (a + 6)² < 2a² + 26", Ya, 2 0) as:
E (110* - 2 (
E E(1BAAL-
2)(x)11))
(19)
where the expectation is over the draw X and, in the case of private solver, on the intrinsic randomness of MT.
The first term in the right hand side of 19 only depends on the properties of the "ideal" maximum likelihood istimator 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
vn (6" 0aL)) ~ N (0, CT."),
where -y refers to the convergence in distribution, and
E (100 -bxcull)) =0(()) nd
(20)
The second term in 19 depends on the solver, which here can be controlled with Fact 5 the ratio bet ween the error of estimation and the minimax risk which lower-bounded in 18] can be bounded follows:
As a consequence,
E E(10r ))())
Di, (p-ZCDP, (P& """"))) || 11. (1.
[E 1100 0m1l12)) EE 11110MT--200 (1)()
18
d
max
n²Bp"
( n23 E -1001))x 0xall?)
n² n² (11AAL 2m(x))12)
0
In particular, for the fixed step-size (see Fact 5), when OML the interior of θ and when the variance term due to the clipped gradient is negligible (i.e., when be batch size big enough have &² = = [dL the second term is 8 1
px"n"
All in all, the ratio between the risk of DP-SGML for maximum likelihood in exponential faminics when the maximum likelihood estimator is in the interior of the search set is
E E(100 213)
Mr (p-CCDP, (p 6 )ee, || - (l) = 0 (2+
32L A3
DP-SGML optimally captures the variation in the sample size n, in the privacy parameter p. and to some extent, the dimensionality (to some extent bocause even if vanishes in the expressions, L, B and 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 broad class of parametric models.
16

---

Published in Transactions on Machine Learning Research (04/2023)
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-0006)) and Chaire AeQ (ANR-20- CHIA-0020-01). This project was supported in part by the AlsegroAssai ANR project Additionally, we thank the anonymous reviewers for their precions input and suggestions.
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Lya Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on compuler and communications security, pp. 308-310- 2016.
John M Abowd. The census bureau adopts differential privacy. Tn 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 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 raints. IEEE J. Sel. Areas Inf. Theory, 2(1):253 267, 2021a.
Jayadev Acharya, Clément L. Canonne, Prathamesh Mayekar, and Himanshu Tyagi. Information-constranned 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 inter- active 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 multiple random variables. arXiv preprinl arXiv:1903.cm 00632, 2019.
Hilal Asi and John C Duchi. Near instance-optimality in differential privacy. arXie preprint 20Xiv:2005.06330 2020a.
Hilal Asi and John C Duchi. Instanco-optimallty in differential privacy via approximate inverse scnsitivity 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. Comples rendus des séances de I' l'Académie des sciences. Série 1, Mathématique, 2000 1983.
Lars Backstrom, Cynthia Dwork, and Jon Kleinberg. Wherefore art thou r3579x? anonymized social net- works, 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 ISTT, pp. 2704-2708. IEFE, 2019.
Leighton Pate Barnes, Wei-Ning Chen, and Ayfer Ougü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 com- munication constraints via fisher information. J. Mach. Learn. Res., 21:Paper No. 236, 30, 2020b. ISSN 1532-4435.
17

---

Published in Transactions on Machine Learning Research (04/2023)
Björn Bebensee. Local differential privacy: tutorial. arXiv preprint 1rXi::1907.119000 2019.
Amir Beck. First-order methods in oplimization. SIAM, 2017.
Omri Ben-Eliizer, Dan Mikulincer, and Ilias Zadik. Archimedes meets privacy: On privately estimating quantiles in high dimensions under minimal assumptions. arXiv preprinl arXio:2208.07/3: 2022.
Peter Bickel and Yaacov Ritov. Estimating integrated squared density derivatives: sharp best order of convergence estimates. Sankhyā: The Indian Journal of Statisties, 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. 658-658.. Springer, 2016.
Mark Bun and Thomas Steinke. Average-case averages: Private algorithms for smooth sensitivity and mean estimation. Advances in Newral Information Processing Systems, 32, 2019.
Mark Bun, Gautam Kamath, Thomas Steinke, and Steven 7 Wu. Private hypothesis selection. Advances in Neurul Information Processing Systems, 32, 2019.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk mini- mization. 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-14788 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.
llias 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. arXio preprinl arXiv:1712. 01524, 2017.
Trit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Proceedings of the bwenly- second ACM SIGMOD-SIGACT-SICA.. symposium on Principles of database systems, pp. 202 210, 2003.
Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. arXiv preprint 1rXi::1905.02550 2019.
Jinshuo Dong, David Durfee, and Ryan Rogers. Optimal differential privacy composition for exponential mechanisms. 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. 02205,, 2020.
John C Duchi, Michael 1 Jordan, and Martin J Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Poundalions of Computer Science, pp. 429 438. IEEE, 2013a.
John C Duchi, Michael Jordan, and Martin Wainwright. Local privacy, data processing inequalities, and minimax rates. Xix preprint 1rXio:1300.338 2013b.
18

---

Published in Transactions on Machine Learning Research (04/2023)
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium Theory of computing, pp- 371-380 2009.
Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arv preprint arXi::1603.0111 2016.
Cymthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 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 com- munications 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 Tha, 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 Securily, pp.
2015.
Christophe Giraud. Introduction hign-dimensional slatislics. Chapman and Hal//CRC 2021.
László Györfi, Michael Kohler, Adam Krzyzak, Harro Walk, et al. A distribulion-ffre theory of nomporumelric regression, volume 1. Springer, 2002.
Rob Hall, Alessandro Rinaldo, and Larry Wasserman. Random differential privacy. arXiv preprint arXiv: 111.:1110660000 2011.
Nils Homer, Szaboles Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill Muchling, John V
Pearson, Dietrich A Stephan, Stanley Nelson, and David Craig. Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density snp genolyping microarrays. PLoS Genet, 4(8):e1000167, 2008.
dl'drr 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. Tn 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-taill 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: 1.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 arXim:2202.00 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 rescarch participants' privacy. Journal of the American Medical Informatics Association, 17(3):322-321
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. TEFE, 2007.
19

---

Published in Transactions on Machine Learning Research (04/2023)
Frank D McSherry. Privacy integrated queries: an extensible platform for In Proceedings of the 2009 ACM SIGMOD International Conference on Management. of dala, pp. 19-3 19-30, 2009.
data analysis.
Πya Mironov. Rényi differential privacy. In 2017 IEFE 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 dc-anonymization of large sparse datasets. In 2008 IEEE Symposium on Securily and Privacy (sp 2008), pp. 111- IEEE, 2008.
Gabriel Peyré, Marco Cuturi, al. Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning, 11(5-6):355-000 607, 2019.
Phillippe Rigollet and Jan-Christian Hütter. High dimensional statistics. Lecture noles for course 18S997, 813(814):46, 2015.
Benjamin IP Rubinstein, Peter Bartlett, Ling Huang, and Nina Taft. Learning in a large function space: Privacy-preserving mechanisms for sym learning. arXiv preprint (xxi:0991..7000 2009.
Théo Ryffel, Francis Bach, and David Pointcheval. Differential privacy guarantees for stochastic gradient langevin dynamics. arXiv preprint XXt:2201.11988) 2022.
Filippo Santambrogio. Optimal transport for applicd mathematicians. Birkä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 wxXi:1901.00555 2019.
Adam Smith. Privacy-preserving statistical estimation with optimal convergence rates. In Proceedings of the sorby-lhird onrual ACM symposium on Theory of computing, pp. 813 822, 2011.
Latanya Sweency. Simple demographics often identify people uniquely. Health (San Francisco), 62102) 1-34, 2000.
Latanya Sweeney. k-anonymity: A model for protecting privacy. International Journal of Uncerlainly, Fuzziness and Knowledge-Baud 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 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), (1):11133) 38, 2018.
20

---

Published in Transactions on Machine Learning Research (04/2023)
Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Stalistical Associalion, 105 -375-38, 2010.
Mengmeng Yang, Lingjuan Lyu, Jun Zhao, Tianqing Zhu, and Kwok- Yan Lam. Local differential privacy and its applications: A comprehensive survey. arXiv preprint ar Xix:20008. 03686, 2020.
21

---

Published in Transactions on Machine Learning Research (04/2023)
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 the result requires some work from the existing literature. N is the set of natural mumbers starting at O. # (S) E U [+oo] refers to the cardinality of a set S. Bold letters will be used for vectors, and their non-bold counterparts with i E NN (0} as subscript will refer to their i-th entry. For instance, X = (X). Considering any set X and n E N {0); dham (..-) : x x X + is the Hamming distance defined as
duam ((X X,), Y,)) Σ 1x
The notation II (P,....,PP Pn) used to refer to the set distributions that have Pi...., ......,,,, Pn as their marginals. Any such distribution called coupling between/ol Pi,.... P.. For two distributions PI, P2, the notation Pi < P2 means that Pj is absolutely continuous with respect to P2, i.e. that for any S measurable,
P2(S) = = Pi(S)= =0 0.
For two probability distributions P and Q on the same space, the total variation between IP and Q is
TV (P, Q)
sup S messurable
P(S) - Q(S).
Note that it is symmetric function of PP and Q. For two probability distributions P and Q on the same space with P that is absolutely continuous with respect to Q, the KI. divergence between P and Q is
KL (PI = / In dP
dP.
dQ
Tt is always positive but may be infinite. Furthermore, whenever we have access to a-finite measure μ such that Q is absolutely continuous with respect to μ (for instance μ P + Q), we note up and To the Radon-Nikodym densities of P and Q respectively with respect to μ, then
KL =
/ In
TTP
xrdp.
For two probability distributions and Q on the same space with IP that is absolutely continuous with respect to Q, and a E [1, +00), the Rényi divergence of level a between and Q is Da (P)) Q) = KL KL (P) if a = 1 or
1 In / D& (PIIQ) = a a-
dP a-1
dQ
dQ
when 1. Furthermore, whenever we have access to a-finite mcasure μ such that Q is absolutely continuous with respect to (for instance μ PP + Q), if we note mp and ma the Radon-Nikodym densities of P and Q respectively with respect to μ.,
Da (FII Q) a- In /
AP
a-1
TodJ
TQ
when a > 1. For brevity of notations, when applied to random variables, information theoretic quantities (.Il.),... are to be understood as applied to the probability distributions of these random variables. For two series (aw)nEN E RRN and (bn)neN E RN, we use the following notations for asymptotic comparisons:
such as TV TV KL (LL
an = o(bx) or equivalently an & bn when there exists (Cx)nEN RNN such that On 7 and
Emo IN,Yn no: On C.bn.
22

---

Published in Transactions on Machine Learning Research (04/2023)
On =Q(b,) when there exist M > 0 and (Cn)NEN E +00+ such that
3oo E EN, 2 no: = Cnb
a, (b,,) when an (bb.)) and b, (((a)-
These notations may be used addition to other notations the problem when there is no ambiguity, for instance when also refers the parameter space later. All the different. parameters are considered as series of n, the sample size. For x E +00) [x] inf ynf y. For a differentiable f - where E a Euclidean space, Vf(x) refers to its gradient at the point When sub-scripted by subset of variables, Vef(z) refers to the gradient at the point of f restricted to the variables in 9. We say that function is L-smooth if it is differentiable and if its gradient in I-Lipschitz. A function f : θ > R where O is convex is said to be X-strongly convex if
y E,, f(x) v)(a)" x) + ++2211 Ily x/|2
Furthermore, a function is said to be X-strongly concave if its opposite X-strongly convex.
Similarity functions
B.1 The case of (c, dddifferrntt privacy
(c, ddddiferreat privacy allows compare conditional distributions for datascts depending on thoir Ham- ming distance. In particular, characlerizing the pushforward of a distribution by private mechanism in not easy task. We overtake that difficulty with technique that call anchoring. Informally, an anchor is a function that, given multiple datasets, decides common dataset to exploit so called group privacy of (c, 8D mechanisms and to give numerically tractable results.
Fact 6 ((e, 8D- Group Privacy). Given R4+ and ô E [0,,), randomized mechanism 2N X codom (2R) is (c, (). difffrrrrreltllllly private, then, for all X, Y E X" and all measurable S C codom (M)), have
Pmn (X)(X) E S) S (c (Y E S) + 8dham (X, Y) (xd))a(Xx))))11 (X,
B.1.1 Global Anchoring
The first type of anchor global anchor, where all the marginal datasets are compared to the same one.
Lemma 4 (Global Anchoring). Consider 8D mechanism M. test function
V codom (It) (I,...,M N), and dalasels X X1...., XN n For any anchor function A (Am)N xm we have
N
Pon (v (X.)) +1)
max; dham (X..)) e - max mmmax dham (X,, A)
N
N
where A is shorthand for A ,
XN).
Proof. By the group privacy property (see Fact G), we have for each E (I....,N)
Pon ( (2T (X.)) # i) 2 edham (X. (v (NT (A)) # - -ddham (X,, A)
23

---

Published in Transactions on Machine Learning Research (04/2023)
As result,
Pan oo V (WI (X:)) fi)
N
ednam (X,,A) Pan (V (DI (A)) # i) e "òchamm (Xi,
N
Cmmx, dham (X..A)
Σ
Pen ( (22 + i)
N
-Ne max dham (x,
N 1
e -max, cham (X...) c max dnam (X;, A)
e
N
where we used E Di=1 Pan (V (M (A)) = = Pen (v (MM (A)) =)) N - to get the last equality.
Remark 1 ((e, 8)-DP Le Cam Matching). When we have to find an anchor betweeen only two datasets, we can design it optimally. Considering any X1, X2 E X", by definition these datasets disagree on enactly dham (X1,Xy entries. The projection anchor = Aç. j E {1,2} consists in anchoring both X1 and X₂ to x, Consequently, we have max (dham (X1, A) dham (X2, A)] = dnam (X X2) If inslead we allocate the anchor A half of the disagreeing components X1 and the other half X2, we get an anchor that satisfies
max {dham (X,, dham (X2 = [dham (x1, /21.
Furthermore, one con check that no anchor can achieve a beller bound. With this new anchor, the direct application of Lemma 4 yields
1 PPon an (V' (MN (X1)) 1) Pan (V (IN (X2)) + #2))
2
(21)
2 - (X,, (2,,,22/21 e 5 [dham (X1, X2) /2]
2
B.1.2 Pairwise Anchoring
The fact that one needs to control the maximum of the hamming distances between single anchor and the marginals might be prohibitive. We give here symeetrized version that only requires to control the hamming distances between the pairs of marginals.
Lemma 5 (Pairwise Anchoring). Under the assumplions of Lemma 4 we have
Pan (T (W (X.)) i
N N
- cTdaam (X (X.x))/21 26 "[[aam (X,, X,) x,)/21)
2N
1=1
Proof. First we observe that
Pon V (Ml) (X))) # i)
N
Σ
(Psn ( (MI (X.)) + + Pox (V (20 (X,)) # 5))
2N
24

---

Published in Transactions on Machine Learning Research (04/2023)
We then consider the two-point anchor defined in Remark [ and get using 21
that for every si,j N,
o0 ( (II (X.)) * + pM (2I (Xj)) # 5)
2 cfcham (X, xx,//2 2e " [dham (X,, Xj) /2].
B.1.3 The special case of (c, OP The following lemma yields bound the KL divergence between the output distributions of an (e, O) mechanism applied to different datasets.
Lemma 6. If a randomized mechanism Wi X" + codom (2T) is (e, OD-P, then
d XR)) dPRR(Y)
YY,Y
S Maam Pan(x) almost surely
aFeer the Radon- Nidoon- density of the distribution of the oulput of the mechanism with impul X, with respect to the distribution of the oulpul of the mechanism with inpul Y. As a consequence,
where dP (P
YX KL (XI()) ()()) S edham (X. Y)
Proof. By the group privacy property (see Fact 6 it is clear that the measurable sets of null measure for P Pon(x) are exactly the measurable sets of mull measure for POR(Y)- In particular, P)R(X) < Pançr) and hence dP anx exists. By group privacy property again for each measurable set S S codom (DI) we have = 2P m())
(8) 2 edduum (X, Y) en (x)
cdow (X.)
pdl
2 c eddamm (X
(int)) (S).
S
So, for each measurable set S,
(9) > = inf p I
Furthermore, p is measurable for the Borel o-algebra of I.. In particular, for any E N., (Iehham(X, (X, Y)c + ,, +o)) is measurable. As consequence,
Vn N., Pan(Y) ([ethanxx + n. +00))
and then
P Pon(Y) (p-1 ((othmn(X,))), PAR(Y) (p-2 (UNEN, [echam + +00
Pam(Y) (UDEN.D" (( ((othmnXX) + +/- +
Σ Fan(Y) (p-1 (( (fetham(X + +00
neN.
which proves that A anr;; thanks to the first remark of the proof. The result about the KL divergence is direct consequence of this inequality.
dP mxx
< (mmmm(X,Y) F almmst- surely, which is also the case P -amost surely,
25

---

Published in Transactions on Machine Learning Research (04/2023)
In particular, this result allows us to apply Fano's lemma in order to obtain similarity function that is based anchoring the conditional distributions rather than the marginals. Lee, given, X,,.... X N X
(...,)))...,; P (xx) are anchored to 1
N ン (x)(X;)
Lemma 7 ((c, O)-D Fano Matching). Let X1, XN E N and v codom (2I). NJ,
1 Σ Pm v
1 N
j=1 dham (x,
(2I
In(N)
Proof. By Fano's lemma (see Fact
1+ N Em=KK KL (Pmxx 1 N Eÿ= Pan(x;))
N Σ Pan V (20 (XI
+1 21
In(N)
By convexity of the KL divergence with respect to its second argument (sec Van Erven & Harremos Theorem 12)), it follows that
2014
1 N
Σ Pm (V (MI (X.)
# N
DE
Ej= KL (Porxx)) PoR(X,))
j=
(22)
In(N)
An application of Lemma concludes the proof.
B.2 The case p-zero concentrated differential privacy
For p-zero concentrated differential privacy, the fact that the definition uses information theoretic quantities makes things easier than with the traditional definition of privacy. Tn particular, the anchoring technique happens implicitly on the distributions rather than on the marginals (similarly as with the (e, O)-D case). Again, the notion of group privacy is central in proofs.
Fact (p-CDDP Group Privacy (Bun & Steinke 2016 Proposition 27)). Let p E R4n, if a randomized mechanism M. : X codom (M) is p-zero concentrated differentially private, then, for any X, Y E X and for any a E o0),
Da (X(())))X((()))))) S pdham (X, Y)² a.
Lemma 8 (p-ZCDP Le Cam Matching). Consider p-zCDP mechanism M. test function v codom (D >> {1,2), and two datasets X1, X2 E x We have.
2
(1 (1- wp/2duam (X1, X2)
Fon T
(21
+
2
2
Proof. By the Neyman-Pearson lemma (see Fact
on (M (M (X.))
TV (1-TVV(D(XX)) (XX(
By Pinsker's lemma (see
Tay bakov
2003
Lemma 2.5)), TV,, S (KL Q) and hence
Pox (V (20) (X:))
# >
1 V KL ( X )1 20 x2)
2
2
1 /D, (2)) )/ x /2
2
26

---

Published in Transactions on Machine Learning Research (04/2023)
Since the Renyi divergence between given pair of distributions Da (-Il.) is non-decreasing in (see Van Er- ven & Harremos
2014 Theorem 3)), we obtain for any a E (1,+0), 8
1 (1
Pon V (2I (X.)) 1)
Da (2n())) 2T(22) /2)
2
2
Eventually, we obtain using group privacy (see Fact that
2
Σ on ( (DI XX, )
2
(1 - pax//22l p (X1, X2))
2
The supremum the right hand side over (1, +oo) yields the result.
We also obtain zero concentrated DP version of the Fano matching method that introduced previously for D)...
Lemma 9 (p-zCDP Fano Matching). Consider p-2CDP mechanism M, test function v == codom (Wl) + (1,..., N), and datasets X1, XI,..., XN E x". We have
N Σ N
1
14 1= j=1 dnam (Xi, Xz)²
Pm (V (M )) # 1) 2012
In(N)
Proof. By the inequality (22) established in the proof of Lemma 7 and using again the fact that D (.Il.) is non-decreasing in (see Van Erven & Harremos (2014 Theorem 3)), as well the group privacy property (soe Fact 7), we obtain that for any E +00),
1 N j=1 KL (Prx(x.) Ps)(X,))
Pon V (I (X.)) #1)21 21
N
In(N)
1+ N E j-11 Da (Pon(x)) Po)(x,))
In(N)
==1 dram (Xi, X,)
In(N)
The supremum of the right-hand side
(1, +00) yields the result.
C Quantitative lower bounds
In this subsection, we finally put the pieces logether order to oblain quantitative lower bounds on 11 This subsection serves a joint proof for Theorem [ Theorem 2 Theorem 3 and Theorem !
Immediate results on the private minimax risk. A usual estimator (i.e. a measurable function of the samples) i may be viewed as randomized and almost surely constant to å (i.e. VX, M[(X) == 0(X) almost surely). As result, it clear that the private minimax risk is always bigger than the non-private one. For distributional tests, the result is not obvious, and give the following general purpose lemma that ensures that Fano's and Le Cam's 's regular inequalities still hold.
Lemma 10. Let (P...E be family of probability distributions on X and let Mr X + codom (WI)
be a randomized mechanism,
inf Wccndom (2))
Σ Pxap.on (V (X(()) +
inf
xxPP (v (X) +
N)
N.N
In particular, the inequalities in Le Cam's 's lemma (see Fact 1 or Fano's 's lemma (see Fact 2 still hold when the lest function V is fed with an input M(X) E codom (2l) instead of an input X E x
27

---

Published in Transactions on Machine Learning Research (04/2023)
Proof. Let V codom (II) - fl....,NY be test function. Then,
N
N
PX-P (V (2I()) # i) dRæ /
xx (V (2)(X)) + =
==1
N
Px~P; ((V W)) (X) + i) dl oz
inf
Σ Px-P; (VV' (X) + i) dmm
vix +12,
N Px~P, (V' x
inf
Σ
Taking the infimumm over v codom (2I) + {I..... N} concludes the proof.
The case of two hypotheses (N 2). At first, we look at the implications of couplings between pairs of distributions. Given P1 and P2 distributions on x", a direct implication of Lemma 10 and of Le Cam's lemma (see Fact [ is that independently on the privacy condition C imposed on 21,
max Px-P..on (V (2N + i) 2 (1 (2), .E(1.2)
This is the first ingredient in the proof of Theorem and Theorem 2 that we now detail.
Proof of Theorem 1 When 2 is (c, 8)-DP, the generic bound of Thcorem apppicdd with the Le Cam matching technique described in Theorem and the coupling x~h (PI,P2) leads
max ox (V (20 (X)) (
(x Xx (.).TT((PPPP))))) (G-Mham(X
EE (x) (dham (X1, X2))
Lemma
II 1
2
(1 -0)))))))) - - E8nA1.
11 (1 e nne + 2nc TV (P1,
(X, # X2) and in the last line we use that 2 = TV PP) with the chosen coupling. Similarly, in the case of product distributions, with the same matching but 8 (Pf) son (n)) we obtain as a consequence of Lemma 2
where in the second line we denote A == Xx)
max Px~P,,0 (V (MI (X)) i)
(E(2.2
1
2 ((1 - (1- TV (p1, p2))" 2ne One-581m 88VV
2
When 21 is pDD,, the generic bound of Theorem 5 applied with the Le Cam matching technique described in Theorem 7 and the coupling (P,1 leads to
Proof of Theorem 2:
max Px~P.,0r (1 (I0 (X)) # 1) (E(1,2
Vpi p/ Xx) (dham (X,, X2))
Lemma 2
(1 Vp/2ônA1.2
2
(1 (PP,
where in the second line we denote 412 == P X.)m (X1 * X2) and in the last line we use that 4 = TV (PI, P2) with the chosen coupling, Similarly, in the case of product distributions, with the same @n
matching but n (p]" ( we obtain as a consequence of Lemma 2
(1 htpppTV pn/p22V((p1.P)))
max PxmP,.o (V (M (X)) # 2 2 (E(2)
28

---

Published in Transactions on Machine Learning Research (04/2023)
The case of arbitrary many hypotheses (N 2 2). implication of Lemma and of Fano's lemma (see Fact 2 is that independently on the privacy condition C imposed on 21, for any Q such that P, < Q for all i
Given Pi...., PN distributions on X", direct
Px-P. (V ()) + i) 21 1+ N)
EN - (L:) In(N)
max
Again, this serves as the first ingredient of the proof of Theorem and Thcorem that we now detail.
Proof of Theorem 3 When Dt is (c, (),D), the generic bound of Theorem 5 applied with the pairwise
anchoring technique described Theorem G and the coupling x (P leads to (since [n/2] S n for each integer 2 0)
max Pxwe,, (V (X)(X) # ii)
N)
N N
-chamm Xy,
XN) (PI....
2N2
1=
-e "Edham (X1
N
N
Lemma
2
(1 - - Ais) - 22 -Onn
2N2
1=1
j=1
2ne 58
2TV 2TV P2)
2N
TV Pg)
1
(X, X,) and in the last line use that A < ITTV with the chosen coupling. Similarly, in the case of product distributions, with the same matching but the product coupling π =8(pp (pf".... ..... ,....,N'')) we oblain as a consequence of Lemma
where in the second line denote A.j 2TV(P.PP))
Px (4) (2I(X)) #
k ().
(1-(1--)
2TV (O;)
2N
+ TV (P:)
2TV (ps.P,)
2ne 5
1 TV (p++ (p..p))
When 8 0, the generic bound of Theorem 5 applied with the Fano matching technique described in
Theorem 6 and the coupling x (PI,,,.... PN)) leads to
max Px (2I(X)) f ig N.
1+ No ΣN En E(x..... ........ XN)= (P) (dham (X,,X,))
N
1+ EN N Ej= mAi
Lemma
N N
R4
2TV(P.P)) j=1 (TT.
21
In
(X, + X,) and in the last line use that Ary < ITTV(P.PF)) with the chosen coupling, Similarly, in the case of product distributions, with the same matching but the coupling म (p
where in the second line denote Aij 2TV(P.PP;)
.....))))
@ we obtain as a consequence of Lemma
N 2TV(p.e,) i= 2j=1 1+TV(pie,)
1
De N2
max PxmP,yo (V (XI(X)) # 2 (E......)
In N
29

---

Published in Transactions on Machine Learning Research (04/2023)
Proof of Theorem 4
When 21 is p-zCDP, the generic bound of Theorem 5 applied with the Fano
matching technique described in Theorem 7 and the coupling x (PI...., IP N leads to
max Px ( (2)) # (E)
1t N E 1= Σド E [ Xx)~aa (PI....Px) (dnam (X,,,))² x,)²)
In N
1+ N 2i=1 D -i==1 n² niAij
Lemma
1
In N
1+ N
N
> P..
1j=1 IFIV(F...))
2
In N
where in the second line we denote A.j := (w).....)))""Pp,....." (X; + Xj) and in the last line we use PT.( that A S (TTV(P,Ps)) with the chosen coupling, Similarly, in the case of product distributions, with the matching but with the product coupling n (pf .....,N''' )) we obtain,
Pxwp.on (V (2)(X)) # (1)
iE N)
1+ N
Ei=1 Σ/= Ex,, Xx) "...."")) (dham (X,, X,)²
N
2
In
1+ P Ei=l EØ=1 (n²6%, + ndd.s))
N
N
Lemma
No
IN
1+
n2p N
No
2i=1
E5=1
N
(2TVVoapp) )² 2TV(p)ps)
14TV(D:P))
2
In
where the sccond line we denote ōG5 == Xw) (X, # Xj) and in the last line we use 2TV(p.P))) with the chosen coupling. that ōag I+TV(p(Pp))
D Examples of applications
This section presents three examples of applications of our lower bounds: The Bernoulli Model, the Gaussian Model and the Uniform Model.
In the first two applications, we show that the rate at which the privacy parameters vary has an importance. Namely, show in both models that if the privacy parameters are too small, the private minimax risk becomes predominant compared to the non-private one, to put it simply, we show that under strong privacy constraints, the performance of estimation has to be degraded.
Furthermore, we also show for the first model that above this threshold, the minimax risk is not degraded by privacy, essentially meaning that we then have privacy "for free".
In contrast, in the last example prove that the minimax risk is systematically degraded by privacy soon consider estimation procedures with increasing privacy requirements in the sense that the privacy parameters decrease as the sample size increases.
D.1 Bernoulli Model
The first application is the estimation of the proportion of a population that satisfies a certain property. is prime example of the application of Le Cam's lemma Fact [ and its private counterparts Theorem T and Theorem 2
When consider the parametric Bernoulli model
(B(O))
θ =0011)
30

---

Published in Transactions on Machine Learning Research (04/2023)
classical and simple estimator for estimating the true parameter 0 from i..d. samples X1. Xn drawn according to B (0*) is via the empirical average
0
X1
71 1=1
The quadratic risk this estimator is
E E(10- 00))
(1 0*)
1/4
n
n
In order to find lower bounds on the minimax risk (with or without privacy constraints), let us investigate
an packing with 0, == 1 and 02:= 3
Regular Minimax Risk. By the master bound (see Tsybakov 2003
6 Le Cam's lemma (Fact and Pinsker's inequality
Lemma 2.5)),
Mw, ((B(0)))) 8n)
AEe -l ......()))))
2 (a/442
1
(1
- TV (B(0)) @n (B(2))))m))
2
a²
2
@m| ((02))0) /2 VkL
32
a²
nKL (B( ((02)) /2
32
where we used the tensorization property of the KL divergence (see Van Erven & Harremos 20114 Theorem 28)). We can observe that when a E [0, 1/2].
KL (B(0)) B(02)) S a².
Indeed, let us note g(x) = 1tz (1 + x) -با In (1 - -xx2 We have that dala) (x) In In(1+z)))((1-2) 2x and since g(0) and - In(1 + x) is 2-Liscchitz on In particular, when E [0, 1/2],
2
[-1/2, we have that g(x) S x, 1/-1/2.1/2]
01
1 - 01
KL ((02)) 01 In
+ (1 01) In
02
1 02
+ a
1 In (1 a)
In
(1 + a)
2
So, with a 1 V as soon as 2 4, we obtain that
Mn, (B(()) 1. -.- (1))
> (1 11-Vno?77
a²
1/160
S2 1
32
which concludes that the non-private minimax rate lower bounded by a quantity of the order of and in particular, that the empirical mean estimator is minimax optimal in term of rates of convergence. Furthermore, any private minimax rate also has to be of the order of at least 1
Minimax Risk with c-Differential Privacy. By the private master lower bound 10) and the product form of Le Cam's lemma for (c, O) (see Theorem combined with the last inequality in Lemma 2 we obtain
Mr, (cDP,, (B(0) on) PEB - ..(())) 2 (a/4)2 (() 2
a
nc (KL
32
a²
V
32
With d(.,)) = =|--.|, see Section 1.3 an Q-packing must satisfy d(0,,9,) > 20, #
31

---

Published in Transactions on Machine Learning Research (04/2023)
where we used again Pinsker's inequality.
So, with a = ne.
L when ne 2 2, we obtain that
1/32 2m (<DDP, (B(0) @n) Jee .-. 2 (nc)² e v1/2
1/80
1
=
(nc)²
(nc)²
p-zero Concentrated Differential Privacy. Similarly, by the product form of Le Cam's lemma for p-zCDP (see Theorem 2 we get with 1 when nvp 2 2,
nyD
a²
Mr, (pzCDP, (B(0) (B(0) 8r) AEe 1l- 1...)
nv P/2TV ptWp///V (B(O1).
32
a
1 n-n ØKL (B((,)) ((02)) /4
32
a²
1/64
1
32
n22p
= Ω
n2p
Matching Upper Bounds. Consider the Laplace mechanism MIX) == Ei= X, + 1 Lap(1). It is an (c, O)-DP estimator X Dwork et al. 2014) and its quadratic risk is [
ne
(nc) Likewise, the Gaussian
mechanism 2n(X) = Em= X; + 2 (), is p>xCDP (Bun & Steinke 2016 and its one is 0 0 + ++1p)) 22))) Combined with the lower bounds established so far and with Lemma 10 this allows conclude that fact
1 2n, (DDP,, (B(0) (0)) oeo - 1.0) - max n (ne)² ))
and that this optimal rate is achieved with the Laplace mechanism, while
1 (n n2p 1)
Ny, (D2CDP, (B(0)**) **) Be . (.())) = max
which is an optimal rate achieved by the Gaussian mechanism.
The Cost of Privacy. An interesting observation for both definitions of privacy is that there exist regimes (e < V or p p 1/n) for which the minimax rate convergence degraded compared to the non private one. In other words, privacy has an unavoidable cost on utility, no matter the mechanism used. Conversely, the order of magnitude of the minimax risk is not degraded otherwise.
D.2 Gaussian Model
The second application is the estimation of the unknown mean 0* E Rd of multivariate normally distributed data with fixed covariance matrix I²I,. When consider the paramctric model (N(0, I2)) see O Rd classical and simple estimator for istaiig the mean 0* from i.i.d. samples XI...., Xn is the empirical average 0 = E Xt. The quadratic risk of this estimator is
odd
E 110- - -12)
(23)
If we were to apply Le Cam's lemma Fact | or its private counterparts Theorem | and Theorem 2 the parameter that tunes the dimensionality would not be captured by the resulting minimax lower bounds which would thus be overly optimistic. This example forces us to use Fano's lemın Fact 2 or its private counterparts Theorem 3 or Theorem in order have chance to capture this phenomenon.
The total variation that appears in Fano's incquality is controlled via Pinsker's incquality in terms of Kullback-Leibler divergence, which in the case of isotropic Gaussians is known to be proportional to the squared Euclidean distance.
v0 02 E O, KL (W(0,, o² o21)) |00 -0
(24)
2o
32

---

Published in Transactions on Machine Learning Research (04/2023)
This enables the use of packing results for the Euclidean norm, and minimax bounds valid in the more general case where the KL, divergence is controlled by the Fuclidean norm between parameters.
Packing Choice. In high dimension, the packing is chosen with exponential number of hypotheses. A good way to obtain well-spread points is to use Varshamov Gilbert's theorem
Fact 8 Beaahamov-Gilbeere theorem (Rigollet & Hütter 2013 Lemma 5.12)). For any Ç (0. 2)) and for every dimension d there erist. 2 E and WT W1,.... WN {0, 1]a such that,
2 - )-aa
i i 7 dham (w,, wy) 2
Minimax Lower Bounds, We obtain the following minimax lower bounds that we factorized in single result:
Proposition 1. Let (poloee be a family of probability distributions on the same measurable space and θ be subset of Bd with d 2 66 that contains a ball of radius for the euclidean distance. Assume that y 0 is such that
v0,,02 E KL (Po.lll po.) S 02 0 111
(25)
Then we have the following results on the minimax: rates:
min
Mn, (p) lEO - (1..
Val GAyNY
12
32
117
leee -e- .1..--11.(.)) max min
To (va) 64,a7)
min
Ja
Vi' 64 Van
Wr, (DD,, (p) 60m
32
Ω max { d d2
))
(ny' (nc)2y
Mn, (ozCDD, (p
Jeco - (1.1)))))))
max (min
))² 2
Va 64:o7
.iiin
Co Va 24
= (max {
d d mmmm))
32
my
when p < 1. Note that all the asymptotic expressions are taken when ro > CVd for a positive constant C' i.e. when the parameter space is not "too small'.
Note that the constraint d 2 66 can be relaxed to smaller constants by changing the Ç in the application of Beshhamov-Gilberte thoorem at the cost of changing the constants the minimax lower bounds. Likewise, the constraint p can be replaced by p < M for any positive constant M at the cost again of worse constants. Since aim to this result. in high dimension and with high privacy, those hypotheses are natural in order to simplify the expressions. Before giving the proof, discuss some practical consequences.
The Cost of Privacy. For Gaussians, by 23 and Proposition
with 7 - (cf (4 the non-private
minimax risk is
Mn, ((N(0) (((() reO |l - -1. = o
hence Proposition shows that there a degradation the private minimax rate over the non-private minimax rate in the regime < V when working under eDD.. Note that this shift in regime depends on the dimensionality. For p-2CDP, the minimax rate of convergence is degraded as soon as p < 1. Comparod to c-DP, the rate at which we observe a degradation does not depend on the dimension d. We study an upper bound in Section! 4
33

---

when Published in Transactions on Machine Learning Research (04/2023)
Proof of Proposition Without loss of generality, let suppose that 0 is the center of the ball of radius (without loss of generality because are going to work neighborhood of 0 but it can be translated to any point). Varshamov Gilbert's theorem (Fact 8 with Ç = allows us to consider N and wi...., WN and to define a packing of the form 81 = aw.,,... 8N = own such that
add
i
10: 0 S a²d.
This yields an f = aVd/4-packing with respect to the Euclidean metric. Since in the interior of θ all the 0,'s are in O provided that small enough. By the (non-private) master lower bound 6 and Fano's lemma (Fact 2
Mr, ((p) 8n) BEB
(1.1
1 1 N
E, KL
N Σ, Pē, In N
Pe.
En
(uvd/4)2.
Jensen's inequality
(1
1 1+ No
Eis KL
Po;
Tn En
Pe;
(ava/4)2.
In N
1+ No Eis nKL (pa, pe.))
(aVa//4)
N
and
+ No Eis n7|10: - 0,,1²
16
IN
ad
+ nyaad
d/32
where in the last line used that N 2 d/32 and d 2 66 leads to
110, 0 s a²d. With min (Va (dv
min
To Va
2R, (Pp 80
Dee 000 - (1.)))
64,m0
Ω
32
For <-DP and p=CDP, the first term in the max expressed in Proposition 1 is direct consequence of the above bound and of Lemma I0 so now concentrate the other term By the private master lower bound (10) and Fano's lemma for product distributions and (c, O) (see Theorem arguments as above show that
add
1 2nd Ei, TV (po,, (pu..o,)) vo,) )
M. (cDDP, (p. (0 Aee .l. - (+))
.1.....11111.))))) > 16
N
In
ad
1 1 N
2nc
Eig y KL (Po, ll (oo,) /2
1 -
16
In N
ad
2nc 1 N² Nn
Ei, vr/2/10: - 03
1
16
add
2nea / /7/2vd
16
d/32
34

---

Published in Transactions on Machine Learning Research (04/2023)
Again, setting a = min
ra Vdl
642 22ne
dd when d 2 66 allows to conclude that
Nn, (D,,((p) see Il -1. min
Za va
642 2err/
32
df
Ω
(nE)
Similarly, by Fano's lemma for product distributions and p-zCDP (see Theorem
Mr, (-zCDP, (p@ AE - -.. (1.
a²d
1 + tn²
Ei.s 2n TV (pe,, (o.) + TV (poo, pe, )²
No
16
ln
ad
+ N
An
Ei, i.j
KL
(po, pe,) 12 + KL (Ioo pe,) /2
3n
1
16
In
add
1 +
tn p Σ
7/22100 0yll + >110: - 00,11//2
1
N
i.j
2n
16
N
ad d
1 + 22v2npa / 7d + 2n pra d)
16
d/32
and setting min
"/ 6122vEn//p5
when 2 66 concludes that (because P S 1)
min va 21"2//2n/p7
Mr (pzCDP, (p 8m
Rge - -1-1 (1))
32
d n2pp
Ω
D.3 Support of Uniform Distributions
For the last example, we chose investigate statistical problem that has a non-private minimax rale faster than We consider the parametric model
(po == u{(0 01))
θ -0,
To exploit Le Cam's lemma we will need to control the total variation between two distributions. In this &n model, it can be done explicitly. The total variation between Po,
and p En can be computed as
TV (P& P2 = ff
10.11" min (T0O), pp
-1-
min (01, 62)
"
max (01, 02,
Non-Private Minimax Risk. By the (non-private) master lower bound 6 and Le Cam's lemma (Fact) 1 applied the In -packin 01 = and 02 = 1, we have
MR, (u(((o) 0) oN) AEO - ...))))))) 2
8n =
nz
where we used that 1- TV (P&, p Sn (1- 1)"d e1_ Furthermore, now show, the estimator max X achieves this rate of convergence when X X, ~ 4((0,0)) are independent. Indeed, for any E [0, 0*),
t
(max X < = 11= P X < =
g
35

---

Published in Transactions on Machine Learning Research (04/2023)
Hence, max X has density Tmax X with respect to the Lebesgue measure where
nt" gun
AE R, Tmax x (t) (1)
so that
dt n
E(max X)
Tt + 0"
On"
0-
nt=-1>
n²
V(max X)
12
dl [E(max X]]2 = 0²2
n2
(n + 1)2
By the bias-variance tradeoff, the quadratic risk of max is thus O non-private minimax rate of convergence is θ (11=) and that max achieves this minimax rate convergence.
6-2 n²
In particular, this proves that the
Minimax Risk with e-Differential Privacy. By the private master lower bound 10 and the product form of Le Cam's private lemma for e-PP on product distributions (see Theorem with å 0) with the 2ar -pccking 81 1 I. and 02 1 we have when ne
Mr, (e-DP, (u((0, 0)0 rEe -..(())) 8(ne)²
Ω
(nE)²
In particular, the rate is degraded compared to the non-private one as soon as c is decreasing.
Minimax Risk with p-zero Concentrated Differential Privacy. Similarly, using the product form of Le Cam's private lemma for p-zCDP on product distributions (see Theorem 2 and the 2nv/p" -packing
01 = 1 myo and 02 1 gives that when n 1,
2n, (-zCDD, (4( ree . (.))))
v2 8n
Ω
n22p
In particular, the rate is degraded compared to the non-private one soon as p is decreasing.
This example shows that when the stochastic noise due to sampling shrinks too fast (here max X has quadratic risk O(1nn²)), then the noise due to privacy becomes predominant. In particular, we do not observe a distinction on the rate at which or p tends to order the conclude degradation of the minimax risk. It is systematically degraded.
36


Reviews:
[{"review_id": "2J46832N9i", "reviewer": "Reviewer_9Gwj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper provides a unification of lower bound techniques that have been scattered around in the private statistical estimation literature using couplings and reformulating the lower bound as a transport problem.\n2. Results are also given for the case when the database doesn't necessarily come from a product joint distribution, which could be more widely applicable than the problems which enforce product distributions.\n\nWeaknesses:\n1. The notation M satisfying condition C is unnecessary and only adds to confusion, it can easily be denoted as the estimator lying in a set.\n2. On Page 7, a lot of emphasis is given comparing the constants in the lower bounds against the paper Acharya et al. This emphasis is unnecessary and misleading, constants in lower bounds don't matter as much and the results of Acharya et al. are clearly not optimized for constants.\n3. The applications of the lower bounds as presented don't prove any new bounds, which leads one to question the necessity of this unification of coupling results as a transport problem. In particular, while I do not myself know the exact references for some of the derived lower bounds in the past literature, they seem to be derivable, albeit using the same coupling based arguments. It would be interesting to see if the authors can prove a lower bound on a problem where the results are not known or perhaps not even tackled by the privacy community. An example of this could be moving beyond the i.i.d. assumption in building a dataset which leads to product distributions to the setting of data with some form of structured dependence.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies methods of finding minimax lower bounds when the estimators are constrained to be differentially private (pure, approximate and concentrated DP). They generalize the previous techniques of finding a coupling between distributions and using the definition of differential privacy to give suitable lower bounds using modifications of Le Cam's and Fano's method. They illustrate how these methods can be used to give lower bounds for three parameter estimation problems and show the tightness of the bounds provided by DP-SGLD for maximum likelihood estimation problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses above.\nIn particular, points 1 and 2 are minor, but I would love to know thoughts of the authors on point 3.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2yy6JIFu7c", "reviewer": "Reviewer_hRYr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The results in this paper give tighter lower bounds than previous work.\n2. The authors nicely give some high-level idea about the methods and honestly cite related work.\n3. The paper offers new insights of using transport method into the distributional test under differential privacy to solve minimax lower bound problem.\n\nWeaknesses:\n1. The authors mentioned local DP model in introduction. So how about the Le Cam and Fano inequalities under local DP by using the methods in the paper?\n2. The authors give results in the case of product distributions such as in Theorem 1. But they only give examples of i.i.d data in  Bernoulli, Gaussian and Uniform models, and also in DP-SGLD. How about the example of non-i.i.d data?\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper makes several contributions in the area of statistical inference under privacy constraints. Some of the key contributions of the paper are:\n1.\tThe paper provides minimax lower bounds on the statistical complexity of estimation and testing under differential privacy constraints, which characterize the fundamental trade-off between privacy and accuracy in statistical inference.\n2.\tThe paper proposes a new approach for characterizing the power of distributional tests under differential privacy, based on solving a transport problem. The authors derive Le Cam-type and Fano-type inequalities for both regular and divergence-based definitions of differential privacy.\n3.\tThe paper illustrates the results with three worked-out examples, Bernoulli, Gaussian and Uniform models, highlighting the impact of problem class on the degradation of utility due to privacy.\n4.\tThe paper shows that the known privacy guarantees of DP-SGLD, a private convex solver, lead to an algorithm that is near-minimax optimal for a broad class of parametric estimation procedures, including exponential families.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "Give corresponding version of the results under LDP or the discussion.", "broader_impact_concerns": "no", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dTTRwI6lp2", "reviewer": "Reviewer_BEaX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper proves new lower bounds for zCDP using Le Cam and Fano, analogous to the bounds for approximate DP, which is nice. The exposition is also clear and I like the common underlying principle presented in Section 2 (e.g., Theorem 7 is nice). So I think there is sufficient value in the paper to meet the TMLR bar.\n\nThat said, I think the paper can be significantly improved. As noted by the authors, the problem and tools are very similar to those studied by Acharya et al. As also pointed out by the authors, the contribution that sets the two apart is that the present paper presents a general, “plug-and-play” approach, which allows instantiating the results for zCDP, and also the new results achieve better constants for approximate DP. Personally, I think the first contribution is worth a publication; the second one feels more incremental. One reason is that the paper aims to provide abstract theoretical characterizations (e.g. if one runs a real algorithm where an improvement in constants matters that makes more sense to me).  The other reason is that the coupling approach doesn’t sound that orthogonal to the approach of Acharya et al. My other main comment is that the writing is in general too verbose and it tries to cover too much at the expense of concision and clarity.\n\nOverall, given all of the mentioned considerations, my suggestion is the following. For the main contribution, focus on the general coupling principle and lower bounds for zCDP. I would briefly mention the main takeaways from the results for approximate DP in the text and defer the formal statements and details to the appendix. For example, I would move Theorem 1, Theorem 3, Theorem 6, etc to the appendix. If you explain in the text early on what the main improvements are relative to Acharya et al., it will be easy to for the reader to get the point without having to go through a long list of case-by-case analyses. Currently the main body of the paper is 28 pages which is quite long for the amount of truly novel content in my opinion, so I think an appendix focusing on approximate DP would help with this. (For example, Section 5, which has new results for private maximum likelihood estimation, only starts on page 25, and it would be a shame for this to get lost.) I could be convinced otherwise—that the results for approximate DP are equally significant standalone results—by the other reviewers or the authors. I would be happy to hear if I’m misunderstanding some subtlety about the relationship to existing work.\n\n\nMinor comments:\n- In abstract, “whereas for other problem” -> “whereas for other problems”\n- In abstract, “parametters” -> “parameters”\n- The way you use the word “hypotheses” clashes with the standard learning-theory way of using hypotheses. I’d avoid using the word if possible.\n- On page 4, taylored -> tailored\n- On page 5, the paragraph explaining how “Facts” are used is distracting and unnecessary. For almost all of them you add a reference from prior work directly in the Fact environment. You can add references for all of them and there won’t be a misunderstanding about the use of Fact environments.\n- On page 6, allow -> allows", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies minimax lower bounds for differentially private (DP) estimation. It proves Le Cam- and Fano-type inequalities for approximate differential privacy and zero-concentrated differential privacy (zCDP). The proofs rely on a general coupling principle that could be used toward other related analyses. The paper also shows that DP-SGLD gives a near-minimax-optimal algorithm for maximum likelihood estimation (for a broad class of settings).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above for suggested changes. The suggestions are not critical to securing my recommendation for acceptance but I feel quite strongly that the presentation can be improved by moving some less novel results to the appendix.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All of the reviewers felt that the two criteria for acceptance to TMLR are met, and hence this paper is recommended to be accepted. The reviewers have made useful suggestions to help improve the presentation of the paper. The authors are highly encouraged to incorporate them in the final version of the paper.
Decision: Accept (poster)