Robustness of Sketches to Adaptive nputs
summary
Shows how a differential-privacy-style wrapper (replicating sketches, DP aggregation) gives robustness to adaptive inputs and supports about d^2 queries on a sketch of dimension d, then reduces an awkward epsilon^3 loss by a per-bucket redesign of CountSketch so privacy can be charged more finely and the bound becomes square. Also delivers matching-style negative results: the standard median estimator breaks with only linear many queries, and any correct heavy-hitter estimator for CountSketch admits a quadratic attack (simple vectors: one fixed heavy key plus random tails, barely adaptive and efficient), with empirical success on vision models.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:13Adaptive inputs and risks
- 5:18Statistical queries and overfitting
- 8:12Differential privacy for queries
- 11:42Differential privacy in algorithms
- 16:08CountSketch design
- 23:02Robust CountSketch with DP
- 26:45Tighter CountSketch bounds
- 31:23Attacks on linear sketches
- 36:54CountSketch classic estimator
- 39:25Attacks on heavy hitters
- 43:23Attacks on ML models
- 45:38Q&A
- 49:05Closing remarks
related talks
44mHow Robust are Linear Sketches to Adaptive Inputs?
30mA Strong Separation for Adversarially Robust L_0 Estimation for Linear Sketches
47mA Blackbox Reduction for Adaptive Adversaries using Differential Privacy
58mLarge-Scale Private Learning, Part III
01h 03mAdversarially Robust Streaming Algorithms
43mDifferential Privacy Meets Robust Statistics
40mEvasion, Poisoning, Extraction, and Inference: Tools to Defend and Evaluate
01h 00mDifferential Privacy: Fundamentals to Forefront I