A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
summary
Presents a concrete algorithmic framework that combines difference estimators with differential privacy to convert oblivious streaming routines into adversarially robust ones, proving a general space blowup of square root of alpha lambda (more precisely O(√(α·λ))) versus prior O(λ), O(α·λ), or O(√λ) bounds. Builds a hybrid wrapper, adds a monitor and a new twist number stream statistic, applies it to F2 in the turnstile model and shows improved or matching space guarantees.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:28Talk Outline: Plan
- 1:08What is streaming?
- 4:52Streaming: Oblivious and Adaptive settings
- 6:42The Adaptive Inputs Setting: Motivation
- 7:45The Adaptive Inputs Setting: Possible approaches
- 9:15Robustification via wrapping techniques
- 13:47F₂ estimation in the 'turnstile' setting
- 16:20Difference Estimators [WZ '21]
- 21:06Recap
- 24:28Summary: Wrapping techniques performance
related talks
01h 03mAdversarially Robust Streaming Algorithms
47mA Blackbox Reduction for Adaptive Adversaries using Differential Privacy
01h 00mDifferential Privacy: Fundamentals to Forefront I
43mDifferential Privacy Meets Robust Statistics
58mLarge-Scale Private Learning, Part III
16mHow to Break, Then Fix, Differential Privacy on Finite Computers
27mVerified Differential Privacy for Finite Computers
28mPrivacy versus Robustness in Federated Learning: Limits and Algorithms