Towards a Characterization of Differentially Private Learning
summary
Shows that private PAC learnability implies a finite Littlestone dimension and that private proper learning is equivalent to private uniform convergence. Proofs embed arbitrarily many thresholds via a Ramsey-style lower bound, giving sample-complexity lower bounds that grow extremely slowly (roughly log* of the dimension). Builds a private sanitizer by an online Alice/Bob game: propose candidate samples, get counterexamples, and turn a private proper learner into a private convergent mechanism; arguments are information-theoretic, not computational.
AI-written summary · about
chapters (12)
- 0:00Intro
- 3:52Supervised Learning (Binary Classification)
- 5:59Uniform Convergence, Learnability
- 7:19Vapnik Chervonenkis Dimension
- 9:06The Fundamental Theorem of PAC Learning
- 9:50Private Uniform Convergence and Learnability
- 12:53Littlestone Dimension (= adaptive VC dimension)
- 16:42Private Learnability Implies Finite Littlestone Dimension
- 26:52Recall: Uniform Convergence
- 27:19Private uniform convergence Private proper learning
- 27:45Private proper learning → Private uniform convergence
- 32:20Private proper learning = Private uniform convergence
related talks
17mData privacy and reliable learning
33mHeterogeneity and Privacy in Modern Learning
37mUser-level and federated local differential privacy
01h 02mLarge-Scale Private Learning, Part I
28mPrivacy versus Robustness in Federated Learning: Limits and Algorithms
01h 16mLaw and CS
36mPrivately Learning High-Dimensional Distributions
33mPrivacy of Decentralized Machine Learning