Privacy Amplification by Sampling and Renyi Differential Privacy
summary
Provides a usable amplification bound that maps a mechanism's Rényi DP curve to the subsampled mechanism, with near-tight constants and matching lower bounds for Gaussian and Laplace noise; Poisson sampling yields exact formulas. Shows a phase transition when gamma = m/n and alpha interact, explains why composed noisy-SGD gains orders of magnitude over epsilon‑delta composition, and implements an analytic moment accountant to track RDP composition and convert to (epsilon, delta). Proof uses ternary Pearson divergences.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 0:20Agenda
- 1:41Differential Privacy
- 7:58Other mechanisms
- 12:05SGD
- 14:37Use Cases
- 16:15Generic amplification lemma
- 18:38Generic amplification bomb
- 19:49Sampling without replacement
- 21:31Intuition
- 24:17Technical result
- 26:36Analysis
- 29:29Comparison
- 31:03Data Structure
- 33:32Results
- 37:42Proof
- 39:01Divergences
- 41:47Subsampling
related talks
01h 14mTutorial: Privacy, Part II
43mPrivacy Amplification by Sampling in Practice
54mPrivacy Amplification from Structured Algorithmic Randomness
35mPrivacy amplification by random allocation
01h 00mDifferential Privacy: Fundamentals to Forefront I
26mAaron Roth, Associate Professor, University of Pennsylvania, NYC 2017
31mGaussian Differential Privacy (GDP)
37mUser-level and federated local differential privacy