Privacy amplification by random allocation
summary
Analyzes k‑out‑t random allocation sampling and provides an algorithm that computes the privacy loss distribution (PLD) for that scheme efficiently, with runtime roughly scaling as 1/alpha^2 and polylogarithmic dependence on t; proves for the Gaussian mechanism that random allocation gives no privacy degradation vs Poisson subsampling and often slightly better epsilon bounds; supplies a PLD-to-PLD accounting tool, a working implementation on GitHub, and practical timings (order 100s on a laptop for realistic accuracies), enabling tight end‑to‑end DPSGD accounting.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 1:03Motivation for random allocation
- 3:54Sampling schemes and privacy gaps
- 5:00One out of t random allocation
- 6:23Distributed mean estimation
- 10:01Generalizing to k out of t
- 10:44Privacy analysis methods
- 11:51Random allocation and Poisson subsampling
- 16:57Formal privacy bounds
- 22:40Numerical privacy estimation
- 23:44Privacy loss accounting
- 27:21Experimental results
- 29:06Implementation in libraries
- 31:17PLLD accounting for subsampling
- 32:00Case study: DP-SGD with Preamble
- 33:24Conclusion
related talks
50mPrivacy Amplification by Sampling and Renyi Differential Privacy
54mPrivacy Amplification from Structured Algorithmic Randomness
01h 14mTutorial: Privacy, Part II
01h 02mLarge-Scale Private Learning, Part I
26mLocally Private Histograms in All Privacy Regimes
26mAlgorithms with More Granular Differential Privacy Guarantees
47mBlack-box Random Differential Privacy with Sensitivity Sampling
01h 00mDifferential Privacy: Fundamentals to Forefront I