Abstract

This paper develops differentially private mechanisms for test of independence. While existing works put their effort into properly controlling the type-I error, in addition to that, we investigate the type-II error of differentially priva mechanisms. Based on the analysis, we present unit circle mechanism: a novel differentially private mechanism based on the geometrical property of the test statistics. Compared to existing output perturbation mechanisms, our mechanism improves the dominated term of the type-II error from O(1) to where N is the sample size. Furthermore, we introduce novel procedures for multiple tests by incorporating the unit circle mechanism into the sparse vector technique and the exponential mechanism. These procedures can control the family-wise error rate (FWER) properly, which has never been attained by existing mechanisms.