Timezone: »

 
Poster
Private frequency estimation via projective geometry
Vitaly Feldman · Jelani Nelson · Huy Nguyen · Kunal Talwar

Wed Jul 20 03:30 PM -- 05:30 PM (PDT) @ Hall E #1023
in Poster Session 2 »

In this work, we propose a new algorithm ProjectiveGeometryResponse (PGR) for locally differentially private (LDP) frequency estimation. For universe size of k and with n users, our eps-LDP algorithm has communication cost ceil(log_2 k) and computation cost O(n + k\exp(eps) log k) for the server to approximately reconstruct the frequency histogram, while achieve optimal privacy-utility tradeoff. In many practical settings this is a significant improvement over the O~(n+k^2) computation cost that is achieved by the recent PI-RAPPOR algorithm (Feldman and Talwar; 2021). Our empirical evaluation shows a speedup of over 50x over PI-RAPPOR while using approximately 75x less memory. In addition, the running time of our algorithm is comparable to that of HadamardResponse (Acharya, Sun, and Zhang; 2019) and RecursiveHadamardResponse (Chen, Kairouz, and Ozgur; 2020) which have significantly worse reconstruction error. The error of our algorithm essentially matches that of the communication- and time-inefficient but utility-optimal SubsetSelection (SS) algorithm (Ye and Barg; 2017). Our new algorithm is based on using Projective Planes over a finite field to define a small collection of sets that are close to being pairwise independent and a dynamic programming algorithm for approximate histogram reconstruction for the server.

Keywords: SA: Privacy-preserving Statistics and Machine Learning

Author Information

Vitaly Feldman (Apple)
Jelani Nelson (UC Berkeley)
Huy Nguyen (Northeastern University)
Kunal Talwar (Apple)

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

More from the Same Authors