Locally Private Hypothesis Testing
[edit]
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:46054614, 2018.
Abstract
We initiate the study of differentially private hypothesis testing in the localmodel, under both the standard (symmetric) randomizedresponse mechanism (Warner 1965, Kasiviswanathan et al, 2008) and the newer (nonsymmetric) mechanisms (Bassily & Smith, 2015, Bassily et al, 2017). First, we study the general framework of mapping each user’s type into a signal and show that the problem of finding the maximumlikelihood distribution over the signals is feasible. Then we discuss the randomizedresponse mechanism and show that, in essence, it maps the null and alternativehypotheses onto new sets, an affine translation of the original sets. We then give sample complexity bounds for identity and independence testing under randomizedresponse. We then move to the newer nonsymmetric mechanisms and show that there too the problem of finding the maximumlikelihood distribution is feasible. Under the mechanism of Bassily et al we give identity and independence testers with better sample complexity than the testers in the symmetric case, and we also propose a $\chi^2$based identity tester which we investigate empirically.
Related Material


