Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the problem of releasing anonymized histograms subject to DP in various privacy models.    Privatizing anonymized histograms has been considered before, but only in the global privacy model.  This paper considers the pan privacy and shuffle DP models.  Their results show that the anonymized histograms can be approximated up to error that matches the special case problem of Count-Distinct in both the shuffle and pan privacy models.  
strengths_and_weaknesses: Strengths: 
- Anonymized histograms seem to be growing in popularity as an important problem to research.  The paper presents nice results in various privacy models.
- The introduction presents the previous work very clearly, giving a nice history of releasing anonymous histograms subject to privacy.  
- The post processing function to get back an anonymous histogram from a privatized cumulative prevalence is a nice result.  In particular, prior work did not need to consider noise when the cumulative prevalence was privatized before converting back to an anonymous histogram.  This post processing function and its analysis are the main contribution of this work.  
- I like that this work addressed the issue of large domains, although it does look like an "off the shelf" approach with a random hash.  
- Estimating Symmetric Properties of Discrete Distributions is a nice application of the results in the paper.

Weaknesses: 
- The results seem to follow from prior work on privatizing count-distinct.  Although the anonymized histogram problem is more general, the techniques in the analysis seem to be largely the same.  The main observation is that for count distinct, we need to compute the number of items that have true count larger than 0, which can then be generalized to number of items that have true count larger than r, which will result in a histogram with sensitivity of 1.  Hence the results boil down to the same analysis as before except applying it to a sensitivity 1 histogram rather than a single count.  
- The general approach largely follows previous work, using Laplace mechanism and estimating the cumulative prevalence to then get an anonymous histogram.  
- I would have liked to have seen more detail in Section 4, such as how hash functions are selected randomly.  Theorem 12 seems a bit hand wavy.   


Minor nits: 
- In the introduction, it states that $n^{\ell}$ is the $\ell$th largest element among the $h_j$'s, but should this be the *count* of the $\ell$th largest element for anonymous histograms?
- There are too many footnotes in the beginning, which should be included in the main body of the paper.  
questions: Why not consider continuous Gaussian noise for the $\ell_2$ error metric?  This can be applied in the shuffle model.  If noise must be discrete for other reasons, perhaps the Skellem distribution could also be used.

Should the $\ell_2$ error be squared?  Just want to make sure that the informal statements of theorems are supposed to be $\ell_2^2$ or $\ell_2$.  
limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies private anonymized histograms in shuffle DP and pan privacy models. Under $\ell_1$ loss, the proposed algorithm achieves $\tilde{O}(\sqrt{n}/\varepsilon^{2.5})$ error, which nearly matches the optimal bound in central DP model in terms of $n$. This paper also applies the proposed algorithm on shannon entropy estimation for discrete distributions.
strengths_and_weaknesses: Strengths: 1. The proposed algorithm is simple. It is based on random hashing and laplacian mechanism, which can be implemented in pan privacy and shuffled DP models.
2. This paper is well written. The structure is easy to follow.

Weaknesses: 1. It is not clear if the dependence on $\varepsilon$ is tight. Compared to the lower bound in central DP, there is a $1/\varepsilon^{1.5}$ gap. 
2. Time complexity is not discussed here.
questions: 1. Under the central DP model and $\ell_2^2$ loss, the proposed algorithm is worse than Hay et al [33] (This paper has $O(\sqrt{n}/\varepsilon^3.5)$). Both algorithms use a Laplacian noised histogram and a post-processing step. I am wondering if there is any connection and differences.

2. I am not very familiar with pan privacy and the shuffled DP model. I am wondering if there is any lower bound technique that translates central DP bounds into these settings. What would break if you apply prior works for central DP under pan privacy and shuffled DP model?
limitations: This paper is theoretical and does not have a direct negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: 
The authors study the problem of releasing anonymized (labels are not released) histograms with DP. First result is an algorithm that takes a histogram with Discrete Laplace noise, and returns an anonymized histogram with l_1 and l_2 errors of O(\sqrt(n + D)). Where n is number of records and D is the size of the histogram domain. Second main result is an algorithm that via hashing, overcomes the dependence on D in the previous bound. This algorithm can be implemented in the pan private model on in the shuffle model of DP. Last main result is an algorithm to estimate symmetric properties of distributions, entropy being an example. 
strengths_and_weaknesses: Strengths: The paper is written clearly, it is easy to follow, literature review is sufficient to give the reader context. Algorithms and bounds are novel and improve upon state of the art. 
Weakness: Seeing the algorithms being applied in a real world problem or a simulation comparing to previous work would have been cool to motivate the reader. However, this is a theory paper and there is limited space so, although I think it would improve the paper,  I don’t think it is a big deal.
questions: It seems to me that we need knowledge of the domain size D in advance. I’m curious, are there settings of practical interest where D is not known in advance and we still want to release an anonymized histogram? I’m asking because this is an important problem in the setting of DP Histograms with labels (https://proceedings.neurips.cc/paper/2019/file/b139e104214a08ae3f2ebcce149cdf6e-Paper.pdf)
limitations: NA
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers the release of anonymized histograms under differential privacy. In this setting, $n$ users each have some integer from the domain $[D]$. A histogram of the data is the number of users with each integer in the domain. An anonymized histogram is the set of frequencies in the histogram without the corresponding domain labels. This paper first shows that given a noisy histogram procured by adding Laplacian noise with scale parameter $\frac{1}{\varepsilon}$, there exists an algorithm that outputs an anonymized histogram with expected $\ell_1$ and $\ell_2^2$ error $O_{\varepsilon}(\sqrt{n})$. This subroutine can then be used to achieve private anonymized histograms as well as private symmetric function property testers in the pan-private and shuffle models.
strengths_and_weaknesses: Strengths: The main subroutine is nice and simple. Given an input (discretized) noisy histogram, the algorithm essentially builds a noisy cumulative mass function and then outputs the best fit integral histogram. The analysis is more intricate but also reasonably intuitive. To decrease the domain size from $D$ to $O(n)$, the algorithm hashes the universe into buckets of size $B=O(n)$. It then remains to bound the collision error, which intuitively should not be too high because many values of the domain must have frequency zero, while the remaining collisions can be charged to the $\ell_1$ error. 

Weakness: I think the main weakness of the paper is that the post-processing algorithms do not have runtime analysis. Specifically, the runtime to output the best fit integral histogram is not analyzed and I think the efficiency of these post-processing algorithms can make a large difference in the practicality of this paper. Perhaps the authors can address this concern in the rebuttal phase.

Post-rebuttal update: I'm pleased to see details for a near-linear time post-processing steps for Algorithm 1 and 2. Though I have not gotten a chance to verify correctness, it seems my main concern is a non-issue, so I have increased my score from a 4 to a 6. 
questions: Are there linear time algorithms for the post-processing steps in Algorithms 1 and 2?
limitations: N/A
review_title: null

Meta-review: metareview: This paper considers the release of anonymized histograms under differential privacy, and presents new (and simple) algorithms for the shuffle model and the pan-private model of differential privacy. The reviewers all agree that the problem and the results are interesting, and support accepting the paper.
confidence: Certain
Decision: Accept