A Blackbox Reduction for Adaptive Adversaries using Differential Privacy

on YouTube ↗47m

" summary

A black-box transformation converts any dynamic estimation algorithm that is correct against an oblivious adversary into one robust against an adaptive adversary by running about sqrt(T) copies, returning a private median of their outputs, and paying a runtime overhead ≈ T · sqrt(T) instead of T². Privacy of each copy’s randomness uses adaptive composition (giving the √ factor) and DP’s generalization guarantees that most copies remain accurate, so the private median yields a slightly degraded γ(1+α) approximation.

AI-written summary · about

" chapters (7)

1. 0:00Start
2. 3:34The Setting
3. 4:49Dynamic Estimation Algorithms
4. 14:01Differential Privacy
5. 20:00Main Steps
6. 22:17Adaptive Composition
7. 40:35Proof of Claim: Applying Generalization

" related talks

• 50mRobustness of Sketches to Adaptive nputsEdith Cohen · Sketching and Algorithm Design 2023
• 26mA Framework for Adversarial Streaming via Differential Privacy and Difference EstimatorsIdan Attias, Edith Cohen, Moshe Shechner, Uri Stemmer · ITCS 2023
• 43mDifferential Privacy Meets Robust StatisticsSewoong Oh · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 01h 00mDifferential Privacy: Fundamentals to Forefront ICynthia Dwork · Cryptography Boot Camp 2015
• 58mLarge-Scale Private Learning, Part IIIIlya Mironov · Data Privacy: Foundations and Applications Boot Camp
• 26mGeneralized Private Selection and Testing with High ConfidenceEdith Cohen, Uri Stemmer, Xin Lyu, Jelani Nelson, Tamás Sarlós · ITCS 2023
• 32mYou've got trust issues, we've got solutions: Differential PrivacyVikram Waradpande · PyCon US 2024
• 16mHow to Break, Then Fix, Differential Privacy on Finite ComputersDamien Desfontaines, Samuel Haney · PEPR '23