On the Power of Interactivity in Local Differential Privacy
summary
Defines a compositionality parameter K-compositional and proves any fully interactive ε‑DP protocol with that property compiles to a sequentially interactive one that preserves transcript distribution with sample blowup ≈ K·e^ε, using a rejection sampling simulation plus a generalized data-independent decomposition of local randomizers. Gives a concrete separation: a pointer‑jumping family has a K‑compositional fully interactive solution with ~d^2/ε^2 samples but forces Ω(d^3/ε^2) for sequential protocols, and shows optimal locally private hypothesis tests are noninteractive.
AI-written summary · about
chapters (13)
- 0:00Intro
- 3:17Formalizing things a bit.
- 9:28Three kinds of Interactivity in the Local Model
- 13:32This Work
- 17:55Is everything compositional? No!
- 19:58From Full to Sequential Adaptivity
- 21:47Bayesian Thought Experiment.
- 28:00Idea 2: Private Rejection Sampling
- 35:43Idea 3: Data Independent Decomposition
- 36:11Putting it All Together
- 37:08A Hard Problem for Sequential Interactivity
- 41:27Analysis
- 45:18Hypothesis Testing
related talks
37mUser-level and federated local differential privacy
33mHeterogeneity and Privacy in Modern Learning
01h 00mDifferential Privacy And The Complexity Of Simple Queries
09mIntegrating Differential Privacy and Contextual Integrity
26mAaron Roth, Associate Professor, University of Pennsylvania, NYC 2017
35mDifferential Privacy Made Practical
09mFrom Robustness to Privacy and Back
01h 14mTutorial: Privacy, Part II