Estimating Sparse Discrete Distributions Under Privacy and Communication Constraints

Jayadev Acharya, Peter Kairouz, Yuhan Liu, Ziteng Sun
Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:79-98, 2021.

Abstract

We consider the problem of estimating sparse discrete distributions under local differential privacy (LDP) and communication constraints. We characterize the sample complexity for sparse estimation under LDP constraints up to a constant factor, and the sample complexity under communication constraints up to a logarithmic factor. Our upper bounds under LDP are based on the Hadamard Response, a private coin scheme that requires only one bit of communication per user. Under communication constraints we propose public coin schemes based on random hashing functions. Our tight lower bounds are based on recently proposed method of chi squared contractions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v132-acharya21b, title = {Estimating Sparse Discrete Distributions Under Privacy and Communication Constraints}, author = {Acharya, Jayadev and Kairouz, Peter and Liu, Yuhan and Sun, Ziteng}, booktitle = {Proceedings of the 32nd International Conference on Algorithmic Learning Theory}, pages = {79--98}, year = {2021}, editor = {Feldman, Vitaly and Ligett, Katrina and Sabato, Sivan}, volume = {132}, series = {Proceedings of Machine Learning Research}, month = {16--19 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v132/acharya21b/acharya21b.pdf}, url = {https://proceedings.mlr.press/v132/acharya21b.html}, abstract = {We consider the problem of estimating sparse discrete distributions under local differential privacy (LDP) and communication constraints. We characterize the sample complexity for sparse estimation under LDP constraints up to a constant factor, and the sample complexity under communication constraints up to a logarithmic factor. Our upper bounds under LDP are based on the Hadamard Response, a private coin scheme that requires only one bit of communication per user. Under communication constraints we propose public coin schemes based on random hashing functions. Our tight lower bounds are based on recently proposed method of chi squared contractions.} }
Endnote
%0 Conference Paper %T Estimating Sparse Discrete Distributions Under Privacy and Communication Constraints %A Jayadev Acharya %A Peter Kairouz %A Yuhan Liu %A Ziteng Sun %B Proceedings of the 32nd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Vitaly Feldman %E Katrina Ligett %E Sivan Sabato %F pmlr-v132-acharya21b %I PMLR %P 79--98 %U https://proceedings.mlr.press/v132/acharya21b.html %V 132 %X We consider the problem of estimating sparse discrete distributions under local differential privacy (LDP) and communication constraints. We characterize the sample complexity for sparse estimation under LDP constraints up to a constant factor, and the sample complexity under communication constraints up to a logarithmic factor. Our upper bounds under LDP are based on the Hadamard Response, a private coin scheme that requires only one bit of communication per user. Under communication constraints we propose public coin schemes based on random hashing functions. Our tight lower bounds are based on recently proposed method of chi squared contractions.
APA
Acharya, J., Kairouz, P., Liu, Y. & Sun, Z.. (2021). Estimating Sparse Discrete Distributions Under Privacy and Communication Constraints. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 132:79-98 Available from https://proceedings.mlr.press/v132/acharya21b.html.

Related Material