Understanding and Improving Fast Adversarial Training against $l_0$ Bounded Perturbations

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:

W1: Limited Novelty

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.

It 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.

Moreover, 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.

W2: Technical Flaws in Presentation

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.

In 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.

W3: Marginal Practical Improvement

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.

W4: CO mitigation is inconsistent

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.

Moreover, 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.

We hope our responses can address your concerns.

We really appreciate you acknowledge that our work is sufficient for acceptance. We provide point-to-point responses to your concerns as follows:

W1.1: For which values of $p$ do these theorems hold? Is it $p \in [0, \infty]$ or $p \in [1, \infty]$?

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.

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).

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.

W1.3: Local changes in $\theta$ may result in no change in $\delta$ under the $l_0$ norm.

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.

Similar 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$.

W2.1: The causal relationship—whether rugged landscapes actually aggravate CO—remains unestablished.

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. We will clarify this point in a clearer way in the revised version.

W2.2: The appropriate selection of $\epsilon$ values is unclear

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.

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?

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.

We hope our responses can address your concerns.

[1] Xuyang Zhong et al. Towards Efficient Training and Evaluation of Robust Models against $l_0$ Bounded Adversarial Perturbations. ICML 2024.

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:

W1: Experimental coverage

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.

W2: Verification attack

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.

W3: Need for fast adversarial training

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.

W4: Need for clarification

Reply:

• We compute these eigenvalues based on the final checkpoint, where the model parameters already converge.
• The non-smoothness can be measured by the curvature of loss landscape indicated by the largest eigenvalues of Hessian matrix as indicated in [1].
• 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.
• Note that we employ the power method [2] to iteratively estimate the eigenvalues and the corresponding eigenvectors of Hessian matrices.

W5: Tradeoff loss function

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.

W6: The paper uses both "tradeoff" and "trade-off" terms.

Reply: Thanks for pointing this out. We will unify the terminology in the revised version.

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?

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.

Q1: Is the perturbation budget $\epsilon$ defined over pixels or feature channels?

Reply: Please see the response to W7.

Q2: How does Fast-LS-l0 perform on larger and distinct architectures?

Reply: Please see the response to W1.

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?

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.

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.

[1] Chen Liu et al. On the loss landscape of adversarial training: Identifying challenges and how to overcome them. NeurIPS 2020.

[2] Zhewei Yao et al. Hessian-based analysis of large batch training and robustness to adversaries. NeurIPS 2018.

[3] Aleksander Madry et al. Towards deep learning models resistant to adversarial attacks. ICLR 2018.

[4] Xuyang Zhong et al. Towards Efficient Training and Evaluation of Robust Models against $l_0$ Bounded Adversarial Perturbations. ICML 2024.

4. Difference between $l_0$ pixel-space threat model and $l_1$ threat model

Reply: We would like to highlight that the $l_1$-bounded perturbations are not strictly sparse [1]. What is even worse, as indicated in [1], strong $l_1$ bounded adversarial attackers such as AA-l1 [2] tend to exploit non-sparse perturbations bounded by $l_1$ norms to successfully attack the model.

Furthermore, $l_0$ bounded sparse perturbations are quite common in the physical world. Examples include dirt or sticker on a road sign, abnormal LED pixels and token replacement in a sentence. The sparse perturbations in these examples have their specific structures and can be better modeled by strict $l_0$ constraints instead of $l_1$ ones. Therefore, we believe the problems we study in this work have rich realistic applications, the methods we propose can be customized for broad downstream applications.

Finally, the optimization under the $l_0$-norm constraint is challenging due to its non-convex nature. Methods for $l_1$, $l_2$ and $l_\infty$ bounded perturbations are usually invalid for $l_0$ perturbations. Therefore, research on the robustness against sparse adversarial attacks is also of great practical significance.

5. Certified robustness

Reply: Thanks for your suggestion. We only implement [b] since the source code for [a] is not available. However, we cannot certify the robustness of adversarially trained models, including the baselines in Table 5 and our methods, under the setting of [b]. The observation is consistent with $l_2$, $l_\infty$ cases. We provide our clarifications as follows:

(a) There's a key distinction between certified robustness and empirical robustness, plain adversarial training usually only achieves the latter. Certified robustness establishes a lower bound on a model's true robustness, whereas empirical robustness establishes an upper bound on the true robustness. In this context, low certified robustness may arise from the certification algorithm's incapability to tightly bound the model's output. Extensive literature has indicated that the certification method needs to adapt to the training algorithm to achieve competitive performance; otherwise, it usually has trivial results. For example, the model trained by IBP [3] cannot be certified by CROWN [4] and vice versa. Specifically, models obtained by adversarially training, despite high empirical robustness, have almost zero certified robustness. This phenomenon is broadly observed in $l_2$ and $l_\infty$ cases [3, 4, 5, 6]. The results in $l_0$ cases turn out consistent.

(b) The setting of [b] is not applicable to adversarial training. The analysis in [b] relies on randomized smoothing. For example, in the setting for CIFAR-10, the model should be trained on images with 974 randomly perturbed pixels, and theoretically, the certification algorithm in [b] can only certify robustness against 13 perturbed pixels in the most optimistic scenario (where the top-1 probability approaches 100%). Actually, the original paper only reports the certified robustness for at most 5 perturbed pixels, while our model is evaluated with an $\epsilon=20$. Based on the theoretical analyses in [b], to certify robustness against 20 perturbed pixels, we need to perturb at least 990 pixels during training, which dramatically affects the convergence speed and model utility.

(c) As discussed in point (a), the certified robustness is very strict and establishes the lower bound of true robustness, in contrast to the empirical robustness, which our work focuses on. In addition, the certification methods will dramatically increase the computational overhead, either for the provable training (like CROWN [4], CROWN-IBP [5]) or for the Monte Carlo sampling during inference of a randomized model (like randomized smoothing [b] the reviewer mentioned). The computational overhead is contradictory to the motivation of this work: boosting efficiency while maintaining (empirical) robustness.

[1] Towards stable and efficient adversarial training against l1 bounded adversarial attacks. ICML 2023.

[2] Mind the Box: l1-APGD for Sparse Adversarial Attacks on Image Classifiers. ICML 2021.

[3] On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models. ICCV 2019.

[4] Efficient Neural Network Robustness Certification with General Activation Functions. NeurIPS 2018.

[5] Towards Stable and Efficient Training of Verifiably Robust Neural Networks. ICLR 2020.

[6] Towards Fast Computation of Certified Robustness for ReLU Networks. ICML 2018.

[7] DANETs: Deep Abstract Networks for Tabular Data Classification and Regression. AAAI 2022.

Thanks for your detailed and insightful feedback. We would like to provide point-to-point responses to your questions as below and hope this can address your concerns.

1.Details of the adaptation of $\sigma$-zero to pixel space

Reply: $\sigma$-zero utilizes an approximated $l_0$-norm regularization term $\hat{l_0}=\sum_{i=1}^d\frac{x_i^2}{x_i^2+\sigma}$ ($\sigma>0$ is a smoothing hyperparameter) to constrain the sparsity of perturbations. However, it calculates the approximated $l_0$ norm in feature space. To calclate the pixel-space approximated $l_0$ norm,we modify the regularization term to $\hat{l_0}=\sum_{i=1}^{hw}\frac{\sum_{j=1}^{c}x_{i,j}^2}{\sum_{j=1}^{c}x_{i,j}^2+\sigma}$, where h, w and c are the height, width and channel of images, and $x_{i, j}$ represents the perturbation on the $j$-th channel of a particular pixel. As for the hyperparameters, we adopt the ones designed for sAT/sTRADES models in the original paper. Specifically, $\sigma=1$, $\tau_0=0.1$, where $\tau_0$ is the initial sparsity threshold used to guarantee full sparsity (clip the perturbation value lower than it to 0). The other hyperparameters are the same as the default ones.

Moreover, we update the table above with the results of sPGD_p, sPGD_u and RS when they have the same query budget as $\sigma$-zero, i.e., 10000 queries, while sAA is the ensemble of sPGD_p, sPGD_u and RS. The observation is consistent with the previous one that $\sigma$-zero underperforms in pixel space.

We admit that $\sigma$-zero is an effective white-box attack (in some particular cases, it overperforms white-box sPGD_p or sPGD_u) and will include it in our revised manuscript. However, sAA is still the most comprehensive and reliable toolkit to evaluate $l_0$ robustness, and models trained by our proposed algorithm can stably achieve competitive robustness very efficiently.

2. Robustness under feature-space attacks

Reply: Thanks for your constructive suggestion. We report the results of a model trained with our method in feature space below. To accommodate the feature-space sparsity, we modify the shape of perturbation mask in sPGD from (b,1,h,w) to (b,c,h,w). Since RS is unable to generate feature-space perturbations, we set its pixel-space adversarial budget to $\epsilon / c$ to ensure the equivalent feature-space budget as other attacks. The results indicate that our method can also achieve robustness in this setting. In addition, we notice that $\sigma$-zero outperforms sPGD in feature-space attacks, which is consistent with what the reviewer has pointed out. Nevertheless, sAA is still the most comprehensive and reliable robustness evaluation method.

3. Effectiveness beyond images

To further validate the effectiveness beyond images, we employ our method on tabular data. We aim to perturb one input feature of DANet [7] trained on the forest cover type dataset (54 features in total). The training attack is 1-step sPGD ($\epsilon_{train} = 6$) and the evaluation attacks are 10000-step sPGD and $\sigma$-zero ($\epsilon = 1$). The results indicate that our method is still effective for tabular data. Due to the time limit, we cannot explore more application scenarios. Despite this, the results in Table 4, 7, 8, 10, and below can already demonstrate the effectiveness of our method across different datasets, networks, and modalities.

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:

W1: The techniques appear not new and have been extensively studied.

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.

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

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.

W3: Some practical aspects, such as hyperparameter sensitivity, could be discussed in more detail.

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.

Q1: How sensitive is the performance to the choice of hyperparameters in the trade-off loss and label smoothing?

Reply: Please see the response to W3.

Q2: Have the authors considered or explored any new or specifically tailored solutions for the l_0 case, beyond directly applying existing regularization methods?

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.

We hope these responses can address your concerns and look forward to your feedback.

We are happy that our responses addressed many of your concerns and acknowledge our work's contribution. We will incorporate the critical points during the rebuttal in the revised paper. Thanks again for your commitment in reviewing our work.