Timezone: »

 
Poster
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters
Jayadev Acharya · Ziteng Sun

Tue Jun 11 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #177
in Posters Tue »
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.
Keywords: Information Theory and Estimation · Privacy-preserving Statistics and Machine Learning

Author Information

Jayadev Acharya (Cornell University)
Ziteng Sun (Cornell/Google)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors