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

We sincerely thank the reviewer for the insightful feedback, and for highlighting 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.

[W1] Could you specify conditions on $\mathcal{D}$ under which $f _{\mathcal{S}}$ would exhibit robust overfitting with high probability over the randomness of drawing $\mathcal{S}$ from $\mathcal{D}$? Could you also provide theoretical analysis towards how the sample size $N$ as well as $\delta$ and $p$ affect \mathcal{L} _{\mathcal{D}}^{p,\delta} (f _{\mathcal{S}) ?

[E1] 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$. And we also provide theoretical analysis about \mathcal{L} _{\mathcal{D}}^{p,\delta} (f _{\mathcal{S}). See details in Appendix B. We propose a novel robust generalization bound that is mostly related to global flatness of loss landscape. And this Relation Is also observed in practice.

[W2] The construction of $\mathcal{A} _{p}(\boldsymbol{X},\delta)$ is important for understanding the results in Theorem 5.9. I hope the authors could clarify the definition of $\mathcal{A} _{p}(\boldsymbol{X},\delta)$.

[E2] We would like to clarify that the perturbed range $\mathcal{A} _{p}(\boldsymbol{X},\delta)$ ensures that adversarial perturbations used to generate adversarial examples are always aligned with the meaningful signal vector $\boldsymbol{w}^{*}$ during adversarial training, which exactly simplifies the analysis. Specifically, we have

$

\boldsymbol{X}^{\text{adv}}[j] = \alpha(1-\gamma) y \boldsymbol{w}^{*}, j = \operatorname{signal}(\boldsymbol{X})

$

$

\boldsymbol{X}^{\text{adv}}[j] = \boldsymbol{X}[j], j \in [p] \setminus \operatorname{signal}(\boldsymbol{X})

$

We then derive the correctness as $y f _{\boldsymbol{W}}(\boldsymbol{X}^{\text{adv}}) = y \sum _{r=1}^{m} \langle\boldsymbol{w} _r, \boldsymbol{X}^{\text{adv}}[\operatorname{signal}(\boldsymbol{X})]\rangle^{q} + y \sum _{r=1}^{m}\sum _{j \in [P]\setminus \operatorname{signal}(\boldsymbol{X})} \langle \boldsymbol{w} _{r}, \boldsymbol{X}^{\text{adv}}[j] \rangle^{q} = \underbrace{y \sum _{r=1}^{m} \langle\boldsymbol{w} _r, \alpha(1-\gamma) y \boldsymbol{w}^{*} \rangle^{q}} _{{\alpha}^{q}(1-\gamma)^{q}\mathcal{U}} + \underbrace{y \sum _{r=1}^{m}\sum _{j \in [P]\setminus \operatorname{signal}(\boldsymbol{X})} \langle \boldsymbol{w} _{r}, \boldsymbol{X}[j] \rangle^{q}} _{\mathcal{V}}$

Thus, the model correctly classify the perturbed data if and only if $\alpha^{q}(1-\gamma)^{q}\mathcal{U} + \mathcal{V} \ge 0$, which implies that we can analyze the perturbed data by tracking the dynamics of $\mathcal{U}$ and $\mathcal{V}$.

[W3] Under the settings in Section 5, is it possible to show that a model trained via standard (non-adversarial) training would only learn the true feature and ignore the spurious feature? Establishing this distinction is important, as it would suggest that CGRO arises from the nature of AT itself rather than from the artificial construction of the data model.

[E3] 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.

[W2] Specifically, the paper should analyze:

1. For an unseen samples, what is the probability that the model will correctly classify it? Need analysis of the condition $\alpha^q U + V \geq 0$ for a new sample.
2. For adversarial examples generated from this unseen sample, what is the probability of misclassification? Need analysis of the condition $\alpha^q U + V < 0$for adversarial example.

These probability analyses would help complete the connection between the training dynamics results and the CGRO phenomenon.

[E2] Theorem E.12 We sincerely thank the reviewer for the insightful suggestion. We would like to point out that our Theorem E.12 gives the probability analysis as the reviewer suggested. See details in the proof of Theorem E.12 (Appendix E). Here, we briefly provide high-level intuition behind the probability analysis as follows:

1. For an unseen clean data $(\boldsymbol{X}, y) \sim \mathcal{D}$, we have $\mathbb{P} _{(\boldsymbol{X},y)\sim \mathcal{D}}[y f _{\boldsymbol{W}^{(T)}}(\boldsymbol{X}) < 0] = \mathbb{P} _{(\boldsymbol{X},y)\sim \mathcal{D}}[\alpha^{3} \sum _{r=1}^{m} (u _{r}^{(T)})^{3} + y \sum _{r=1}^{m}\sum _{j \in [P]\setminus \operatorname{signal}(\boldsymbol{X})} \langle \boldsymbol{w} _{r}^{(T)}, \boldsymbol{X}[j] \rangle ^{3} < 0]$ $\le \mathbb{P} _{(\boldsymbol{X},y)\sim \mathcal{D}}[ \sum _{r=1}^{m}\sum _{j \in [P]\setminus \operatorname{signal}(\boldsymbol{X})} \langle \boldsymbol{\beta} _{r}^{(T)}, \boldsymbol{X}[j] \rangle^{3} \ge \tilde{\Omega}(1) ] \le \operatorname{exp}(-\frac{\tilde{\Omega}(1)}{\sigma^{6}\sum _{r=1}^{m}\|\boldsymbol{\beta} _{r}^{(T)}\| _{2}^{6}}) \le O(\frac{1}{\operatorname{poly}(d)}) = o(1).$

It shows that, after adversarial training, the network learns the partial true feature, which ensures to correctly classify unseen clean data with high probability.

2. For the adversarial example $\boldsymbol{X} + \boldsymbol{\xi}$ generated from the unseen data $(\boldsymbol{X}, y) \sim \mathcal{D}$ and adversarial attack $\mathcal{A}:\mathbb{R}^{D}\rightarrow \mathbb{R}^{D}$, we have $\mathbb{P} _{(\boldsymbol{X},y)\sim \mathcal{D}}[\operatorname{min} _{\|\boldsymbol{\xi}\| _{2}\le \delta}y f _{\boldsymbol{W}^{(T)}}(\boldsymbol{X}+\boldsymbol{\xi}) < 0] \ge \mathbb{P} _{(\boldsymbol{X},y)\sim \mathcal{D}}[y f _{\boldsymbol{W}^{(T)}}(\mathcal{A}(\boldsymbol{X})) < 0] = \mathbb{P} _{(\boldsymbol{X},y)\sim \mathcal{D}}[\alpha^{3}\sum _{r=1}^{m}(u _{r}^{(T)})^{3}(1-\gamma)^{3} + y \sum _{r=1}^{m}\sum _{j \in [P]\setminus \operatorname{signal}(\boldsymbol{X})} \langle \boldsymbol{w} _{r}^{(T)}, \boldsymbol{X}[j] \rangle^{3} < 0]$ $\ge \frac{1}{2} \mathbb{P} _{(\boldsymbol{X},y)\sim \mathcal{D}}[ \|\sum _{r=1}^{m}\sum _{j \in [P]\setminus \operatorname{signal}(\boldsymbol{X})} \langle \boldsymbol{\beta} _{r}^{(T)}, \boldsymbol{X}[j] \rangle^{3}\| \ge \tilde{\Omega}((1-\gamma)^{3})] \ge \frac{1}{2}(1 - \frac{\tilde{O}(d)}{2^{d}}) = \frac{1}{2} - o(1).$

It shows that, with probability at least $1/2$, the network learner fails to classify the adversarial examples generated from unseen clean data.

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 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 and suggestions raised by the reviewer.

[W1] However, the $\operatorname{poly}(D)$ complexity of clean classifiers is simply assumed in Assumption 4.3 rather than proven. This is problematic because if clean classification also requires $\operatorname{exp}(D)$ parameters, the entire complexity hierarchy becomes meaningless. The authors need to either: 1.Prove that clean classifiers can indeed be approximated by neural networks with $\operatorname{poly}(D)$ parameters, even though it is trivial.

2. Cite existing results that establish this fact, even though this is a well-known classical result.

[E1] 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.

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.

[Q1] I explained my confusions with the authors' asymptotic analysis in data dimension $D$. Can the authors clarify on the questions I raised on the analysis?

[A1] We would like to clarify that our asymptotic analysis in data dimension $D$ is widely used in the literature of deep learning theory, as demonstrated in papers such as [1][2][3] in our related work section. We would also like to point out that the constant property of $R$ is reasonable, since the range of image pixels is typically $0$–$255$, while the data dimension can be very large. Additionally, our assumption about the perturbation radius $\delta$ is reasonable, because, for real datasets, different classes tend to be well-separated, while the perturbation radius is often much smaller than the separation distance, as empirically observed in the work of [4].

[Q2] Can the authors provide more numerical results where the clean test accuracy remains stable while adversarial test accuracy improves where the model complexity grows?

[A2] We would like to point out that our experimental results show that clean test accuracy remains stable while adversarial test accuracy improves as model complexity grows. See Figure 1 (a) (b) and Table 1: for the MNIST dataset, when the model size increases from $12$ to $16$, robust test accuracy significantly improves (from $77.96\%$ to $83.43\%$), while the change in clean test accuracy is minimal (from $95.06\%$ to $94.85\%$); for the CIFAR-10 dataset, when the model size increases from $5$ to $10$, robust test accuracy significantly improves (from $46.25\%$ to $50.08\%$), while the change in clean test accuracy is minimal (from $85.83\%$ to $86.05\%$).

[Q3] Minor comment: In my opinion, copying a figure from another paper (Figure 1 in the introduction) is inappropriate in a top-level machine learning paper. It would have been better if the authors' replicated the results on a different dataset or architecture and while giving credit to the cited paper, they presented their own computed version of the figure in the submission.

[A3] We sincerely thank the reviewer for the suggestion. We have updated our experimental results in Figure 1 of the revised paper, where we apply the WideResNet architecture [5] to run the standard adversarial training algorithm on the CIFAR-10 dataset. The results show that CGRO occurs during adversarial training.

Reference

[1] Bubeck, S., & Sellke, M. (2021). A universal law of robustness via isoperimetry. Advances in Neural Information Processing Systems, 34, 28811-28822.

[2] 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.

[3] 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.

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

[5] Zagoruyko, S. (2016). Wide residual networks. arXiv preprint arXiv:1605.07146.

We sincerely thank the reviewer for the support 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 and suggestions raised by the reviewer.

[W1] The model representation perspective shows that the models need more parameters to achieve robust generalization than CGRO. But how do we validate that the number of parameters of the deep networks such as ResNet is in this CGRO range?

[E1] We would like to clarify that, from the perspective of representation complexity, models require more parameters to achieve robust generalization than CGRO. However, we do not provide an explicit method to validate that the number of parameters in practical deep networks falls within this CGRO range, as our lower bound applies in the worst-case scenario. We also believe that exploring the range of parameter counts to determine whether a network is in the CGRO regime is an important and interesting avenue for future research.

[W2] The data structure is not very realistic. I think a more realistic assumption would be the data lies in a low-dimensional subspace or manifold. The assumption that only a pixel-space patch has useful signals would be too tough in my opinion.

[E2] 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.

[W3] Although the authors validate the three stages of training dynamics in the synthetic structure data, they don't validate it on real data. Could you provide some experimental results to show it?

[E3] We sincerely thank the reviewer for the valuable and thoughtful suggestion. 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 [1][2][3][4]. We also believe that validating this on real data is an important and promising direction for future research.

Reference

[1] 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.

[2] 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.

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

[4] 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 encouraging and insightful feedback, and for highlighting the strength of our theoretical contributions. 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.

[W1] The paper falls short in clarifying how its results contribute to understanding why CGRO occurs during adversarial training. The paper raises this broad question in the introduction but lacks a detailed explanation of how its findings can offer insights into addressing it. [E1] We would like to clarify that we provide theoretical insights to understand why CGRO occurs from two perspectives: expressive power and training dynamics.

1. From the perspective of expressive power, we show that only polynomial representation complexity can achieve a CGRO classifier (Theorem 4.4), while an exactly robust classifier requires exponentially large representation complexity in the worst case (Theorem 4.7). This implies that the CGRO phenomenon may stem from the limits of expressive power in practice.
2. From the perspective of training dynamics, our theoretical analysis of the feature learning process suggests that, with moderate over-parameterization, the network model trained via adversarial training learns partial true features but exactly memorizes training-data-specific random spurious features (Theorem 5.9). This leads to perfect clean generalization and significant robust overfitting.

We believe that our theoretical insights will help in designing better adversarially robust algorithms to address robust learning problems.

[W2] From the perspective of representation complexity to illustrate the CGRO phenomenon, the main theorem relies on Assumption 4.3, which posits the existence of a clean ReLU network classifier of polynomial size. However, this assertion pertains to a factual claim and cannot be directly treated as an assumption. Instead, it would be more appropriate to formulate it as a theorem accompanied by a rigorous mathematical proof. This would strengthen the foundation of the theoretical results presented in the paper.

[E2] 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.

[W3] From the perspective of training dynamics to elucidate the CGRO phenomenon, the analysis depends on the assumption that the perturbation radius $\delta$ is only marginally smaller than the signal norm $\alpha$. The theoretical results are derived specifically under this condition for the perturbation radius. However, in practical scenarios, the perturbation radius can be chosen arbitrarily. The paper does not adequately address whether the same theoretical results can be achieved in this more generalized context, which leaves an important gap in understanding the robustness of the findings. Further exploration of this aspect would enhance the comprehensiveness of the study.

[E3] We sincerely thank the reviewer for the suggestion. We would like to point out that, for real datasets, different classes tend to be well-separated, while the perturbation radius is often much smaller than the separation distance, as empirically observed in the work of [8]. Under our theoretical setup for training dynamics analysis, the separation between the positive and negative classes is roughly of the order of the signal norm $\alpha$. Thus, the assumption that the perturbation radius $\delta$ is only marginally smaller than the signal norm $\alpha$ is reasonable. We also acknowledge that exploring more generalized setups is an important and interesting future direction for our work.

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.

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