Locally differentially private estimation of functionals of discrete distributions
Authors: Cristina Butucea
Yann Issartel
Venue: NeurIPS 2021 Poster (2021)
Keywords: high-dimensional statistics
local differential privacy
power sum functional
minimax estimation
interactive privacy mechanism
non-interactive privacy mechanism
plug-in estimator
threshold estimation

Abstract: We study the  problem of estimating non-linear functionals of discrete distributions in the context of local differential privacy. The initial data $x_1,\ldots,x_n \in[K]$ are supposed i.i.d. and distributed according to an unknown discrete distribution $p = (p_1,\ldots,p_K)$. Only $\alpha$-locally differentially private (LDP) samples $z_1,...,z_n$ are publicly available, where the term 'local' means that each $z_i$ is produced using one individual attribute $x_i$. We exhibit privacy mechanisms (PM) that are interactive (i.e. they are allowed to use already published confidential data) or non-interactive. We describe the behavior of the quadratic risk for estimating the power sum functional $F_{\gamma} = \sum_{k=1}^K p_k^{\gamma}$, $\gamma >0$ as a function of $K, \, n$ and $\alpha$. In the non-interactive case, we study twol plug-in type estimators of $F_{\gamma}$, for all $\gamma >0$, that are similar to the MLE analyzed by Jiao et al. (2017) in the multinomial model. However, due to the privacy constraint the rates we attain are slower and similar to those obtained in the Gaussian model by Collier et al. (2020). In the sequentially interactive case, we introduce for all $\gamma >1$ a two-step procedure which attains the parametric rate $(n \alpha^2)^{-1/2}$ when $\gamma \geq 2$.  We give lower bounds results over all $\alpha-$LDP mechanisms and over all estimators using the private samples.

Locally differentially private estimation of nonlinear functionals of discrete distributions
Cristina Butucea CREST, ENSAE, IP Paris Palaiseau 91 120 Cedex, France cristina. butucea@ensae fr
Yann Issartel CREST, ENSAE, IP Paris Palaiseau 91120 Cedex, France wew.ssssateeeeeeeeeeeeeee fr
Abstract
We study the problem of estimating non- con-linear functionals of discrete distributions in the context of local differential privacy. The initial data æ1...., In E [K] are supposed i.i.d. and distributed according an unknown discrete distribution [PI.....PR' PR). Only a-locally differentially private (I.P) samples 21, .... 2n are publicly available, where the term 'local' means that each 2; is produced using one individual attribute z₁, We exhibit privacy mechanisms (PM) that are sequentially interactive (i.e. they are allowed to already published confidential data) non-interactive. We describe the behavior the quadratic risk for estimating the power sum functional F- = Ek= P7- > O as function of K, n and a. In the non-interactive case, we study two plug-in type estimators of Fz. for all y O, that are similar to the MLE analyzed by Jiao et al. [18) in the multinomial model. However, due the privacy constraint the rates we attain are slower and similar to those obtained in the Gaussian model by Collier et al. [9. In the sequentially interactive case, we introduce for all ?
two-step procedure which attains the parametric rate (na²)-1/2 when 7 2 2. We give lower bounds results over all o-L.P mechanisms and all estimators using the private samples.
Introduction
Information theoretic measures have become of utmost importance and extensively used in informa- tion theory, image processing, physics, genetics and more recently in machine learning and statistics. Such functionals of probability distributions are useful to design estimators, to choose most infor- mative features in different algorithms, to test identity or closeness of distributions. Popular such measures are the power-sum, the entropy and more general Rényi entropies of discrete distributions.
In this paper, we are interested in estimating the power sum functional F, (p) of a discrete distribution p (pi, "0.,,,PK Pr)):
(p)
Pk
with power 7 E (0, o0).
This instance of information measure has tight connection with the famous Rényi entropy H, via the formula H, log f.
In the statistical literature, smooth nonlinear functionals are often reduced via Taylor expansion to several functionals of the type F,, for positive integer values of (see monographs like e.g. [14) ).
For example. the entropy H (p) = Σ P, log(1/p)) of the probability distribution p with finite support and probabilities bounded away from can be approximated via a Taylor expansion to linear combination of F., for integer values of y and estimated parametric rate of 1/ l/vn.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Symmetric functions of pi......P PK. i.e. functions of at most K variables that are permutation invariant, play an important role deep learning, e.g. [3), 23] Such functions can be written as polynomials of functionals Fy for integer values of y and estimated using our procedures.
Another important application of such functionals is testing identity or closeness of distributions. For example, 1et us consider uniformity testing that is the null hypothesis is Ho P; 1/K for all j from to K against the alternative hypothesis p is not the uniform distribution. Suppose the distance measuring how far p is from the uniform distribution is the Hellinger distance
Therefore a test procedure will proceed by estimating this Hellinger distance using the sample and this involves estimating F1/2 for ? = 1/2. Thus, an uniformity test procedure will be based on the estimator of this discrepancy, and similarly for identity or closeness tests. More generally, when the distance between two probability distributions is evaluated by a discrepancy or a distance, functionals F,, naturally appear in their expression. Note however that testing rates may differ from the estimation rates of the discrepancy as is the case for the L1 distance where [26) showed that several tests procedures must be aggregated in order to attain better rates for testing. We stress the fact that testing is a different problem from learning the functional.
1.1 Plug-in Approach
In the standard statistical setup (also called multinomial setting), the goal is to estimate the power sum functional F., based on i.dd. samples I1, ..,, Zy following an unknown discrete distribution approach to this problem is the plug-in
p (Pi..... : p with alphabet size K. A commonly-usee approach, which amounts to using an estimate á of the parameter p in order to build an estimator (0) of the functional (p). The resulting plug-in estimator actually corresponds to the so-called maximum likelihood estimator (MLE) when the estimate ş = (ΦK) is defined as the empirical distribution p& = 1 Ei= 12,= (i.e. the average counts in the 1-th box after binning). This approach is not only intuitive and simple, but is also theoretically well grounded, it asymptotically efficient for finitely supported probabilities (finite K), and is non-asymptotically nearly optimal for possibly increasing K [18] (for details, the related literature below). A natural question that investigate in this paper is whether such plug-in type approach still performs well in a non-standard statistical setup where constraint of privacy is imposed on the observed data.
In the standard setup, estimation of power-sum functionals was studied for the widely spread MLE estimator in [18] where the authors found that its maximal quadratic risk (also called worst case squared error risk) is sub-optimal only by some logarithmic factor. The estimation rates have then been tightened to minimax optimal bounds using the best polynomial approximation of the power function [17. 29). Following the chronology of this literature, our study in a non-standard privacy setup starts with an analogue of this MLE, with a twofold purpose: (i) to highlight an important difference between the LDP setting and the standard (non private) setting: practical methods performing well in the non private case should not be systematically transferred to the private settings, good estimator in the first setup not being necessarily a good estimator in the latter setup; (ii) to show the regimes where plug-in type estimators fail and the estimation problem is delicate, thus setting benchmarks for future work on functional estimation in the LDP setting, as well as more involved private settings.
1.2 Differential Privacy
Keeping sensitive data . Th private is major concern in the modern area of Big Data. For example, #1,, Tr may be personal health or financial data of n participants to survey. Differential privacy (DP) [12) has prevailed in the recent literature as a convenient approach to randomize samples with control of the amount a > 0 of privacy introduced. The randomized samples 21,.... : En, also known private samples, are provided to the statisticians who want to extract information the underlying distribution p of the initial data Ti,.... In. Global or central DP allows simultancous treatment of the whole initial sample in order to produce the privatized random variables. In contrast, Local differential privacy (LDP) is a stronger setup of privacy where no one has access to all sensitive data 21...., In (not even trusted curator or third party to handle the privatization), but each individual i has access to one Z;.
It is quite popular now that privacy, in particular local differential privacy, comes at the cost of slower rates of learning in many estimation problems. For example, estimation of the probability density is known to be achieved with slower rates in the minimax sense under c- constraints, see [10).
2

---

28 24 and 4. There is a rush nowadays to better understand when the loss is unavoidable and to show that such loss is optimal over all privacy mechanisms and procedures at hand.
In this LDP setup, there are major distinctions according to the way the privacy mechanisms use the available information, that is non-interactive, sequentially interactive fully interactive setups. When using non-interactive mechanisms, each private sample 2; is produced by privacy mechanism Qi that has access only to one sensitive sample I₁. They are arguably the simplest mechanisms. A richer class of mechanisms are the so-called sequentially interactive mechanisms where each agent i is allowed to incorporate into its private mechanism Q; the already privatized data 21...... ........2.... 2 of other agents, along with T; It is known e.g. [3] that sequentially interactive methods attain much faster rates than the non-interactive mechanisms in some inference problems. This has also been proved for identity testing of discrete distributions in [3I. Finally, the fully interactive privacy mechanisms are allowed to use one T; several times, together with all publicly available randomized z's. In this case, the natural question is how many randomizations are necessary in order to acquire the desired amount of information. It has been proved that there exist separations between fully and sequentially interactive procedures, e.g. [20] and [21], as well as separations between fully interactive mechanisms and global DP, e.g. [8]. We do not consider fully interactive mechanisms the current paper (neither in the upper, nor in the lower bounds).
Understanding the relative power of interactivity is a crucial question in the LDP setting. In this line of work, we study the estimation of the power sum functional F,, under the constraints that the available data 21...... Zn stem from non-interactive and sequentially interactive privacy mechanisms, respectively.
1.3 Contributions
In the a-LDP setting we propose three estimators of the power sum function (p(p) based on the randomized observations. The performance of any estimator F,, is controlled by proving upper bounds on its non-asymptotic quadratic risk B[( - F2)²), with an explicit dependence on the parameters of the problem: the power y, the alphabet size K, the sample size n and the amount of privacy a.
Our first contribution is tight characterization of the quadratic risk of the plug-in in estimator, an analogue of the plug-in MLE (discussed above). Unfortunately, its risk grows rapidly with the alphabet size K, thus showing that the plug-in approach is by far not optimal for large K. This contrasts with the good performance of the plug-in in the standard statistical setup [8]. Thus, good estimators in the standard setup are not necessarily to be used as such in the LDP setting.
Our second contribution is a correction of this plug-in estimator by truncating the small probabilities Pa- The induced procedure, called thresholded estimator in the sequel, performs significantly better than the plug-in estimator, typically when the alphabet size K is large. We emphasize that this improvement is important, since the risk of this thresholded estimator is (almost) independent of the support size K for large K, unlike the risk of the plug-in estimator. is therefore different from the literature on functional estimation (in the standard setting) where the improvements in the risk of plug-in estimators are often of magnitude of logarithmic factors.
The privatized data ø1,.... 2n used by both our plug-in and thresholded estimators are generated by a simple Laplace non-interactive mechanism. In contrast, our third contribution is two-step procedure based on a sequentially interactive mechanism. The definition of this two-step procedure heavily relies on the plug-in estimator, and thus can be seen as refinement of the plug-in approach. Such sequentially interactive method was studied in (5) for the particular power sum functional F2 (7 = 2), also called quadratic functional, in a continuous setup (where the probability distribution is smooth function on [0. IJ). By allowing to encode information from previous observations 21..... 24-1 into new released data 2,. this sequentially interactive procedure achieves faster rates than the thresholded estimator, when K is large and y 1, though this improvement is only of a logarithmic factor. Unfortunately, this sequentially interactive procedure is only defined for y > 1, and has slower rates than the thresholded and plug-in estimators when K is small. Accordingly, none of our three estimators overall better than the others. Table presents upper bounds on the maximal quadratic risks of these three estimators. The choice of estimators therefore depends on regimes (i.e. values of K, 7), and our fastest rates attained by some combination of these three estimators are written in Corollary 2.5
3

---

Table 1:
Upper bounds on maximal quadratic risks of three procedures
E (0,
7 7>1 1
Plug-in estimator
K² (nAn)>
K² (aAn)r
+
k3 20v1
= R
(Non-Interactive PM)
Thresholded estimator
K² K2(1-1) A [a"nj7
min R1, 12).
PM)
Two-step procedure (Interactive PM)
R2
We finally give lower bounds on the maximal quadratic risk, over all estimators and all (non-interactive and sequentially interactive) privacy mechanisms. These lower bounds are optimal for y 2 2 as they match our fastest rates. Unfortunately for 7 E (0, 2), gap of factor K" remains between our lower bounds and fastest rates. All proofs are in [].
1.4 Related Literature
To the best of our knowledge, estimating non linear functionals under global DP has been considered by [2]. The authors estimate the entropy, the support size and the support coverage of discrete distribution in the context of global differential privacy. In each setup they show that the cost of privacy is relatively small when compared to the standard (non private) setup. Their upper bounds allow quantify the amount of privacy that we can have without deteriorating the estimation rates.
We study for the first time the estimation of the nonlinear power-sum functional F-, for any real 7 0 in the context of LDP. The case 2 has been considered in the LDP setup, for smooth distributions in [5], and for testing discrete distributions in [3]. In (5), the association of a plug-in estimator and Laplace mechanism is optimal among all non-interactive mechanisms, whereas a sequentially interactive procedure improves dramatically the minimax rates. We will also try to further understand when such phenomena hold for different values of y, in particular when the functional F, is less smooth for 7 <
In non-private settings, it has been shown different behaviors for estimating F, according to the observations scheme, namely faster rates are attained in the multinomial setup [18] than in the Gaussian vector model [9] see details below. We will see that due to the LDP setup our rates are similar those proved in the Gaussian vector model by [ though our plug-in type estimator an analogue of the MLE analyzed in the multinomial setting by [8]
Standard (or multinomial) setting: When the L.v. Ii, ...; 2n observed, 18] show that the maximal
quadratic risk of the maximum likelihood estimator (MLE) in estimating F,, 7 > 0, is
K2
(2((1-)
1
2 1 EE(1)) +
1 + nonn-2k1 2(x-1) 1
+ n 722
In this model, the MLE of p& is the average of the 1 over from to n. These results entail that the MLE achieves the minimax rate n when 2 3/2. However, when the regularity y decreases below 3/2, the rates of the MLE get slower. In particular, the MLE does not achieve the minimax rates of estimation of F,, when 0 < y 3/2. For 0 <<<- the difficulty of estimation increases, especially if the alphabet size K is large, which may even prevent from a consistent estimation of F; (i.e. from the risk of the MLE to converge zero). More precisely, the MLE consistently estimates Fz, 0 7 < 1, if and only if, the sample size is large enough satisfy > K//7,
For the values of < 3/2, the minimax rates in estimating F_ roughly correspond to the performance of the MLE (written above) with n replaced by n log n [17]. These faster rates have been attained through a different estimator that uses best polynomial approximation of the functional pi for small values of Ps. which allows to gain a log factor in the bias. This method has been largely employed in the literature since the pioneer work by [22]. the Gaussian white noise model. The best polynomial approximation technique has been used for estimating the IL, norm in Gaussian setting 7. the LL, norm in the Gaussian white noise model [5), the entropy of discrete distributions [29], the entropy
of Lipschitz continuous densities [16]. In the multinomial setting, | studied the estimation of the

---

Rényi entropy of order a > 0 and [33 extended these results to more general additive functionals of the form Σ k= (pp),, for 4-times differentiable functions yp
Gaussian vector setting: the observations are y/ = 8, + c Ei, -a.i=..... K where (#1..... 0x) are unknown parameters, > 0 is known, and &, are i.i.d. standard Gaussian random variables. The authors of [9] show that there exists an estimator based on best polynomial approximation with the following error bound see (14) in the proof of their Theorem
( - R3)
22
E²
07 Σ
K
1 2
0
0
1 7>1
log" (K) log( K)
for any real >> When 7 E (0, 1), this bound is equal to e K²// log" (K) and turns out to be minimax optimal [9]. Besides, the authors show that better rates can be achieved if y is an integer. Namely, there exists an estimator with the following error bound, see Theorem in (9)
E (
= + 210012--2
(2)
for any integer > 2 1. In this special case of an integer y, the rate (2 is achieved by a simple estimator that has bias.
2 Estimators and results
We aim at estimating the power sum functional Fj(p) Σ Ph. for E (0, c0), in the LDP setting where we only have access to privatized versions 21, ,n of the sensitive original data Lid. T1...., Zn ~ p. The sensitive random variables I1, In are i.idd distributed according to the discrete density model P(z; k) pk for h = 1...., K where the unknown parameter
p = (pi...., PK) belongs the set P = {p 10 E Ps =1} of discrete distributions with alphabet size K. The .., Fn are not publicly available; instead they are used as inputs into a privacy mechanism (PM), order to produce available sanitized observations 21, ... Zn. We use the sanitized observations to estimate the functional Fyy.
Notation:
The symbol x Sn y means that the inequality S C.y holds for some constant C, depending only on We denote min(x,y) y) by x A y, and max (2, y) by x V y.
2.1 LDP setup
The privacy mechanism PM also known as channel or randomization, is submitted to the constraint that it is a-locally differentially private (LDP) for some a > O. This means that the PM generates the private samples using a conditional distribution Qi(-|24,, 21, 2-- such that
Qi(- 21,..., 21-1) S e", for all = 1,...,
sup
(3)
Ai 1 Qi(-12) 21, 21..,, 2
with the convention that (z1,..... 2 } is the empty set for i These PM are called sequentially interactive, as each Q; is allowed to use previously published samples 21...., 2;-1- We are also interested in the sub-class of non-interactive PM which not allowed to use previous released data. A non-interactive PM generates each z, only accessing via conditional distribution of the form Q+(+1z). We assume from now on that the level of privacy belongs (0, 1) and satisfies a²n 1.
2.2 Non-interactive privacy mechanism (NI PM)
We introduce a non-interactive PM, denoted by Q(TT), Given the original data x,, individual i generates a random vector z; (..1..., =i) using the Laplace non-interactive privacy mechanism ((NT) defined by
Wiks where the Wik are i..dd Laplace distributed with density (" (xp(-lx)). Note that Was are all centered, with variance 2. Setting 2, one can readily check that the channel Q(NT) above is an o-LDP non-interactive mechanism, see 3 and the references therein. We denote the mean of the
(INI)
Zik (2.=k)
k: 1,...,K, K,
(4)
privatized observations in the tth box by 24 E Zik.
5

---

2.3 Plug-in estimator based on NI PM
The first estimator we introduce is an analogue of the MLE [8] discussed in the introduction. uses an unbiased estimation of the parameter p. by averaging the privatized samples in each bin, thus using the 2g. kt = ,....,,K K. The resulting estimator F', of F, is actually not a MLE in our privatized context, hence we call it plug-in estimator. The plug-in estimator uses the privatized data produced by the NI PM above, and then estimates separately each term F-, Pk of the functional
F = > (k) as follows:
K Σ
(2(K) with (k) (To.e) (+x])²
(5)
where Tio.2] [-] is the clipping operation defined by To.23 lvl = (v) A 2. As 2 is an unbiased estimator of pk with fluctuations of order (vPp(1 P*)/n) m)) + (a/vaa /v///. the quantity
c/ V Va where с 2 1 is a numerical constant, can be seen as a threshold that is just above the noise level in the available data. Write p²² (respectively pT)) the vector containing the thresholded values of pt Pk (pr 2 T) (respectively pk 1pp < T)) for k E [K].
Theorem 2.1. For any y > 0 and E Pk, the quadratic risk of the estimator is bounded by
K2
11
2(7-2)
11
2y
Ep and thus is uniformly bounded over all E Pk by
Sx (a?n)7
1 (x22)
+1211
2y
(6)
(a2n)²
a 2n
K² [ Fx)2 Sn (a²n)) + 1 (221)
(T A-AKK)S-21
sup
a²n
PEPx
This upper bound on the quadratic risk of the plug-in estimator grows quadratically with the alphabet size K, even for arbitrarily large K. This poor performance unfortunately inherent to the plug-in estimator, as shown by the lower bound in Proposition] (.2 Accordingly, we will correct the plug-in estimator in the next section to reduce the effect of the alphabet size K on the risk.
Proposition 2.2. For any 7 > 0, Y # 1, and integer K 2 2, the maximal quadratic risk of F., is asymptotically bounded from below by
K2
sup E [F, F.) 23 (a2n)) PEPK
as 12 - 00
The maximal quadratic risk of the plug-in estimator has therefore a quadratic dependence on the alphabet size K, and thus it is necessary and sufficient to have > K2/ initial observations for this estimator be consistent (in the sense that its risk converges to zero). This rate slower than that of the MLE in the standard setup without privacy constraint [18], though both our plug-in estimator and the MLE have similar definitions based on the plug-in principle. Indeed, the MLE of [T8] is less sensitive to the support size K than our plug-in in estimator, as the MLE is consistent regardless of the alphabet size K, as soon as y > 1. In addition, when y E (0, 1). the MLE is consistent if, and only if > k//,, This better performance of the MLE can be explained by the fact that [8] benefits from direct observations &e == Σ (z.=k) that have non-homogeneous fluctuations, i.e. a variance Var( = P (1 - pn)/n that scales with the signal pk- By contrast, our plug-in estimator employs privatized observations ån resulting from the Laplace PM in
4 which have nearly homogeneous fluctuations with a variance Var that scales with 2 x (a n2) regardless of k E [K]. Thus,
both situations are different for small pk. which typically occurs when K is large since ΣK Σk=1 Pk 1.
Link with the Gaussian vector model. The observations released by the Laplace PM in 4 are in fact close to the observations of the Gaussian vector model [9] and, as a consequence, our plug-in estimator achieves similar rates to those obtained in 9 Indeed, our observations (&x (&*)<E(K) can be seen as homoskedastic random variables having common characteristics to the Gaussian random variables in [9] with variance eg = 1/(a2n). Let us check that our upper bound (6) implies, up to log factors, the same bound as from [9] (The logarithmic gap comes from the fact that we do not use

---

the best polynomial approximation, unlike 1 see the introduction for details.) The square root of in )
the second term 112-112/// (a²n)
6 is bounded from above by
Ex 7-2 (m+r))
k= Pk
Pe Pk
' (ma2r) Vo
|p 111l--1 Va
a2n
a
Va
which corresponds to the square root of the second term of ( up to log factor. Thus, our bounds similar to those in for specific variance ej. Note the difference that we impose the constraint E Px. whereas [9] consider all E TR
2.4 Thresholded plug-in estimator based on NI PM
Our objective is reduce the effect of the alphabet size K on the risk of the plug-in estimator. A natural solution is to not estimate the small probabilities Ps. as their contribution to the functional Fy is relatively weak, while they may add much fluctuations to the plug-in estimator F, >x=1 F7. Accordingly, we introduce a refinement of the plug-in estimator, called thresholded plug-in estimator F,, which does not estimate all components pk of the sum F = Σx P.. Similar to the plug-in estimator, this estimator F,, uses the private sample (zi)))E())ME{{] produced by the non-interactive PM in
The definition of F, split two cases, y E (0, and y > 1. When y E (0, we simply set F, = k Ey, meaning that F,y is equal the trivial estimator 0 if K 2 -- and to the plug-in estimator F,, otherwise.
For 1, the thresholded estimator F, uses the plug-in estimator only on the significant components P7 of the sum F, = >x P.. via a truncation of the small probabilities pk- This two-step procedure first detects the significant probabilities pk that are above the threshold = c/ Va and then estimates the part of the functional Fy induced by those Pk. Assume that the sample size is 2n for
convenience, and split the data in two samples (1) (z) ,....,hh" 21 and ( = (x/²3) ....,."")) (2)). which 1,2, the non-interactive mechanism
The individuals owning the data 2(0),
(4) generates 2 (+) = (2(1) ...... =xxx) for i = I...., n. Denote the two sample means of the hthh bin by (x)
) to detect large values of the underlying probabilities as follows. For each & E [K], if af is strictly smaller than the the empirical threshold f,
(x) Σm Pik = 1,2. We use the (z(²)),
log (Kn)
= 192a
2n
then we do not estimate (k). The threshold chosen larger than by a logarithmic factor, only to have high probability concentration for the (=(²))x around their means (pk)s. Otherwise, when
N f, we estimate (k) using the same plug-in estimator as in 5 This gives the following estimator F,, of Fy, y 1,
K F,
FL(()) with (k) = (Tio.2) (2) 1 12 A=1
where the (E are used to estimate the functional. The independence between (e(() > and (z(²)) allows us to avoid cumbersome statistical dependencies between the two stages of the procedure.
Theorem 2.3. For any integers K,n satisfying > 2 log(K), the quadratic risk of F,y is uniformly bounded over all p E Pk by 1) (0,1) 1):
K2
sup E (F FF) Sn (1(1-)) A pcPx
(a²n)
2) 1:
(log(Kn))>~>
)
K22 (1og(K)))))
K3-21 V1 ann
sup E. [[F F2)9] Sn PEPK
(a?n))-1
(a2n)
7

---

Compared to the plug-in in estimator performance, the quadratic risk of the thresholded estimator F,, is much less sensitive to the alphabet size K when y 1 and K is large. Indeed, our bound on this risk is minimum between two error terms where the left-term only depends on K logarithmically. However, the new logarithmic factors that come from our use of high probability concentration are not satisfactory. We remove them in the next section, replacing the current non-interactive PM with sequentially interactive PM.
2.5 Two-step procedure based on sequentially interactive PM
A sequentially interactive PM is allowed to use the prior released (sanitized) data to encode our present knowledge in the new released data. The idea is to rewrite the functional F- =k=1 Pk: (k). so that we first compute the plug-in estimator fk-1(k) of F and then build on Fq-1 to estimate the functional Eg. In this two step procedure, half of the sample is released via the Laplace mechanism 4 and is used for computing (k)), then the other half is released through a sequentially interactive PM encoding the information from ( This procedure is only applicable for > since it requires to compute Fy-1- The sequentially interactive PM we consider here is similar the ones studied for the specific functional F2 (7 2) in continuous setting [5] and identity testing 3
Assuming that the sample size is 2n for convenience, we split the data in two groups x!1)
(of").... xh and (:) (ar (2)
). The individuals owning the data (11) use the non-
interactive mechanism i.e.
Q(Nn:
2k
(1) 1 (1 mk + a
Wik:
K,
which generates e. (2 (=("),
2 for i I....,m n. Denote this first sample by z(1)
(1) These sanitized data allow us to estimate (k)1(k) (px)r=1 using the plug-in estimator i.c
(2 1 (k)
T [0,21
(1)
[T022 2k # 7-1
We then design estimator of Σ P possible with the following sequentially interactive mechanism that encodes prior information F(1) in the released data (2).
(k) which can be seen proxy of F,.. This is
1 11 (イ
Q
(2) Za, with probability 2
where
-2-11e e- and with the following sequentially interactive estimator
(2) F,
2
Denoting the second sample by 2(2) (2)3)
(22))
easy see that the privatized sample
(2(), 2(2) satisfies 33) and thus is a-LDP.
Theorem 2.4. For any r >> 1 and p Pk. the quadratic risk of the sequentially interactive estimator F.y is bounded by
(F,- p.))] Sn (a2n)6r-1)AT + 1 (x23)
12²
1p
2
27 2
(n²n)²
+
(+22)
a
and thus is uniformly bounded over all p Pk by
sup E. (F. F2)
Sx: (a²n)r-1
1
PEPx
8

---

For 1, the rate of the two-step procedure is therefore independent of the alphabet size K, unlike the rates of the plug-in and thresholded estimators. Hence, when K' is large, this rate is faster than those of the two (non-interactive) estimators. In particular, it is equal to (a²n)-² as soon as Y 2 2, which is the minimax optimal rate (see next section). Conversely for small K and 7 E 2). this rate is slower than those of the plug-in and thresholded estimators. Accordingly, none of the three estimators overall better than the others, and we discuss the choice of estimator in next section.
2.6 Optimality of the Results
Among the three estimators we proposed. the choice of estimators depends on the problem parameters K, 7. The following recipe leads to better estimator E.g. If K S va?n, define E., as the plug-in estimator Fy: otherwise (when K > Va2n), Fry is equal the thresholded estimator F-y for y < 1, and to the sequentially interactive procedure Fr, for y > 1.
Corollary 2.5. The quadratic risk of E,y is uniformly bounded over all E Pk by 7) E (0,
sup E (EE - F.)²] Sn x201-)) A PEPk
K²
(8)
(a?n)7
2) y E (1,3/2):
E [ -F,,a] Sn (a2n)--1 A ( K2
1
k3-21
sup
[a?2]) +
(9)
a²n
PEPk
3) y E (3/2,2):
sup E (E. Fag²| Sn (a²n) ( K2
(a²n)) + 1 -2m)
(10)
PEPK
4 1722 2:
sup E (E,
Sn a²n
(11)
PEPK
The rate (TT) for y 2 2 can be seen as the private parametric rate, which is minimax optimal (see lower bounds in Theorem 2.6 Then for 7 2), the smaller y is, the slower the rates are. Specifically, each upper bound in (8) to (TO) is the minimum of two error bounds, with a phase transition at K x Va²n. Above this transition level, i.e. when K Z Va the upper bounds ( and (10) for E (1, 2) are equal to the first error bound (a²n)- which is free of K. Below the transition level, i.e. when K S Vo they are equal to the second error bound that depends on K. 21, the upper bounds on the maximal quadratic risk of É., increase with K as long as K S Va and become equal to (a²n)- for any K larger than Va²n. In contrast, the upper bound (8) for y E (0, depends on K regardless of the value of K. Thus, the rates get slower as the power y decreases, where 7 can be seen as a smoothness indicator of the function + x² and thus of the functional F, = Ex Pk.
Hence, for
We give lower bounds over all estimators and all a-LDP sequentially interactive mechanisms. Recall that non-interactive mechanisms are just a special case of sequentially interactive mechanisms, thus lower bounds hold in particular for non-interactive mechanisms. In the special case where K < is a numerical constant, the next lower bounds match the rate of the plug-in estimator (Theorem 2.1 for any 7 > 0, # 1.
Theorem 2.6. For any y > O. y # and integer K 2 2. we have the lower bound
inf Q.F
sup E
+ F2)2 [ Z ann (a?n)>
1
1
PEPx
where the infinum is taken over all estimators F and all a-LDP sequentially interactive PM Q.
In the general situation of any K > 2, we thus have the minimax optimal rate (a²n)-1 when y 2 2, which is achieved by the sequentially interactive estimator (Theorem) 2.4 contrast for 7 E (0, 2). the next lower bounds depend on the alphabet size K.

---

Theorem 2.7. For any integer K 2 2, we have the lower bounds 1) E (0,1):
K²-
E - -P)3 Zn ~201~>) A (n(e2a e-20)22)
inf sup
(12)
Q. pEPx
2) 7 E (1,2):
1
K²
inf inf sup Q F PEPK
E
2s [622 - 2a (2]222|((67-)
A [6220 e- e-22))22)
(13)
where the infimum is taken over all estimators F and all a-LDP sequentially interactive PM Q.
Note that e2a e when a is small. Then the lower bound (2) for 7 E (0, 1) matches, up to a factor K", the quadratic risk of the thresholded estimator (Theorem 2.3 or equivalently the rate (8) of the combined estimator E.,. For y E (1, the situation is slightly more involved, but one can see again that there a gap of factor K" between some terms of the lower bound (13) and the upper bounds (9) and (TO) of Corollary 2.5 Besides, reading the proof of lower bounds, one can check that this K -gap is tightly connected to the gap between the left-terms 1/ 1/(a2n)>(>-1 and 1/ 1/(a²n)>*
of the lower and upper bounds respectively, so that the optimality of the problem actually boils down to reducing this -ga.
Discussion In this first work on the estimation of the power sum functional F,, we focus plug-in estimator based on samples obtained using a non- non-interactive PM. Although its analogue estimator in the non private case known to be nearly minimax optimal, we show that our plug-in in estimator performs poorly in the LDP setting for large K (proving a tight characterization of its maximal quadratic risk). Hence, practical methods performing well in the non private systematically transferred to the LDP setting, which requires to design new statistical procedures. We then suggest a correction of this estimator using thresholding, which significantly improves the rates of convergence, removing almost the whole dependence of the risk in the support size K for large K. We finally get faster rates by combining these two previous estimators with sequentially interactive procedure. It is also important to highlight that all privacy mechanisms and estimators introduced here could be further investigated for other functionals, for example the Rényi entropy H- which is fundamental in information theory and is connected to the power sum F,, via the relation H,, log f.
should not be
We conjecture that upper bounds are tight, up to some logarithmic factors. In future work, this logarithmic factor should be reduced via the best polynomial approximation method. This is similar to the line of work in the standard setup (without privacy constraint), where the analogue of plug-in estimator (the MLE) is known to be nearly minimax optimal up to a poly-logarithmic factor [14], while the the best polynomial approximation method closes this logarithmic-gap and minimax optimal [1 [29] Leaving aside the logarithmic factors, we conjecture that our lower bounds are not optimal, up to a factor K7. The two fuzzy hypothesis theorem is often used in the standard (non-private) setting to derive lower bounds on the estimation rate of functionals such as the power sum F,, A challenge in the LDP setting is to provide such turnkey tools that help prove universal lower bounds.
Another challenge is understand when sequentially interactive procedures outperform non- interactive ones. When y > 1, we have gained logarithmic factors in our error bounds by considering sequentially interactive procedures. However, because the optimal rate of non-interactive mecha- nisms is not proven, it is unclear that our logarithmic gap between non-interactive and sequentially interactive actually exists. The estimation of power sum functionals in the context of local differential privacy proves to be a rich topic potentially difficult to solve sharply in all possible cases.
Acknowledgments and Disclosure of Funding
The authors acknowledge financial support from GENES and the French National Research Agency (ANR), under the grant "Investissements d' d'venr"" (LabEx Crode//ANR-II-LAB--O00
10

---

References
[1] Acharya, J., Orlitsky, A., Suresh, A.T., and Tyagi, H. (2015) The complexity of estimating Rényi entropy. Proceedings of the Twenty-Siae SSttt Annual ACMSIAM Symposium Discrete Algorithms, SODA 2015, pages 1855-1869.
[2] Acharya, J., Kamath, G., Sun, 7., and Zhang. H. (2018) INSPECTRE: Privately estimating the unseen. Proceedings of the International Conference Machine Learning, PMLR 80.
[3] Berrett, T. and Butucea, C. (2020) Locally private aon-asymplotic testing of discrete distributions is faster using interactive mechanisms. NeurIPS, 33.
[4] Butucea, C., Dubois, A., Kroll, M. and Saumard, A. (2020) Local differential privacy: Elbow effect optimal density estimation and adaptation over Besov ellipsoids, Bernoulii, 26(3):1727- 1764.
[5] Butucea, C. and Rohde, A. and Steinberger, L. (2020) Interactive versus non-interactive locally, differentially private estimation: Two elbows for the quadratic functional. arXiv:2003.0477;
[6] Butucea, C. and Issartel, Y. (2021) Supplementary Material to "Locally diferentially private estimation of nonlinear functionals of discrete distributions', NewrlPS, 34.
[7] Cai. T. T. and Low, M. G. (2011) Testing composite hypothesis, Hermite polynomials and optimal estimation of nonsmooth functional. Ann. STatist., 39: 1012-1041.
[8] Chan, T.H. H., Shi, E. and Song, D. (2012) Optimal lower bound for differentially private multi-party aggregation. ESA'12 Proceedings, 277-288
[9] Collier, O., Comminges, L. and Tsybakov, A. B. (2020) On estimation of nonsmooth functionals of sparse normal means. Bernoulli, 26(3):
[10] Duchi, J. C., Jordan, M. and Wainwright, M. J. (2018) Local privacy and minimax bounds: sharp rates for probability estimation. NeurlPS, 26.
[11] Duchi, J. C., Jordan, M. I. and Wainwright, M. J. (2018) Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):182-201.
[12] Dwork, C., McSherry, F., Nissim, K. and Smith, A. (2006). Calibrating noise to sensitivity in private data analysis. Theory of Cryptography, 265-284.
[13] Fukuchi, K. and Sakuma, J. (2017) Minimax optimal estimators for additive scalar functionals of discrete distributions,EEE International Symposium on Information Theory (ISIT), 2017, 2103-2107.
[14] Giné, E. and Nickl, R. (2016) Mathematical Foundations of Deffesie-iimnsiionall Statistical Models Cambridge University Press, NY
[15] Han, Y., Jiao, J., Mukherjee, R. and Weissman, T. (2017) On estimation of LL, norm in Gaussian white noise models. arxiv: 1710.03863
[16] Han, Y., Jiao, J., Weissman, T. and Wu, (2017) Optimal rates of entropy estimation over Lipschitz balls. arxiv: 1711.0214)
[17] Jiao, J., Venkat, K., Han, Y., and Weissman, T. (2015) Minimax estimation of functionals of discrete distributions. Transactions on Information Theory, 61(5): 2835-2885.
[18] Jiao, J., Venkat, K., Han, Y. and Weissman, T. (2017) Maximum Likelihood Estimation of Functionals of Discrete Distributions. Institute of Electrical and Electronics Engineers (IEEE), 63(10):6774-6798.
[19] Joag-Dev, K., Proschan, F. (1983) Negative association of random variables with applications. The Annals of Statistics, vol 11, no. 1. pages 286-295.
[20] Joseph, M., Mao, J., Neel, S. and Roth, A. (2019) The role of interactivity in local differential privacy. IEEE DOI 10. 200.00//

---

[21] Joseph, M., Mao, J., and Roth, A. (2019) Exponential separations in local differential privacy. arxiv: 1907.00813
[22] Lepski, O., Nemirovski, A. and Spokoiny, V. (1999) On estimation of the L, norm a regression function. Probub. Theory Related Fields, 113: 221-253
[23] Murphy, R.L.,, Srinivasan, B., Rao, V. and Ribeiro, B.(2019) Janossy Pooling: Learning Deep crmmutattionInvariann Functions for Variable-Size Inputs, ICLR
[24] Rohde, A. and Steinberger, I., (2020) Geometrizing rates of convergence under local differential privacy constraints, Annals of Statistics, 4865):2646-2670.
[25]
Tsybakow, A. B. (2009) Introduction to Nonparametric Estimation, Springer series in statistics.
[26] Valiant, G. and Valiant, (2014) An Automatic Inequality Prover and Instance Optimal Identity Testing; FOCS
[27] Wainwright, M. J. (2019) High-dimensional statistics, Cambridge Series in Statistical and Probabilistic Mathematics, 48, Cambridge University Press, Cambridge
[28]
Wasserman, L., and Zhou, S. (2010) A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375-39) 2010
[29] WU, Y. and Yang, (2016) Minimax rates of entropy estimation on large alphabets via best polynomial approximation. IEEE Transactions on Information Theory, 62(6): 3702-3720.
[30] Zaheer, M., Koturr, S., Ravanbhakhsh, S., Poczos, B., Salakhutdinov, R., and Smola, A. (2017)
Deep Sets. Advances in Neural Information Processing Systems
12


Reviews:
[{"review_id": "ye32x30mDhq", "reviewer": "Reviewer_bSYV", "summary": "This work considers locally differentially private (LDP) estimation: in\nparticular, the authors estimating functionals of discrete distributions, i.e.,\nfor a discrete distribution supported on $K$ elements with probabilities $p_1,\n\\ldots, p_K$ the goal is to estimate the quantities $F_\\gamma = \\sum_{k=1}^K\np_k^\\gamma$ for some smoothness parameter $\\gamma > 0$.  In general, the closer\n$\\gamma$ is to $0$ the harder the estimation problem becomes.\nThey distinguish between interactive and\nnon-interactive locally private mechinisms.  In interactive LDP mechanisms\nagents can release information that depends on the already released information\nof other agents that is already privatized.  In non-interactive mechanisms\nevery agent can only release privatized data depending only on their own data.\nThe authors provide a fine-grained sample complexity analysis of both non-interactive\nand interactive estimators for estimation of the functionals $F_\\gamma$ for\ndifferent regimes of the smoothness parameter $\\gamma$.\n\nWhen the smoothness parameter $\\gamma \\in (0,1)$ the authors give an estiamator\nthat is $\\alpha$-LDP, uses $n$ samples and achieves mean squared error\n$\\min(K^{2 (1- \\gamma)}, K^2/(\\alpha^2 n)^\\gamma)$.\nThey also show a sample complexity lower bound of\n$\\min(K^{2 (1-\\gamma)}, K^{2 -\\gamma}/(\\alpha^2 n)^\\gamma)$. The upper\nand lower bounds match up to a factor dependending on the support\nof the distribution: $K^\\gamma$.  They have similar upper and lower\nbounds for $\\gamma > 1$ that have roughly the same gap.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Providing LDP mechanisms and estimation algorithms is a well-motivated and\nimportant problem with a lot of prior work by now.  This paper fits in this\nline of research and aims to analyze an estimation problem that has been\npreviously studied from a classical (non-Differentially Private) statistical\nviewpoint.  The problem of estimation of power functionals $F_\\gamma$ described\nhere seems to be of interest as it reveals usefull information about the\nunderlying distribution.   I think it would be beneficial for the paper if the\nauthors expanded more on the applications and the usefullness of estimating the\npower functionals $F_\\gamma$ -- especially for the more challenging cases of\n$\\gamma$ close to $0$.\n\nI found the distinction between interactive and non-interactive mechanisms\nto be interesting.  However, in this case the results in the two settings\nturn out to be very close (the authors are able to shave off log-factors\nusing interactive mechanisms).  A weakness of this work is that the estimators\nproposed are rather straightforward: adding laplace noise and using\na thresholded plug-in estimator basically gives the best results in this work (up\nto log-factors).  The paper is well written, but I think it would benefit from\na cleaner and more high-level presentation of the main results.\nI think Table 1 should include both (the best) upper and lower bounds clearly\nstating the gaps (perhaps ignoring the interactive vs. non-interactive distinction).\nOverall, I am leaning towards acceptance since the model and the task considered here\nare interesting and well-motivated.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "u5z0y2Rm__E", "reviewer": "Reviewer_AFYC", "summary": "This paper studied the problem of estimating non-linear functionals of discrete distributions (more precisely, the power sum functions $F_\\gamma = \\sum_k p_k^\\gamma$) with LDP constraints. Based on the well-known plug-in approach, the authors proposed three private mechanisms: \n\n1. Non-interactive: estimate each probability using the Laplace mechanism, and use the plug-in estimator. \n2. Non-interactive: apply the above estimator, but truncate all small probabilities to zero; the truncation is conducted using sample splitting. \n3. Interactive: using the Laplace mechanism to estimate each $p_k^{\\gamma-1}$, then use the sampling-based estimator (as well as sample splitting) to estimate $F_\\gamma$. \n\nThe authors also proved two minimax lower bounds (Theorems 5.1 and 5.2). However, Theorem 5.1 does not give the important dependence on K (as K=2 is considered), and Theorem 2 does not match the upper bound. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The functional estimation problem under LDP constraints is definitely interesting - there are still many technical difficulties unsolved in this problem. The current paper provides a nice trial to this problem; however, in my opinion, this paper does not tackle the most important ones. To name a few: \n\n1. This paper restricts to the plug-in approach, and only proposed a few private mechanisms around it. Even for the non-constrained case, it was known that the plug-in approach is suboptimal - so considering only the plug-in approach in the LDP case is also not sufficient in my opinion. Also, the authors only considered *a few* private mechanisms based on the plug-in approach without sufficient motivation - the choice of the mechanisms seems arbitrary. In the literature the proposed mechanism should be motivated by a matching lower bound for all possible mechanisms, but the lower bounds in this paper do not match the upper bound so fail to support the optimality arguments (see next point). \n\n2. The lower bounds shown in this paper are not tight. Theorem 5.1 only considers the case K=2, but it is widely believed that the functional estimation problem only becomes interesting when the alphabet size K is large. Theorem 5.2 has the dependence on K, but it is far from the dependence in the upper bound so potentially very loose. Besides, the proofs of these lower bounds are very standard, and essentially directly follow from the tools in [8] and [4]. In summary, there is no proof of optimality for the proposed mechanisms in this paper. \n\n3. The logarithmic improvement based on polynomial approximation, an important aspect of the problem, is missing in both the upper and lower bounds. For the upper bound, is there a private mechanism to perform the polynomial approximation based estimator which is known to be minimax rate-optimal in the non-constrained case? For the lower bound, is there a good way to adapt the fuzzy hypothesis testing approach to the private mechanism? I think those are central questions in the study of functional estimation under privacy constraints, but the current paper answers neither of them. \n\nIn addition to the above major comments, the writing of this paper could be greatly improved. Currently a lot of statistical rates are listed without sufficient discussion, and the reader could be easily lost with the heavy notations. \n\nPost-rebuttal feedback: \n\nThanks to the authors for the detailed feedback. The rebuttal alleviates my following concerns: \n\n1. The motivation of studying plug-in based approach. In my previous review I am mainly questioning the lightness of new algorithmic ideas, but in the rebuttal the authors provided an important message which I overlooked: truncation is necessary on top of the plug-in approach to remove the heavy dependence on $K$ when $\\gamma>1$. This point indeed adds to the algorithmic idea. \n\n2. Possible gaps between upper and lower bounds. In the rebuttal, the authors mentioned that they closed the gap when $\\gamma\\in (1,2)$ and $\\sqrt{n\\alpha^2}\\lesssim K$. Therefore, currently a gap only shows up when $\\gamma<2$ and $\\sqrt{n\\alpha^2}\\gg K$, which looks better than the original manuscript. \n\nHowever, the above concerns are only alleviated but not fully addressed. On the algorithmic idea, truncating the small probabilities is very natural: if $\\gamma>1$, the contribution of small probabilities to $F_\\gamma$ becomes tiny, while directly applying an LDP mechanism to small symbols adds too much variance. This has been observed in the literature on the estimation of $F_\\gamma$ without the LDP constraint (although only reflected in the analysis but not in the estimator) - so I am not entirely sure of the significance of this idea. Regarding the gap, it is always not that satisfactory to see a gap in the asymptotic scenario (i.e. when $n$ is large). I believe a potential improvement should be possible. \n\nIn summary, I think this manuscript presents some interesting contributions and I'm willing to increase my score from 4 to 5. However due to the above concerns I still think this is a borderline paper and I tend to recommend rejection - there are many writing/clarity issues to fix, some new results to check, and more importantly, potentially fully closing the gap after some additional effort. But I am fine to see it accepted too - if so, please add the new results, clearly prove the lower bound under interactive protocols (as other reviewers point out), and improve the writing & organization. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no negative societal impact of this work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "O9pwlaz_Imc", "reviewer": "Reviewer_VFZT", "summary": "This paper deal with the locally differentially private estimation of the power sum over the discrete distribution. The authors introduce the plugin estimator and thresholded plugin estimator for estimating the power sum under the non-interactive setting, and they also develop an interactive mechanism for estimating the power sum. Their theoretical analyses of these estimators reveal the upper bounds of the estimation errors. Furthermore, the authors derive the lower bound on the estimation error of the plugin estimator and confirm that the lower bound matches the derived upper bound in a certain situation, meaning that the upper bound is tight. Moreover, the authors present the fundamental lower bound on the private estimation error in the interactive case, giving some insight into the optimality of the proposed mechanism for the interactive case. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "This paper tackles the well-motivated problem of the locally differentially private estimation of the power sum and is well-written and technically sound. Hence, my current decision is acceptance. \n\nThis paper reveals three estimation error bounds corresponding to three private mechanisms for estimating the power sum. All of these results are solid contributions. I'll mention some drawbacks of these results; however, these drawbacks have little effect on the paper's score.\nThe tightness of the estimation error upper bound of the plugin estimator is not proved when $\\gamma \\ge 1$, and $K$ is small.\nBecause the optimality of the non-interactive mechanism is not proven, it is unclear that the logarithmic gap between non-interactive and interactive actually exists.\nThe optimality of the interactive mechanism for $\\gamma \\in (0,2)$ is proven only when $K \\asymp n(e^{2\\alpha}-e^{-2\\alpha})^2$.\n\nMinor comments:\nThe left-hand side of the inequality in Theorem 5.1 is independent of  $K$, which is different from the statement in the proof. $\\mathcal{P}(2)$ should be replaced by $\\mathcal{P}(K)$.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is better to summarize the limitations of the results. The potential societal impact is not discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "LLWSlrwKeUE", "reviewer": "Reviewer_j1d8", "summary": "The paper looks at upper and lower bounds for LDP estimation of a particular family of functionals of a discrete probability distribution. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "This paper looks at estimating a particular family of functionals of a discrete distribution in the *local* model of differential privacy. Given a distribution $(p_1,…,p_K)$ on $[K]$, the goal is to learn $\\sum_i p_i^\\gamma$ for a given parameter $\\gamma \\in (0,1)$. This is closely related to the Renyi entropy of the distribution. For example, when $\\gamma=2$, one is estimating the collision probability of two independent samples from the distribution. \n\nStrengths: \n\n- The paper is generally clear and technical statements are crisp and easy to understand. \n- The paper considers both a straightforward estimation algorithm (which estimates the individual probabilities and then estimates the functional based on those) as well as a two-step estimator that combines an initial estimation phase with a subsequent phase. As I understand it, the combination eliminates one source of bias in the estimator. \n- The paper provides lower bounds that match the upper bounds in some parameter regimes\n\nWeaknesses: My hesitations about the paper in its current form center around “presentation” issues that make the ultimate contribution hard to evaluate. Specifically, I feel the paper needs work on (1) motivation, (2) comparison to previous work, and (3) discussion and contextualization of the technical statements.\n\n- Motivation: There is no discussion of why this particular family of estimators is important or should be a central object of study in the LDP model. Is there a reason why these particular functionals are characteristic of more general estimation problems? Are these functionals somehow representative of “symmetric” functionals of the distributions (those that are invariant to permutations of $[K]$)? Are they important in practice? For which values of $\\gamma$?\n- Modeling: The paper considers the normal notion of noninteractive LDP (which is fine). However, for interactive LDP it considers only a special case sometimes dubbed “sequential interaction”, in which participants generate a single output each, but possibly taking into account the outputs of previous participants. (See bottom of page 3 in the submission.) There are more general types of interaction possible—see the work of Joseph, Mao, Neel and Roth (https://arxiv.org/abs/1904.03564 and https://arxiv.org/abs/1907.00813) for example. The more specific model used here is fine for upper bounds, but it wasn’t clear to me if the lower bounds developed by the authors are specific to the sequential model. \n- Context and previous work: How does this work fit into the larger body of work on LDP hypothesis testing and learning? What other functionals have been considered? Is there work, for example, on estimating entropy. Also, how does it compare to the central-model results such as those in Acharya et al (http://proceedings.mlr.press/v80/acharya18a/acharya18a.pdf)?\n- Comparison to nonprivate estimation: I found it confusing in Section 1.1 that some parts of the discussion appeared to be specific to the MLE, and others seem to apply to all possible estimators. A lot of detail is provided about estimation in the Gaussian vector setting, but it was not clear to me which parts of that discussion are relevant to the discrete setting considered here. (I’m not saying that work shouldn’t be discussed, just that the relevant lessons for discrete estimation should be clearly extracted.)\n- Discussing the results: I found it hard to digest the main results, for a few reasons. First, it was difficult to understand the regimes in which the upper and lower bounds match versus those in which they differ by a non constant factor. It was even hard to understand why the upper bounds don’t contradict the lower bounds :) I think there is probably a way to reformulate the bounds so that they are easy to compare. Perhaps the authors could add the lower bounds to Table 1, and further break the possible values of $\\gamma$ into a small set of ranges in which different simple behaviors emerge (e.g $\\gamma in (1,2)$ and $\\gamma>2$). As I mentioned earlier, it was also hard for me to understand just how general a set of protocols the lower bounds apply to. \n- The authors claim that their results extend to estimation of entropies. This claim should either be made explicit (e.g. stated as a theorem or conjecture) or qualified (“we conjecture that…”). In its current form, it inhibits further work by others on the topic, without providing a clear statement to which other authors can refer. This tends to have a bad effect on the community researching the topic.\n- Minor note: the paper uses the phrase “faster rates” and “slower rates” in a few places, and it was not always clear to me what the point of comparison was. For example, the abstract refers to a “faster parametric rate” of $\\sqrt{n\\alpha^2}$. Faster than what? \n- It would be good to explain in Section 4 *why* the combination of two independent estimates of $p_k$ leads to the elimination of the log factor in the upper bound. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors could do more to explain what gaps exist between their upper and lower bounds. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers appreciated the technical contributions of the paper. Their initial major concerns centered around the novelty of the ideas and various presentation issues around placing the work in its prior context in DP and statistical estimation. Author feedback revealed new results and an explanation of the paper's algorithmic ideas that helped convince the reviewers as to their novelty. I recommend acceptance, with remaining hesitation (from committee discussion) arising from a lack of opportunity to verify the new results or see concretely how the authors implemented their revision of the paper's presentation.

I wish to emphasize one presentation point that was raised in the reviews, but still not quite adequately addressed in the author feedback. It is extremely important for the authors to be crystal clear about the model(s) of local DP (non-interactive, sequential, fully-interactive, etc.) that they consider in each of their upper and lower bounds. As pointed out in the reviews, understanding the relative power of these models is an active area of investigation and it is a major source of confusion when the literature is unclear about which models various results/techniques actually apply to. The authors should also be aware that fully-interactive LDP does not collapse to central DP; separations are known, e.g., Corollary 1 of https://eprint.iacr.org/2012/373.pdf.
Decision: Accept (Poster)