Differential Privacy: Fundamentals to Forefront II
summary
Defines the privacy loss random variable and relaxes pure privacy to epsilon delta so composition error grows like √k (with log(1/δ) factors) instead of k. Shows sparse vector as an ε-differentially private primitive that halts at the first significant query and pays per significant result, and uses private multiplicative weights to answer many counting queries with error tied to N and log universe size. Replaces Laplace with Gaussian noise (L2 sensitivity) for better accuracy, develops concentrated-DP, and enables a reusable DP holdout for adaptive analysis.
AI-written summary · about
chapters (19)
- 0:00Start
- 1:10The Privacy Loss Random Variable
- 10:14Adversary's Goal: Guess b
- 13:14Bounding Expected Loss
- 14:29Sparse Vector ▸ Database size n
- 27:02Limit for Large Universe Size
- 30:33Addition of Gaussian Noise
- 31:39Privacy Loss with Gaussian Noise
- 32:52Taking a Closer Look
- 34:27Concentrated Differential Privacy
- 38:36Propose-Test-Release Want to compute the median ▸ For "nice" distributions this is very stable.
- 42:50Continual Observation Algorithms
- 45:16Counter: The Segment Construction Maintain counters for all intervals of length powers of 2 (see drawing)
- 47:23Not a Panacea
- 48:23Privacy and Mechanism Design
- 50:32Great Efforts to Control False Discovery
- 53:11Intuition
- 54:42DP, Stability, and Generalization Known connections between nations of the stability of a leaming algorithm and its ability to generalize
- 58:45Conclusion
related talks
20mDesigning for User Privacy: Integrating Differential Privacy into Ad Measurement...
20mShare data without revealing personal information
39mPufferfish Privacy Mechanisms for Correlated Data
21m"SECRETS ARE LIES, SHARING IS CARING, PRIVACY IS THEFT." - A Dive into Privacy Preserving
40mOn the Complexity of Two-Party Differential Privacy
34mEfficient Robust Private Aggregation for DP
18mProtecting User Privacy in Private Set Intersection: A Journey Toward Mitigating User
29mTalk by Audra McMillan (Apple Inc)