Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper looks at upper and lower bounds for LDP estimation of a particular family of functionals of a discrete probability distribution. 
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. 

Strengths: 

- The paper is generally clear and technical statements are crisp and easy to understand. 
- 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. 
- The paper provides lower bounds that match the upper bounds in some parameter regimes

Weaknesses: 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.

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

limitations_and_societal_impact: The authors could do more to explain what gaps exist between their upper and lower bounds.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work considers locally differentially private (LDP) estimation: in
particular, the authors estimating functionals of discrete distributions, i.e.,
for a discrete distribution supported on $K$ elements with probabilities $p_1,
\ldots, p_K$ the goal is to estimate the quantities $F_\gamma = \sum_{k=1}^K
p_k^\gamma$ for some smoothness parameter $\gamma > 0$.  In general, the closer
$\gamma$ is to $0$ the harder the estimation problem becomes.
They distinguish between interactive and
non-interactive locally private mechinisms.  In interactive LDP mechanisms
agents can release information that depends on the already released information
of other agents that is already privatized.  In non-interactive mechanisms
every agent can only release privatized data depending only on their own data.
The authors provide a fine-grained sample complexity analysis of both non-interactive
and interactive estimators for estimation of the functionals $F_\gamma$ for
different regimes of the smoothness parameter $\gamma$.

When the smoothness parameter $\gamma \in (0,1)$ the authors give an estiamator
that is $\alpha$-LDP, uses $n$ samples and achieves mean squared error
$\min(K^{2 (1- \gamma)}, K^2/(\alpha^2 n)^\gamma)$.
They also show a sample complexity lower bound of
$\min(K^{2 (1-\gamma)}, K^{2 -\gamma}/(\alpha^2 n)^\gamma)$. The upper
and lower bounds match up to a factor dependending on the support
of the distribution: $K^\gamma$.  They have similar upper and lower
bounds for $\gamma > 1$ that have roughly the same gap.
main_review: Providing LDP mechanisms and estimation algorithms is a well-motivated and
important problem with a lot of prior work by now.  This paper fits in this
line of research and aims to analyze an estimation problem that has been
previously studied from a classical (non-Differentially Private) statistical
viewpoint.  The problem of estimation of power functionals $F_\gamma$ described
here seems to be of interest as it reveals usefull information about the
underlying distribution.   I think it would be beneficial for the paper if the
authors expanded more on the applications and the usefullness of estimating the
power functionals $F_\gamma$ -- especially for the more challenging cases of
$\gamma$ close to $0$.

I found the distinction between interactive and non-interactive mechanisms
to be interesting.  However, in this case the results in the two settings
turn out to be very close (the authors are able to shave off log-factors
using interactive mechanisms).  A weakness of this work is that the estimators
proposed are rather straightforward: adding laplace noise and using
a thresholded plug-in estimator basically gives the best results in this work (up
to log-factors).  The paper is well written, but I think it would benefit from
a cleaner and more high-level presentation of the main results.
I think Table 1 should include both (the best) upper and lower bounds clearly
stating the gaps (perhaps ignoring the interactive vs. non-interactive distinction).
Overall, I am leaning towards acceptance since the model and the task considered here
are interesting and well-motivated.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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. 

This 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.
The tightness of the estimation error upper bound of the plugin estimator is not proved when $\gamma \ge 1$, and $K$ is small.
Because the optimality of the non-interactive mechanism is not proven, it is unclear that the logarithmic gap between non-interactive and interactive actually exists.
The optimality of the interactive mechanism for $\gamma \in (0,2)$ is proven only when $K \asymp n(e^{2\alpha}-e^{-2\alpha})^2$.

Minor comments:
The 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)$.

limitations_and_societal_impact: It is better to summarize the limitations of the results. The potential societal impact is not discussed.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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: 

1. Non-interactive: estimate each probability using the Laplace mechanism, and use the plug-in estimator. 
2. Non-interactive: apply the above estimator, but truncate all small probabilities to zero; the truncation is conducted using sample splitting. 
3. 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$. 

The 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. 
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: 

1. 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). 

2. 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. 

3. 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. 

In 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. 

Post-rebuttal feedback: 

Thanks to the authors for the detailed feedback. The rebuttal alleviates my following concerns: 

1. 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. 

2. 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. 

However, 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. 

In 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. 
limitations_and_societal_impact: There is no negative societal impact of this work.
review_title: null

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)