Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters

Jayadev Acharya, Ziteng Sun
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:51-60, 2019.

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 no public randomness. We also show that Hadamard Response, a recently proposed scheme for $\eps$-LDP distribution estimation is also utility-optimal for heavy hitters estimation. Our final result shows that unlike distribution estimation, without public randomness, any utility-optimal heavy hitter estimation algorithm must require $\Omega(\log n)$ bits of communication per user.

Cite this Paper

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 no public randomness. We also show that Hadamard Response, a recently proposed scheme for $\eps$-LDP distribution estimation is also utility-optimal for heavy hitters estimation. Our final result shows that unlike distribution estimation, without public randomness, any utility-optimal heavy hitter estimation algorithm must require $\Omega(\log n)$ bits of communication per user.} }
Endnote
%0 Conference Paper %T Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters %A Jayadev Acharya %A Ziteng Sun %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-acharya19c %I PMLR %P 51--60 %U https://proceedings.mlr.press/v97/acharya19c.html %V 97 %X 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 no public randomness. We also show that Hadamard Response, a recently proposed scheme for $\eps$-LDP distribution estimation is also utility-optimal for heavy hitters estimation. Our final result shows that unlike distribution estimation, without public randomness, any utility-optimal heavy hitter estimation algorithm must require $\Omega(\log n)$ bits of communication per user.
APA
Acharya, J. & Sun, Z.. (2019). Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:51-60 Available from https://proceedings.mlr.press/v97/acharya19c.html.

Related Material