Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs

• URL: http://arxiv.org/abs/2207.00956v1
• Date: Sun, 3 Jul 2022 05:00:55 GMT
• Title: Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs
• Abstract summary: We show that when inputs are adaptive, an adversarial input can be constructed after $O(ell)$ queries. Our attack uses "natural" non-adaptive inputs (only the final adversarial input is chosen adaptively) and universally applies with any correct estimator.
• Score: 25.724067100459916
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: CountSketch and Feature Hashing (the "hashing trick") are popular randomized dimensionality reduction methods that support recovery of $\ell_2$-heavy hitters (keys $i$ where $v_i^2 > \epsilon \|\boldsymbol{v}\|_2^2$) 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(\ell/\epsilon)$ are accurate for a number of queries that is exponential in $\ell$. When inputs are adaptive, however, an adversarial input can be constructed after $O(\ell)$ queries with the classic estimator and the best known robust estimator only supports $\tilde{O}(\ell^2)$ queries. In this work we show that this quadratic dependence is in a sense inherent: We design an attack that after $O(\ell^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.

Related papers

• Small-Bias Quantum Approximate Counting via the Multiplicative Adversary Method [1.2799130177714182]
  We study the two-weight decision version of quantum approximate counting.<n>Given oracle access to $xin0,1N$, distinguish $|x|=M$ from $|x|=M+$ with success probability $1/2+$.<n>Using the multiplicative adversary method, we prove $left(maxleftsqrt(N-M)(M+)/,sqrtN/rightright)$.
  arXiv  Detail & Related papers  (2026-09-09T07:01:11Z)
• The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation [27.82218389495089]
  Dimensionality reduction via linear sketching is a powerful and widely used technique, but it is known to be vulnerable to adversarial inputs.<n>We study the black-box adversarial setting, where a fixed, hidden sketching matrix A in $Rk X n$ maps high-dimensional vectors v $in Rn$ to lower-dimensional sketches A v in $Rk$.<n>We present a universal, nonadaptive attack that, using tilde(O)($k2$) queries, either causes a failure in norm estimation or constructs an adversarial input on which the optimal estimator for the query distribution fails
  arXiv  Detail & Related papers  (2025-07-22T08:25:05Z)
• Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update [62.96781471194877]
  Two principled strategies for handling heavy-tailed noise, truncation and median-of-means, have been introduced to heavy-tailed bandits.<n>We propose a emphone-pass algorithm based on the online mirror descent framework.
  arXiv  Detail & Related papers  (2025-03-01T09:41:45Z)
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  Motivated by crowdsourcing, we consider a problem where we partially observe the correctness of the answers of $n$ experts on $d$ questions. In this paper, we assume that the matrix $M$ containing the probability that expert $i$ answers correctly to question $j$ is bi-isotonic up to a permutation of it rows and columns. We construct an efficient-time algorithm that turns out to be minimax optimal for this classification problem.
  arXiv  Detail & Related papers  (2024-08-27T18:28:31Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  Learning from human feedback plays an important role in aligning generative models, such as large language models (LLM) We study a model within this domain--contextual dueling bandits with adversarial feedback, where the true preference label can be flipped by an adversary. We propose an algorithm namely robust contextual dueling bandits (RCDB), which is based on uncertainty-weighted maximum likelihood estimation.
  arXiv  Detail & Related papers  (2024-04-16T17:59:55Z)
• Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
  We propose the first computationally efficient horizon-free algorithm for linear mixture MDPs. Our algorithm adapts a weighted least square estimator for the unknown transitional dynamic. This also improves upon the best-known algorithms in this setting when $sigma_k2$'s are known.
  arXiv  Detail & Related papers  (2022-05-23T17:59:18Z)
• On the Robustness of CountSketch to Adaptive Inputs [22.34019676119989]
  CountSketch is a popular dimensionality reduction technique that maps vectors to a lower dimension using randomized linear measurements. We show that the classic estimator is not robust, and can be attacked with a number of queries of the order of the sketch size. We propose a robust estimator that allows for quadratic number of queries in the sketch size.
  arXiv  Detail & Related papers  (2022-02-28T13:04:41Z)
• Smoothed Analysis with Adaptive Adversaries [28.940767013349408]
  We prove novel algorithmic guarantees for several online problems in the smoothed analysis model. In this model, at each time an adversary chooses an input distribution with density function bounded above by $tfrac1sigma$ times that of the uniform distribution. Our results hold for em adaptive adversaries that can choose an input distribution based on the decisions of the algorithm and the realizations of the inputs in the previous time steps.
  arXiv  Detail & Related papers  (2021-02-16T20:54:49Z)
• CountSketches, Feature Hashing and the Median of Three [18.85876632959721]
  We revisit the classic CountSketch method, which is a sparse, random projection that transforms a (high-dimensional) Euclidean vector $v$ to a vector of dimension $(2t-1) s$. Our main contribution is a new analysis of Count-Sketch, showing an improvement in variance to $O(min|v|2/s2,|v|2/s2)$ when $t > 1$. This finding suggests that the Feature Hashing method, which is essentially identical to CountSketch but does not make use of the median, can be made
  arXiv  Detail & Related papers  (2021-02-03T18:45:21Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  Inversion bias arises when averaging estimates of quantities that depend on the inverse covariance. We develop a framework for analyzing inversion bias, based on our proposed concept of an $(epsilon,delta)$-unbiased estimator for random matrices. We show that when the sketching matrix $S$ is dense and has i.i.d. sub-gaussian entries, the estimator $(epsilon,delta)$-unbiased for $(Atop A)-1$ with a sketch of size $m=O(d+sqrt d/
  arXiv  Detail & Related papers  (2020-11-21T01:33:15Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  We study learning in contextual bandits with the help of loss predictors. We show that the optimal regret is $mathcalO(minsqrtT, sqrtmathcalETfrac13)$ when $mathcalE$ is known.
  arXiv  Detail & Related papers  (2020-03-04T07:36:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.