Skip to yearly menu bar Skip to main content


Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters

Jayadev Acharya · Ziteng Sun

Pacific Ballroom #177

Keywords: [ Privacy-preserving Statistics and Machine Learning ] [ Information Theory and Estimation ]

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 \emph{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.

Live content is unavailable. Log in and register to view live content