NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:5819
Title:Private Testing of Distributions via Sample Permutations

Reviewer 1

Update after reading the author response =============================== The feedback helped me to appreciate the contribution. I changed my scores accordingly. The paper considers the challenge of private distribution testing. Previous results considered "testing samples" approach. This paper considers the flattening samples approach which is more challenging in terms of privacy preserving. To overcome this difficulty, the authors suggest a method that look at all possible permutations of the samples in order to eliminate the sensitivity caused by the flattening process. Overall the suggested algorithm gives an adequate solution for DP in the context of distribution testing. It took a lot of effort from my side to understand the contribution of the paper. The presentation goes back and forth between preliminaries and novel parts, and also between various settings of the problem. I wish that the author presented the setting and the main results in a more concise manner.

Reviewer 2

Additional Comments after feedback period: I've changed my score. I also edited my comment on the typo in line 154-155. ---------------------------------------------------- The paper has a number of typos and should be proofread carefully. Some of them are described below. Overall, though, the paper is written clearly. Since I do not know the literature in differential privacy, it is difficult for me to asesss the originality of the work. Some of the typos in the paper: Line 25: "the 'far'" should be "they 'far'" line 83: "and output" should be "and outputs" line 93 missing right paren line 101: missing citation (?) line 120: typos in definition of Lap(x:gamma) line 128: S and S should be S and S' line 154-155: doesn't parse, needs to be corrected. In the expression in line 154, in the theta notation, the quantity max(||p||_2, ||q||_2) should not be in the denominator. The expression in the footnote also needs to be fixed.

Reviewer 3

Written clearly. Perhaps would benefit from some empirical examples demonstrating the difference in error rate for a two-sample test, as a result of privatizing the test statistic. Comments on notation: Line 120: Laplace distribution has an extra e? Line 157: The reference in [25] indicates that "To begin with, we note that it suffices that only one of ||p||2 and ||q||2 is small. This is essentially because if there is a large difference between the two, this is easy to detect." ... If both are small, might that still make it hard to detect?