Pith. sign in

REVIEW 4 major objections 5 minor 53 references

Rewriting the Budget: A General Framework for Black-Box Attacks Under Cost Asymmetry

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper argues that black-box attacks should minimize total query cost, not query count, and shows that two modifications—a cost-ratio-aware search and a shifted, reweighted gradient estimator—cut cost by up to 40% and beat stealthy…

desk verdict A solid generalization of decision-based attacks to asymmetric query costs; the AS part is clean and worth adopting, while the 40% AGREST gains rest on an untested local-linearity assumption. read the letter →

arxiv 2506.06933 v1 pith:EAVNVY7F submitted 2025-06-07 cs.LG cs.AIcs.CRcs.CV

Mahdi Salmani , Alireza Abdollahpoorrostam , Seyed-Mohsen Moosavi-Dezfooli This is my paper
classification cs.LGcs.AIcs.CRcs.CV
keywords adversarialexamplesdecision-basedblack-boxattackasymmetricquerycostsefficiencygradientestimationbinarysearchimageclassifiersstealthyattacks
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Decision-based black-box attacks find images that fool a classifier by repeatedly querying it, and most methods count every query as equally expensive. This paper starts from the observation that in deployments such as content moderation a query that gets flagged is far more costly than one that does not, so the right objective is expected total cost rather than total query count. The authors propose two modifications that plug into existing attacks: Asymmetric Search (AS), which splits the search interval in proportion to the cost ratio instead of in half, and Asymmetric Gradient Estimation (AGREST), which samples gradient estimates from a point shifted into the low-cost region and reweights the two query types. They claim that across cost ratios from 2 to effectively infinity these modifications beat both vanilla attacks and earlier stealthy attacks, with up to 40% smaller perturbations at the same total cost, because the framework keeps efficient gradient estimation instead of throwing it away.

What carries the argument

The two load-bearing objects are AS and AGREST. AS is a binary-search variant that splits the current search interval at a point dividing it roughly in the ratio $1:c^\star$, so that the larger, cheaper subinterval is explored first; with $c^\star=1$ it reduces to binary search and with $c^\star=\infty$ it becomes line search. AGREST estimates the gradient at an overshot point $x'_t = x_t + \omega_t (x_t-x^\star)/\|x_t-x^\star\|$ and weights each query by $\widehat\phi_t(x) = (1-\beta_t)\mathbf{1}\{\phi(x)=1\} - \beta_t\mathbf{1}\{\phi(x)=-1\}$, with the optimal weight set to the probability $p_t(\omega_t)$ of a low-cost query and the overshoot maximizing $$\widehat{J}_t(\omega_t) = \frac{\left(1-(\$delta^{{-1}}$\cos\alpha_t\,\omega_t)^2\right)^{d-1}}{p_t(\omega_t)(1-p_t(\omega_t))(c^\star-(c^\star-1)p_t(\omega_t))}.$$ The machinery is completed by a scheduler that estimates the angle $\alpha_t$ between the attack direction and the true gradient, starting from a closed-form initial cosine value and decaying as $1-(1-\cos\alpha_1)t^{-m}$.

What would settle it

Run AS and AGREST against a classifier with a known strongly curved boundary, such as a low-dimensional classifier whose decision boundary is a sphere, then compare the empirical probability of low-cost queries and the final $\ell_2$ distance at fixed total cost with the theoretical $p_t(\omega^\star)$ prediction; if the empirical gradient direction is far from the locally linear estimate, or if the $1:c^\star$ split gives higher expected cost than binary search on some non-uniform boundary distribution, the core claim is contradicted.

Watch

Extended reading notes

Core claim

On its own terms, the paper claims that the total cost of a decision-based black-box attack can be substantially reduced by changing two core routines without altering the attack's structure. AS replaces the symmetric split of binary search with a $1:c^\star$ split, giving a $\Theta(\log(c^\star+1))$ expected-cost improvement over binary search under a uniform-boundary assumption; when $c^\star=1$ it is binary search and when $c^\star\to\infty$ it degenerates to line search. AGREST estimates the gradient at an overshot point $x_t + \omega_t (x_t-x^\star)/\|x_t-x^\star\|$ instead of at the boundary point, and uses importance weights so that the estimator stays aligned with the true gradient while the share of high-cost queries falls; the optimal weight is the probability of a low-cost query and the optimal overshoot maximizes an explicit function built from the hyperspherical-cap probability. The theoretical part establishes these choices under a local-linearity assumption on the decision boundary, and the empirical part shows that the resulting attacks (A-HSJA, A-GeoDA, A-CGBA, A-SurFree) attain the same perturbation size with lower total cost than prior stealthy attacks even when high-cost queries are treated as infinitely expensive.

Load-bearing premise

The derivation of AGREST's optimal overshoot and weighting assumes the decision boundary is locally linear around the current boundary point (Eq. 3); if the boundary is strongly curved, the computed overshoot and weights no longer minimize expected cost and the reported gains can shrink.

Editorial extensions

If this is right

  • When $c^\star$ is large, adding AGREST to a gradient-based attack alone reduces $\ell_2$ distance by roughly 40% at the same total cost, and combining it with AS gives a further reduction.
  • Against Stealthy HSJA on ResNet-50, all four asymmetric attacks achieve lower $\ell_2$ distance at the same total cost for $c^\star = 10^4$, $10^5$, and $\infty$, with the largest margin when cost is measured by the number of high-cost queries.
  • The framework transfers to CLIP in both zero-shot and fine-tuned settings, where after 300 total queries the asymmetric attacks reach 40–60% lower $\ell_2$ distortion than Stealthy HSJA.
  • Because AS and AGREST only replace the search and gradient-estimation modules, they can be applied to SurFree, HSJA, GeoDA, and CGBA with minimal changes, and the same pair of modules should transfer to other decision-based attacks that use binary search and Monte Carlo gradients.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: the same shift-and-reweight recipe is a generic importance-sampling trick for hard-label queries, so it could reduce the number of expensive labels in active learning or model extraction, not just adversarial examples.
  • Editorial extension: the $1:c^\star$ split rule optimizes expected cost only when the boundary position along the path is uniformly distributed; measuring AS's per-iteration cost on real classifiers would show where the $\Theta(\log(c^\star+1))$ gain actually holds.
  • Editorial extension: the paper's $c^\star=\infty$ comparison counts high-cost queries only, which treats low-cost queries as free; a fuller comparison would report a Pareto frontier over both query types, as the paper's own Figure 1 does.
  • Editorial extension: since AGREST explicitly optimizes $\beta_t = p_t(\omega_t)$, the same estimator could be used to predict boundary curvature by comparing the empirical low-cost fraction with the locally linear prediction, yielding a curvature estimate for free.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proposes a general framework for decision-based black-box adversarial attacks under asymmetric query costs. Two modifications to standard attacks are introduced: Asymmetric Search (AS), which replaces binary search with a cost-aware split, and Asymmetric Gradient Estimation (AGREST), which shifts the sampling center and reweights queries to reduce the frequency of high-cost queries. The authors provide theoretical analyses of the expected search cost, the approximation of the cosine similarity, and the optimal AGREST parameters, and they evaluate the framework by modifying HSJA, GeoDA, CGBA, and SurFree on ImageNet classifiers including ResNet, ViT, and CLIP models. The reported results show consistent reductions in total query cost and perturbation size, up to 40% in high-asymmetry regimes, and the code is publicly available.

Significance. If the results hold, this is a meaningful step forward for decision-based attacks in asymmetric-cost scenarios, where prior work (stealthy attacks) minimized flagged queries but largely ignored the cost of non-flagged queries. The paper's idea of adapting both the search and the gradient-estimation components, rather than replacing them, is broadly applicable. Strengths include the systematic ablation separating AS and AGREST, the extension to several attack families and architectures, and the public code release. The theoretical claims are conditional on assumptions (uniform boundary prior, local linearity) that are common in the literature but not fully validated; the reported gains should therefore be treated as promising but not definitive.

major comments (4)
  1. [Appendix B, Theorem 1 proof] The induction in the proof of Theorem 1 does not establish the stated bound. After bounding both ceilings by L = ceil(log_{c*+1} m), the terms combine to 2c*L + c*(c*−1)/(c*+1), not 2c*L; the extra nonnegative term is silently dropped. Consequently, the proof only gives C(m) < 2c*L + O(c*), which is not the claimed O(c* log(1/tau)/log(c*+1)) when L is small, e.g., for large c* and moderate tau. The big-O rate may be recoverable by a sharper analysis, but the proof as written is incorrect.
  2. [Appendix B, Lemma 6 and Theorem 2 proof] The proof of Lemma 6 contains a sign error: the identity should be 1−q = P(<u,g_t> <= −a), equivalently P(<u,g_t> > a), not P(<u,g_t> > −a), where a = cos(alpha_t)*omega_t/delta > 0; the stated identity is actually q, the low-cost query probability. In the proof of Theorem 2, the ratio (1+E2)/J is claimed to be Theta(d^{1/2}), but with E2 = Theta(n_t^{1/2}) and J = Theta(n_t^{1/2} d^{1/2}) it is Theta(d^{-1/2}). These errors are internally inconsistent. Although the final O(d^{-z}) conclusion may still hold because the error term K decays exponentially, the proof needs correction.
  3. [Section 3.2 (Eq. (3)) and Section 4 (Table 1)] The optimal overshoot omega_t and weighting beta_t in AGREST, and hence the reported up-to-40% improvements, are derived under the local linearity assumption of Eq. (3). The only empirical validation is in Appendix C (Fig. 4), where the predicted and empirical low-cost query probabilities are compared for one AGREST iteration on 100 ImageNet images. This does not test the linearization error across iterations, models, or at the operating overshoot. Since Section 5 acknowledges that local linearity may not hold for some models, the central quantitative claim requires a direct test (e.g., comparing predicted and observed p_t over all iterations and models) or a sensitivity analysis showing that deviations from Eq. (3) do not erase the reported gains.
  4. [Appendix D (hyperparameter m) and Table 1] The scheduler rate m introduced in Algorithm 2 is tuned on 20 randomly selected images at c* = 10^3 and then fixed across all other cost ratios and models. The paper claims generality across arbitrary cost ratios, but it does not report how sensitive the results are to m for other c* values, nor whether the validation images are disjoint from the 500-image test set. If m is re-tuned per c*, the reported improvements are partly conditional on this tuning. Please clarify the selection procedure and provide results for at least one additional c* value to demonstrate robustness.
minor comments (5)
  1. [Tables 1-3] Tables 1-3 report no variance or confidence intervals; the claim of consistently lower cost would be stronger with error bars or multiple random seeds.
  2. [Table 2] Some entries in Table 2 are non-monotonic in total cost (e.g., the HSJA VA+AGREST row for c* = 100), which suggests high variance; this should be discussed.
  3. [After Theorem 3] The notation after Theorem 3, 'omega* = cos alpha_1 * omega*_1 = cos alpha_2 * omega*_2', re-uses omega* for both the optimized overshoot and the scheduler constant; please introduce distinct symbols.
  4. [Appendix C, Figure 4] Appendix C's Figure 4 appears to have garbled axis labels and legend text; the figure should be regenerated with proper fonts and labels.
  5. [Algorithm 3] In Algorithm 3, the budget c_t is an expected cost, but the while loop terminates on actual cost, so the total cost may exceed c_t; please state whether a hard budget is enforced in the experiments.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found: the optimal overshoot in AGREST is derived from an explicitly stated local-linearity assumption and benchmarked against external attacks, while the scheduler rate m is a tuned hyperparameter rather than a fitted prediction.

full rationale

The derivation chain is self-contained relative to its stated assumptions. The low-cost query probability p_t(omega_t) in Lemma 1 follows from the explicitly stated local-linearity assumption in Eq. (3) together with the hyperspherical cap formula, and it is not defined in terms of the empirical outcomes that AGREST later predicts; Appendix C simply checks the theoretical p_t against observed frequencies as a consistency test. Theorem 3 maximizes the surrogate objective J and returns the best AGREST parameter within the declared estimator family, so its optimality claim is conditional on the stated linearity and does not reduce to a fitted output. The AS cost bound in Theorem 1 is derived under the explicit uniform-boundary Assumption A1, and the reported improvements of up to 40% are measured against external baselines (SurFree, HSJA, GeoDA, CGBA, and Stealthy HSJA) on ImageNet and CLIP, rather than against the framework's own inputs. The heuristic scheduler for alpha_t is explicitly labeled as a heuristic and motivated by HSJA's convergence result, not by a result from this paper. The scheduler rate m is selected on 20 images at a fixed c* and budget; that is a hyperparameter-tuning or overfitting concern (a correctness risk), not a circular reduction. Self-citations to GeoDA, qFool, and the Fawzi-Moosavi-Dezfooli-Frossard papers provide background for the local-linearity assumption, but the assumption is stated directly in the paper and those cited works do not contain the AGREST result, so the citations are not load-bearing in a circular sense. No equation in the paper is defined in terms of the quantity it claims to predict, and no fitted parameter is renamed as a prediction.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The central claim depends on two domain assumptions, one uniform-prior assumption for the search analysis, and one fitted hyperparameter. No new physical or conceptual entities are introduced.

free parameters (1)
  • scheduler rate m = 0.02 (HSJA), 0.06 (GeoDA, CGBA)
    Controls the decay of cos α_t in the overshooting scheduler; selected using 20 ImageNet images at c*=10^3 and 250K total cost (App. D, Fig. 5), not derived from theory.
assumptions (3)
  • domain assumption Assumption A1: the boundary point along a chosen search path is uniformly distributed in [0,1).
    Used to compute expected cost in Theorem 1 and to derive the 1:c* split; real decision boundaries need not be uniform.
  • domain assumption Local linearity of the decision function S around the boundary point xt (Eq. 3).
    Underpins Lemma 1 and Theorems 2-4; deep network boundaries are not exactly linear and the paper acknowledges this may affect gradient estimates.
  • domain assumption Initial boundary point x1 has no closer adversarial point along the ray x*→x1 and its direction is independent of the true gradient.
    Used in Theorem 4 to fix the initial angle α1; approximate for random initialization and not verified empirically.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Rewriting the Budget: A General Framework for Black-Box Attacks Under Cost Asymmetry." pith.science (2026). https://pith.science/paper/EAVNVY7F

@misc{pith2026250606933,
  author       = {Pith},
  title        = {Pith review of: Rewriting the Budget: A General Framework for Black-Box Attacks Under Cost Asymmetry},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EAVNVY7F}},
  note         = {Machine review of arXiv:2506.06933}
}
read the original abstract

Traditional decision-based black-box adversarial attacks on image classifiers aim to generate adversarial examples by slightly modifying input images while keeping the number of queries low, where each query involves sending an input to the model and observing its output. Most existing methods assume that all queries have equal cost. However, in practice, queries may incur asymmetric costs; for example, in content moderation systems, certain output classes may trigger additional review, enforcement, or penalties, making them more costly than others. While prior work has considered such asymmetric cost settings, effective algorithms for this scenario remain underdeveloped. In this paper, we propose a general framework for decision-based attacks under asymmetric query costs, which we refer to as asymmetric black-box attacks. We modify two core components of existing attacks: the search strategy and the gradient estimation process. Specifically, we propose Asymmetric Search (AS), a more conservative variant of binary search that reduces reliance on high-cost queries, and Asymmetric Gradient Estimation (AGREST), which shifts the sampling distribution to favor low-cost queries. We design efficient algorithms that minimize total attack cost by balancing different query types, in contrast to earlier methods such as stealthy attacks that focus only on limiting expensive (high-cost) queries. Our method can be integrated into a range of existing black-box attacks with minimal changes. We perform both theoretical analysis and empirical evaluation on standard image classification benchmarks. Across various cost regimes, our method consistently achieves lower total query cost and smaller perturbations than existing approaches, with improvements of up to 40% in some settings.

Figures

Figures reproduced from arXiv: 2506.06933 by the authors.

Figure 1
Figure 1. Each point represents the median number of queries required by an attack method to reach a median ℓ2 norm of 10. The x-axis shows the num￾ber of flagged queries (Qflagged) and the y-axis re￾ports the total number of queries (Qtotal). It demon￾strates the superiority of our method in achieving a more favorable trade-off between flagged and total number of queries in stealthy attack settings. Debenedetti et al. [14] i… view at source ↗
Figure 2
Figure 2. Left. Illustration of Asymmetric Gradient Estimation (AGREST), which reduces the frequency of high-cost queries by shifting the sampling region from xt toward the adversarial region x ′ t and appropriately reweighting the outcomes. Right. Three steps of Asymmetric Search (AS) along the path from a clean (flagged) source image to an adversarial (non-flagged) image. Flagged queries are shown in red, non-flagged querie… view at source ↗
Figure 3
Figure 3. Performance of various asymmetric attacks compared to Stealthy HSJA under high cost asymmetry with ResNet-50. The value of c ⋆ is 104 , 105 , and ∞ from left to right. Asymmetric attacks against CLIP. We evaluate CLIP [28] as a representative vision-language model (VLM) under both zero-shot and fine-tuned settings. Our asymmetric attack achieves significantly better performance than stealthy baselines; results are p… view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Empirical study of AS and AGREST. The left plot compares AS with vanilla search (binary [PITH_FULL_IMAGE:figures/full_fig_p022_4.png]
Figure 5
Figure 5. Figure 5: Median ℓ2 distance of adversarial perturbations for varying values of m, with c ⋆ = 103 and a total query cost of 150K. AGREST with dimension reduction As mentioned earlier, most practical attacks use a dimension reduction matrix R ∈ R d×d ′ to perform the sampling pro…
Figure 6
Figure 6. Figure 6: provides a visual example of the Asymmetric Search (AS) algorithm running with parameters τ = 0.1 and c ⋆ = 2. The illustration shows the iterative progression and query evaluations leading to successful convergence near the decision boundary. Asymmetric Search (AS) Al…
Figure 7
Figure 7. Figure 7: Performance of various asymmetric attacks compared to Stealthy HSJA on CLIP. [PITH_FULL_IMAGE:figures/full_fig_p026_7.png]
Figure 8
Figure 8. Figure 8: Comparison of vanilla gradient estimation and its asymmetric counterpart. Vanilla sampling results in roughly half high-cost and half low-cost queries, whereas AGREST reduces the frequency of high-cost queries by shifting the sampling region and weighting outcomes acco…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

53 extracted references · 39 canonical work pages

  1. [14]

    Evading black-box classifiers without breaking eggs

    Edoardo Debenedetti, Nicholas Carlini, and Florian Tramèr. Evading black-box classifiers without breaking eggs. In2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 408–424. IEEE, 2024

    work page 2024

  2. [1]

    Decision-based adversarial attacks: Reliable attacks against black-box machine learning models.arXiv preprint arXiv:1712.04248, 2017

    Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: Reliable attacks against black-box machine learning models.arXiv preprint arXiv:1712.04248, 2017

    arXiv 2017

  3. [2]

    Imagenet: A large- scale hierarchical image database

    Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009

    2009

  4. [3]

    Hopskipjumpattack: Aquery-efficient decision-based attack

    JianboChen,MichaelIJordan,andMartinJWainwright. Hopskipjumpattack: Aquery-efficient decision-based attack. In2020 ieee symposium on security and privacy (sp), pages 1277–1294. IEEE, 2020

    work page 2020

  5. [4]

    Rays: Araysearchingmethodforhard-labeladversarialattack, 2020

    JinghuiChenandQuanquanGu. Rays: Araysearchingmethodforhard-labeladversarialattack, 2020

    work page 2020

  6. [5]

    Query-efficient hard-label black-box attack: An optimization-based approach.arXiv preprint arXiv:1807.04457, 2018

    Minhao Cheng, Thong Le, Pin-Yu Chen, Jinfeng Yi, Huan Zhang, and Cho-Jui Hsieh. Query-efficient hard-label black-box attack: An optimization-based approach.arXiv preprint arXiv:1807.04457, 2018

    arXiv 2018

  7. [6]

    Sign-opt: A query-efficient hard-label adversarial attack.arXiv preprint arXiv:1909.10773, 2019

    Minhao Cheng, Simranjit Singh, Patrick Chen, Pin-Yu Chen, Sijia Liu, and Cho-Jui Hsieh. Sign-opt: A query-efficient hard-label adversarial attack.arXiv preprint arXiv:1909.10773, 2019

    arXiv 1909

  8. [7]

    Ageometry-inspireddecision- based attack, 2019

    YujiaLiu,Seyed-MohsenMoosavi-Dezfooli,andPascalFrossard. Ageometry-inspireddecision- based attack, 2019

    work page 2019

Show all 53 references
  1. [8]

    Geoda: a geometric framework for black-box adversarial attacks

    Ali Rahmati, Seyed Mohsen Moosavi-Dezfooli, Pascal Frossard, and Huaiyu Dai. Geoda: a geometric framework for black-box adversarial attacks. InProceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 8446–8455, 2020

    2020

  2. [9]

    How does facebook use artificial intelligence to moderate content? URLhttps: //www.facebook.com/help/1584908458516247, 2024

    Facebook. How does facebook use artificial intelligence to moderate content? URLhttps: //www.facebook.com/help/1584908458516247, 2024. Accessed 03-05-2024

    2024

  3. [10]

    X’s sensitive media policy

    Twitter. X’s sensitive media policy. URL https://help.twitter.com/en/ rules-and-policies/media-policy, 2024. Accessed 03-05-2024

    2024

  4. [11]

    Detect explicit content (safe search)

    Google. Detect explicit content (safe search). URLhttps://cloud.google.com/vision/ docs/detecting-safe-search, 2024. Accessed 03-05-2024

    2024

  5. [12]

    Moderating content

    Amazon. Moderating content. URL https://docs.aws.amazon.com/rekognition/ latest/dg/moderation.html, 2024. Accessed 03-05-2024

    2024

  6. [13]

    Detect adult, racy, or gory content

    Microsoft. Detect adult, racy, or gory content. URL https://learn.microsoft.com/ azure/ai-services/computer-vision/concept-detecting-adult-content , 2024. Accessed 03-05-2024

    2024

  7. [15]

    Egg dropping

    Gabriel Alves, Geoff Pilling, James Innes, Refath Bari, Nguyen Quang, Josh Silverman, Arron Kau, and Jimin Khim. Egg dropping. URL https://brilliant.org/wiki/ egg-dropping/, 2024. Accessed 26-04-2024

    2024

  8. [16]

    Cgba: Curvature-aware geometric black-box attack

    Md Farhamdur Reza, Ali Rahmati, Tianfu Wu, and Huaiyu Dai. Cgba: Curvature-aware geometric black-box attack. InProceedings of the IEEE/CVF International Conference on Computer Vision, pages 124–133, 2023

    2023

  9. [17]

    Understanding x limits

    Twitter. Understanding x limits. URL https://help.twitter.com/en/ rules-and-policies/x-limits, 2024. Accessed 04-05-2024. 10

    2024

  10. [18]

    Surfree: a fast surrogate-free black- box attack

    Thibault Maho, Teddy Furon, and Erwan Le Merrer. Surfree: a fast surrogate-free black- box attack. InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10430–10439, 2021

    2021

  11. [19]

    Robustness of classifiers: from adversarial to random noise.Advances in neural information processing systems, 29, 2016

    Alhussein Fawzi, Seyed Mohsen Moosavi-Dezfooli, and Pascal Frossard. Robustness of classifiers: from adversarial to random noise.Advances in neural information processing systems, 29, 2016

    2016

  12. [20]

    The robustness of deep networks: A geometrical perspective.IEEE Signal Processing Magazine, 34(6):50–62, 2017

    Alhussein Fawzi, Seyed Mohsen Moosavi-Dezfooli, and Pascal Frossard. The robustness of deep networks: A geometrical perspective.IEEE Signal Processing Magazine, 34(6):50–62, 2017

    2017

  13. [21]

    Empirical study of the topology and geometry of deep networks

    Alhussein Fawzi, Seyed Mohsen Moosavi-Dezfooli, Pascal Frossard, and Stefano Soatto. Empirical study of the topology and geometry of deep networks. InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3762–3770, 2018

    2018

  14. [22]

    On minimax signal generation and reception algorithms

    Alexander Mikhailovich Chudnov. On minimax signal generation and reception algorithms. Problemy Peredachi Informatsii, 22(4):49–54, 1986

    1986

  15. [23]

    American Mathematical Soc., 2001

    Michel Ledoux.The concentration of measure phenomenon. American Mathematical Soc., 2001

    2001

  16. [24]

    Quadpack: a subroutine package for automatic integration, volume 1

    Robert Piessens, Elise de Doncker-Kapenga, Christoph W Überhuber, and David K Kahaner. Quadpack: a subroutine package for automatic integration, volume 1. Springer Science & Business Media, 2012

    2012

  17. [25]

    A simplex method for function minimization.The computer journal, 7(4):308–313, 1965

    John A Nelder and Roger Mead. A simplex method for function minimization.The computer journal, 7(4):308–313, 1965

    1965

  18. [26]

    Deep residual learning for image recognition

    Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. InProceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016

    2016

  19. [27]

    An image is worth 16x16 words: Transformers for image recognition at scale, 2021

    Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at...

    2021

  20. [28]

    Learning transferable visual models from natural language supervision, 2021

    Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, GirishSastry,AmandaAskell,PamelaMishkin,JackClark,GretchenKrueger,andIlyaSutskever. Learning transferable visual models from natural language supervision, 2021

    2021

  21. [29]

    Scipy 1.0: fundamentalalgorithmsforscientificcomputinginpython

    Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. Scipy 1.0: fundamentalalgorithmsforscientificcomputinginpython. Naturemethods,17(3):261–272, 2020

    2020

  22. [30]

    Visionllama: A unified llama backbone for vision tasks, 2024

    Xiangxiang Chu, Jianlin Su, Bo Zhang, and Chunhua Shen. Visionllama: A unified llama backbone for vision tasks, 2024

    2024

  23. [31]

    Llama 2: Open foundation and fine-tuned chat models, 2023

    Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, NikolayBashlykov,SoumyaBatra,PrajjwalBhargava,ShrutiBhosale,DanBikel,LukasBlecher, CristianCantonFerrer,MoyaChen,GuillemCucurull,DavidEsiobu,JudeFernandes,JeremyFu, Wenyin Fu, Brian Fuller,...

    2023

  24. [32]

    Jailbreaking leading safety-aligned llms with simple adaptive attacks.arXiv preprint arXiv:2404.02151, 2024

    Maksym Andriushchenko, Francesco Croce, and Nicolas Flammarion. Jailbreaking leading safety-aligned llms with simple adaptive attacks.arXiv preprint arXiv:2404.02151, 2024

    2024 arXiv

  25. [33]

    Jailbreakbench: An open robustness benchmark for jailbreaking large language models

    Patrick Chao, Edoardo Debenedetti, Alexander Robey, Maksym Andriushchenko, Francesco Croce, Vikash Sehwag, Edgar Dobriban, Nicolas Flammarion, George J Pappas, Florian Tramer, et al. Jailbreakbench: An open robustness benchmark for jailbreaking large language models. arXiv pre...

    2024 arXiv

  26. [34]

    Chrysos, and Volkan Cevher

    Elias Abad Rocamora, Grigorios G. Chrysos, and Volkan Cevher. Certified robustness under bounded levenshtein distance, 2025

    2025

  27. [35]

    Explainingandharnessingadversarial examples

    IanJGoodfellow,JonathonShlens,andChristianSzegedy. Explainingandharnessingadversarial examples. arXiv preprint arXiv:1412.6572, 2014

    2014 arXiv

  28. [36]

    Deepfool: a simple and accurate method to fool deep neural networks

    Seyed Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: a simple and accurate method to fool deep neural networks. InProceedings of the IEEE conference on computer vision and pattern recognition, pages 2574–2582, 2016

    2016

  29. [37]

    Towards evaluating the robustness of neural networks

    Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp), pages 39–57. Ieee, 2017

    2017

  30. [38]

    Su- perdeepfool: a new fast and accurate minimal adversarial attack

    Alireza Abdolahpourrostam, Mahed Abroshan, and Seyed-Mohsen Moosavi-Dezfooli. Su- perdeepfool: a new fast and accurate minimal adversarial attack. InThe Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    2024

  31. [39]

    Simpleblack-boxadversarialperturbations for deep networks.arXiv preprint arXiv:1612.06299, 2016

    NinaNarodytskaandShivaPrasadKasiviswanathan. Simpleblack-boxadversarialperturbations for deep networks.arXiv preprint arXiv:1612.06299, 2016

    2016 arXiv

  32. [40]

    Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models

    Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 15–26, 2017

    2017

  33. [41]

    Black-box adversarial attacks with limited queries and information

    Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. InInternational conference on machine learning, pages 2137–2146. PMLR, 2018

    2018

  34. [42]

    Online convex optimization in the bandit setting: gradient descent without a gradient

    Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007, 2004

    2004 arXiv

  35. [43]

    Randomgradient-freeminimizationofconvexfunctions

    YuriiNesterovandVladimirSpokoiny. Randomgradient-freeminimizationofconvexfunctions. Foundations of Computational Mathematics, 17(2):527–566, 2017

    2017

  36. [44]

    Qeba: Query-efficient boundary-based blackbox attack

    Huichen Li, Xiaojun Xu, Xiaolu Zhang, Shuang Yang, and Bo Li. Qeba: Query-efficient boundary-based blackbox attack. InProceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 1221–1230, 2020

    2020

  37. [45]

    Ageometry-inspireddecision- based attack

    YujiaLiu,SeyedMohsenMoosavi-Dezfooli,andPascalFrossard. Ageometry-inspireddecision- based attack. InProceedings of the IEEE/CVF International Conference on Computer Vision, pages 4890–4898, 2019

    2019

  38. [46]

    Triangle attack: A query-efficient decision-based adversarial attack

    XiaosenWang,ZeliangZhang,KanghengTong,DihongGong,KunHe,ZhifengLi,andWeiLiu. Triangle attack: A query-efficient decision-based adversarial attack. InEuropean conference on computer vision, pages 156–174. Springer, 2022

    2022

  39. [47]

    Springer Science & Business Media, 1986

    Vitali D Milman and Gideon Schechtman.Asymptotic theory of finite dimensional normed spaces: Isoperimetric inequalities in riemannian manifolds, volume 1200. Springer Science & Business Media, 1986

    1986

  40. [48]

    A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.The Annals of Mathematical Statistics, pages 493–507, 1952

    Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.The Annals of Mathematical Statistics, pages 493–507, 1952

    1952

  41. [49]

    Cambridge University Press, 2023

    Mor Harchol-Balter.Introduction to probability for computing. Cambridge University Press, 2023. 12 A Related work Decision-based attacks. Adversarial examples can be crafted in three setups: white-box [35,36, 37, 38], score-based black-box [39, 40, 41], and decision-based blac...

    2023

  42. [50]

    GeoDA and qFool [8,45] use techniques similar to HSJA’s gradient estimation to locally approximate the decision boundary as a hyperplane at each iteration

    uses various techniques to approximate the gradient of the classification margin more effectively thanHSJA,leveraginginsightslikelocalsimilarityandtheimportanceofthelow-frequencysubspace. GeoDA and qFool [8,45] use techniques similar to HSJA’s gradient estimation to locally ap...

  43. [51]

    copy ofbϕt,i, then the following inequality holds: P 1 nt ntX i=1 bϕ2 t,i − E[ bϕ2 t ] > ε ! ≤ 2 exp − 2ntε2 (2βt − 1)2

    If bϕt is an i.i.d. copy ofbϕt,i, then the following inequality holds: P 1 nt ntX i=1 bϕ2 t,i − E[ bϕ2 t ] > ε ! ≤ 2 exp − 2ntε2 (2βt − 1)2 . 14 Proof of Lem. 3: The result follows by applying the Chernoff bound for binomial distributions [48, 49] to the transformed random var...

  44. [52]

    (Upper bound) µ(xt, ωt, βt, nt) ≤ √nt E h bϕt⟨gt, u⟩ i q E[ bϕ2 t ] − ε2 − (nt − 1)β2 t ε1 +  1 + √nt βtq E[ bϕ2 t ] − ε2 − (nt − 1)β2 t ε1   Knt,d (ε1, ε2) . 15

  45. [53]

    Here, the error termKnt,d(ε1, ε2) is defined as Knt,d (ε1, ε2) = nt(nt + 1) exp −Cdε 2 1 + 2 exp − 2ntε2 2 (2βt − 1)2 , for some universal constantC >0

    (Lower bound) µ(xt, ωt, βt, nt) ≥ √nt E h bϕt⟨gt, u⟩ i q E[ bϕ2 t ] + ε2 + (nt − 1)β2 t ε1 −  1 + √nt βtq E[ bϕ2 t ] + ε2 + (nt − 1)β2 t ε1   Knt,d (ε1, ε2) . Here, the error termKnt,d(ε1, ε2) is defined as Knt,d (ε1, ε2) = nt(nt + 1) exp −Cdε 2 1 + 2 exp − 2ntε2 2 (2βt − ...

    2000

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.