About the Cost of Central Privacy in Density Estimation
Authors: Clément Lalanne
Aurélien Garivier
Rémi Gribonval
Venue: Accepted by TMLR ()

Abstract: We study non-parametric density estimation for densities in Lipschitz and Sobolev spaces, and under central privacy. In particular, we investigate regimes where the privacy budget is not supposed to be constant. We consider the classical definition of central differential privacy, but also the more recent notion of central concentrated differential privacy. We recover the result of Barber & Duchi (2014) stating that histogram estimators are optimal against Lipschitz distributions for the L2 risk and, under regular differential privacy, we extend it to other norms and notions of privacy. Then, we investigate higher degrees of smoothness, drawing two conclusions: First, and contrary to what happens with constant privacy budget (Wasserman & Zhou, 2010), there are regimes where imposing privacy degrades the regular minimax risk of estimation on Sobolev densities. Second, so-called projection estimators are near-optimal against the same classes of densities in this new setup with pure differential privacy, but contrary to the constant privacy budget case, it comes at the cost of relaxation. With zero concentrated differential privacy, there is no need for relaxation, and we prove that the estimation is optimal.

Published in Transactions on Machine Learning Research (08/2023)
About the Cost of Central Privacy in Density Estimation
Clément Lalanne
demment.ddannccSenns-lp...
Unio. Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69842, Lyon Cedex 07, Pronce
Aurélien Garivier
currelen..porriier/eessss......
Univ. Lyon, ENS Lyon, UMPA UMR 5669, 46 allée d'Italie, F-69964, Lyon cedex 07
Rémi Gribonval
remi.grbonnuldiirii..f
Unio. Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedez 07, Prance
Reviewed on OpenReview:
Abstract
We study non annpparametric donsity estimation for densitics in Lipschitz and Sobolev spaces, and under central privacy. In particular, we investigate regimes where the privacy budget be constant. We consider the classical definition of central differential pri- vacy, but also the more recent notion of central concentrated differential privacy. We recover the result of Barber & Duchi (2014) stating that histogram estimators optimal against Lipschitz distributions for the T,² risk and, under regular differential privacy, we extend it to other norms and notions of privacy. Then, we investigate higher degrees of smoothness, drawing two conclusions: First, and contrary to what happens with consland privacy budget Wasserman & Zhou 2010), there are regimes where imposing privacy degrades the regular minimax risk of estimation on Sobolev densities. Socond, so-called projection estimators are near-optimal against the same classes of densities in this new setup with pure differential privacy, but contrary to the constant privacy budget case, it comes the cost of relaxation. With zero concentrated differential privacy, there is need for relaxation, and prove that the estimation is optimal.
not supposed
1 Introduction
The communication of information built on users' data leads to new challenges, and notably privacy concerns.
It is now well documented that the release of various quantities can, without further caution, have disastrous
repercussions (Narayanan & Shmatikov 2006
Backstrom et al. 20077 Fredrikson et al. 2015 Dinur & Nissim
2003
Homer al. 2008 Loukides al.) 2010 Narayanan & Shmatikov 2008 Sweeney 2000 Gonon al.
2023
Wagner & Fckhoff
2018 [weeneyy 2002)_ Tn order to address this issue, differential privacy (DP)
Dwork al. 2006b) has become the gold standard in privacy protection. The idea is to add proper layer
of randommess in order to hide each user's data. It is notably used by the US Census Bureau Abowd
2018
Google (Erlingsson et al.) 2014), Apple (Thakurta et al.] 2017) and Microsoft (Ding et al.
2017 among
many others.
As with other forms of communication or processing constraints [Bannes et al. b a), privacy recently gained a lot of attention from the statistical and theoretical machine learning communities. At this point, the list of interesting publications is far vast to be exhaustive, but here is sample: Wasserman & Zhoul (2010) is the first article to consider problems analogous to the ones presented in this article. It notably studies the problem of nonparametric density estimation, which provide many complements. Duchi et al. (2014 2013 2016); Barber & Duchi (2014); AAharya et al. (2021c); Lalanne et al. (2023a) present general frameworks for deriving minimax lover-bounde under privacy constraints. Many parametric problems have already been studied, notably in Acharya et al. (2018) 2021e): Karwa & Vadhan (2018); Kamath et al.] (2019); Biswas al. (2020); Lalanne al. (2022 2023b): Kamath al. (2022); Singhal (2023). Recently, some important contributions were made. For instance, Asi al. (2023) sharply characterized the equivalence between private estimation and robust estimation with the inverse sensitivity
2019
2020
Acharya et al.

---

Published in Transactions on Machine Learning Research (08/2023)
mechanism (Asi & Duchi 2020a b). and Kamath et al. (2023) detailed the bias-variance-privag trilemma, proving in particular the necessity of adding bias, even on distributions with bounded support, for many private estimation problems.
We address here the problem of privately estimating a probability density, which fits in this line of work. Given X := (x..... Xn) ~ p where P5 refers to a distribution of probability that has a density a with respect to the Lebesgue measure on [0, 1], how to estimate क privately? Technically, what metries or hypothesis should be set on n? What is the cost of privacy? Are the methods known so far optimal? Such are the questions that are investigated in the rest of this article.
1.1 Related work
Non-parametric density estimation has been an important topic of research in statistics for many decades now. Among the vast literature on the topic, let us just mention the important references Györfi et al.
2002 Tsybakov (2009).
Recently, the interest for private statistics has shone a new light on this problem. Remarkable carly con- tributions (Wasserman & Zhou 2010 Hall et al. 2013) adapted histogram estimators, so-called projection estimators and kernel estimators to satisfy the privacy constraint. They conclude that the minimax rate of convergence, n=20/(25+1), where n is the sample size and 8 is the (Sobolev) smoothness of the density, is not affected by centrol privacy (also known global privacy). However, an important implicit hypothesis in this line of work is that 6, the parameter that decides how private the estimation needs to be, is supposed not to depend on the sample size. This hypothesis may seem disputable, and more importantly, it fails to prociscly characterize the tradeoff between utility and privacy.
Indeed, differential privacy gives guarantees on how hard it is to tell if a specific user was part of the dataset. Despite the fact that one could hope to leverage the high number of users in a dataset in order to increase the privacy w.r.t. each user, previous studies (Wasserman & Zhou 2010 Hall et al.) 2013) cover an asymptotic scenario with respect the number of samples n, for fized e. In contrast, our study highlights new behaviors for this problem. For cach sample size, we emphasize the presence of two regimes: when the order of c is larger than some threshold (dependent on n) that we provide, privacy can be obtained with virtually no cost; when is smaller than this threshold, it is the limiting factor for the accuracy of estimation.
To the best of our knowledge, the only piece of work that studies this problem under central privacy when is not supposed constant is Barber& & Duchi (014). They study histogram estimators on Lipschitz distributions for the integrated risk. They conclude that the minimax risk estimation is max (n-2/ + (ne)- showing how small e can be before the minimax risk of estimation is degraded. Our article extends such results to high degrees of smoothness, to other definitions of central differential privacy, and to other risks.
In the literature, there exist other notions of privacy, such as the much stricter notion of local differential privacy. Under this different notion of privacy, the problem of non-parametric densily estimation has already been extensively studied. We here give few useful bibliographic pointers. A remarkable early piece of work Duchi et al. (2016) has brought a nice toolbox for deriving minimax lower bounds under local privacy that has proven to give sharp results for many problems. As a result, the problem of non-parametric density estimation (or its analogous problem of mar-mmraetr regression) has been extensively studied under local privacy. For instance, [utucea et al. (2019) investigates the elbow effect and questions of adaptivity over Besov cllipsoids. [Koll] (2021) and |Schluttenhofer & Johannes (2022) study the density estimation problem al given point. with an emphasis on adaptivity. Universal consistency properties have recently been derived
in Györfi & Kroll (2023). Analogous regression problems have been studied in Berrett et al. (2021) | and in
Györfi & Kroll (2022). Finally, the problem of optimal non-parametric testing has been studied in Lam Weil et al. 2022)).
1.2 Contributions
In this article, we investigate the impact of central privacy when the privacy budget not constant. We treat multiple definitions of central privacy and different levels of smoothness for the densities of interest.
In terms of bouer- we analyze histogram and projection estimators at resolution that captures the impact of the privacy and smoothness parameters. We also prove new lower bounds using the classical
2

---

Published in Transactions on Machine Learning Research (08/2023)
packing method combined with new tools that characterize the testing difficulty under central privacy from Acharya et al. (2021e) e Kamath et al. (2022 Lalanne et al. (2023a]
In particular, for Lipschitz densities and under pure differential privacy, we recover the results of Barber & Duchi (0144) with few complements. We then extend the estimation on this class of distributions to the context. concentrated differential privacy (Bun & Steinke, 2016), a more modern definition of privacy that is compatible with stochastic processes relying on Gaussian noise, We finally investigate higher degrees of smoothness by looking at periodic Sobolev distributions. The main results are summarized in Table 1.2
eDD Equation
p-zCDP Equation
Upper-bone bound:
Upper-bound: })
O Omaxx n 2/3
(nc)-
O (max {nr Theorem
Barber & Duchi 2014 & Theorem 1
Lipschitz
Lower-bounde
Lower-bounds:
Equation (4)
Pointwisc: Q (max (n-2/3 2/3 (nc)
-Pointwise: S2 (max (n-2/3 (n -11))
Theorem 2 & Corollary
Theorem 2 & Corollary
Integrated: S2 max n 2/3 (NE)
-Integrated: ! [max 2/33 (n -1)
Barber & Duchi 2014 & Theorem
Theorem
Upper- bounds:
-Pure DP: O
max n 2017, (ne)
#+3/2
Upper-bound:
Theorem
28 I
max
n 20+1, (n #+1
Periodic Sobolev
-Relaxed: max
28 n
Theorem
Smoothness 8 Equation
9
Section
4.4
Lower-boun:: 28 Ω max
28 (n/p) 28+1
1+1
Lower-bounde 28 x0=T
28 #FT
Theorem
Ω max
(nc)
Theorem
Table 1: Summary of the results
The paper is organized follows. The required notions regarding central differential privacy recalled in Section 2 Histogram estimators and projection estimators respectively studied in Section 3 on Lipschitz densities, and in Section 4 on periodic Sobolev densities. A short conclusion in provided in Section 5
2 Central Differential Privacy
We recall in this section some useful notions of central privacy. Here, X and refer respectively to the sample space and to the sample size.
Given two datasets X = (X1...., "i.....,,),,Y Y (Yı,..., Yn) E X", the Hamming distance between X and is defined as
dram X. Y
1x
1=1
Given e > 0 and 8 E
[0, 1), a randomized mechanism 21 2 + codom (M)) (for codomain or image of M is (e, diffeeferyyyllllyy private (or (c,8)-DP) (Dwork et. al. S C codom (I)):
2006b a if for all X, Y nm and all measurable
dham (X S1
Pon (XI(X) 5) < ef (M(Y)= S) +
(1)
where dham ( denotes the Hamming distance on x
In order to sharply count the privacy of a composition of many Gaussian mechanisms (soc Abadi al. (2016)
privacy is also often characterized in terms of Renyi divergence (Mironov) 2017). Nowadays, seems that
all these notions tend to converge towards the definition of zero concentrated differential privacy (Dwork &

---

Published in Transactions on Machine Learning Research (08/2023)
Rothblum 2016 Bun & Steinke 2016). Given p e (0, +oo), randomized mechanism 21 X - codom (M
is p-zero concentrated differentially private (D=xDDP) if for all X, Y E X",
dham
(X, Y) - =
Da (2I(X) ()())) S pa
(2)
where Da (-11-) denotes the Renyi divergence of level a, defined when as
Da (PII = In
dQ
For more details, we recommend referring to the excellent article van Erven & Harremoës (2014).
There are links between (e, 8)-DP and p-zCDP. For instance, if a mechanism is p-zCDP, then Bun & Steinke 2016 Proposition 3) it is (e, 6)PD) for a collection of (e, 6)'s that depends on p. Conversely, if a mechanism is (c, (),P), then [Bun & Steinke 2016 Proposition 4) it also e//2-2CDP.
Given deterministic function f mapping dataset to quantity in R2, the Laplace mechanism (work ct al. 2006b) and Gaussian mechanism (Bun & Steinke 2016) are two famous ways to turn f into private mechanism. Defining the 4 sensitivity of as
Aif =
sup
[[(X) f(Y)
d ( (X
the Laplace mechanism instantiated with f and e defined as
X - f(X) A C(la),
where C(Ia) refers to a random vector of dimension d with independent components that follow a centered Laplace distribution of parameter 1. Notice that we took the liberty to use the same notation for the random variable and for its distribution. We made this choice for brevity, and because does not really create any ambiguity. It is O) (simply noted e-DP) Dwork et al. 2006a b). Likewise, defining the L sensitivity of as
A2f = X (X, Y)
sup
(xx) -(Y)
the Gaussian mechanism instantiated with f and p > 0 is defined as
Aef N(O 22p
X [(X)
where (0,, Ia) refers to random vector of dimension d with independent components that follow centerod Normal distribution of variance 1. It is p>CDDP (unn & Steinke 2016
A quick word on local privacy. Central privacy comes with the hypothesis of a trusted aggregator (also known a curator, hence the alternative known under the name global privacy) that sees the entire dataset, and builds estimator with it. Only the produced estimator is private. In order to give example, this is like having a datacenter that stores all the information about the users of service, but only outputs privatized statistics.
"trusted curator model' for central privacy, which is also
Local privacy on the other hand does not make that hypothesis. Each piece of data is anonymized locally (on the user's device) and then it is communicated to an aggregator. Any locally private mechanism also centrally private, but the converse is not true.
At first, local privacy can seem more appcaling is indoed a stronger notion of privacy. However, it degrades the utility much more than central privacy. As result, both notions are interesting, and the use of one or the other must be weighted for given problem. This work focuses the central variant.
4

---

Published in Transactions on Machine Learning Research (08/2023)
3 Histogram Estimators and Lipschitz Densities
Histogram estimators approximate densities with a piecewise continuous function by counting the number of points that fall into each bin of a partition of the support. Since those numbers follow binomial distributions, the study of histogram estimators is rather simple. Besides, they are particularly interesting when privacy is required, since the sensitivity of a histogram query is bounded independently of the number bins. They were first studied in this sctup in Wasserman & Zhou (2010). while Barber & Duchi (2014) provided new lower-bounds that did not require constant privacy budget.
As warm-up, this section proposes new derivation of known results in more modern lower-bounding frameworks (Acharya et al. 2021c Kamath et al., 2022 Lalanne et al., 2023a). and then extends these upper-bounds and lower-bounds to the case of zCDP. Furthermore, it also covers the pointwise risk as well as the momitee-norm risk.
Let > be a given bandwidth or binsize. In order to simplify the notation, we suppose without loss of generality that 1/h N \ {0} (if the converse true, simply take h = [1/h]] where [x<] refers to the smallest integer bigger than x). [0, 1] is partitioned in sub-intervals of length h, which called the bins of the histogram. Let Zi...., Z1/h be independent and identically distributed random variables with the same distribution as a random variable Z that is supposed to be centered and to have a finite variance. the (randomized) histogram estimator is defined for x E [0, as
Given a dataset X =
hist (x)
Σ bEbins
16(x)) nh
Σ (X:) ( -/))
We indexed the Z's by a bin instead of an integer without ambiguity. Note that by taking Z almost-surely constant to 0, one recovers the usual (non-private) histogram estimator of a density.
3.1 General utility of histogram estimators
Characterizing the utility of 3 typically requires assumptions on the distribution to estimate. The class of L-Lipschitz densities is defined as
@ { π (10.
(vr [0, (T()) (()) Lly 2
}
[Ja.I]== =
(4)
The following general-purpose lemma gives an upper-bound on the error that the histogram estimator makes on Lipschitz distributions:
Lemma 1 (General utility of 31). There exists Cr. 0, posilive constant. that only depends on L, such that
VZZ) n2
sup sup Ex-ps= grme (Hhist(() m(æo))²) s Cz 12² 1 nh 20 reoLi
The proof is given in Appendix C The term h? corresponds the bias of the estimator. The variance V(2)
term v(2) naa² exhibits two distinct contributions the sampling noise t and the privacy noise лशा.. In particular, the utility of hhist changes depending whether the variance is dominated by the sampling noise or by the privacy noise.
3.2 Privacy and bin size tuning
hhist (X) is simple function of the bin count vector S(X) = =
18 (X:),..,, 1 (X.). In particular, since the bins form partition of [0, 1], changing the value of one of the X's can change the values of at most two components of f(X) by at most 1. Hence, the l and lN sensitivities of f are respectively 2 and /2. By a direct application of the Laplace or Gaussian mechanisms, and by choosing the binsize that minimizes the variance, we obtain the following privacy-utility result.:
1 1,
Thcorem (Privacy and utility of (3) DP casc). Given c <> 0, using *hist with max(n (/2) and Z 2 L(1), where ((1) refers to a random variable following a Laplace distribution of param- eter 1, leads to eDPP procedure. Furthermore, in this case, there erists Cr. > 0, positive constant that.
DP
5

---

Published in Transactions on Machine Learning Research (08/2023)
only depends L, such that
E Ex-po" ahint (x)(a)())( - -x(2)))) s CD max {n (nc)
sup =cc(0.1) ree
sup
anin
Furthermore, given p p> O, using a hist with = max(n 1/3, (n/P) and Z= -VVENO0.) where N/ 1) refers to random variable following a centered Gaussian distribulion of variance 1, leads to a p-zCDP procedure. Furthermore, in this case, there evists Cz. 0, positive constant that only depends on L, such that
sup sup Ex-P?" phin (((oo)) S C2 max {n fn-2/3, (mvP) moE "
Note that this bound uniform in zo, which more general than the integrated upper-bounds presented Barber & Duchi (2014). In particular, by integration on [0, 1], the same bound also holds for the integrated risk (in L norm), which recovers the version of Barber & Duchi 2014).. As expected, the optimal bin size h depends on the sample size and on the parameter (e or p) tuning the privacy. Also note that p>2CDP version may also be obtained by the relations between c-DP and p-zCDP (scc Bun & Steinke (0016)).
3.3 Lower-bounds and minimax optimality
All lower-bounds will be investigated in a minimax sense. Given a class II of admissible densities, a semi- norm 1 || on a space containing the class II, and a non-decreasing positive function & such that o(0) = 0, the minimax risk is defined as
inf sup IE rell
Xx-P=", ((I+(X)) =1))
where C is a condition that must satisfy the estimator (privacy in our case).
General framework. A usual technique for the derivation of minimax lower bounds on the risk uses a
reduction to testing problem (see Tsybakov (2009 ). Indeed, if a family IT' := (mI,-.., Tm C IT of cardinal m is an O-packing of (that is if fj
T k,ll 2 202), then a lower bound is given by
inf sup Ex-Pg- (()((()= Il))
s.b. #ell
(5)
(())
inf s.t.
max P Pxwpor,* (V (f(X)) + (E......m)
@ sendom () (m....m
For more details, Duchi et al. side characterizes the difficulty of discriminating the distributions of the packing by statistical test. Inde- pendently on the condition C, it can be lower-bounded using information-theone
2016 Acharya al. (001c);; Lalanne al. (023a)) The right-hand
results such Le Cam's lemma (Rigollet & Hütter 2015 Lemma 5.3) or Fano's lemma (Giraud) 2021 Theorem 3.1). When C is a local privacy condition, Duchi et al. (2016) provides analogous results that take privacy into account. Recent work (Acharya et al.] 2021e; Kamath et al. 2022: Lalanne el al., 2023a) provides analogous forms for multiple notions of central privacy. When using this technique, finding good lower-bounds on the minimax risk boils down to finding a packing of densities that are far enough from one another without being too easy to discriminate with statistical test.
It is interesting to note that for the considered problem, this technique does not yield satisfying lower-bounds with p-zCDP every time Fano's lemma is involved. Systematically, small order is lost. To circumvent that difficulty, we had to adapt Assouad's technique to the context of p-zCDP. Similar ideas have been used in Duchi et al. (2016) for lower-bounds under local diffcrential privacy and in AAharya et al. (2021c) for regular central differential privacy. To the best of our knowledge, such a technique has never been used in the context of central concentrated differential privacy, and is presented in Appendix D In all the proofs of the lower-bounds, we systematically presented both approaches whenever there is a quantitative difference. This difference could be due to small suboptimalities in Fano's lemma for concentrated differential privacy, simply to the use of suboptimal packing.

---

Published in Transactions on Machine Learning Research (08/2023)
3.3.1 Pointwise lower-bound
The first lower-bound that will be investigated is with respect to the pointwise risk. Pointwise, that is to say given To E [0, IJ, the performance of the estimator á is measured by how well it approximates x at To with the quadratic risk Ex-PP",= ((o) - T (xx)))²). Technically, it the casiest since requires a "packing" of only two elements, which gives the following lower-bound:
Theorem 2 (Pointwise lower-bound). There ewists CL > 0, a positive constant depending only on such that, for any To E [0, there exist no(zo, E N and co(ro. > such that for any n 2 nu, and ony a 2 ca/n
inf sup x (1(())(0)) - -((o)))))~(<)))))) T max { ts. real
2/3 (na)
(6)
where a = when the condition C is the e-DP condition and a vp when C is p-zCDP.
Proof idea. Let 20 E [0, 1]. As explained above, finding a 'good' lower-bound can be done by finding and analyzing a 'good' packing of the parameter space. Namely, in this case, we have to find distributions on [0,1] that have a L-Lipschitz density (w.r.t. Lebesgue's mcasure) such that the densitics are far from one another at zo, but such that it is not extremely easy discriminate them with a statistical test. We propose to use a packing {P,, } of two elements where g is the constant function on [0, (hence Pg is the uniform distribution) and f deviates from by small triangle centered at zp. The two densities are represented in Figure
After analyzing various quantities about these densities, such as their distance at Tus their KL divergences their TV distance, leverage Le Cam-lype results to conclude.
The full proof can be found in Appendix
Additionally, we notice that, when applied to any fixed 20 E [0, 1], Theorem following corollary for the control in infinite norm
2 immediately gives the
Corollary (Infinite norm lower-bound), There erists Cz O, a positive constant depending only on L such that there erist no(L) and co(L) such that for any n Z no, and any a 2 co/n
|I(()) - 113 2 OT. max {n 2/33 (na)
inf sup Ex- #s..t. wEel."
(7)
where a = when the condition C is the c-DP condition and a = vp when C is p-zCDP.
On the optimality and on the cost of privacy. Theorem ! Theorem 2 and Corollary [ give the following general result Under eDP or under p-zCDP, histogram estimators have minimax-optimal rates of convergence against distributions with Lipschitz densities, for the pointwise risk or the risk in infinite norm. In particular, in the low pricacy regime (*large" a:), the usual minimax rate of estimation of n is not degraded. This includes the early observations of Wasserman & Zhou (010 in the case of constant a (e or vP). However, in the high privacy regimes (a < n $), these results prove systematic degradation of the estimation. Those regimes are the same as in Barber & Duchi (014). the metrics on the other hand are different.
3.3.2 Integrated lower-bound
The lower-bound of Theorem 2 is interesting, but its pointwise (or in infinite norm in the case of Corollary 1 nature means that much global information is possibly lost. Instead, one can look at the integrated risk Ex Ex=eer,;1|f(0 (X) Tl2 Given Lemma I and the fact that we work on probability distributions with a compact support, upper-boumding this quantity is straightforward.
The lower-bound for the integrated risk is given by

---

Published in Transactions on Machine Learning Research (08/2023)
Theorem 3 (Integrated lower-bound). There erists CL > 0, positive constont depending only L such Uhat, there exist (I)).) E IN and co(T.) > O such that for any 2 na, and any 2 co/n
sup F =x- . =ll+(x)= - x x122> 2 OT max {"² n1=2) {1-211, (nas, T
inf
* a.t.
where a =e when C is the e-DP condition, and a vp when C is the p-2CDP condition.
Proof idea. If we were to use the same packing (see Figure I as in the proof of Theorem 2 the lower-bounds would not be good. Indeed, moving from the pointwise difference to the 1,2 norm significantly diminishes the distances in the packing, Instead, we will use the same idea of deviating from a constant function by triangles, except that we authorize more than one deviation. More specifically, we consider a packing consisting of densities fw's 's's where the w's are a well-chosen family of {0, (m is fixed in the proof) (Van der
Vaart 1998). Then, for a given w E {0, 10", fw has triangle centered on m+11 iff w; +
We then leverage Fano-type inequalities, and we Assouad's method in order to find the announced lower-bounds.
The full proof is in Appendix
Since the lower-bounds of Theorem 3 match the upper-bounds of Theorem ! we conclude that the corre- sponding estimators are optimal in terms of minimax rate of convergence.
4 Projection Estimators and Periodic Sobolev Densities
The Lipschitz densities considered in Section are general enough to be applicable in many problems. However, this level of generality becomes curse in terms of rate of estimation. Indeed, as we have seen, the optimal rate of estimation is max (n~ 2/3 (n=2/3 (ne)="). To put it into perspective, for many parametric estimation procedures, the optimal rate of convergence usually scales as max (n (ne)))))))) 2021ch. This section studies the estimation of smoother distributions, for different smoothness levels, at the cost of generality. In particular, it establishes that the smoother the distribution class is, the closer the private rate of estimation is to max (n-1, (mc)==² In other words, it means that the more regular the density is supposed to be, the closer we get to the difficulty of parametric estimation.
(2)) (Acharya et al,
When the density of interest π is in (2 1]), it is possible to approximate it by projections. Indeed, ([0, 1]) being a separable Hilbert space, there exists countable orthonormal family (0s) that is Hilbert basis. In particular, if 0g == So.1) Φ then
1,2
Σ
0,00
Let N be a positive integer, Zi...., ZN be independent and identically distributed random variables with the same distribution as centered random variable Z having a finite variance. Given a dataset X = (X1,...;X,, that is also independent of Zi,...; ZN, the (randomized) projection estimator is defined as
proi (X) Σ
8
Ze Φ where 8.- n2 >>>>(()) n
1
(8)
The truncation order N and the random variable Z are tuned later to obtain the desired levels of privacy and utility. (10 1J) has many well known Hilbert bases, hence multiple choices for the family (dx) (o): For instance, orthogonal polynomials, wavelets, or the Fourier basis, are often great choices for projection estimators. Because of the privacy constraint however, it is better to consider a uniformly bounded Hilbert basis Wasserman & Zhou 2010), which is typically not the case with a polynomial or wavelet basis. From now on, this work will focus on the following Fourier basis
Φ1 (z)
Φo (z) v2 sin (2Tkkz)
k
022+1 (x) = V2 cos (2Ttkr)
k 1.
8

---

Published in Transactions on Machine Learning Research (08/2023)
Note that used the upper notation π to refer to the real number 3, 14..., which is not to be mistaken for the lower notation which is reserved for the density of the distribution of interest. This shouldn't introduce any ambiguity since π is only used locally when looking at Fourier coefficients, and is often simply hidden in the constants.
4.1 General utility of projection estimators
By the Parseval formula, the truncation resulting of approximating the density x on finite family of N orthonormal functions induces bias term that accounts for ΣisN+1 0f in the mean square error. Charac- terizing the utility of Aproj requires controlling this term, and this is usually done by imposing that is in Sobolev space. We recall the definition given in Tsybakov (2009): given B ENN) {0} and L > 0, the class 07, of Sobolev densities of parameters 3 and L is defined as
((0-1) is absolutely continuous, fo.11 ( (z(01)² 2 L²
Sob LB
т E (10,11,R4)
SoaJ [ ==
For function f. used the notation f(0) to refer to its derivative of order B. In addition, the class O of periodic Sobolev densities of parameters 3 and L is defined
PSoh LB
= TT Soh Vj E 3 1), =00000)-11),,0000=000)}
(9)
Finally, we recall the following general-purpose lemma Tsybakov 2009 that allows controlling the truncation bias
Fact 1 (Ellipsoid reformulation
Tsybakov 2009 ) A non-negative function with integral 1 belongs to
L
PSob if and only if
28 0
where aj = if j is even and aj j- if odd.
723
In this class, one can characterize the utility of projection estimators with the following lemma:
Lemma 2 (General utility
8
There a constant CT. > O, depending only on L, B, such that
N NV(Z)
S ( - -1122- S C1.99
sup
N28 +
r Pdak
n n
L.J
The proof can be found in Appendix G
4.2 Privacy and bias tuning
The estimator (X) is function of the sums (E)= (X,))... Ei= (x(,)) In particular, it is possible to use Taplace and Gaussian mechanisms on this function in order to obtain privacy. Since the functions |0:| are bounded by /2 for any i, the I sensitivity of this function is 2/2N and its l2 sensitivity is 2/2VN. Applying the Laplace and the Gaussian mechanism and tuning N to optimize the utility of Lemma 2 gives the following result:
Thcorem (Privacy and utility of 8)) Given any c > and truncation order N, using prros with Z 2Nv2 ((1), where L(1) refers to random variable following a Laplace distribution of parameter 1, leods to an c-DP procedure. Moreover, there erists C1,9 > O, a positive constant that only depends on and B, such
that if N is of the order of min (A (nc) 34372
sup E EXPPER tomel proj x) - -x - S Cr.,s max {n Io st HEE L.9
(ne)
Furthermore, given any 0, and truncation order N, using Aproj with Z = 2 N 1), where N( 1) Jo refers random variable following a centered Gaussian distribution. of variance 1, leads to a p-2CDP

---

Published in Transactions on Machine Learning Research (08/2023)
procedure. Moreover, there erists CL,B 0, positive constant that only depends L and 3, such that, if N is of the order of min (n (n/p) गेत
28 Ex || x)- - S CL,S max {ni 2p41, (n/p))
29
sup x 2 1,U
We now discuss these guarantees depending on the considered privacy regime.
Low privacy regimes. According to Theorem 4 when the privacy-tuning parameters are not too small 22
(i.e. when the estimation is not too private), the usual rate of convergence n is not degraded. In particular, for constant e or P, this recovers the results of Wasserman Zhou (010)).
n or P < क ) the provable guarantoes of the projection estimator are degraded compared to the usual rate of convergence. Is this degradation constitutive of the estimation problem, is it due to suboptimal upper-bound? Section 4.3 shows that this excess of risk is in fact almost optimal.
High privacy regimes. Furthermore, Theorem tells that in high privacy regimes (e <
4.3 Lower-bounds
As with the integrated risk on Lipschitz distributions, obtaining hourer-ounds for the class of periodic Sobolev densitics is done by considering packing with many elements. The idca of the packing globally the same as for histograms, except that the uniform deusity is perturbed with general C kernel with compact support instead of simple triangles. In the end, obtaín the following result:
Theorem 5 (Integrated lower-bound). Given L, B > there exists constants CL,B 0, no B) E IN, and co(L, > 0, such that for any n 2 no, and any 2 co/n
20 ll((() Tll 2 C. max n 184
20 (na)
inf sup s.t. PS
EX-e3"
347
where a = when C is the e-DP condition, and a = vp when is the p-2CDP condition.
Proof idea. As with the proof of Theorem 3 this lower-bound is based on the construction of packing of densities fw's 's where the w's are a well-chosen family of {0, 13 (m is fixed in the proof). Then, for a given w f0, 1)mh, fo deviates from a constant function around m+11 if, and only if, w; * Contrary proof of Theorem 3 however, the deviation cannot. be by triangle Indeed, such a function wouldn't 't even be differentiable. Instead, we deviation by t kernel with compact support. Even if the complete details are given in the full proof, Figure 3 gives general illustration of the packing.
the
Again, Fano-type type inequalities (for the e- eD case), and Assouad's 's lemma (for the p-zCDP case) are used to conclude.
The full proof can be found in Appendix H Tn comparison with the upper-bounds of Theorem 4 for eDDP the lower-bound almost matches the guarantees of the projection estimator. In particular, the excess of risk in the high privacy regime is close to being optimal. Section 4.4 explains how to bridge the gap even more, at the cost of relaxation.
Under p-2CDP, the lower-bounds and upper- bounds actually match. We conclude that projection estimators with CDP obtain minimax-optimal rates of convergence.
4.4 Near minimax optimality via relaxation
An hypothesis that we can make on the sub-oplimality of the projection estimator against e-DP mechanisms is that the Iisensitivity of the estimation of N Fourier coefficients scales as N whereas its l2 sensitivity scales as VN. Traditionally, the Gaussian mechanism (Dwork al. 2006a b) has allowed to use the I2 scnsitivity instead of the I one at the cost of introducing a relaxation term 8 the privacy guarantees, leading (e, dD-DP.
10

---

Published in Transactions on Machine Learning Research (08/2023)
A direct application of the Gaussian mechanism Dwork & Roth (2014) thus tells that aoros with Z 4v/n (1.5//)) NO0, 1) is (e, and, by Lemma has an error bounded as
N 16N In (1.25/8)
sup Ex-P#- Apea || (X) - T1l22 S CLa
+
N23
enn2
PSab e 2
n
Thus, choosing N of the order of min n
leads to a general error
Vln(1.25/6)
28
DTI
sup Ex-PE- #pmos proj (X) - =Tl22= S C2 max n2 2F+1,
nC
T 1.
In (1.25/0)
Finally, can be interesting look at prescribed rates for 8 as function of n.
Corollary (Privacy and utility of (8 with relaxation). Consider Y O, and integer, and 0 8lnn". Defining P == 16 In(n>) and using gorod with = 2/N (N 1), where N(0,1) 1) refers to a random variable following a centered Gaussian distribution of variance 1, leads to an (c, nz) ) procedure. there exists CL,B 0, a positive constant that only depends on L and B, such that if N is of the order of vln
vp
min n2o--,
then
sup E Ex-P8n amm ( - -11i.-- I CL, max {n {--===) ( (nn())()))nn)) 5+ S5
where Pary is polynomial expression depending on B and
Proof. Since S 8ln (n"), have á 2 pln(n"). By Theorem the mechanism is p-zCDP, and satisfics the claimed upper bounds for N on the considered order. By Bun & Steinke (2016) (that states that if a mechanism Di is p>zCDP, then it is (p+ 22+22/n (B/pl((1/)),))DD for any 8 > 0) it is thus (4Vōln(m7), n DP.
In order to understand the implications of this result, must understand the role of 5 in (e, ddiffferrnnt privacy. It is usually interpreted the probability of the procedure not respecting the e-DP condition (Dwork & Roth 2014). Hence, with probability 6, the result is not guaranteed to be private. A general rule of thumb for choosing 5 to take it much smaller than 1/n so that each individual of the database only has a small chance of socing its data leak Dworrk & Roth 2014). Choosing 5 = 1/n" for y >>> is hence considered a good choice for 8.
With this relaxation, the upper-bount of Corollary 2 matches the lower-bound of Theorem for e-DP up polylog factors.
5 Conclusion
As we have seen throughout this article, under central privacy, one can usually distinguish two estimation regimes. In the low privacy regime, the one hand, the estimation rate is not degraded compared to its non-private counterpart. This notably covers the early observation of Wasserman & Zhou (2010) for constant privacy budget. In the high privacy regime on the other hand, a provable degradation is unavoidable, and we extended the study of such regimes beyond the cases covered in Barber & Duchi 2014).
Besides examples in which the estimation sharp both regimes, we also presented some example which there are small gaps between the proved upper-bounds and lover-bounds. These gaps are nevertheless very small, especially for high degrees of smoothness, and they can be bridged up logarithmic factors with a reasonable and quite standard relaxation.
11

---

Published in Transactions on Machine Learning Research (08/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 -0N--16-IDEX-0005), and Chaire SeQ (ANR-20- CHIA-0020-01). This project was supported in part by the AllegroAssai ANR project ANR-19-CHIA-0000 Additionally, we thank the anonymous reviewers for their precious inputs and suggestions.
References
Martin Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Nya Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi (eds.), Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24- 2016, pp. 308 31-81.8..00 ACM, 2016. doi: 11145/29767492297833 URL https://doi..... orw.e/....11.. 11411/176//999.... 2978318
John M Abowd. The census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2867-2867, 2018.
Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially privale testing of identity and closeness of discrete distributions. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (ods.), Advances in Neural Information Processing Systems 81: An- nual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 1879-6891, 2018. URL. 1482244448800000b0bce44444444444
www.ggs..eurip... wwtps/esccccpppppree////////seee wwtp:cceepppeee.../.../... //ash/
Jayadev Acharya, Clement Canonne, Aditya Vikram Singh, and Himanshu Tyagi. Optimal rates for nonpara- metric density estimation under communication constraints. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Newral Information Processing Systems, vol- ume 34, pp. 26754-26766 Curran Associates, Inc., 2021a. URL hctpss//proooeddggs..onrr www.hig....eripp..oo. pdf
Jayadev Acharya, Clément L. Canonne, Prathamesh Mayekar, and Himanshu Tyagi. Informationn-onstrained optimization: can adaptive processing of gradients help? CoRR, abs/2104.00979, 2021b. URL https:
00979
Jayadev Acharya, Clément L.. Canomne, Zuteng Sun, and Himanshu Tyagi. Unified lower bounds for inter- active high-dimenssonall estimation under information constraints. CoRR, abs/2010.06562, 2021c. URL
http://axxxvo..//bbbb/// 2010.. 26662
Jayadev Acharya, Clément L. Canonne, Cody Freilag, Ziteng Sun, and Himanshu Tyagi. Inference under information constraints iii: Local privacy constraints. IEEE Journal on Selected Areas in Information The- orv, 2(1):253-22) 267, 2021d. doi: 10.1109/JSATT.200 2012 URL 2021 3053569
Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. Tn Vitaly Feldman, Katrina Ligett, and Sivan Sabato (eds.), Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide, volume 132 of Proceedings of Machine Learning Reseorch, pp. 48- 78. PMLR, 2021e. URL httpp://proceedings.u mll. mlr (atsss//13//ccchraaa//
Hilal Asi and John C. Duchi, Near instaccc in differential privacy. CoRR, abs 200//200000030, 2020a. URL htttps://arxie htt///aaaviiorrrb/rr/aaa wwtpoo/////...//eeeeeeeeee
Hilal Asi and John C. Duchi. Instance-optimality in differential privacy via approximate inverse sensilivily mechanisms. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 39: Annual Conference on Neural
Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020b. Utt/nttps://
12

---

Published in Transactions on Machine Learning Research (08/2023)
Hilal Asi, Jonathan R. Ullman, and Lydia Zakynthinou. From robustness to privacy and back. CoRR. hts//230.001183 2023. doi: 10.48550/arXiv http:///ww..22...183533. 2302.01855. URL httpp:://dii.rrg//// 40tp://0..8550///// 48850//555ii arriv 2302. 01855
Lars Backstrom, Cynthia Dwork, and Jon M. Kleinberg. Wherefore art thou r3579x?: anonymized social networks, hidden patlerns, and structural steganography. In Carey L. Williamson, Mary Ellen Zurko, Peter F. Patel-SSiie Schneider, and Prashant J. Shenoy (eds.), Proceedings of the 16th International Conference on World Wide Web, WWW 2007, Banff, Alberta, Canada, May 8-12, 2007, pp. 181-190. ACM, 2007. URL https://doi...... http::///oioorr/1..111111
doi: 0111451124272.12225555
1242598
Rina Foygel Barber and John C. Duchi. Privacy and statistical risk: Formalisms and minimax bounds, 2014.
Leighton Pate Barnes, Yanjun Han, and Ayfer Ozgur. Fisher information for distributed estimation under a blackboard communication protocol. In 2019 TEFE International Symposium on Information Theory (ISIT), pp. 2704-2708, 2019. doi: 10.1109/ISTT 8019.8849821.
Leighton Pate Barnes, Yanjun Han, and Ayfer Özgür. Lower bounds for learning distributions under com- munication constraints via fisher information. Journal of Muchine Learning Research, 21:Paper No. 236, 30, 2020. ISSN 1532-4435. URL htt.hhttts:///lll http:///mmrrccsalll... csail. mit ettp:ppppeess/oooluee//1117777/3 .df.......fff
Thomas B. Berrett, László Györfi, and Harro Walk. Strongly universally consistent nonparametric regression and classification with privatised data. Electronic Journal of Statistics, 15(1):2430 2453, 2021. doi:
10.1214/21-EJS1822 URL https:://oi.org: 12111111111142111111155555
Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan R. Ullman. Coinpress: Practical pri- vate mean and covariance estimation. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Had- sell, Maria-Florina Balcan, and Hsuan-Tien Lin (ods.), Advances in Newral Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020. URL html
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam D. Smith (eds.), Theory of Oryplography 14th Intervational Con- ference, TCC 2016-B, Beijing, China, October 31 November 3, 2016, Proceedings, Part 1, volume 9985 24. URL
of Lecture Notes in Computer Science, pp. 635-658, 2016. doi:
https: wtt.://///..0000/77----------0-0
Cristina Butucea, Amandine Dubois, Martin Kroll, and Adrien Saumard. Local differential privacy: Elbow effect in optimal density estimation and adaptation over besov ellipsoids. CoRR, abs/1 190300197,, 2019.
URL http:://aaxii..ogabbb//////////e
01927
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 3571 3580, 2017. URL htttps:/prroeeedings neurips. pctp:/ccpppp/p////aaaaaaa
1a31114aacc990888000313351331111 Abstract. html
Trit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Frank Neven, Catriel Beeri, and Tova Milo (eds.), Proceedings of the Twenty-Secome ACM SIGACT-SIGMOD-CS SIGART Symposium on Principles of Dalabase Systems, June 9-12, 2003, San Diego CA, USA, pp. 202 210. ACM, 2003. doi: URL http::///ooiii.... org/ 10. 10tg//...11//773113... 773173.
John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Local privacy and statistical minimax rates. In 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013, Allerton Park & Retreat Center, Monticello, IL, USA, October 2-4, 2013, pp. 1592. IEEE, 2013. doi: 10.1109/ Merron.2013.6777 URL /stp::///ai..og//0..1000 110.9/11.11191111111 201.errttoo..o...eeee.e.
2013. 2013.6736718
13

---

Published in Transactions on Machine Learning Research (08/2023)
John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Local privacy, data processing inequalities, and statistical minimax rates, 2014. URL httpps://arvvv.ogg//aaaass attp:abb//13.20000 3203.
John C. Duchi, Martin J. Wainwright, and Michael I. Jordan. Minimax optimal procedures for locally private URL http:///arrvy..rrr//////0.....00 02390
estimation. CoRR, abs/1604.02390 02390, 2016.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends
Theor. Comput. Sci., 9(3-4):211-077, 2014. doi: /11501//440000044. URL https://dol. http:////ooo.gg/....11.. ptrg/0..561/ 0400000042
Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arxiv preprint or urXiw:1603.01897 2016.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Nya Mironov, and Moni Naor. Our data, our- selves: Privacy via distributed noise generation. In Serge Vaudenay (ed.), Advances in Cryptology EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryplo- graphic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings, volume 4004 of Lec- ture Notes Computer Science, pp. 486-503. Springer, 2006a. doi: 10.1007/11761679/ 29. URL
https://doi. htt///ii.ogg////// ww.//o....///...... 100g/10..007/1176116799 29
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin (eds.), Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, volume 3876 of Lecture Notes in Computer Science, pp. 265 284. Springer, 2006b. doi: https://doi.org/ org/...g//11000.. 10011110771111188
14. URL
Ülfr Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: randomized aggregalable privacy- preserving ordinal response. In Gail-Joon Ahn, Moti Yung, and Ninghui Li (eds.), Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, Scottsdale, AZ, USA, November 3-7, 2014, pp. 1054-1067. ACM, 2014. doi: 10.1145/266027..266000 2660348. URL lhttp::// org/10. 014/1/.1145/ 2660267.2660345
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Indrajit Ray, Ninghui Li, and Christopher Kruegel (eds.), Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12-16, 2015, pp. 1322- 1333. ACM, 2015. doi: 10.1145/2810103.28811
URL https:
//doi. //doi.org/10.. 114.//81111//111111 2813677
Christophe Giraud. Introduction to high-dimensional statistics. 9781008158745. doi: 00.101197810001158745
Chapman and Hall/CRC 2021. ISBN
Antoine Gonon, Léon Zheng, Clément Lalanne, Quoc-Tung Le, Guillaune Lauga, and Can Pouliquen. Sparsity in neural networks can improve their privacy, 2023.
László Györfi and Martin Kroll. On rate optimal private regression under local differential privacy. arXiv preprint Xix:22200 00114,, 2022.
László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. A Distribution-Pree Theory of Nonparamet- ric Regression. Springer series in statistics. Springer, 2002. ISBN 978-0-387-95441-7, doi: 10.1007 10.1007/b97848. /998488. URL httts:://di.orgg:: 10. 1007/697848)
László Györfi and Martin Kroll. Multivariate density estimation from privatised data: universal consistency and minimax rates. Journal of Nonparametric Statistics, 0(0): 23, 2023. doi: 10. 10.10800/10485552.2000
2163634. URL https://doi.orgee http://p///ooooo///////////////0
1080/10485022 2022. 21282/24448822222222226266633
Rob Hall, Alessandro Rinaldo, and Larry A. Wasscrman. Differential privacy for functions and functional data. J. Mach. Learn. Res., 7001 2013. doi: 10.5555 045555/556779..0 /257//662222766000 URL https: sattps://dl. acm.
htg//b8//10..55525677739 250.0
14

---

Published in Transactions on Machine Learning Research (08/2023)
Nils Homer, Szaboles Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill Muchling, John V Pearson, Dietrich A Stephan, Stanley F Nelson, and David W Craig. Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density sup genotyping microarrays. PLoS Genet, 4(8))c1000167, 2008.
Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan R. Ullman. Privately learning high-dimensional distributions. In Alina Beygelzimer and Daniel Hsu (eds.), Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoeniz, AZ, USA, volume 99 of Proceedings of Machine Learning Reseorch, pp. 1853- 1902. PMLR, 2019. URL http://proceediings... .lr. http:/edding.......rrs//s//ee/ee
kaaath19a. 9aatattttaa////////aaaaaaa.a html
Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, 1CML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 10633 10660. PMLR, 2022. URL
mlr wtw...prees//vv1/// 1ar11662kaaaa222a...mm html
Gautam Kamath, Argyris Mouzakis, Matthew Regehr, Vikrant Singhal, Thomas Steinke, and Jonathan Ullman. A hias-variance-privacy trilemma for statistical estimation, 2023.
Vishesh Karwa and Salil P. Vadhan. Finite sample differentially private confidence intervals. In Anna R. Karlin (ed.), 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 1 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pp. 44:1-44:9. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2018. doi: MA2230LLIPIs.ITTTTT 2018.44
URL https://doi..rg// wtt.://g/...........oo 4230/LIPICs. ITC.S.
Martin Kroll. On density estimation at fixed point under local differential privacy. Electronic Jour- nal of Statistics, 15(1):1783 - 1813, 2021. doi: 10. 10.1214/11EJ511800 URL https://doii org/10. 1r1/1..1214/
21 E1-EJS1830
Clément Lalanne, Clément Gastaud, Nicolas Grislain, Aurélien Garivier, and Rémi Gribonval. Private quantiles estimation in the presence of atoms. CoRR, abs/22022 abs/2220.088669, 2022. URL, hattss://arx/: /rrg 0ba/2200.009633
Clément Lalanne, Aurélien Garivier and Rémi Gribonval. On the Statistical Complexity of Estimation and Testing under Privacy Constraints. Transactions on Machine Learning Research Journal, April 2023a.
URL https: hctaaa/cccccccaa-0043333/////
Clément Lalanne, Aurélien Garivier, and Rémi Gribonval. Private Statistical Estimation of Many Quantiles. In ICML 2023- 40th International Conference Machine Learning, Honolulu, United States, July 2023b. URL https: http:/hall.ccciccceallll-----
Joseph Weil, Béatrice Laurent, and Jean-Michel Loubes. Minimax optimal goodness-of-fit testing for densities and multinomials under a local differential privacy constraint. Bernoulli, 28(1):579-66) 600, 2022.
Grigorios Loukides, Joshua C. Denny, and Bradley A. Malin. The disclosure of diagnosis codes can breach research participants' privacy. J. Am. Medical Informatics Assoc., 17(3):322 3277227,22222 2010. doi: 10.1136/ hamia.2009.000 URL https: //doi. org/ 10. 1136/jamia. 20w.. 002725
Ilya Mironov. Rényi differential privacy. In 30th IEEE Computer Security Foundations Symposium, CSF 2017, Sanla Barbara, CA, USA, August 21-25, 2017, pp. 263 275. IEEE Computer Sociely, 2017. doi:
BLL1109/CFF2017..00 URL httpp:://ooii...o// www.ao...rr//1..0 10.g///0.111 1009///0.119//SFPP 2017.11
Arvind Narayanan and Vitaly Shmatikov. How to break anonymity of the netflix prize dataset. CoRR, abs/cs/0610105, 2006. URL http:://aa...voorg/aa//////////a org//bb/cc//0001100
Arvind Narayanan and Vitaly Shmatikov. Robust dc-anonymization of large sparse datascts. In 2008 IEEE Symposium on Security and Privacy (S&P 2008), 18-21 May 2008, Oakland, California, USA, pp. 111-125. TEEE Computer Society, 2008. doi: N0.1109/SP.2008..0 URL htttt::st//pooooooo 1109/SP 2008 33
15

---

Published in Transactions on Machine Learning Research (08/2023)
Phillippe Rigollet and Jan-Christian Hütter. High dimensional statisties. MIT lecture notes for course 188997, 2015. URL htttps:/matthmiit.eert http://tteeeeeeoooo/oo////////// pdff
Sandra Schluttenhofer and Jan Johannes. Adaptive pointwise density estimation under local differential privacy, 2022.
Vikrant Singhal. A polynomial time, pure differentially private estimator for binary product distributions, 2023.
Latanya Sweeney. Simple demographics often identify people uniquely. Health (San Francisco), 671 (2000): 1 34, 2000.
Latanya Sweeney. k-anonymity: A model for protecting privacy. Int. J. Uncertain. Fuzziness Knowl, Based Syst., 10(5):537-570, 2002. doi: 10.1142/5021848550000111 URL 50218488502001642
Abhradeep Guha Thakurta, Andrew H Vyrros, Umesh S Vaishampayan, Gaurav Kapoor, Julien Freudiger, Vivek Rangarajan Sridhar, and Doug Davidson. Learning new words. Gronted US Patents, 9594741, 2017.
Alexandre B. Tsybakov. Introduction to Nonparumetric Estimalion. Springer series in statistios. Springer, 2009, ISBN 975-0-387-79051-0, doi: 10.1007/b13794. URL htttpe///ab..org/10010////////
A. W. Van der Vaart. Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998. doi: 10.007//CB0998801110255.4
Tim van Erven and Peter Harremoës. Rényi divergence and kullback-leibler divergence. IEEE Trans. Inf. Theory, 60(7):3797-3822) 2014. doi: 200.0/T1T..01122255050 URL https:://di..rgg// 1109//IIT 2014. 2320500
Isabel Wagner and David Eckhoff. Technical privacy metrics: A systematic survey. ACM Compul. Surv., 51 (3):57:1-57:388 57:38, 2018. doi: 10.1145/3165389. URL
Larry A. Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):3755333) 389, 2010. doi: (0.1198/jasa.2000.mmm 2009. URL https: 7/doi
2009. tm08651
16

---

Published in Transactions on Machine Learning Research (08/2023)
A Useful results from the litterature
Fact 2 (Neyman-Peanee Pearson Le Cam's lemma (Rigollct & Hütter 2015 P2 be two probabilily distribulions a measure space E, then
Lemma 5.3)). Let P1
2 Px~P,
inf max PX~P, (V (X) * (1.2) (E(1.2
inf 2 (1,2)
1=1
(10)
= ス/4 - TV
(V (1,1
Fact 3 (Fano's lemma GGraud 2021 Theorem 3.1)). Let (P (P.))e be a family of probability distributions
on a measure space E. For any probability distribution Q on & such that P, < Q for all i, and for any test function V X N),
max PX~P; (V (X) +
P Px-P, (V) (X) +
iE N)
(11)
1 + Σ i=
KL (Pr Q)
In(N)
Often Q set to t Ei P..
Fact 4 (Le Cam's lemma for differential privacy Lalanne et al. 2023a Theorem 1)). If a randomized
mechanism IN satisfies O), then for any test function v codom (2I) + {1,2} and any probability distributions P1 and P2 on X we have
max Px~ Px-pon ie (1,2)
( (I (X)) ii)
2 (1- TV 2ne 28TV (P1,
Fact 5. Le Cam's lemma for concentrated differential privacy (Lalanne et al. 2023a Theorem 2)] 1f randomized mechanism M satisfies p-2CDP, then for any test function codom (Ml) + (1...., N and any probubilily distributions P1 and P2 on X,
max P Px-po" an (II * 1- /1- (1.12)
Fact 6 (Fano's lemma for diffcrential privacy Lalanne et al. 2023a anism DI satisfies c-DP, then for any test function codom (M) + N}, any family of probability distributions (Pr),E(L....)) on X,
Theorem 3)). If a randomized mech-
2TV(P..P,) N2 En 14TV(P,PPs)
max P Pxupsi (V (I[(X) +1) 2 18 (E(L....NN)
In(N)
Fact 7 (Fano's lemma for diffcrential privacy Lalanne et al. 2023a Theorem 4)). If a randomized mech- anism Di salisfies e-DP, then for any lest function : codom (D) + {I...., N}, any family of probability distributions (P (P.))E().....)) on X,
n NO
Σn 2TV(F.P.).
2TV(P.P. 2 TVT((P..P.))
1+
ii I+TV(P.P.))
max P Px-ppnon on (V (XI())) #1) 21 (E......))
In(N)
17

---

Published in Transactions on Machine Learning Research (08/2023)
y
Slope
Slope - L
y/ - g(x)
1
(())
Tuneable deviation support
250
Figure Packing for Theorem
Slope L
Slope L
y = (w(
Tuncable deviation support
When Wi
when wy
m=+1
m+1
Figure Packing for Thcorem
B Figures
C Proof of Lemma 1
Let I.ip zo E [0, 1]. The classical bias-variance decomposition gives that
E hiittt (x) - (<=o)) (E (X)( =(zo))² + V (*tist (x)()))
For any x E [0,1], we note bin(x) the bin of the histogram in which x falls into. Notice that, for any Tp E [0, 1] and any integer i, the random variable (bin(za)()) follows Bernoulli distribution of probability of success S æ. Let us first study the bias, using the definition 3 of hhist
E E (Bbincr)) (X.)) - T(rr)) = Unin(zo) x(x) nh.
1
E hist (X)())) - T(To)| =
nh
1=1
(π(()) ((0o)) do < L /
10 xo. dr < Lh
(T(2)) (xx)))d
< h bin(xo)
Ti J
bin(sr))
2
18

---

Published in Transactions on Machine Learning Research (08/2023)
C
Derivative of order / with bounded energy
y = (w)
Tuneable deviation support
m+1 0
when Wi
m+11 when wi
Figure 3: Packing for Theorem
Let us now look at the variance. By independence of X3's and Zz's,
(Ahist (z))
Σ v (Inin(rr)) (X+)) (Zointoni)
n²
( 1 (1- biu(so)
क + +2((2)
m
n?
W (Z)
nh2
bin((ra)
Since is L-Lipschitz on [0. 1] and has to integrate to 1 (because it is a density), is uniformly bounded from above by L+1 1 on [0, 1]. Hence, Shin(se) x S (L+ + 1)h and the result. follows.
D Assouad's lemma with concentrated differential privacy.
As the reduction to a testing problem between multiple hypotheses, Assouad's lemmn relies on similar ideas, where the packing has to be parametrized by a hypercube. Its advantage over tools like Fano's lemma is that it only makes tests between pairs of hypotheses (instead of all of them at the same time). The cost of this is that the control of the packing is slightly more difficult.
Suppose that the set of distributions of interest P contains family of distributions (Pww) (0.1) for certain positive integer m. If the loss function (taken quadratic for simplicity) can be decomposed as
Yw (0,1)", I1 far 112
2T
Witw 27 (w,, (,)
(12)
where for any w, fo represents the density of P.. then the minimax risk can be lower-bounded as (the proof is classical and can be found in Acharya et al. 2021e Section 5.4))
inf sup Ex-P,= i st. C PEP
x1122)
(13)
inf
Exppen cto.
(V (II(X)) + 0) P Pxpeo (V (II(X) #1)
201 sit. (xcodom(SDD -0,1)
where Puiio and Poin are the mixture distributions
PP P == 2m-1
Σ
Pwr and
Pura == 2m-1
P
(14)
WE (0
(E( lay=1
19

---

Published in Transactions on Machine Learning Research (08/2023)
The term
P X--pon (V (X[()) * 0) + IP Xx-P3n wi.1 wi.0
( (XI( + 1)
characterizes the testing difficulty between PP Pod and Pws... can be controlled by Te Cam's lemma, and by its variants when working under privacy (see Acharya et al. (2021e); Lalanne et al. (2023a) for differential privacy and Lalanne et al. (2023a] for concentrated differential privacy). Such results are reminded in Appendix
E Proof of Theorem 2
Let 2g E 1). As explained in the sketch of the proof, we build a packing consisting of two elements, and after controlling quantities such as their KL divergences or their TV distances, we leverage Le Cam-type inequalities in order to obtain lower-bounds.
Packing construction.
We define the functions A vh 0 as
Lhe if [0, 2o h) U [mo + h, 1],
Vr e [0.1], ( =
Lh² + Lh + L(x - mg) æ E nTu h, z0) Lh Lh L(x 20) if (ro, 3o + h)
(15)
Note that as fashion, but by considering functions that only contain 'half of a spike" centered zo- Furthermore, let note y the function that is constant to 1 on [0, 1] (we have y E e)),".
h S min No), L. 1 The case so E (0, is treated in the exact
We start by recalling the total variation distance between two probability distributions, and we recall some useful alternative expressions that are used in the proofs of this article. Given (4, a set U equipped with a o-algebra T, and two probability measures P1 and P2 two probability distribut on U, and compatible with T, the total variation distance TV (+.-) between P1 and P2 is defined
TV (P1, P2) sup |P (S) P2(S))
SET
Furthermore, when P2 are dominated by common o-finite measure μ (U, T), by noting Pl == dP1 and P2 == dF2, the Madon-Nikodym derivatives of P1 and P2 with respect to the following alternative du expressions to the total variation can be useful:
dy
TV (PI, = sup (P((S) P2((S] = Pi(tpi > p2)) PPl(pi > m2)) SET
(pi - P2) du
(p2 Pi) du
(pi>ps)
[po2pp)
/
1p1 P2 ld =
ju min(p1,P22 P2)du
These expressions simply come from considering the events {pr > p2} and (p2 2 P1} that form a partition of U1 and from the relation la = a + 2 min b) for any real numbers a and b.
Jumping back to our original proof, when ft.,. A E Liip we can compute the total variation between P and Pg the distributions of probability with densities fL.za. and g with respect to Lebesgue's measure on [0, 1},
/ min (FI.zo Constant part [o.1]
TV TV (P/ Mrano Py)) =1
1 Lh?do Lh? [0.1]
(16)
Another important measure of discrepancy between probability distributions is the so-called Kulbback-eiillr (KL) divergence. For two probability distributions P and Q such that P < Q (absolute continuity), it is defined as
dP
KL. (P]) Q) =
dP
dD
20

---

Published in Transactions on Machine Learning Research (08/2023)
Back to our problem, for h in neighborhood of 0, we also have the following Taylor expansion on their KL divergence:
KL (Pall P Plnagin) = Soon In (T-2
9 - 9 - In ( Th SLaaa S 0 (h² + +(hh))
(1- - 2h) + //¹ In
( Lh2 + Lt
di
(17)
where C is positive constant depending only on the O only hides constant factors. Furthermore, (0( Fo (2o) = L1 h| and {g, (t,2a,h is thus a 1 h| packing of O O w.r.t the seminorm fig Ilf - glو = (f - g(xa)).
Recovering the usual lower-bound By the classical minimax reduction hypothesis testing Equa- tion
inf # s.t.
sup F Ex (A(( m)00))²) x66
L
2 (h2 - -1)² inf inf max {ir PPxpp3n (V(((X)) # 0),
# s.t. e -. (0.1)
(v(+(X)) + #11
Pxwpon Iemann
Fact L2
1:2(1 112(1 11)2 (1 1- (pon pen se.eo..))
(18)
8
Pinsker
1,2
21 11²
(1- /
KI. [p@n]] psn frneog /2
8
Tensorization
L2
112
11)2
1 V-VVKL (P (P 12)
8
17
T
h3
+ +o(ht))
h2
h)²
1
The second incquality comes from the so-called Le Cam's lomma Rigollet Hütter 2015) that lower-bounds the lesting difficulty (without further constraints) between two distributions. The next inequality comes from the so-called Pinsker's inequality Tsybakov (2009), that states that for two probability distributions and Q, TV TV(P, Q) s /KL (P]) Q) /2. The last incquality is the result of the so-called tensorization property of the KL divergence that states that for two probability distributions P and Q, and for an integer 2 1, KT. (PSn) Q@*) < (KIT(P]) Q).
When possible (i.e. when n is big enough), setting h = 1===(d) (nn77 1/2 and (0(A))s 1242)
1/3
leads to, for big enough (so that
1,2
inf sup Ex-pom (((()) ((20))²) 2 *eel
n 2/3
64
4L2
This implics the first lower bound.
eD overhead. By Equation
[8 and by Le Cam's lemma for differential privacy on product distributions
(Fact 4
L? h2 -h2e -neTV (Prc.
sup Exxegr (A(X)(20) ((2))) >
inf
* cDP neeLip
8
16
I
h²2 - Imchh -Lmehh
8
21

---

Published in Transactions on Machine Learning Research (08/2023)
When possible (i.e. when ne is big enough), setting 1/yne leads to, when ne is large enough to ensure - h 2 1/2.
inf sup eDP
Ex-Pg" (#(()) -z(0))))
32 (nc) -1
PzCCP overhead. By Le Cam's lemma for zero-concentraatel differential privacy on product distributions
FFact 5 in 18
L 11 - (1) (1 -1- (P (r 2
inf
sup x
Ex~P?", ((( - (
cDD
L h2 - 11)2 (0))(111))) (nnn-hh)(-n////1- D//2//3)
1/2
When possible (i.e. when n/P is large enough), setting h (veLLRp) enough (so that 1 - h 1/2),
leads to, when nyD is large
sup Ex~P3" ((*(X)(zo)= x(20))²) 2 64 (nvP)-
inf p-ZDPP xce
F Proof of Theorem 3
Let m E IN) \ (0} that will be fixed later the proof. As explained in the sketch of the proof, we build a
packing consisting of functions that are parametrized by a vector w E {0, 1J After controlling quantities such as their pairwise TV distances, and their KL divergences to the uniform distribution, leverage Fano-type inequalities in order to obtain lower-bounds.
Packing construction. For any w E {0, 13 different from and any > O, we define the function 9L,w,h as
9L.whh |wlll
we wifliell L. mir.h
(19)
where the functions f are defined in 15 Note that Ihachh is L-Lipschitz and that as soon as h S hm == 2M+IJJ it is also valid density that Ir,wihh E @lip. Notice that the function gr.w. is constant to - |ell Lhd everywhere except on cach interval deviates by triangle of slopes +L and L..
i m++1 h, m+1 + h.] with such that wi * 0, on which it
By denoting by K the triangle kernel such that K(t) Lt1 [t( - (o. (t), it might be easier to visualize gLawh as
Vt E 1]. (L. = 1 - -1wl|12 /
m wiK 1
m + 11)
+
(20)
where f K Th2..
22

---

Published in Transactions on Machine Learning Research (08/2023)
For w. E {0,1) and for h small enough (i.e. h I hm), can bound the total variation between gr... and IP, Bo,wi, as
TV (P perwen P P
IØL.En - 9L,wnul
/ ||///|1 11wl12) / K Σ
m
(.
1
(w) w:)
m +
1 / |||ao||2 (elll-1lwopp -|Wlla1 K Σ
(:-
Iuy
wil K
+
2=1
|||w'||2 ||l||a| + duam (w.w")) ) K
(21)
S mLh?
(22)
The KL divergence between P ge.w. and Pg. with the density constant equal to on [0, 1], satisfies
KL (Po (o. Pg) = S In (gr,we)) graa.
In (1- ||]|| Lh?? (1- ([-[WW]Ibh? (1 ||w||12h ph
+ +||W/|| / In (1 |||| Lh + Lt) (1 - || LAd + Lt) dt
(23)
In(1+))
(- 1 Lh²) (1- ||l|| [l²) ) (1
[|]])2h)
T.1² + T.I) dl + +2||W|| //" (-||w|h T.222 I.) (1 - ||
Calculus 2 | 12 (13lulll))))))
Finally, we lower bound the squared 2 distance between gLawh and gL M
Moun
(gran gr,,.r.h) .h)²
m
m +h
(11w'111- [1wll1) / K + (wi- wi) ( (t-m i m
))²
dt
mII -h
m
m+ th
K 1--
m + #11)
-I|wwl - || K) de
m+
m
m th
m 2
i
))
K
t
- n
(24)
i
|||w|| |w///11 f {x]ar dt
-2K
t
m +
dham (w) (ʃ K2
(ʃx² -2m 2m (f
2
2 2dham (w, w/) 1 (1i2 -mhi
2dmam (w,w)) 1,2 (1 3mh)
3
23

---

Published in Transactions on Machine Learning Research (08/2023)
By the Varshamov-Gilben Gilbert theorem (Tybakov
2009
Lemma 2.7), as long
8, there exist M N
and w(()) ((.,,..,, E {0, 1 such that M 2 nn/ w0) = {0)m and i + j = dham (w(t) w(l) 2 m/8.
According to 24 the family (1),w)),,);=11 is then an = V mL2(hh3-3kl packing of Lip for the L distance.
12
Recovering the usual lower-bound. By Equation 5 with +(-) = (.)2 and || the L norm,
inf sup E Ex-prn, (1 (f(X) 7)² =
mL? (1 3mh)
inf
max P Exppon (T # == i-...,, 2 (,, - (0.1)
inf
48
# s.. C v.
1 M Ei KL pen Pem(W)
pen
Fact mm22/3 (1 3mh)
48
1
In(M)
(25)
Eisign KL ( (Poeass (PP)
Tensorization 3 (1 -3mh)
1 +
m 15
1
48
In(M)
dello|l M22
m (1
3mh)
1 + umh3 3mhh)
48
In(2)m/8
So, by choosing m [n2/3] and e where is a positive constant small enough we get, for n big enough,
inf sup Ex-pen # (Jonn) (#(X) m)²² 2 (n) cDP
where is a positive constant depending only on L.
DD overhead. By the same reduction and Fano's lemma for differential privacy on product distributions (Fact 6 we get for any h < hym:
(non (+(X) (+(x)- xx))
inf sup E Exapon cDD
xeelip
1 + nc Σ ISijEM TV (P, (o Pa B n.)
h (1 3mh)
48
In(M)
22
& M2
mL2 (1 3mh)
(1
+ Lne
48
In(2)m/8
So, by choosing m = [/ne]] and h = - where e is small enough a positive constant (depending only on L). we get, as soon as min(n, nc) is big enough,
(San (#(X) -n))=
inf sup Ex-P3",6 cDP ree
2 C'- ('n) (m)e)==((n
where O' is a positive constant depending only on L.
p=CDP overhead. For p-zCDP, we present the proof using both Fano's lemma and Assouad's method, We will that Assouad gives better results
24

---

Published in Transactions on Machine Learning Research (08/2023)
Fano version. By again the same reduction and Fano's lemma for zero-concentrated differential privacy (Fact denoting 4. = TV (P (Prr, P (e..))),.)) we get for any h S hms
sup Ex~P2" , (Ya)) (+(X) =)² -=)
inf p=CDPP x
m 3mh)
1 2 E LisiJSM (1 + (2.5) In(M
48
mL? (1 3mh)
1 1+ n p2
mLA +m² 1²²1²²²
48
lm(2)m/88
(nvD) 31
So, by choosing we get that
and h = s for small enough (depending only on L), if 2 is big enough,
P
_ (1on)
inf sup T
0..1 (#(X) (((x)=z}² 2 20" 4/3
s.t. pDCDPP
where O" a positive constant depending only on L.
A ssouad version. From Equation 24 we can see that when == for a positive that is small enough, the condition expressed Equation [2 is satistied for 1(h9). To apply (14). the only missing ingredient
is to bound the testing difficulties between the mixtures the hypercube.
In the sequel, P., is used as short for P POw.o. We need to bound the total variation between the mixtures on the hypercube (see 14 as
(V (Po,o,, Parsi) TV
Σ
Σ
2
ge.w 2m-1
ge.w.h
WE wE(0,1) wi=0
WE wi=1
1 1
Σ
ILawh
ILawh
2 2
WE(0,1]m"wys
=E(0,1)"|[w==
1
Σ
(gL,(W i 0,0
2m
W4 - Wm E(0.13
91.(wI..... 1, (..
1
Σ
2m
Wi... 1,6% I mm e ((U,1}
91.(w1ome) 1.lwe 1 w )
Σ
2Lh²
2m
W1 Wi We
1:We| 1m... E (0.1)
0 (1:2)
Here and in the sequel, the asymptotic comparators only hide constants and terms that depend on L. All in all, by using Le Cam's lemma for product distribution and p>cCPP Fact and by Equation 13 since
T = 2(h3) we obtain
Ex-po- (1 (+(X) 7)² Ω (mhi² (1- 1i-n/pp0 (1²))
inf
sup Piob L.B
(26)
# PCCCDP
25

---

Published in Transactions on Machine Learning Research (08/2023)
Setting h z (n/D) concludes the proof.
G proof of Lemma
Let E L We have,
(Vmn) p..) (#pro) x))
2
+00
Parseval
[
Σ
0 0j + 41
+
Σ
0g
N=
N
+
E
0, - 0, +
- 44
+ Σ
0..
==1
1=N+1
Furthermore, for any i, since Z is centered
E 0.: =
(x()))
(x)((,))) x, L.L.d. Ltd.
(x(1) / Jt. 0.
71
Hence, for any i, since Ze is independent from the dataset
((1: - 0: + 2/ ) -v (0.) + n2
(2,)
Independence of X,
1
V (os ( + v
n 1=1
lo.lsv
2
1
v (Z)
n
Finally, with aj
1, Fact allows bounding
Σ Ei=m+1 0
Σ
0
23
0
F Fact 1
1 L
a
N25
N28
N25 7223
i=++1
N=++1
This yiclds the conclusion with CL,B == max (2, 1.2 / 2
H Proof of Theorem 5
Let us consider the following well-known function :
Vo E R, Ko(x) := e T- 1 (-11))(x).
We can notice that for any 8 there exists 0 such that the kernel K(x) vKo(2x) satisfies
2 < and K(x) > 0 ifl x E (-1/2,1/2). Furthermore, for any i E N, K(0 0 for every (-00,- U 1/2,+000
K C (R, [0, +oo)), f (K(#))²
Packing construction. Let m E IN \ {0} that will be fixed later. For any h > 0, and w E t0, we define the function 9L.3 as,
Vo [0, 1], (L, =1 1- 1 f + Th Σ wiK
T m+
(27)
h
Note that when h < m4I we have fo aL.h 1; when mh f (K(()) < 1, we have I1. 2 0; and when both hold we have wh E PSoh (see Equation (0)) Indeed, under these hypotheses, the periodicity conditions immediate (the function is constant neighborhoods of 0 and with the same value). The
26

---

Published in Transactions on Machine Learning Research (08/2023)
energy of the 3th derivative can be bounded as
(9) 2
/ (1LBAeerh)
=-
/
Lh
Σ
m
wi
x + K
2 m+
(()
m-11
h
Σ /
disjoint support
I,2
Wi
K(3)
m++1
h
1=1
= Lmmmh / (K(0))
S L2
In the sequel of this proof, this hypothesis will always be satisfied asymptotically for all the values of m and h that will be considered. From now on, we may consider it valid.
Given à > O and w, w (0,1) 10", when Wh 9L P Fgt.tar. and Se.a as,
PSob, LB we can bound the total variation between
TV (P (PoL.Owe Pol.o..))
1
/
/
[[(w/112 - 11wl1)) f K +
Σ (w/ - Lh
m+1
2
h
1=1
/ |||/'|| 1T / K Σ
< 2
|w! - wi Th
h
1=1
|||l/| - || dham (w) Lha+1 f K
(28)
2
< 0+
(29)
27

---

Published in Transactions on Machine Learning Research (08/2023)
The KL divergence between P Sg. and pg the uniform distribution on [0, 11, is bounded
KT (P ge. = -oonn In (gr.8arh) Se.
= -ao. mom - 2
(1- |||/|| Lhet3 / K K)
1
(1-
||w]l
[| L1 / (K)
+ ||w|11 / In (1-
(1- || [[wll1bh8 f K + LhnK
t
h1
1--1W111hh&t f JK= [K+ Dhe K
1
1p
In(1+)) 5
(1 (1
(1[w]]I { (1-1W111 / {K]
(30)
||wl12 _ /
(-Ilwll |
| LNOK (1h)
- (1-1WollLhetH p K LI K
1
hn)
dt
|| / K2 - -WW11B222 f
Calculus
/ 122 mL1212001 / k2
I (
Finally, the squared 2 distance between & and IL,B can be lower bounded as,
So.n) 0..1
(oL, IL,B.".N) )n
m
M.
Lh (1Ww112 - [1lll2) / K + (wi Wh K
("r
(1-
m+I
dt
h
I
m
m+
L K
1
m+1
i
Lh
||||||
||W//111 /K)
2
di
(31)
2
m
M sWw!
LIFK
m+1
-Iw''1i / K keau
m+1
|||||| L
h
duam w/) 2241 (ʃ R22 (xx²=2m)) 2mh (fx² )
By the Varshamov-Gillee theorem (Tyyakov 2009 and w())) (...,.(M)
Lemma 2.7), as long 8, there exist M E N
(M) E {0, 1 such that M > 2n/8 (0) = =007 and i + j = duam (w((), wli)) 2 m/8.
-mhh According to 311, the family (gr,),,()) (w) is then a Ω -b m L212841 (SK² 2mh (J (JK) k))) packing
of PSob for the 1,2 distance.
28

---

Published in Transactions on Machine Learning Research (08/2023)
Recovering the usual lower-bound. By Equation 5
with Φ(-) = (.)2 and ||
the L norm,
it / (f(X) - -)
inf s.t.
sup Ex-P "8h
10,1]
L
(f K² 1 2mh (ʃ
20+1
32
inf
inf
max P Px-pon
(v(((X)) # i)
s.t. C 1.
-(013) im I....M.
Fact 8 2
(ʃ (n²=220m 2mh (f K)
mh
1+ 1I Eisism KL (pon In(M)
potn
(32)
1
L2
2mhh (xx) (K) 2)
Tensorization
mh 32
mhh2++1 23+1
1x22-2ah
1 M Eisism KT. (P (P Por.awer Pg
1
In(M)
30 & M222//
L
2mh (ʃ K
)) (1- + nmL22 f K2
mhh8+1
mh
28+1
32
ln(2)m/8
Finally, setting
n n and h for small enough gives that, for big enough,
F Exppon / (f(X) 7)² C- 28+T
inf sup DD
TEPP L,B
where C is a positive constant depending only on L and B.
e- DP overhead.
By the same reduction and Fano's lemma for differential privacy on product distributions
(Fact
we get
E Ex-ppn / (+(X) - x²²
inf a c-DP
sup PBob 1,0
11o11]
1
20+1
-22h
2mh (fx) )
32
1 1+ ne Eis TV (P
Se. P P Ps..e.().))
In(M)
I
mh23+1 (SX-
2mhh 2mh (fx)) (1-
1 2ncm 2h f K
32
In ln(2)m/8
Setting m (ne) nमन and
for small enough leads to, for ne big enough, m
Ex Ex~pon / (*(X) =)² 2 C'-1(nc) 3
inf # cDP
sup TEOP L.
[0.1]
where O' is constant depending only I and B.
29

---

Published in Transactions on Machine Learning Research (08/2023)
pzCDP overhead. For p-zCDP, we present the proof using both Fano's lemma and Assouad's method. We will see that Assouad gives better results.
Fano version. By again the same reduction and Fano's lemma for zero-concentrated differential privacy (Fact denoting las = TV (P& (Po P. (en.owts),)) we gel.
/ (+(X) - =)²²
inf p>CDPP
sup aa L,p
E EX-P8"
[0.1]
2
( 2mh (ʃz² K
mh mhh 29+1
32
1+ n²
Σ ISEJsM Hes + +
M
In(M
29
1,2
mh mhh 23+1
(s 12
|k²-2mml
2mh (f
2
32
mLL fK
4n
+ (mLh8+1 (aihhtt-KK SK]
n
1n(2)m/8
So, by choosing (m)P) )ā. and h for small enough, if nvp and
=(n/p) उगना lvP
(nvD) म
are big enough,
inf
sup
E Ex-pin
/
(+(X) x)² 2 C"-1 (nvp)
2-1/3
28
wee PSah
10.11
where C a constant depending only on and B.
Assouad version. From Equation we can see that when == e for a positive that is small enough, the condition expressed in Equation (12 satisfied for 2+12))) To apply (14). the only missing ingredient is to bound the testing difficulties between the mixtures the hypercube.
30

---

Published in Transactions on Machine Learning Research (08/2023)
In the sequel, Pw is used as short for P St.a We need to bound the total variation between the mixtures the hypercube (denoted Puil and Puid, of 14 as
TV woo Pwni)
1
E [e{101)""|u==
Σ
2 2m
gLAWA
|E/0,1
1
Σ
(w1.3. 1.0, 1....am
2
Wi
1 mn [0,1)
1
Σ
/
2
por to (0.1)
woree i, 1 (..ghim))))))
Σ
2Lh 3+1
f K
2
1,044 {(01))
0 (1 2+1)
Here and in the sequel, the asymptotic comparators only hide constants (such f JK3) and terms that depends L and B. All in all, by using Le Cam's lemma for product distribution and p-xCDP (Fact 5 and by leveraging Equation
13 with r = 2(h28+1),
inf # PDD Pabb
sup Exxpp" (+(X) - = 22 22@ (1 nvpo (1++1))
(33)
[01]]
Setting h s (1)D) Zh and m c/h for small enough concludes the proof by yielding a lower bound Ω (n)))) 2841
31


Reviews:
[{"review_id": "p5bVbJqgkO", "reviewer": "Reviewer_P6Fj", "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 of the paper:\n1. It provides new lower bound results for the Lipschitz distribution under $\\rho$-zCDP\n2. It establishes new upper and lower bound results for smooth distributions\n3. The upper bound results are (almost) optimal in several settings\n\nWeaknesses of the paper:\n1. The results in Theorem 1 seem to be some known results\n2. It is unclear which part will be loss when using the general lower bound framework to establish the $\\rho$-zCDP for the Lipschitz distribution\n3. The statement in the corollary 2 with respect to the $\\delta$ parameter under $(\\epsilon,\\delta)$-DP is unclear", "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 the problem of density estimation under differential privacy. More specifically, the authors consider the Lipschitz and smooth distributions, and provide upper and lower bounds for the proposed differentially private density estimators. The main contribution of the paper is the new lower bound and upper bound results in different settings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall, the results are interesting and seems to be important. I have the following questions need to be addressed in the current paper:\n1. Same results have been established in Barber & Duchi 2014 for Lipschitz distribution under $\\epsilon$-DP. Then, why Theorem 1 is needed in the main paper since the $\\rho$-zCDP results can be obtained by its relationship to $\\epsilon$-DP.\n2. Why do you consider the $\\rho$-zCDP instead of the Renyi DP?\n3. See point 2 in Weakness section.\n4. In corollary 2, can you restate the results in terms of $\\epsilon,\\delta$ instead of $n^\\gamma$. In this case, it is easy for the reader to compare the results to the results under $\\epsilon$-DP.\n5. The results in Table 1 about the Pure DP and Relaxed DP are also misleading. The relaxed DP result is missing the $\\delta$ parameter which is the key difference when $\\beta$ is large enough.\n", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XE8qadpF2J", "reviewer": "Reviewer_WJct", "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 result gracefully recover known results in the literature ([Barber and Duchi, 2014] for Lipschitz densities).\n2. In most cases, the authors obtain matching lower bounds, making their results particularly crisp.\n3. The authors discuss optimality and sub-optimality of various classical lower bounding techniques (Fano,\nAssouad, Tsybakov) for their problem.\n4. The article is well-written and makes for a good read.\n\n**Weaknesses**\n1. The techniques employed to derive the rates appear to be standard.\n2. In the flow of the paper, while global privacy is mentioned early in the paper, local privacy is currently explained before global privacy. This is a bit unnatural.\n\n___\n\nR. F. Barber and J. C. Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint\narXiv:1412.4451, 2014", "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 topic of this work is differentially-private (DP) non-parametric density estimation.\nSpecifically, the authors derive minimax rates for the density (w.r.t the Lebesgue measure on $[0,1]$) estimation problem (from $n$ iid samples) under:\n- different notions of smoothness (Lipschitz, periodic Sobolev).\n- different DP frameworks (pure/relaxed differential privacy with Laplace noise, concentrated differential privacy with Gaussian noise).\n\n\nThe analysis is conducted under a global privacy assumption where a central agent (aggregator) has access to the entire dataset and computes a DP estimator (as opposed to local privacy, where the aggregator only sees data which has already been DP blurred by each data holder separately).\nOf particular interest, in the $\\varepsilon$-DP setting, the authors investigate the influence of $\\varepsilon$ on the minimax rates, highlighting the existence of a ``phase transition'' in the problem. When $\\varepsilon$ becomes too small (compared to the sample size), DP becomes the bottleneck in the density estimation problem (high-privacy regime). On the other hand, when $\\varepsilon$ is relatively large, DP does not impact the estimation rate.\nTable~1 on p.3. compactly summarizes their results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please recall the definition of the Hamming distance when introduced on p.3.\n\n- In Fact.1, the right hand side of the inequality reads as $\\leq \\frac{L^2}{\\pi^{2 \\beta}}$ where here $\\pi$ if understood correctly is $3.1416...$. However the distribution in context is also $\\pi$. Perhaps disambiguate $\\pi$ in Fact 1 (adding a sentence for the reader).\n\n- Add an explanation (in words) of global privacy before explaining local privacy.\n\n- Typos:\n  - p.2. remove space after trilemma in ``trilemma ,''\n  - p.4 ``mechamisn''\n  - p.7 ``Lebesque's measure''", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "uoA0lxgHD5", "reviewer": "Reviewer_uQLW", "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": "Overall, this seems like a solid paper. The technique developed by the authors have two benefits:\n- they recover already known bounds without loss, hinting that the authors' techniques don't lose power due to their generality.\n- the authors provide a lot of novel bounds, with lower and upper bounds often closely matching.  \n- the results are given both for pure DP and zCDP.\n- the authors provide bounds under a general Lipschitz density assumption, and bounds under an assumption of periodic Sobolev densities that focuses on a less general class of smoother densities, but this allows the authors to obtain more refined bound. \n\nDisclaimer: I have not had a chance to check the proofs carefully. That said, assuming the authors' results are right, I think this is a strong theory paper for DP density estimation. I am also not too familiar with previous work and unable to judge the novelty, and taking the authors' word on what has been and not been done.\n\nThe main and only complaint that I have is that the authors mention early on that \"however, an important implicit hypothesis in this line of work is that ϵ, the parameter that decides how private the estimation needs to be, is supposed not to depend on the sample size. This hypothesis may seem disputable.\" I do not disagree with the authors, but can they motivate and discuss this point a bit more? ", "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 goal of the paper is to provide new lower and upper sample complexity bounds for non-parametric differentially private density estimation in the central (or \"global\") model. In terms of novelty, the bounds developed by the authors make the dependencies on $\\epsilon$ explicit. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "A bit more motivation of the problem and why having $\\epsilon$ depend on $n$ is useful practically would be nice. Overall, however, this seems like a strong paper and I am happy with the current results. ", "broader_impact_concerns": "No broader impact concerns---the paper is about differential privacy and the entire point is ethical concerns in CS/ML. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors provide new lower bounds under central differential privacy for various estimation tasks. Reviewers agreed these were interesting. There were fairly few questions or concerns, but the authors dispatched them with alacrity. Assuming soundness, which the reviewers vouch for, then the paper should be accepted.
Decision: Accept (poster)