Adversarial Training Can Provably Improve Robustness: Theoretical Analysis of Feature Learning Process Under Structured Data

Authors: Binghui Li, Yuanzhi Li
Primary area: learning theory
Keywords: deep learning theory, feature learning, adversarial robustness, adversarial training, non-convex optimization

Abstract:
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.

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730286537611

thread_type:
official_review

<thread_object>
creator: reviewer_xdz5

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730532194778

thread_type:
official_review

<thread_object>
creator: reviewer_cqxx

<content>
summary:
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.

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

weaknesses:
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.

questions:
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\)$.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730670437888

thread_type:
official_review

<thread_object>
creator: reviewer_gmkj

<content>
summary:
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.

strengths:
+ 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

weaknesses:
- 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

questions:
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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730908727907

thread_type:
official_review

<thread_object>
creator: reviewer_ubb1

<content>
summary:
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.

strengths:
+ 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.

weaknesses:
- The complexity of the models and the heavy reliance on specific assumptions about data structure may limit the general applicability of the results.

questions:
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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731253056865

thread_type:
official_review

<thread_object>
creator: reviewer_wbrq

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
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.

>>> After rebuttal, I appreciate the author's explanations, I will not object to the acceptance of this paper. However, the author should clearly explain the effect of $\epsilon$, as a continuous variable, on feature learning in adversarial training.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732428931712

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response to Reviewers

comment:
We sincerely thank all reviewers for their positive support and valuable feedback! We greatly appreciate the insightful reviews and the recognition of the significance of our contributions, the strength of our theory and experiments, and the clarity of our writing. Their feedback has been instrumental in helping us improve our manuscript. We have provided a revised manuscript (with text highlighted in blue) and outline our revisions in this global response:

 1. We have relaxed the definition of adversarial examples in lines 285–288, as mentioned by reviewer cqxX, where we no longer require the classifier $\boldsymbol{F}$ to correctly classify the clean data point $(\boldsymbol{X}, y)$.

 1. We have corrected typos in line 197, as pointed out by reviewer XDz5.

Once again, we thank all reviewers for their insightful and valuable comments.
</content>
</thread_object>

</thread>


Metareview:
metareview:
Summary: This paper studies the difference of adversarial training vs. normal training, by looking at the learned features on a two-layer network with smoothed ReLU activation. The paper shows that adversarial training tends to learn robust features, while normal training tends to learn non-robust features. The paper sends a similar take-away message as [1].

[1] Ilyas, Andrew, et al. "Adversarial examples are not bugs, they are features." Advances in neural information processing systems 32 (2019).


Strengths:
1. The paper analyzes the benefits of adversarial training in terms of learning robust features, with rigorous theoretical proofs.
2. Experiments are performed in alignment with the theoretical discovery.

Weaknesses:
1. It is unclear what new take-home message this paper sends compared with [1]. Adversarial training learns more robust features than normal training has been well-studied before (though this paper tries to provide a rigorous proof under certain assumptions).
2. Strong assumptions. The analysis is built upon a stylized data distribution and a two-layer smoothed ReLU convolutional neural network. This may limit its extension to broader applications, e.g., other data distribution and network architectures.
3. The theory does not show a relation with variable $\epsilon$, which is the adversarial attack budget.
4. The theoretical analysis of adversarial training is with just one step gradient ascent (FGSM), which is vulnerable to attacks in practice.

All 5 reviewers consistently vote for 6: marginally above the acceptance threshold. AC would follow reviewers' opinion and recommend for acceptance. However, AC would encourage the authors to take weaknesses into consideration in the future research.