Lossless Compression of Efficient Private Local Randomizers
By Vitaly Feldman, Kunal Talwar. 2021
48 citations recorded by the source corpus.
Locally Differentially Private (LDP) Reports are commonly used for collection of statistics and machine learning in the federated setting. In many cases the best known LDP algorithms require sending prohibitively large messages from the client device to the server (such as when constructing histograms over large domain or learning a high-dimensional model). This has led to significant efforts on reducing the communication cost of LDP algorithms. At the same time LDP reports are known to have relatively little information about the user's data due to randomization. Several schemes are known that exploit this fact to design low-communication versions of LDP algorithm but all of them do so at the expense of a significant loss in utility. Here we demonstrate a general approach that, under standard cryptographic assumptions, compresses every efficient LDP algorithm with negligible loss in privacy and utility guarantees. The practical implication of our result is that in typical applications the message can be compressed to the size of the server's pseudo-random generator seed. More generally, we relate the properties of an LDP randomizer to the power of a pseudo-random generator that suffices for compressing the LDP randomizer. From this general approach we derive low-communication algorithms for the problems of frequency estimation and high-dimensional mean estimation. Our algorithms are simpler and more accurate than existing low-communication LDP algorithms for these well-studied problems.
Subfields: Artificial Intelligence, Electrical and Electronic Engineering
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Ayfer Özgür
- Wei-Ning Chen
- Peter Kairouz
- Vitaly Feldman
- Kunal Talwar
- Pramod Viswanath
- Jayadev Acharya
- Sewoong Oh
In Electrical and Electronic Engineering
Citations in the corpus
- Breaking the Communication-Privacy-Accuracy Trilemma (2020, background): “6We remark that after our paper being published, a recent work [41] shows that DJW and its improved version privUnit [7] can be compressed in a more efficient way.”