Understanding and Improving Fast Adversarial Training against $l_0$ Bounded Perturbations
Authors: Xuyang Zhong
Yixiao Huang
Chen Liu
Venue: NeurIPS 2025 poster ()
Keywords: adversarial robustness
adversarial training
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: This work studies fast adversarial training against sparse adversarial perturbations bounded by $l_0$ norm. We first demonstrate the unique challenges of employing $1$-step attacks on $l_0$ bounded perturbations, especially catastrophic overfitting (CO) that cannnot be properly addressed by existing fast adversarial training method for other $l_p$ norms ($p \geq 1$). We highlight that CO in $l_0$ adversarial training arises from sub-optimal perturbation locations of $1$-step attack. Some strategies like multi-$\epsilon$ can mitigate this sub-optimality to some extent, they lead to unstable training in turn. Theoretical and numerical analyses also reveal that the loss landscape of $l_0$ adversarial training is more craggy than its $l_\infty$, $l_2$ and $l_1$ counterparts, which exaggerates CO. To address this issue, we adopt soft labels and the trade-off loss function to smooth the adversarial loss landscape. Extensive experiments demonstrate our method can overcome the challenge of CO, achieve state-of-the-art performance, and narrow the performance gap between $1$-step and multi-step adversarial training against sparse attacks.

Understanding and Improving Fast Adversarial Training against to Bounded Perturbations
Xuyang Zhong
Yixiao Huang
Department of Computer Science City University of Hong Kong xuyang- zhong@my city.. edu hk
Department of Computer Science
City University of Hong Kong yixiao. huang@my ci cityu. edu hk
Chen Liu
Department of Computer Science City University of Hong Kong chen. liuuciiityi tyu. edu. hk
Abstract
This work studies fast adversarial training against sparse adversarial perturbations bounded by lo norm. We first demonstrate the unique challenges of employing 1-step attacks on lo bounded perturbations, especially catastrophic overfitting (CO) that cannnot be properly addressed by existing fast adversarial training method for other lp norms (p 2 1). We highlight that CO in lo adversarial training arises from sub-optimal perturbation locations of 1-step attack. Some strategies like multi-e can mitigate this sub-optimality to some extent, they lead unstable training in turn. Theoretical and numerical analyses also reveal that the loss landscape of lo adversarial training is more craggy than its loc. la and l counterparts, which exaggerates CO. To address this issue, we adopt soft labels and the trade-off loss function to smooth the adversarial loss landscape. Extensive experiments demonstrate our method can overcome the challenge of CO, achieve sate--of-theaat performance, and narrow the performance gap between 1-step and multi- step adversarial training against sparse attacks. Codes are available
Introduction
Deep neural networks have been shown vulnerable adversarial perturbations [1. To achieve robust models, comprehensive evaluations 22] 3 4 have demonstrated that adversarial training (5) and its variants (6
& 9 10 I1 12] the most effective methods. However, adversarial training is generally computationally expensive because generating adversarial perturbations in each training step needs multiple forward and backward passes of the model. Such efficiency issues hinder the scalability of adversarial training.
employ faster but weaker 1-step attacks to generate adversarial perturbations for training. However, such methods may suffer from catastrophic overfitting (CO) (17): the model overfits these weak attacks instead of achieving true robustness against adaptive and stronger attacks. On the other hand, most existing works [5] g [9] focus studying adversarial perturbations bounded by loc. la li norms. In these scenarios, the set of allowable perturbations is convex, which facilitates optimizing adversarial perturbations and thus adversarial training. However, there many scenarios in real-
Improving the efficiency of adversarial training is tricky. Some works 13
14
15
16
"Coreepooning Author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table I: Robust accuracy of SAT and STRADES 23 with different steps (t) evaluated by Sparse-
AutoAttack (sAA) 23 where the sparsity level is 20. The models are PreactResNet-11 24
trained on CIFAR- 10
25
SAT (t = 1) SAT (t= 20)
sTRADES (t (t= 1) sTRADES (t = 20)
Robust Acc.
0.0
36.2
31.0
61.7
world applications where sparse perturbations, bounded by the lo norm, need to be considered 200 21 22 23). Since the lo norm is not a proper norm, the set of all allowable perturbations in this case is not convex. Consequently, from optimization perspective, obtaining robust models against sparse perturbations becomes more challenging. Compared with the lec l2 and 2 counterparts, more steps are needed generate strong lo bounded perturbations, making the corresponding adversarial training even more computationally expensive.
Among algorithms aiming at obtaining robust models against sparse perturbations, SAT and STRADES [23] stand out as the most effective ones. These methods employ adversarial train- ing against Sparse-PGD (sPGD) (23). However, they still require 20 steps to generate adversarial perturbations in each training step to achieve decent performance. As demonstrated in Table [ naively decreasing the number of steps to leads to a significant performance decline for both SAT
and STRADES.
In this work, we investigate the challenges associated with fast adversarial training against sparse perturbations, including training instability caused by CO and performance decline in both robust and clean accuracy. Specifically, we highlight that CO in lo adversarial training is caused by sub-optimal perturbation locations of 1-step attack. Our observation indicates that adjusting the perturbation magnitudes alone cannot help mitigate CO in this context, many existing CO mitigation methods [26 (7 28 29 used in other cases do not work at all in the lo scenario. Although the multi-c
strategy 19 23 can mitigate sub-optimal perturbation locations, it suffers from unstable training and degraded clean accuracy. In light of these findings, we present empirical and theoretical evidence to illustrate that the loss landscape of adversarial training against lo bounded perturbations is markedly more craggy compared to its loc. 12, and / counterparts. Furthermore, we corroborate that the craggy loss landscape aggravates CO in to adversarial training.
Drawing from these insights, we adopt soft labels and a trade-off loss function to enhance the smoothness of the adversarial loss objective function, thereby improving the performance of fast adversarial training against sparse perturbations. Although similar smoothing techniques have been applied in adversarial training [30 31 32 33). existing literature employs them address robust overfitting to boost performance in l2 and (.0 cases. By contrast, we demonstrate that it is essential and has much larger performance improvement in the case of fast adversarial training. Finally, our extensive experiments demonstrate that smoothing the loss landscape can eliminate CO in the lo case, and significantly narrow the performance gap between 1-step adversarial training and its multi-step counterparts.
To the best of our knowledge, this work is the first to investigate fast adversarial training in the context of lo bounded perturbations. We summarize the contributions of this paper as follows:
We highlight that catastrophic overfitting (CO) in fast ln adversarial training arises from sub- optimal perturbation locations in 1-step attacks. Techniques effective in loc. 42, and l cases cannot fully address the CO issue in the lu case.
2. Our theoretical and empirical analysis shows that the adversarial loss landscape is more craggy in lo cases, exacerbating CO. In this regard, we can adopt soft labels and the trade-off loss function provably smooth the adversarial loss landscape.
3. Comprehensive experiments demonstrate that smoothing the loss function significantly narrows the performance gap between 1-step lo adversarial training and its multi sulti-step counterparts, achieving ofate-of-the-ane performance in efficient adversarial training against sparse perturbations.
Notation and Terminology Consider a classification model F(xr, 0) = (Jr 0) where E Rd is the input, 0 represents the parameters of the model, and K is the number of classes, fa 0) is the logit of the i-th class. Correspondingly, we use { K-1 to represent the output probability of each class, which is the result of softmax function applied to [f.)--) Therefore, the

---

loss objective function L based on the cross-entropy is calculated as follows:
K
K 1
exp(fa(x; 0))
C( 0)
Ys log hy (x, 0)
Ys log
(1)
EK-1 j=u (x,
==0
==
where y = Vuu. yc]
] is the label of x in a simplex, i... Σg y: = 1. In the context of adversarial perturbation, we use s(²) (x:) {ōll|01p S c.0 x + 1) to represent the adversarial budget, Le., the set of all allowable input perturbations for the input æ. The adversarial loss function is c! (a: 0) def max (
(a) L(x + 5, 0). Despite no guarantee to obtain the optimal perturbation in
practice, simplify the notation, denote the term c(P) also the adversarial loss induced by the actual attack algorithms and omit the superscript (p) when there is no ambiguity.
Related Works
The existence of adversarial examples is first identified in M. which focuses on norm-bounded adversarial perturbations. Fast gradient sign method (FGSM) 34 introduces an efficient approach by generating perturbations bounded by its (o norm in a single step. Furthermore, projected gradient descent (PGD) [5] extends and improves FGSM [35] by iterative updating and random initialization. In addition to these white-box attacks where the attackers have full access to the models, there are also several black-box attacks [36] 37] where the attackers' access is restricted. AutoAttack (AA) [3] is an ensemble of both white-box and black-box attacks to ensure a more reliable evaluation of model's 's robustness.
Adversarial Attacks:
12 has emerged as a popular and reliable framework to obtain robust models 2 Under this framework, we first generate adversarial examples and update model parameters based on these examples in each mini-batch update. Different adversarial training variants, such TRADES (3) and MART (32), may have different loss objective functions for generating adversarial examples and updating model parameters. Furthermore, compared with training on clean inputs, adversarial training is shown to suffer more from overfitting [38 399] In this regard, self-adaptive training (SAT) [40), which utilizes historical predictions as the soft label, has demonstrated its efficacy in improving the generalization.
Adversarial Training: Adversarial training 6 6
Sparse Perturbations: Adversarial budget defined by l norm is the tightest convex hull of the one defined by 4o norm. In this context, SLIDE [8] extends PGD and employs k-coordinate ascent to generate 4 bounded perturbations. Similarly, AutoAttack-li (AA-li) [4] extends AA to the 4 case. However, AA-I, is found generate non-sparse perturbations that SLIDE fails discover [I9), indicating that I bounded perturbations are not necessarily sparse. Therefore, we use In norm to strictly enforce sparsity. It is challenging to optimize over an adversarial budget defined by to norm, because of non-convex adversarial budgets. While naively applying PGD in this case turns out sub-optimal, there are several black-box attacks, including CornerSearch [21] and Sparse-RS (22). and white-box attacks, including Sparse Adversarial and Interpretable Attack Framework (SAIF) 42 and Sparse-PGDD (sPGD) 23 which address the optimization challenge of finding to bounded perturbations. Ultimately, Sparse- Autsse-AutAAttaa (sAA) 23). combining the most potent white-box and black-box box attacks, emerges as the most powerful sparse attack.
While effective, adversarial training is time-consuming due to the use of multi-step attacks. To reduce the computational overhead, some studies [ 14 employ faster one-step attacks in adversarial training. However, the training based on these weaker attacks may suffer from catastrophic overfitting (CO) [17]. where the model overfits to these weak attacks instead of achieving true robustness against a variety of attacks, CO is shown to arise from distorted decision boundary caused by sub- sub-optimal perturbation magnitudes (26] There are several methods proposed to mitigate CO, including aligning the gradients of clean and adversarial samples (27, adding stronger noise to clean sample [43] adaptive step size (29, regularizing abnormal adversarial samples [44], adding layer-wise weight perturbations [45. and penalizing logits discrepancy [31] Furthermore, compared to its la and Im counterparts, CO is caused by overfitting to sparse perturbations during I adversarial training [9). To address this issue, Fast-EG-l,, [19 is introduced to generate 1 bounded perturbations by Fuclidean geometry instead of coordinate ascent. this work, we investigate fast adversarial training against io bounded perturbations.
Fast Adversarial Training:
3

---

Unique Challenges in Fast to Adversarial Training
To obtain robust models against sparse perturbations, preliminary efforts use 20-step sPGD in adversarial training, which introduces significant computational overhead. To accelerate training, we explore using 1-step sPGD in adversarial training. However, as reported in Table[]] the models obtained in this way exhibit weak robustness against stronger sparse attacks, such as SAA. In this section, we study the underlying factors that make fast lo adversarial training challenging.
3.1
Catastrophic Overfitting in lo Adversarial Training
100
Alsan,Ac,
Clean Acc.
80
Robusd
80
80-
Rotue Aet.
Accuracy
Accuracy
Accuracy
Thean Ace.
40
40
Robust Arc.
40
0-
20
40
60
100
Epoch
Epoch
(a) Ctraan 20
(b) Ctraan = 40
(c) Ctrain = 120
The learning curves of adversarial training against 1-step sPGD with random noise initialization. The models are PreactResNet-13 trained on CIFAR-10. The dashed and the solid lines represent the accuracy of the training and the test set, respectively. The test robust accuracy is based on sAA with e = 20. The values e used in training are shown as Etroins the training robust accuracy based on the 1-step sPGD with Crrain-
Figure 1:
We plot the learning curves of adversarial training using 1-step sPGD in Figure Specifically, we adopt the multi-e strategy [19 23 and allow for different adversarial budget sizes, i.e., e. during training and testing. The results in Figure I iiniicate that CO happens in all configurations. Moreover, our observations CO in lo cases are different from other cases in several aspects. First, random initialization of adversarial perturbation, proven effective in I 12 and l cases, does not yield similar results in the lu case. In addition, Figure T showcases that the training accuracy on the inputs perturbed by 1-step sPGD is even higher than their clean counterparts. What's more, when CO happens in lox. 1z and 1 cases, the model sharply achieves perfect robustness against 1-step attacks but zero robustness against multi-step attacks, both in few mini-batch updates. Such phenomenon not observed in ln cases. By contrast, we observe dramatic performance fluctuations on clean examples throughout the training process, indicates a non-smooth landscape of the loss function in the parameter space: a subtle change in parameters 0 leads abrupt fluctuation in the loss.
in the fine- fine-tuning phase. Such training instability
Moreover, we apply existing CO mitigation methods (ATTA 28 Free-Al AT 13 GradAlign (GA) 277, Fast-BAT [46). FLC Pool [47). N-AAER (44), N-LAP 45 and NuAT [66), which effective in lxc and l2 cases, fast lo adversarial training. As shown Table most methods designed for other 4, norms (p > 1) turn out ineffective at all in the 4 scenario. Although NuAT achieves non-trivial performance, there is still significant performance gap to multi-step methods. Therefore, it is imperative ascertain more essential causes of CO in fast lo adversarial training and formulate effective mitigation strategies accordingly.
Table 2: Comparison between existing CO mitigation methods and multi-step method (STRADES) in robust accuracy (%) by sAA. The target sparsity level 20. We compare PreAct ResNet- 18 24 models trained on CIFAR- 10 25). The italic numbers indicate catastrophic overfitting (CO) happens. Note that all baselines are tuned by a thorough hyperparameter search.
FLC
Method
ATTA
Free-AT
GA
Fast-BAT
N-AAER
N-LAP
NuAT
STRADES
Pool
Robust Acc.
0.0
8.9
0.0
14.1
0.0
0.1
0.0
51.9
61.7

---

Table 3: Robust accuracy of the models obtained by 1-step SAT with different Etrain against the interpolation between perturbations generated by 1-step sPGD = 20) and their corresponding clean examples, where a denotes the interpolation factor, i.e. Zinterp = a + a 8. The results of sAA are also reported.
0.0
0.2
0.4
Etrain 20
77.5
69.1
80.4
88.0
6train -0
70.2
64.3
79.8
87.4
89.6
89.6
0.0
120
32.5
24.5
41.5
65.2
72.8
67.6
0.0
3.2 Unique Cause of CO in Adversarial Training: Sub-optimal Perturbation Location
In Io and l2 cases, CO occurs due to distorted decision boundary caused by sub-optimal perturbation magnitude [26]. To ascertain if this applies to adversarial training, we evaluate the robustness accuracy of models trained by 1-step SAT with varying étraán against interpolations between the clean inputs and the perturbed ones by 1-step sPGD. Table TableBishove shows that cannot find successful adversarial examples through such simple interpolations.
By contrast, we notice that the adversarial perturbations generated by 1-step sPGD during training are almost completely different from those generated by sAA in location rather than magnitude (see in Figure 2(a) Combining with the results in Table 3 we can demonstrate that CO in to adversarial training is primarily due to sub-optimal perturbation locations rather than magnitudes.
Due to non-convyxity and unique project operator to lo adversarial budget, most existing methods designed for le lo cases do not help improve the perturbation locations. Instead, we study multi-c strategy, which is particularly effective in multi-step lo adversarial training [23]. Figure 2(b) indicates that the perturbations generated by 1ssee attack with larger étrain overlap more with those generated by sAA with a smaller and fixed étest in terms of location. These findings suggest that the sub- optimal location issue brought by 1-step attacks can be mitigated some extent by multi- strategy. However, as illustrated in Figure I, larger Etroins in turn, leads to unstable training and degraded clean accuracy. To address this challenge, we investigate the loss landscape in the subsequent sections.
Eyae 80
Fooas 80
Coux
0.4
Rusas
Probabiity
0.3
Probability
0.3
0.2
0.2
1.75
1.80
1.05
1.90
1.95
2.00
0.0
0.1
0.2
0.3
0.4
0.5
[|Oraa Beaello
[|emse Swello
(a) Location Difference
(b) Location Overlapping
Figure 2: Visualization of location difference and location overlapping. (a) The distribution of the normalized lu distance between training adversarial examples generated by 1-step sPGD and sAA. The models trained on 20-step SAT with different training are evaluated. (b) The distribution the location overlapping rate between the perturbations generated by attacks used in training (20-step sPGD) and test (sAA), where Exett = 20. The models trained on 20-step sAT with different training é evaluated.
4 Fast lo Adversarial Training Requires Loss Smoothing
In this section, we investigate the landscape of adversarial loss through theoretical analyses and numerical experiments. Ultimately, we provide our solution to stabilize and improve the performance of fast adversarial training.
5

---

4.1 Theoretical Analysis
We first provide theoretical analyses on the smoothness of adversarial loss function. Similar to we assume the first-order smoothness of the model's 's outputs (fk-K-1
48
Assumption 4.1. (First-order Lipschitz condition) vi E {0, I,.., K - 1}, the function fi satisfies the following first-order Lipschitz conditions, with constants Lg. Læ:
Væ, 01. O2. [[, 01) fi 02) - Lol 02l
(2)
v0, 1 22 (2 0) [z 0) v T | 22
(3)
We then study the first-order smoothness of the adversarial loss objective function L, (zc, 0).
Theorem 4.2. (Lipschitz continuity of adversarial loss) If Assumption 4.1 holds. we have:
Vx, 01, 02, (zx 01) (x, 02) AAll0 B2ll.
(4)
The constant Ag = 2 Ess.. Lo where S+ = ii yi 2 0, h:(a + 51, 02) > h(( + 81, 01)}.
81 E arg maxses, f(x + 8, 0) and 02 mrg C(x + 6, 0).
The proof is deferred to Appendix B.1 in which we can see the upper bound in Theorem 4.2 is tight.
Theorem 4.2 indicates that the adversarial loss (x, 0) is Lipschitz continuous, consistent with [48
To study the second-order smoothness of L. (2, 0). we start with the following assumption.
Assumption 4.3. (Second-order Lipschitz condition) Vi E 10.1.... K - 1}, the function fa satisfies the following second-order Lipschitz conditions, with constants Loo, Loz:
Va, θ,, 02,
(z, 0 - Vafi 02)1 & Lool - 021l
(5)
v0, x x2, [ofi(z 0) Vefi(x2, 0) S Lex [x - x22l
(6)
Theorem 4.4. (Lipschitz smoothness of adversarial loss) If Assumption 4.7 and 4.3 hold, we have;
Va, 01, IVVoL, 01) - VoL. (xx, 02) < Aoal 00 02 + Bos
(7)
The constants Agø = Leo and Bas = Loa |6 821l 4e where d E arg max C(x + 8, 01) and 82 E arg maxges, L(x + 8, 02).
The proof is deferred to Appendix B. Theorem 4.4 indicates the adversarial loss objective function (a. 0) w.r.t. the model parameter 0 is no smooth That to say, gradients arbitrarily small neighborhoods in the f-space can change discontinuously. Furthermore. the degree of discontinuity is indicated by the value of Bes Lo 81 -821 + 4Lg. so a larger 88 52ll can intensify the gradient discontinuity. Additionally, in adversarial training. A large Bos introduces large gradient magnitudes asymptotically, making optimization challenging.
smooth.
elucidated by Theorem 2 in [88) the gradients
In practice, we may use non non-smooee smooth activations, like ReLU, which do not strictly satisfy Assumption 4.3 For example, the gradient of ReLU changes abruptly in the neighborhood around O. In this regard, we provide a more detailed analysis of this case in Appendix [D] which suggests that our analyses can be straightforwardly extended to networks with non-smooth activations.
Without the loss of generality, the Lipschitz properties Assumption 4.1 and 4.3 can be based on any proper 4p norm, i.c., E [1, +oo), which, however, does not include to norm. Correspondingly, 82 in the expression of Bos based on the same norm as the assumptions. On the popular benchmark CIFAR-10, the commonly used values of c in the lg. I, l and lo cases are 360 24, 0.5 and 8 8/255, respectively 19 23). In Appendix we discuss the numerical upper bound of |8 - 8z when the Lipschitz assumptions are based on different proper norms. The results demonstrate that the upper bound of |6, - 8211 in the lo case always significantly larger than other cases, indicating more craggy adversarial loss function in la adversarial training. Moreover, to corroborate the Lipschitz smoothness assumption Inequality ( we compare the distances between the gradients induced by one-step and multi-step attacks in Appendix F2

---

1.0
Oran
10a
0.8
Fman
0.6
:20
value
10
10a
20
-0.4
0.00
Index
Index
0.22
6.24
(a) Figenvalues of VoL
(b) Figenvalues of ViLC
(c) Le Ctrain
222
20
25
20
9
10
675
155
16
35
677
10
358
0.00
-0.4
0.00
-061
0.00
02
0,33
2
0.c-2.04
12
-300
(d) (( Ctrain 24
Ctrain 0.5
(I)
Ctrain 8/255
Figure 3: Smoothness of adversarial loss objective functions. All losses are calculated on the training 18. The lo. 4. le and loo models are obtained by 1-step sAT 23 Fast-EG-Iy [9). 1-step PGD [3 and GradAlign (37 respectively. (a) Top eigenvalues of
set of CIFAR-10 by PreactResNet-11
vici (x.0) 0) with different values of Étrain in the to case. (b) Top 10 eigenvalues of V2 v. (x. 0) under different choices p. including 1, and oc. The y-axis is shown on a log scale. (c) - (f) The
c(P)
loss landscape of Ce 0 + 01 + (222)) where and U2 are the eigenvectors associated with the top eigenvalues V (ax, )), respectively. (c) lo case, Gtrain = (d) case, Ctrain 24. (e)
12 case, Ctrann 0.5. (f) to case, Crrain = 8/255.
4.2 Numerical Validation
To validate the conclusions in theoretical analyses, we conduct numerical experiments study the properties of loss landscape of lu adversarial training and compare it with the lac (2 and l cases.
We first study the curvature in the neighborhood of model parameters, which reflects the second-order smoothness the loss function and is dominated by top eigenvalues of Hessian matrix V2C. 0). Numerically, we employ the power method 49 48 50] to iteratively estimate the eigenvalues and the corresponding eigenvectors of Hessian matrices. We plot the top-10 eigenvalues of the Hessian matrices (ar, 9)) under different in lo cases in Figure 3 (a). In addition, we compare the Hessian spectrum the to case with 1oo la and 1 cases in Figure 3)) (b). Our results in Figure 3 (a) demonstrate that eigenvalues of Hessian matrices degree of non-smoothness for a larger e. Moreover, Figure 3 (b) indicates that the adversarial loss landscape in the ln case is more craggy than its 4.c. and | counterparts, even when we i.e., perturbing only a single pixel. These observations corroborate that lo adversarial training exhibits worse second-order smoothness than other cases, causing challenges in optimization.
cases increase as grows, indicating higher
To study the first-order smoothness, we visualize the loss landscape of different settings in Figures (f)-(f), which demonstrate that the loss in the lo case abruptly increases in the model parameters. This further suggests the non-smooth nature of the In adversarial loss landscape. More loss landscape visualizations of adversarial training with different in Appendix F.9 The observations are consistent with that in FigureB Accordingly, we confirm that the loss landscape of lo adversarial loss function is more craggy than other cases from both theoretical and empirical perspectives. In addition, among the cases studied in Figure 3 the lo cases are the only ones suffering from CO.
with subtle changes
provided
Pin 233,, the lp adversarial budget for training on CIFAR- 10 is 120 in the pixel space of RGB images, so the equivalent la norm in the feature space is 360. Note that the adversarial budget mentioned in the experiment part is still in the pixel space.

---

On the other side, we show in Figure 4f of Appendix F.I that successful attempts to obtain robust models against in bounded perturbation also include elements that help improve the smoothness of the loss landscape. 20-step SAT in 233 uses an early stopping (ES) strategy to avoid CO and to achieve competitive performance. Specifically, ES interrupts the attack iteration once the current perturbed input is misclassified. ES is shown to circumvent the potential for excessive gradient magnitude while maintaining the efficacy of the generated perturbations. This finding further highlights a strong correlation between CO and the craggy nature of the loss landscape in adversarial training.
In summary, our results suggest that the lo adversarial training exhibits more eraggy loss landscape than other cases, which shows strong correlation with CO. Additionally, despite the non convirivial performance of 20-step sAT with ES, its performance still exhibits considerable fluctuation and can be further improved, underscoring the need for a smoother loss function. In the next subsection, we will offer our recipe to address the CO issue in fast lo adversarial training.
4.3 Recipe: Soft Label and Trade-off Loss Function Smooth Loss Landscape
Notice that Ag in Theorem 4.2 can be regarded as a function of the label y. Let E {0, 1) and ys E (0, 1)* denote the hard and soft label, respectively. That is say, yv. is a one-hot vector, while yı is dense vector in simplex. We find that soft label y. leads to a reduced first-order Lipschitz constant, thereby enhancing the Lipschitz continuity of the adversarial loss function. Detailed theoretical analysis is deferred to Proposition of Appendix C
However, indicated by Theorem 4.4 the second-order Lipschitz constant remains unaffected by variations in y- Considering the poor performance on clean inputs when CO happens, we introduce trade-off loss function Le.a which interpolates between clean and adversarial losses: Leio (æ. 0) (1 a1l-a) C(x, 0)+a maxses. 6 0) where a E [o, 1] is the interpolation factor. We find that trade-off loss function can enhance the second-order smoothness of adversarial loss
function. Detailed theoretical analysis is deferred to Proposition C.2 of Appendix C
stabilize and improve the performance of fast adversarial training against lo bounded perturbations by combining soft labels and tradc-off loss function. In addition, several available techniques, such self-adaptive training (SAT) [40] and TRADES (30], can be considered variations soft labels and trade-off loss function. In Appendix A
In implementation.
we provide the pseudo-codes of both SAT and TRADES and the formulation of their combination
reference. It should be highlighted that the rationale for using soft labels and trade-off loss function different for the lo case. Although they widely leveraged to address robust overfitting to boost performance in l2 and Loc cases, smoothing the loss function is essential to address the CO issue in the lo case.
5 Experiments
In this section, we perform extensive experiments investigate various approaches that can stabilize and improve the performance of fast lo adversarial training. Then, we compare the performance of 1 1-step adversarial training with the multi-step step counterparts.
5.1 Approaches to Improving 1-Step lo Adversarial Training
Table 4: Comparison of different approaches and their combinations in robust accuracy (%) by sAA. The target sparsity level 20. We compare PreAct ResNet-18 [24] models trained on
CIFAR-10 (25). Note that and N denote SAT and N-FGSM, respectively. The italic numbers indicate catastrophic overfitting (CO) happens.
Method
SAT
Trade-off
STRADES (T)
sTRADES (F)
1-step
0.0
2.6
31.0
55.4
N
0.3
17.5
46.9
55.9
+
29.3
30.3
61.4
59.4
S&N
43.8
39.2
63.0
62.6
We begin our analysis by evaluating the effectiveness of different approaches and their combinations, focusing on those that incorporate either soft labels or trade-off loss functions. Additionally, we explore a data augmentation technique N-FGSM [43), which may mitigate the sub-optimality of

---

Table 5: Robust accuracy (%) against sparse attacks. (a) PreActResNet-188 trained on CIFAR-10.
where the attack sparsity level c = 20. (b) ResNet-34 trained on ImageNet-100, where c = 200. CornerSearch (CS) is not evaluated due to its high computational complexity. Cost times are recorded on one NVIDIA RTX 6000 Ada.
(a) CIFAR-10, e 20
(b) ImageNet- E 200
Model
Time Cost
Clean
CS
RS
SAIF o-zaro sPGD, sPD,,
White
SAA
Model
'Time
Cost
Claa
Black RS
SAIP o-zero sPGD, sPGD, SAA
White
Multi-step
Multi-step
AA
5.3
84.5
[2.1
36.2
76.6
79.8
75.9
75.3
[36.2
SAT
325 h: 86.2
61.4
69.0
78.6
78.0
77.8
61.2
+S&N
5.5h
64.1
76.1
78.7
76.8
75.1
+S&N
336 h 83.0
75.0
76.4
80.8
78.8
79.2
74.8
TRADES
5.5h
89.8
69.9
61.8
84.9
85.9
84.6
81.7
61.7
STRADES
84.8
76.0
77.4
81.6
+S&N
5.4h
82.2
66.3
66.1
77.1
77.0
74.1
72.2
65.55
+S&NN
360
82.4
78.2
79.2
80.0
78.2
79.8
77.8
One-step
One-steep
Fast-LS-lo
0.8h 82.5
669.3 65.1
75.7
73.7
67.2
67.7
663.0
Fast- Li
44h
82.4
76.8 |
75.4
74.0
74.6
74.6
72.4
perturbation location by randomly perturbing more pixels. Our findings, summarized in Table are all based on 1-step adversarial training. The robust accuracy is measured using the sparse-AutoAttact (sAA) method, with set to 20.
In Table 4 we investigate the following approaches and their combinations: (1) SAT: adversarial
training against 1-step sPGD [23]. (2) Tradeoff: 1-step adversarial training with the trade-off loss
function as discussed in Section 4.3 (3) STRADES: the 1-step sTRADES [23]. As discussed in
Appendix[A] A it incorporates both soft label and trade-off loss function. We include two variants of STRADES for comparison: STRADES (T) is the training mode where we only use the loss objective function of TRADES for training but still use the cross-entropy loss to generate adversarial examples; sTRADES (F) is the full mode where we use the KL divergence loss function for generating adversarial perturbations. Compared with 1-step SA,, STRADES (T) introduces 25% overhead while sTRADES (F) introduces 50% overhead. (4) SAT (S): self-adaptive training [4). As discussed in Appendix A it introduces soft labels based on the moving average of the historical predictions and uses adaptive weights for training instances of different prediction confidence. (5) N-FGSM (N): data augmentation technique by adding random noise to the training data. It is proven effective in 1-step adversarial training 44). I. Among these approaches, SAT (S) and sTRADES introduce soft labels; trade-off and STRADES use trade-off loss functions to smooth the loss objective function. The comparison with other smoothing approaches is undertaken in Appendix F3 The implementation details are deferred to Appendix G
The results Table 4 indicate that using trade-off loss function alone still suffers from CO. In contrast, combining it with soft label, either by SAT or STRADES, can eliminate CO and achieve notable robust accuracy. Furthermore, STRADES (F) outperforms STRADES (T) by a substantial margin of 24.4%. which can be attributed to the generation of higher-quality adversarial examples for training by sTRADES (F). Finally, both SAT and N-FGSM can enhance the performance of all approaches, demonstrating their effectiveness.
Note that the results presented in Table are obtained using sAA, which known for generating the strongest attacks in terms of lu perturbations. Our findings demonstrate that incorporating soft labels and trade-off loss function yields substantial performance improvements in 1-step lo adversarial training. Among various combinations of methods explored, the model trained with STRADES (T) with SAT and N-FGSM achieves the highest robust accuracy against sAA, reaching an impressive 63.0%. This establishes the state-of-the-ar performance in fast lo adversarial training methods. For convenience, we name this combination (i.c., 1-step sTRADES + SAT + N-FGSM) Fast-Loss Smoothing-lo (Fast-LS-(o). Its pscudo-code is given in Algorithm 3 of Appendix
Furthermore, we validate the robustness of our method against feature-space attacks in Appendix F.6 validate the efficacy of our method for I, la and T cases in Appendix F.7 validate the efficacy of our method on different networks in Appendix F.8 visualize the loss landscape when using our method in Appendix F. to demonstrate its improved smoothness, and conduct ablation studies for analysis in Appendix F.IT Our extensive results demonstrate the broad effectiveness of smoothing loss landscape in fast adversarial training. Nevertheless, it turns out essential to address CO and has the largest performance improvement in the lo cases compared with other 4p norms (p 2 1), because the loss landscape is much more craggy in the to cases, analyzed in Section 4

---

5.2 Comparison with Multi-Step Adversarial Training
In this section, we compare 1-step adversarial training with its multi-step counterpart. For multi-step adversarial training. we follow the settings in (23] and use 20-step sPGD based on cross-entropy to generate adversarial perturbations in sAT and sTRADES. Similar to Table we incorporate SAT and N-FGSM into multi-step adversarial training as well. For 1-step adversarial training, we focus on the best configuration Table i.e., Fast-L.S-lo.
We conduct extensive experiments on various datasets. The results on CIFAR-10 10 and ImageNet- 100 [51] are demonstrated T More results on CIFAR-IO0 100 (25 and GTSRB [22 are in Table 8 and of Appendix F.4 respectively. In addition to the performance under SAA, we report the robust accuracy under various black-box and white box attacks, including CornerSearch (CS)
211 Sparse-Re RS (RS) 22) SAIF [42). a-zerd [53] and two versions of sPGD (33 Moreover, we report the clean accuracy and running time for reference. Finally, to more comprehensively validate the effectiveness of our results, we report the standard deviation of the performance in Table If of
Appendix
F.5
The results Table and 9 suggest that our method can improve the performance of both 1-step and multi-step adversarial training. In addition, N-FGSM, originally designed for 1-step adversarial training, also contributes to performance improvements in the multi-step scenario. Furthermore, these techniques can greatly narrow down the performance gaps between 1-step and multi-step adversarial training, making fast adversarial training more feasible and competitive. With the assistance of SAT and N- N-FGSM, our Fast-LS-ly can achieve a performance that merely 2.5% lower than that of the 20-step sTRADES while requiring less than 1/6 of the total running time.
Conclusion
We highlight that the catastrophic overfitting (CO) in lo adversarial training is caused by sub-optimal perturbation locations. Our analyses show that the loss landscape of lo adversarial training is more eraggy than other cases and correlates with CO. To address this, utilize soft labels and trade-of off loss function to smooth the adversarial loss. Extensive experiments show our method effectively mitigates CO and narrows the performance gap between 1-step and multi-step adversarial training, achieving state-of-the-art robustness against sparse attacks.
Broader Impacts and Limitations
Since our method is evaluated on benchmarks, we do not see it has an obvious negative societal impact. Despite the effectiveness of soft label and trade-off loss function, we cannot guarantee they are the optimal method to smooth the loss landscape of lo adversarial training. We leave developing more effective methods as future work.
Acknowledgments and Disclosure of F Funding
This work is supported by National Natural Science Foundation of China (NSFC Project No. 62306250) and City University of Hong Kong (CityU Project No. 9610614).
References
[1] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 131.6699, 2013.
[2] Anish Athalye, Nicholas Carlini, and David A. Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning, 2018.
We replace the regularization term in a-zero with To hhu Σi +1, generate perturbations in pixel space. where h. w and are the height, width and channel of images, and R4 represents the perturbation on the i-th channel of a particular pixel.
Ei
10

---

[3] Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International conference on machine learning. pages 2206-2216, PMLR, 2020.
[4] Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Edoardo Debenedetti, Nicolas Flammarion, Mung Chiang, Prateek Mittal, and Matthias Hein. Robustbench: a standardized adversarial robustness benchmark. arXiv preprint urXiv:201000960 2020.
[5] 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.
[6] Francesco Croce and Matthias Hein. Minimally distorted adversarial examples with fast adaptive boundary attack. In International Conference on Machine Learning, pages 2196-2205. PMLR, 2020.
[7] Vikash Schwag, Saeed Mahloujifar, Tinashe Handina, Sihui Dai, Chong Xiang, Mung Chiang. and Prateek Mittal. Robust learning meets generative models: Can proxy distributions improve adversarial robustness? In International Conference on Learning Representations.
[8] Sylvestre-Alvis Rebuffi. Sven Gowal, Dan A Calian, Florian Stimberg, Olivia Wiles, and Timothy Mann. Fixing data augmentation to improve adversarial robustness. arXiv preprint arXiv:2105. 0946, 2021.
[9] Sven Gowal, Sylvestre-Alvise Rebuffi, Olivia Wiles, Florian Stimberg, Dan Andrei Calian, and Timothy A Mann. Improving robustness using generated data. Advances in Neural Information Processing Systems, 14:4221-42333 2021.
[10] Rahul Rade and Seyed- Mohsen Moosavi- -oosavi-Dezfooli. Helper-based adversarial training: Reducing excessive margin to achieve a better accuracy vs. robustness trade-off. In ICML 2021 Workshop on Adversarial Machine Learning. 2021.
[11] Jiequan Cui, Zhuotao Tian, Zhisheng Zhong, Xiaojuan Qi, Bei Yu, and Hanwang Zhang. Decoupled kullback-leibler divergence loss. arXiv preprint arXiv:2305. 13948, 2023.
[12] Zekai Wang, Tianyu Pang, Chao Du, Min Lin, Weiwei Liu, and Shuicheng Yan. Better diffusion models further improve adversarial training. In International Conference on Machine Learning, pages 36246-36263, PMLR, 2023.
[13] Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! Advances in neural information processing systems, 32, 2019.
[14] Dinghuai Zhang, Tianyuan Zhang, Yiping Lu, Zhanxing Zhu, and Bin Dong. You only propagate once: Accelerating adversarial training via maximal principle. Advances in neural information processing systems, 32, 2019.
[15] Eric Wong, Leslie Rice, and J Zico Kolter. Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations.
[16] Gaurang Sriramanan, Sravanti Addepalli, Arya Baburaj. and Venkatesh Babu R. Towards efficient and effective adversarial training. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 1 11821-11833, Curran Associates, Inc., 2021.
[17] Peilin Kang and Seyed-Mohsen Moosavi-Dezfoolli Understanding catastrophic overfitting in adversarial training. arXiv preprint arXiv:2105.02942 2021.
[18] Florian Tramer and Dan Boneh. Adversarial training and robustness for multiple perturbations. Advances in neural information processing systems, 32, 2019.
[19] Yulun Jiang, Chen Liu, Zhichao Huang, Mathieu Salzmann, and Sabine Süsstrunk.. Towards stable and efficient adversarial training against bounded adversarial attacks. International Conference Machine Learning. PMLR, 2023.

---

[20] Apostolos Modas, Seyed- Mohsen GboosaviDezzooole and Pascal Frossard. Sparsefool: a few pixels make big difference. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9087-9096, 2019.
[21] Francesco Croce and Matthias Hein. Sparse and imperceivable adversarial attacks. In Pro- ceedings of the IEEE/CVE international conference on computer vision, pages 4724-4732, 2019.
[22] Francesco Croce, Maksym Andriushchenko, Naman D Singh, Nicolas Flammarion, and Matthias Hein. Sparse-rs: versatile framework for query-efficient sparse black-box ad- versarial attacks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 0437-6445. 2022.
[23] Xuyang Zhong, Yixiao Huang, and Chen Liu. Towards efficient training and evaluation of robust models against ln bounded adversarial perturbations. In Forty-first International Conference on Machine Learning. 2024.
[24] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[25] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[26] Hoki Kim, Woojin Lee, and Jaewook Lee. Understanding catastrophic overfitting in single-step adversarial training. AAAI Conference on Artificial Intelligence. 2020.
[27] Maksym Andriushchenko and Nicolas Flammarion. Understanding and improving fast ad- versarial training. Advances in Neural Information Processing Systems, 33:16048-16055 2020.
[28] Haizhong Zheng, Ziqi Zhang, Juncheng Gu, Honglak Lee, and Atul Prakash. Efficient adversar- ial training with transferable adversarial examples. 2020 IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pages 1178-1187, 2019.
[29] Zhichao Huang, Yanbo Fan, Chen Liu, Weizhong Zhang, Yong Zhang, Mathieu Salzmann, Sabine Süsstrunk, and Jue Wang. Fast adversarial training with adaptive step size. IEEE Transactions on Image Processing, 2023.
[30] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference on machine learning, pages 7472-7482. PMLR, 2019.
[31] Lin Li and Michael Spratling. Understanding and combating robust overfitting via input loss landscape analysis and regularization. Pattern Recognition, 136: 109229, 2023.
[32] Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving adversarial robustness requires revisiting misclassified examples. In International Conference on Learning Representations, 2020.
[33] Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang. Robust overfitting may be mitigated by properly learned smoothening. In International Conference on Learning Representations, 2020.
[34] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint 14Xiv:1412.6555 2014.
[35] Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial machine learning scale. In International Conference on Learning Representations, 2017.
[36] Yinpeng Dong, Fangzhou Liao, Tianyu Pang. Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li. Boosting adversarial attacks with momentum. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018
12

---

[37] Maksym Andriushchenko, Francesco Croce. Nicolas Flammarion, and Matthias Hein. Square attack: query-efficieen black-box adversarial attack via random search. In European conference on computer vision, pages 484-501. Springer, 2020.
[38] Leslie Rice, Eric Wong, and Zico Kolter. International conference machine learning, pages -094-8104. PMLR, 2020.
Overfitting adversarially robust deep learning. In
[39] Chen Liu, Zhichao Huang, Mathieu Salzmann, Tong Zhang, and Sabine Süsstrunk. On the impact of hard adversarial instances on overfitting in adversarial training, 2021.
[40] Lang Huang, Chao Zhang, and Hongyang Zhang. Self-adaptive training: beyond empirical risk minimization. Advances in neural information processing systems, 33: 19365-19336,, 2020.
[41] Francesco Croce and Matthias Hein. Mind the box: l_1-apgd for sparse adversarial attacks on image classifiers. In International Conference on Machine Learning, pages 2201-2211. PMLR, 2021.
[42] Tooba Imtiaz, Morgan Kohler, Jared Miller, Zifeng Wang, Mario Szmaier, Octavia Camps, and Jennifer Dy. Saif: Sparse adversarial and interpretable attack framework, arXiv preprint arXiv:2212.07499 2022.
[43] Pau de Jorge Aranda, Adel Bibi, Riccardo Volpi, Amartya Sanyal, Philip Torr, Grégory Rogez, and Puncet Dokania. Make some noise: Reliable and efficient single-step adversarial training. Advances in Neural Information Processing Systems, 35: 1 1288-112889 2022.
[44] Runqi Lin, Chaojian Yu, and Tongliang Liu. Eliminating catastrophic overfitting via abnormal adversarial examples regularization. Advances in Neural Information Processing Systems, 36, 2024.
[45] Runqi Lin, Chaojian Yu, Bo Han, Hang Su, and Tongliang Liu. Layer-aware analysis of catastrophic overfitting: Revealing the pseudo-robust shortcut dependency. In Forty-first International Conference on Machine Learning, 2024.
[46] Yihua Zhang, Guanhua Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu. Revisiting and advancing fast adversarial training through the lens of bi-level optimization. In International Conference on Machine Learning, pages 26693-26713 12. PMLR, 2022.
[47] Julia Grabinski, Steffen Jung, Janis Keuper, and Margret Keuper. Frequencyloweut pooling-plug and play against catastrophic overfitting. In European Conference on Computer Vision, pages 36-57. Springer, 2022.
[48] Chen Liu, Mathieu Salzmann, Tao Lin, Ryota Tomioka, and Sabine Süsstrunk. On the loss landscape of adversarial training: Identifying challenges and how to overcome them. Advances in Neural Information Processing Systems, 33:21476- 224822 2020.
[49] Zhewei Yao, Amir Gholami, Qi Lei, Kurt Keutzer, and Michael W Mahoney. Hessian-based analysis of large batch training and robustness adversaries. Advances in Neural Information Processing Systems, 31, 2018.
[50] Xuyang Zhong and Chen Liu. Toward mitigating architecture overfitting on distilled datasets.
IEEE Transactions on Neural Networks and Learning Systems, 2025.
[51] Deng, W. Dong. Socher, L.-J. Li, K. Li, and L. Fei-Fei. Hierarchical Image Database. In CVPR09, 2009.
ImageNet: A Large-Scale
[52] Johannes Stallkamp, Mare Schlipsing, Jan Salmen, and Christian Igel. Man vs. computer: Benchmarking machine learning algorithms for traffic sign recognition. Neural networks, 32:323-332, 2012.
[53] Antonio Emanuele Cinà, Francesco Villani, Maura Pintor, Lea Schönherr, Battista Biggio, and Marcello Pelillo. a-zero: Gradient-bast optimization O-norm adversarial examples. In ICLR, 2025.
13

---

[54] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Re- thinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2818-2888 18-2826, 2016.
[55] Zhuang Liu, Hanzi Mao, Chao- Yuan Wu, Christoph Feichtenhofer. Trevor Darrell, and Saining Xie. A convnet for the 2020s. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11976- 177776-1186.,. 2022.
[56] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF international conference on computer vision, pages 10012-10022, 2021.
[57] Edoardo Debenedetti, Vikash Sehwag, and Prateek Mittal. light recipe to train robust vision transformers. In 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), IEEE, 2023.
pages
[58] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In Computer Vision-ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part IV 14, pages 630-645. Springer, 2016.
[59] Charles Dugas, Yoshua Bengio, François Bélisle, Claude Nadeau, and René Garcia. Incor- porating second-order functional knowledge for better option pricing. Advances in neural information processing systems, 13, 2000.
14

---

A Algorithm Details
Algorithm Self-Adaptive Training (SAT) 400
1: Input: Data: {(x,, hn; Initial target (t,)n {3i Jn Batch size: mi Classifier: fü Enabling
epoch: Eg; Momentum factor: a
2: repeat
3: Fetch mini-batch data {(2,, hm at current epoch
4: for I,..., do
5:
P: softmax f (x:))
6: if E, then
7:
4 == a x t; + a) x x
8:
end if
9:
Wi = maxj tij
end for
11: Calculate the loss LSAT = Ei wi Ej tiss Pig
12: Update the parameters of on LSAT
13: until end of training
Algorithm TRADES [30]
1: Input: Data: (æ,y); Classifier: f: Balancing factor: A; TRADES mode: mode; Sparse level:
2: if mode F then
3: Generate adversarial sample ă max(a-=)cS.((m) (L(
4: else if mode = then
5: Generate adversarial sample ă max(a-4)cS.(e) CE(J()),))
6: end if
7: Calculate the loss LTRADES CE(f(=), + (L(f
8: Update the parameters of on CTRADES
The pscudo-codes of SAT 40 and TRADES 30 provided in Algorithm I and 2 respectively. For SAT, the moving average of the previous predictions {t,)" can be regarded as the soft labels. For TRADES, fxx can be seen the soft label of f()), and the combination of cross-entropy and KL divergence is also a trade-off loss function. Note that when combining SAT and TRADES, the loss Ls4T for mini-bateh data {(x,, y:) m be written
LS+T Σ; mi
Σ we CE(S(a))) (.) + m
Σ KL(((
(8)
In addition, we provide the pseudo-code of the proposed Fast-LS-lo, which incorporates SAT, TRADES and N-FGSM, in Algorithm 3
B Proofs
B.1 Proof of Theorem 4.2
Proof. Based the definition of ö, and d2, have (, 0.) L(x + 81, 0i) and (x, 02)
L(x + 52, 02). In this regard, we have:
(x, 01) - (x, 02)1 = +1, 0,) L(x + 82, 02)
(9)
When f(x + 81, 01) f(x + 52, 02) we have
[|[( + 01 L(x 82, 02)1l
= [[[ 0,, 01) - L(x 8,, 02) + L(x + 01, - -((x 82, 02)1
(10)
<1| 06, -(x + 02)
The inequality above is derived from the optimality of 52. which indicates L(x + 02) L(x 82, 0z) < 0 and the assumption L(x + 01) L(x + 82, 0z).
15

---

Algorithm 3 Fast-LL--0
Input: Data: {(t, y:)s Initial target {t,)" {y:) )m; Batch size: m. Classifier: Enabling
epoch: Es; Momentum factor: a; Balancing factor: 3; TRADES mode: mode; Sparse level:
2: repeat
3: Fetch mini-batch data {(,,, hm at current epoch
4: for L...., do
5:
? (2:))
6:
x; x; + 77
// Augment sample with additive noise
7:
if mode = F then
8:
3. = max 2x )... (x.)
9:
else if mode T then
10:
ã; m..
(B(
11:
end if
12:
P: = softmax(f(x)
13:
if E, then
14:
t, = a x t, + (1 - a) x p:
15:
end if
16:
Wi = maxj ti.j
17:
end for
18:
Calculate LS+T in Eq.
Update the parameters of f LS+T
20:
until end of training
Similarly, when [(x + 01) - f(x + 82, 02) we have
[[ + 01 L(x 62, 02)l
= =I + 01) - f(x + 82, 01) + L(x + 02, - L(x + 82, 02)1l
(11)
<IIC(x
L(x + 82, 02)1
Without the loss of generality, further bound [ac, 01) (xr, 02)l based on 10 The derivation can be straightforwardly extended to (11) by replacing 5n with 82-
Based on the formulation of L in 11. Ce (ar, 11) (ar 02)1 can be further derived as follows:
1 + 02) h:( 01)
[,, 01) L. (x, 02)1 5
Σ iES+
Vi log
(12)
1 Σ Eidi exp(f +1, 02) - f((x + 6,, 02))
log
+ 544 (x fi(x + 81, 01))
EES
where S+ {i ( ys 1a(2 + 82,02) > h 01,01). Then, according to the mediant inequality, we have
1 jn ===
log
1 + 01) f(x
Σ i exp(/(=++0,00)) 6
< log
Σ j exp(f/ - f((
(13)
(p( f(( 11, 02)
< max log
exp(fx(2+6 01 6
max (f 51, 02) fa(x 6, 01) + 1ff(z 5,, 02)
f((x 5, 01)
<2Lg| 0, -0
16

---

Note that the bound on the right of (33) is tight. The upper bound can be achieved asymptotically if the condition (4) and the Lipschitz bound in Assumption 4.1 are satisfied.
[ + 81, 02) - Si( + 51, 02) - ( + 01) - l: + 81, 0131
(14)
> max jzh
+
81, 02) - f 81, 02) + 01) fi( + 81. 01]
Combining 9
13 have
(0, 01) 02)1ll - Aollo; - 02ll.
(15)
where Ag = 2 Eies, ViLo.
B.2
Proof of Theorem 4.4
Proof. Given
VgL is computed as
Σ Vi Vol((z,)) 0) -i Es exp(ff(x, Vof 0)
K
Vol(x,
Ej Exx 0))
1=
Σ, exp(ff a Vo)
Σ y1 Vol((x0
(16)
E, 0))
1=0
K-1
K-1
(2,
Σ
W: V.Vol((
The second equality is based the fact that {y is in a simplex. To simplify the notation, the last
equation is based the definition that {
K- is the result of softmax function applied {fz}
i.e., (2r, ? Dg (a. Therefore, have Σ/=D1 h5(2;, 0) and vjj h,((x, 0) 0.
exp(f,
According to the triangle inequality, have:
Vo, L(x 01) Vo.C(x 52, 02)1
V C(x + 01) - Vo, C(x + 52, 01)1 + Ve, C(x + 0,,0,) - Vo, L(x + 62, 02)1 (17)
Plug 16 the first term the right hand side of [77
we obtain:
|| Vo, f(x 01,
Vo, C(x 01,01)1
Σ Vi Vo,f(a
Vo, (o 01,
01)l
hr + + 0,Vo + 0,
Σ
h1( + 82, 0 82 01)
(18)
The first term can be bounded based Assumption
4.1
The second term can be bounded follows:
17

---

R-1
+ (1.
Σ
h (1 82,
Σ h
01, +,,
hy(æ + 82, 02 82, 02)
K-1
$
Σ
h1 + 01)
max Vosk(w 81, 01)
+ Σ /=0
hy(a + 82, 01) max Volu(a 82, 01)
/=0
<2Le
(19)
Note that the bound on the right of 19 is tight. The first inequality is based on the triangle inequality. The second inequality and the third inequality be achieved asymptotically when the equality of first-order Lipschitz continuity in Assumption 4.1 achieved and the following condition is satisfied.
3k E arg max T. Ni, (x + 01) + max hy (a: + 51, 01) 0 jzk
(20)
3gg E arg max 1.)) h, + 82, 01) 1, max 82, 01) 0
Note that and ka are not always the same, since there may exist more than one biggest first-order Lipschitz constant.
Combining (18) and 199 together, we obtain:
Ve + 62 s 2Le Lox 81
(21)
Similarly, we have:
IV, C(x 82, 01) Ve, 82, 02)1 s 2L Leel02 011
(22)
Combing the two inequalities above, we have:
VoL(( 01) VoL(x 82, 02)1 s Aoo 00 021 + Boo
(23)
where
Ase = Leoi Boo 4Le + Lex 821l
(24)
C Theoretical Analysis of Soft Labels and Trade-off Loss Function
We have the following proposition about soft labels: Proposition C.1. (Soft label improves Lipschitz continuity) Based on Theorem 4.2 given a hard label vector yı E {0, 1) and soft label vector ys E (0, 1) we have Ag(y.) Ao A0()))
Proof. For hard label yı E {0.1) let that the j-th elements yn and the rest be 0. By the definition of Ag in Theorem 4.2 we have
Ao(yr) 2L.-
(25)
known that K-- hy( 0) 1, which means Ej. h + 81, 02) S hy(x + 61,0,). Then.
for soft label ys (0, 1)KK, we have |S+1 K where S+ {i Di h1(w + 02) > ha( + 81, 0.)). Thus, it holds
Ao(u.) =2 2 Σ y Lo S Ao(yn).
(26)
iES,
The equality can be achieved asymptotically if Lies, ys 0.
18

---

Proposition C.1 indicates that soft labels lead to reduced first-order Lipschitz constant, thereby enhancing the Lipschitz continuity of the adversarial loss function.
Then, we have the following proposition about trade-off loss function:
Proposition C.2. (Trade-off loss function improves Lipschitz smoothness) If Assumption 4.1 and
4.3 hold, have:
VV (2. 01) - VoLu. 02)1 S Ago 00 - -02ll + Bogs
(27)
The constants Age = Leo and Bes = aLoæ 61 521 + 2(1 + Lo where ò1 E
arg mmx) f(x 6, 6,) and 82 max (m) a(x 6, 62).
Proof. By the definition of Le in Section we have
IV (a, ar, 01) - Vo,Le.n (x. 02)1
(28)
< (1- -a]l Va, L(x, 01) Vo, ((,, 02) Vo, Vo, (x, 02)1
According to 22) in the proof of Theorem the first term of the right hand side of 28 can be derived as
Ve, C(x, 01) Ve, C(, 02) Lee 0: -02l 2Lg.
(29)
According to Theorem
4.4 the second term of the right hand side of 28 satisifies
Vo, 01) Vo,Ce 02)1l < Loo| 0211 + Lax |6 82ll + 4Lg-
(30)
Combining 28
29 and (30), we have
Vo, Le, 01) VolCc,a (z) I Aool 0211 + B3g8.
(31)
where Age Lee and Bos aLo |ō 8211 + 2(1 + Lo.
According to Proposition C.2 the trade-off loss function Le,a enhances the second-order smoothness of adversarial loss objective function. Furthermore, compared with I, la and lxc cases, the trade-off loss function is particularly useful and necessary in the lo case. This supported by the analyses in Section 1 and Appendix [ which demonstrate that |60 82ll is much larger in 4n bounded perturbations than other cases. Therefore, expect the trade-off loss function Lr,a can help mitigate CO by improving smoothness.
Similar to Theorem 4.4 Proposition C.2 can be straightforwardly extended to the networks with
non non-smooth activations, where Assumption 4.3 is not strictly satisfied. We provide a more detailed
analysis in Appendix D to demonstrate the generality of our conclusions.
D Theoretical Analysis of ReLU Networks
Similar to 48 we first make the following assumptions for the functions K- represented by ReLU network.
Assumption D.1. Vi E {0, I,... K 13. the function f. satisfies the following conditions:
Var, 0,, O2,
[|,( 0 - f( 02) < Lo 0 0211,
(32)
40, 21 22
[[fi(x,, 0) f1 0)1 Lg |x| x2I1.
(33)
Va,, 0 02,
Vo, 01) - Vofi(w 02)] < Loo| 0 - 02l
+ Coo:
(34)
vO, 21, 272
Vol(mm Voli(w2, 0)] Lax |x x2l
Con-
(35)
Compared to Assumption 4.1 and 4.3
modify the the second-order smoothness assumptions by adding two constants Coe and Can- respectively. They denote the upper bound of the gradient differ- ence in the neighborhood non-smooth point. Thus, they quantify how drastically the (sub)gradients can change in sufficiently small region in the parameter space.
Based on Assumption D.I we have the following corollary:
19

---

Corollary D.2. If Assumptiin D.1 is satisfied, it holds
|1, 01) L. (zz, 02) - Ao A O2ll:
(36)
[V,,, (1) VoL. (xx 02) _ Agell 01 02l1 + Bas + Cee + Caz-
(37)
The Lipschitz constant Ag = 2 Lies, Vg Age = Lee and Bes = Lew |ô1 8211 + 4Lg where 81 arg maxses, f(x + 8, 01) and 82 E arg max L( + 6, 02).
The proof is similar to that of Theorem 4.2 and 4.4 Corollary D.2 indicates more craggy loss landscape in the adversarial training of networks with non-smooth activations.
Additionally, the Proposition C.2 can be easily extended to accommodate Assumption D.1
Corollary D.3. If Assumption D.1 holds, then we have
VoLc,a 01) - Va 02)ll S Aso 0 02l + Bos + Coo + Coa-
(38)
The Lipschitz constant Ase = Lee and Bos = aLeæ 6 - 82ll + 2(1 + a)Le where 51 E arg maxses. C(x + ò. +,,01) 01) and 82 E arg max C(x + 6, 02)
E Discussion of the Upper Bound of ||, 82ll
We define the lp adversarial budget for the perturbation 5 Rd as S!P) { |011 S c,
+ I 13. Therefore, we have | - 5211 S 2c, and Vi, S 18 8! S where 8 and
82 are the i-th element of 81 and 62, respectively. For convenience, denote ô 82 Ad and 01 5/4 as Ad; in the following.
Assume that < d for lo, lı and lz bounded perturbations, and < for the Lo bounded perturbation. Then, Vg 2 1, we have
budget:
A < 2e,,
l budget:
Ad,1% < Di + (2e - D1)a,
(39)
12 budget:
A0;11 S D2 + (462 D2)
1oo budget:
A < d x (26)*,
where D1 [2e] and D: [4<²]. The derived upper bounds are tight because
(1) to budget: The equality achieves when the location non nor-zero elements in d1 and 62 has no overlap, and the magnitude of their non-zero elements reaches +1.
(2) 1 budget: Since < |d,| < 1, the equality achieves when there exists at most one Adg such that Adg < and vj + k, Adyl = 1. The maximum number of Adj is [2e]. Then, according to | 1 S 26, we have A& 2
[2c].
(3) /2 budget: The derivation is similar to that of the I case.
(4) loc budget: The equality achieves when d -62.
On popular benchmark CIFAR-10,
32 32 x 3072, and the commonly used values of
e in the lo. 11. l2 and 1oo cases are 360, 24, 0.5 and 8/255, respectively [5] [3] 41,41, Substitute these into (3)), we can easily get that Vg 1, the upper bound of Σ, A is significantly larger in the ly case than the other cases. For instance, (2c- - D2)a, (4c² D2) a and (2c)a reach their respective maximum values when q 1, since all of them smaller than 1. Then, the upper bounds of Σ, | in the lo, 4,, l2 and los cases are 720, 24, and 49152/255 x 192.8, respectively.
Furthermore, the l norm of A6 is defined as follows:
A =
Σ Ad
(40)
20

---

-55
20 step SAT
20-step sAll
robust accuracy
20-step SAT w/o ES
20
15
110.
10.
20
40
60
80
100
20
40
80
100
Epoch
Epech
(a) Gradient Norm
(b) Test Robust Accuracy
Figure 4: Relationship between craggy loss landscape and CO. (a) Gradient norm Vo, l|- (b) Test robust accuracy against sAA (e 20). The results obtained from PreactResNet-118 trained CIFAR-10 10 with ttein = 40. Since the training of 20-step SAT w/o ES diverges under train = 120,
the results are presented under étrain 40 instead.
| in the lo case is larger than 1 for all q 2 1, we can also derive that Vq 2 1, the upper bound of | always significantly larger in the to case than the other cases.
Since the upper bound of Σ;
F
More Experimental Results
F1 Early Stopping in Multi-step Adversarial Training Avoids Catastrophic Overfitting
In Figure we compare the cases with and without ES in terms of gradient norm and robust accuracy on the test set by sAA. We can observe that 20-step sAT without ES still suffers from CO and the corresponding gradient magnitude during training indicates craggy loss landscape.
F.2 Distances between Gradients Induced by 1-step and Multi-step Attacks
Table 6: Average la distances between gradients induced by 1-step and multi-step attacks, represented by I C (x: done) V.L.(2 (x: + 6mauts))l2 The gradients are calculated of the training set of
CIFAR- 10 25 The lo. I, la and Loo models are obtained by 1-step sAT [23], Fast-EG-l, [19 1-step PGD 38 and GradAlign (37], respectively. The 1-step and multi-step lo attacks are 1-step and
10000-step sPGD 223 respectively. The 1-step and multi-step / attacks are 1-step Fast-EG-11 and
100-step APGD 41, respectively. The 1-step and multi-step attacks for other norms are 1-step PGD
5 and 100-step APGD 33. respectively.
Model
lo (e = 1)
4 (e = 24)
12 (F = 0.5)
1.0 (E 8/255)
12 distance
15.8
10
3.6 10-4
x 10-4
Based on the Lipschitz smoothness assumption in Inequality (6) the gradient difference arising from approximated adversarial perturbations is bounded by T.o. d 82ll where ö1 the perturbation generated by 1-step attack and &n is the optimal perturbation. Based on the same reason that lo norm not proper norm, || 521 || is significantly larger in lo cases than l.o. and I cases, which makes 1-step adversarial training more challenging in lo cases. To corroborate this, we compare the distance between gradients induced by 1-step and multi-step attacks. As presented in Table 6 the average distance between gradients induced by 1-step and multi-step attacks is 5 orders of magnitude greater than those in the I, le and loc cases, even when a single pixel perturbed. This finding indicates that the loss landscape of lo adversarial training is significantly more craggy than other cases in the input space.
F.3 Comparison with Other Smoothing Approaches
In this section, we undertake a more comprehensive comparison between our proposed Fast-L.S-lp and other smoothing approaches (label smoothing (L.S) [54], AdvLC (31), MART (32 and SWA [3 Note that all baselines are tuned by thorough hyperparameter search. demonstrated in Table method achieves the strongest robustness against sAA. First, naive LS turns out ineffective under
21

---

Table 7: Comparison with other smoothing approaches in robust accuracy (%) by SAA. The target
sparsity level = 20. We compare PreAct ResNet-18 18 [24] models trained on CIFAR-10 25 The italic numbers indicate catastrophic overfitting (CO) happens.
Method
LS
AdvLC
MART
TRADES
Ours
Ours+ SWA
Robust Acc.
0.0
59.6
48.0
45.0
63.0
59.1
the lo setting. The performance of AdvLC, MART, and SWA is not good the method we use. Additionally, the combination of our method with SWA harms robustness due to wro-ssnot
F.4 More Results of Section
Table 8: Robust accuracy (%) of various models on different attacks that generate 4 bounded perturbations, where the sparsity level 10. The models are PreAct ResNet-18 trained CIFAR-
100 |25 with 60. Note that the results of vanilla sAT and sTRADES are obtained from 23 ComerSearch (CS) is evaluated on 1000 samples due to its high computational complexity.
Time Cost
Black-Box
White-Box
Model
Clean
SAA
CS
RS
SAIF
sPGD sPGDunpro]
Mulii-step
SAT
4h 27m
67.0
44.3
41.6
60.9
56.8
58.0
41.6
+S&N
4h 58m
64.3
53.0
52.9
61.2
59.2
59.6
52.8
TTADDE
5h 10m
70.9
52.8
50.3
65.2
64.0
63.7
50.2
+S&N
5h 40m
63.8
56.5
55.6
61.2
60.5
59.0
55.3
One-step
Fast-LS-lo (T)
Ih 05m
65.3
54.5
$4.3
60.4
55.6
54.4
52.2
Fast-LS-Ip (F)
26m
65.0
56.2
54.6
60.8
54.9
54.9
52.3
Table 9: Robust accuracy (%) of various models different attacks that generate lo bounded perturbations. where the sparsity level e 12. The models are PreAct ResNet-1 88 trained on GTSRB [52] with 72. All methods evaluated 500 samples, and CornerSearch (CS) is not evaluated here due to its high computational complexity.
Time Cost
Black-Boo Box CS
White-Box
Model
Clean
SAA
RS
SAIF
sPGD proj
sPGD Dumpraj
Multi-step
SAT
1h 3m
98.4
43.2
92.4
96.0
96.2
43.2
+S&N
Ih 2m
98.4
77.8
97.4
96.8
95.4
77.6
STRADES
Ih 6m
67.6
94.0
95.6
95.0
67.4
+S&N
1h 7m
95.6
75.4
93.6
92.6
91.2
75.2
One-step
Fast-LS-lo (T)
7m
97.8
75.2
89.2
74.4
74.4
63.2
Fast-LS-lo (F) 9m
98.6
80.4
94.2
75.0
79.8
67.8
The results CIFAR-100 and GTSRB datasets presented in Table X and 9 respectively. The findings are consistent with those observed in Table 5(a) further validating the effectiveness of the proposed methods across different datasets. contrast the settings in (23,, we resize the images in GTSRB to 32 x 32 instead of 224 x 224 and retrain the models from scratch. The model are trained with 72 and evaluated for robustness with 12. It important note that due to the smaller search space resulting from low-resolution images, the attack success rate of the black-box Sparse-RS (RS) under this setting is significantly higher than that reported in 23
F.5 Standard Deviation of Robust Accuracy against Sparse-
Table ((a)
To better validate the effectiveness of our method, we report the standard deviations of robust accuracy against SAA Table TO We calculate these standard deviations by running the experiments three times with different random seeds. The configurations are the same as in Table 5(a) It can be
22

---

Table 10: Average robust accuracy against SAA 23
obtained from three runs, where the sparsity level 20. The variances shown in brackets. The configurations the same in Table ((a)
Note that we do not include the results of vanilla sAT and sTRADES since their results are obtained
from 23
Model
SAT S&N
STRADES S&N
Fast-LS-lo (T) Fast-LS-ll (F)
Acc.
61.2 (#: 0.2)
65.5 (# 0.7)
63.0
62.1 (# 0.6)
observed that the fluctuation introduced by different random seeds does not outweigh the performance gain from the evaluated approaches.
F.6 Robustness under Feature-space Attacks
Table 11: Robust accuracy (%) of cominations of our method under feature-space attacks. The model the ResNet-18 trained with Fast-LS-44 on CIFAR-10.
60
Clean Acc.
0-2ero
sPGD,
sPGD..
RS
sAA
Fast-I.S-lo
84.9
64.2
76.6
73.5
58.5
58.3
We train a ResNet with our method in feature space with Etroin 360 and evaluate its robustness under different attacks with e 60. To accommodate the feature-space sparsity, we modify the shape of perturbation mask in sPGD from (b, 1, h, w:) to (b, h, w). Since RS is unable to generate spatuee-space perturbations, we its pixel-space adversarial budget to c/c to ensure the equivalent feature-space budget other attacks. As presented in Table [1 our method can also achieve robustness this setting. In addition, we notice that a-zero outperforms sPGD feature-spart space attacks. Nevertheless, sAA is still the most comprehensive and reliable robustness evaluation method.
E.7 Effectiveness in Improving Fast (,, l2 and 1.0 Adversarial Training
Table 12: Robust accuracy (%) of cominations our method with fast I, 12, and loo adversarial training methods. The results are obtained through the AutoAttack for corresponding norms.
1 (e 12)
l2 (e = 0.5)
4 (c 8/255)
Fast-EG-I1
45.4
GradAlign Ours 63.1
60.2
39.4
Ours
49.2
42.4
We combine our method with fast (, l2, and loc adversarial training methods. Specifically, we use Fast-EG-I, [19] for cases and GradAlign [27] for la and loo cases. The results in Table [2 show that our method enhances robustness all cases. Overall, these findings demonstrate the effectiveness of method in enhancing robustness against different attacks.
F88 Evaluation on Different Networks
Table 13: Robust accuracy (%) of various networks against SAA on CIFASR-10, where the sparsity
level = 20. The networks are adversarially trained with different methods, including 1-step sAT, 1-step sTRADES and the proposed Fast-LS-
PRN-18
ConvNeXi-T
Swin-T
1-step sAT 1- 1-step STRADES
0.0
0.8
0.1
31.0
71.0
43.2
Fast-LS--o
63.0
78.6
58.9
Despite the effectiveness of our method on PreActResNNtt-13 (PRN-18) and ResNet-34, the per- formance of our Fast-LS-lg and its ablations on different networks remains unexplored. In this regard, we further evaluate our method on two popular architectures. i.e.. ConvNeXt (55) and Swin Transformer [56]. Note that we adopt their tiny versions for CIFAR-10 10, which have similar number of parameters as ResNet-18, and we follow the training settings of their CIFAR-10 implementations. The other experimental settings the same as those described in Section 5.1 As shown in Table
23

---

13
vanilla adversarial training results in CO on all networks, and our method produces the best robust accuracy against sAA, demonstrating the effectiveness our method on different networks. Notably, ConvNeXt shows surprisingly strong robustness against sAA, suggesting that advanced architecture design and dedicated hyperparameter tuning can provide additional performance gains. However, as Transformers has struggled to perform well on small datasets without pretraining [57] Swin Transformer also underperforms CNN-based networks in this scenario.
F.9 Loss Landscape of one-step SAT with Different
20
10
0.
0.62
0.02
0.0
0.0
5.01
(a) (0) 20
(b)
40
(c) Cc
120
Figure 5: Loss landscape of 1-step SAT 23 with different values on the training set of CIFAR-10
25]. The architecture of the model is PreactResNet-18. (a) Landscape of C. (x. + a1 1 + v2
with 20, where and d2 are the eigenvectors corresponding to the top 2 eigenvalues of the
Hessian matrices, respectively. (b) Landscape of c! with e 40. (c) Landscape of L! with
e = 120.
As supplementary of Figure we visualize the loss landscapes of 1-step SAT 2 with different including 20, 40 and 120, in Figure It can be observed that the lo adversarial loss exhibits drastic increase in response relatively minor alterations in the O-space. Moreover, the degree of non-smoothness increases in proportion to e, which is consistent with the observation in Figure (a).
F.10 Smoother Loss Landscape Induced by Soft Label and Trade-off Loss Function
The effectiveness of soft label and trade-off loss function in improving the performance of lo adversarial training is demonstrated Section and 5.2 Additionally, we visualize the curves of top-10 eigenvalues of Hessian matrices of the different methods discussed in Section 5.1 and their respective loss landscapes Figure Note that since N-FGSM results in larger upper bound of || d2l1, it is not considered here make fair comparison. Figure 6 (a) shows that STRADES induces considerably smaller eigenvalues of Hessian matrices compared to SAT, while the difference between STRADES (T) and STRADES (F) negligible. SAT, on the other hand, has only marginal effect on the eigenvalues. However, as illustrated in Figure (b)-re))))))())) (b)-(f), SAT plays a crucial role in smoothing the loss landscape, which relates to the change rate of loss, i.e., the first-order smoothness. These observations align with the theoretical derivation presented in Section 4.33 indicating that soft label improves the first-order smoothness, while trade-ofi off loss function contributes the second-orde smoothness.
F11 Ablation Studies
In this section, we conduct more ablation studies on the results in Section 5.1 Specifically, we focus on the best configuration in Table 4 Fast-LS-lo (T) (i.c., 1-step STRADES (T) + SAT & N-FGSM). Unless specified, we adopt the same training settings in Table
Table 14 presents performance comparison of the model when SAT is enable in different training that the performance achieves the best when enabling SAT at the 50-th epoch. This observation demonstrates that the best performance in 1-step STRADES is achieved when SAT enabled the intermediate epoch where the learning rate is relatively low.
phases. We
In Table 15 we compare the performance when using different momentum factor in SAT, We can see that the default setting in [40], i.c., 0.9, provides the best performance.
24

---

1.0
TTT
0.8
T(F)
Value
0.4
20
50
0.2
0.0
8
8:00
Index
0.22
6.01
6.01-101
6.33
(a) Eigenvalues V ((
(b) 1-step SAT
(c) 1-step STRADES (T)
60
50
40
30
10
27
20
20
6:34
1.04
0.54
02
1.2
2.52
40.8
1.02
0.
0.20
-194
3.42
02
0.00
-0.6
0.00
-.00
0.54
0.0
0.04
(d) 1-step STRADES (F)
(c) 1-step STRADES (T) + SAT
(f) 1-step STRADES (F) SAT
Figure Smoothness visualization of different methods with = 120 on the training set of CIFAR-10
(25. The architecture of the model is PreactResNet-188 18. (a) Top- 10 eigenvalues of V (0)
(x. 0) of
different methods. A and denote 1-step SAT and 1-step STRADES, respectively. and in the brackets are two respective versions of sTRADES indicated in Sec. 5.1 (b) Loss landscape of 1-step
SAT. (c) Loss landscape of 1-step STRADES (T). (d) Loss landscape of 1-step STRADES (F). (e)
Loss landscape of 1-step sTRADES (T) SAT. (f) Loss landscape of 1-step sTRADES (F) + SAT.
In Table 16 we compare the performance when using different balance factor 3 in TRADES. It can be observed that = and induce similar results, indicating the default setting in [30] i.c. 6, is the optimal.
In Table 17 compare the performance when using different étrain- It can be observed that when Grain 120, our method achieves the best performance, which is consistent with the observations in Notably, with the assistance of our method, CO does not appear in all settings.
23
Table 14: Ablation study on the epoch of en- abling SAT. The evaluated attack is sAA, where sparsity level
Table 15: Ablation study on the momentum fac- tor of SAT. The evaluated attack is sAA, where the sparsity level 20.
SAT epoch
30
50
70
SAT momentum
0.5
0.7
0.9
Robust Accuracy
60.2
63.0
62.8
Robust Accuracy 55.4
60.4
63.0
Table 16: Ablation study on the balance factor 3 TRADES loss function. The evaluated attack is sAA, where the sparsity level 20.
Table 17: Ablation study Etrain The eval- uated attack sAA, where the sparsity level 20.
TRADES 3
3
Etrain
20
40
120
Robust Accuracy
58.7
63.0
63.0
Robust Accuracy
61.4
62.1
63.0
G Implementation Details
Generally, the epoch of enabling SAT is 1/2 of the total epochs. For N-FGSM, the random noise for augmentation is the random sparse perturbation with sparsity level ranging from 0 to 2e, where the sparsity level of adversarial perturbations. The interpolation factor in trade-off loss function is set to 0.75. The balance factor TRADES loss function is set to 6. The optimizer SGD with momentum factor of 0.9 and weight decay factor of 5 x 10-4, The learning rate is initialized to
25

---

0.05 and is divided by factor of 10 at the 1/4 and 3/4 of the total epochs. The specific settings for different datasets are listed as follows:
CIFAR-10, CIFAR-100 100 (25] and GTSRB [52]] The adopted network is PreAct ResNet- 18 [58
with softplus activation 59 The training batch size 128. We train the model for 100 epochs.
ImageNet- [51] The adopted network ResNet-34 [24 The training batch size is 48. We
train the model for 50 epochs.
Unless specified, the hyperparameters attacks and other configurations are the same in
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: This paper discusses the limitations of the work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairnsss.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
27

---

For each theoretical result, the paper provides the full set of assumptions and complete proof.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
This paper discloses all the information needed for reproduction.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
28

---

Answer: [Yes]
Justification:
This paper provides open access to the code in supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
public/guides/ Stwriidde/CCoeeuubbsssstteee Policy)l for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7
htte//CoooSSSiiieeeeee wwweiisssoonoooni ooic for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: This paper specifies all the training and test details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: This paper report the standard deviation of results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
29

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
This paper provides sufficient information on the computer resources.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///wwrr..cppppaaococccccaaa
Answer: [Yes]
Justification: Ethics.
The research conducted in the paper conforms with the NeurIPS Code of
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The paper discusses broader impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
30

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The creators or original owners of assets, used the paper, are properly credited. The license and terms of use explicitly mentioned and properly respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, datasets..papersstt wwwppppipphhheeeeeoppppppoo thoode. com/ datasets
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
31

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
32

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
33


Reviews:
[{"review_id": "kjzkMC3EwH", "reviewer": "Reviewer_pKXP", "summary": "This paper conducts a systematic study of catastrophic overfitting (CO) in $l_0$ adversarial training. While regularization techniques such as soft labels and trade-off loss functions have been widely used to mitigate robust overfitting in $l_2$ and $l_\\infty$ adversarial settings, this work focuses on analyzing the unique challenges presented by the $l_0$ case. The authors provide both theoretical analysis and extensive empirical results to demonstrate that smoothing the adversarial loss landscape through the use of soft labels and trade-off loss can effectively eliminate CO and significantly improve robustness against sparse $l_0$ attacks, with only a minor impact on standard accuracy. Importantly, the proposed smoothing techniques also substantially reduce the robustness gap between one-step and multi-step adversarial training, thereby making fast adversarial training much more practical and effective in the $l_0$ setting.", "questions": "1.\tHow sensitive is the performance to the choice of hyperparameters in the trade-off loss and label smoothing?\n\n2.\tThe paper provides a detailed analysis of the differences between catastrophic overfitting in the $l_0$ setting and in the $l_2$/$l_\\infty$ cases. Given these newly identified distinctions and the theoretical formulas presented, have the authors considered or explored any new or specifically tailored solutions for the $l_0$ case, beyond directly applying existing regularization methods? More dicussions are expected.", "limitations": "YES", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n•The paper addresses an underexplored and practically important problem: catastrophic overfitting(CO) in $l_0$ adversarial training.\n\n•Theoretical analysis offers new insights about the discrete and highly non-smooth nature of the $l_0$ loss landscape.\n\n•Experiments are thorough and well-controlled, reporting both robust and clean accuracy, and ablation studies confirm the effectiveness of regularization techniques.\n\nWeaknesses:\n\n•The techniques (soft label, trade-off loss) appear  not new and have been extensively studied in the context of $l_2$/$l_\\infty$ adversarial training.\n\n•The main contribution is a systematic analysis and empirical demonstration of these techniques’ value in the $l_0$ setting, rather than proposing fundamentally new methods.\n\n•Some practical aspects, such as hyperparameter sensitivity, could be discussed in more detail.", "was_revised": true, "final_justification": "Thank the authors for the response which addressed many of my concerns. While I am still a bit unconvinced by the novelty, I think this paper is a good contribution to the community. I will keep my positive rating.", "rebuttal": "Thanks for acknowledging that the theoretical analysis is insightful and the experiments are thorough and well-controlled. We provide point-to-point responses to your concerns as follows:\n\n---\n\n**W1: The techniques appear not new and have been extensively studied.**\n\n**Reply:**  We clarify that the rationale for using soft labels and trade-off loss functions is different for $l_0$ cases, since we point out that existing CO mitigation methods for $l_1$, $l_2$ and $l_\\infty$ cases turn out to be insufficient to address the CO issue in $l_0$ cases. Smoothing the loss function can help boost the performance for $l_1$, $l_2$ and $l_\\infty$ cases, as the goal of soft label and trade-off loss function is to address robust overfitting to boost performance. By contrast, smoothing the loss function is **essential** to address the CO issue in $l_0$ cases.\n\n---\n\n**W2: The main contribution is a systematic analysis and empirical demonstration of these techniques’ value in the l_0 setting, rather than proposing fundamentally new methods**\n\n**Reply:** The main contribution of this work is **highlighting the challenge of fast $l_0$ adversarial training (AT) is different from the $l_1$, $l_2$ and $l_\\infty$ counterparts**, specifically the suboptimal perturbation location. **To the best of our knowledge, this is a novel finding**. Although the multi-$\\epsilon$ strategy can help alleviate this suboptimality by perturbing more pixels, it causes a craggy loss landscape. In this context, soft labels and trade-off loss functions are proposed to smooth the loss landscape. However, we acknowledge that our solution is mostly intuitive and may have room for improvement. We will leave further methodology improvement as a future work.\n\n---\n\n**W3: Some practical aspects, such as hyperparameter sensitivity, could be discussed in more detail.**\n\n**Reply:**  We have conducted a comprehensive ablation study on hyperparameters in Appendix F.10, the results indicate that our method is robust to different hyperparameters. Results in Table 13, 14, 15 and 16 indicate that our method can always achieve competitive performance, similar to the multi-step counterpart, as long as the hyper-parameters are set reasonable values. In addition, no case in these results in ablation study suffers from CO, validating the stability of our method.\n\n---\n\n**Q1: How sensitive is the performance to the choice of hyperparameters in the trade-off loss and label smoothing?**\n\n**Reply:** Please see the response to W3.\n\n---\n\n**Q2: Have the authors considered or explored any new or specifically tailored solutions for the l_0 case, beyond directly applying existing regularization methods?**\n\n**Reply:** In this work, we mainly focus on exploring the common solution to mitigate CO in fast $l_0$ adversarial training, and find the combination of TRADES and SAT, which improves both 1st and 2nd Lipschitz smoothness, performs the best. Despite intuitive, extensive experiments validate the effectiveness of our method in various tasks and models. **We believe that the motivation of smoothing loss landscape and our exemplary methods can be broadly applied in the situations where we need to efficiently robustify the model against a kind of sparse perturbations**. Nevertheless, we acknowledge the necessity to develop specifically tailored method for the $l_0$ case to further boost the performance and will leave it as the future work.\n\n---\n\n**We hope these responses can address your concerns and look forward to your feedback.**"}, {"review_id": "0vasPnWtBf", "reviewer": "Reviewer_GeaB", "summary": "This paper investigates the problem of catastrophic overfitting in fast adversarial training under $\\ell_0$-norm bounded perturbations. The authors argue that single-step adversarial training methods, which have shown promise under $\\ell_\\infty$ and $\\ell_2$ norms, fail to generalize when the threat model is defined under $\\ell_0$ constraints. Through both theoretical analysis and empirical validation, the paper identifies that catastrophic overfitting in this regime is due to the sub-optimal selection of perturbation locations, rather than their magnitudes. The authors further demonstrate that the non-convex nature of the $\\ell_0$ space leads to a bumpy loss landscape, rendering training more unstable. To address this, they introduce Fast-LS-$\\ell_0$, which reduces the computational complexity of adversarial training by leveraging a one-step $\\ell_0$ attack, while still achieving robustness comparable to multi-step $\\ell_0$ adversarial training.", "questions": "Is the perturbation budget $\\epsilon$ defined over pixels or feature channels?\n\nHow does Fast-LS-$\\ell_0$ perform on larger and distinct architectures?\n\nGiven the non-convexity of the $\\ell_0$ constraint space, how can we be confident that the proposed one-step perturbation method sufficiently explores the adversarial landscape during training?", "limitations": "Yes, partially. The limitations are presented in the appendix, while it would be more transparent and valuable to discuss them in more detail in the main paper.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper, in general, is well-written and coherent in its presentation. The authors clarify the fundamental question posed at the state of the art and propose multiple ways to understand the phenomenon, subsequently attempting to provide a possible solution to the catastrophic overfitting issue in $\\ell_0$-norm adversarial training. The paper employs a tutorial writing style, making it easy to follow. However, it would require some improvements that, at the current status, are limiting its impact.\n\n+ **Experimental coverage.** The experiments conducted by the authors consider only small case convolutional neural networks. Specifically, for CIFAR-10, they consider PreActResNet-18, and for ImageNet, only ResNet-34. Both networks are definitely small in the number of parameters and it remains unclear whether the same argumentation persists when increasing the number of parameters, giving thus more degrees of freedom to the network during training, or whether a different architecture is required (e.g., ViT). Moreover, this becomes much more relevant when considering that the majority of the empirical observations and results are observed only at CIFAR-10 with PreActResNet-18.\n\n\n+ **Verification attack**. The major algorithm utilized by the authors to assess robustness in the $\\ell_0$ norm threat model is Sparse AutoAttack (sAA), defined as an ensemble of other $\\ell_0$ attacks. However, the attacks defined in sAA have been shown to be less reliable compared to more recent works [a]. Furthermore, [a] has been conceived as a minimum-norm attack with an approximated $\\ell_0$ loss function, meaning that it would look for complementary directions not observed and investigated in the actual attacks. For completeness of the results, both sAA and [a], should be included in the evaluation of robustness. Table 5, for example, reports the results when considering two versions of sPGD, which hold similar results and are already included in sAA. The authors could include [a] as a more advanced baseline of verification and replace it with sPGD_p, which yields less effective results. \n\n[a] σ-zero: Gradient-based Optimization of 𝓁-norm Adversarial Examples ICLR 2025.\n\nThe above ones are considered the main lack related to this paper. The following are observations that can be more easily clarified by the authors.\n\n+ **need for fast adversarial training** the authors base their paper on the observation that running adversarial training with a multi-iterative attack (e.g., sPGD with 20 step iterations) is computationally challenging. How is this due to the intrinsic complexity of the attack itself? In practice, if the attack is fast, having more internal iterations should not be the bottleneck of the training pipeline. \n\n+ **need for clarification**. In the numerical validation (section 4.2) the authors compute the eigenvalues of the Hessian matrix $\\nabla^2_\\theta L$ and visualize them in Figure 3. However, they do not specify their role or the stage at which these eigenvalues are computed during the training epochs. Are they done at the convergence of the training algorithm? The authors mention they are connected with the non-smoothness of the loss landscape, in which measure? Can the authors provide more details on that? Similarly, how are Figures 3(c-f) implemented in detail? The pseudocode released by the authors does not seem to contain this part of the paper.\n\nMinor observations: \n- Tradeoff loss function. The tradeoff loss function introduced involves a min-max optimization problem, which may increase the complexity of the procedure if the inner maximization problem is not computed in a closed form. Can the authors expand on this point? How is it implemented?\n\n- The paper uses both \"tradeoff\" and \"trade-off\" terms. \n\n- It seems that the budget $\\epsilon$ is expressed in terms of features, not pixels. At least this is what I understood from line 207 and the footnote on page 6. Can you please make it more explicit in the paper?\n\n**Conclusions**\nThe paper offers a fascinating exploration of catastrophic overfitting in adversarial norm $\\ell_0$ training and introduces Fast-LS-$\\ell_0$ as an efficient alternative. The paper is primarily based on empirical observations and intuitions. However, its generalizability is limited by the narrow experimental coverage, which focuses on small models, and the use of solely sAA as the primary robustness checker, despite the availability of complementary and reliable alternatives. In essence, to improve the paper, the authors should expand the evaluations to larger architectures, incorporate stronger verification attacks, and address the above-mentioned minor issues.", "was_revised": true, "final_justification": "The authors clarified their contributions, experimental setup, and included the necessary comparisons that were missing and that I had requested in my initial review. Therefore, I increased my score.", "rebuttal": "We appreciate your effort in reviewing and thank you for mentioning our paper is well-written. We provide point-to-point responses to your concerns as follows:\n\n---\n\n**W1: Experimental coverage**\n\n**Reply:**  Apart from PreActResNet-18 and ResNet-34, we also verify the effectiveness of our method on more advanced architectures, e.g., ConvNeXt and Swin-Transformer (a variant of ViT), in Table 12 of Appendix F.7.\n\n---\n\n**W2: Verification attack**\n\n**Reply:** Thanks for your constructive suggestion, we will include $\\sigma$-zero in our revised manuscript.We report the robust accuracy of the evaluated methods in Table 5 under $\\sigma$-zero below. Notably, $\\sigma$-zero was originally designed to generate perturbations in feature space, we adapt it to the pixel space to accommodate our experiment settings for fair comparison. The results show that $\\sigma$-zero achieves lower attack success rate than sAA in the pixel space, because the decoupling mechanism of perturbation location and magnitude may make sAA more advantageous in generation of structured sparse perturbations. In summary, **the model efficiently trained by our method is still robust against $\\sigma$-zero and sAA is a more effective attack for our models**.\n\n| CIFAR-10 | sAT | sAT+S&N | sTRADES | sTRADES+S&N | Fast-LS-$l_0$ |\n| --- | --- | --- | --- | --- | --- |\n| Clean Acc. | 84.5 | 80.8 | 89.8 | 82.8 | 82.5 |\n| sAA | 36.2 | 61.0 | 61.7 | 65.5 | 63.0 |\n|$\\sigma$-zero | 79.8 | 78.7 | 85.9 | 77.0 | 73.7 |\n\n| ImageNet-100 | sAT | sAT+S&N | sTRADES | sTRADES+S&N | Fast-LS-$l_0$ |\n| --- | --- | --- | --- | --- | --- |\n| Clean Acc. | 86.2 | 83.0 | 84.8 | 82.4 | 82.4 |\n| sAA | 61.2 | 74.8 | 75.8 | 77.8 | 72.4|\n|$\\sigma$-zero | 78.6 | 80.8 | 81.6 | 80.0 | 74.0 | \n\n---\n\n**W3: Need for fast adversarial training**\n\n**Reply:** Black-box attacks are weaker than white-box attacks and cannot be employed for adversarial training. For white-box attacks, each iteration has at least one forward and one backward propagation. Since the attack we used in adversarial training has only one forward and one backward propagation at each iteration, **the intrinsic complexity cannot be further reduced**.\n\n---\n\n**W4: Need for clarification**\n\n**Reply:**\n\n- We compute these eigenvalues based on the final checkpoint, where the model parameters already converge.\n- The non-smoothness can be measured by the curvature of loss landscape indicated by the largest eigenvalues of Hessian matrix as indicated in [1].\n- As illustrated by the caption of Figure 3, the loss landscape is drawn based on $\\mathcal{L}_{\\epsilon} (x, \\theta + \\alpha_1 v_1+ \\alpha_2 v_2)$ where $v_1$ and $v_2$ are the eigenvectors associated with the top 2 eigenvalues of Hessian matrix. $\\alpha_1$ and $\\alpha_2$, and the loss value are the x-, y-, and z-axis, respectively.\n- Note that we employ the power method [2] to iteratively estimate the eigenvalues and the corresponding eigenvectors of Hessian matrices.\n\n---\n\n**W5: Tradeoff loss function**\n\n**Reply:** Both adversarial training loss and trade-off loss involve max operator, training based on these loss functions is a min-max optimization. In both cases, we cannot find the closed form of the inner max, because of the high-dimensional non-convex loss function of neural networks. In practice, using methods like PGD can well approximate the inner max for the outter min operation [3], but it is computionally expensive. This motivates us to develop fast adversarial training, which utilizes one-step attack to generate adversarial samples efficiently for robust learning. **Our work shows that for $l_0$ bounded adversarial perturbations, we can smooth the loss landscape so that we can use efficient but weak one-step sparse attacks to reliably train model robust against sparse perturbations without the worry of CO.**\n\n---\n\n**W6: The paper uses both \"tradeoff\" and \"trade-off\" terms.**\n\n**Reply:** Thanks for pointing this out. We will unify the terminology in the revised version.\n\n---\n\n**W7: It seems that the budget is expressed in terms of features, not pixels. At least this is what I understood from line 207 and the footnote on page 6. Can you please make it more explicit in the paper?**\n\n**Reply:** Sorry about the confusion. Following the setting of previous work [4], the adversarial budget used in the experiment part is considered in the pixel space. However, in line 207 and the footnote on page 6, the mentioned $l_0$ norm is calculated in feature space for a fairer comparison. We will clarify this point in the revised version.\n\n---\n\n**Q1: Is the perturbation budget $\\epsilon$ defined over pixels or feature channels?**\n\n**Reply:** Please see the response to W7.\n\n---\n\n**Q2: How does Fast-LS-l0 perform on larger and distinct architectures?**\n\n**Reply:** Please see the response to W1.\n\n---\n\n**Q3: Given the non-convexity of the $l_0$ constraint space, how can we be confident that the proposed one-step perturbation method sufficiently explores the adversarial landscape during training?**\n\n**Reply:** We demonstrate the **suboptimal location** of perturbations generated by one-step attack is due to the non-convexity of the $l_0$ adversarial budget. Furthermore, we find that **this issue can be mitigated to some extent by multi-$\\epsilon$ strategy**.  The effectiveness of multi-$\\epsilon$ strategy is proven in previous work [4]. However, as illustrated in Figure 1, a larger $\\epsilon_{train}$, in turn, leads to unstable training and degraded clean accuracy. Therefore, we utilize **trade-off loss function** and **soft labels** to smooth the landscape. Our method achieves competitive robustness against $l_0$ attacks. Similar to previous literatures, we employ the strongest existing attack method (e.g. sAA, $\\sigma$-zero) to evaluate the robustness of the model trained by our method, indicating that the one-step attack is sufficient to explore the adversarial loss landscape to robustify the model.\n\n---\n\n**We hope our responses can address your concerns in the review above and look forward to your feedback. We will appreciate it if you can increase the rating after reading our rebuttal if your concerns are addressed.**\n\n[1] Chen Liu et al. On the loss landscape of adversarial training: Identifying challenges and how to overcome them. NeurIPS 2020.\n\n[2] Zhewei Yao et al. Hessian-based analysis of large batch training and robustness to adversaries. NeurIPS 2018.\n\n[3] Aleksander Madry et al. Towards deep learning models resistant to adversarial attacks. ICLR 2018.\n\n[4] Xuyang Zhong et al. Towards Efficient Training and Evaluation of Robust Models against $l_0$ Bounded Adversarial Perturbations. ICML 2024."}, {"review_id": "8u9c4rklol", "reviewer": "Reviewer_c9Ts", "summary": "This work presents the first study of $\\ell_0$ fast adversarial training. The authors demonstrate that existing catastrophic overfitting (CO) mitigation techniques, such as random initialization, fail in the $\\ell_0$ setting. They attribute this failure to the fact that perturbations generated by 1-step $\\ell_0$ training are sub-optimal in terms of location rather than magnitude. While multi-$\\epsilon$ strategies can address this issue, they lead to unstable training and degraded clean accuracy. The authors further show that $\\ell_0$ adversarial loss creates a more rugged landscape compared to other $\\ell_p$ norms, complicating the training process. To address these challenges, they propose combining soft labels with a trade-off loss function to smooth the loss landscape and mitigate CO.", "questions": "I believe the contributions of this research are sufficient for acceptance. The issues raised in Weaknesses represent minor gaps or questions in the detailed discussions within the study, and do not significantly diminish the research's significance.\n\nThe reason I did not assign a Strong Accept is due to the contribution being in the somewhat minor area of $\\ell_0$ norm adversarial training combined with fast strategies, compared to $\\ell_2$ or $\\ell_\\infty$. I believe increasing the rating on this aspect would be difficult, so the authors need not feel compelled to address this in their rebuttal.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n- The paper provides comprehensive experimental evidence that $\\ell_0$ fast adversarial training exhibits fundamentally different behavior from existing fast adversarial training methods. The insights regarding location-based sub-optimality and rugged loss landscapes offer valuable contributions to future research in $\\ell_0$ fast adversarial training.\n- The proposed method achieves high robustness while maintaining computational efficiency.\n\n**Weaknesses**\n\n**1. Theoretical Analysis (Section 4.1)**\n\n*1.1* The scope of applicability for the results in Section 4.1 requires clarification. For which values of $p$ do these theorems hold? Is it $p \\in [0, \\infty]$ or $p \\in [1, \\infty]$? The description in lines 204-205 creates confusion regarding the theorem's applicability. Specifically, it is crucial to specify which $\\ell_p$ norm is used to compute $\\\\|\\delta_1 - \\delta_2\\\\|$. If these theorems cannot be applied to the $\\ell_0$ norm, the relevance of this section to the paper's main focus is unclear.\n\n*1.2* Theorem 4.4 provides an upper bound on gradient variation. This does not always describe the actual magnitude of gradient variation (just upper bound). Thus, this does not rigorously establish that the gradient changes are non-smooth or rugged.\n\n*1.3* The term $B_{\\theta\\delta}$, particularly the component $\\\\|\\delta_1 - \\delta_2\\\\|$, is presented as a measure of discontinuity. However, this requires additional discussion about how significantly $\\delta_1$ and $\\delta_2$ can vary in response to differences between $\\theta_1$ and $\\theta_2$. Local changes in $\\theta$ may result in no change in $\\delta$ under the $\\ell_0$ norm. Understanding the extent to which the loss landscape ($\\theta$ space) contains regions that destabilize training appears crucial for the analysis.\n\n**2. Numerical Validation (Section 4.2)**\n\n*2.1* In Section 4, the authors claim that rugged landscapes cause or accelerate CO, as stated in line 234: \"the craggy loss landscape aggravates CO.\" However, the study only demonstrates that $\\ell_0$ adversarial loss landscapes are rugged and that CO occurs in $\\ell_0$ adversarial training as separate phenomena. The causal relationship—whether rugged landscapes actually aggravate CO—remains unestablished. While I agree that rugged loss landscapes complicate training, the direct connection to CO requires more evidence (or explanation).\n\n*2.2* When comparing $\\ell_0$ norms with other $\\ell_p$ norms, the appropriate selection of $\\epsilon$ values is unclear, though this limitation is inherent to the nature of $\\ell_p$ norms. In Figure 3(c), the relatively rugged appearance of the $\\ell_0$ landscape may result from $\\epsilon = 1$ being exceptionally strong compared to other attacks. Indeed, $\\ell_0$ attacks should be considerably more powerful than other attacks in terms of local magnitude.\n\n**Question**\n\nThe contribution of N-FGSM appears relatively modest in the results. Does this suggest that location-based sub-optimality has limited negative impact, or do other methods automatically address this issue?", "was_revised": true, "final_justification": "Since the author has clearly addressed my concern, I will maintain my original rating.", "rebuttal": "We really appreciate you acknowledge that our work is sufficient for acceptance. We provide point-to-point responses to your concerns as follows:\n\n--- \n\n**W1.1: For which values of $p$ do these theorems hold? Is it $p \\in [0, \\infty]$ or $p \\in [1, \\infty]$?**\n\n**Reply:** Sorry for the confusion, we will clarify this in the revised manuscript. The norm in the theorems in Sec. 4.1 (i.e., Inequality [2 - 7]) should be $l_p$ norm with $p\\in [1,\\infty]$ since the $l_p$ norm should be a proper norm in these theorems. However, the theoretical analyses can also be applied to the cases of $l_0$-bounded perturbations, because it is feasible to compute the $l_p$ norm ($p\\in [1,\\infty]$) upper bound of these $l_0$ bounded perturbations. The detailed discussion about the upper bound of $||\\delta_1-\\delta_2||$ is conducted in Appendix E.\n\n--- \n\n**W1.2: Theorem 4.4 provides an upper bound on gradient variation. This does not always describe the actual magnitude of gradient variation (just upper bound).**\n\n**Reply:** Apart from providing the upper bound of gradient variation, we numerically validate the rugged landscape of $l_0$ adversarial training loss in Sec. 4.2, where we see consistent observations with the theorems. Moreover, the derived bounds are tight since the upper bound can be achieved asymptotically when the equalities in Assumption 4.1 and Eq. 14 are achieved.\n \n--- \n\n**W1.3: Local changes in $\\theta$ may result in no change in $\\delta$ under the $l_0$ norm.**\n\n**Reply:** We have discussed the worst-case $||\\delta_1-\\delta_2||$ in Appendix E. To further validate this, we supplement with a numerical experiment here. \n\nSimilar to Figure 3 (c)-(f), we perturb the parameter $\\theta$ with $\\alpha \\times v_1$, where $v_1$ is the eigenvector associated with largest eigenvalue of Hessian matrix and $\\alpha$ is a small constant. As shown in the table below, even when $\\alpha=0.0001$, $|| \\delta_1 - \\delta_2 ||_2$ is not negligible. Due to the high dimensionality of the model parameter $\\theta$, the adversarial perturbation from the attack changes even with small changes in $\\theta$.\n\n| | $\\theta - 0.0003 \\cdot v_1$ | $\\theta - 0.0002 \\cdot v_1$ | $\\theta - 0.0001 \\cdot v_1$ | $\\theta + 0.0001 \\cdot v_1$ | $\\theta + 0.0002 \\cdot v_1$ | $\\theta + 0.0003 \\cdot v_1$ | \n| --- | --- | --- | --- | --- | --- | --- |\n| $\\| \\| \\delta_1-\\delta_2\\| \\|_2$ | 8.31 | 8.32 | 8.32 | 8.34 | 8.32 | 8.32 |\n\n\n--- \n\n**W2.1: The causal relationship—whether rugged landscapes actually aggravate CO—remains unestablished.**\n\n**Reply:**  In Sec. 4.2, we corroborate the relationship between CO and rugged landscape using the example of **early stopping (ES) strategy in multi-step attack**, where ES can circumvent the potential for excessive gradient magnitude while maintaining the efficacy of the generated perturbations. As illustrated in Figure 4 of Appendix F.1, **CO also occurs at the multi-step adversarial training without ES**, indicating a strong correlation between CO and craggy loss landscape.\nWe will clarify this point in a clearer way in the revised version.\n\n--- \n\n**W2.2: The appropriate selection of  $\\epsilon$ values is unclear**\n\n**Reply:** In the experiment part, we use the same $\\epsilon$ value adopted in the previous work [1] for fair comparison. However, in Sec. 4.2, we use $\\epsilon=1$ to specifically exhibit the craggy nature of landscape in the $l_0$ case. Additionally, $||\\delta_1-\\delta_2||_2$ of $l_0$-bounded perturbations when $\\epsilon=1$ could be 1 in the worst case, which is much larger than the common used 0.5 in the $l_2$ case.\n\n--- \n\n**Q1: The contribution of N-FGSM appears relatively modest in the results. Does this suggest that location-based sub-optimality has limited negative impact, or do other methods automatically address this issue?**\n\n**Reply:**  As demonstrated in Sec. 3.2, CO is caused by the **suboptimal location** of perturbations in the $l_0$ case. Furthermore, we find that **this issue can be mitigated to some extent by multi-$\\epsilon$ strategy**, and its effectiveness is proven in the previous work [1]. However, as illustrated in Figure 1, a larger $\\epsilon_{train}$, in turn, leads to unstable training and degraded clean accuracy. Therefore, we utilize **trade-off loss function** and **soft labels** to smooth the landscape, thereby achieving competitive robustness against $l_0$ attacks. In a similar way, N-FGSM contributes since it augments the original images with random noise, thereby covering more perturbation location. N-FGSM can be considered as a kind of data augmentation and has some smoothing effect.\n\n---\n\n**We hope our responses can address your concerns.**\n\n[1] Xuyang Zhong et al. Towards Efficient Training and Evaluation of Robust Models against $l_0$ Bounded Adversarial Perturbations. ICML 2024."}, {"review_id": "xcut9VnihW", "reviewer": "Reviewer_VsK8", "summary": "This paper investigates catastrophic overfitting (CO) in 1-step adversarial training against sparse (l0-bounded) perturbations. The authors identify that CO arises from suboptimal perturbation locations (rather than magnitudes) in 1-step attacks and attribute this to the non-convex, \"craggy\" loss landscape of l0 adversarial training. To mitigate CO, they propose smoothing the loss landscape using soft labels (via self-adaptive training, SAT) and a trade-off loss (via TRADES), combined with noisy data augmentation (N-FGSM). The resulting method, Fast-LS-l0, reportedly narrows the performance gap between 1-step and 20-step adversarial training while reducing computational cost.", "questions": "N/A", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. Problem Significance: Addresses an underexplored but relevant challenge—efficient adversarial training for l0 attacks—with clear practical implications for real-world sparse perturbations.\n\n2. Theoretical Analysis: Provides a rigorous Lipschitz-based analysis comparing the smoothness of l0 loss landscapes to lp (p≥1) norms, reinforcing the claim that non-convexity exacerbates CO.\n\n3. Comprehensive Experiments: Evaluates across multiple datasets (CIFAR-10/100, ImageNet-100, GTSRB) and architectures (ResNet, ConvNeXt, Swin-T), demonstrating robustness gains.\n\n\nWeaknesses:\n1. Limited Novelty: The core techniques (SAT, TRADES, N-FGSM) are repurposed from prior work without significant innovation. The combination is heuristic, lacking a principled justification for why these methods synergize uniquely for l0. Claims of being \"the first\" to study fast l0 training are overstated: [19, 23] explicitly address l1/l0 efficiency, and the solution (loss smoothing) is adapted from l2/l∞ literature. And [S1] which uses hamiltonian monte carlo for generation diversity with few steps can also be easily adapted to l0 training. Here should be further discussed or shown comparison with releveant works.\n\n2. Technical Flaws in Presentation: Theorem 4.2 assumes \\(\\mathcal{S}_+ = \\{i \\mid y_i > 0, h_i(\\cdot) > h_i(\\cdot)\\}\\) without clarifying edge cases (e.g., \\(y_i = 0\\)). Appendix B.1 contains informal bounds (e.g., Eq. 13) lacking rigorous derivation.  \n\n3. Marginal Practical Improvement: Fast-LS-\\(l_0\\) still lags >15% behind multi-step sTRADES in robust accuracy on CIFAR-10 (Table 5a) and exhibits high variance (Table 10). The 6× speedup is negated by the performance drop, limiting real-world applicability.  \n\n4. CO mitigation is inconsistent: Table 4 shows CO persists in some configurations (e.g., Tradeoff+N), and larger \\(\\epsilon_{\\text{train}}\\) (Sec. 3.2) destabilizes training.  \n\n[S1] Wang, H., Li, G., Liu, X., & Lin, L. (2020). A Hamiltonian Monte Carlo method for probabilistic adversarial attack and learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(4), 1725-1737.", "was_revised": true, "final_justification": "Since the authors has solved my concerns, I will keep my positive score.", "rebuttal": "Thanks for acknowledging that the theoretical analysis is rigorous and the experiments are comprehensive. We provide point-to-point responses to your concerns as follows:\n\n---\n\n**W1: Limited Novelty**\n\n**Reply:**  The main contribution of this work is **highlighting the challenge of fast $l_0$ adversarial training (AT), specifically the suboptimal perturbation location. To the best of our knowledge, this is a novel finding**. Moreover, the rationale for using soft labels and trade-off loss functions is different for $l_0$ cases, since we point out that existing CO mitigation methods for $l_1$, $l_2$ and $l_\\infty$ cases turn out to be insufficient to address the CO issue in $l_0$ cases. Smoothing the loss function can help boost the performance for $l_1$, $l_2$ and $l_\\infty$ cases, as the goal of soft label and trade-off loss function is to address robust overfitting to boost performance. By contrast, smoothing the loss function is **essential** to address the CO issue in $l_0$ cases.\n\nIt should be noted that [19] investigated fast $l_1$ adversarial training. However, $l_1$ adversarial budget is convex and not strictly sparse, so it is a completely different task. In addition, [23] proposed $l_0$ attack, which does not involve the fast adversarial training: the algorithm it proposes suffers from huge computational overhead. \n\nMoreover, we  included the comparison with other methods in Table 2. According to your suggestion, we further test [S1] in the fast $l_0$ adversarial training. However, CO occurs since it incorporates neither trade-off loss function nor soft labels.\n\n---\n\n**W2: Technical Flaws in Presentation**\n\n**Reply:** Thanks for pointing this out. We would like to clarify that $y_i=0$ does not change the solution of our theorems, because the Eq. 12 still holds when $y_i=0$. Nevertheless, we will modify this expression to make it less confusing.\n\nIn Eq. 13, we derive the upper bound of the term on the right of Eq. 12 according to the mediant inequality. Note that the bound on the right of (13) is tight. The upper bound can be achieved asymptotically if the condition in (14) and the Lipschitz bound in Assumption 4.1 are satisfied.\n\n---\n\n**W3: Marginal Practical Improvement**\n\n**Reply:** It can be observed from Table 5a and 10 that the robust accuracy of Fast-LS-$l_0$ and multi-step sTRADES against sAA are 63.0% and 61.7%, respectively. **This indicate that the effectiveness of our method is comparable to the multi-step variants**. This is also true for other models and datasets, like the results in Table 5b. Additionally, the variance of Fast-LS-$l_0$ is 0.7%, which is small and does not outweigh the performance gain.\n\n---\n\n**W4: CO mitigation is inconsistent**\n\n**Reply:** As demonstrated in Sec. 3.2, CO is caused by the **suboptimal location** of perturbations in the $l_0$ case. Furthermore, we find that **this issue can be mitigated to some extent by multi-$\\epsilon$ strategy**, and its effectiveness is proven in the previous work [1]. However, as illustrated in Figure 1, a larger $\\epsilon_{train}$, in turn, leads to unstable training and degraded clean accuracy. Therefore, we utilize **trade-off loss function** and **soft labels** to smooth the landscape, thereby achieving competitive robustness against $l_0$ attacks. In a similar way, N-FGSM contributes since it augments the original images with random noise, thereby covering more perturbation location.\n\nMoreover, it should be noted that Tradeoff is the naive trade-off loss function, which **only** improves the second-order Lipschitz smoothness, the first-order Lipschitz can still be high. To mitigate CO, we need elements to boost **both** first-order and second-order smoothness. In this regard, we find the best combination is TRADES+SAT+N-FGSM, which incorporates both trade-off loss function and soft labels.\n\n---\n\n**We hope our responses can address your concerns.**"}]

Author rebuttal:

Meta-review: Thanks for submitting to NeurIPS 2025. The paper studies the ineffectiveness of 1-step adversarial training against $l_0$ bounded perturbations. The craggy loss landscape of $l_0$ adversarial training is identified as the major cause. The paper then proposes soft labels and trade-off loss function to smooth the landscape and achieve strong robustness against $l_0$ perturbations within the 1-step adversarial training scheme. Reviewers are overall positive about the paper, especially after the discussion phase where authors put a diligent effort to address concerns on experimental evaluation and theoretical foundations. After the discussion phase, all reviewers are positive. There are some minor concerns about novelty but not critical. We recommend acceptance. Congratulations! Authors should incorporate the reviews and responses in the camera-ready version.
Decision: Accept (poster)