For finite discrete distributions, a recursive mechanism that preserves the public prior is exactly minimax optimal for every f-divergence, and reduces to randomized response when the prior is uniform.
Optimal Compression of Locally Differentially Private Mechanisms
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Compressing the output of \epsilon-locally differentially private (LDP) randomizers naively leads to suboptimal utility. In this work, we demonstrate the benefits of using schemes that jointly compress and privatize the data using shared randomness. In particular, we investigate a family of schemes based on Minimal Random Coding (Havasi et al., 2019) and prove that they offer optimal privacy-accuracy-communication tradeoffs. Our theoretical and empirical findings show that our approach can compress PrivUnit (Bhowmick et al., 2018) and Subset Selection (Ye et al., 2018), the best known LDP algorithms for mean and frequency estimation, to to the order of \epsilon-bits of communication while preserving their privacy and accuracy guarantees.
fields
cs.LG 1years
2024 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Locally Private Sampling with Public Data
For finite discrete distributions, a recursive mechanism that preserves the public prior is exactly minimax optimal for every f-divergence, and reduces to randomized response when the prior is uniform.