On the Robustness of CountSketch to Adaptive Inputs

• URL: http://arxiv.org/abs/2202.13736v1
• Date: Mon, 28 Feb 2022 13:04:41 GMT
• Title: On the Robustness of CountSketch to Adaptive Inputs
• Abstract summary: 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.
• Score: 22.34019676119989
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: CountSketch is a popular dimensionality reduction technique that maps vectors to a lower dimension using randomized linear measurements. The sketch supports recovering $\ell_2$-heavy hitters of a vector (entries with $v[i]^2 \geq \frac{1}{k}\|\boldsymbol{v}\|^2_2$). We study the robustness of the sketch in adaptive settings where input vectors may depend on the output from prior inputs. Adaptive settings arise in processes with feedback or with adversarial attacks. 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 (for a slightly modified sketch) that allows for quadratic number of queries in the sketch size, which is an improvement factor of $\sqrt{k}$ (for $k$ heavy hitters) over prior work.

Related papers

• Robust Estimation of Sparse Numerical Vectors under Local Differential Privacy [61.848691894557426]
  Local differential privacy (LDP) protocols are vulnerable to poisoning attacks.<n>In this paper, we address the robust sparse vector mean estimation problem.<n>We propose a correction method based on a careful analysis that gives an exact expression of the bias.
  arXiv  Detail & Related papers  (2026-07-30T07:55:09Z)
• 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)
• 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)
• SketchINR: A First Look into Sketches as Implicit Neural Representations [120.4152701687737]
  We propose SketchINR, to advance the representation of vector sketches with implicit neural models. A variable length vector sketch is compressed into a latent space of fixed dimension that implicitly encodes the underlying shape as a function of time and strokes. For the first time, SketchINR emulates the human ability to reproduce a sketch with varying abstraction in terms of number and complexity of strokes.
  arXiv  Detail & Related papers  (2024-03-14T12:49:29Z)
• Sketched Ridgeless Linear Regression: The Role of Downsampling [5.615701056715101]
  We investigate two out-of-sample prediction risks of the sketched ridgeless least square estimator. We identify the optimal sketching size that minimizes out-of-sample prediction risks. We extend our analysis to cover central limit theorems and misspecified models.
  arXiv  Detail & Related papers  (2023-02-02T13:21:09Z)
• Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs [25.724067100459916]
  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.
  arXiv  Detail & Related papers  (2022-07-03T05:00:55Z)
• Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs [2.737640280995564]
  We use network embeddings to perform dimensionality reduction of tensor network structured inputs $x$. We provide an algorithm to efficiently sketch input data using such embeddings. We show optimality of an existing algorithm for train rounding.
  arXiv  Detail & Related papers  (2022-05-26T05:27:31Z)
• Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel [15.535749953841274]
  Randomized sketches of a product of $p$ vectors follow a tradeoff between statistical efficiency and computational acceleration. We propose a simple Complex-to-Real (CtR) modification of well-known sketches that replaces real random projections by complex ones. We show that our method achieves state-of-the-art performance in terms of accuracy and speed compared to other randomized approximations from the literature.
  arXiv  Detail & Related papers  (2022-02-04T09:15:43Z)
• A Precise Performance Analysis of Support Vector Regression [105.94855998235232]
  We study the hard and soft support vector regression techniques applied to a set of $n$ linear measurements. Our results are then used to optimally tune the parameters intervening in the design of hard and soft support vector regression algorithms.
  arXiv  Detail & Related papers  (2021-05-21T14:26:28Z)
• Learning-Augmented Sketches for Hessians [54.97773807211337]
  We show how to design learned sketches for the Hessian in the context of second order methods. We show empirically that learned sketches, compared with their "non-learned" counterparts, improve the approximation accuracy for important problems.
  arXiv  Detail & Related papers  (2021-02-24T14:50:59Z)
• Learning the Positions in CountSketch [51.15935547615698]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work we propose the first learning algorithm that also optimize the locations of the non-zero entries. We show this algorithm gives better accuracy for low rank approximation than previous work, and apply it to other problems such as $k$-means clustering for the first time.
  arXiv  Detail & Related papers  (2020-07-20T05:06:29Z)
• Error Estimation for Sketched SVD via the Bootstrap [60.67199274260768]
  This paper develops a fully data-driven bootstrap method that numerically estimates the actual error of sketched singular vectors/values. The method is computationally inexpensive, because it operates only on sketched objects, and it requires no passes over the full matrix being factored.
  arXiv  Detail & Related papers  (2020-03-10T19:14:08Z)

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.