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 92020 Cedex, France wew.ssssateeeeeeeeeeeeeee fr
Abstract
We study the problem of estimating non-lime non-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 zy, 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)2), 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 (Non-Interacee PM)
K² K2(1-1) A [a"nj7
min R1, 12).
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 (" <x((-l=)). 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.e1 (+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/va/ /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 Fy = Σ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) = (Iio.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 PR 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.)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
(a22)) +
(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 { Fo,
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 PEPx
E
2s [622 - 2a (2]222]((67-1)
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-38) 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": "gWkY-tX8RwD", "reviewer": "Reviewer_ztVm", "summary": "The paper considers the problem of estimating the power sum of discrete distributions p under local differential privacy (LDP) constraints, which is defined as $F_\\gamma(p) = \\sum_x p_x^{\\gamma}$. The paper analyzes three types of algorithms. \n\nThe first is the plug-in estimator which first estimates the distribution p by $\\hat p$ using Laplace mechanism and then the final estimate is simply $F_{\\gamma}(\\hat p)$. The paper characterizes the minimax mean squared error (MSE) for the plug-in estimator for $\\gamma \\in (0,1)$.\n\nThe second is a thresholded plug-in estimator which sets a threshold and the final estimate is only the sum of functionals over heavy elements. The paper shows that the estimator can achieve an MSE which depends only logarithmically on the alphabet size K.\n\nBoth above algorithms are non-interactive in the sense that each participant cannot see the message of other participants. The paper then presents an interactive algorithm that improves over the thresholded estimator by a logarithmic factor. \n\nThe paper also provides lower bounds which are off the upper bounds by a polynomial factor.", "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 paper considers an interesting problem and makes some nontrivial progress. However, the technical contribution still appears limited. \n\n1. The paper focuses on analyzing plug-in estimators and variants of them. In particular, the thresholded estimator can still be seen as a plug-in estimator with the estimated distribution being the thresholded distribution. The lower bound and upper bound provided in the paper don't match hence the paper does not provide a clear scope of how well plug-in estimators perform in general. For more general interactive estimators, the provided upper and lower bounds don't match as well. Hence the contribution of these results to the understanding of the problem is limited. The paper will be stronger if the paper can provide a clearer scope of the problem by closing these gaps.\n\n2. The writing of the paper can be improved. The paper states many results in the main paper and it is less clear to the readers what are the main theorems to look at. It would be better if the authors can emphasize some important results for better clarity.\n\nOverall, I think the contribution of the paper is limited hence I would tend towards a rejection.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "XYToyYcFYr", "reviewer": "Reviewer_H2n9", "summary": "This paper studies the problem of estimating non-linear functionals of discrete distributions\nin the  local differential privacy model. The authors first study the non-interactive case and provide both lower and upper bound of the minimax private rate. Then they showed that in the interactive case there is an algorithm that is much more better than the optimal minimax private rate in the non-interactive one. ", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "Originality: This paper provides the first study on the problem of estimating non-linear functionals of discrete distributions\nin the  local differential privacy model. \n\nQuality: The paper is a theoretical paper, some of the proofs are tricky which might be used to other problems. Moreover, they provide both lower and upper bounds. And show the advantage if we allow interactions in the LDP model. \n\nAlthough the proof is hard to following, the idea of the paper is clear and readable. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I tend to weakly reject the paper. My main reason is the topic itself is too narrow to ML or DP audience, and I think it will better to submit the paper to information theory or statistics area. \n\n1) As I see from the reference of this paper, in the previous ICML or NeurIPS conferences. There is no paper on estimating non-linear functionals of discrete distributions and most of the related papers appeared at information theory or statistics area. So I do not think NeurIPS is a good place to this paper. \n\n2) As the authors mentioned, this is the first paper studying the problem in LDP model. My question is why the authors study LDP model first instead of the central model? Is that local model is easier? \n\n3) There is no experimental study. \n\n4) The motivation of this paper is unclear. The authors should claim this problem indeed has potential privacy issue (for example, a previous work indeed studied the problem with some sensitive data) ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6h"}, "extra_text": {}}, {"review_id": "2GfZ8GfXe2Z", "reviewer": "Reviewer_zEEc", "summary": "The paper studies the problem of estimating power sum functionals  F_{\\gamma}:= \\sum_i p_i^\\gamma for \\gamma>0 using locally differentially private (LDP) samples and derives the bounds on the mean square error (MSE).\nThe results for \\gamma =2 follows from [2] and [4], and this paper derives the results for general \\gamma.\n\nTo obtain the upper bound, authors privatize the samples using the standard Laplace mechanism, where each sample can be thought of as a collection of indicator random variables. \nThe average of these privatized indicator random variables forms an unbiased estimator of the distribution vector, which is then used in the plug-in estimator of F_{\\gamma}. \nFor large alphabet size, they obtain a better bound on MSE by detecting and zeroing small probabilities.\nFurther, the authors consider a procedure similar to the interactive procedure used in [4].  \nFor this interactive procedure, the upper bound obtained on the MSE error is smaller by log factors than the non-interactive thresholded estimator.\n\nThe authors also provide the lower bounds that match the upper bound for \\gamma \\ge 2.\n\n", "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": "The problem of estimating the power sum of a discrete distribution has recently received a lot of attention \nand is now fairly well understood for non-private samples. \nFor LDP samples the paper extends the previous results beyond the special case of \\gamma =2.\nThe upper bounds are derived using the now-standard Laplace mechanism and plug-in-based estimators.\nThe lower bounds are for all possible privacy mechanisms and over all possible estimators.\nThe lower and upper bound match for \\gamma\\ge 2, but they may differ by polynomial factors for \\gamma<1.\n\nThe paper is generally well written and appropriate references are provided.\nAll the proofs appear in the appendix.\nFor the lower bounds in section 5, and no intuition is provided in the main paper.\nIt would beneficial for the readers to include at least a brief outline of these proofs in the main paper.\n\n\nOther comments:\nPlease fix the reference [2].\nIt is unclear to me if statements in lines 302 and 173 are facts or mere conjectures, in either case, these statements should be made more precise.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any potential negative impact of the work on society.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "-tlEFgxS16T", "reviewer": "Reviewer_V6UM", "summary": "The paper studies estimating power sums of discrete distributions under local DP constraints. In particular, the results leverage standard Laplacian DP procedures and cover both the interactive and non-interactive cases. A summary of the main results appears on page 9, Table 1, for power sums with different order parameters. ", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "Pros:\n\n- The paper reads well and clearly explains its relation to some of the existing works. The derivations in the appendix also seem nontrivial, presented with concise notations. \n\n\n\n- As line 83 claims, the paper \"for the first time the estimation of nonlinear and nonquadratic power-sum functionals...\" In other words, I like the submission for the problem's novelty, though the approach is similar to [4] and some other existing works. \n\n\n\n- The upper bounds mimic those non-private ones, such as [14], and demonstrate the effects of privacy constraints on the estimation rates. \n\n\n\n- In the discussion section, the authors pointed out the limitations of their results and proposed several exciting directions for future research. I appreciate the authors for their honesty and hopefulness.  \n\n\n\n\n\nCons:\n\n\n- The paper misses numerous essential references in the \"Related Literature\" section: \n\n  - Estimating functionals of discrete distributions under DP constraints have been studied in the following two papers. The first paper considers specific cases such as entropy, and the second paper further addresses all Lipschitz additive functionals. \n\n    1. Acharya, J., Kamath, G., Sun, Z., & Zhang, H. (2018, July). \"INSPECTRE: Privately Estimating the Unseen.\" In International Conference on Machine Learning (pp. 30-39). PMLR. \n\n    2. Hao, Y., & Orlitsky, A. (2019). \"Unified Sample-Optimal Property Estimation in Near-Linear Time.\" Advances in Neural Information Processing Systems, 32, 11106-11116.\n\n  - In addition to [1], the best results for Renyi entropy estimation appear in the following two papers. The first paper considers constant accuracy and error, and the second paper studies all levels of accuracy and error.\n\n    1. Obremski, M., & Skorski, M. (2017). \"Renyi Entropy Estimation Revisited.\" Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. \n\n    2. Hao, Y., & Orlitsky, A. (2019). \"The Broad Optimality of Profile Maximum Likelihood.\" Advances in Neural Information Processing Systems, 32, 10991-11003. \n\n  - The content from line 54 to line 60 does not correspond to any of the obtained results but the ones in [13, 14]. I believe it is necessary to include relevant citations in this paragraph. \n\n\n\n- The gap between the upper and lower bounds is relatively large since the improvements are often just logarithmic for the line of works concerning distribution functionals. Also, the paper provides no concrete results about entropy estimation under DP constraints but emphasizes a few times that the technique extends to such cases. I don't find these statements very convincing in a theoretical paper. In particular, the title may oversell the results as they are just about power sums. \n\n\n\n- The techniques used in the paper are variants of those in [2, 4, 5, 17] and are of medium novelty. I think the authors may compensate for this aspect by adding some numerical experiments on the proposed schemes. For example, showing the differences in error rates among the best estimators for non-private, non-interactive LDP, and interactive LDP cases would be excellent. \n\n\n\n\nMinors: \n\n- Lines 19 to 23, it might be better to add some references; line 68, typo in \"multinomial\"; line 99, typo in \"mimic\"; in several places, maybe write \"logarithmic factor\" instead of \"$\\log$ factor\"? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors explained the limitation of their work in the discussion section and clearly indicated (Checklist) that the work has no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "-G1_2JIgtHV", "reviewer": "Reviewer_zYFp", "summary": "The paper studies the problem of estimating non-linear functionals of discrete distribution under local differential privacy. Given i.i.d. data from an unknown discrete distribution, the paper wants to estimate the power sum of functional F_\\gamma = \\sum p_k^\\gamma. The author has made the following contributions:\n\n1. Based on the Laplace mechanism, the first algorithm is proposed and studied, as an analogue of the MLE in the multinomial model.\n2. Noticing that small probabilities below the fluctuation level of their unbiased estimator need not in fact be estimated, since the bias introduced by skipping those values is smaller. The paper proposes another algorithm based on the thresholding, improving the rate of the first technique when K is large.\n3. In the interactive case, the paper proposes a two-step algorithm, which removes the log factor in (2).\n4. A lower bound is proposed.", "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": "The paper studies the problem of estimating non-linear functionals of discrete distribution under local differential privacy. This topic is interesting. However, I do not think the paper has made a lot of theoretical contributions to the community. The Laplace mechanism and thresholding method are quite common, broadly used in the property estimation problem. Besides, in the non-private case, the optimal performance is attained by the best polynomial estimator when gamma is small. However, I do not see any effort spent to see its performance in the private case. Furthermore, the rate of the paper is not tight with respect to K when gamma is small.\n\nMinor comments:\n1. There are several papers working on the central DP property estimation, e.g., [1] and [2], which also use the best polynomial estimation. Maybe worth adding them to the reference.\n\n[1]: http://proceedings.mlr.press/v80/acharya18a.html\n[2]: https://papers.nips.cc/paper/2019/file/f06ae085fe74cd78ad5e89496b197fe1-Paper.pdf", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Did not see any negative social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides LDP algorithms for estimating functionals of discrete distributions. While the paper addresses a fundamental question, reviewers raise concerns regarding the writing of the paper and the gap between upper and lower bounds. I encourage authors to incorporate reviewer concerns in subsequent versions.
Decision: Accept (Poster)