Private Frequency Estimation via Projective Geometry
Jelani Nelson (UC Berkeley)

We propose a new algorithm ProjectiveGeometryResponse (PGR) for locally differentially private (LDP) frequency estimation. For a universe size of $k$ and with $n$ users, our $\varepsilon$-LDP algorithm has communication cost $\lceil \log_2 k\rceil$ bits in the private coin setting and $\varepsilon\log_2 e+O(1)$ in the public coin setting, and has computation cost $O(n+k\exp(\varepsilon)\log k)$ for the server to approximately reconstruct the frequency histogram, while achieving optimal privacy/utility tradeoff, including optimality of the leading constant factor. Our empirical evaluation shows a speedup of over 50x over PI-RAPPOR [3], while using approximately 75x less memory for practically relevant parameter settings. In addition, the running time of our algorithm is within an order of magnitude of HadamardResponse [1] and RecursiveHadamardResponse [2] which have significantly worse reconstruction error. 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 on the server side. We also give an extension of PGR, which we call HybridProjectiveGeometryResponse, that allows trading off computation time with utility smoothly.

Joint work with Vitaly Feldman (Apple), Huy Le Nguyen (Northeastern), and Kunal Talwar (Apple). This work is to appear in ICML 2022.

[1] Jayadev Acharya, Ziteng Sun, Huanyu Zhang. Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1120--129, 2019.

[2] Wei-Ning Chen, Peter Kairouz, Ayfer Özgür. Breaking the Communication-Privacy-Accuracy Trilemma. Proceedings of the 32nd Annual Conference on Advances in Neural Information Processing Systems (NeurIPS), 2020.

[3] Vitaly Feldman and Kunal Talwar. Lossless Compression of Efficient Private Local Randomizers. Proceedings of the 38th International Conference on Machine Learning (ICML), pages 3208--3219, 2021