The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation

• URL: http://arxiv.org/abs/2507.16345v1
• Date: Tue, 22 Jul 2025 08:25:05 GMT
• Title: The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
• Abstract summary: 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
• Score: 27.82218389495089
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Dimensionality reduction via linear sketching is a powerful and widely used technique, but it is known to be vulnerable to adversarial inputs. We study the black-box adversarial setting, where a fixed, hidden sketching matrix A in $R^{k X n}$ maps high-dimensional vectors v $\in R^n$ to lower-dimensional sketches A v in $R^k$, and an adversary can query the system to obtain approximate ell2-norm estimates that are computed from the sketch. We present a universal, nonadaptive attack that, using tilde(O)($k^2$) queries, either causes a failure in norm estimation or constructs an adversarial input on which the optimal estimator for the query distribution (used by the attack) fails. The attack is completely agnostic to the sketching matrix and to the estimator: It applies to any linear sketch and any query responder, including those that are randomized, adaptive, or tailored to the query distribution. Our lower bound construction tightly matches the known upper bounds of tilde(Omega)($k^2$), achieved by specialized estimators for Johnson Lindenstrauss transforms and AMS sketches. Beyond sketching, our results uncover structural parallels to adversarial attacks in image classification, highlighting fundamental vulnerabilities of compressed representations.

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)
• Refined Risk Bounds for Unbounded Losses via Transductive Priors [58.967816314671296]
  We revisit the sequential variants of linear regression with the squared loss, classification problems with hinge loss, and logistic regression.<n>Our key tools are based on the exponential weights algorithm with carefully chosen transductive priors.
  arXiv  Detail & Related papers  (2024-10-29T00:01:04Z)
• Sparse Linear Bandits with Blocking Constraints [22.01704171400845]
  We investigate the high-dimensional sparse linear bandits problem in a data-poor regime.<n>We show novel offline statistical guarantees of the lasso estimator for the linear model.<n>We propose a meta-algorithm based on corralling that does not need knowledge of optimal sparsity parameter $k$ at minimal cost to regret.
  arXiv  Detail & Related papers  (2024-10-26T01:42:03Z)
• 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)
• $σ$-zero: Gradient-based Optimization of $\ell_0$-norm Adversarial Examples [14.17412770504598]
  We show that $ell_infty$-norm constraints can be used to craft input perturbations.<n>We propose a novel $ell_infty$-norm attack called $sigma$NISTtt-.
  arXiv  Detail & Related papers  (2024-02-02T20:08:11Z)
• Compressive Recovery of Sparse Precision Matrices [5.557600489035657]
  We consider the problem of learning a graph modeling the statistical relations of the $d$ variables from a dataset with $n$ samples $X in mathbbRn times d$. We show that it is possible to estimate it from a sketch of size $m=Omegaleft((d+2k)log(d)right)$ where $k$ is the maximal number of edges of the underlying graph. We investigate the possibility of achieving practical recovery with an iterative algorithm based on the graphical lasso, viewed as a specific denoiser.
  arXiv  Detail & Related papers  (2023-11-08T13:29:08Z)
• Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuning [5.293069542318491]
  We employ random matrix theory to establish consistency of generalized cross validation (GCV) for estimating prediction risks of sketched ridge regression ensembles. For squared prediction risk, we provide a decomposition into an unsketched equivalent implicit ridge bias and a sketching-based variance, and prove that the risk can be globally tuning by only sketch size in infinite ensembles. We also propose an "ensemble trick" whereby the risk for unsketched ridge regression can be efficiently estimated via GCV using small sketched ridge ensembles.
  arXiv  Detail & Related papers  (2023-10-06T16:27:43Z)
• Iterative Sketching for Secure Coded Regression [66.53950020718021]
  We propose methods for speeding up distributed linear regression. Specifically, we randomly rotate the basis of the system of equations and then subsample blocks, to simultaneously secure the information and reduce the dimension of the regression problem.
  arXiv  Detail & Related papers  (2023-08-08T11:10:42Z)
• 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)
• 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)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• 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)
• Mean Nystr\"om Embeddings for Adaptive Compressive Learning [25.89586989444021]
  We study the idea of performing sketching based on data-dependent Nystr"om approximation. We show for k-means clustering and Gaussian modeling that for a fixed sketch size, Nystr"om sketches indeed outperform those built with random features.
  arXiv  Detail & Related papers  (2021-10-21T09:05:58Z)
• Transferable Sparse Adversarial Attack [62.134905824604104]
  We introduce a generator architecture to alleviate the overfitting issue and thus efficiently craft transferable sparse adversarial examples. Our method achieves superior inference speed, 700$times$ faster than other optimization-based methods.
  arXiv  Detail & Related papers  (2021-05-31T06:44:58Z)
• 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)
• 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)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  We consider the contextual bandit problem under the high dimensional linear model. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. We propose doubly growing epochs and estimating the parameter using the best subset selection method.
  arXiv  Detail & Related papers  (2020-09-04T04:10:39Z)
• Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization [101.5159744660701]
  In distributed second order optimization, a standard strategy is to average many local estimates, each of which is based on a small sketch or batch of the data. Here, we introduce a new technique for debiasing the local estimates, which leads to both theoretical and empirical improvements in the convergence rate of distributed second order methods.
  arXiv  Detail & Related papers  (2020-07-02T18:08:14Z)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  We provide the first result of the optimal minimax guarantees for the excess risk for adversarially robust classification. Results are stated in terms of the Adversarial Signal-to-Noise Ratio (AdvSNR), which generalizes a similar notion for standard linear classification to the adversarial setting.
  arXiv  Detail & Related papers  (2020-06-29T21:06:52Z)
• 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.