Locally Private Histograms in All Privacy Regimes
summary
Shows that the standard bitwise randomized-response protocol RAPPOR already attains much better accuracy in the low-privacy (large ε) regime once analyzed with the Kearns–Saul inequality and a recent Cohen–Kontorovich product-distribution bound: error smoothly interpolates from the known O(√(log k/(n ε^2))) high-privacy rate to a substantially smaller large-ε rate (roughly O((log k)/(n ε)) up to exponential factors), and a matching lower bound (modulo an e^{Θ(ε)} constant) is proved. Communication remains k bits per user, so implementation is trivial but costly.
AI-written summary · about
chapters (16)
- 0:00Locally private histograms
- 1:03Problem setup and privacy
- 3:52Local differential privacy
- 5:18Histogram estimation goal
- 7:30High privacy challenges
- 8:54Privacy parameters implications
- 9:38Subgaussian random variables
- 11:10Frequency estimation algorithm
- 12:59Accuracy with repetition
- 14:47Kearns-Saul inequality bounds
- 16:34Lower bounds attempt
- 17:38Cohen-Kontorovich results
- 19:45Key takeaways and improvements
- 20:47Revisiting solved privacy
- 21:29Open questions and future
- 22:12Q&A
related talks
44mLocally Private Statistical Inference: Communication, Samples, and Shared Randomness
01h 03mStatistical Inference and Privacy, Part II
30mAccuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained...
58mLarge-Scale Private Learning, Part III
35mPrivacy amplification by random allocation
53mOptimality in Locally Private Estimation and Learning
01h 00mDifferential Privacy: Fundamentals to Forefront I
26mAlgorithms with More Granular Differential Privacy Guarantees