Learning without Interaction Requires Separation
summary
Shows that non‑interactive local differential privacy (LDP) provably needs many more samples: any non‑interactive LDP PAC learner for a negation‑closed class requires at least margin complexity^(2/3) examples, via the known statistical query equivalence that simulates LDP. Corollaries give exponential sample lower bounds for decision lists and for boolean linear classifiers under the uniform distribution. Proof tools are reductions to correlation dimension/margin complexity; an upper bound uses perceptron‑style expected updates with public or unlabeled samples.
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:47Local Differential Privacy (LDP)
- 2:57Non-interactive LDP
- 3:56PAC learning
- 5:44Statistical query model [Kearns 93]
- 13:43Margin Complexity
- 22:16Lower bound technique
- 26:37Upper bound
- 27:53Algorithm
- 31:08Conclusions
related talks
33mHeterogeneity and Privacy in Modern Learning
37mUser-level and federated local differential privacy
58mLarge-Scale Private Learning, Part III
01h 00mDifferential Privacy And The Complexity Of Simple Queries
17mData privacy and reliable learning
01h 02mLarge-Scale Private Learning, Part I
19mPractical Considerations for Differential Privacy
01h 03mStatistical Inference and Privacy, Part II