betaFeedback

WorksComputer Science

No Escape from the Quadratic Barrier: Adaptive Attacks on Linear ℓ2\ell_2 Sketches

Abstract

Linear sketches estimate properties of high-dimensional inputs from a fixed low-dimensional projection. At constant accuracy, randomized Euclidean-norm sketches, notably the Johnson-Lindenstrauss transform, support exponentially many nonadaptive queries in sketch dimension kk. For adaptive black-box queries, known privacy-based defenses guarantee Ω~(k2)\widetildeΩ(k^2) and it remained open whether stronger guarantees were possible. Prior attacks used more queries, restricted the responder, or provided weaker failure guarantees. We show that the quadratic guarantee is optimal up to logarithmic factors, even with a computationally unbounded responder that knows the matrix, attack algorithm, history, and query distributions and may change its randomized rule after every query. For every fixed hidden A∈Rk×nA\in\mathbb{R}^{k\times n} with n>40kn>40k and target accuracy α∈(0,1]α\in (0,1], our black-box attack uses O(k+α2k2log⁡(2+α2k))O(k+α^2k^2\log(2+α^2k)) queries in O~(1+α2k)\widetilde{O}(1+α^2k) adaptive rounds to force, with constant probability, a round in which a constant fraction of answers have Ω(α)Ω(α) relative error. This fraction can be taken arbitrarily close to one half. Our results clarify the limits of defending a fixed compressive linear representation by adapting the prediction rule.

Introduction

A system that is reliable on independently chosen inputs may fail under adaptive interaction, where new queries are formed after observing answers that may reveal internal parameters. In machine learning, a model can have small error on its test distribution while searches guided by its outputs find failures [44, 56]. Defenses against language-model attacks can be bypassed through adaptive interaction [54]. The robustness of a system is studied by quantifying how many interactions are needed to find a failure, and by how much a responder can delay this process by controlling what its answers reveal.

We study this question for the fundamental task of estimating the Euclidean norm of a vector from a linear sketch. A fixed matrix A∈Rk×nA \in\mathbb{R}^{k \times n} compresses each input v∈Rnv \in\mathbb{R}^{n} to kk linear measurements AvAv. A responder uses this sketch to estimate ∥v∥2\lVert v\rVert_2. The black-box attacker chooses inputs and sees the returned estimates, but never sees AA or the sketches. Note that when k<nk<n, inputs with different norms can have the same sketch, so errors exist. The aim of the attacker is to force failures efficiently.

The quadratic benchmark. At constant relative accuracy, classical randomized constructions, including the Johnson–Lindenstrauss transform and the AMS sketch [4, 47], support exponentially many nonadaptive queries in the sketch dimension kk. Under adaptivity, the immediate guarantee is Ω~(k)\widetilde{\Omega}(k), by using a fresh sketch for each query. Defenses based on differential privacy or subsampling support Ω~(k2)\widetilde{\Omega}(k^2) queries [14, 41], by using a randomized estimator with JL or AMS sketches. These defenses draw on adaptive data analysis: limiting what each answer reveals allows repeated use of the same randomness [9, 27]. The quadratic guarantee is attainable but its optimality remained open:

Question. Can a different choice of a linear sketch and responder support substantially more adaptive queries at the same sketch dimension?

Prior attacks either required polynomially more queries, targeted particular sketching matrices or estimators, restricted the responder, or established weaker failure guarantees [2, 12, 20, 40].

Our results: attacks

We show that the quadratic guarantee is also a limit. We design an attack algorithm that applies to any matrix with n>40kn > 40k and forces errors even from powerful unrestricted responders.

Informed responder model. The responder has unbounded computation, memory, and private randomness. It knows AA, the attack algorithm, and the attacker’s complete execution history and current state. Before each query, it knows the input distribution. It may change its randomized rule adaptively after every query. Its only information restriction is that it observes each fresh input through the sketch. After it returns a response, the input itself and the rest of that query’s execution are revealed. Note that a stronger responder model only strengthens the attack guarantee. Definition 2.1 formalizes this model.

Norm gap task. Our attacks work even when the responder only has to distinguish ∥v∥2≤L\lVert v\rVert_2 \le L from ∥v∥2≥U\lVert v\rVert_2 \ge U, for fixed public thresholds with U/L=1+Θ(α)U/L = 1 + \Theta(\alpha); either binary answer is permitted between the thresholds. This task, also considered by [2, 40], is easier than norm estimation with relative error Ω(α)\Omega(\alpha): thresholding a sufficiently accurate norm estimate gives a correct gap answer. Thus errors on the norm-gap task transfer to errors in norm estimation.

Theorem 1.1 (A universal attack). For every constant 0<cfrac<1/20 < c_{\mathrm{frac}} < 1/2 there is an attack algorithm such that, for every A∈Rk×nA \in\mathbb{R}^{k \times n} with n>40kn > 40k, every α∈(0,1]\alpha\in(0,1], and every informed responder, the attack uses

O(k+α2k2log⁡(2+α2k))O\left(k+\alpha^2 k^2\log\left(2+\alpha^2 k\right)\right)

queries and returns, with probability at least 0.9, a round JJ of Θ(k)\Theta(k) consecutive queries generated independently from one announced distribution. For binary norm gap with U/L=1+Θ(α)U/L = 1 + \Theta(\alpha), at least cfrac∣J∣c_{\mathrm{frac}}|J| answers are incorrect; for norm estimation, at least cfrac∣J∣c_{\mathrm{frac}}|J| estimates have relative error Ω(α)\Omega(\alpha). The constants in the bounds depend only on cfracc_{\mathrm{frac}}.

All queries are supported on a common set of 40k+140k+1 coordinates, which may be prescribed arbitrarily before the interaction. The attack uses O(1+α2klog⁡(2+α2k))O(1+\alpha^2 k\log(2+\alpha^2 k)) adaptive rounds; working memory is O(k+α2k2)O(k+\alpha^2 k^2) words and arithmetic cost is O~(k2+α4k4)\widetilde{O}(k^2+\alpha^4 k^4).

The error fraction is optimal for binary answers. A responder that answers each norm-gap query with an independent fair coin errs with probability at most 1/21/2 on every query, conditionally on the past. By the Azuma–Hoeffding inequality, with high probability no round of Θ(k)\Theta(k) queries among polynomially many rounds has an error fraction exceeding 1/2+o(1)1/2 + o(1).

The linear support size is optimal up to a constant factor: if AA is such that every kk columns are linearly independent, every input supported on a known set of at most kk coordinates can be recovered exactly from its sketch, allowing exact norm answers that do not reveal anything about $A.

Accuracy vs. robustness The attack is more effective when higher accuracy is required. At constant accuracy, our bounds match known defenses of Ω~(k2)\widetilde{\Omega}(k^2) up to logarithmic factors. At high accuracy α=Θ(k−1/2)\alpha=\Theta(k^{-1/2}), the attack uses O(k)O(k) queries in O(1)O(1) rounds. At very high accuracy (α<Ck−1/2\alpha< Ck^{-1/2}), the initial distribution already forces the same error fraction.

Attack structure. Each query combines a scalar signal with Gaussian noise. The signal distribution remains fixed, while the attacker changes the noise covariance between rounds. The attack keeps the noise norm concentrated, so accurate norm answers distinguish low from high signal values. Our analysis proceeds through this auxiliary signal-gap task.

The noise covariance determines how accurately the signal can be estimated from the sketch. Higher signal-estimation variance makes the two signal regimes harder to distinguish, even while the input noise norm remains concentrated. Starting from isotropic covariance, the attack seeks a universally hard query distribution1 by changing the noise covariance (see Figure 1).

Figure 1. The covariance attack in sketch space for queries with signal w=1w=1 (blue) and w=1+αw=1+\alpha (orange). Sketches are projected on the signal column AhA_h and an orthogonal direction. Illustration shows 2σ2\sigma ellipses of the sketch noise. The dashed line is the threshold 1+α/21+\alpha/2. At the start the input noise is isotropic, and the sketch noise may separate the two signals (if there is overlap we are done). At the end, if the responder does not err earlier on an easy distribution, the sketch noise is stretched along AhA_h and the two signals overlap.

Each round also checks accuracy. If its empirical signal-gap loss exceeds the validation threshold, the attack returns the round and its query distribution. Otherwise, correlations between the answers and the sampled noise guide a covariance update. The analysis bounds the number of rounds that can pass validation, forcing an observed round with many errors. The returned distribution need not be universally hard, since the responder can err on an easier distribution. But if the responder maintains sufficiently small error whenever a smaller constant error is achievable, the returned distribution is universally hard.

Sufficient-statistic responders. For each fixed distribution, a scalar sufficient statistic contains all the information about the signal available in the sketch. A sufficient-statistic responder is restricted so that, conditional on the disclosed history, its mean binary answer depends on the current sketch only through this statistic (formalized in § 5). The class includes the Bayes-optimal signal-gap predictor, as well as predictors computed from the statistic followed by output noise, rounding, or clipping. It provides an idealized model of repeatedly fitting a predictor to the current query distribution while keeping the compressive map fixed. In this interpretation, accurate predictions supply feedback that guides the attacker’s search for a hard noise distribution, even as the predictor is adapted to each new distribution. Section A.2 develops the learning interpretation and its implications for output defenses. We obtain a more efficient attack for informed responders with this additional restriction.

Theorem 1.2 (Attack on sufficient-statistic responders; informal). For every constant 0<cfrac<1/20 < c_{\mathrm{frac}} < 1/2 there is an attack algorithm such that, for every A∈Rk×nA \in\mathbb{R}^{k \times n} with n>40kn > 40k, every α∈(0,1]\alpha\in(0,1], and every sufficient-statistic norm responder, with probability at least 0.90.9 the attack returns a round of Ω(k)\Omega(k) consecutive queries, generated independently from one distribution, for which at least a cfracc_{\mathrm{frac}} fraction of norm estimates have relative error Ω(α)\Omega(\alpha). The constants in the bounds below depend only on cfracc_{\mathrm{frac}}. The attack uses O~(k+α2k2)\widetilde{O}(k+\alpha^{2}k^{2}) queries, O(log⁡(2+α2k))O(\log(2+\alpha^{2}k)) adaptive rounds, O(klog⁡(2+α2k))O(k\log(2+\alpha^{2}k)) words of working memory, and O~(k2+α2k3)\widetilde{O}(k^{2}+\alpha^{2}k^{3}) arithmetic operations. All queries use any prescribed set of 40k+140k+1 coordinates. On the same success event, if the threshold is reached before a round is rejected, the final query distribution is universally hard for norm tasks.

Analyzing attack progress. We establish the existence of a comparator covariance whose signal-estimation variance makes the query distribution universally hard. The key property exploited by both attacks is that accurate answers force a component of the mean signed noise—the expected product of the generated noise vector and the binary answer—along the hidden signal-estimation direction; we extend the correlation bound of Ahmadian et al. [2] to general covariances. The signal values are drawn from a density with exponential ramps on both sides of the gap. This makes the correlation bound hold for every error rate below a level that approaches one half. For sufficient-statistic responders, the mean signed noise is aligned with the hidden direction, allowing direct multiplicative growth of the signal-estimation variance. For general responders, the challenge is that other components of the mean signed noise can obscure the useful direction. We extract measurements that separate the current covariance from the hard comparator and use them in matrix multiplicative-weights updates, with progress measured by a relative-entropy potential.

Tightness of the accuracy dependence

Our attacks use O~(k+α2k2)\widetilde{O}(k+\alpha^{2}k^{2}) queries but known defenses [14, 41]2 guarantee only Ω~(α4k2)\widetilde{\Omega}(\alpha^{4}k^{2}) adaptive queries, leaving a gap for higher accuracy. We show that the dependence α2k2\alpha^{2}k^{2} is the right one in two settings.

Informed stateless responders. For a broad family of signal–noise query distributions, a Gaussian JL sketch can withstand Ω(α2k2)\Omega(\alpha^{2}k^{2}) adaptive queries when paired with a responder that is provided with the noise mean and covariance.

Theorem 1.3 (Matching lower bound; informal). *Fix a target error fraction δ∈(0,1)\delta\in(0,1). For a sufficiently large constant CC and C/k≤α≤1C/\sqrt{k} \leq\alpha\leq1, consider attacks using the signal–noise query

family specified in Section D, with sufficiently concentrated noise energy. For either norm task, any such attack that forces, with probability at least 0.90.9, a δ\delta fraction of errors in an observed interval of Ω(k)\Omega(k) consecutive queries against every sketching matrix and every informed responder requires Ω(α2k2)\Omega(\alpha^2 k^2) queries. The constants may depend on δ\delta.

Subject to the family’s moment and concentration conditions, the noise law is arbitrary and may depend on the signal; the distribution may change after every answer. The lower bound is witnessed by a Gaussian JL matrix sampled once and kept fixed, together with a responder that beyond the matrix, current sketch, and task parameters, uses only the signal direction and noise mean and covariance.

Taking δ\delta to be the constant error fraction guaranteed by our attacks, this establishes optimal query complexity for the sufficient-statistic attack within this family and accuracy regime. The general attack is optimal up to its logarithmic factor.

The responder adds noise to a distribution-informed linear estimator. For the analysis, we use KL divergence to bound what its answers reveal about the hidden Gaussian matrix, showing that finding a query law with large signal-estimation variance requires Ω(α2k2)\Omega(\alpha^2 k^2) queries. Section D gives the precise statement and proof.

Uninformed stateful responders. The factor α4\alpha^4 in the known defenses matches the sample complexity O~(Q/ε2)\widetilde{O}(\sqrt{Q}/\varepsilon^2) of answering QQ adaptive statistical queries with accuracy ε\varepsilon through the transfer theorem of adaptive data analysis [9, 27]. Robust estimation from a sketch with independent rows can be cast as an adaptive data analysis problem over the rows [21]. Combining this with the recent population-accurate ADA mechanism of Lyu [51], which needs only O~(Q/ε+ε−4)\widetilde{O}(\sqrt{Q}/\varepsilon+\varepsilon^{-4}) samples, we obtain a Gaussian JL sketch with a stateful responder that withstands Ω~(α2k2)\widetilde{\Omega}(\alpha^2 k^2) arbitrary adaptive queries once k=Ω~(α−4)k=\widetilde{\Omega}(\alpha^{-4}).3 The precise statement is given in Section E.

The guarantee of the stateful responder holds when a single instance of the underlying mechanism answers all QQ queries sequentially. In contrast, stateless responders including the known ones mentioned and our informed responder of Section D, keep their guarantees for the total number of queries even when independent copies answer queries in parallel.

Comparison with prior work

Table 1 summarizes a comparison of our results with directly related prior work. A broader related work discussion is included in Section A.

The problem was first formalized by Hardt and Woodruff [40]. They gave polynomial-query attacks for arbitrary sketching matrices AA, using O~(k)\widetilde{O}(k) adaptive rounds and common query support of size O(k)O(k) at constant relative accuracy. Their responder uses a randomized estimator that may change between rounds, but remains fixed throughout each round. Their attack returns a distribution on which that estimator has a constant error rate. Our attack forces errors from a much stronger informed responder that additionally knows each query distribution and may change its rule after every query.

Ahmadian, Cohen, and Stemmer [2] (ACS) obtained a O~(k2)\widetilde{O}(k^2)-query attack against arbitrary AA (with n=Ω~(k2)n = \widetilde{\Omega}(k^2)) and informed responders. It samples all queries i.i.d. from one distribution in a single nonadaptive round. The attack guarantees that either the responder makes errors on a constant fraction of queries, or the attack constructs an input on which the estimator optimal for the query distribution fails (but the latter need not be an error by the actual responder). They left open the existence of a quadratic-query attack with a constant error rate and with support reduced from O~(k2)\widetilde{O}(k^2) to O~(k)\widetilde{O}(k) coordinates. As observed by [2], at constant accuracy, Ω~(k)\widetilde{\Omega}(k) adaptive rounds are necessary to force errors against arbitrary sketches and responders using polynomially many queries.4

Organization. § 2 defines the interaction model and attack objective. § 3 presents the general attack. § 4 previews the analysis. § 5 gives the more efficient attack for sufficient-statistic responders. § 6 concludes. Section A places our work in a broader context of related works. The full analyses appear in Sections B and C; the lower bounds in Section D and Section E; subsequent appendices give supporting proofs and details.

Interaction model and attack objectives

Fix a matrix A∈Rk×nA \in\mathbb{R}^{k \times n} and a publicly specified task with response space Y\mathcal{Y}. The task determines which answers are correct for each input.

The interaction is between an attacker and a responder. In query ii, the attacker chooses an input vi∈Rnv_i \in\mathbb{R}^n, the responder receives the sketch AviAv_i and returns an answer ai∈Ya_i \in\mathcal{Y} that the attacker observes.

The attacker never observes AA or the sketches; it observes only its own execution and the returned answers from the responder. Its objective is to cause the responder to return incorrect answers.

The informed responder model

Our attacks are analyzed against an informed responder, which has unbounded computation, memory, and randomness. It knows AA and the attacker’s algorithm and its parameters, and the complete execution history. The only information temporarily withheld from the responder at the beginning of query ii is the fresh randomness that the attacker uses to sample its current input viv_i. This information is shared with the responder, but only after the answer aia_i is determined.

Let Tri\mathrm{Tr}_i denote the complete execution of both parties through the completion of query ii, including their random choices, inputs, and responses. This transcript is available to the responder. Our attack queries follow a particular structure:

Definition 2.1 (Adaptive interaction query). Query ii proceeds as follows.

(i) The attacker announces a Borel distribution Di\mathcal{D}_i on Rn\mathbb{R}^n, chosen measurably from its own execution transcript so far and fresh randomness. It discloses Di\mathcal{D}_i and the execution history of this query.

(ii) Using AA, Tri−1\mathrm{Tr}_{i-1}, and the newly disclosed information, the responder privately selects a measurable map ψi:Rk→Y\psi_i:\mathbb{R}^k \to\mathcal{Y}, possibly at random.

(iii) The attacker draws vi∼Div_i \sim\mathcal{D}_i using fresh randomness. The responder receives the sketch yi=Aviy_i = Av_i and returns an answer ai=ψi(yi)a_i = \psi_i(y_i), which the attacker observes. After the answer, the attacker discloses the remainder of its execution for this query.

The attacker may stop and return an output based on its information and fresh randomness.

Attack structure and objective

Our attacks proceed in rounds, each containing Ω(k)\Omega(k) queries. At the start of each round, the attacker fixes a query distribution and the number of queries, then draws the queries independently from that distribution. Thus, conditional on these choices and the preceding history, the queries in a round are i.i.d. The responder may still change its rule after every query. We use ii for the global query index, tt for the round index, and jj for the query index within a round.

The attack’s goal is to return a round, together with its query distribution, in which a constant fraction of the answers were incorrect for the task. We seek this guarantee with constant probability using few queries and rounds.

Norm tasks

References

  1. [1]Sara Ahmadian and Edith Cohen. Unmasking vulnerabilities: Cardinality sketches under adaptive inputs. In Proceedings of the 41st International Conference on Machine Learning (ICML), volume 235 of PMLR, pages 550–576, 2024. URL https://proceedings.mlr.press/v235/ahmadian24a.html.arxiv.org/abs/2405.17780
  2. [2]Sara Ahmadian, Edith Cohen, and Uri Stemmer. The cost of compression: Tight quadratic black-box attacks on sketches for ℓ₂ norm estimation. In Advances in Neural Information Processing Systems 38 (NeurIPS), pages 25633–25659, 2025. URL https://proceedings.neurips.cc/paper_files/paper/2025/hash/249f73e01f0a2bb6c8d971b565f159a7-Abstract-Conference.html. arXiv:2507.16345.arxiv.org/abs/2507.16345
  3. [3]Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 459–467, 2012. doi: 10.1137/1.9781611973099.40. URL https://doi.org/10.1137/1.9781611973099.40.
  4. [4]Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58(1):137–147, 1999. URL https://doi.org/10.1006/jcss.1997.1545.
  5. [5]Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. Journal of the ACM, 63(2):12:1–12:35, 2016. doi: 10.1145/2837020. URL https://doi.org/10.1145/2837020. Preliminary version in STOC 2007, pages 227–236.
  6. [6]Anish Athalye, Logan Engstrom, Andrew Ilyas, and Kevin Kwok. Synthesizing robust adversarial examples. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages 284–293, 2018. URL https://proceedings.mlr.press/v80/athalye18b.html.
  7. [7]Idan Attias, Edith Cohen, Moshe Schuchner, and Uri Stemmer. A framework for adversarial streaming via differential privacy and difference estimators. In 14th Innovations in Theoretical Computer Science Conference (ITCS), volume 251 of LIPIcs, pages 8:1–8:19, 2023. URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.8.arxiv.org/abs/2107.14527
  8. [8]Peter L. Bartlett, Sébastien Bubeck, and Yeshwanth Cherapanamjeri. Adversarial examples in multi-layer random ReLU networks. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 9241–9252, 2021. URL https://arxiv.org/abs/2106.12611.
  9. [9]Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the 48th ACM Symposium on Theory of Computing (STOC), pages 1046–1059, 2016. URL https://doi.org/10.1145/2897518.2897566. Full version in SIAM Journal on Computing, 50(3), 2021.
  10. [10]Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: Generic constructions and lower bounds. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), pages 1671–1684, 2022. doi: 10.1145/3519935.3520064. URL https://doi.org/10.1145/3519935.3520064.
  11. [11]Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, and Avi Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11(1):2–14, 1994. doi: 10.1007/BF01294260. URL https://doi.org/10.1007/BF01294260.
  12. [12]Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. In Proceedings of the 39th ACM Symposium on Principles of Database Systems (PODS), pages 63–80, 2020. URL https://arxiv.org/abs/2003.14265. Full version in Journal of the ACM, 69(2):17:1–17:33, 2022.
  13. [13]Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak. Adversarially robust streaming via dense-sparse trade-offs. In Symposium on Simplicity in Algorithms (SOSA), pages 214–227, 2022. URL https://doi.org/10.1137/1.9781611977066.15.
  14. [14]Guy Blanc. Subsampling suffices for adaptive data analysis. In Proceedings of the 55th ACM Symposium on Theory of Computing (STOC), pages 999–1012, 2023. URL https://doi.org/10.1145/3564246.3585226.
  15. [15]Sébastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 28811–28822, 2021. URL https://arxiv.org/abs/2105.12806.
  16. [16]Sébastien Bubeck, Yeshwanth Cherapanamjeri, Gauthier Gidel, and Rémi Tachet des Combes. A single gradient step finds adversarial examples on random two-layers neural networks. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 10081–10091, 2021. URL https://arxiv.org/abs/2104.03863.
  17. [17]Jianbo Chen, Michael I. Jordan, and Martin J. Wainwright. HopSkipJumpAttack: A query-efficient decision-based attack. In IEEE Symposium on Security and Privacy (SP), pages 1277–1294, 2020. URL https://arxiv.org/abs/1904.02144.
  18. [18]Yeshwanth Cherapanamjeri and Jelani Nelson. On adaptive distance estimation. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 11178–11190, 2020. URL https://arxiv.org/abs/2010.11252.
  19. [19]Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Schechner, and Uri Stemmer. On the robustness of CountSketch to adaptive inputs. In Proceedings of the 39th International Conference on Machine Learning (ICML), volume 162 of PMLR, pages 4112–4140, 2022. URL https://proceedings.mlr.press/v162/cohen22a.html.arxiv.org/abs/2202.13736
  20. [20]Edith Cohen, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Tricking the hashing trick: A tight lower bound on the robustness of CountSketch to adaptive inputs. Proceedings of the AAAI Conference on Artificial Intelligence, 37(6):7235–7243, 2023. URL https://doi.org/10.1609/aaai.v37i6.25882.
  21. [21]Edith Cohen, Mihir Singhal, and Uri Stemmer. Breaking the quadratic barrier: Robust cardinality sketches for adaptive queries. In Proceedings of the 42nd International Conference on Machine Learning (ICML), volume 267 of PMLR, pages 11185–11199, 2025. URL https://proceedings.mlr.press/v267/cohen25c.html.arxiv.org/abs/2502.05723
  22. [22]Edith Cohen, Elena Gribelyuk, Pasin Manurangsi, and Uri Stemmer. Tight bounds on the cost of adaptivity for the Meyerson sketch. arXiv:2609.06669, 2026. URL https://arxiv.org/abs/2609.06669.
  23. [23]Edith Cohen, Elena Gribelyuk, Jelani Nelson, and Uri Stemmer. Adaptively robust resettable streaming. In Proceedings of the 43rd International Conference on Machine Learning (ICML), volume 306 of Proceedings of Machine Learning Research, pages 21046–21087. PMLR, 2026. URL https://proceedings.mlr.press/v306/cohen26a.html.arxiv.org/abs/2601.21989
  24. [24]Edith Cohen, Jelani Nelson, Tamás Sarlós, Mihir Singhal, and Uri Stemmer. One attack to rule them all: Tight quadratic bounds for adaptive queries on cardinality sketches. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3162–3200, 2026. URL https://arxiv.org/abs/2411.06370.
  25. [25]Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via randomized smoothing. In Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97 of PMLR, pages 1310–1320, 2019. URL https://proceedings.mlr.press/v97/cohen19c.html.arxiv.org/abs/1902.02918
  26. [26]Amit Daniely and Hadas Shacham. Most ReLU networks suffer from ℓ² adversarial perturbations. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 6629–6636, 2020. URL https://papers.nips.cc/paper/2020/hash/497476fe61816251905e8baafdf54c23-Abstract.html.arxiv.org/abs/2010.14927
  27. [27]Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the 47th ACM Symposium on Theory of Computing (STOC), pages 117–126, 2015. URL https://doi.org/10.1145/2746539.2746580.
  28. [28]Shimon Even and Yossi Shiloach. An on-line edge-deletion problem. Journal of the ACM, 28(1):1–4, 1981. doi: 10.1145/322234.322235. URL https://doi.org/10.1145/322234.322235.
  29. [29]Alhussein Fawzi, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. Robustness of classifiers: from adversarial to random noise. In Advances in Neural Information Processing Systems 29 (NIPS), pages 1632–1640, 2016. URL https://arxiv.org/abs/1608.08967.
  30. [30]David A. Freedman. A note on screening regression equations. The American Statistician, 37(2):152–155, 1983. doi: 10.1080/00031305.1983.10482729. URL https://doi.org/10.1080/00031305.1983.10482729.
  31. [31]Paweł Gawrychowski, Shay Mozes, and Oren Weimann. Minimum cut in O(m log² n) time. In 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168 of LIPIcs, pages 57:1–57:15, 2020. URL https://doi.org/10.4230/LIPIcs.ICALP.2020.57.
  32. [32]Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations (ICLR), 2015. URL https://arxiv.org/abs/1412.6572.
  33. [33]Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou. A strong separation for adversarially robust ℓ₀ estimation for linear sketches. In Proceedings of the 65th IEEE Symposium on Foundations of Computer Science (FOCS), pages 2318–2343, 2024. URL https://arxiv.org/abs/2409.16153.
  34. [34]Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou. Lifting linear sketches: Optimal bounds and adversarial robustness. In Proceedings of the 57th ACM Symposium on Theory of Computing (STOC), pages 395–406, 2025. URL https://doi.org/10.1145/3717823.3718227.
  35. [35]Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou. Adversarial robustness on insertion-deletion streams. In Proceedings of the 58th ACM Symposium on Theory of Computing (STOC), pages 2278–2289. ACM, 2026. URL https://arxiv.org/abs/2602.20854.
  36. [36]Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou. Adversarial robustness for small frequency moments and a weak equivalence theorem for turnstile streams. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), 2026. URL https://arxiv.org/abs/2607.06312.
  37. [37]Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Decremental SSSP in weighted digraphs: Faster and against an adaptive adversary. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2542–2561, 2020. URL https://arxiv.org/abs/2001.10821.
  38. [38]William W. Hager. Updating the inverse of a matrix. SIAM Review, 31(2):221–239, 1989. doi: 10.1137/1031049. URL https://doi.org/10.1137/1031049.
  39. [39]Moritz Hardt and Jonathan Ullman. Preventing false discovery in interactive data analysis is hard. In Proceedings of the 55th IEEE Symposium on Foundations of Computer Science (FOCS), pages 454–463, 2014. URL https://doi.org/10.1109/FOCS.2014.55.
  40. [40]Moritz Hardt and David P. Woodruff. How robust are linear sketches to adaptive inputs? In Proceedings of the 45th ACM Symposium on Theory of Computing (STOC), pages 121–130, 2013. URL https://doi.org/10.1145/2488608.2488624.
  41. [41]Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 147–158, 2020. URL https://arxiv.org/abs/2004.05975. Full version in Journal of the ACM, 69(6):42:1–42:14, 2022.
  42. [42]Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778, 2016. URL https://openaccess.thecvf.com/content_cvpr_2016/html/He_Deep_Residual_Learning_CVPR_2016_paper.html.arxiv.org/abs/1512.03385
  43. [43]Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations (ICLR), 2022. URL https://openreview.net/forum?id=nZeVKeeFY19.
  44. [44]Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of PMLR, pages 2137–2146, 2018. URL https://proceedings.mlr.press/v80/ilyas18a.html.arxiv.org/abs/1804.08598
  45. [45]Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019. URL https://arxiv.org/abs/1905.02175.
  46. [46]John P. A. Ioannidis. Why most published research findings are false. PLoS Medicine, 2(8): e124, 2005. doi: 10.1371/journal.pmed.0020124. URL https://doi.org/10.1371/journal.pmed.0020124.
  47. [47]William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in Modern Analysis and Probability, volume 26 of Contemporary Mathematics, pages 189–206. American Mathematical Society, 1984. URL https://doi.org/10.1090/conm/026/737400.
  48. [48]Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In IEEE Symposium on Security and Privacy (SP), pages 656–672, 2019. URL https://arxiv.org/abs/1802.03471.
  49. [49]Erich L. Lehmann and George Casella. Theory of Point Estimation. Springer, 2nd edition, 1998. ISBN 978-0-387-98502-2.
  50. [50]Paul M. Lukacs, Kenneth P. Burnham, and David R. Anderson. Model selection bias and Freedman’s paradox. Annals of the Institute of Statistical Mathematics, 62(1):117–125, 2010. doi: 10.1007/s10463-009-0234-4. URL https://doi.org/10.1007/s10463-009-0234-4.
  51. [51]Xin Lyu. Sample-efficient adaptive data analysis. Manuscript, 2026. Shared September 2026.
  52. [52]Ilya Mironov, Moni Naor, and Gil Segev. Sketching in adversarial environments. In Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), pages 651–660, 2008. URL https://doi.org/10.1145/1374376.1374471.
  53. [53]Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 86–94, 2017. URL https://arxiv.org/abs/1610.08401.
  54. [54]Milad Nasr, Nicholas Carlini, Chawin Sitawarin, Sander V. Schulhoff, Jamie Hayes, Michael Ilie, Juliette Pluto, Shuang Song, Harsh Chaudhuri, Ilia Shumailov, Abhradeep Thakurta, Kai Yuanqing Xiao, Andreas Terzis, and Florian Tramèr. The attacker moves second: Stronger adaptive attacks bypass defenses against LLM jailbreaks and prompt injections. arXiv:2510.09023, 2025. URL https://arxiv.org/abs/2510.09023.
  55. [55]Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. The limits of post-selection generalization. In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 6402–6411, 2018.arxiv.org/abs/1806.06100
  56. [56]Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM Asia Conference on Computer and Communications Security (ASIA CCS), pages 506–519, 2017. URL https://arxiv.org/abs/1602.02697.
  57. [57]Thomas Steinke and Jonathan Ullman. Interactive fingerprinting codes and the hardness of preventing false discovery. In Proceedings of the 28th Conference on Learning Theory (COLT), volume 40 of PMLR, pages 1588–1628, 2015. URL https://proceedings.mlr.press/v40/Steinke15.html.arxiv.org/abs/1410.1228
  58. [58]Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations (ICLR), 2014. URL https://arxiv.org/abs/1312.6199.
  59. [59]Florian Tramèr, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick McDaniel. The space of transferable adversarial examples. arXiv:1704.03453, 2017. URL https://arxiv.org/abs/1704.03453.
  60. [60]Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In International Conference on Learning Representations (ICLR), 2019. URL https://arxiv.org/abs/1805.12152.
  61. [61]Koji Tsuda, Gunnar Rätsch, and Manfred K. Warmuth. Matrix exponentiated gradient updates for on-line learning and Bregman projection. Journal of Machine Learning Research, 6:995–1018, 2005. URL https://jmlr.org/papers/v6/tsuda05a.html.DOI
  62. [62]David Wajc. Rounding dynamic matchings against an adaptive adversary. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC), pages 194–207, 2020. doi: 10.1145/3357713.3384258. URL https://doi.org/10.1145/3357713.3384258.
  63. [63]Manfred K. Warmuth and Dima Kuzmin. Randomized online PCA algorithms with regret bounds that are logarithmic in the dimension. Journal of Machine Learning Research, 9:2287–2320, 2008. URL https://jmlr.org/papers/v9/warmuth08a.html.
  64. [64]David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In Proceedings of the 62nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 1183–1196, 2021. URL https://arxiv.org/abs/2011.07471.

Paper details

vlnc:W_rantgpk5
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT, Claude, Gemini (multiple versions)

View statement
Looking for related papers…
Contents