Differentially Private Uniformly Most Powerful Tests for Binomial Data
We derive uniformly most powerful (UMP) tests for simple and one-sided hypotheses for a population proportion within the framework of Differential Privacy (DP), optimizing finite sample performance. We show that in general, DP hypothesis tests can be written in terms of linear constraints, and for exchangeable data can always be expressed as a function of the empirical distribution. Using this structure, we prove a 'Neyman-Pearson lemma' for binomial data under DP, where the DP-UMP only depends on the sample sum. Our tests can also be stated as a post-processing of a random variable, whose distribution we coin "Truncated-Uniform-Laplace" (Tulap), a generalization of the Staircase and discrete Laplace distributions. Furthermore, we obtain exact p-values, which are easily computed in terms of the Tulap random variable. We show that our results also apply to distribution-free hypothesis tests for continuous data. Our simulation results demonstrate that our tests have exact type I error, and are more powerful than current techniques.
Short summary: In this paper, the authors derive uniformly most powerful differentially private simple and one-sided tests for the parameter $\theta$ of the Binomial distribution with parameters $(n,\theta)$. In this context, the requirement of differential privacy translates to certain regularity conditions on the test as a function. The authors explicitly establish the necessary form of a test which fulfils these conditions (i.e. the in some sense strongest version of them) and express it as the distribution function of a novel distribution they call Tulap distribution. The UMP-property is then asserted through a Neyman-Pearson-type lemma. Later on, the close connection between the test and the Tulap and Binomial distributions leads to a convenient representation of the associated p-value and therefore the test as such. The paper closes with possible applications to situations without a priori Binomial distributions and simulations comparing the empirical type-I error probability and power when using the new test, the classical non-private UMP test and the test based on Normal approximation.   Comments: Since the differentially private UMP tests for the considered problem were unknown and the authors introduce a new distribution as an essential tool, I consider the paper significant and original. Also, this work appears to be technically sound. A final proof-reading would be advisable nonetheless; for instance, there are several typos in the paragraph on the nearest integer function (lines 98-100) and there is a factor $\exp(\epsilon)$ missing in the second equation on page 11. In fact, I would like to mention as my primary concern that I found sections 2 though 4 very difficult to read - fortunately, sections 5 through 7 are well-written and helped clarify my earlier problems. More specifically, Definition 2.1. clearly creates the impression that $X$ is a parameter. Then, in Definition 2.3., $X$ ist the random object and there is a new parameter $\theta$; however, only a few lines after that, $X$ appears as the index of the test, which is very confusing since it is actually the input variable (i.e. you would typically write $\phi(X)$). After section 3, there is no motivation yet to introduce the Tulap distribution and on top of that, you are again confused about the role of $X$ since it seems to be a parameter. I understand that each consideration in these sections is an important preparation for what follows, but the current structure is unsettling, at least for me: For instance, would it not be more natural to place Lemma 5.2 at the end of section 3 and let this be the motivation for Definition 4.1? Furthermore, the notion of post-processing (where the interpretation of $X$ as a parameter is warranted) is only needed in section 7, so would it not be more natural to discuss it only in that section? I realise that many people would dismiss all this as being a question of taste and hence it does not affect my opinion that this significant and original paper should be published, but I would still appreciate a more accessible version (through a revised structure or helpful remarks).    Regarding the rebuttal: I have read the other reviews and the authors' response. Even in light of the points raised by the other reviewers, I still vote for accepting the paper since the authors' response is quite convincing; I particulary appreciate how seriously the authors took my review and which adjustments they announced.