Differentially Private Identity and Equivalence Testing of Discrete Distributions

Maryam Aliakbarpour, Ilias Diakonikolas, Ronitt Rubinfeld
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:169-178, 2018.

Abstract

We study the fundamental problems of identity and equivalence testing over a discrete population from random samples. Our goal is to develop efficient testers while guaranteeing differential privacy to the individuals of the population. We provide sample-efficient differentially private testers for these problems. Our theoretical results significantly improve over the best known algorithms for identity testing, and are the first results for private equivalence testing. The conceptual message of our work is that there exist private hypothesis testers that are nearly as sample-efficient as their non-private counterparts. We perform an experimental evaluation of our algorithms on synthetic data. Our experiments illustrate that our private testers achieve small type I and type II errors with sample size sublinear in the domain size of the underlying distributions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-aliakbarpour18a, title = {Differentially Private Identity and Equivalence Testing of Discrete Distributions}, author = {Aliakbarpour, Maryam and Diakonikolas, Ilias and Rubinfeld, Ronitt}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {169--178}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/aliakbarpour18a/aliakbarpour18a.pdf}, url = {https://proceedings.mlr.press/v80/aliakbarpour18a.html}, abstract = {We study the fundamental problems of identity and equivalence testing over a discrete population from random samples. Our goal is to develop efficient testers while guaranteeing differential privacy to the individuals of the population. We provide sample-efficient differentially private testers for these problems. Our theoretical results significantly improve over the best known algorithms for identity testing, and are the first results for private equivalence testing. The conceptual message of our work is that there exist private hypothesis testers that are nearly as sample-efficient as their non-private counterparts. We perform an experimental evaluation of our algorithms on synthetic data. Our experiments illustrate that our private testers achieve small type I and type II errors with sample size sublinear in the domain size of the underlying distributions.} }
Endnote
%0 Conference Paper %T Differentially Private Identity and Equivalence Testing of Discrete Distributions %A Maryam Aliakbarpour %A Ilias Diakonikolas %A Ronitt Rubinfeld %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-aliakbarpour18a %I PMLR %P 169--178 %U https://proceedings.mlr.press/v80/aliakbarpour18a.html %V 80 %X We study the fundamental problems of identity and equivalence testing over a discrete population from random samples. Our goal is to develop efficient testers while guaranteeing differential privacy to the individuals of the population. We provide sample-efficient differentially private testers for these problems. Our theoretical results significantly improve over the best known algorithms for identity testing, and are the first results for private equivalence testing. The conceptual message of our work is that there exist private hypothesis testers that are nearly as sample-efficient as their non-private counterparts. We perform an experimental evaluation of our algorithms on synthetic data. Our experiments illustrate that our private testers achieve small type I and type II errors with sample size sublinear in the domain size of the underlying distributions.
APA
Aliakbarpour, M., Diakonikolas, I. & Rubinfeld, R.. (2018). Differentially Private Identity and Equivalence Testing of Discrete Distributions. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:169-178 Available from https://proceedings.mlr.press/v80/aliakbarpour18a.html.

Related Material