Locally Differentially Private Protocols for Frequency Estimation
summary
Framework generalizes deployed LDP schemes (e.g. RAPPOR) and gives a fast aggregator with exact accuracy formulas, then derives two new mechanisms Optimized Unary Encoding and Optimized Local Hashing that minimize variance under ε-LDP. Unary and OLH achieve the smallest variance while direct/randomized encoding has variance Θ(d); unary costs O(d) communication, OLH uses hashing to get O(log n). Analysis gives when to pick each method, experiments show magnitude improvements, and limitations include n = Ω(d) and difficulty with extremely large domains.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 0:30Different Privacy
- 3:22Warner Model
- 7:33Direct Encoding
- 9:29Unary encoding
- 11:13Binary local hash
- 16:13Optimization
- 18:11Results
- 19:33Conclusion
- 20:57Questions
related talks
58mLarge-Scale Private Learning, Part III
37mUser-level and federated local differential privacy
53mOptimality in Locally Private Estimation and Learning
14mDifferentially-Private Software Frequency Profiling under Linear Constraints
44mLocally Private Statistical Inference: Communication, Samples, and Shared Randomness
18mDifferentially Private Continual Releases of Streaming Frequency Moment Estimations
26mLocally Private Histograms in All Privacy Regimes
30mAccuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained...