Differentially Private Chi-squared Test by Unit Circle Mechanism

Kazuya Kakizaki, Kazuto Fukuchi, Jun Sakuma
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:1761-1770, 2017.

Abstract

This paper develops differentially private mechanisms for χ2 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 private 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 O(exp(−√N)) where N is the sample size. Furthermore, we introduce novel procedures for multiple χ2 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-kakizaki17a, title = {Differentially Private Chi-squared Test by Unit Circle Mechanism}, author = {Kazuya Kakizaki and Kazuto Fukuchi and Jun Sakuma}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {1761--1770}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/kakizaki17a/kakizaki17a.pdf}, url = {https://proceedings.mlr.press/v70/kakizaki17a.html}, abstract = {This paper develops differentially private mechanisms for $\chi^2$ 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 private 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 $O(\exp(-\sqrt{N}))$ where $N$ is the sample size. Furthermore, we introduce novel procedures for multiple $\chi^2$ 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.} }
Endnote
%0 Conference Paper %T Differentially Private Chi-squared Test by Unit Circle Mechanism %A Kazuya Kakizaki %A Kazuto Fukuchi %A Jun Sakuma %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-kakizaki17a %I PMLR %P 1761--1770 %U https://proceedings.mlr.press/v70/kakizaki17a.html %V 70 %X This paper develops differentially private mechanisms for $\chi^2$ 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 private 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 $O(\exp(-\sqrt{N}))$ where $N$ is the sample size. Furthermore, we introduce novel procedures for multiple $\chi^2$ 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.
APA
Kakizaki, K., Fukuchi, K. & Sakuma, J.. (2017). Differentially Private Chi-squared Test by Unit Circle Mechanism. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:1761-1770 Available from https://proceedings.mlr.press/v70/kakizaki17a.html.

Related Material