INSPECTRE: Privately Estimating the Unseen

Jayadev Acharya, Gautam Kamath, Ziteng Sun, Huanyu Zhang
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:30-39, 2018.

Abstract

We develop differentially private methods for estimating various distributional properties. Given a sample from a discrete distribution p, some functional f, and accuracy and privacy parameters alpha and epsilon, the goal is to estimate f(p) up to accuracy alpha, while maintaining epsilon-differential privacy of the sample. We prove almost-tight bounds on the sample size required for this problem for several functionals of interest, including support size, support coverage, and entropy. We show that the cost of privacy is negligible in a variety of settings, both theoretically and experimentally. Our methods are based on a sensitivity analysis of several state-of-the-art methods for estimating these properties with sublinear sample complexities

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-acharya18a, title = {{INSPECTRE}: Privately Estimating the Unseen}, author = {Acharya, Jayadev and Kamath, Gautam and Sun, Ziteng and Zhang, Huanyu}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {30--39}, 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/acharya18a/acharya18a.pdf}, url = {https://proceedings.mlr.press/v80/acharya18a.html}, abstract = {We develop differentially private methods for estimating various distributional properties. Given a sample from a discrete distribution p, some functional f, and accuracy and privacy parameters alpha and epsilon, the goal is to estimate f(p) up to accuracy alpha, while maintaining epsilon-differential privacy of the sample. We prove almost-tight bounds on the sample size required for this problem for several functionals of interest, including support size, support coverage, and entropy. We show that the cost of privacy is negligible in a variety of settings, both theoretically and experimentally. Our methods are based on a sensitivity analysis of several state-of-the-art methods for estimating these properties with sublinear sample complexities} }
Endnote
%0 Conference Paper %T INSPECTRE: Privately Estimating the Unseen %A Jayadev Acharya %A Gautam Kamath %A Ziteng Sun %A Huanyu Zhang %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-acharya18a %I PMLR %P 30--39 %U https://proceedings.mlr.press/v80/acharya18a.html %V 80 %X We develop differentially private methods for estimating various distributional properties. Given a sample from a discrete distribution p, some functional f, and accuracy and privacy parameters alpha and epsilon, the goal is to estimate f(p) up to accuracy alpha, while maintaining epsilon-differential privacy of the sample. We prove almost-tight bounds on the sample size required for this problem for several functionals of interest, including support size, support coverage, and entropy. We show that the cost of privacy is negligible in a variety of settings, both theoretically and experimentally. Our methods are based on a sensitivity analysis of several state-of-the-art methods for estimating these properties with sublinear sample complexities
APA
Acharya, J., Kamath, G., Sun, Z. & Zhang, H.. (2018). INSPECTRE: Privately Estimating the Unseen. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:30-39 Available from https://proceedings.mlr.press/v80/acharya18a.html.

Related Material