How Robust are Linear Sketches to Adaptive Inputs?
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19·
summary
Shows a reconstruction attack that, given oracle access to any r‑row linear sketch, uses Gaussian query distribution and polynomially many adaptive queries to learn a subspace approximation and produce inputs where the sketch fails on the gap‑norm (≤1 vs ≥B) promise. The method combines a conditional‑expectation lemma and a boosting step (top singular vector of accepted samples) and runs in poly(r,B) time. Consequence: linear sketches cannot solve L2/L2 sparse recovery on polynomially many adaptive queries with fewer than n / C^2 lower bound rows, and the attack succeeds with high probability.
AI-written summary · about
chapters (18)
- 0:00Intro
- 0:22Two Aspects of Coping with Big Data
- 1:16Algorithmic paradigm: Linear Sketches
- 4:30Example: Johnson-Lindenstrauss Sketch
- 8:22Benchmark Problem
- 9:26Main Result
- 13:02Outline
- 13:29Computational Model
- 18:46Conditional Expectation Lemma
- 20:40Simplification
- 21:14The three step intuition
- 25:09By correctness of sketch
- 28:55Sliding X2-distributions
- 33:30Averaging Argument
- 35:21Boosting small correlations
- 37:30Implementation in poly(r) time
- 38:22Iterating previous steps
- 39:49Open Problems
related talks
30mA Strong Separation for Adversarially Robust L_0 Estimation for Linear Sketches
50mRobustness of Sketches to Adaptive nputs
01h 03mAdversarially Robust Streaming Algorithms
01h 24mAdversarial Examples
25mThe Whole is Greater than the Sum of its Parts: Linear Garbling and Applications
01h 06mOn the Assumptions Used for Obfuscation
46mLessons Learned from Evaluating the Robustness of Defenses to Adversarial Examples
47mA Blackbox Reduction for Adaptive Adversaries using Differential Privacy