On the Clean Generalization and Robust Overfitting in Adversarial Training from Two Theoretical Views: Representation Complexity and Training Dynamics

We sincerely thank the reviewer for the positive support and valuable feedback! We greatly appreciate the insightful review, and the recognition of highlighting the significance of our contribution and solidity of our theory, as well as the clarity of our writing. We are very glad to address the questions and suggestions raised by the reviewer, which we believe will help further refine our work. Below are our responses to the questions and suggestions raised by the reviewer.

[C1] However, the results heavily depend on Assumption 4.3 rather than proven, as mentioned by two reviewers as well. Though it may be observed from empirical results, it requires a careful theoretical demonstration.

[A1] We sincerely thank the reviewer for the valuable and thoughtful suggestion. As the reviewer mentioned, we would like to clarify that the main theorem relies on Assumption 4.3, where we apply a teacher-student learning framework. This framework assumes the existence of a ground-truth neural network of moderate size that can achieve perfect clean classification. This teacher-student setup is widely used in deep learning theory (e.g., [1][2][3]).

We also emphasize that the polynomial-size assumption arises from empirical observations, where mildly over-parameterized networks achieve good clean classification performance but poor robust classification performance (e.g., [4][5][6]), rather than from a rigorous mathematical proof. Furthermore, providing a lower bound for the representation complexity required to achieve robust generalization under Assumption 4.3 is highly non-trivial due to the complex decision boundary induced by the ground-truth polynomial-size network. To address this, we build on the technique from [7] to establish an exponential lower bound in the worst case.

[C2] Regarding the training dynamics, the statement is incomplete as the comparison to classifiers under standard training is missing. In this case, it is unclear to us whether a model trained via standard (non-adversarial) training would only learn the true feature and ignore the spurious feature?

[A2] We sincerely thank the reviewer for the insightful suggestion. As the reviewer pointed out, we can prove that a model trained using standard (non-adversarial) training will only learn the true feature and ignore the spurious feature. We will include this statement in the revision of our paper.

Reference

[1] Allen-Zhu, Z., Li, Y., & Liang, Y. (2019). Learning and generalization in overparameterized neural networks, going beyond two layers. Advances in neural information processing systems, 32.

[2] Lv, B., & Zhu, Z. (2022). Implicit bias of adversarial training for deep neural networks. In International Conference on Learning Representations.

[3] Allen-Zhu, Z., & Li, Y. (2023, July). Backward feature correction: How deep learning performs deep (hierarchical) learning. In The Thirty Sixth Annual Conference on Learning Theory (pp. 4598-4598). PMLR.

[4] Biggio, B., Corona, I., Maiorca, D., Nelson, B., Šrndi´ c, N., Laskov, P., Giacinto, G. and Roli, F. (2013). Evasion attacks against machine learning at test time. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III 13. Springer.

[5] Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I. and Fergus, R. (2013). Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199.

[6] Goodfellow, I. J., Shlens, J. and Szegedy, C. (2014). Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572.

[7] Li, B., Jin, J., Zhong, H., Hopcroft, J., & Wang, L. (2022). Why robust generalization in deep learning is difficult: Perspective of expressive power. Advances in Neural Information Processing Systems, 35, 4370-4384.

We sincerely thank the reviewer for the positive feedback! We greatly appreciate the recognition of the novelty and significance of our contribution to the topic of adversarial robustness in the deep learning community, as well as the positive remarks on the clarity of our writing. We are very glad to address the questions and suggestions raised by the reviewer, which we believe will help further refine our work. Below are our responses to the questions and suggestions raised by the reviewer.

[Q1] How would practitioners efficiently verify that a given task satisfies assumptions 4.1-4.3 in order to leverage insights from claim 1 to construct their model and vary its capacity?

[A1] For Assumption 4.1, due to the normalization (or centralization) of the data, we assume that Assumption 4.1 holds for general deep learning problems. For Assumption 4.2, we compute the $\ell_{p}$ distance between data from different classes in the training or test set, as done in the empirical work [1], to validate Assumption 4.2. For Assumption 4.3, we train a suitably-sized ReLU neural network (with network width equal to $\operatorname{poly}(D)$ and network depth $L$ as a constant, resulting in a total parameter count of $\operatorname{poly}(D)$) as a clean classifier. We then test its clean test accuracy and robust test accuracy to verify whether Assumption 4.3 holds. We thank the reviewer for this insightful suggestion, and we will add the above discussion in the revision of our paper.

[Q2] Can claim 2 (eventual CRGO and the three stage phase transition) be demonstrated for a real, existing dataset without special construction?

[A2] We would like to clarify that the patch structure we use can be seen as a simplification of real-world vision-recognition datasets. Specifically, images are divided into signal patches that are meaningful for classification, such as the whisker of a cat or the nose of a dog, and noisy patches, like the uninformative background of a photo. Our assumption about patch data can also be generalized to situations where there exists a set of meaningful patches. However, analyzing the learning process in such cases would complicate our explanation and obscure the main idea we wish to present. Therefore, we focus on the case of a single meaningful patch in our work. We would like to point out that, for real data and real models, it is difficult to rigorously define true feature learning and spurious feature learning. As a result, verifying the phase transition in real-world experiments is challenging, and this issue is commonly encountered in feature learning theory papers, such as [2][3][4][5]. We also believe that validating this on real data is an important and promising direction for future research.

[Q3] Have the authors considered experimentally comparing against a standardly trained model baseline in Section 6.2 on the synthetically constructed dataset? This would serve as a relevant control to understand unique dynamics of adversarial training.

[A3] We thank the reviewer for the valuable suggestion. We have added a standardly trained model baseline on the synthetically constructed dataset. The experiment results are presented as follows:

Reference

[1] Yang, Y. Y., Rashtchian, C., Zhang, H., Salakhutdinov, R. R., & Chaudhuri, K. (2020). A closer look at accuracy vs. robustness. Advances in neural information processing systems, 33, 8588-8601.

[2] Allen-Zhu, Z. and Li, Y. (2023b). Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. In The Eleventh International Conference on Learning Representations.

[3] Chidambaram, M., Wang, X., Wu, C. and Ge, R. (2023). Provably learning diverse features in multi view data with midpoint mixup. In International Conference on Machine Learning. PMLR.

[4] Chen, Z., Deng, Y., Wu, Y., Gu, Q., & Li, Y. (2022). Towards understanding mixture of experts in deep learning. arXiv preprint arXiv:2208.02813.

[5] Zou, D., Cao, Y., Li, Y., & Gu, Q. (2023, July). The benefits of mixup for feature learning. In International Conference on Machine Learning (pp. 43423-43479). PMLR.

We sincerely thank the reviewer for the thoughtful feedback. We are very glad to address the questions and suggestions raised by the reviewer, which we believe will help further refine our work. Below are our responses to the questions and suggestions raised by the reviewer.

Response to claims and evidences:

See our response to [Q3-1].

Response to methods and evaluation criteria:

[Q1] As the reviewer mentioned, we would like to clarify that the main theorem relies on Assumption 4.3, where we apply a teacher-student learning framework. This framework assumes the existence of a ground-truth neural network of moderate size that can achieve perfect clean classification. This teacher-student setup is widely used in deep learning theory (e.g., [1][2][3]). We also emphasize that the polynomial-size assumption arises from empirical observations, where mildly over-parameterized networks achieve good clean classification performance but poor robust classification performance (e.g., [4][5][6]), rather than from a rigorous mathematical proof. Furthermore, providing a lower bound for the representation complexity required to achieve robust generalization under Assumption 4.3 is highly non-trivial due to the complex decision boundary induced by the ground-truth polynomial-size network. To address this, we build on the technique from [7] to establish an exponential lower bound in the worst case.

[Q2] We sincerely thank the reviewer for the valuable and thoughtful suggestion. Indeed, if the data distribution $\mathcal{D}$ satisfies that the covering number of the supporting set is exponential in the data input dimension $D$, we can rigorously prove the third condition, i.e., $L_{\mathcal{D}}^{p,\delta}(f) = \Omega(1)$, which complete the proof of Lemma 4.5. We will include this in the revision of our paper.

[Q3-1] We would like to clarify that, from the perspective of expressive power, our analysis demonstrates that CGRO classifiers can be achieved with only polynomial representation complexity (Theorem 4.4), whereas an exactly robust classifier necessitates representation complexity that is exponential in the worst case (Theorem 4.7). Given the simplicity bias inherent in neural network training (e.g., [8][9][10][11]), this fundamental complexity gap may explain the implicit bias observed in adversarial training.

[Q3-2] We would like to clarify that our paper focuses on the underlying mechanism behind CGRO, and explaining the effectiveness of robustness improvement methods (such as [12]) is beyond the scope of our paper.

[Q4] We simplify real-world vision-recognition datasets by dividing images into meaningful patches (e.g., a cat's whisker or a dog's nose) and noisy ones (e.g., an uninformative background). While this can be generalized to scenarios with multiple meaningful patches, analyzing such cases would complicate our explanation. Hence, we focus on a single meaningful patch. Defining true versus spurious feature learning in real data and models is difficult, making phase transition verification challenging, as seen in feature learning theory papers. We believe validating this on real data is a promising direction for future research.

Response to experimental designs and analyses:

We would like to emphasize that our exponentially large lower bound for representation complexity holds only in the worst case. On the other hand, the computational cost of training neural networks with exponentially large input dimensions is unacceptable in practice. Therefore, as an alternative, we conducted experiments on MNIST and CIFAR10 by appropriately scaling up the network, and the phenomena observed are consistent with our theory.

Response to essential references not discussed:

We thank the reviewer for pointing out the related work [17]. We will include it in the related work section in the revised version of our paper.

Response to other comments and suggestions:

We thank the reviewer for the valuable suggestion. Indeed, when the training data is sufficiently large, i.e., when $N = \Omega(exp(D))$ (at which point Lemma 4.5 no longer holds, as seen in our response to [Q2]), the upper bound of the CGRO classifier's complexity matches the lower bound of the robust classifier's complexity. This also indicates that adversarial robustness requires more data. We will include this part in the revision of our paper.

Reference (Arxiv Index)

[1] 1811.04918

[2] 2001.04413

[3] 2102.06701

[4] 1708.06131

[5] 1312.6199

[6] 1412.6572

[7] 2205.13863

[8] 1901.06523

[9] 2201.07395

[10] 2110.13905

[11] 2410.10322

[12] 2004.05884

[13] 2012.09816

[14] 2210.13512

[15] 2208.02813

[16] 2303.08433

[17] 2209.14105

We sincerely thank the reviewer for the encouraging and insightful feedback, and for highlighting the strength of our theoretical contributions and the clarity of our writing. We are very glad to address the questions and suggestions raised by the reviewer, which we believe will help further refine our work. Below are our responses to the questions raised by the reviewer.

[Q1] the intervals in Table 1 and the figure need modification.

[A1] We thank the reviewer for the valuable suggestion.

• For MNIST, we have added experiments with model size factors of 9, 10, and 11. The experimental results are presented in the following table.

We can observe that when the model size factor is less than or equal to 11, the adversarially trained LeNet model fails to learn non-trivial classifiers. However, when the model size factor is greater than or equal to 12, there is a sudden improvement in model performance. This phenomenon has also been mentioned in previous empirical work [1], and studying the theoretical mechanism behind it is an interesting future direction.

• For CIFAR10, we did not observe the robust test accuracy spike phenomenon (we used the WideResNet architecture here, and a model size factor smaller than 1 results in an inability to achieve a clean classifier, even with clean training). We speculate that this is due to the inherent complexity of the CIFAR10 dataset, which is much higher than that of the MNIST dataset. We also acknowledge that theoretically analyzing the occurrence or absence of the spike phenomenon is an interesting and important direction for future research.

[Q2] It is not clear about the smallest/largest/average noise memorization in figure 2(c).

[A2] We would like to clarify that, for our two-layer neural network and a given data point $(\boldsymbol{X}, y)$, we define the noise memorization as $\mathcal{V} := \sum_{r=1}^{m}\sum_{j \in [P] \setminus \operatorname{signal}(\boldsymbol{X})} \langle \boldsymbol{w}_r^{(T)}, y \boldsymbol{X}[j] \rangle^q$, which is mentioned in lines 291-296 (right page). Then, for the $N$-size training dataset, we obtain a total of $N$ noise memorizations $\mathcal{V}_1, \mathcal{V}_2, \dots, \mathcal{V}_N$. We define the smallest, largest, and average values of these as the smallest, largest, and average noise memorization, respectively. We thank the reviewer for pointing this out, and we will include the relevant explanation in the revision of our paper.

[Q3,4] From Figure 2(c) and Phase III analysis, it seems the true feature learning would not decrease during the training, so how do the authors explain the general phenomenon that robust test accuracy will decrease after some point in the training phase? Similarly, why does the true feature learning not suffer catastrophic forgetting since the “signal component is now mostly dominated by the noise component” as claimed in the paper?

[A3,4] As the reviewer mentioned, we would like to clarify that during training, the true feature learning does not decrease. However, its increment is dominated by the noise component (as seen in Lemma 5.12). Thus, our theory cannot directly explain the observation that robust test accuracy decreases after some point in the training phase and that true feature learning suffers catastrophic forgetting, which implies a gap between theory and observation. We believe that theoretically explaining this gap is an interesting and important future direction.

Reference

[1] Madry, A., Makelov, A., Schmidt, L., Tsipras, D., & Vladu, A. (2017). Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083.