ICML 2019oral69 citations
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters
Abstract
We consider the problems of distribution estimation, and heavy hitter (frequency) estimation under privacy, and communication constraints. While the constraints have been studied separately, optimal schemes for one are sub-optimal for the other. We propose a sample-optimal $\eps$-locally differentially private (LDP) scheme for distribution estimation, where each user communicates one bit, and requires
BibTeX
@InProceedings{pmlr-v97-acharya19c,
title = {Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters},
author = {Acharya, Jayadev and Sun, Ziteng},
booktitle = {Proceedings of the 36th International Conference on Machine Learning},
pages = {51--60},
year = {2019},
editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan},
volume = {97},
series = {Proceedings of Machine Learning Research},
month = {09--15 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v97/acharya19c/acharya19c.pdf},
url = {https://proceedings.mlr.press/v97/acharya19c.html},
abstract = {We consider the problems of distribution estimation, and heavy hitter (frequency) estimation under privacy, and communication constraints. While the constraints have been studied separately, optimal schemes for one are sub-optimal for the other. We propose a sample-optimal $\eps$-locally differentially private (LDP) scheme for distribution estimation, where each user communicates one bit, and requires