User-level and federated local differential privacy
summary
Shows that imposing user-level LDP (each user holds T samples) interpolates between item-level LDP and central DP and changes minimax rates: central mean error scales like 1/(n^2 α^2), item-level LDP like 1/(n α^2), while with T→∞ an infinite-T exponential rate in n appears. Proves lower bounds via Fano/Assouad and gives mechanisms (randomized response + majority vote, split-sample voting then local estimation) that recover sparse high‑dimensional rates (error ≈ s/T under mild conditions), permitting d exponentially large.
AI-written summary · about
chapters (7)
- 0:00Introduction
- 1:23DP definitions central vs local
- 4:12Local DP rates user-level DP
- 9:18User-level DP framework
- 19:28Minimax framework infinite T
- 29:52Sparse mean estimation under DP
- 34:10Q&A
related talks
58mLarge-Scale Private Learning, Part III
33mHeterogeneity and Privacy in Modern Learning
44mFederated Heavy Hitters Discovery with Differential Privacy
44mLocally Private Statistical Inference: Communication, Samples, and Shared Randomness
28mPrivacy versus Robustness in Federated Learning: Limits and Algorithms
36mLearning without Interaction Requires Separation
50mPrivacy Amplification by Sampling and Renyi Differential Privacy
01h 14mTutorial: Privacy, Part II