2022/07/03 by Edith Cohen, Cohen, Edith, Jelani Nelson +5 · 3 citations
Computer Science · #Adversarial Robustness in Machine Learning #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2207.00956
openalex publication_date 2022/07/03 · openalex created_date 2022/07/07 · openalex updated_date 2026/07/28
CountSketch and Feature Hashing (the "hashing trick") are popular randomized dimensionality reduction methods that support recovery of ℓ2-heavy hitters (keys i where vi2 > ε‖\boldsymbolv‖22) and approximate inner products. When the inputs are \em not adaptive (do not depend on prior outputs), classic estimators applied to a sketch of size O(ℓ/ε) are accurate for a number of queries that is exponential in ℓ. When inputs are adaptive, however, an adversarial input can be constructed after O(ℓ) queries with the classic estimator and the best known robust estimator only supports O(ℓ2) queries. In this work we show that this quadratic dependence is in a sense inherent: We design an attack that after O(ℓ2) queries produces an adversarial input vector whose sketch is highly biased. Our attack uses "natural" non-adaptive inputs (only the final adversarial input is chosen adaptively) and universally applies with any correct estimator, including one that is unknown to the attacker. In that, we expose inherent vulnerability of this fundamental method.