Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Summary: This paper gives a precise analysis of the privacy loss, as measured by differential privacy, from drawing samples from the Dirichlet posterior distribution on multinomial parameters conditioned on a sensitive data set. 
main_review: The paper has a single main result, namely a precise analysis of the distribution of the privacy loss—in the sense of differential privacy—of the algorithm which takes a sensitive data set as input and a nonsensitive Dirichlet prior on parameters of a multinomial distribution, constructs a posterior distribution on the parameters, and samples a single value from that distribution. 

The main result (Theorem 1) is stated in terms of truncated concentrated DP, though I think it might be easier to state it in terms of Renyi DP (as a function of the $\alpha$ vector and the “order” $\lambda$) and then derive the tCDP and $(\epsilon,\delta)$-DP statements as corollaries. (I also think it would be worthwhile, in the corollaries, setting $\Delta_\infty$ and $\Delta_2$ to particular values, say 1, to get clear statements.) 

I have very few comments on the writing: the paper is clear and easy to understand and, I think, accurately represents and discusses the contributions. The only question here is significance: the paper is providing updated calculations for a well-know idea. It definitely should be published in an archival and refereed venue. I’m less sure that it meets the bar for NeurIPS. If the committee ultimately decides not to accept the paper, I would encourage the authors to submit to an appropriate journal. 

limitations_and_societal_impact: Well addressed in a separate section.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies releasing a single sample from a Dirichlet posterior with several variants of differential privacy in the two specific tasks of Dirichlet sampling and private normalized histogram publishing. Both privacy and utility guarantees are analyzed by the authors. The authors compare the results with Gaussian mechanism theoretically and empirically using a simple simulation.
main_review: The paper is well-organized and easy to follow. The related works are summarized and allow the reader to compare the drawbacks of existing methods relatively to the proposed methods. All the notations and background definitions are clearly stated. While the paper contains a significant amount of theoretical derivations, many of them are accompanied by intuitions and interpretations (such as discussion of low/high privacy regimes or illustrations of  behavior of the computed quantities as a function of parameters, such as Fig. 1). I was not able to thoroughly verify all the derivations, but the math seems sounds. Overall, i believe the paper makes a good contribution and will be interesting to the researchers in the area.
limitations_and_societal_impact: The paper contains a section on "Potential negative societal impacts" which reasonably discussed the implications of the usage of the method in an industrial setting.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: 
This paper studies differential privacy and the dirichlet mechanism.

main_review: 

The paper contains quite some phrases which aren't fully precise.  Often, a minor effort can make the text more precise without taking significantly more space.  In some other cases, the question is whether it is worthwhile to give technical details without giving the reader the context in which he can understand these details.  E.g.,
* Line 38: "DP allows us to quantify how much the privacy of the Dirichlet posterior sampling is affected by the prior parameters" -> what is meant here with "afect"?  Maybe you want to analyze how privacy guarantees depend on these parameters, but the cause of the change in privacy is in the publishing of the output so I wouldn't use "affect" for the parameters.
* Line 67: "any posterior sampling with the log-likelihood bounded by B is 4B-differentially private" -> which log-likelihood must be bounded by B ?  Do you mean classic \epsilon-differential privacy here (where you use B instead of \epsilon for some other reason) ?  Usually a loglikelihood B is a negative value, while \epsilon=4B must be positive to be able to consider \epsilon-DP.  Should the loglikelihood be upper bounded or lower bounded by B ?
* line 70: "if the condition on the log-likelihood is relaxed to the Lipschitz continuity with high probability," -> the uninformed reader reading only your summary may not understand how a log-likelihood bound |log(P(x))| < B (which is typically applied to random variables) can be relaxed to a Lipschitz continuity requirement (which is typically applied to functions).  
* Line 74: "the sufficient statistics x" refers to some not-yet-introduced variables x on which "the" sufficient statistics is considered without explaining to the reader which sufficient statistics is being considered.
* Line 165: The theorem uses expressions involving x and x'.  x and x' are sample statistics of datasets, but it is unclear how they are sampled (e.g., with replacement / without replacement or other sample properties).  Even though we learn that x and x' are sample statistics from two adjacent datasets.
* Theorem 1, and also a few earlier sentences, use the term "one-time sampling", but this concept isn't defined (and also not a hit when provided to Google).  Do you mean "a single value x drawn from the distribution" (a single sample) or do you mean "at one time we draw many values x_1, x_2, x_3 ... without doing other things in between" (e.g., in contrast to MDP no decision can be made after a first sample to infleunce a later sample), or something else?

There are some minor language issue, often related to the use of articles where I wouldn't expect them or the absence of articles where I would expect them.  Also,
* Line 128: "... privacy" -> ... private

Some other comments:
* Line 142 saying "p(x|y)" suggests a conditional probability distribution where y is known and the distribution of drawing next x depends on y.  On the other hand, the equation between lines 144 and 145 suggests that we need to know x in order to draw Y.
* Line 150 discusses "Consider a special case where x = p", but p isn't introduced yet at that point: the only thing we know about p already is (from the notations section) that \sum_i p_i = 1.
* It turns out that p is an empirical distribution of a dataset.  The paragraph mentions the question how to make a private version of p (a problem which has been solved without using Dirichlet distributions), but doesn't immediately provide an answer.  
* Figure 2: I guess that instead of "accuracy" (typically used in classification problems as the fraction of cases classified correctly, so ideally close to 1) you mean "norm" or "loss" (ideally small), at least this is what the Y-axis scale suggests.

The paper doesn't clearly define the problem it is trying to solve.  E.g., What values are sensitive and need to be protected from being revealed?  How does the "one-time sampling" differ from earlier work which considered the same problem but without "one-time sampling" ?


In conclusion, the paper has numerous minor issues (which individually can probably be easily solved but collectively may form a serious hurdle for a non-expert reader), introduces insufficiently clearly the problem (a problem formulation is the key part of a paper which should be understandable for all Neurips attendees), clarifies insufficiently in which way the contribution is novel and significant, and only in a limited way validates the work through experiments (with a single Gaussian baseline) where it would be possible to compare to other alternatives and discuss limitations and advantages.

limitations_and_societal_impact: 
The text presents a comparison between the Guassian and Dirichlet mechanisms, and highlights around line 280 that the accuracy of the Dirichlet mechanism is better for spartse histograms and small N, but is silent about limitations, e.g., in the cases of dense hisograms and large N.

The paper doesn't discuss limitations, nor plans for future work where such limitations could be addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a method for releasing differentially private samples from Dirichlet posterior distribution. Authors present a privacy analysis for their proposed method and demonstrate that the method out performs Gaussian mechanism under certain conditions. Besides the empirical evaluation, authors also derive analytical utility guarantees for the method.
main_review: In this paper authors propose a method that draws a single sample from Dirichlet posterior distribution. The method is rather simple and draws from Dir$(x + \alpha)$, which is the posterior of multinomial observations $x$ given a Dirichlet prior Dir$(\alpha)$ for the multinomial probabilities. The privacy of the method is analysed with respect to the prior parameter $\alpha$ using truncanted CDP. Authors consider two use cases for this method (which I think are rather similar), and derive analytical expressions for the utility of these cases. Finally authors demonstrate that the proposed method outperforms Gaussian method in a histogram release task when the number of samples is small.

The analysis of the paper seems novel to me. I appreciate the authors' efforts for deriving analytical expressions between the privacy and utility. I can also see a use case for such method (for example the histogram release demonstrated in Sec 4.2), however I think the use cases might be rather limited. Thus I think the method might not be the most striking from usage perspective, but with the analysis it is a solid privacy paper.

Pros:
- (+++) Very clearly written paper
- (++) Novel privacy analysis in terms of Dirichlet prior parameter $\alpha$
- (++) Utility analysis in terms of sample size
- (+) Emprical results showing improvement over Gaussian mech.

Cons:
- (--) Use case might be limited
- (--) I'm not sure what is the actual difference between uses in 4.1 and 4.2

Minor comments/questions:
- Introduction, lines 30-32. Are you talking about drawing from posterior predictive? In that case I think Y should also be drawn for each sample.
- Theorem 1, proof. Is there really $\alpha'$ separate from $\alpha$ or is it a typo?
- Figure 2, I guess it would make more sense to call the y-axis $\ell_2$-error instead of $\ell_2$-accuracy. For me it seems odd to say that "We see that the $\ell_2$-accuracy of the Dirichlet mechanism is smaller than that of the Gaussian mechanism for small N when d = 1000.", when you actually want to point out that your method works better in the small N domain, i.e. it's more "accurate".

limitations_and_societal_impact: Yes
review_title: null

Meta-review: Reviewers generally appreciated the paper's clean problem formulation, algorithmic result, and analysis. There was consensus that the result is something that should be recorded in the literature. The two main downsides are 1) there is not much conceptual innovation behind the paper's algorithmic approach. Obtaining privacy by sampling once from an updated posterior distribution is a known idea, and the paper's novelty is in the analysis of privacy and utility. 2) Reviewer QwTp pointed out some editorial concerns that should be addressable in a revision of the paper. While the paper is technically sound and should be published, we did not find it exciting enough to meet the bar for NeurIPS.

Technical comment: The authors should justify why they measure utility using expected KL divergence with a particular ordering between P and Q. The way the paper is written, it seems this is just done for mathematical convenience rather than for relevance, e.g., to downstream inference tasks.
Decision: Reject