Adversarial Training Can Provably Improve Robustness: Theoretical Analysis of Feature Learning Process Under Structured Data
deep learning theory;feature learning;adversarial robustness;adversarial training;non-convex optimization
Yes
No ethics review needed.
My major questions are already pointed out in the "weakness" section above, in addition to that, I have the following minor questions:

1. In line 247, the author does not provide any intuition or reference about the design of the smoothed ReLU. Why don't the authors use softplus or GeLU? They are popular smooth alternatives of ReLU. In addition, the function proposed by authors here seems discontinuous at the point $z = \rho$?

2. In line 281, why $\epsilon = \Theta(\sigma_n \sqrt{d})$? In practice, we typically use smaller $\epsilon$ for $l_\infty$ bounded perturbations when the dimension $d$ is larger. For example, we usually use $\epsilon = 0.3$ for MNIST, $\epsilon = 8/255$ for CIFAR10, and $\epsilon=2/255$ for ImageNet, these are the datasets with increasing input dimensions.
This paper has the following strengths and contributions:

1. This work theoretically investigates how different adversarial training learns features compared with normal training. Although the results are based on a simple two-layer neural network, it is still meaningful and beneficial for the community as it may be the basis for extension to general neural architectures.

2. The theoretical analyses are consistent with numerical experiments on various datasets.
This paper conducts theoretical analyses on how different the learned features are by normal training and adversarial training. The authors use two layer neural networks with smoothed ReLU as the model, they show that normal training tend to extract non-robust features, while adversarial training encourages the model to learn robust features. Observations in numerical experiments are consistent with theoretical analyses.
I have the following major questions or concerns regarding the current manuscript:

1. The title is a bit misleading. Usually, 'provable robustness' means 'robustness verification', the conclusion of this work does not involve robustness verification.

2. The conclusions of theoretical analyses should involve the magnitude of perturbation $\epsilon$. As we can see when $\epsilon = 0$, adversarial training will be degraded to normal training. Therefore, I believe adversarial training can learn a considerable amount of "non-robust features" when $\epsilon$ is small. A more comprehensive theoretical contribution should be a spectrum instead of discussing two distinct cases: the model learns non-robust features in normal training, as the value of $\epsilon$ increases, the ratio of non-robust features v.s. robust features decreases and in the end, the model will primarily focus on robust features. Can the authors extend your results in this manner? In the current manuscript, Lemma 5.2 cannot degrade to Lemma 5.1 by setting $\epsilon = 0$.

3. The authors assume to use one-step attack in adversarial training (Remark 2.5). However, adversarial training against one-step attacks (like FGSM) does not actually produce robust models. The models trained in this way may be easily broken by a stronger attack.

Based on the weakness above, as well as the questions pointed out in the next section, I think the current manuscript needs a comprehensive edit before publication. I acknowledge the contribution made in this paper, but it still needs improvement. I encourage the authors to address my concerns in the rebuttal.
Yes
No ethics review needed.
Overall, I enjoyed reading the paper. The paper provides a viable theoretical framework for characterizing the feature learning process of standard and adversarial training of two-layer neural networks. I like the level of formalism presented in this paper, which clarifies the theoretical settings and main theoretical results precisely. I think the theoretical framework and the proof techniques can potentially be an important step to eventually understanding the internal mechanism of adversarial learning.

My main questions relate to the assumptions used to derive the theoretical results. The paper assumes the activation is smoothed ReLU and considers one-step gradient descent for generating adversarial examples. These assumptions are different from common practice in adversarial training. Can the authors clarify whether their theoretical framework can be applied to standard ReLU-activated neural nets and multi-step PGD? If this is difficult, it would be helpful to explain the bottleneck for extending the theoretical results to more typical settings. In addition, I did not fully understand why the patch-structured data model (Definition 2.2 and Assumption 2.3) is more realistic than the data model (i.e., the Gaussian mixture model or the multi-cluster data model) assumed in previous works. It is hard to tell from my perspective which data model is more realistic since they are all synthetic data distributions. Can the authors provide some explanations or references?

A few specific questions are listed below:

1. The relationship between robust/non-robust features and the input data is sort of linear, up to some noise. Is it possible to consider a non-linear relationship (e.g., using a ground-truth feature extractor to map the input space to some latent space)?

2. The robust/non-robust features are assumed to be well-separated with respect to particular input dimensions. Generally speaking, there could be cases where robust and non-robust features overlap with each other within the input, and for each input, the robust/non-robust feature dimensions may vary. Is it possible to use the proposed theoretical framework to analyze the feature learning process for such a more generalized setting?
+ The paper proves rigorous theoretical results that elucidate the dynamics of feature learning under adversarial conditions. The clear distinction between robust and non-robust features and their impact on network vulnerability is particularly insightful.

+ The paper is well-structured and easy to follow. The assumptions, theoretical statements, and proof techniques are clearly presented.

+ The theoretical findings are well-supported by experiments on real-image datasets like MNIST, CIFAR10, and SVHN, enhancing the credibility of the results.
The paper presented provides a theoretical framework to understand adversarial examples and the mechanisms by which adversarial training improves model robustness. The authors focus on a two-layer smoothed ReLU convolutional neural network trained on structured data composed of robust and non-robust features. The goal is to demonstrate how standard training methods tend to favor non-robust features, causing adversarial vulnerability, and how adversarial training can shift this learning towards more robust features.
- The complexity of the models and the heavy reliance on specific assumptions about data structure may limit the general applicability of the results.
Yes
No ethics review needed.
How would you motivate the assumption that the class signal vectors are one-hot? How important it is from a technical point of view?

Overall, this is a clear and well-executed result, so in the end it is about weighing the pros against cons. I personally am positive about this result.
+ Bringing a new perspective on a very core and extremely well studied topic
+ Establishing the result required a major technical effort and delivered some interesting insights into underlying training dynamics of two-layer convnets
This work centers on adversarial robustness—the capacity of machine learning models to be resistant to so-called adversarial examples. Its goal is to provide an optimization-focused perspective on the effectiveness of adversarial training (currently the most widely used approach to achieve adversarial robustness) and contrasts it to standard training methods that do not provide this kind of resilience.

More precisely, the paper sets up a stylized data distribution setting (building on settings proposed in the past) and subject to it the authors rigorously prove that a simple deep learning model (two-layer convnet) becomes adversarially robust when trained using adversarial training, but becomes (demonstrably) not adversarially robust if trained using the standard training.
- The considered data distribution is quite interesting and has a clear motivations but at the end of the day it is really heavily stylized, especially the choice to make the class signal be essentially a (scaled) one-hot vector
- It is unclear what are the take-aways from this results (beyond the interesting insights into the training dynamics of the two-layer network), given how heavily stylized the setting is and that the outcomes are fully in line with what one would expect based on the prior work
Yes
No ethics review needed.
1. In Proposition 3 and Theorem 4.3, what if the adversarial perturbation is designed as $\(\delta_p = -\beta_p v_y + \epsilon v_t\)$, where $\(v_t\)$ is orthogonal to all $\(v_i\)$ for $\(i \in [k]\)$? For example, could an adversarial perturbation be constructed without using any known non-robust features from the set$ \(J_{NR}\)$? Given the high dimensionality of $\(d\)$, and the potential infinitude of non-robust features, this scenario might be feasible.

2. In the definition of “Small Perturbation Radius” (lines 281-284), two data points $\(X\)$ and $\(X'\)$ with distinct labels may have significant differences with high probability. While this may hold for real data, what if $\(X'\)$ is also an adversarial example?

3. In line 285, the authors assume that $\(F\)$ is an accurate classifier on $\((X, y)\)$. However, since $\(F\)$ is only a two-layer neural network, this assumption may not be entirely valid. There could be a substantial portion of the dataset on which $\(F\)$ misclassifies. Can the authors discuss which parts of the theory would be impacted by relaxing this assumption? For instance, in Propositions 3.1 and 3.2, \$(\arg \max F_i(X + \Delta) \neq y\)$ could hold even with $\(\Delta = 0\)$ if $\(F_i(X) \neq y\)$.
- The paper provides a compelling theoretical explanation for a well-known empirical phenomenon, as demonstrated in prior work [1].

[1] Ilyas, Andrew, et al. "Adversarial examples are not bugs, they are features." Advances in neural information processing systems 32 (2019).
The paper proposes a theoretical framework to explain why standard training leads models to learn non-robust features, whereas adversarial training encourages models to focus on robust features. This theoretical insight supports previously observed empirical results in the literature.

To illustrate this, the authors construct data using two distinct sets of features: robust-feature patches and non-robust-feature patches. These two sets are disjoint and collectively span the entire feature space \([P]\) (Definition 2.2), with the additional assumption that all features are orthonormal.

Using this setup and the associated assumptions, the paper demonstrates that a network relying solely on non-robust features becomes vulnerable to adversarial perturbations. Conversely, a network that learns robust features is shown to achieve robustness, as formalized in Propositions 3.1 and 3.2.

Finally, Theorem 4.3 demonstrates that standard training encourages the model to learn non-robust features, achieving low loss on clean data but high loss under adversarial conditions. In contrast, Theorem 4.4 shows that adversarial training shifts the model’s focus toward learning robust features, rather than non-robust ones.
The theoretical framework relies on several significant assumptions:
- **Types of Features:** The paper assumes only two types of features: robust and non-robust, both of which contribute meaningfully to model predictions. However, this simplification may not fully capture the complexity of real data, as observed in [1], which categorizes features into robust/non-robust and useful/non-useful, based on their contribution to the model’s predictions. The set of non-robust features could be infinite, whereas this paper imposes a limit.

- **Orthogonality Assumption:** The core theorem relies on the assumption that features are orthogonal. However, in practical settings, features are not typically orthogonal. The proofs, particularly of Propositions 3.1 and 3.2 (provided in Appendix C), depend on this orthogonal assumption by considering robust features $(\(u_y\))$ orthogonal to non-robust features $(\(v_y\))$.

- **Data Construction Assumption:** Each data point $\(X\)$ is composed of multiple patches $\(\{x_1, \dots, x_P\}\)$, where each patch represents either a robust or non-robust feature (Definition 2.2, Step 3), with certain scaling and randomness. These features are modeled in the input space, but to satisfy the strict assumptions made in the paper, it would seem more appropriate to consider them in the latent space.

- **Definitions of Robust and Non-Robust Features (Assumption 2.3):**
  - Robust features are defined as stronger than non-robust features.
  - Non-robust features are defined as denser than robust features.
  - However, these definitions lack interpretability, which would be beneficial for a more complete understanding.
  - Under this assumption, standard training picks up denser features, while adversarial training picks up stronger features, assumed to be robust features.
  - The paper lacks experiments to demonstrate the existence of these properties (strength and density) in real-world datasets.
Yes
No ethics review needed.
1. From the analysis, there seems to be no tradeoff between standard and robust accuracies in adversarial training contrary to the empirical observations [P1]. Can the analysis show this tradeoff? Perhaps, in theorem 4.4, it might be worthwhile to include what happens to the standard accuracy $P_{(X,y)\sim \mathcal{D}}[\arg\max F_i^{(T)}(X) \ne y]$ and also what happens when $(X_f,y) \sim \mathcal{D}_{NR}$. 
2. The adversarial training analysis shows a phase transition where non-robust features are learned in phase 1, and then robust feature learning increases over the non-robust in phase 2. This is also observed in the simulated experiments. However, some works with similar robust and non-robust feature definitions suggest robust features are learned first. For instance, [P2] shows it empirically using the neural tangent kernel, while Proposition 5.1 in [P3] shows it using generalized additive models theoretically. The phase transition is also not really observed in real data and neural networks with activations other than smoothed ReLU. Can the authors comment on why there is a discrepancy in the results? Adding a discussion contrasting to these results would be helpful.
3. The analysis considers smoothed ReLU activation following the feature learning analysis from Allen-Zhu & Li 2023a. Why is this particular choice made? What happens with other activations? 
4. Minor comment: in line 179, 'where $u,v$ are the corresponding' - u,v should be boldfaced.

[P1] Tsipras et al. "Robustness May Be at Odds with Accuracy." ICLR 2019.

[P2] Tsilivis and Kempe. "What can the neural tangent kernel tell us about adversarial robustness?." NeurIPS 2022.

[P3] Singh et al. "Robust Feature Inference: A Test-time Defense Strategy using Spectral Projections." TMLR 2024.
1. The theoretical analysis is rigorous in the feature learning regime, and the derived results are interesting contributions to the robustness of neural networks, adding to the previous works.
2. The paper is clearly written with a detailed related work section. The discussions on the theoretical results and assumptions are very helpful in understanding the paper.
3. Experiments also support the theoretical findings.
This paper studies the adversarial robustness of neural networks theoretically from the perspective of feature learning theory. The analysis is done for a two-layer ReLU convolutional network under constructed data that has sparse robust features and dense non-robust features. Main results are,
* standard training of gradient descent learns non-robust features. Therefore, adversarial perturbations exist along the negative non-robust feature directions. 
* adversarial training with one step gradient ascent provably learns the robust features, thus improving the robustness of the network. 

Empirical results on MNIST, CIFAR-10 and SVHN demonstrate the above theoretical findings.
1. Extending the analysis beyond the two layer smoothed ReLU convolution network to realistic, deeper neural networks seems difficult. 
2. The adversarial training is with just one step gradient ascent which is usually not the case in practice. 
3. The definition of robust and non-robust features require parallel to the coordinate axis along with orthonormal condition which is restrictive.
In this paper, we provide a theoretical understanding of adversarial examples and adversarial training algorithms from the perspective of feature learning theory.
@inproceedings{
anonymous2024adversarial,
title={Adversarial Training Can Provably Improve Robustness: Theoretical Analysis of Feature Learning Process Under Structured Data},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=inLUnCpDIB},
note={under review}
}
Adversarial training is a widely-applied approach to training deep neural networks to be robust against adversarial perturbation. However, although adversarial training has achieved empirical success in practice, it still remains unclear why adversarial examples exist and how adversarial training methods improve model robustness. In this paper, we provide a theoretical understanding of adversarial examples and adversarial training algorithms from the perspective of feature learning theory. Specifically, we focus on a multiple classification setting, where the structured data can be composed of two types of features: the robust features, which are resistant to perturbation but sparse, and the non-robust features, which are susceptible to perturbation but dense. We train a two-layer smoothed ReLU convolutional neural network to learn our structured data. First, we prove that by using standard training (gradient descent over the empirical risk), the network learner primarily learns the non-robust feature rather than the robust feature, which thereby leads to the adversarial examples that are generated by perturbations aligned with negative non-robust feature directions. Then, we consider the gradient-based adversarial training algorithm, which runs gradient ascent to find adversarial examples and runs gradient descent over the empirical risk at adversarial examples to update models. We show that the adversarial training method can provably strengthen the robust feature learning and suppress the non-robust feature learning to improve the network robustness. Finally, we also empirically validate our theoretical findings with experiments on real-image datasets, including MNIST, CIFAR10 and SVHN.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
deep learning theory feature learning adversarial robustness adversarial training non-convex optimization
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/4811e024f7405d0ed4ddc8212b37c531982c2caf.pdf
learning theory
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Adversarial Training Can Provably Improve Robustness: Theoretical Analysis of Feature Learning Process Under Structured Data
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission