Discrete Distribution Estimation under Local Privacy

Peter Kairouz, Keith Bonawitz, Daniel Ramage
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2436-2444, 2016.

Abstract

The collection and analysis of user data drives improvements in the app and web ecosystems, but comes with risks to privacy. This paper examines discrete distribution estimation under local privacy, a setting wherein service providers can learn the distribution of a categorical statistic of interest without collecting the underlying data. We present new mechanisms, including hashed k-ary Randomized Response (KRR), that empirically meet or exceed the utility of existing mechanisms at all privacy levels. New theoretical results demonstrate the order-optimality of KRR and the existing RAPPOR mechanism at different privacy regimes.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-kairouz16, title = {Discrete Distribution Estimation under Local Privacy}, author = {Kairouz, Peter and Bonawitz, Keith and Ramage, Daniel}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2436--2444}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/kairouz16.pdf}, url = {https://proceedings.mlr.press/v48/kairouz16.html}, abstract = {The collection and analysis of user data drives improvements in the app and web ecosystems, but comes with risks to privacy. This paper examines discrete distribution estimation under local privacy, a setting wherein service providers can learn the distribution of a categorical statistic of interest without collecting the underlying data. We present new mechanisms, including hashed k-ary Randomized Response (KRR), that empirically meet or exceed the utility of existing mechanisms at all privacy levels. New theoretical results demonstrate the order-optimality of KRR and the existing RAPPOR mechanism at different privacy regimes.} }
Endnote
%0 Conference Paper %T Discrete Distribution Estimation under Local Privacy %A Peter Kairouz %A Keith Bonawitz %A Daniel Ramage %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-kairouz16 %I PMLR %P 2436--2444 %U https://proceedings.mlr.press/v48/kairouz16.html %V 48 %X The collection and analysis of user data drives improvements in the app and web ecosystems, but comes with risks to privacy. This paper examines discrete distribution estimation under local privacy, a setting wherein service providers can learn the distribution of a categorical statistic of interest without collecting the underlying data. We present new mechanisms, including hashed k-ary Randomized Response (KRR), that empirically meet or exceed the utility of existing mechanisms at all privacy levels. New theoretical results demonstrate the order-optimality of KRR and the existing RAPPOR mechanism at different privacy regimes.
RIS
TY - CPAPER TI - Discrete Distribution Estimation under Local Privacy AU - Peter Kairouz AU - Keith Bonawitz AU - Daniel Ramage BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-kairouz16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2436 EP - 2444 L1 - http://proceedings.mlr.press/v48/kairouz16.pdf UR - https://proceedings.mlr.press/v48/kairouz16.html AB - The collection and analysis of user data drives improvements in the app and web ecosystems, but comes with risks to privacy. This paper examines discrete distribution estimation under local privacy, a setting wherein service providers can learn the distribution of a categorical statistic of interest without collecting the underlying data. We present new mechanisms, including hashed k-ary Randomized Response (KRR), that empirically meet or exceed the utility of existing mechanisms at all privacy levels. New theoretical results demonstrate the order-optimality of KRR and the existing RAPPOR mechanism at different privacy regimes. ER -
APA
Kairouz, P., Bonawitz, K. & Ramage, D.. (2016). Discrete Distribution Estimation under Local Privacy. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2436-2444 Available from https://proceedings.mlr.press/v48/kairouz16.html.

Related Material