Optimality in Locally Private Estimation and Learning
summary
Proves lower bounds for locally private estimation by reducing estimation to testing via Assouad’s method and a communication-complexity / strong data processing inequality argument under a KL-local privacy budget. For D-dimensional Bernoulli means the minimax squared error is Ω( D · min(1, D/(N · ε_avg)) ), so when N is large the private rate incurs an extra factor D/(N·ε_avg) versus the central D/N rate. The construction and bound are explicit and information-theoretic.
AI-written summary · about
chapters (8)
- 0:00Start
- 0:15Outline
- 1:10The Local Model of Privacy
- 3:12Communication Scheme
- 15:01Intuition
- 26:58Swats Method
- 35:35Sdp Strong Data Processing Inequality
- 46:25Bounded Likelihood Ratio
related talks
17mData privacy and reliable learning
21mDimension-free Private Mean Estimation for Anisotropic Distributions
15mFundamental Limits Of Learning In Data-Driven Problems
01h 02mLarge-Scale Private Learning, Part I
58mLarge-Scale Private Learning, Part III
01h 03mStatistical Inference and Privacy, Part II
26mLocally Private Histograms in All Privacy Regimes
37mUser-level and federated local differential privacy