Differential Privacy: Fundamentals to Forefront I
summary
Formalizes differential privacy as outputs changing by at most an e^epsilon factor when any one person is added or removed; gives concrete mechanisms: randomized response (ln 3 ≈ 1.098 privacy factor, √N error), the Laplace mechanism (add noise scaled to sensitivity/epsilon, histogram cells need noise ~1/epsilon) and the exponential mechanism (sample with probability ∝ exp(epsilon·utility/2Δ)). Shows synthetic-database construction via alpha‑nets (size ~ log|Q|/α^2) yielding ~n^{2/3} error while supporting exponentially many queries in low dimension, notes Google deploys randomized response for Chrome, and proves cryptographic hardness (exponential time) for some synthetic-data tasks.
AI-written summary · about
chapters (16)
- 0:00Intro
- 2:47The Statistics Masquerade
- 7:17Privacy-Preserving Data Analysis?
- 15:03Properties
- 25:07Vector-Valued Functions
- 26:01Why Does it Work?
- 31:40Accuracy of the Laplace Mechanism
- 33:10Report Noisy ArgMax
- 37:03The Exponential Mechanism
- 39:15Utility of Exponential Mechanism
- 43:48Radical Application of Exp Mech
- 48:29The Role of Data Dimensionality
- 50:00Efficiency?
- 52:57Efficient Synopsis Generation?
- 55:12Start with a Traitor Tracing Scheme Private key length x, ciphertext length One universe element for each private key
- 56:36Intuition for the Converse
related talks
30mAccuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained...
42mDifferential Privacy
26mAlgorithms with More Granular Differential Privacy Guarantees
19mPractical Considerations for Differential Privacy
01h 03mStatistical Inference and Privacy, Part II
43mDifferential Privacy Meets Robust Statistics
58mLarge-Scale Private Learning, Part III
32mYou've got trust issues, we've got solutions: Differential Privacy