Algorithms with More Granular Differential Privacy Guarantees

on YouTube ↗26m

" summary

Defines per-attribute differential privacy and gives concrete algorithms that trade per-person epsilon for much smaller per-attribute epsilon0. Uses Gaussian projection to answer k‑way marginals with average error scaling like sqrt(k/(ε0 n)) instead of sqrt(d/(ε n)), and a modified multiplicative‑weights/exponential mechanism that samples l≈d/k queries in parallel to control worst‑case error over disjoint sets. For histograms a recursive heavy‑hitters builder yields max error ~log d / ε0 versus the standard d / ε worst case, demonstrating exponential separation.

AI-written summary · about

" chapters (9)

1. 0:00Intro
2. 0:42Background: Differential Privacy (DP)
3. 2:14Motivating question: How to interpret ?
4. 4:44What do "Nice" DP Algorithms Look Like?
5. 10:33Algorithms for k-way Marginals: Average Error
6. 13:53Algorithms for k-way Marginals: Max Error
7. 16:45Histograms/Heavy Hitters
8. 20:54Our Heavy Hitters Algorithm
9. 23:30Conclusion

" related talks

• 01h 00mDifferential Privacy And The Complexity Of Simple QueriesJonathan Ullman · Rigorous Evidence for Information-Computation Trade-offs
• 01h 00mDifferential Privacy: Fundamentals to Forefront ICynthia Dwork · Cryptography Boot Camp 2015
• 01h 02mLarge-Scale Private Learning, Part IKunal Talwar · Data Privacy: Foundations and Applications Boot Camp
• 01h 03mStatistical Inference and Privacy, Part IIGautam Kamath · Data Privacy: Foundations and Applications Boot Camp
• 30mAccuracy First: Selecting a Differential Privacy Level for Accuracy-Constrained...Katrina Ligett · Optimization, Statistics and Uncertainty
• 31mGaussian Differential Privacy (GDP)Jinshuo Dong · Beyond Differential Privacy 2019
• 01h 14mTutorial: Privacy, Part IIAdam M. Smith, Lydia Zakynthinou · Federated and Collaborative Learning Boot Camp 2026
• 42mDifferential PrivacyKunal Talwar · Uncertainty in Computation 2016