SAIF: Sparse Adversarial and Imperceptible Attack Framework
Authors: Tooba Imtiaz
Morgan R Kohler
Jared F Miller
Zifeng Wang
Masih Eskandar
Mario Sznaier
Octavia Camps
Jennifer Dy
Venue: Accepted by TMLR ()

Abstract: Adversarial attacks hamper the decision-making ability of neural networks by perturbing the input signal. For instance, adding calculated small distortions to images can deceive a well-trained image classification network. In this work, we propose a novel attack technique called \textbf{S}parse \textbf{A}dversarial and \textbf{I}mperceptible Attack \textbf{F}ramework (SAIF). Specifically, we design imperceptible attacks that contain low-magnitude perturbations at a few pixels and leverage these sparse attacks to reveal the vulnerability of classifiers. We use the Frank-Wolfe (conditional gradient) algorithm to simultaneously optimize the attack perturbations for bounded magnitude and sparsity with $O(1/\sqrt{T})$ convergence. Empirical results show that SAIF computes highly imperceptible and interpretable adversarial examples, and largely outperforms state-of-the-art sparse attack methods on ImageNet and CIFAR-10.

Published in Transactions on Machine Learning Research (07 (07/2025)
SAIF: Sparse Adversarial and Imperceptible Attack Frame- work
Tooba Imtiaz Morgan R. Kohler 1, Jared F. Miller Zifeng Wang 9, Masih Eskander, Mario Sznaier, Octavia Camps and Jennifer Dy 1
Department of Electrical & Computer Engineering, Northeastern University, Boston MA.
Reviewed OpenReview:
Abstract
Adversarial attacks hamper the decision-making ability of neural networks by perturbing the input signal. For instance, adding calculated small distortions to images can deceive a well-trained image classification network. In this work, we propose a novel attack tech- nique called Sparse Adversarial and Imperceptible Attack Framework (SAIF). Specifically, we design imperceptible attacks that contain low-magnitude perturbations at a few pix- els and leverage these sparse attacks to reveal the vulnerability of classifiers. We use the Trank-Wolfe (conditional gradient) algorithm to simultaneously optimize the attack pertur- bations for bounded magnitude and sparsity with O(1/VT) convergence, Empirical results show that SAIF computes highly imperceptible and interpretable adversarial examples, and largely outperforms state-of-the-ard sparse atlack methods on ImageNet and CIFAR-10. Implementation of SAIF is available at https:/ http///gttttttttt ggttub..cm//toolie wott./ooo/oooot//SS.A.
1 Introduction
Deep neural networks (DNNs) are widely utilized for various tasks such as object detection (Redmon ct al. 2016 Girshick 2015), classification (Krizhevsky et al., 2012 He et al. 2016). and anomaly delection (Chan- dola et al.] 2009). These DNNs are ubiquitously integrated into real-world systems for medical diagnosis, autonomous driving, surveillance, etc., where misguided decision-makee makinn can have catastrophic consequences. Therefore, it is crucial to inspect the limitations of DNNs before deployment in such aefetyccritical systems.
Adversarial attacks (Szegedy et al. 2014) are one means of exposing the fragility of DNNs. In the classification task, these attacks can fool well-trained classifiers to make arbitrary (untargeted) MMosavi-Dezfool et al. 2016) or targeted misclassifications (Carlini & Wagner 2017 by negligibly manipulating the input signal. For instance, a road sign classifier can be led interpret a slightly modified stop sign as speed limit sign (Benz) ct al. 2020). Such adversarial attacks fool learning algorithms with high confidence while being imperceptible to the human eye. Most atlack methods achieve this by constraining the pixel-wise magnitude of the perturbation. Minimizing the number of modified pixels is another strategy for making the perturbations
unnoticeable (Su et al. [201 Narodytska & Kasiviswanathan 2017). Bringing these two together generates
high-stealth attacks (Modas et al. 2019 Croce & Hein 2019 Dong et al. 2020 Fan et al. 2020: Williams
& Li 2023
Existing mothods, however, fail produce attacks with simultancously very high sparsity and low magnitude perturbations. In this paper, we address this limitation by designing novel method that produces strong
"Corrssoondng author. intiaa, tonorrtttootttttrncncooo
kooler.r.morgannk/. moggan&ggmail.com Work done while author was at Northeastern University. jjared. meireddiilleriii uni-stutigart.dd. Work done while author was at Northeastern University. saffengwdgooglee.omm Work done while author at Northeastern University. (eskandar.ng m, m.sznaier, o.camps, j.dy) Smortheastern.edl

---

Published in Transactions on Machine Learning Research (07/2025)
Input 'x'
Perturbation 'p' + P
Input 'x'
Perturbation 'p'
x + p
kit lox (96.2%)
byena (100%)
dingo (94.3%)
screwdriver (100%)
vulture (95.0%)
Loy shop (99.6%) moving (98.0%)
dust cart (100%)
Figure I: Using the Trank-Wolit algorithm to jointly constrain the perturbation magnitude and sparsity, we craft highly sparse and imperceptible adversarial attack. By restricting attack sparsity, we can visualize the most vulnerable pixels in an image. The GT bounding boxes for the subject of the input x are drawn in red. Note that SAIF mostly distorts pixels within that region. Inception-v3 is used for predicting labels.
adversarial attacks with a significantly low perturbation strength and high sparsity. Our proposed approach, we call Sparse Adversarial and Imperceptible attack Framework (SAIF), minimally modifies only fraction of pixels to generate highly concealed adversarial attacks.
SAIF aims to jointly minimize the perturbation magnitude and sparsity. We formulate this objective as a constrained optimization problem. Previous works propose projection-based methods (such as PGD (Madry et al. 2018)) to optimize similar objectives, however, these require projection step at each iteration to obtain feasible solutions (Croce & Heiin 2019 Such projections give rise to iterates very close to/at the constraint boundary, and projecting the solutions can diminish their 'optimality'. Optimization methods
such as ADMM (Xu et. al.) 2019 Fan et al. 2020) and homolopy (Fan et al. 2020 have also been explored
but have prohibitively long running times for large images.
To address these limitations, we propose to optimize our objective using the Wolle algorithm (FW) Frank et al., 1956). FW is projection-free, iterative method for solving constrained convex optimization problems using conditional gradients. In contrast to PGD attacks, the absence of a projection step allows Frank Wolfe to find perturbations well within the constraint boundaries. Throughout optimization, the iterates are within the constraint limits as they are convex combinations of feasible points. Moreover, there are several algorithmic variants of Trank-Wolfe for efficient optimization.
Furthermore, the benefit from adversarial examples can be maximized by examining the vulnerabilities of deep networks alongside model explanations (Ignatiev et al., 2019: Wang et al. [022 Xu et al., 2019). Magnitude-coonstrined attacks distort all image pixels, leaving little room to interpret the additive pertur- bations. Our proposed attack offers explicit control over the sparsity of the distortions. This facilitates more controlled and straightforward semantic analyses, such as identifying the top-"k '/' pixels critical to fool DNNs.
Concretely, the contributions of this paper are:
We introduce novel optimization-base adversarial attack that is visually imperceptible due to low-magnitude distortions to fraction of image pixels.
We show through comprehensive experiments that, for tight sparsity and magnitude constraints, SAIF outperforms state-of-the-art sparse attacks by large margin (by 2 2x higher fooling rates for most thresholds).
2

---

Published in Transactions on Machine Learning Research (07/2025)
Our sparse attack provides transparency by indicating vulnerable pixels in images. We quantitatively evaluate the overlap between perturbations and salient image regions to emphasize the utility of SAIF for such analyses.
2
Related Works
Constrained Adversarial Attacks. The first discovered adversarial attack by Szegedy et al. (0144) uses nox-constrained L-BFGS to minimize the l norm of additive distortion, however, is slow and does not scale to larger inputs. To overcome speed limitations, the Fast Gradient Sign Method (FGSM) GGoodfellow al., 2015) uses lo constrained gradient ascent w.r.t. the loss gradient for each pixel, compute an efficient attack but with poor convergence. Projected Gradient Descent (PGD) is another optimization-based attack algorithm that is fast and computationally cheap, but yields solutions closer to the boundary and often fails to converge (addy et al. 2018).. Auto-attack (Croce & Hein 2020) addresses the convergence limitations of PGD. Nevertheless, these attacks distort all the image pixels, potentially leading to high visual perceptibility. We address this shortcoming by explicitly constraining the sparsity of the adversarial perturbations.
Charsity-Constrainee Adversarial Attacks. The Jacobian-based Saliency Map Attack (JSMA) de- notes pixel-wise saliency by backpropagated gradient magnitudes, then searches over the most salient pixels for a sparse targeted perturbation (Papernot et al. 2016). This attack is slow and fails to scale to larger images. SparseFool (Modas et al. 2019) extends DeepFool -Moosavi-Dezoooo et al. 2016) to a sparse attack within the valid pixel magnitude bounds. The attack, however, is untargeted. Croce & Hein (2019) devise a black-box attacks PGD too and PGD to+a by evaluating the impact of each pixel on logits and randomly sampling salient pixels to find a feasible sparse combination. Similar to JSMA, these attacks are expensive to compute, visually noticeable, and unstructured. The same limitations hold for SA-MOO (Williams & Li, 2023). StrAttack (Xu et al. 2019) uses ADMM (Alternating Direction Method of Multipliers) optimize for group sparsity and perturbation magnitude constraints, but the perturbations pensive, visually noticeable, and of low sparsity. SAPF (Fan et al. 2020) also uses ADMM with projections to solve a factorized objective. It fails to converge for a tighter sparsity budget, requires extensive hyper- parameter tuning, and has a prohibitively long running time. Among generator- based methods, Dong et al.) (2020) propose Greedy Fool, a two-stage approach to greedily sparsily perturbations obtained from a gen- erator. Similarly, TSAA (He al.) (202)) generates sparse, magnitude-coustrainee adversarial attacks with high black-box transferability. The perturbations are typically spatially contiguous and are therefore more noticeable than other sparse allacks. The design of our atlack, and employing Frank-Wai Wolfe for optimization, yield highly sparse and inconspicuous ad adversarial examples efficiently.
compulationally ex-
Understanding Adversarial Attacks A fairly novel research direction examines adversarial examples and model explanations in conjunction, noting the overlap between core ideas the domains. On simple datasets such MNIST, Ignatiev al. (2019) demonstrates hitting set duality between model explanations and adversarial examples i.e. there exists light overlap between features identified imporlant for model's prediction and those targeted by successful adversarial attacks (and that one be recovered from the other), suggesting that both explanations and attacks often focus on the same critical input features. Similarly, Wang el al. (2022) leverage adversarial allacks to devise a novel model explainer. Xu et al. (2019) examine the correspondence of attack perturbations with discriminative image features. We formulate our attack with an explicit sparsity constraint, which emphasizes only the most vulnerable pixels in an image. We also empirically analyze the overlap of adversarial perturbations and salient regions images.
3 Background
In this section, we introduce the notations and conventions for adversarial attacks. We also provide a brief review of the Frank-Wolfe algorithm.
3

---

Published in Transactions on Machine Learning Research (07 (225))
3.1 Adversarial Attacks
Given image R hx a trained classifier f Rxxwxcc {1...C) C} that maps the image to of C' classes, and f(x) = Adversarial attacks aim at finding x' that is very similar to x by distance metric, i.e. ||x-x||> S (p 10, jo,, e is small) such that f(x)) = where +
Depending on the adversary's knowledge of the target model, adversarial attacks can be white- box (known model architecture and parameters) or black-box (unknown learning algorithm; the attacker only sees the most likely prediction given an input). Whether SAIF can be extended to the black-box setting (via, e.g.. gradient approximations (Chen et al. 2020 is not addressed in this work and deserves study.
3.2 Frank Wolfe Algorithm
The Frank-Wolfe algorithm (FW) (Frank et al., 1956, is a first-order, projection-free algorithm for optimizing a convex function f(x) over a convex set X. a projection-free method since it solves linear approxima- tion, known as the Linear Minimization Oracle (LMO), of the objective over X. The key advantage of FW is that the iterates X always remain feasible (x, E X) throughout the optimization process. The algorithm popularized for machine learning applications by Jaggi 2013) (xx)- where x* is the optimal point.
with rigorous proofs in objective value
The first work using Frank- Wolfe for adversarial attacks (Chen et al. 2020) constrains only the magnitude of perturbation -x As a result, the crafted attack is non-sparse. Later works also employ Frank- Wolfe for explaining predictions (Roberts & Tsiligkaridis 2021 and for faster adversarial training (Tilligkaridis & Wang al. 2019).
Roberts 2022
Our motivation to employ FW for optimizing SAIF is twofold: (1) it is 'conservative' algorithm with iterates strictly in the feasible region throughout the optimization. Its projection-fie -ree nature prevents sub- optimal solutions common in methods like PGD, and (2) it has sparsity-inducing properties, which fits our goal.
4 Method
Our goal is to caleulate adversarial atlack that has low magnitude and high sparsity simultaneously. Formally, the perturbations should have low fg-norm and low -orm to satisfy the sparsity and magnitude requirements, respectively. Moreover, the (untargeted) attack should maximize classification loss for the true class.
To implement such an attack, we define a sparsity-conntrained mask s to preserve pixels of an additive adversarial perturbation p. We also impose an En constraint on the magnitude p. Decoupling the allack into a sparse mask and perturbation also allows visualizing the vulnerable pixels of the image.
Untargeted Attack. Given f(x) = e, we define our untargeted objective function D(s, P)ado as
D(s, p)ade = 4 + s
(1)
Here ((.,c) c) is the classification loss function (e.g., cross-entropy) with respect to the true class
Note that optimization over the to constraint is NP-hard. We use & as the tightest convex approximation for to over s following the common practice in the literature (Macdonald et al. 2022 He et al. 2022). Thus, the optimization objective is to maximize the loss for the original class as:
max D(s, p)edu. s.t./|s/11 < k, s 1xxwech |Ipll Se s.p
(2)
This formulation not only highlights the vulnerable regions of the image to perturb via s, but also yields an adversarial attack method where we can explicitly control the sparsity using k and the perturbation magnitude per pixel with
4

---

Published in Transactions on Machine Learning Research (07/2025)
Targeted Attack.
We extend 1 to targeted attacks by replacing with chosen target class č.
D(s,Pla,ed + č č
(3)
Then to enhance the odds of predicting è, minimize o to obtain the SAIF attack:
min (s, P)a,ades s.t.||s||1 S k, E [0, 1 hxwxok ||p| S s.p
(4)
Optimization. We use Frank- Wolfe the solver for our objectives 2 and in order to ensure that the variable iterates remain feasible (see Algorithm []. The algorithm proceeds by moving the iterates towards a minimum by simultaneously minimizing the objective w.r.t. 8 and p.
To constrain S we use a non-negative k-sparse polytope, which is convex hull of the set of vectors in 00, 1]xxarxe,, each vector admitting most & non-zero elements. We adopt the method in Macdonald et al. 2022 to perform the LMO over this polytope. That is, for 2t choose the vector with at most k non-zero entries, where the conditional gradient mf assumes & smallest negative values (thus highest in magnitude). These k components of Ze are then set to 1 and the rest lo zero. For example, if A: = 10 and there are 20 negative values in m the 10 smallest values are set to 1 and the rest to O.
For P. the LMO of foo has a closod-form solution Chen et al. 2020
V. - sign(m)))
(5)
Note that it possible combine s and p into one variable using a method such as Gidel et al. (2018) However, in doing we would lose the interpretability brought by disentangling the sparse mask This is because enforcing an & constraint is not the same as the currently enforced k-sparse polytope. Therefore, such a dual constraint would result in perturbation of varying values which is harder to interpret than a [o, 1]-valued mask.
Since the objective of SATF is non-convex, a monotonicity guarantee helpful to ensure that the separate optimizations of each variable syne well. Such monotonicity guarantee facilitates coordinated convergence of the sparse mask and perturbation variables, ensuring that both sparsity and magnilude constraints are jointly optimized in stable and synchronized manner. To this end, use the following adaptive step size formulation (Carderera et al. 2021: Macdonald et al. 2022) to ensure monotonicity in the objective, which, together with the iterates being convex combinations, ensures that solutions do not leave the domain of feasible solutions:
1/ 2n +I+I
(6)
where we choose the r2 E N by increasing from rt-1, until we observe primal progress of the iterates. This method conceptually similar to the backtracking line search technique often used with standard gradient descent.
5 Experiments
We evaluate SAIF against several existing methods for both targeted and untargeted attacks. We report performance on the effectiveness as well as saliency of adversarial attacks.
Datasct and Models We use the ImageNet classification datasct (ILSVRC2012) KKrizhessky et al. 2012) in our experiments, which has [299 x 299] RGB images belonging to 1,000 classes. We evaluate all atlacks on 5,000 samples chosen from the validation set. For classification, we test on two deep convolutional neural network architectures, namely Inception-v3 (top-1 accuracy: 77.9%) and ResNet-50 (top-1 accuracy: 74.9%). We use the pre-trained models from Keras applications (Chollet et al. 2015). We also report results CIFAR-10 in the appendix.
5

---

Published in Transactions on Machine Learning Research (07/2025)
Algorithm 1: SATF Adversarial attack using Trank-Wolff for joint optimization.
Input: Clean image x E marl [maxa]xxxxe, So E C, = {s E [0, 1|xxuxck ||||| S k),
Po E Cp = {p E [0, maz] [maz) hxxxcc :|plloo S e).
Output: Perturbation p, Sparse mask
for 1..... do
m 1s P1-1)
m I.D(
Vi argminvec, (m v)
Z: argmin (mj; 2)
P: P:-1 17, (V: Pt- P(-1)
S, S (7 8,-1)
end
Inception-v3
ResNet50
|pl
Attacks
Sparsity "k"
Sparsity 'I"
100
200
600
1000
2000
100
200
600
1000
2000
GreedyFool
0.40
1.19
19.36
49.70
87.82
0.59
2.59
28.94
70.06
96.21
TSAA
0.00
1.15
31.61
77.01
100.0
255
Homotopy-Attack
0.00
18.23
90.97
100.0
100.0
0.00
0.00
0.00
0.00
0.00
SAIF (Ours)
55.97
84.00
100.0
100.0
100.0
80.10
100.0
100.0
100.0
100.0
100
200
600
1000
2000
100
200
600
1000
2000
GreedyFool
0.20
0.40
4.59
12.18
25.35
0.20
1.59
12.37
28.
44.11
100
Homotopy-Ataen
9.04
18.27
72.07
100.0
100.0
0.00
(Ours)
21.73
66.27
100.0
100.0
100.0
59.01
90.72
100.0
100.0
100.0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
CrcedyFool Hlomotopy-Attack
0.20
1.39
2.99
5.59
8,98
5.59
18.36
30. 14
39.12
47.50
10
0.00
30.05
58.27
69.59
85.03
0.00
0.00
0,00
0.00
0.00
SAIF (Ours)
14.28
44.79
90.29
94.97
100.0
60.19
80.02
89.93
90.42
100.0
Table 1: Quantitative evaluation of targeted attack ImageNet. We report the ASR for varying constraints sparsity 'k' and -oom of the magnitude of perturbation 'e'. (* TSAA codebase lacks pre-trained generators for targeted attacks on Re and lower e.)
Implementation We implement the experiments Julia and use the Frank- Wolfe variants library (Be sançon al., (021). We code the classifier and gradient computation backend Python using TensorFlow run on single Tesla V100 SXM2 GPU, for
and Keras deep learning frameworks. The experiments empirically chosen number of iterations T for each dataset. SAIF typically converges in ~20 iterations, however, we relax the maximum iterations to T 100 in our experiments.
5.1 Evaluation Metrics
Adversarial Attacks.
Adversarial attacks are commonly evaluated by the attack success rale.
Attack Success Rate (ASR). A targeted adversarial attack is deemed successful if perturbing the image fools the classifier into labeling it with premeditated target class An untargeted attack successful if it leads the classifier to predict any incorrect class. Given images in dataset, attacks successful, the attack success rate defined ASR m/n(%).
Note that for RGB images, SparseFool (Modas et al. 2019 and Greedyfool (Dong et al. 2020 average the perturbation p across the channels and report the ASR for sparsity ||Pnalllo S k, where Pran E [0, I Imaz hxw
Since for SAIF the sparsity constraint & applies across all x ch pixels, we report the ASR for all methods without averaging the final perturbation across the channels (i.e. for ||p||o k, p [0, Imaz] xxxxek))

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
X
P
xtp
X
P
x+p
Chibuabus: 96.9%
Mexican bairless: 99.9%
Ioe cream: 97.7%
Mop: 100.0%
Tricycle: 99.9%
Studio couch: 98.5%
Lotion: 99.9%
Qualitative results of targeted SAIF attack on Inception-v3 trained on ImageNet, using 100 (39% of the dynamic range of image) and h 400 (0.15% of pixels). The source and target class, along with the corresponding probability, are stated below each and x + respectively.
Figure 2:
Attack Saliency. We use the following metric capture the correspondence between the vulnerable and salient pixels in the imput images. The score represents the overlap of the ground-truth (GT) bounding box of the subject of the input image with the (sparse) adversarial perturbation.
Localization (Loc.) (Chattopadhay et al. 2018) Effectively the same loU for object de- tection. Given image pixels X, GT salient pixels S and SAIF sparse mask A, the localization score is:
|An
Loc.
(7)
| + ||An (X S)llo
In the event of perfect correspondence between the GT salient regions and adversarial perturbation, Loc.>11 Whereas, Loc.-0 when there is poor overlap between the two.
6 Results
6.1
Quantitative Results.
We evaluate the ASR of all attack methods on range of constraints on perturbation magnitude: and sparsity k. The results for targeted attacks on ImageNet are reported in Table The target class randomly chosen for each sample. Note that TSAA (He et al.) 2022 does not evaluate attacks for 100. Moreover, for both targeted and untargeted attacks, SAPF
FFan et al. 2020 fails for all the evaluated thresholds.
Table D demonstrates that SAIF consistently outperforms both targeted attack baselines by a large margin for all e and & thresholds. For smaller GreedyFool fails to attack samples unless the sparsity threshold is significantly relaxed. similar pattern observed for the sparsity budget competing attacks completely fail for tighter bounds on perturbation magnitude (scc c {10, 100, 255} at k 2000). Moroover, at lower k, ResNet50 is easier fool than Inception-v3.
We also compare the ASR for untargeted attacks against the baselines in Table 2 Here well SAIF significantly outperforms other attacks, particularly on tighter perturbation bounds. By jointly optimizing over the two constraints, we are able to fool DNNs with extremely small distortions. For instance, at e = 10, SAIF modifies only 0.37% pixels per image to successfully perturb 89.02% input samples. This is more than twice the ASR of statc-of-tho-art sparse attack methods. Similarly, at 255, only 0.03% pixels are attacked to achieve a perfect ASR. On CIFAR-10, SAIF achieves ~3x higher ASR on lower sparsity thresholds. The results reported in the Appendix.

---

Published in Transactions on Machine Learning Research (07/2025)
Inception-v3
ResNet50
Attacks
Sparsity
Sparsity
100
10
20
50
100
200
SparseFool
1.59
4.39
15.37
32.14
32.14
1.79
3.19
8,78
17.76
33.33
Foel
3.99
7.58
16.57
35.33
62.87
4.19
7.78
21.76
42.12
72.26
TSAA
0.00
0.00
0.00
0.00
2.02
0.00
0.00
0.00
1.95
16.06
255
PGD to feo
0.81
0.81
3.63
5.65
7.80
11.20
11.20
11.67
12:25
12.25
PGD to *
0,00
0.00
0.62
1.55
2.78
0.00
0.00
0.84
4.92
6.54
SA-MO0*
9.52
10.04
14.28
38.09
39.47
27.98
44.32
45.12
54.83
60.91
SAIF (Ours)
19.88
60.16
90.05
100.0
100.0
38.25
61.72
100.0
100.0
100.0
20
100
200
10
20
50
100
200
SparseFool
0.79
3.39
9.98
27.54
48.90
1.39
2.50
7.58
19.56
35.72
GreedyFool
2.39
3.79
10.18
23.15
45.11
2.20
5.99
15.77
34.73
61.68
PGD Eo loo
0.00
0.24
3.29
5.22
11.67
12.25
12.25
12.25
14.49
100
PGD to + o*
0.00
0.00
0.28
0.62
2.49
0.00
0.00
0.00
3.78
5.92
SA-MOO*
4.67
9.52
9.98
14.28
23.81
29.86
34.10
35.56
39.83
50.24
SAIF (Ours)
0.00
28.91
60.26
90.03
100.0
20.42
41.26
79.32
100.0
100.0
200
500
1000
2000
3000
200
500
1000
2000
3000
SparseFool
4.19
14.17
38.92
67.86
82.24
11.98
39.92
69.46
90.02
95.61
GreedyFool
8.78
22.55
40.52
65.07
77.25
18.77
47.70
74.65
93.41
97.21
TSAA
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.59
6.89
PGD &oo*
4.83
7.69
11.21
22.03
30.47
11.28
11.28
11.64
12.80
14.83
PGD *
0.72
4.02
7.06
12.83
13.76
0.00
0.00
0.04
0.22
6.24
SA-MOO*
4.76
9.52
10.98
15.56
17.82
18.01
18.94
SAIF (Ours)
10.21
52.40
89.02
90.00
100.0
50.04
73.09
95.00
100.0
100.0
Table 2: Quantitative evaluation of untargeted attack on Inception-v3 and ResNet50 trained on ImageNet
dataset. We report the ASR for varying constraints on sparsity 'k' and -norn of the magnitude of perturbation 'c'. Black-box attacks are marked with *
Note that sparse attacks like ours address a more challenging problem than -orm threat models since both the perturbation magnitude and sparsity are be constrained. For foo constraints =10, 100, and 255, AutoAttack (Croce & Hein 2020) achieves 100% ASR while perturbing 998% of image pixels for each c. For the same c, SAIF achieves 100% ASR with 1.12%, 0.07%, and 0.037% sparsity, respectively. Moreover, sparse altacks are more visually interpretable than foo attacks
We additionally evaluate SAIF against the One Pixel Attack (Su et al., 2019), which aims to fool classifiers by modifying only a single pixel per image. For ResNet50 trained on ImageNet, the One Pixel Attack is reported lo achieve 34.0% ASR for untargeted and 14.4% ASR for targeted settings. Despite not being specifically optimized for such an extreme sparsity regime, SAIF achieves fairly competitive 20.93% ASR in the untargeted setting and 6.04% in the targeted case, demonstrating its robustness even under highly constrained attack scenarios.
6.2 Qualitative Results.
We include some examples of targeted adversarial examples using SAIF in Figure 2 Note that the pertur- bations have been enhanced in all figures for visibility. Visually, the perturbations generated by SAIF are only slightly noticeable in regions with uniform color palette/low textural detail, such as on the beige couch (sce the zoomed-in segments of Figure 2) The other images are bereft of such regions and thus have negligible visible change. Moreover, the attack predominantly perturbs semantically meaningful pixels in the images.
For untargeted attacks, we present examples from all competing attack methods in Figure 3 the magnit ude constraint to allow all baselines to achieve some successful attacks al the same level of sparsity. Upon a closer visual inspection, it can be observed that competing methods produce significantly more conspicuous perturbations around the face of the leopard and on the outlines of the forklift and the albatross. PGD fo + lu, in particular, adds the most noticeable distortions to images. In contrast, SAIF attack produces adversarial examples that appear virtually identical to the clean input images.
We case
8

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
Ieopard
albatross
Input image
Spanseooll
GreedyFool
TSAA
PGD L +1
SA-MOO
SAIF (Ours)
Figure 3: Visual results of untargeted attack on three images for 255, k == 600. Our method produces the most imperceptible adversarial examples despite the relaxed constraint magnitude.
Attack
Loc.
SparseFool
0.006
GreedyFool
0.001
TSAA
0.006
SAIF (untargeted)
0.126
SATF (targeted)
0.118
Table 3: Quantitative evaluation of interpretability w.r.t. overlap with GT bounding boxes of ImageNet val set. We use 255, & 200 for all untargeted attacks unless indicated otherwise.
6.3 Perturbations and Interpretability
The sparse nature of perturbations allows us study the interpretability of each attack (i.c. their corre- spondence with discriminative image regions). A similar evaluation is carried out in Xu et al.) (2019), but

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
Input image
FGSM
PGD
SAIF (Ours)
Figure 4: Attacks with == 2/255 on ResNet-50. (Best viewed at higher brightness levels).
they treat the saliency maps obtained from CAM Zhou et al. 2016 as the ground truth. The saliency maps from CAM (and other existing methods) incur several failure cases. Therefore, we the ImageNet bounding box annotations
reliable baseline to analyze attack understandability.
We use ResNet50 as the target model and set == 255 and k = 2000 for all attacks. The results are reported in Table 3] SAIF achieves the highest Loc. score among competing methods in both the targeted and untargeted attack setting. Note that SAIF performs better on this metric in the untargeted attack setting versus the targeted attack. This intuitive since the untargeted objective only diminishes features of the true class. Whereas, targeted attacks introduce features to convince DNN to predict the target class.
6.4 Comparison against non-sparse methods
To demonstrate the importance of sparsity adversarial attacks, we present a quantitative and qualitative comparison against non-sparse attack methods.
Percentage of pixels perturbed: To emphasize the significance of explicit sparsity constraint for adversarial attacks, report the percentage of pixels perturbed by three non-sparse attacks against SAIF. Comprehensive results are in table 4 SAIF achieves perfect ASR by modifying 51% of pixels. The same ASR is achieved by non-sparse baselines by modifying 99% pixels for all constraints on perturbation magnitude.
FGSM
PGD
AutoAttack
SATF
255
99.28
99.87
98.85
0.04
100
99.29
99.98
98.99
0.07
10
99.28
99.98
99.93
1.12
Table 4: Percentage of pixels attacked for 100% ASR on ResNet50. the constraint on perturbation magnitude.
Visual imperceptibility: We evaluate all methods for 2/255, which an extremely low perturbation magnitude, and present the qualitative results in Figure Despite the very small c, non-sparse attacks are more noticeable than SAIF due to a lack of sparsity in the perturbations.
6.5 Speed Comparison
Table reports running times of all baselines. PGD Eo Eoo (Croce & Hein 2019 runs the fastest but produces the most noticeable perturbations. Note that, although the inference time for GreedyFool (Dong ct al. 2020) and TSAA (He et al.] 2022) is < 2 seconds, these generator-based attacks require pre-training a generalor for each larget model (as well as each and larget class for TSAA (He el al.) 2022)). This incurs a significant computational overhead (>7 days on a single GPU), which offsets their faster optimization times. SAIF attack relies solely on pre-trained classifiers, and is significantly faster than the existing statc-of-tho-ee Homotopy-Atee Attack (Zhu et al. 2021). Moreover, more efficient implementations of the FW LMO can further shorten running times, which leave for future work.
10

---

Published in Transactions on Machine Learning Research (07/2025)
Attack
Time (sec)
SparseFool
20
GreedyFool
1.7
TSAA
1.8
SAPF
1142
Homotopy-Attack
1500
PGD Enc
1.46
SA-MOO
56.07
SAIF (ours)
15
Table 5: Average running time (per image) on ImageNet
Attack Type
Dataset
ASR
Ipllo/m +
< = 255
100.0
1.0
untargeted
100
100.0
1.0
e 10
100.0
1.0
255
100.0
1.0
targeted
100
100.0
1.0
c 10
100.0
1.0
Table 6: Quantitative evaluation of optimizing SATF without a sparsity constraint for Inception-v3 on
ImageNet. For each perturbation magnitude, the attack distorts all m pixels in the image, leading to high perceptibility.
7 Ablation Studies
We perform two sets of ablative experiments to highlight. the significance of our design choices.
Attack Sparsity. To illustrate the importance of limiting the sparsity of attack using s, we reformulate the problem to one constrained only over the perturbation magnitude. That is, we use the following objective for the untargeted attack:
D(p) = +(xx + c.
(8)
max D(p)adu: s.t. ||pl Se
(9)
Similarly, we reframe the targeted attack by optimizing for the objective D(p)adv where,
D(p) 4xxx + P,t)
(10)
min D(p) s.L. || Se
(11)
This is similar to Chen et al. 2020 's attack method that uses Frank- for optimization.
Following Table 2 we test the attack for various and report the results in Table G In the absence of a sparsity constraint, the attack distorts all image pixels regardless of the constraint on magnitude. Moreover, such spatially 'contiguous' perturbations are visible even at magnitudes as low as c 10 (see Figure 4). By constraining the sparsity for SAIF attack, we ensure the adversarial perturbations stay imperceptible even al 255, which the non-sparse attack completely obfuscates the image.
Loss formulation. We also experiment with different losses, mainly the fz-attack proposed by Carlini & Wagner (2017), but observe a decline in allack success (see Table 7 we choose and k for which SAIF achieves 100% ASR in Table [). A possible explanation for this behavior that the loss formulation tries increase the target class probability too aggressively, which makes the simultancous optimization of s and p difficult. We observe that this yields solutions closer the constraint boundaries, increasing the attack visibility.
11

---

Published in Transactions on Machine Learning Research (07/202) 2025)
Input image
e-constrained attack
SAIF
butiterily & beaver plate rack > dutch oven couch > alligatoo lizard
10 (only)
C 10, k 4000
100 (only)
6=100, k=4000
255 (only)
E=255, k=600
Figure 5: Exploring the significance of sparsity of the adversarial attack. When the sparsity is not constrained
(middle column), perturbations of very small magnitude (e = 10) are noticeable and completely distort the image for larger e. On the contrary, SAIF (third column) stays imperceptible at higher magnitudes as well.
Constraints
ASR.
255, 1 600
97.78%
100, k 600
98.30%
= 10, A: = 3000
88.97%
Table 7: ASR for targeted attacks on Inception-v3 when cross-entropy is replaced with fg-attack loss (Callini
& Wagner 2017
12

---

Published in Transactions on Machine Learning Research (07 (07/2025)
8 Conclusion
In this work, we propose novel adversarial attack, 'SAIF", by jointly minimizing the magnitude and sparsity of perturbations. By constraining the attack sparsity, we not only conceal the attacks but also identify the most vulnerable pixels in natural images. We use the Frank-Wolfe algorithm to optimize our objective and achieve effective convergence, with reasonable efficiency, for large natural images. We perform comprehensive experiments against state-of-the-art attack methods and demonstrate the remarkably superior performance of SAIF under tight magnitude and sparsity budgets. Our method also outperforms existing methods on a quantitative metric for interpretability and provides transparency to visualize the vulnerabilities of DNNs.
Discussion and Ethics Statement
Adversarial attacks expose the fragility of DNNs. Our work aims demonstrate that highly imperceptible adversarial atlack can be generated for natural images. This provides new benchmark for the research community to test the robustness of the learning algorithms. A straightforward defense strategy can be using the adversarial examples generated by SAIF for adversarial training, We leave more advanced solutions for future exploration.
Morcover, in principle, SAIF can be extended to other input modalitics, with appropriate adaptations for the target domain. For example, extending SAIF to video data would require adding a temporal consistency constraint, alongside the existing sparsity and magnitude constraints, to preserve the imperceptibility of perturbations. We leave detailed exploration of these potential extensions to future work.
Acknowledgments
This project was supported by NIH/NCI grant RO1C424077..
References
Philipp Benz, Chaoning Zhang, Tooba Intiaz, and In So Kweon. Double targeted universal adversarial perturbations. In Proceedings of the Asian Conference on Computer Vision, 2020.
Mathieu Besançon, Alejandro Carderera, and Sebastian Pokutta. FrankWolfe.jl: high-performance and flexible toolbox for Frank- Wolfe algorithms and Conditional Gradients, 2021. https://arxiv.orgg/aa
2164.
Alejandro Carderera, Mathieu Besançon, and Sebastian Pokutta. Simple steps are all you need: Frank- wolfe and generalized celf-concordaat functions. Advances in Neural Information Processing Systems, 34: 139005401, 2021.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp), pp. 39-57. IEEE, 2017.
Varun Chandola, Arindam Banerjee, and Vipin Kumar. Anomaly detection: A survey. ACM computing surveys (CSUR), 41(3):1-58, 2009.
Aditya Chattopadhay, Anirban Sarkar, Prantik Howlader, and Vincoth N Balasubramanian. Grad-cam+ Generalized gradient- basdie visual explanations for deep convolutional networks. In 2018 IEEE winter conference on applications of computer vision (WACV), pp. 839 847, 2018.
Jinghui Chen, Dongruo Zhou, Jinfeng Yi, and Quanquan Gu. A frank-wolfe framework for efficient and effec- tive adversarial attacks. Proceedings of the AAAT Conference on Artificial Intelligence, 34(04):3446-34444 Apr. 2020. doi: 10.1609 11660//aaii.vo.
URL https://ojs. aaai. wwwoorrggngg.e. httg//ndx...ph/A////arrtii.eee
view/5753
François Chollet et al. Keras. https://keras http:////aaaaaa.oppppppaaaaaaaaa 2015.
13

---

Published in Transactions on Machine Learning Research (07/2025)
Francesco Croce and Matthias Hein. Sparse and imperceivable adversarial attacks. In Proceedings of the IEFE/CVP International Conference on Compuler Vision, pp. 4724-4732, 2019.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International conference on machine learning, pp. 2206-2216. PMLR, 2020.
Xiaoyi Dong, Dongdong Chen, Jianmin Bao, Chuan Qin, Lu Yuan, Weiming Zhang, Nenghai Yu, and Dong Chen. Greedyfool: iistortion-aware sparse adversarial attack. Advances in Neural Information Processing Systems, 18:11226-11236 2020.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Un- terthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021. URL pttpg:://pppuueereeeeee///rrrrrr
Yanbo Fan, Baoyuan Wu, Tuanhui Li, Yong Zhang, Mingyang Li, Zhifeng Li, and Yujiu Yang. Sparse adver- sarial attack via perturbation factorization. In Computer Vision ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXII 16, pp. 35-50. Springer, 2020.
Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic programming. Noval research logistics quarterly, 3(1-2):95-110 1956.
Yonatan Geifman. Vgg16 models for cifar-10 and cifar-100 using keras, 2019. https://github. com/
geifmany/cifar--eg
Gauthier Gidel, Fabian Pedregosa, and Simon Lacoste-Julien. Frank-wolfe splitting via augmented la-
grangian method. In Proceedings of the Twenty-Fine First International Conference Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pp. 1456-1465. PMLR, 2018. URL https://proceedingg mml.eiinnn..m.......mmmmm..m wwr.mlrreeeeeeee mlw..press/v44.. gitp//8..dllllaeee...
Ross Girshick. Fast r-cnn. In Proceedings of the IEEE international conference on computer vision, pp. 1440-1448, 2015.
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015. URL
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Tn
Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Ziwen He, Wei Wang, Jing Dong, and Tieniu Tan. Transferable sparse adversarial attack. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. -9962, 2022.
Alexey Tgnatiev, Nina Narodytska, and Joao Marques-Silva. On relating explanations and adversarial ex-
amples. Advances in neural information processing systems, 2019.
Martin Jaggi. Revisiting frank wolfe: Projection-free free sparse convex optimization. In International Conference on Machine Learning, pp. 427-435. PMTRR, 2013.
Alex Krizhevsky, llya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems, volume 25, pp. 1097-1105. Curran Associates, Inc., 2012. URL http://s/ppoeeeee...ooo///////e/ pdf
Alex Krizhevsky al. Learning multiple layers of features from tiny images. 2009.
Simon Laliste-Julien. Convergence rate of frank-wolfe for non-convex objectives. arXiv preprint arXin:1607.00345, 2016.
14

---

Published in Transactions on Machine Learning Research (07/)025)
Jan Macdonald, Mathicu E. Besançon, and Sebastian Pokutta. Interpretable neural networks with frank- wolfe: Sparse relevance maps and relevance orderings. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 14699 14716. PMLR, 2022. URL httpps://proceedings mlr. wwwpppreesssse v162/ mwcdomal d22a. h2mm.hmml
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018. URL https:://openrevier wwtp://oooommdddddillll....
Apostolos Modas, Seyed-Mohsen Moosavi-Dezffooli, and Pascal Frossard. Sparsefool: a few pixels make a big difference. In Proceedings of the IEEE/CVE conference on computer vision and pottern recognition, pp. 9087-9096, 2019.
Seyed-Mohsen Moosavi-Dezfood Alhussein Fawzi, and Pascal Frossard. Deepfool: a simple and accurate method fool deep neural networks. In Proceedings of the IEEE conference on computer vision and pottern recognition, pp. 2574-2582, 2016.
Nina Narodytska and Shiva Prasad Kasiviswanatham. Simple black- box adversarial attacks on deep neural networks. In CVPR Workshops, volume 2, pp. 2, 2017.
Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial scttings. In 2016 IEEE Europeon symposium on security and privacy (EuroS&P), pp. 372 387. IEEE, 2016.
Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi. You only look once: Unifiod, rcal-time object detection. In Proceedings of the IEEE conference on computer vision and pottern recognition, pp. 779-788, 2016.
Jay Roberts and Theodoros Tsilikkaridi.. Controllably Sparse Perturbations of Robust Classifiers for Ex- plaining Predictions and Probing Learned Concepts. In Machine Learning Methods in Visualisation for Big Data, The Eurographics Association, 2021. ISBN 978-3-03868-16655, doi: 10.2312 2t.2312mmlvis.220 mlvis.20211077
Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai. One pixel attack for fooling deep neural networks. IEEE Transactions on Evolutionary Computation, 23(5), 2019.
Christian Szegedy, Wojciech Zaremba, 1lya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of noural networks. In International Conference Learning Representations, 2014. URL
http:///rggaabssb///aaa 6199
Theodoros Tsiligkaridis and Jay Roberts. Understanding and increasing efficiency of frank-wolfe adversarial training. In Proceedings of the IEEE/CVE Conference on Compuler Vision and Pallern Recognition, pp. 50-59, 2022.
Yisen Wang, Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. On the convergence and robustness of adversarial training. In Proceedings of the 36th International Conference on Machine Learning, Proceedings of Machine Learning Research. PMLR, 2019.
Zifan Wang, Matt Fredrikson, and Anupam Datta. Robust models are more interpretable because attri- butions look normal. In Proceedings of the 39th International Conference on Machine Learning, vol- une 162 of Proceedings of Muchine Leurning Research, pp. 22625 22651. PMLR, 2022. URL https: //proceedings. mlr, pptps//162/wwaaeggeeeee wang22e. html
Phoenix Neale Williams and Ke Li. Black-box sparse adversarial attack via multi-objeclive optimisation. In Proceedings of the LEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2023.
Kaidi Xu, Sijia Liu, Pu Zhao, Pin-Yo Chen, Huan Zhang, Quanfu Fan, Deniz Erdogmmss, Yanzhi Wang, and Xue Lin. Structured adversarial attack: Towards general implementation and better interpretability. In International Conference on Learning Representations, 2019. URL http://pppaarviioooeee/oooooooo net/formm?dd BkgzniCqY7
15

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Bolci Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba. Learning deep features for discriminative localization. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 2921 2929, 2016.
Mingkang Zhu, Tianlong Chen, and Zhangyang Wang. Sparse and imperceptible adversarial attack via a homotopy algorithm. In IOML. PMLR, 2021.
Appendix
A
Frank Wolfe Algorithm
The Frank-Woon Wolfe algorithm (FW) Frank et al., 1956 is first-order, projection-free algorithm for optimizing a convex function f(x) over a conveX set X (Algorithm 2
The set. X may be described as the convex hull of a (possibly infinite) set of atoms A. In the case of the ball (X exe R" ||x||| S r),, these atoms may be chosen the 2n unit vectors, i.c., A {+ez. j = 1 I...n..
Algorithm 2: Frank- Wolfe Algorithm
Input: Objective f. convex set N, Maximum iterations T, stepsize rule Output: Final iterate Xxr
Xo
for t O do
a, = arg min (V[(x,),a)
Xt+1 Xt + (at xt)
end
FW projection-free method since it solves a linear approximation of the objective over X (see step 3 in Algorithm 2), known the Linear Minimization Oracle (LMO). For convex optimization, the optimality gap f(x)) f(x") is upper bounded by the duality gap g(x,) min.e (Vx())) a), which measures the instantaneous expected decrease in the objective and converges at sub-linear rate of (1/TT) for Algorithm (Jaggi 2013). FW can locally solve non-convex objectives over convex regions with O(IvVT) convergence
Lacoste- Julien 2016
B Results on Vision Transformers
We also evaluate SAIF and GreedyFool (the best performing//eesooabbl efficient baseline) on pre-trained ViT-B/16 (Dosovitskiy al. 2021 (see Table 8). Although GreedyFool performs similarly, SAIF produces more visually imperceptible perturbations.
Sparsity 9
Attack
100
200
600
1000
2000
GreudyFool [11]
5.7
29.1
87.4
99.2
99.8
255
SAIF
28.3
54.4
89.4
93.5
100.0
CroodyFool [11]
1.7
14.3
54.5
82.0
100
SAIF
4.5
26.7
76.8
80.7
100.0
1000
2000
3000
4000
5000
GreedyFool [11]
25.34
66.7
83.2
91.8
95.7
10
SAIF
2.9
22.4
34.9
42.0
52.3
Table Targeted ASR (higher is better) on ViT-B/16 (Imagenet).
16

---

Published in Transactions on Machine Learning Research (07 (07/202) /025)
Psl
Pi2
X
Pul
Pt2
conure: 99.9%
airship: 96.2%
howler monkey: 99.9%
horse: 91.7%
airship: 99.7%
tabby cat: 99.9%
tiger cat: 99.6%
pickup: 99.9%
husky: 90.9%
husky: 90.9%
banjo: 89.5%
tabby cat: 99.9%
Figure 6: Impact of choice of target class adversarial perturbations. We run targeted attacks for two target classes (t1 and t²) for each input. The perturbations enhanced for visualization.
C Results on additional dataset
For comprehensive evaluation of our attacks, also test our approach on a smaller dataset:
C.1 Dataset and model
We test SAIF and the existing sparse attack algorithms on the CIFAR-10 dataset (Krizhevsky et al., 2009) The dataset comprises [32 32] RGB images belonging 10 classes. We evaluate all algorithms on 10,000 samples from the Lest. set.
We attack VGG-16 (Geifman 2019 trained CIFAR-10, having accuracy of 92.32% clean images.
C.2 Quantitative Results
We run all attacks for range of and k, and report the results in Tables 10
The ASR for unlargeted attack is reported in Table g SAIF consistently outperforms SparseFool (Modas et al. 2019) and GreedyFool (Dong et al.) 2020) on all sparsity and magnitude constraints. Similar results
are obtained for targeted attacks, reported in Table 10 The target classes are randomly chosen in all
experiments.
C.3 Qualitative Results
We provide several examples of adversarial examples produced by SAIF and competing algorithms. Figure shows samples obtained by untargeted attacks on VGG-16 trained on CIFAR-10. Tt observed that SAIF consistently produces the most imperceptible perturbations.
Visual interpretability of SAIF
From visual inspection (see Figure 6 it is observed that the nature of the target class also determines the sparse distortion pattern. Tn particular, attacking input images of an animate class towards another animate class (t2) results in perturbations focused predominantly on the facial region in the image. The reverse is observed when attacking animate towards inanimate object classes (41), which typically modify the body of the subject in the image.
17

---

Published in Transactions on Machine Learning Research (07 (07/2025)
airplane
automobile
bird
deer
dog
frog
horse
ship
Thrtt
Thrt
Them
Thrit
truck
Input
SpanseFool
GreedyFool
SAIF (Ours)
Input
Spanseooo
GreedyFool
SAIF (Ours)
Figure 7: Untargeted adversarial examples obtained from SAIF and competing attack algorithms on CIFAR-
10. The attacked classifier is VGG-16
18

---

Published in Transactions on Machine Learning Research (07 (07/2025)
VGG-16
Attacks
Sparsity "
2
5
10
20
SparseFool
10.78
18.56
38.32
63.67
85.23
255
CroodyFool
0.00
0.00
24.75
69.26
85.83
SAIF (Ours)
91.20
92.87
94.46
96.35
100.0
5
10
15
20
30
SparseFool
30.54
51.50
65.47
74.45
86.43
Gool
25.95
55.09
67.26
73.65
86.43
SAIF (Ours)
91.89
92.84
93.57
96.74
97.80
30
40
50
60
100
SparseFool
19.36
24.75
27.94
31.94
44.51
6 10
Fool
33.93
39.92
45.91
51.10
66.27
SAIF (Ours)
90.32
91.57
92.14
92.65
94.14
Table 9: Quantitative evaluation of untargeted attack on CIFAR-10. constraints sparsity 'k' and lo -orm of the magnitude of perturbation 'e'.
We report the ASR for varying
VGG-16
|| I
Attacks
Sparsity '
2
5
10
20
Gool
0.00
0.00
2.79
13.17
29.94
255
SAIP (Ours)
12.36
12.83
27.02
44.05
61.10
5
10
15
20
30
GreedyFool
2.20
9.58
14.97
16.97
30.74
100
SAIF (Ours)
13.37
21.03
26.27
36.18
51.43
30
40
50
60
100
GreedyFool
3.99
5.19
6.99
8.98
16.17
= 10
SAIF (Ours)
5.46
13.35
18.13
22.25
29.26
Table 10: Quantitative evaluation targeted attack on CIFAR-10. straints on sparsity 'k' and -nom of the magnitude of perturbation 'e'.
We report the ASR for varying con-
19


Reviews:
[{"review_id": "L1tne3Vypi", "reviewer": "Reviewer_QsS6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Important problem \n2. A novel interesting sparse attack is proposed\n3. A rather thorough experimental comparison, which also includes qualitative results & efficiency results.\n4. The paper is generally well written.\n\nWeaknesses\n1. The paper's clarity (description of algorithms) can be improved.\n2. It is not clear why authors do not compare to L_0 + sigma-map\n3. Imperceptibility claims are anecdotal", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper adapts a Frank-Wolfe algorithm to generate a new type of sparse attacks. This is a very interesting topic because sparse attacks can be fairly unconstraint in the pixel modification magnitude yet relatively imperceptible. The new attack variant outperforms baselines in terms of success rate (at a given level of sparsity) while being reasonably efficient. It is 10x slower compared to PGD L_0 + L_inf, which is an acceptable trade off. At the same time it is 3x times faster compared to the next-best sparse attack SA-MOO.\n\nThe paper is generally well written and I enjoyed it. However, there are a couple of issues. First, it can benefit from a more self-contained description of the algorithm (see some suggested changes). Second, it compares to the L_0 + L_inf attack by Croce & Hein (2019), but not to the improved variant L_0 + sigma-map that the paper also proposes. It is not clear why this baseline is omitted.\n\nFinally, I think one has to be careful in making imperceptible claims when large pixel distortions are allowed. In particular, Croce & Hein provide an example of a picture with only 0.4% of pixels changed where results are quite visible. I am not a fan of imperceptibility claims based on just a couple of anecdotal examples. Sometimes, you can get lucky with changes from one similar color to another and sometimes you can get a few black pixels turning black. I understand this has been a system problem in the literature (including the paper of Croce & Hein), but I still find this practice problematic. I would **not** suggest carrying out human evaluations for this specific revision. However, I think this would be necessary for making strong imperceptibility claims. \n\nSo, maybe, adding a small disclaimer in regard to this issue would be helpful. Moreover, I would recommend against using terms such as  **strongly** imperceptible.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Comparison to baselines:\n\nL_0 + sigma-map\n\nEditorial changes:\n\np3.  demonstrates a hitting set duality between model explanations and adversarial examples. -> please rephrase, it's unclear what a hitting set is.\np3. Given an image x ∈ R^h×w×c , a trained classifier f : R^h×w×c −→ {1 . . . k} -> seems like it should be R^{h \\times w}, i.e., without c. I encounter the same notation issue in other places, including but not limited to equations (2) and (4).\n\np3. We adopt the white-box setting in this work, however, gradient approximations (Chen et al., 2020) can be used for black-box attacks. -> It's a bit unclear what you mean here. If you want to say that your methods can be extended to a black-box case, it's likely some overpromising, because gradient approximations are expensive and inaccurate. Whether the method works well `in this case is an empirical question you do not answer.\n\np4. I \n\np4. Is \"iterate\" a widely adopted term?\n\np5. top of the page: did you define z_t and m_t before?\n\np5. Since the objective of SAIF is non-convex, a monotonicity guarantee is helpful to ensure that the separate optimizations of each variable sync well. -> this seems to be unclear (not understandable without context). This comment applies to most of the method's description on this page.\n\nEquation (5): Where do we incorporate constraint on k?\n\n\nTable 1 and others: please, clarify that epsilon is normalized by 255.\n\n\np8: It can be observed that all competing methods produce highly conspicuous perturbations around the face of the leopard and on the outlines of the forklift and the albatross -> Honestly, it was very difficult for me to judge. I am not sure if these are more or less conspicuous except for the albatross picture and  PGD ℓ∞ + ℓ0. I think you may need to frame this statement a bit more cautiously (unless you want to carry out a human study where you randomly show two images and ask humans which one has more visible perturbations).\n\n\np8. Where does  PGD ℓ∞ + ℓ0 is described? Why do you use it as a speed, but not a quality baseline?\n\nAlgorithm 1 : It does NOT seem to use constraint k, but it should I guess.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "mlKt14VRnO", "reviewer": "Reviewer_2vD8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- This manuscript jointly consider attacks with high sparsity and low magnitude perturbations.\n- The Frank-Wolfe algorithm (FW) is used to find perturbations well within the constraint boundaries.\n\n Weaknesses\n- The paper suffers from limited technical novelty.  Previous works have explored how to jointly consider attacks with high sparsity and low magnitude perturbations, e.g., [1,2,3].\n\n[1] Williams P N, Li K. Black-box sparse adversarial attack via multi-objective optimisation[C]//Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023: 12291-12301.\n\n[2] Gao Y, Li Y, Gong X, et al. Backdoor attack with sparse and invisible trigger[J]. IEEE Transactions on Information Forensics and Security, 2024.\n\n[3] Sadiku S, Wagner M, Pokutta S. GSE: Group-wise Sparse and Explainable Adversarial Attacks[C]//The Thirteenth International Conference on Learning Representations. 2025.\n- The SAIF algorithm lacks the convergence guarantee. The paper claim a $\\mathcal{O}(1/\\sqrt{T})$ convergence rate, while I have not seen the theoretical result analysis.\n- Proposed method are limited in back box attacks, which are popular in practice.\n- Although the authors emphasize that sparsity brings a certain degree of interpretability, the consistency between the perturbation and the “semantic regions” is not always significant. \n- The improvement in the evaluation metric Loc. is significant, but the absolute value remains low. (Table 3)\n- SAIF assumes that every pixel can be attacked, but in practice, some model inputs (such as medical images) may only allow perturbations in specific regions. It should consider spatial constraint / patch constraint for practical problems.\n- Table 7 shows a significant decrease in performance when using the L2 attack loss, indicating that the method is sensitive to the choice of loss function.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a novel sparse attacks method that produces low-magnitude perturbations and high sparsity. The Frank-Wolfe algorithm is used to optimize the proposed objective and achieve effective convergence for large natural images. Empirical results seem to demonstrate the effectiveness of proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The optimization objective of SAIF is non-convex. Although the paper has experimentally validated the effectiveness of the algorithm, the discussion on the theoretical convergence and optimality guarantees of the algorithm is relatively limited. \n-The paper does not provide a detailed discussion on how the selection of hyperparameters (such as the maximum number of iterations T, step size rules,  initialization, etc.) affects the attack performance. These hyperparameters may need to be carefully tuned in practical applications.\n- Insufficient Experimental Results. It is suggested to add a set of cross-model transfer attack experiments to evaluate its generalizability. The effectiveness test of SAIF is limited to vanilla models. There is no test on its performance on defensive models (such as adversarial training).\n- Whether SAIF is still effective remains unknown. Sparse perturbations may be ineffective for text alignment models, or may be easily “corrected” by text conditions.  It is suggested to add  a set of attack experiments for attacking vision-language models.", "broader_impact_concerns": "In my own opinion, there is no ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Uv8FqhVQXo", "reviewer": "Reviewer_boMK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The focus on sparse adversarial perturbations is a realistic scenario. Proposed attack formulation is intuitive and well described.\n\n- Empirical attack evaluations to demonstrate the efficacy of optimization are thorough and well executed. The evaluation metrics and the handling of baseline methods are described in sufficient detail.\n\n- Another interesting contribution of this attack algorithm is that the optimized perturbations are also somewhat interpretable.\n\n- The solid foundation of the proposed approach is also experimentally well-supported, as the attack is shown to be effective in several settings.\n\nWeaknesses: I do not see any weaknesses that contradicts the support of the claims and evidence provided in the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a novel optimization-based adversarial attack, annotated as sparse adversarial and imperceptible attack framework. Specifically, the adversary aims to obtain spatially highly sparse adversarial perturbations (i.e., only effecting a few pixels), via joint optimization of the attack perturbations with bounded magnitude and sparsity constraints, using the Frank-Wolfe algorithm as the solver. This multi-constrained optimization objective can also be solved in shorter time by an adversary, in comparison to several other existing sparse attack variants. Experiments are conducted on image classification benchmarks (e.g., ImageNet) with various architectures.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Did the authors explore how much SAIF can contribute to the AutoAttack benchmark in terms of additional adversarial power? In other words: What is the percentage of the test samples that can be additionally misclassified with SAIF, which were not misclassified via the AutoAttack ensemble?\n\n- Given the visual interpretability aspect of the attack, can we also empirically argue black-box transferability of the optimized adversarial perturbations as well? Did the authors explore this aspect? Note that this is one missing argumentation against TSAA, which can demonstrate high black-box transferability.\n\n- Considering the experimental focus with comparisons to sparsity-centric attacks, it would be interesting to see how does SAIF compare against the One-Pixel attack [Su et al., 2019] as well?\n\n- Could the authors elaborate on whether this optimization approach can be applied to tasks beyond image classification?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)