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

## Abstract

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.

## 1 Introduction

Recently, large-scale neural networks have achieved remarkable performance in many disciplines, especially in computer vision (Krizhevsky et al., ; Dosovitskiy et al., ; Kirillov et al., ) and natural language processing (Kenton and Toutanova, ; Brown et al., ; Ouyang et al., ; Achiam et al., ). However, it is well-known that neural networks are vulnerable to small but adversarial perturbations, i.e., natural data with strategic perturbations called adversarial examples (Biggio et al., ; Szegedy et al., ; Goodfellow et al., ), which can confuse well-trained network classifiers. This potentially leads to reliability and security issues in real-world applications.

To mitigate this problem, one seminal approach to improve robustness of models is called adversarial training (Goodfellow et al., ; Madry et al., ; Shafahi et al., ; Zhang et al., ; Pang et al., ; Wang et al., ), which iteratively generates adversarial examples from the training data and updates the model with these adversarial examples rather than the original training examples.

However, despite the significant empirical success of adversarial training in enhancing the robustness of neural networks across various datasets, the theoretical understanding of adversarial examples and adversarial training still remains unclear, particularly from the perspective of network optimization.

Therefore, we ask the following fundamental theoretical questions:

Q1: Why do neural networks trained with standard training tend to converge to non-robust solutions that fail to classify adversarially-perturbed data?

Q2: How does the adversarial training algorithm assist in optimizing neural networks to enhance their robustness against adversarial perturbations?

Indeed, we emphasize that a common challenge in analyzing adversarial robustness is the gap between theory and practice, primarily attributed to the data assumptions in theoretical frameworks (see detailed discussion in Section 1.1), which motives us considering realistic data model. In our paper, the data foundation that we leverage is predicated on the decomposition of robust and non-robust features, which suggests that data is comprised of two distinct types of features: robust features, characterized by their strength yet sparsity, and non-robust features, noted for their vulnerability yet density (Assumption 2.3). This decomposition has been empirically investigated in a series of previous studies (Tsipras et al., ; Ilyas et al., ; Kim et al., ; Tsilivis and Kempe, ; Han et al., ). Furthermore, we mathematically represent this concept as the patch-structured data proposed in the recent work of Allen-Zhu and Li (), in which they utilize multi-view-based patch-structured data to provide a fruitful setting for theoretically understanding the benefits of ensembles in deep learning. Specifically, inspired by Allen-Zhu and Li () and Ilyas et al. (), we propose a novel patch-structured data model based on robust/non-robust feature decomposition (Definition 2.2), and show our patch data model enables us to rigorously establish the existence of adversarial examples and demonstrate the efficacy of adversarial training by directly analyzing the feature learning process for two-layer networks under our structured data. More precisely, the main results in our work are summarized as follows:

- •
By analyzing the feature learning process on robust/non-robust feature decomposition based data, we demonstrate that in standard training, the neural network predominantly learns non-robust features rather than robust features (Theorem 4.3). This leads to the generation of adversarial examples with perturbations stemming from these non-robust features
- •
Furthermore, we show that adversarial training algorithms can provably both suppress the learning of non-robust features and enhance the learning of robust features (Theorem 4.4), thereby improving models robustness.
- •
We also substantiate the theoretical findings about robust and non-robust feature learning discussed in Section 4 through a series of experiments conducted on real-image datasets (MNIST, CIFAR10, and SVHN). Detailed results can be viewed in Figure 4.

Figure: Figure 1: An overview of our paper: robust/non-robust-feature-decomposition-based framework and key messages about standard/adversarial training. And the robust/non-robust features of elephant and cat are generated in the same way of Ilyas et al. () from random noise to ImageNet instances.
Refer to caption: x1.png

### 1.1 Related Works

Theoretical Explanations for Adversarial Examples.
A line of works (Daniely and Shacham, ; Bubeck et al., ; Bartlett et al., ; Montanari and Wu, ) demonstrates the existence of adversarial examples in random-weight neural networks with various architectures. Another line of works (Bubeck et al., ; Bubeck and Sellke, ; Li et al., ; Li and Li, ) suggests that over-parameterization is necessary to achieve robustness, and that non-robustness may stem from the expressive power of neural networks. However, these works do not consider the optimization process when explaining adversarial examples in trained networks. Recently, Frei et al. () proved that, for two-layer ReLU networks, gradient flow leads to well-generalizing but non-robust solutions under a synthetic multi clusters data assumption. In our paper, we analyze the feature learning process under a more realistic structured data model inspired by the robust/non-robust feature decomposition proposed in Ilyas et al. (). Indeed, we not only prove that standard training causes a two-layer neural network to converge to a non-robust solution, but also rigorously analyze how adversarial training algorithm provably guides the network towards a robust solution.

Theoretical Understanding of Adversarial Training for Linear Models.
A series of works (Li et al., ; Javanmard and Soltanolkotabi, ; Chen et al., ) demonstrate that a linear classifier trained through adversarial training can achieve robustness under the Gaussian-mixture data model. However, standard training does not explicitly converge to non-robust solutions under these conditions. This discrepancy does not align with the empirical observation that networks trained by standard methods exhibit poor robust performance (Biggio et al., ; Szegedy et al., ; Goodfellow et al., ). For example, as noted in Chen et al. (), similar to standard training, adversarial training also directionally converges to the maximum $\ell_{2}$-margin solution when considering a Gaussian-mixture data model with $\ell_{2}$ perturbations. This suggests that, under their settings, standard training alone can achieve adversarial robustness due to the maximum-margin implicit bias, even though neural networks trained with standard training typically exhibit non-robustness in practice. In our paper, to bridge the gap between theory and practice, we consider a more structured data assumption and apply a non-linear two-layer CNN as the learner, which ensures that both robust global minima and non-robust global minima exist due to the non-linearity of our data model and and non-convexity of our learner model (see a detailed discussion in Section 3).

Feature Learning Theory of Deep Learning.
The feature learning theory of neural networks, as proposed in various recent studies (Wen and Li, ; Allen-Zhu and Li, ; Chen et al., ; Jelassi et al., ; Chidambaram et al., ; Allen-Zhu and Li, , ; Lu et al., ; Chen et al., ), aims to explore how features are learned in deep learning tasks. This theory extends the theoretical optimization analysis paradigm beyond the scope of the neural tangent kernel (NTK) theory (Jacot et al., ; Du et al., , ; Allen-Zhu et al., ; Arora et al., ). Based on the sparse coding model, Allen-Zhu and Li () consider a binary robust classification problem and proposes a principle called feature purification to explain the workings of adversarial training. In our paper, we focus on a multiple robust classification problem by leveraging more image-like, patch-structured data with an assumption of robust/non-robust feature decomposition. We study how the feature learning process differs when applying adversarial training instead of standard training.

## 2 Problem Setup

### 2.1 Notations

Throughout this work, we use letters for scalars and bold letters for vectors. For any given two sequences $\left\{A_{n}\right\}_{n=0}^{\infty}$ and $\left\{B_{n}\right\}_{n=0}^{\infty}$, we denote $A_{n}=O\left(B_{n}\right)$ if there exist some absolute constant $C_{1}>0$ and $N_{1}>0$ such that $\left|A_{n}\right|\leq C_{1}\left|B_{n}\right|$ for all $n\geq N_{1}$. Similarly, we denote $A_{n}=\Omega\left(B_{n}\right)$ if there exist $C_{2}>0$ and $N_{2}>0$ such that $\left|A_{n}\right|\geq C_{2}\left|B_{n}\right|$ for all $n>N_{2}$. We say $A_{n}=\Theta\left(B_{n}\right)$ if $A_{n}=O\left(B_{n}\right)$ and $A_{n}=\Omega\left(B_{n}\right)$ both holds. We use $\widetilde{O}(\cdot),\widetilde{\Omega}(\cdot)$, and $\widetilde{\Theta}(\cdot)$ to hide logarithmic factors in these notations respectively. Moreover, we denote $A_{n}=\operatorname{poly}\left(B_{n}\right)$ if $A_{n}=O\left(B_{n}^{K}\right)$ for some positive constant $K$, and $A_{n}=\operatorname{polylog}\left(B_{n}\right)$ if $B_{n}=\operatorname{poly}\left(\log\left(B_{n}\right)\right)$. We say $A_{n}=o(B_{n})$ (or $A_{n}\ll B_{n}$ or $B_{n}\gg A_{n}$) if for arbitrary positive constant $C_{3}>0$, there exists $N_{3}>0$ such that $|A_{n}|<C_{3}|B_{n}|$ for all $n>N_{3}$. And we also use $A_{n}\approx B_{n}$ to denote $A_{n}=B_{n}+o(1)$.

Figure: Figure 2: Illustration of our patch data: Each patch in data point $(\bm{X},y)$ has the form $\bm{x}_{p}=\alpha_{p}\bm{u}+\bm{\xi}_{p}$ (robust-feature patch) or $\bm{x}_{p}=\beta_{p}\bm{v}+\bm{\xi}_{p}$ (non-robust-feature patch), where $u,v$ are the corresponding features for class $y$. For non-robust-feature patches, adversarial perturbation $\bm{\Delta}$ replaces non-robust feature $\bm{v}$ with other non-robust feature $\bm{v}^{\prime}$ (corresponding to other class $y^{\prime}$), which causes adversarial example $\tilde{\bm{X}}$ with incorrect label $y^{\prime}$ when the network learner trained by standard training mainly learns non-robust features $\bm{v},\bm{v}^{\prime}$ rather than robust features $\bm{u},\bm{u}^{\prime}$. And we construct robust-feature/non-robust-feature data $\bm{X}_{\bm{u}}/\bm{X}_{\bm{v}}$ by replacing $\bm{v}/\bm{u}$ with all-zero vector $\bm{0}$.
Refer to caption: x2.png

### 2.2 Data Distribution

In this paper, we consider a $k$-class classification problem involving data that is structured into $P$ patches, with each patch having a dimension of $d$. Specifically, each labeled data point is represented by $(\bm{X},y)$, where $\bm{X}=(\bm{x}_{1},\bm{x}_{2},\dots,\bm{x}_{P})\in\left(\mathbb{R}^{d}\right)^
{P}$ denotes the data vector, and $y\in[k]$ signifies the data label. We first present the formal definition of robust and non-robust features as follows.

###### Definition 2.1 (Robust and Non-robust Features) .

We assume that each label class $j\in[k]$ is associated with two types of features, for the sake of mathematical simplicity, represented as two feature vectors $\bm{u}_{j}$ (robust feature) and $\bm{v}_{j}$ (non-robust feature), both in $\mathbb{R}^{d}$. For notation simplicity,
we also assume that all the features are orthonormal and parallel to the coordinate axes. Namely,
the set of all features is defined as

$$ $\mathcal{F}:=\{\bm{u}_{j},\bm{v}_{j}\}_{j\in[k]},$ $$

which satisfies that

$$ $\forall\bm{f}\in\mathcal{F},\|\bm{f}\|_{2}=\|\bm{f}\|_{\infty}=1\quad\textit{ and}\quad\forall\bm{f}\neq\bm{f^{\prime}}\in\mathcal{F},\bm{f}\perp\bm{f^{ \prime}}.$ $$

For simplicity, we focus on the case when the dimension of patch $d$ is sufficiently large (i.e. we assume $d=\operatorname{poly}(k)$ for a large polynomial) such that all $2k$ features can be orthogonal in the space $\mathbb{R}^{d}$. And we use “with high probability” to denote with probability at least $1-e^{-\Omega(\operatorname{log}^{2}d)}$.

Now, we give the following robust/non-robust-feature-decomposition-based patch-structured data distribution and some assumptions about it.

###### Definition 2.2 (Patch Data Distribution) .

Each data pair $(\bm{X},y)\in\left(\mathbb{R}^{d}\right)^{P}\times[k]$ is generated from the distribution $\mathcal{D}$ with latent distributions $\{(\mathcal{D}_{\mathcal{J},y},\mathcal{D}_{\alpha,y},\mathcal{D}_{\beta,y})\}
_{y\in[k]}$, where $\mathcal{D}_{\mathcal{J},y}$ is a probability distribution over all $2$-partitions of $[P]$ and $\mathcal{D}_{\alpha,y},\mathcal{D}_{\beta,y}$ are two distributions over the positive real number. Then, it generates data points as follows.

- 1.
The label $y$ is uniformly drawn from $[k]$.
- 2.
Uniformly draw the two-type patch index sets $(\mathcal{J}_{\textit{R}},\mathcal{J}_{\textit{NR}})\subset[P]\times[P]$ from the distribution $\mathcal{D}_{\mathcal{J},y}$, where $\mathcal{J}_{\textit{R}}$ and $\mathcal{J}_{\textit{NR}}$ corresponds to the robust-feature patches and non-robust feature patches such that $\mathcal{J}_{\textit{R}}\cup\mathcal{J}_{\textit{NR}}=[P]$ and $\mathcal{J}_{\textit{R}}\cap\mathcal{J}_{\textit{NR}}=\emptyset$.
- 3.
For each $p\in[P]$, the corresponding patch vector is generated as
$\bm{x}_{p}:=\begin{cases}\alpha_{p}\bm{u}_{y}+\bm{\xi}_{p},\textit{ if }p\in
\mathcal{J}_{\textit{R}}&\textit{ (robust-feature patch)}\\
\beta_{p}\bm{v}_{y}+\bm{\xi}_{p},\textit{ if }p\in\mathcal{J}_{\textit{NR}}&
\textit{ (non-robust-feature patch)}\end{cases}$
where $\alpha_{p},\beta_{p}>0$ are the random coefficients sampled from the distribution $\mathcal{D}_{\alpha,y},\mathcal{D}_{\beta,y}$ respectively, and $\bm{\xi}_{p}\sim\mathcal{N}(\bm{0},\sigma_{n}^{2}\mathcal{I}_{d})$ is the random Gaussian noise with variance $\sigma_{n}^{2}$.

###### Assumption 2.3 .

We suppose that the following conditions holds for the data distribution $\mathcal{D}$. In a data point $(\bm{X},y)$ sampled from $\mathcal{D}$, with high probability, it satisfies:

- •
Robust feature is stronger than non-robust feature: $\forall(p,p^{\prime})\in\mathcal{J}_{\textit{R}}\times\mathcal{J}_{\textit{NR}
},\alpha_{p}\gg\beta_{p^{\prime}}$.
- •
Non-robust feature is denser than robust feature: $\exists\tau\geq 0,\sum_{p\in\mathcal{J}_{\textit{R}}}\alpha_{p}^{\tau}\ll\sum_
{p\in\mathcal{J}_{\textit{NR}}}\beta_{p}^{\tau}$.

Regarding the first condition of Assumption 2.3. We further assume that $\alpha_{p},\beta_{p}$ concentrate on their expectations (i.e., w.h.p. $\alpha_{p}\approx\mathbb{E}[\alpha_{p}],\beta_{p}\approx\mathbb{E}[\beta_{p}]$) and $\mathbb{E}[\alpha_{p}]\gg\mathbb{E}[\beta_{p}]=\Theta(\sigma_{n}\sqrt{d})$ for simplicity. Then, we know, with high probability over a sampled data, it holds that $\forall(p,p^{\prime})\in\mathcal{J}_{\textit{R}}\times\mathcal{J}_{\textit{NR}
},\alpha_{p}\gg\beta_{p}\approx\|\bm{\xi}_{p^{\prime}}\|_{2}\approx\|\bm{\xi}_
{p}\|_{2}\approx\sigma_{n}\sqrt{d}$, which means that robust-feature patches $\bm{x}_{p}=\alpha_{p}\bm{u}_{y}+\bm{\xi}_{p}\approx\alpha_{p}\bm{u}_{y}$ appear more prominent, but non-robust-feature patches $\bm{x}_{p^{\prime}}=\beta_{p}\bm{v}_{y}+\bm{\xi}_{p^{\prime}}$ are noise-like.

Regarding the second condition of Assumption 2.3. Here, $\tau$ is an absolutely constant. We notice that when $\tau=0$, it implies w.h.p. $|\mathcal{J}_{\textit{R}}|\ll|\mathcal{J}_{\textit{NR}}|$, which manifests that non-robust-feature patches are denser than robust-feature patches. And we assume $\tau\geq 3$ for simplifying our mathematical analysis.

Our Patch Data Aligns with Realistic Images. In all, it shows that Assumption 2.3 can be tied to a down-sized version of convolutional networks applied to image classification data. With a small kernel size, high-magnitude good features that are easily perceivable by humans in an image typically appear only at a few patches (such as the ears of a cat or the nose of an elephant), and most other patches look like random noise to human observers (such as the textures of cats and elephants blended into a random background). See illustrations of real images and our patch data in Figures 1 and 2.

###### Remark 2.4 .

Previous empirical works of Ilyas et al. (); Kim et al. () characterize robust features as useful for both clean and robust classification, whereas non-robust features, although helpful for clean classification, fail in robust scenarios. Consistent with these observations, our definitions and assumptions suggest that networks leveraging robust features $\{\bm{u}_{i}\}_{i\in[k]}$ act as robust classifiers, while those relying on non-robust features $\{\bm{v}_{i}\}_{i\in[k]}$ perform well on clean data but not on perturbed data, as detailed in Propositions 3.1 and 3.2 in Section 3.

###### Definition 2.1 (Robust and Non-robust Features) .

###### Definition 2.2 (Patch Data Distribution) .

###### Assumption 2.3 .

###### Remark 2.4 .

### 2.3 Network Learner

We consider the setting of learning the data distribution $\mathcal{D}$ by applying the same two-layer convolutional architecture used in Allen-Zhu and Li ()
with the following smoothed ReLU activation.

Activation. For integer $q\geq 2$ and threshold $\varrho$, the smoothed ReLU is defined as $\widetilde{\operatorname{ReLU}}(z):=0$ for $z\leq 0;\widetilde{\operatorname{ReLU}}(z):=\frac{z^{q}}{q\varrho^{q-1}}$ for $z\in[0,\varrho];$ and $\widetilde{\operatorname{ReLU}}(z):=z-\left(1-\frac{1}{q}\right)\varrho$ for $z\geq\varrho$.

$\widetilde{\operatorname{ReLU}}$ addresses the non-smoothness of original ReLU function at zero.We focus on the case when $q=3$ and $\varrho=\frac{1}{\operatorname{polylog}(d)}$ for simplicity, while our result
indeed applies to other constants $q\in[3,\tau]$.

Network Model. For the $k$-class classification task, we consider the following two-layer convolutional neural network as $\bm{F}(\bm{X})=(F_{1}(\bm{X}),F_{2}(\bm{X}),\dots,F_{k}(\bm{X})):\left(\mathbb
{R}^{d}\right)^{P}\rightarrow\mathbb{R}^{k}$, and $F_{i}(\bm{X})$ denotes

$$ $F_{i}(\bm{X}):=\sum_{r\in[m]}\sum_{p\in[P]}\widetilde{\operatorname{ReLU}}( \langle\bm{w}_{i,r},\bm{x}_{p}\rangle),$ $$

where $\{\bm{w}_{i,r}\in\mathbb{R}^{d}\}_{(i,r)\in[k]\times[m]}$ are learnable weights for different convolutional filters. We set the width $m=\operatorname{polylog}(d)$ to achieve
mildly over-parameterization for efficient optimization purpose.

### 2.4 Standard Training

Training Objective. During the standard training, we learn the concept class (namely, the labeled data distribution $\mathcal{D}$) by minimizing the cross-entropy loss function $\mathcal{L}_{\textit{CE}}$ using $N=\operatorname{poly}(d)$ training data points $\mathcal{Z}=\left\{\left(\bm{X}_{i},y_{i}\right)\right\}_{i\in[N]}$ randomly sampled from $\mathcal{D}$. By denoting $\mathcal{L}_{\textit{CE}}(\bm{F};\bm{X},y):=-\log\frac{e^{F_{y}(X)}}{\sum_{j
\in[k]}e^{F_{j}(X)}}$, we use the empirical loss $\mathcal{L}_{\textit{CE}}(\bm{F}):=\mathbb{E}_{(\bm{X},y)\sim\mathcal{Z}}[
\mathcal{L}_{\textit{CE}}(\bm{F};\bm{X},y)]$ as objective.

Network Initialization. We randomly initialize the network $\bm{F}$ by letting each $\bm{w}_{i,r}^{(0)}\sim\mathcal{N}\left(0,\sigma_{0}^{2}\mathcal{I}_{d}\right)$ for $\sigma_{0}^{2}=\frac{1}{d}$, which is the standard Xavier initialization (Glorot and Bengio, ).

Training Algorithm. To train the model, at each iteration $t$ we update using the gradient descent (GD) with small learning rate $\eta\leq\frac{1}{\operatorname{poly}(d)}$:
$\bm{w}_{i,r}^{(t+1)}=\bm{w}_{i,r}^{(t)}-\eta\mathbb{E}_{(\bm{X},y)\sim\mathcal
{Z}}\left[\nabla_{\bm{w}_{i,r}}\mathcal{L}_{\textit{CE}}\left(\bm{F}^{(t)};\bm
{X},y\right)\right],$

where we run the algorithm for $T=\frac{\operatorname{poly}(d)}{\eta}$ iterations. We use $\bm{F}^{(t)}$ to denote the model at iteration $t$.

### 2.5 Adversarial Training

$\ell_{p}$-Adversarial Robustness. In our work, we consider $\ell_{p}$-robustness within a perturbation radius $\epsilon>0$, especially the $\ell_{\infty}$-norm on which we focus henceforth for notation simplicity. Our main results can be easily extended to other $\ell_{p}$-norm case $(p\geq 2)$.

Small Perturbation Radius. In our setting, we choose $\epsilon=\Theta(\sigma_{n}\sqrt{d})$. Then, for two data points $(\bm{X},y),(\bm{X}^{\prime},y^{\prime})\sim\mathcal{D}$ with distinct labels $y\neq y^{\prime}\in[k]$, it can be checked that w.h.p. $\|\bm{X}-\bm{X}^{\prime}\|_{\infty}\gg\Theta(\sigma_{n}\sqrt{d})=\Theta(\epsilon)$, which is consistent with the empirical observation that typical perturbation radius is often much smaller than the separation distance between different classes (Yang et al., ).

Adversarial Example. For a given network $\mathcal{F}$ and a data point $(\bm{X},y)$, we suppose that $\mathcal{F}$ is an accurate classifier on $(\bm{X},y)$. We say that $\widetilde{\bm{X}}$ is an adversarial example (Szegedy et al., ) if the classifier predicts a wrong label for it (i.e. $\operatorname{argmax}_{j\in[k]}F_{j}(\widetilde{\bm{X}})\neq y$) and the perturbation $\bm{\Delta}:=\widetilde{\bm{X}}-\bm{X}$ satisfies $\|\bm{\Delta}\|_{\infty}\leq\epsilon$.

Adversarial Training Algorithm. During adversarial training, we first find the adversarial examples $(\widetilde{\bm{X}},y)$ by one-step gradient ascent with learning rate $\tilde{\eta}$ ($\gg\eta$) over the margin loss $\mathcal{L}_{\textit{margin}}(\bm{F};\bm{X},y)$ using training data points $(\bm{X},y)\in\mathcal{Z}$. Here, we choose $\mathcal{L}_{\textit{margin}}(\bm{F};\bm{X},y):=-F_{y}(\bm{X})$ for simplicity, and our theoretical analysis can also be extended to the standard margin-based adversarial-attack objective function $\mathcal{L}_{\textit{margin}}(\bm{F};\bm{X},y):=-\left(F_{y}(\bm{X})-
\operatorname{max}\limits_{j\in[k]\setminus\{y\}}F_{j}(\bm{X})\right)$ (Carlini and Wagner, ; Gowal et al., ; Sriramanan et al., ). And then we train the network parameters $\{\bm{w}_{i,r}\}_{(i,r)\in[k]\times[m]}$ by taking gradient descent over the adversarial loss $\mathbb{E}_{(\bm{X},y)\sim\mathcal{Z}}\left[\mathcal{L}_{\textit{CE}}\left(\bm
{F};\widetilde{\bm{X}},y\right)\right]$.

Concretely, the adversarial examples $\{(\widetilde{\bm{X}}^{(t)},y)\}$ and the network $\bm{F}^{(t)}$ are updated alternatively as

$$ $\begin{cases}\widetilde{\bm{X}}^{(t)}=\bm{X}+\operatorname{Clip}_{\infty, \epsilon}\left(\tilde{\eta}\nabla_{\bm{X}}\mathcal{L}_{\textit{margin}}\left( \bm{F}^{(t)};\bm{X},y\right)\right),\quad\forall(\bm{X},y)\in\mathcal{Z},\\ \bm{w}_{i,r}^{(t+1)}=w_{i,r}^{(t)}-\eta\mathbb{E}_{(\bm{X},y)\sim\mathcal{Z}} \left[\nabla_{\bm{w}_{i,r}}\mathcal{L}_{\textit{CE}}\left(\bm{F}^{(t)}; \widetilde{\bm{X}}^{(t)},y\right)\right],\quad\forall(i,r)\in[k]\times[m],\end {cases}$ $$

where $\epsilon>0$ is the $\ell_{\infty}$-perturbation radius and patch-wise clip function $\operatorname{Clip}_{\infty,\epsilon}(\cdot)$ is used to enable $\widetilde{\bm{X}}^{(t)}\in\mathbb{B}_{\infty}(\bm{X},\epsilon)$, which is defined as, for the clip radius $\rho>0$ and a given flattened patch data $\bm{Z}=(z_{1},z_{2},\dots,z_{Pd})\in\left(\mathbb{R}^{d}\right)^{P}$, $\operatorname{Clip}_{\infty,\rho}(\bm{Z}):=(\tilde{z}_{1},\tilde{z}_{2},\dots,
\tilde{z}_{Pd}),\tilde{z}_{j}=\frac{z_{j}}{\operatorname{max}\{1,\|z_{j}\|_{
\infty}/\rho\}},\forall j\in[Pd]$.

###### Remark 2.5 .

Indeed, a more general form of adversarial example update in adversarial training algorithm is to directly maximize the loss value over the perturbed data point, i.e.

$$ $\widetilde{\bm{X}}^{(t)}=\bm{X}+\operatorname{argmax}_{\|\bm{\Delta}\|_{\infty }\leq\epsilon}\mathcal{L}_{\textit{margin}}\left(\bm{F}^{(t)};\bm{X}+\bm{ \Delta},y\right)\quad\forall(\bm{X},y)\in\mathcal{Z}.$ $$

However, different from some previous works (Li et al., ; Javanmard and Soltanolkotabi, ; Chen et al., ) that study training dynamics of adversarial training under linear classifier, we are unable to derive the closed-form solution of adversarial examples due to the high non-linearity and non-convexity of the objective function $\mathcal{L}_{\textit{margin}}\left(\bm{F}^{(t)};\bm{X}+\bm{\Delta},y\right)$ over $\bm{\Delta}$. To overcome this challenge, we use one-step gradient ascent method to approximate the optimal solution.

###### Remark 2.5 .

## 3 Warm Up: There Exist both Non-Robust and Robust Global Minima

In this section, as a warm up, we show that there exist both robust global minima and non-robust global minima due to the non-convexity of empirical risk $\mathcal{L}_{\textit{CE}}(\bm{F})$ over the parameters $\{\bm{w}_{i,r}\}_{(i,r)\in[k]\times[m]}$.

###### Proposition 3.1 (The Existence of Non-robust Global Minima) .

We consider the special case when $m=1$ and $\bm{w}_{i,1}=\gamma\bm{v}_{i}$, where $\gamma>0$ is a scale coefficient. Then, it holds that the standard empirical risk satisfies $\operatornamewithlimits{lim}_{\gamma\rightarrow\infty}\mathcal{L}_{\textit{CE}
}(\bm{F})=o(1)$, but the adversarial test error satisfies $\operatornamewithlimits{lim}_{\gamma\rightarrow\infty}\mathbb{P}_{(\bm{X},y)
\sim\mathcal{D}}\left[\exists\bm{\Delta}\in\left(\mathbb{R}^{d}\right)^{P}
\textit{ s.t. }\|\bm{\Delta}\|_{\infty}\leq\epsilon,\operatorname{argmax}_{i
\in[k]}F_{i}(\bm{X}+\bm{\Delta})\neq y\right]=1-o(1)$.

###### Proposition 3.2 (The Existence of Robust Global Minima) .

We consider the special case when $m=1$ and $\bm{w}_{i,1}=\gamma\bm{u}_{i}$, where $\gamma>0$ is a scale coefficient. Then, it holds that the standard empirical risk satisfies $\operatornamewithlimits{lim}_{\gamma\rightarrow\infty}\mathcal{L}_{\textit{CE}
}(\bm{F})=o(1)$, and the adversarial test error satisfies $\operatornamewithlimits{lim}_{\gamma\rightarrow\infty}\mathbb{P}_{(\bm{X},y)
\sim\mathcal{D}}\left[\exists\bm{\Delta}\in\left(\mathbb{R}^{d}\right)^{P}
\textit{ s.t. }\|\bm{\Delta}\|_{\infty}\leq\epsilon,\operatorname{argmax}_{i
\in[k]}F_{i}(\bm{X}+\bm{\Delta})\neq y\right]=o(1)$.

Proposition 3.1 and Proposition 3.2 demonstrate that a network is vulnerable to adversarial perturbations if it relies solely on learning non-robust features. Conversely, a network that learns all robust features can achieve a state of robustness. In general, by calculating the gradient of empirical loss, it seems that the whole weights during gradient-based training will have the following form

$$ $\bm{w}_{i,r}\approx A_{i,r}\bm{u}_{i}+B_{i,r}\bm{v}_{i}+\textit{Noise},$ $$

where $A_{i,r},B_{i,r}>0$ represent the coefficients for learning robust and non-robust features, respectively, and the ’Noise’ term encompasses elements learned from other non-diagonal features $\bm{u}_{j},\bm{v}_{j}(j\neq i)$, as well as random noise $\bm{\xi}_{p}$.

Therefore, we know that the network learns the $i$-th class if and only if either $A_{i,r}$ or $B_{i,r}$ is sufficiently large. However, to robustly learn the $i$-th class, the network must primarily learn the robust feature $\bm{u}_{i}$, rather than the non-robust feature $\bm{v}_{i}$, which motivates us to analyze the feature learning process of standard training and adversarial training to understand the underlying mechanism why adversarial examples exist and how adversarial training algorithm works.

###### Proposition 3.1 (The Existence of Non-robust Global Minima) .

###### Proposition 3.2 (The Existence of Robust Global Minima) .

## 4 Main Results

We first formally introduce the concept, feature learning accuracy, as the following definition.

###### Definition 4.1 (Feature Learning Accuracy) .

For a given feature subset $\mathcal{H}\subset\mathcal{F}$ ($\mathcal{F}$ is all feature set as the same as Definition 2.1), $\mathcal{H}$-extended feature representative distribution $\mathcal{D}_{\mathcal{H}}$ and classifier model $\bm{F}$, we define the feature learning accuracy as $\mathbb{P}_{(\bm{X}_{\bm{f}},y)\sim\mathcal{D}_{\mathcal{H}}}\left[
\operatorname{argmax}_{i\in[k]}F_{i}(\bm{X}_{\bm{f}})=y\right]$, where $\bm{X}_{\bm{f}}(\bm{f}\in\mathcal{H})$ is the $\bm{f}$-extended representative and $y$ is the label which feature $\bm{f}$ corresponds to.

Here, we choose $\mathcal{F}_{\textit{R}}:=\{\bm{u}_{i}\}_{i\in[k]},\mathcal{F}_{\textit{NR}}:=
\{\bm{v}_{i}\}_{i\in[k]}\subset\mathcal{F}$ as robust/non-robust feature sets. We construct $\mathcal{D}_{\mathcal{F}_{\textit{R}}}/\mathcal{D}_{\mathcal{F}_{\textit{NR}}}$ by sampling $(\bm{X},y)\sim\mathcal{D}$ and setting $\bm{X}_{\bm{f}}$ to $\bm{X}$ with all instances of feature $\bm{v}_{i}/\bm{u}_{i}$ replaced by all-zero vector (a figurative illustration is presented in Figure 2).

###### Remark 4.2 .

We define feature learning accuracy based on whether the model $\bm{F}$ can accurately classify data points when presented with only a single signal feature $\bm{f}$, which indeed generalizes the notion of weight-feature correlation $\langle\bm{w}_{i,r},\bm{f}\rangle$ to general non-linear models and non-linear features.

Now, we state the main theorems in this paper as follows.

###### Theorem 4.3 (Standard Training Converges to Non-robust Global Minima) .

For sufficiently large $d$, suppose we train the model using the standard training starting from the random initialization, then after $T=\Theta(\operatorname{poly}(d)/\eta)$ iterations, with high probability over the sampled training dataset $\mathcal{Z}$, the model $\bm{F}^{(T)}$ satisfies:

- •
Standard training is perfect: for all $(\bm{X},y)\in\mathcal{Z}$, all $i\in[k]\backslash\{y\}:F_{y}^{(T)}(\bm{X})>F_{i}^{(T)}(\bm{X})$.
- •
Non-robust features are learned: $\mathbb{P}_{(\bm{X}_{\bm{f}},y)\sim\mathcal{D}_{\mathcal{F}_{\textit{NR}}}}
\left[\operatorname{argmax}_{i\in[k]}F_{i}^{(T)}(\bm{X}_{\bm{f}})\neq y\right]
=o(1)$.
- •
Standard test accuracy is good: $\mathbb{P}_{(\bm{X},y)\sim\mathcal{D}}\left[\operatorname{argmax}_{i\in[k]}F_{
i}^{(T)}(\bm{X})\neq y\right]=o(1)$.
- •
Robust test accuracy is bad: for any given data $(\bm{X},y)$, using the following perturbation $\bm{\Delta}(\bm{X},y):=(\bm{\delta}_{1},\bm{\delta}_{2},\dots,\bm{\delta}_{P})$, where $\bm{\delta}_{p}:=-\beta_{p}\bm{v}_{y}+\epsilon\bm{v}_{y^{\prime}}$ for $p\in\mathcal{J}_{\textit{NR}}$; $\bm{\delta}_{p}:=\bm{0}$ for $p\in\mathcal{J}_{\textit{R}}$, and $y^{\prime}$ is randomly chosen from $[k]\setminus\{y\}$ (which does not depend on the model $\bm{F}^{(T)}$ and is illustrated in Figure 2), we have
$\mathbb{P}_{(\bm{X},y)\sim\mathcal{D}}\left[\operatorname{argmax}_{i\in[k]}F_{
i}^{(T)}(\bm{X}+\bm{\Delta}(\bm{X},y))\neq y\right]=1-o(1).$

Theorem 4.3 states that standard training of a neural network achieves good standard accuracy but poor robust performance. This is due to the dominance of non-robust feature learning during the training dynamics. Moreover, we notice that a perturbation based on non-robust features is sufficient to confuse the network. This implies that adversarial examples may stem from non-robust features.

Next, we present our main results about adversarial training as the following theorem.

###### Theorem 4.4 (Adversarial Training Converges to Robust Global Minima) .

For sufficiently large $d$, suppose we train the model using the adversarial training algorithm starting from the random initialization, then after $T=\Theta(\operatorname{poly}(d)/\eta)$ iterations, with high probability over the sampled training dataset $\mathcal{Z}$, the model $\bm{F}^{(T)}$ satisfies:

- •
Adversarial training is perfect: for all $(\bm{X},y)\in\mathcal{Z}$ and all perturbation $\bm{\Delta}$ satisfying $\|\bm{\Delta}\|_{\infty}\leq\epsilon$, all $i\in[k]\backslash\{y\}:F_{y}^{(T)}(\bm{X}+\bm{\Delta})>F_{i}^{(T)}(\bm{X}+\bm{
\Delta})$.
- •
Robust features are learned: $\mathbb{P}_{(\bm{X}_{\bm{f}},y)\sim\mathcal{D}_{\mathcal{F}_{\textit{R}}}}
\left[\operatorname{argmax}_{i\in[k]}F_{i}^{(T)}(\bm{X}_{\bm{f}})\neq y\right]
=o(1)$.
- •
Robust test accuracy is good:
$\mathbb{P}_{(\bm{X},y)\sim\mathcal{D}}\left[\exists\bm{\Delta}\in\left(\mathbb
{R}^{d}\right)^{P}\textit{ s.t. }\|\bm{\Delta}\|_{\infty}\leq\epsilon,
\operatorname{argmax}_{i\in[k]}F_{i}^{(T)}(\bm{X}+\bm{\Delta})\neq y\right]=o(
1).$

Theorem 4.4 shows that the network learner provably learns robust features through adversarial training method, which thereby improves the network robustness against adversarial perturbations.

###### Definition 4.1 (Feature Learning Accuracy) .

###### Remark 4.2 .

###### Theorem 4.3 (Standard Training Converges to Non-robust Global Minima) .

###### Theorem 4.4 (Adversarial Training Converges to Robust Global Minima) .

## 5 Technique Overview: Learning Process Analysis

We present a high level proof intuition for the training dynamics. For simplicity, we consider a simplified setup with the noiseless population risk (i.e. $\sigma_{n}=0,\textit{w.h.p. }\alpha_{p}\gg\epsilon\gtrsim\beta_{p},\mathcal{Z}
=\mathcal{D}$).

By analyzing gradient descent dynamics of the model $\bm{F}$, we know that there exists time-variant coefficient sequences $\{A_{i,r}^{(t)}\}_{t=0}^{\infty}$ and $\{B_{i,r}^{(t)}\}_{t=0}^{\infty}$ such that, for any pair $(i,r)\in[k]\times[m]$, it holds that $\bm{w}_{i,r}^{(t)}\approx A_{i,r}^{(t)}\bm{u}_{i}+B_{i,r}^{(t)}\bm{v}_{i}$. Then, we focus on dynamics of these two coefficient sequences.

### 5.1 Learning Process Analysis for Standard Training

For standard training, by denoting $\operatorname{logit}_{i}(\bm{F},\bm{X}):=\frac{e^{F_{i}(\bm{X})}}{\sum_{j\in[k
]}e^{F_{j}(\bm{X})}}$, we have the following lemma.

###### Lemma 5.1 (Feature Learning Iteration for Standard Training) .

During standard training, for any time $t\geq 0$ and pair $(i,r)\in[k]\times[m]$, the two sequences $\{A_{i,r}^{(t)}\}$ and $\{B_{i,r}^{(t)}\}$ satisfy:

$$ $\begin{cases}A_{i,r}^{(t+1)}=A_{i,r}^{(t)}+\frac{\eta}{k}\mathbb{E}_{\mathcal{ D}_{\mathcal{J},i},\mathcal{D}_{\alpha,i}}\bigg{[}\big{(}1-\operatorname{logit }_{i}(\bm{F}^{(t)},\bm{X})\big{)}\sum\limits_{p\in\mathcal{J}_{\textit{R}}} \widetilde{\operatorname{ReLU}}^{\prime}\left(\alpha_{p}A_{i,r}^{(t)}\right) \alpha_{p}\bigg{]},\\ B_{i,r}^{(t+1)}=B_{i,r}^{(t)}+\frac{\eta}{k}\mathbb{E}_{\mathcal{D}_{\mathcal{ J},i},\mathcal{D}_{\beta,i}}\bigg{[}\big{(}1-\operatorname{logit}_{i}(\bm{F}^{ (t)},\bm{X})\big{)}\sum\limits_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{ \operatorname{ReLU}}^{\prime}\left(\beta_{p}B_{i,r}^{(t)}\right)\beta_{p}\bigg {]}.\end{cases}$ $$

Approximation Near Initialization. At the start of training, due to our random initialization, i.e., $\bm{w}_{i,r}\sim\mathcal{N}(\bm{0},\bm{I}_{d}/\operatorname{poly}(d))$, we have a constant loss derivative, namely $1-\operatorname{logit}_{i}(\bm{F}^{(t)},\bm{X})=\Theta(1)$. And we know that, w.h.p., the activation function predominantly lies within the polynomial part.

Non-Robust Feature Learning Dominates. Under Assumption 2.3, it holds that $\mathbb{E}\big{[}\sum_{p\in\mathcal{J}_{\textit{NR}}}\beta_{p}^{q}\big{]}\gg
\mathbb{E}\big{[}\sum_{p\in\mathcal{J}_{\textit{R}}}\alpha_{p}^{q}\big{]}$, which implies that the non-robust feature learning $\operatorname{max}_{r\in[m]}B_{i,r}^{(t)}$ increases more rapidly than the robust feature learning $\operatorname{max}_{r\in[m]}A_{i,r}^{(t)}$. Moreover, by applying Tensor Power Method Lemma (Allen-Zhu and Li, ), we know that $\operatorname{max}_{r\in[m]}B_{i,r}^{(t)}$ attains an order of $\tilde{\Theta}(1)$, while $\operatorname{max}_{r\in[m]}A_{i,r}^{(t)}$ still maintains $\tilde{o}(1)$-order. Afterward, the loss derivative approaches zero (i.e. $1-\operatorname{logit}_{i}(\bm{F}^{(t)},\bm{X})=o(1)$), and the network ultimately converges within the linear region of the $\widetilde{\operatorname{ReLU}}$.

Figure: Figure 3: Simulations on synthetic data. The two left figures: dynamics of normalized weight-feature correlations for std/adv training. The two right figures: learning curves for std/adv training.
Refer to caption: x3.png

###### Lemma 5.1 (Feature Learning Iteration for Standard Training) .

### 5.2 Learning Process Analysis for Adversarial Training

For adversarial training, we divide the learning process into two phases via the following lemma.

###### Lemma 5.2 (Feature Learning Iteration for Adversarial Training at Polynomial Part) .

During adversarial training, there exists some time threshold $T_{0}>0$ such that, for any early time $0\leq t\leq T_{0}$ and pair $(i,r)\in[k]\times[m]$, the two sequences $\{A_{i,r}^{(t)}\}$ and $\{B_{i,r}^{(t)}\}$ satisfy:

$$ $\begin{cases}A_{i,r}^{(t+1)}\approx A_{i,r}^{(t)}+\Theta(\eta)\left(A_{i,r}^{( t)}\right)^{q-1}\mathbb{E}\bigg{[}\sum\limits_{p\in\mathcal{J}_{\textit{R}}} \alpha_{p}^{q}\big{(}1-\operatorname{min}\big{\{}\frac{\epsilon}{\alpha_{p}}, \tilde{\Theta}(\tilde{\eta})\sum\limits_{s\in[m]}\big{(}A_{i,s}^{(t)}\big{)}^{ q}\big{\}}\big{)}^{q}\bigg{]},\\ B_{i,r}^{(t+1)}\approx B_{i,r}^{(t)}+\Theta(\eta)\left(B_{i,r}^{(t)}\right)^{q -1}\mathbb{E}\bigg{[}\sum\limits_{p\in\mathcal{J}_{\textit{NR}}}\beta_{p}^{q} \big{(}1-\operatorname{min}\big{\{}\frac{\epsilon}{\beta_{p}},\tilde{\Theta}( \tilde{\eta})\sum\limits_{s\in[m]}\big{(}B_{i,s}^{(t)}\big{)}^{q}\big{\}}\big{ )}^{q}\bigg{]}.\end{cases}$ $$

Phase I: First, Network Partially Learns Non-Robust Features. At the beginning, due to our small initialization, we know all feature learning coefficients $A_{i,r}^{(t)},B_{i,r}^{(t)}=o(1)$, which suggests that the total feature learning $\sum_{s\in[m]}\big{(}A_{i,s}^{(t)}\big{)}^{q}$ and $\sum_{s\in[m]}\big{(}B_{i,s}^{(t)}\big{)}^{q}$ are sufficiently small. Then, the feature learning process is similar to standard training until the non-robust feature learning becomes large.

Phase II: Next, Robust Feature Learning Starts Increasing. Once the total non-robust feature learning $\sum_{s\in[m]}\big{(}B_{i,s}^{(t)}\big{)}^{q}$ attains an order of $\tilde{\Theta}(\tilde{\eta}^{-1})$, it is known that the non-robust feature learning will stop, due to $\frac{\epsilon}{\beta_{p}}\gtrsim 1$ and $1-\tilde{\Theta}(\tilde{\eta})\sum_{s\in[m]}\big{(}B_{i,s}^{(t)}\big{)}^{q}\approx
0$. In contrast, the robust feature learning continues to increase since it always holds that $1-\operatorname{min}\big{\{}\frac{\epsilon}{\alpha_{p}},\tilde{\Theta}(\tilde{
\eta})\sum_{s\in[m]}\big{(}A_{i,s}^{(t)}\big{)}^{q}\big{\}}\geq 1-\frac{
\epsilon}{\alpha_{p}}\geq\Omega(1)$. Thus, the robust feature learning will increase over the non-robust feature learning finally, and the network converges to robust regime, i.e. $\operatorname{max}_{r\in[m]}A_{i,r}^{(T)}\gg\operatorname{max}_{r\in[m]}B_{i,r
}^{(T)}$ for large $T$.

###### Lemma 5.2 (Feature Learning Iteration for Adversarial Training at Polynomial Part) .

## 6 Experiments

### 6.1 Simulations on Synthetic Data

Experiment Settings. We first perform numerical experiments
on synthetic data to verify our theoretical results. Here, our synthetic data is generated according to Definition 2.2. We choose the hyperparameters as: $k=2,d=100,P=16,q=\tau=3,\varrho=1,\epsilon=1.2,N=100,m=100,\sigma_{0}=0.01,
\sigma_{n}=0.1,\eta=0.1,\tilde{\eta}=10^{3},T=1000$, and $|\mathcal{J}_{\textit{R}}|\equiv 1,|\mathcal{J}_{\textit{NR}}|\equiv 15,\alpha
_{p}\equiv 2,\beta_{p}\equiv 1$ for each $(\bm{X},y)\sim\mathcal{D}$. Then, we run the standard training and adversarial training algorithms, and we characterize the feature learning process via the dynamics of normalized weight-feature correlations: $\operatorname{max}_{r\in[m]}\langle\bm{w}_{i,r},\bm{u}_{i}\rangle/\|\bm{u}_{i}
\|_{2},i=1,2$ (robust feature learning), and $\operatorname{max}_{r\in[m]}\langle\bm{w}_{i,r},\bm{v}_{i}\rangle/\|\bm{v}_{i}
\|_{2},i=1,2$ (non-robust feature learning). We calculate the robust test accuracy by the standard PGD attack.

Experiment Results. The numerical results are reported in Figure 3. We observe that, in standard training, non-robust feature learning dominates during training process. There exists a phase transition during adversarial training (it happens nearly at $150$-epoch). Phase I: the network learner mainly learns non-robust features to achieve perfect standard test accuracy, but robust test accuracy maintains zero. Phase II: the increments of non-robust feature learning is restrained while robust feature learning and robust test accuracy start to increase. These results empirically verify our analysis in Section 5.

### 6.2 Experiments on Real-world Datasets

Figure: (a) MNIST
Refer to caption: x7.png

Experiment Settings. Instead of weight-feature correlation used in synthetic data setting, here on MNIST, CIFAR10 and SVHN datasets, we apply feature learning accuracy in Definition 4.1 to measure non-robust/robust feature learning during training dynamics. Similar to the method proposed in Ilyas et al. (), we reconstruct datasets $\hat{\mathcal{D}}_{\textit{NR}},\hat{\mathcal{D}}_{\textit{R}}$ as the feature representative distributions by a one-to-one mapping $\bm{X}\mapsto\hat{\bm{X}}$. Specifically, we solve the following optimization problem to derive $\hat{\bm{X}}$: $\operatorname{min}\limits_{\hat{\bm{X}}}\|\bm{G}(\hat{\bm{X}})-\bm{G}(\bm{X})
\|_{2}$,
where $\bm{X}\in\mathcal{D}$ is the target data point, and $\bm{G}$ is the mapping from input $\bm{X}$ to the representation layer for network learners. When $\bm{G}$ is chosen from a standard/adversarial-trained network, we derive the non-robust/robust representative dataset $\hat{\mathcal{D}}_{\textit{NR}}/\hat{\mathcal{D}}_{\textit{R}}$. Then, we run the standard training and adversarial training algorithms and record the dynamics of feature learning accuracy w.r.t. $\hat{\mathcal{D}}_{\textit{NR}}$ and $\hat{\mathcal{D}}_{\textit{R}}$. For MNIST, we choose ResNet18 and $\ell_{\infty}$-perturbation with radius $0.3$, and we run algorithms for $30$ iterations. For CIFAR10 and SVHN, we choose WideResNet-34-10 and $\ell_{\infty}$-perturbation with radius $8/255$ and run algorithms for $200$ iterations.

Experiment Results. The results are presented in Figure 4. For all three datasets, we could see that, in standard training, network learners predominantly learn non-robust features rather than robust features, while adversarial training can both inhabit non-robust feature learning and strengthen robust feature learning, which empirically demonstrates our theoretical results in Section 4.

## 7 Conclusion

In this paper, we provide a theoretical explanation why adversarial examples widely exist and how the adversarial training method improves the model robustness. Based on robust/non-robust feature decomposition, we prove an implicit bias of standard training that network mainly learns non-robust features, leading to adversarial examples. Furthermore, we demonstrate that adversarial training can provably enhance the robust feature learning and suppress the non-robust feature learning. We believe our theory gives some insights into the inner workings of adversarial robust learning in deep learning.

## Appendix A Additional Experiment Results about Real-Image Datasets

### A.1 Feature Learning Process on Real-world Datasets

Figure: (a) MNIST
Refer to caption: x13.png

**Table 1: Feature learning results on real-world datasets**
| Dataset | Algorithm | Std Test Acc | Rob Test Acc | Non-robust FL | Robust FL |
| --- | --- | --- | --- | --- | --- |
| MNIST | Std Train | 99.56 | 0.04 | 88.11 | 44.61 |
| Adv Train | 99.41 | 94.43 | 39.49 | 69.19 |  |
| CIFAR10 | Std Train | 95.74 | 0.00 | 91.79 | 61.26 |
| Adv Train | 86.28 | 45.13 | 10.88 | 67.88 |  |
| SVHN | Std Train | 96.84 | 0.16 | 73.91 | 65.38 |
| Adv Train | 91.99 | 58.55 | 35.50 | 77.04 |  |

Experiment Settings. Instead of weight-feature correlation used in synthetic data setting, here on MNIST, CIFAR10 and SVHN datasets, we apply feature learning accuracy in Definition 4.1 to measure non-robust/robust feature learning during training dynamics.

###### Definition A.1 (Feature Learning Accuracy) .

For a given feature subset $\mathcal{H}\subset\mathcal{F}$ ($\mathcal{F}$ is all feature set as the same as Definition 2.1), $\mathcal{H}$-extended feature representative distribution $\mathcal{D}_{\mathcal{H}}$ and classifier model $\bm{F}$, we define the feature learning accuracy as $\mathbb{P}_{(\bm{X}_{\bm{f}},y)\sim\mathcal{D}_{\mathcal{H}}}\left[
\operatorname{argmax}_{i\in[k]}F_{i}(\bm{X}_{\bm{f}})=y\right]$, where $\bm{X}_{\bm{f}}(\bm{f}\in\mathcal{H})$ is the $\bm{f}$-extended representative and $y$ is the label which feature $\bm{f}$ corresponds to.

###### Remark A.2 .

We define feature learning accuracy based on whether the model $\bm{F}$ can accurately classify data points when presented with only a single signal feature $\bm{f}$, which indeed generalizes the notion of weight-feature correlation $\langle\bm{w}_{i,r},\bm{f}\rangle$ to general non-linear models and non-linear features.

Similar to the method proposed in Ilyas et al. (), we reconstruct datasets $\hat{\mathcal{D}}_{\textit{NR}},\hat{\mathcal{D}}_{\textit{R}}$ as the feature representative distributions by a one-to-one mapping $\bm{X}\mapsto\hat{\bm{X}}$. Specifically, we solve the following optimization problem to derive $\hat{\bm{X}}$:

$$ $\operatorname{min}\limits_{\hat{\bm{X}}}\|\bm{G}(\hat{\bm{X}})-\bm{G}(\bm{X}) \|_{2},$ $$

where $\bm{X}\in\mathcal{D}$ is the target data point, and $\bm{G}$ is the mapping from input $\bm{X}$ to the representation layer for network learners. When $\bm{G}$ is chosen from a standard/adversarial-trained network, we derive the non-robust/robust representative dataset $\hat{\mathcal{D}}_{\textit{NR}}/\hat{\mathcal{D}}_{\textit{R}}$. Then, we run the standard training and adversarial training algorithms and record the dynamics of feature learning accuracy w.r.t. $\hat{\mathcal{D}}_{\textit{NR}}$ and $\hat{\mathcal{D}}_{\textit{R}}$. For MNIST, we choose ResNet18 (He et al., ) and $\ell_{\infty}$-perturbation with radius $0.3$, and we run algorithms for $30$ iterations. For CIFAR10 and SVHN, we choose WideResNet-34-10 (Zagoruyko and Komodakis, ) as network architecture and $\ell_{\infty}$-perturbation with radius $8/255$ and run algorithms for $200$ iterations by using a single NVIDIA RTX 4090 GPU.

Experiment Results. The results are presented in Figure 5 and Table 1. For all three datasets, we could see that, in standard training, network learners predominantly learn non-robust features rather than robust features, while adversarial training can both inhabit non-robust feature learning and strengthen robust feature learning, which empirically demonstrates our theoretical results (Theorem 4.3 and Theorem 4.4) in Section 4.

###### Definition A.1 (Feature Learning Accuracy) .

###### Remark A.2 .

### A.2 Targeted Adversarial Attack on Real-world Datasets

**Table 2: Targeted attack success rates on CIFAR10**
| Model | Attack | Cat $\rightarrow$ Dog | Dog $\rightarrow$ Cat | Car $\rightarrow$ Plane | Plane $\rightarrow$ Car |
| --- | --- | --- | --- | --- | --- |
| Std Train | NRF-PGD | $71.41\pm 1.17$ | $80.36\pm 0.28$ | $54.08\pm 0.99$ | $76.74\pm 0.77$ |
| RF-PGD | $11.30\pm 0.55$ | $9.58\pm 0.58$ | $1.24\pm 0.10$ | $2.63\pm 0.13$ |  |
| Adv Train | NRF-PGD | $9.60\pm 0.18$ | $15.16\pm 0.23$ | $0.34\pm 0.04$ | $0.40\pm 0.00$ |
| RF-PGD | $19.38\pm 0.29$ | $26.00\pm 0.67$ | $2.64\pm 0.18$ | $1.96\pm 0.13$ |  |

Experiment Settings. To verify whether adversarial examples primarily stem from non-robust features or robust features, we propose two corresponding model-free attack algorithms: non-robust-feature based PGD (NRF-PGD) and robust-feature based PGD (RF-PGD). Concretely, we use $\bm{G}_{\textit{std}}(\cdot)$ and $\bm{G}_{\textit{adv}}(\cdot)$ to denote the mapping from input $\bm{X}$ to the representation layer for standard-trained network and adversarially-trained network, respectively. Similar to the previous section and Ilyas et al. (), we can regard $\bm{G}_{\textit{std}}(\cdot)$ and $\bm{G}_{\textit{adv}}(\cdot)$ as non-robust-feature extractor and robust-feature extractor. Then, we define NRF-PGD by using PGD method to solve the following optmization problem over the perturbation $\bm{\Delta}$:

$$ $\operatorname{min}_{\|\bm{\Delta}\|_{\infty}\leq\epsilon}\|\bm{G}_{\textit{std }}(\bm{X}+\bm{\Delta})-\bm{G}_{\textit{std}}(\bm{X^{\prime}})\|_{2},$ $$

where $\bm{X}$ is the original image from the source class, $\bm{X^{\prime}}$ is a random image sampled from the target class, and $\epsilon$ is the perturbation radius. Similarly, we can define RF-PGD by using PGD method to solve the following optmization problem over the perturbation $\bm{\Delta}$:

$$ $\operatorname{min}_{\|\bm{\Delta}\|_{\infty}\leq\epsilon}\|\bm{G}_{\textit{adv }}(\bm{X}+\bm{\Delta})-\bm{G}_{\textit{adv}}(\bm{X^{\prime}})\|_{2}.$ $$

Then, we evaluate the performance of the two attack methods on the standard-trained network $\bm{F}_{\textit{std}}(\cdot)$ and the adversarially-trained network $\bm{F}_{\textit{adv}}(\cdot)$ (they are different from the reference networks from which we choose our $\bm{G}_{\textit{std}}(\cdot)$ and $\bm{G}_{\textit{adv}}(\cdot)$). For CIRAF10 dataset, we apply WideResNet-34-10 (Zagoruyko and Komodakis, ) as our learner networks, and choose the typical perturbation radius $\epsilon=8/255$ for $\ell_{\infty}$-attack. And all experiments are repeated over $5$ random seeds.

Experiment Results. We select two pairs ((cat, dog) and (car, plane)) to show the targeted attack success rate, which is presented in Table 2. It is evident that, for the standard-trained classifier, the success rates of PGD attacks using non-robust features are significantly high. Specifically, targeted attacks achieve the following success rates with NRF-PGD: Cat → Dog at 71.41%, Dog → Cat at 80.36%, Car → Plane at 54.08%, and Plane → Car at 76.74%. Conversely, when utilizing robust features for PGD, the success rates are considerably lower. For example, RF-PGD attacks yield the following success rates: Cat → Dog at 9.60%, Dog → Cat at 15.16%, Car → Plane at 0.34%, and Plane → Car at 0.40%. In the case of the adversarially-trained network, the situation alters, but in practice, after adversarial training, the success rates for both types of attacks remain low. These findings indicate that adversarial examples predominantly originate from non-robust features.

## Appendix B Preliminary for Proof Technique

### B.1 Notations

Throughout this work, we use letters for scalars and bold letters for vectors. For any given two sequences $\left\{A_{n}\right\}_{n=0}^{\infty}$ and $\left\{B_{n}\right\}_{n=0}^{\infty}$, we denote $A_{n}=O\left(B_{n}\right)$ if there exist some absolute constant $C_{1}>0$ and $N_{1}>0$ such that $\left|A_{n}\right|\leq C_{1}\left|B_{n}\right|$ for all $n\geq N_{1}$. Similarly, we denote $A_{n}=\Omega\left(B_{n}\right)$ if there exist $C_{2}>0$ and $N_{2}>0$ such that $\left|A_{n}\right|\geq C_{2}\left|B_{n}\right|$ for all $n>N_{2}$. We say $A_{n}=\Theta\left(B_{n}\right)$ if $A_{n}=O\left(B_{n}\right)$ and $A_{n}=\Omega\left(B_{n}\right)$ both holds. We use $\widetilde{O}(\cdot),\widetilde{\Omega}(\cdot)$, and $\widetilde{\Theta}(\cdot)$ to hide logarithmic factors in these notations respectively. Moreover, we denote $A_{n}=\operatorname{poly}\left(B_{n}\right)$ if $A_{n}=O\left(B_{n}^{K}\right)$ for some positive constant $K$, and $A_{n}=\operatorname{polylog}\left(B_{n}\right)$ if $B_{n}=\operatorname{poly}\left(\log\left(B_{n}\right)\right)$. We say $A_{n}=o(B_{n})$ (or $A_{n}\ll B_{n}$ or $B_{n}\gg A_{n}$) if for arbitrary positive constant $C_{3}>0$, there exists $N_{3}>0$ such that $|A_{n}|<C_{3}|B_{n}|$ for all $n>N_{3}$. And we also use $A_{n}\approx B_{n}$ to denote $A_{n}=B_{n}+o(1)$.

### B.2 Preliminary Lemmas

###### Lemma B.1 .

Let $X=\left(X_{1},\ldots,X_{n}\right)$, where $X_{i}\sim\mathcal{N}(0,1)$ are i.i.d., then we have

- •
$\mathbb{P}\left[\|X\|_{\infty}\geq\sqrt{2\log(2n)}+t\right]\leq\frac{1}{2}\exp
\left(-t^{2}/2\right)(t>0)$, and
- •
$\mathbb{P}\left[\|X\|_{\infty}\leq\sqrt{2\log(2n)-\delta}\right]\leq\exp\left
\{-\frac{e^{\delta/2}}{\sqrt{2\pi}(\sqrt{2\log(2n)}+1)}\right\}$, where we can take $\delta=K\operatorname{loglog}(n)$ for large $K$ such that this probability is small.

###### Lemma B.2 (Tensor Power Method, from Allen-Zhu and Li ( 2023b ) ) .

Let $q\geq 3$ be a constant and $x_{0},y_{0}=o(1)$. Let $\left\{x_{t},y_{t}\right\}_{t\geq 0}$ be two positive sequences updated as

- •
$x_{t+1}\geq x_{t}+\eta C_{t}x_{t}^{q-1}$ for some $C_{t}=\Theta(1)$, and
- •
$y_{t+1}\leq y_{t}+\eta SC_{t}y_{t}^{q-1}$ for some constant $S=\Theta(1)$,

where $\eta=O(1/\operatorname{poly}(d))$ for a sufficiently large polynomial in $d$. Suppose $x_{0}\geq y_{0}S^{\frac{1}{q-2}}\left(1+\Theta\left(\frac{1}{\operatorname{
polylog}(d)}\right)\right)$. For every $A=O(1)$, letting $T_{x}$ be the first iteration such that $x_{t}\geq A$, we must have that

$$ $y_{T_{x}}=O\left(y_{0}\operatorname{polylog}(d)\right)$ $$

###### Lemma B.1 .

###### Lemma B.2 (Tensor Power Method, from Allen-Zhu and Li ( 2023b ) ) .

### B.3 More Detailed Data Assumption

###### Assumption B.3 (Choice of Hyperparameters) .

We assume that:

$$ $\displaystyle d=\operatorname{poly}(k)\gg 2k,\quad P=\Theta(1),\quad\alpha:= \operatorname{inf}\alpha_{p},\beta:=\operatorname{inf}\beta_{p},$ $\displaystyle\sigma_{0}=\sigma_{n}=\frac{1}{\sqrt{d}},\quad\alpha,\beta, \epsilon=\Theta(1),\quad\alpha\gg\epsilon>\beta,$ $\displaystyle m=\operatorname{polylog}(d),\quad N=\operatorname{poly}(d),\quad q =\tau=3,\quad\varrho=\frac{1}{\operatorname{polylog}(d)},$ $\displaystyle\eta=\frac{1}{\operatorname{poly}(d)},\quad\tilde{\eta}=d^{c_{0}},$ $$

where $c_{0}\in(0,1)$ are any positive constant.

Discussion of Hyperparameter Choices. While the choices of these hyperparameters are not unique, we make specific selections above for the sake of calculations in our proofs. However, it is the relationships between them that are of primary importance. We select the dimension of the patch $d$ to be sufficiently large (i.e., we assume $d=\operatorname{poly}(k)$ for a suitably large polynomial) to ensure that all $2k$ features can be orthogonal within the space $\mathbb{R}^{d}$. The number of patches $P$ is held constant. The conditions $\alpha\gg\epsilon>\beta$ ensure the first part of Assumption 2.3 and accommodate the small perturbation radius condition previously mentioned. The width of the network learner is chosen as $m=\operatorname{polylog}(d)$ to achieve mild over-parameterization for efficient optimization. Furthermore, the adversarial learning rate $\tilde{\eta}$ is significantly larger than the weight learning rate $\eta$, aligning with practical implementations (Carlini and Wagner, ; Gowal et al., ; Sriramanan et al., ).

###### Assumption B.3 (Choice of Hyperparameters) .

## Appendix C Detailed Proofs for Section 3

In this section, we provide a detailed proof for Section 3 (including Proposition 3.1 and Proposition 3.2). And we also give a more detailed discussion about it.

### C.1 Proof of Proposition 3.1

###### Theorem C.1 (Restatement of Proposition 3.1 ) .

We consider the special case when $m=1$ and $\bm{w}_{i,1}=\gamma\bm{v}_{i}$, where $\gamma>0$ is a scale coefficient. Then, it holds that the standard empirical risk satisfies $\operatornamewithlimits{lim}_{\gamma\rightarrow\infty}\mathcal{L}_{\textit{CE}
}(\bm{F})=o(1)$, but the adversarial test error satisfies $\operatornamewithlimits{lim}_{\gamma\rightarrow\infty}\mathbb{P}_{(\bm{X},y)
\sim\mathcal{D}}\left[\exists\bm{\Delta}\in\left(\mathbb{R}^{d}\right)^{P}
\textit{ s.t. }\|\bm{\Delta}\|_{\infty}\leq\epsilon,\operatorname{argmax}_{i
\in[k]}F_{i}(\bm{X}+\bm{\Delta})\neq y\right]=1-o(1)$.

Proof Sketch. For a given data point $(\bm{X},y)\in\mathcal{Z}$ and sufficiently large $\gamma$, we calculate the margin and derive w.h.p. $F_{y}(\bm{X})\gg F_{j}(\bm{X}),\forall j\in[k]\setminus\{y\}$, which implies $\mathcal{L}_{\textit{CE}}(\bm{F})\rightarrow o(1)$. However, if we choose the perturbation $\bm{\Delta}(\bm{X},y):=(\bm{\delta}_{1},\bm{\delta}_{2},\dots,\bm{\delta}_{P})$, where $\bm{\delta}_{p}:=-\beta_{p}\bm{v}_{y}+\epsilon\bm{v}_{y^{\prime}}$ for $p\in\mathcal{J}_{\textit{NR}}$; $\bm{\delta}_{p}:=\bm{0}$ for $p\in\mathcal{J}_{\textit{R}}$, and $y^{\prime}$ is randomly chosen from $[k]\setminus\{y\}$, we know w.h.p. $F_{y^{\prime}}(\bm{X}+\bm{\Delta})\gg F_{j}(\bm{X}+\bm{\Delta}),\forall j\in[k
]\setminus\{y^{\prime}\}$, which suggests the adversarial test error is $1-o(1)$.

Now, we give the detailed proof as follows.

###### Proof.

For a given data point $(\bm{X},y)\in\mathcal{Z}$ and sufficiently large $\gamma$, we calculate the margin as follows. With probability $1-o(1)$, it holds that

$$ $\displaystyle F_{y}(\bm{X})$ $\displaystyle=\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{\operatorname{ReLU }}(\langle\gamma\bm{v}_{y},\alpha_{p}\bm{u}_{y}+\bm{\xi}_{p}\rangle)+\sum_{p \in\mathcal{J}_{\textit{NR}}}\widetilde{\operatorname{ReLU}}(\langle\gamma\bm{ v}_{y},\beta_{p}\bm{v}_{y}+\bm{\xi}_{p}\rangle)$ $\displaystyle=\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{\operatorname{ReLU }}(\gamma\langle\bm{v}_{y},\bm{\xi}_{p}\rangle)+\sum_{p\in\mathcal{J}_{\textit {NR}}}\widetilde{\operatorname{ReLU}}(\gamma(\beta_{p}+\langle\bm{v}_{y},\bm{ \xi}_{p}\rangle))$ $\displaystyle\geq\sum_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{\operatorname{ ReLU}}(\gamma(\beta_{p}-\Theta(\sigma_{n}))\geq\gamma\Theta\bigg{(}\sum_{p\in \mathcal{J}_{\textit{NR}}}\beta_{p}\bigg{)}.$ $$

And for any $j\in[P]\setminus\{y\}$, we have

$$ $\displaystyle F_{j}(\bm{X})$ $\displaystyle=\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{\operatorname{ReLU }}(\langle\gamma\bm{v}_{j},\alpha_{p}\bm{u}_{y}+\bm{\xi}_{p}\rangle)+\sum_{p \in\mathcal{J}_{\textit{NR}}}\widetilde{\operatorname{ReLU}}(\langle\gamma\bm{ v}_{j},\beta_{p}\bm{v}_{y}+\bm{\xi}_{p}\rangle)$ $\displaystyle\leq P\widetilde{\operatorname{ReLU}}(\gamma\Theta(\sigma_{n})) \leq\gamma\Theta(\sigma_{n}).$ $$

Since $\sum_{p\in\mathcal{J}_{\textit{NR}}}\beta_{p}\gg\sigma_{n}$, we know $\operatornamewithlimits{lim}_{\gamma\rightarrow\infty}\mathcal{L}_{\textit{CE}
}(\bm{F})=o(1)$.

Let $\bm{\Delta}(\bm{X},y):=(\bm{\delta}_{1},\bm{\delta}_{2},\dots,\bm{\delta}_{P})$, where $\bm{\delta}_{p}:=-\beta_{p}\bm{v}_{y}+\epsilon\bm{v}_{y^{\prime}}$ for $p\in\mathcal{J}_{\textit{NR}}$; $\bm{\delta}_{p}:=\bm{0}$ for $p\in\mathcal{J}_{\textit{R}}$, and $y^{\prime}$ is randomly chosen from $[k]\setminus\{y\}$, then we derive that, with probability $1-o(1)$, it satisfies that

$$ $\displaystyle F_{y^{\prime}}(\bm{X}+\bm{\Delta}(\bm{X},y))$ $\displaystyle=\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{\operatorname{ReLU }}(\langle\gamma\bm{v}_{y^{\prime}},\alpha_{p}\bm{u}_{y}+\bm{\xi}_{p}\rangle)+ \sum_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{\operatorname{ReLU}}(\langle \gamma\bm{v}_{y^{\prime}},\epsilon\bm{v}_{y^{\prime}}+\bm{\xi}_{p}\rangle)$ $\displaystyle\geq\sum_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{\operatorname{ ReLU}}(\gamma(\epsilon-\Theta(\sigma_{n})))\geq\gamma\Theta(\epsilon).$ $$

However, for other class $j\in[k]\setminus\{y^{\prime}\}$, we know

$$ $\displaystyle F_{j}(\bm{X}+\bm{\Delta}(\bm{X},y))$ $\displaystyle=\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{\operatorname{ReLU }}(\langle\gamma\bm{v}_{j},\alpha_{p}\bm{u}_{y}+\bm{\xi}_{p}\rangle)+\sum_{p \in\mathcal{J}_{\textit{NR}}}\widetilde{\operatorname{ReLU}}(\langle\gamma\bm{ v}_{j},\epsilon\bm{v}_{y^{\prime}}+\bm{\xi}_{p}\rangle)$ (1) $\displaystyle\leq\sum_{p\in[P]}\widetilde{\operatorname{ReLU}}(\gamma\langle \bm{v}_{j},\bm{\xi}_{p}\rangle)\leq\gamma\Theta(\sigma_{n}).$ $$

Due to $\epsilon\gg\sigma_{n}$, we know $F_{y^{\prime}}(\bm{X}+\bm{\Delta}(\bm{X},y))\gg F_{j}(\bm{X}+\bm{\Delta}(\bm{X
},y)),\forall j\in[k]\setminus\{y^{\prime}\}$.

Thus, we have

$$ $\displaystyle\operatornamewithlimits{lim}_{\gamma\rightarrow\infty}\mathbb{P}_ {(\bm{X},y)\sim\mathcal{D}}\left[\exists\bm{\Delta}\in\left(\mathbb{R}^{d} \right)^{P}\textit{ s.t. }\|\bm{\Delta}\|_{\infty}\leq\epsilon,\operatorname{ argmax}_{i\in[k]}F_{i}(\bm{X}+\bm{\Delta})\neq y\right]=1-o(1).$ $$

∎

###### Theorem C.1 (Restatement of Proposition 3.1 ) .

###### Proof.

### C.2 Proof of Proposition 3.2

###### Theorem C.2 (Restatement of Proposition 3.2 ) .

We consider the special case when $m=1$ and $\bm{w}_{i,1}=\gamma\bm{u}_{i}$, where $\gamma>0$ is a scale coefficient. Then, it holds that the standard empirical risk satisfies $\operatornamewithlimits{lim}_{\gamma\rightarrow\infty}\mathcal{L}_{\textit{CE}
}(\bm{F})=o(1)$, and the adversarial test error satisfies $\operatornamewithlimits{lim}_{\gamma\rightarrow\infty}\mathbb{P}_{(\bm{X},y)
\sim\mathcal{D}}\left[\exists\bm{\Delta}\in\left(\mathbb{R}^{d}\right)^{P}
\textit{ s.t. }\|\bm{\Delta}\|_{\infty}\leq\epsilon,\operatorname{argmax}_{i
\in[k]}F_{i}(\bm{X}+\bm{\Delta})\neq y\right]=o(1)$.

Proof Sketch. For a given data point $(\bm{X},y)\sim\mathcal{D}$, sufficiently large $\gamma$ and any perturbation $\bm{\Delta}\in\left(\mathbb{R}^{d}\right)^{P}$ satisfying $\|\bm{\Delta}\|_{\infty}\leq\epsilon$, we show that w.h.p. $F_{y}(\bm{X}+\bm{\Delta})\gtrsim\gamma\sum_{p\in\mathcal{J}_{\textit{R}}}
\alpha_{p}\gg\gamma(\Theta(\sigma_{n})+\epsilon)\gtrsim F_{j}(\bm{X}+\bm{
\Delta}),\forall j\in[k]\setminus\{y\}$, which implies that the adversarial test error is at most $o(1)$.

Now, we give the detailed proof as follows.

###### Proof.

For a given data point $(\bm{X},y)\sim\mathcal{D}$, sufficiently large $\gamma$ and any perturbation $\bm{\Delta}=(\bm{\delta}_{1},\bm{\delta}_{2},\dots,\bm{\delta}_{p})\in\left(
\mathbb{R}^{d}\right)^{P}$ satisfying $\|\bm{\Delta}\|_{\infty}\leq\epsilon$, we calculate the perturbed margin as follows. With probability $1-o(1)$, it holds that

$$ $\displaystyle F_{y}(\bm{X}+\bm{\Delta})$ $\displaystyle=\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{\operatorname{ReLU }}(\langle\gamma\bm{u}_{y},\alpha_{p}\bm{u}_{y}+\bm{\xi}_{p}+\bm{\delta}_{p} \rangle)+\sum_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{\operatorname{ReLU}}( \langle\gamma\bm{u}_{y},\beta_{p}\bm{v}_{y}+\bm{\xi}_{p}+\bm{\delta}_{p}\rangle)$ $\displaystyle=\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{\operatorname{ReLU }}(\gamma(\alpha_{p}+\langle\bm{u}_{y},\bm{\xi}_{p}\rangle+\langle\bm{u}_{y}, \bm{\delta}_{p}\rangle)+\sum_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{ \operatorname{ReLU}}(\gamma(\langle\bm{u}_{y},\bm{\xi}_{p}\rangle+\langle\bm{u }_{y},\bm{\delta}_{p}\rangle))$ $\displaystyle\geq\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{\operatorname{ ReLU}}(\gamma(\alpha_{p}-\Theta(\sigma_{n})-\epsilon))\geq\gamma\Theta\bigg{(} \sum_{p\in\mathcal{J}_{\textit{R}}}\alpha_{p}\bigg{)}.$ $$

And for any $j\in[P]\setminus\{y\}$, we have

$$ $\displaystyle F_{j}(\bm{X}+\bm{\Delta})$ $\displaystyle=\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{\operatorname{ReLU }}(\langle\gamma\bm{u}_{j},\alpha_{p}\bm{u}_{y}+\bm{\xi}_{p}+\bm{\delta}_{p} \rangle)+\sum_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{\operatorname{ReLU}}( \langle\gamma\bm{u}_{j},\beta_{p}\bm{v}_{y}+\bm{\xi}_{p}+\bm{\delta}_{p}\rangle)$ $\displaystyle\leq P\widetilde{\operatorname{ReLU}}(\gamma(\Theta(\sigma_{n})+ \epsilon))\lesssim\gamma(\Theta(\sigma_{n})+\epsilon).$ $$

Since $\sum_{p\in\mathcal{J}_{\textit{R}}}\alpha_{p}\gg\Theta(\sigma_{n})+\epsilon$, we know $\operatornamewithlimits{lim}_{\gamma\rightarrow\infty}\mathcal{L}_{\textit{CE}
}(\bm{F})=o(1)$ and

$$ $\operatornamewithlimits{lim}_{\gamma\rightarrow\infty}\mathbb{P}_{(\bm{X},y) \sim\mathcal{D}}\left[\exists\bm{\Delta}\in\left(\mathbb{R}^{d}\right)^{P} \textit{ s.t. }\|\bm{\Delta}\|_{\infty}\leq\epsilon,\operatorname{argmax}_{i \in[k]}F_{i}(\bm{X}+\bm{\Delta})\neq y\right]=o(1).$ $$

∎

###### Theorem C.2 (Restatement of Proposition 3.2 ) .

###### Proof.

### C.3 Analyzing Learning Process via Weight-Feature Correlations

Proposition 3.1 and Proposition 3.2 demonstrate that a network is vulnerable to adversarial perturbations if it relies solely on learning non-robust features. Conversely, a network that learns all robust features can achieve a state of robustness. In general, by calculating the gradient of empirical loss, it seems that the whole weights during gradient-based training will have the following form

$$ $\bm{w}_{i,r}\approx A_{i,r}\bm{u}_{i}+B_{i,r}\bm{v}_{i}+\textit{Noise},$ $$

where $A_{i,r},B_{i,r}>0$ represent the coefficients for learning robust and non-robust features, respectively, and the ’Noise’ term encompasses elements learned from other non-diagonal features $\bm{u}_{j},\bm{v}_{j}(j\neq i)$, as well as random noise $\bm{\xi}_{p}$.

Therefore, we know that the network learns the $i$-th class if and only if either $A_{i,r}$ or $B_{i,r}$ is sufficiently large. However, to robustly learn the $i$-th class, the network must primarily learn the robust feature $\bm{u}_{i}$, rather than the non-robust feature $\bm{v}_{i}$, which motivates us to analyze the feature learning process of standard training and adversarial training to understand the underlying mechanism why adversarial examples exist and how adversarial training algorithm works.

## Appendix D Detailed Proof for Section 5

In this section, we provide a detailed proof for Section 5, considering the simplified setting where the data is noiseless and we use population risk instead of empirical risk. For the general case (empirical risk with data noise), we assert that the proof idea is similar to this simplified case. This is because we can demonstrate that noise terms are always sufficiently small under our setting, as shown in the next section (Appendix E).

### D.1 Proof for Standard Training

First, we present the restatement of Theorem 4.3 under the simplified setting.

###### Theorem D.1 (Restatement of Theorem 4.3 Under the Simplified Setting, Standard Training Converges to Non-robust Global Minima) .

For sufficiently large $d$, suppose we train the model using the standard training starting with population risk from the random initialization, then after $T=\Theta(\operatorname{poly}(d)/\eta)$ iterations, with probability $1-o(1)$ over the randomness of weight initialization, the model $\bm{F}^{(T)}$ satisfies:

- •
Non-robust features are learned: $\mathbb{P}_{(\bm{X}_{\bm{f}},y)\sim\mathcal{D}_{\mathcal{F}_{\textit{NR}}}}
\left[\operatorname{argmax}_{i\in[k]}F_{i}^{(T)}(\bm{X}_{\bm{f}})\neq y\right]=0$.
- •
Standard test accuracy is good: $\mathbb{P}_{(\bm{X},y)\sim\mathcal{D}}\left[\operatorname{argmax}_{i\in[k]}F_{
i}^{(T)}(\bm{X})\neq y\right]=0$.
- •
Robust test accuracy is bad: for any given data $(\bm{X},y)$, using the following perturbation $\bm{\Delta}(\bm{X},y):=(\bm{\delta}_{1},\bm{\delta}_{2},\dots,\bm{\delta}_{P})$, where $\bm{\delta}_{p}:=-\beta_{p}\bm{v}_{y}+\epsilon\bm{v}_{y^{\prime}}$ for $p\in\mathcal{J}_{\textit{NR}}$; $\bm{\delta}_{p}:=\bm{0}$ for $p\in\mathcal{J}_{\textit{R}}$, and $y^{\prime}$ is randomly chosen from $[k]\setminus\{y\}$ (which does not depend on the model $\bm{F}^{(T)}$ and is illustrated in Figure 2), we have
$\mathbb{P}_{(\bm{X},y)\sim\mathcal{D}}\left[\operatorname{argmax}_{i\in[k]}F_{
i}^{(T)}(\bm{X}+\bm{\Delta}(\bm{X},y))\neq y\right]=1.$

Proof Sketch. To prove Theorem D.1, we study the feature learning process of standard training by decomposing the weights of the neural network into a linear combination of all features ($\bm{f}\in\mathcal{F}$). We then demonstrate that non-diagonal weight-feature correlations (i.e., $\langle\bm{w}_{i,r},\bm{u}_{j}\rangle$ and $\langle\bm{w}_{i,r},\bm{v}_{j}\rangle$, where $j\neq i$) are always smaller than their diagonal counterparts (i.e., $\langle\bm{w}_{i,r},\bm{u}_{i}\rangle$ and $\langle\bm{w}_{i,r},\bm{v}_{i}\rangle$). Next, by applying the Tensor Power Method Lemma (Allen-Zhu and Li, ), we show that non-robust feature learning will dominate throughout the entire process, which directly implies that the network converges to a non-robust solution.

Now, we give the detailed proof as follows.

###### Theorem D.1 (Restatement of Theorem 4.3 Under the Simplified Setting, Standard Training Converges to Non-robust Global Minima) .

#### D.1.1 Weight Decomposition

By analyzing the gradient descent update, we derive the following weight decomposition lemma, which represents each weight through weight-feature correlations.

###### Lemma D.2 (Weight Decomposition Under the Simplified Setting) .

For any time $t\geq 0$, each neuron $\bm{w}_{i,r}$ ($(i,r)\in[k]\times[m]$), we have

$$ $\bm{w}_{i,r}^{(t)}=\underbrace{\bm{P}_{\mathcal{F}}^{\perp}\bm{w}_{i,r}^{(0)}} _{\textit{orthogonal init}}+\underbrace{A_{i,r}^{(t)}\bm{u}_{i}+B_{i,r}^{(t)} \bm{v}_{i}}_{\textit{diagonal correlations}}+\underbrace{\sum_{y\neq i}(C_{i,r ,y}^{(t)}\bm{u}_{y}+D_{i,r,y}^{(t)}\bm{v}_{y})}_{\textit{non-diagonal correlations}},$ $$

where $A_{i,r}^{(t)},B_{i,r}^{(t)},C_{i,r,y}^{(t)}$ and $D_{i,r,y}^{(t)}$ are some time-variant coefficients, and $\bm{P}_{\mathcal{F}}^{\perp}:=\mathcal{I}_{d}-\sum_{\bm{f}\in\mathcal{F}}\bm{f
}\bm{f}^{\top}$ projects a vector into all features $\bm{f}\in\mathcal{F}$’s orthogonal complementary space.

###### Proof.

Notice that the following update iteration:

$$ $\displaystyle\bm{w}_{i,r}^{(t+1)}$ $\displaystyle=\bm{w}_{i,r}^{(t)}-\eta\mathbb{E}_{(\bm{X},y)\sim\mathcal{D}} \left[\nabla_{\bm{w}_{i,r}}\mathcal{L}_{\textit{CE}}\left(\bm{F}^{(t)};\bm{X}, y\right)\right]$ $\displaystyle=\bm{w}_{i,r}^{(t)}+\eta\mathbb{E}_{(\bm{X},y)\sim\mathcal{D}} \left[\left(1_{\{y=i\}}-\operatorname{logit}_{i}(\bm{F}^{(t)},\bm{X})\right) \sum_{p\in[P]}\widetilde{\operatorname{ReLU}}^{\prime}(\langle\bm{w}_{i,r}^{(t )},\bm{x}_{p}\rangle)\bm{x}_{p}\right].$ $$

Due to the definition of patch data $\bm{x}_{p}$, we can derive Lemma D.2 by induction.
∎

At the outset of the algorithm, we establish that the feature-weight correlations possess the following characteristic property.

###### Lemma D.3 .

For each feature $\bm{f}\in\mathcal{F}$ and each $i\in[k]$, with probability $1-o(1)$, we have $\operatorname{max}_{r\in[m]}\langle\bm{w}_{i,r}^{(0)},\bm{f}\rangle=\Theta(
\operatorname{log}(m)/\sqrt{d})$.

###### Proof.

Due to the definition of all features and random initialization $\bm{w}_{i,r}^{(0)}\sim\mathcal{N}(\bm{0},\frac{1}{d}\mathcal{I}_{d})$, we know that, for each $i\in[k],\bm{f}\in\mathcal{F}$, it holds that $\langle\bm{w}_{i,r}^{(0)},\bm{f}\rangle$ are i.i.d. Gaussian random variables with the same variance $1/d$. By applying Lemma B.1, we can derive the result above.
∎

Then, we can present the learning process by the following dynamics of weight-feature correlations.

###### Lemma D.4 (Feature Learning Iteration for Standard Training Under the Simplified Setting) .

During standard training, for any time $t\geq 0$ and pair $(i,r)\in[k]\times[m],y\in[k]\setminus\{i\}$, the two sequences $\{A_{i,r}^{(t)}\},\{B_{i,r}^{(t)}\},\{C_{i,r,y}^{(t)}\}$ and $\{D_{i,r,y}^{(t)}\}$ satisfy:

$$ $\begin{cases}A_{i,r}^{(t+1)}=A_{i,r}^{(t)}+\frac{\eta}{k}\mathbb{E}_{\mathcal{ D}_{\mathcal{J},i},\mathcal{D}_{\alpha,i}}\bigg{[}\big{(}1-\operatorname{logit }_{i}(\bm{F}^{(t)},\bm{X})\big{)}\sum\limits_{p\in\mathcal{J}_{\textit{R}}} \widetilde{\operatorname{ReLU}}^{\prime}\left(\alpha_{p}A_{i,r}^{(t)}\right) \alpha_{p}\bigg{]},\\ B_{i,r}^{(t+1)}=B_{i,r}^{(t)}+\frac{\eta}{k}\mathbb{E}_{\mathcal{D}_{\mathcal{ J},i},\mathcal{D}_{\beta,i}}\bigg{[}\big{(}1-\operatorname{logit}_{i}(\bm{F}^{ (t)},\bm{X})\big{)}\sum\limits_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{ \operatorname{ReLU}}^{\prime}\left(\beta_{p}B_{i,r}^{(t)}\right)\beta_{p}\bigg {]}\\ C_{i,r,y}^{(t+1)}=C_{i,r,y}^{(t)}+\frac{\eta}{k}\mathbb{E}_{\mathcal{D}_{ \mathcal{J},y},\mathcal{D}_{\alpha,y}}\bigg{[}-\operatorname{logit}_{i}(\bm{F} ^{(t)},\bm{X})\sum\limits_{p\in\mathcal{J}_{\textit{R}}}\widetilde{ \operatorname{ReLU}}^{\prime}\left(\alpha_{p}C_{i,r,y}^{(t)}\right)\alpha_{p} \bigg{]},\\ D_{i,r,y}^{(t+1)}=D_{i,r,y}^{(t)}+\frac{\eta}{k}\mathbb{E}_{\mathcal{D}_{ \mathcal{J},y},\mathcal{D}_{\beta,y}}\bigg{[}-\operatorname{logit}_{i}(\bm{F}^ {(t)},\bm{X})\sum\limits_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{ \operatorname{ReLU}}^{\prime}\left(\beta_{p}D_{i,r,y}^{(t)}\right)\beta_{p} \bigg{]}.\end{cases}$ $$

###### Proof.

Notice that we have the following update iteration:

$$ $\bm{w}_{i,r}^{(t+1)}=\bm{w}_{i,r}^{(t)}+\eta\mathbb{E}_{(\bm{X},y)\sim\mathcal {D}}\left[\left(1_{\{y=i\}}-\operatorname{logit}_{i}(\bm{F}^{(t)},\bm{X}) \right)\sum_{p\in[P]}\widetilde{\operatorname{ReLU}}^{\prime}(\langle\bm{w}_{i ,r}^{(t)},\bm{x}_{p}\rangle)\bm{x}_{p}\right].$ $$

Then, we project the iteration above onto the directions of features to derive

$$ $\langle\bm{w}_{i,r}^{(t+1)},\bm{f}\rangle=\langle\bm{w}_{i,r}^{(t)},\bm{f} \rangle+\eta\mathbb{E}_{(\bm{X},y)\sim\mathcal{D}}\left[\left(1_{\{y=i\}}- \operatorname{logit}_{i}(\bm{F}^{(t)},\bm{X})\right)\sum_{p\in[P]}\widetilde{ \operatorname{ReLU}}^{\prime}(\langle\bm{w}_{i,r}^{(t)},\bm{x}_{p}\rangle) \langle\bm{x}_{p},\bm{f}\rangle\right],$ $$

where feature vector$\bm{f}\in\mathcal{F}$.

For feature $\bm{f}\in\{\bm{u}_{i},\bm{v}_{i}\}$ (diagonal features), according to the definition of patch data $\bm{x}_{p}$, we know that $\langle\bm{x}_{p},\bm{f}\rangle$ is not zero if and only if data point $(\bm{X},y)$ belongs to class $i$. Thus, we derive

$$ $\begin{cases}A_{i,r}^{(t+1)}=A_{i,r}^{(t)}+\frac{\eta}{k}\mathbb{E}_{\mathcal{ D}_{\mathcal{J},i},\mathcal{D}_{\alpha,i}}\bigg{[}\big{(}1-\operatorname{logit }_{i}(\bm{F}^{(t)},\bm{X})\big{)}\sum\limits_{p\in\mathcal{J}_{\textit{R}}} \widetilde{\operatorname{ReLU}}^{\prime}\left(\alpha_{p}A_{i,r}^{(t)}\right) \alpha_{p}\bigg{]},\\ B_{i,r}^{(t+1)}=B_{i,r}^{(t)}+\frac{\eta}{k}\mathbb{E}_{\mathcal{D}_{\mathcal{ J},i},\mathcal{D}_{\beta,i}}\bigg{[}\big{(}1-\operatorname{logit}_{i}(\bm{F}^{ (t)},\bm{X})\big{)}\sum\limits_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{ \operatorname{ReLU}}^{\prime}\left(\beta_{p}B_{i,r}^{(t)}\right)\beta_{p}\bigg {]}.\end{cases}$ $$

For feature $\bm{f}\in\{\bm{u}_{j},\bm{v}_{j}\}_{j\in[k]\setminus\{i\}}$ (non-diagonal features), according to the definition of patch data $\bm{x}_{p}$, we know that $\langle\bm{x}_{p},\bm{f}\rangle$ is not zero if and only if data point $(\bm{X},y)$ belongs to class $j$. Thus, we derive

$$ $\begin{cases}C_{i,r,y}^{(t+1)}=C_{i,r,y}^{(t)}+\frac{\eta}{k}\mathbb{E}_{ \mathcal{D}_{\mathcal{J},y},\mathcal{D}_{\alpha,y}}\bigg{[}-\operatorname{ logit}_{i}(\bm{F}^{(t)},\bm{X})\sum\limits_{p\in\mathcal{J}_{\textit{R}}} \widetilde{\operatorname{ReLU}}^{\prime}\left(\alpha_{p}C_{i,r,y}^{(t)}\right) \alpha_{p}\bigg{]},\\ D_{i,r,y}^{(t+1)}=D_{i,r,y}^{(t)}+\frac{\eta}{k}\mathbb{E}_{\mathcal{D}_{ \mathcal{J},y},\mathcal{D}_{\beta,y}}\bigg{[}-\operatorname{logit}_{i}(\bm{F}^ {(t)},\bm{X})\sum\limits_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{ \operatorname{ReLU}}^{\prime}\left(\beta_{p}D_{i,r,y}^{(t)}\right)\beta_{p} \bigg{]}.\end{cases}$ $$

∎

###### Lemma D.2 (Weight Decomposition Under the Simplified Setting) .

###### Proof.

###### Lemma D.3 .

###### Proof.

###### Lemma D.4 (Feature Learning Iteration for Standard Training Under the Simplified Setting) .

###### Proof.

#### D.1.2 Logit Approximation

To analyze the feature learning iteration, we require the following approximations for both diagonal and non-diagonal logits. Indeed, we can divide the full learning process into two stages: During the early stage, the non-diagonal logits and the diagonal logits maintain a constant relationship, and then they decrease at a rate proportional to $O\left(\frac{1}{d^{c}}\right)$, where $c$ reflects the order of the diagonal function output $F_{y}^{(t)}(\bm{X})$. First, we give the following diagonal logit approximation lemma.

###### Lemma D.5 (Diagonal Logit Approximation) .

For any data point $(\bm{X},y)\sim\mathcal{D}$, suppose that $\operatorname{max}_{i\in[k],r\in[m]}B_{i,r}^{(t)}=O(\operatorname{log}(d))$ and $\operatorname{max}_{i\in[k],r\in[m],y\in[k]\setminus\{i\}}C_{i,r,y}^{(t)}=O(
\operatorname{log}(d)/\sqrt{d})$ and $\operatorname{max}_{i\in[k],r\in[m],y\in[k]\setminus\{i\}}D_{i,r,y}^{(t)}=O(
\operatorname{log}(d)/\sqrt{d})$, and $F_{y}(\bm{X})\geq c\operatorname{log}(d)$ for some $c\geq 0$, then we have the following approximation of diagonal logit:

$$ $1-\operatorname{logit}_{y}(\bm{F}^{(t)},\bm{X})=\begin{cases}\Theta(1)&, \textit{if }c=0;\\ O\left(\frac{1}{d^{c}}\right)&,\textit{if }c>0.\end{cases}$ $$

###### Proof.

By assumptions, we know that all of the off-diagonal correlations are at most $O(\operatorname{log}(d)/\sqrt{d})$. Thus, we have, for each class $j\in[k]\setminus\{y\}$,

$$ $\displaystyle F_{j}^{(t)}(\bm{X})$ $\displaystyle=\sum_{r\in[m]}\sum_{p\in[P]}\widetilde{\operatorname{ReLU}}( \langle\bm{w}_{j,r},\bm{x}_{p}\rangle)$ $\displaystyle=\sum_{r\in[m]}\sum_{p\in\mathcal{J}_{\textit{R}}}\frac{\alpha_{p }^{q}}{q\varrho^{q-1}}(C_{j,r,y}^{(t)})^{q}+\sum_{r\in[m]}\sum_{p\in\mathcal{J }_{\textit{NR}}}\frac{\beta_{p}^{q}}{q\varrho^{q-1}}(D_{j,r,y}^{(t)})^{q}$ $\displaystyle\leq m\left(\sum_{p\in\mathcal{J}_{\textit{R}}}\frac{\alpha_{p}^{ q}}{q\varrho^{q-1}}(\operatorname{max}_{r\in[m]}C_{j,r,y}^{(t)})^{q}+\sum_{p \in\mathcal{J}_{\textit{NR}}}\frac{\beta_{p}^{q}}{q\varrho^{q-1}}( \operatorname{max}_{r\in[m]}D_{j,r,y}^{(t)})^{q}\right)$ $\displaystyle\leq\tilde{O}(1/d^{\frac{q}{2}}),$ $$

which implies that

$$ $\operatorname{exp}(F_{j}^{(t)}(\bm{X}))\leq 1+\tilde{O}(1/d^{\frac{q}{2}}),$ $$

where we use the inequality $e^{x}\leq 1+x+x^{2}$ for $x\leq 1$.

Now by the assumption that $F_{y}(\bm{X})\geq c\operatorname{log}(d)$, we know

$$ $\displaystyle 1-\operatorname{logit}_{y}(\bm{F}^{(t)},\bm{X})$ $\displaystyle=1-\frac{\operatorname{exp}(F_{y}(\bm{X}))}{\operatorname{exp}(F_ {y}(\bm{X}))+\sum_{j\neq y}\operatorname{exp}(F_{j}(\bm{X}))}$ $\displaystyle\leq 1-\frac{d^{c}}{d^{c}+(k-1)+o(1)}=O(1/d^{c}).$ $$

∎

Then, we give the following non-diagonal logit approximation lemma.

###### Lemma D.6 (Non-diagonal Logit Approximation) .

For any data point $(\bm{X},y)\sim\mathcal{D}$, suppose that $\operatorname{max}_{i\in[k],r\in[m]}B_{i,r}^{(t)}=O(\operatorname{log}(d))$ and $\operatorname{max}_{i\in[k],r\in[m],y\in[k]\setminus\{i\}}C_{i,r,y}^{(t)}=O(
\operatorname{log}(d)/\sqrt{d})$ and $\operatorname{max}_{i\in[k],r\in[m],y\in[k]\setminus\{i\}}D_{i,r,y}^{(t)}=O(
\operatorname{log}(d)/\sqrt{d})$, and $F_{y}(\bm{X})\geq c\operatorname{log}(d)$ for some $c\geq 0$, then we have the following approximation of non-diagonal logit, for $i\neq y$:

$$ $\operatorname{logit}_{i}(\bm{F}^{(t)},\bm{X})=\begin{cases}\Theta(1/k)&, \textit{if }c=0;\\ O\left(\frac{1}{d^{c}}\right)&,\textit{if }c>0.\end{cases}$ $$

###### Proof.

Similar to the diagonal case, we have, for each class $j\in[k]\setminus\{y\}$,

$$ $F_{j}^{(t)}(\bm{X})\leq\tilde{O}(1/d^{\frac{q}{2}}).$ $$

Then, we know

$$ $\displaystyle\operatorname{logit}_{i}(\bm{F}^{(t)},\bm{X})$ $\displaystyle=\frac{\operatorname{exp}(F_{i}(\bm{X}))}{\operatorname{exp}(F_{y }(\bm{X}))+\operatorname{exp}(F_{i}(\bm{X}))+\sum_{j\neq y,i}\operatorname{exp }(F_{j}(\bm{X}))}$ $\displaystyle\leq\frac{1+\tilde{O}(1/d^{\frac{q}{2}})}{d^{c}+(k-1)}=O(1/d^{c}).$ $$

∎

###### Lemma D.5 (Diagonal Logit Approximation) .

###### Proof.

###### Lemma D.6 (Non-diagonal Logit Approximation) .

###### Proof.

#### D.1.3 Non-diagonal Terms are Small

Then, we will show that non-diagonal terms are always small during the full learning process.

###### Lemma D.7 .

For every time $t$, non-diagonal wieght-feature correlations $C_{i,r,y}^{(t)},D_{i,r,y}^{(t)}$ ($(i,r)\in[k]\times[m],y\neq i$) satisfy that $\operatorname{max}_{r\in[m]}C_{i,r,y}^{(t)}=O(\operatorname{max}_{r\in[m]}C_{i
,r,y}^{(0)})$ and $\operatorname{max}_{r\in[m]}D_{i,r,y}^{(t)}=O(\operatorname{max}_{r\in[m]}D_{i
,r,y}^{(0)})$ for each $i\in[k],y\in[k]\setminus\{i\}$.

###### Proof.

Notice that, for each pair $i\in[k],r\in[m],y\in[k]\setminus\{i\}$, we have

$$ $\begin{cases}C_{i,r,y}^{(t+1)}=C_{i,r,y}^{(t)}+\frac{\eta}{k}\mathbb{E}_{ \mathcal{D}_{\mathcal{J},y},\mathcal{D}_{\alpha,y}}\bigg{[}-\operatorname{ logit}_{i}(\bm{F}^{(t)},\bm{X})\sum\limits_{p\in\mathcal{J}_{\textit{R}}} \widetilde{\operatorname{ReLU}}^{\prime}\left(\alpha_{p}C_{i,r,y}^{(t)}\right) \alpha_{p}\bigg{]},\\ D_{i,r,y}^{(t+1)}=D_{i,r,y}^{(t)}+\frac{\eta}{k}\mathbb{E}_{\mathcal{D}_{ \mathcal{J},y},\mathcal{D}_{\beta,y}}\bigg{[}-\operatorname{logit}_{i}(\bm{F}^ {(t)},\bm{X})\sum\limits_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{ \operatorname{ReLU}}^{\prime}\left(\beta_{p}D_{i,r,y}^{(t)}\right)\alpha_{p} \bigg{]}.\end{cases}$ $$

Since $-\operatorname{logit}_{i}(\bm{F}^{(t)},\bm{X})$ is negative and $\widetilde{\operatorname{ReLU}}^{\prime}(z)=0$ for $z\geq 0$, we can prove the above lemma by induction.
∎

###### Lemma D.7 .

###### Proof.

#### D.1.4 Analysis of Feature Learning Process for Standard Training

Now, we present an enhanced analysis of the feature learning process for standard training scenarios. In fact, the learning process can be conceptualized as comprising two distinct phases: Initially, all weight-feature correlations are closely aligned with their initial values, implying that the activation of all neurons occurs within the polynomial regime of the smoothed $\widetilde{\operatorname{ReLU}}$ function. Subsequently, once the diagonal outputs $F_{y}(\bm{X})$ have scaled to an order of $\operatorname{log}(d)$, we demonstrate that the increase in all weight-feature correlations is arrested due to the diminishing impact of small logits.

Stage I: Almost neurons lie within the polynomial part of activation $\widetilde{ReLU}$.

###### Lemma D.8 .

During standard training, there exists some time threshold $T_{0}>0$ such that, for any early time $0\leq t\leq T_{0}$ and pair $(i,r)\in[k]\times[m]$, the two sequences $\{A_{i,r}^{(t)}\}$ and $\{B_{i,r}^{(t)}\}$ satisfy:

$$ $\begin{cases}A_{i,r}^{(t+1)}=A_{i,r}^{(t)}+\Theta(\eta)\left(A_{i,r}^{(t)} \right)^{q-1}\mathbb{E}\bigg{[}\sum\limits_{p\in\mathcal{J}_{\textit{R}}} \alpha_{p}^{q}\bigg{]},\\ B_{i,r}^{(t+1)}=B_{i,r}^{(t)}+\Theta(\eta)\left(B_{i,r}^{(t)}\right)^{q-1} \mathbb{E}\bigg{[}\sum\limits_{p\in\mathcal{J}_{\textit{NR}}}\beta_{p}^{q} \bigg{]}.\end{cases}$ $$

###### Proof.

According to Lemma D.4, we know that, for early time $t$, it holds that

$$ $\begin{cases}A_{i,r}^{(t+1)}=A_{i,r}^{(t)}+\frac{\eta}{k}\mathbb{E}_{\mathcal{ D}_{\mathcal{J},i},\mathcal{D}_{\alpha,i}}\bigg{[}\big{(}1-\operatorname{logit }_{i}(\bm{F}^{(t)},\bm{X})\big{)}\sum\limits_{p\in\mathcal{J}_{\textit{R}}} \widetilde{\operatorname{ReLU}}^{\prime}\left(\alpha_{p}A_{i,r}^{(t)}\right) \alpha_{p}\bigg{]},\\ B_{i,r}^{(t+1)}=B_{i,r}^{(t)}+\frac{\eta}{k}\mathbb{E}_{\mathcal{D}_{\mathcal{ J},i},\mathcal{D}_{\beta,i}}\bigg{[}\big{(}1-\operatorname{logit}_{i}(\bm{F}^{ (t)},\bm{X})\big{)}\sum\limits_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{ \operatorname{ReLU}}^{\prime}\left(\beta_{p}B_{i,r}^{(t)}\right)\beta_{p}\bigg {]}.\end{cases}$ $$

And it also holds that

$$ $\alpha_{p}A_{i,r}^{(t)},\beta_{p}B_{i,r}^{(t)}\leq\varrho,$ $$

which implies that the activation is within polynomial part now.

Combined with Lemma D.5, we derive the lemma above.
∎

Now, by applying Tensor Power Method Lemma B.2, we can derive the following result.

###### Lemma D.9 (Non-robust Feature Learning Dominates at Early Stage) .

For each $y\in[k]$, let time $T_{y}$ denote the first time when $\operatorname{max}_{r\in[m]}B_{y,r}^{(t)}$ reaches $\varrho/\beta$, then we have $\operatorname{max}_{r\in[m]}A_{y,r}^{(T_{y})}=O(\operatorname{polylog}(d)/
\sqrt{d})$.

###### Proof.

We consider the following sequences $\{x_{t}\}$, $\{y_{t}\}$ and $\{C_{t}\}$:

$$ $x_{t}=\operatorname{max}_{r\in[m]}B_{i,r}^{(t)},\quad y_{t}=\operatorname{max} _{r\in[m]}A_{i,r}^{(t)},\quad C_{t}=\mathbb{E}\bigg{[}\sum\limits_{p\in \mathcal{J}_{\textit{NR}}}\beta_{p}^{q}\bigg{]},\quad S=\frac{\mathbb{E}\bigg{ [}\sum\limits_{p\in\mathcal{J}_{\textit{R}}}\alpha_{p}^{q}\bigg{]}}{\mathbb{E} \bigg{[}\sum\limits_{p\in\mathcal{J}_{\textit{NR}}}\beta_{p}^{q}\bigg{]}}.$ $$

Then, we have

$$ $\begin{cases}x_{t+1}\geq x_{t}+\Theta(\eta)C_{t}x_{t}^{q-1},\\ y_{t+1}\leq y_{t}+\Theta(\eta)SC_{t}y_{t}^{q-1}.\end{cases}$ $$

And we also know that, with high probability $1-o(1)$, we have

$$ $\frac{x_{0}}{y_{0}S^{\frac{1}{q-2}}}=\frac{\operatorname{max}_{r\in[m]}B_{i,r} ^{(0)}}{\operatorname{max}_{r\in[m]}A_{i,r}^{(0)}}\cdot\left(\frac{\mathbb{E} \bigg{[}\sum\limits_{p\in\mathcal{J}_{\textit{NR}}}\beta_{p}^{q}\bigg{]}}{ \mathbb{E}\bigg{[}\sum\limits_{p\in\mathcal{J}_{\textit{R}}}\alpha_{p}^{q} \bigg{]}}\right)^{\frac{1}{q-2}}\gg 1+\frac{1}{\operatorname{polylog}(d)}.$ $$

Where we use Lemma D.3 and Assumption 2.3.

Finally, by directly applying Tensor Power Method Lemma B.2, we derive the conclusion.
∎

Stage II: Non-robust feature learning arrives at linear region of activation $\widetilde{ReLU}$.

###### Lemma D.10 .

For each $y\in[k]$ and $(\bm{X},y)\sim\mathcal{D}$, let time $T_{y}^{{}^{\prime}}$ denote the first time such that $F_{y}(\bm{X})^{(t)}\geq\operatorname{log}(d)$, then $T_{y}^{{}^{\prime}}=\operatorname{poly}(d)\geq T_{y}$, and we have $\operatorname{max}_{r\in[m]}A_{y,r}^{(T_{y}^{{}^{\prime}})}=O(\operatorname{
polylog}(d)/\sqrt{d})$.

###### Proof.

Now, according to Lemma D.9, we know that $\operatorname{max}_{r\in[m]}B_{y,r}^{(t)}\geq\varrho/\beta$, which manifests that there exists at least one neuron $r^{*}\in[m]$ has been within the linear regime of activation function. Thus, so long as $F_{y}(\bm{X})^{(t)}<\operatorname{log}(d)$ now, we have

$$ $\displaystyle B_{y,r^{*}}^{(t+1)}$ $\displaystyle=B_{y,r^{*}}^{(t)}+\frac{\eta}{k}\mathbb{E}\left[(1-\operatorname {logit}_{y}(\bm{F}^{(t)},\bm{X})\sum_{p\in\mathcal{J}_{\textit{NR}}}\widetilde {\operatorname{ReLU}}^{\prime}(\beta_{p}B_{y,r^{*}}^{(t)})\beta_{p}\right]$ $\displaystyle\geq B_{y,r^{*}}^{(t)}+\Theta\left(\frac{\eta}{k}\right)\mathbb{E }\left[\sum_{p\in\mathcal{J}_{\textit{NR}}}\beta_{p}\right].$ $$

Therefore, we know that we can upper bound $T_{y}$ by the number of iterations it takes $B_{y,r^{*}}^{(t)}$ to grow to $\Theta(\operatorname{log}(d))$. Indeed, we clearly have that $T_{y}=O(\operatorname{log}(d)/\eta)=\operatorname{poly}(d)$ for some polynomial in $d$. However, in contrast with $B_{y,r^{*}}^{(t)}$, for $\operatorname{r\in[m]}A_{y,r}^{(t)}$, we can lower bound the number of iterations $T$ it takes for $A_{y,r}^{(t)}$ to grow to by a fixed constant $C$ factor from initialization:

$$ $T\Theta\left(\frac{\eta C^{q-1}\left(A_{y,r}^{(0)}\right)^{q-1}}{\varrho^{q-1} }\right)\geq(C-1)A_{y,r}^{(0)},$ $$

which implies that

$$ $T\geq\Theta\left(\frac{\varrho^{q-1}}{\eta A_{y,r}^{(0)}}\right)\geq\Theta \left(\frac{\varrho^{q-1}d^{\frac{q-2}{2}}}{\eta}\right)\gg\omega\left(\frac{ \operatorname{log}(d)}{\eta}\right)=\omega(T_{y^{{}^{\prime}}}).$ $$

∎

The final remaining task is to show $F_{y}^{(t)}(\bm{X})$ will keep $\Theta(\operatorname{poly}(d))$ for all polynomial time $t$.

###### Lemma D.11 .

For all time $t=O(\operatorname{poly}(d))\geq T_{y}^{{}^{\prime}}$ and each $(\bm{X},y)\sim\mathcal{D}$, we have $F_{y}^{(t)}(\bm{X})=O(\operatorname{log}(d))$, and $\operatorname{max}_{r\in[m]}A_{y,r}^{(t)}=O(\operatorname{polylog}(d)/\sqrt{d})$.

###### Proof.

Firstly, we can form the following upper bound for the gradient updates

$$ $\displaystyle B_{y,r^{*}}^{(t+1)}$ $\displaystyle=B_{y,r^{*}}^{(t)}+\frac{\eta}{k}\mathbb{E}\left[(1-\operatorname {logit}_{y}(\bm{F}^{(t)},\bm{X})\sum_{p\in\mathcal{J}_{\textit{NR}}}\widetilde {\operatorname{ReLU}}^{\prime}(\beta_{p}B_{y,r^{*}}^{(t)})\beta_{p}\right]$ $\displaystyle\geq B_{y,r^{*}}^{(t)}+\Theta\left(\frac{\eta}{k}\right)\left(1- \operatorname{logit}_{y}(\bm{F}^{(t)},\bm{X})\right).$ $$

Then, we know that it follows that it takes at least $\Theta(d\operatorname{log}(d)/\eta)$ iterations (since the correlations must grow at least $\operatorname{log}(d)$) from $T_{y}^{{}^{\prime}}$ for $F_{y}(\bm{X})$ to reach $2\operatorname{log}(d)$. Now let $T_{y}^{(}c)$ denote the number of iterations it takes for $F_{y}(\bm{X})$ to cross $c\operatorname{log}(d)$ after crossing $(c-1)\operatorname{log}(d)$ for the first time. For $c\geq 2$, we necessarily have that $T_{y}^{(}c)=\Omega(dT_{y}^{(c-1)})$ by induction.

Let us now further define $T_{f}$ to be the first iteration at which $F_{y}^{(T_{f})}(\bm{X})\geq f(d)\log d$ for some $f(d)=\omega(1)$. However, we have from the above discussion that:

$$ $\displaystyle T_{f}$ $\displaystyle\geq\Omega(\operatorname{poly}(d))+\sum_{c=0}^{f(d)-2}\Omega\left (\frac{d^{c}\log d}{\eta}\right)$ $\displaystyle\geq\Omega\left(\frac{\log d\left(d^{f(d)-1}-1\right)}{\eta(d-1)}\right)$ $\displaystyle\geq\omega(\operatorname{poly}(d))$ $$

So $F_{y}^{(t)}(\bm{X})=O(\operatorname{log}(d))$ for all $t=O(\operatorname{poly}(d))$. An identical analysis also works for the robust feature correlations $A_{y,r}^{(t)}$, so we are done.
∎

###### Lemma D.8 .

###### Proof.

###### Lemma D.9 (Non-robust Feature Learning Dominates at Early Stage) .

###### Proof.

###### Lemma D.10 .

###### Proof.

###### Lemma D.11 .

###### Proof.

#### D.1.5 Proof of Theorem D.1

Now, we will prove Theorem D.1, which includes the following three parts.

###### Lemma D.12 (Standard Accuracy is Good) .

For $T=\Theta(\operatorname{poly}(d))$ and each data point $(\bm{X},y)\sim\mathcal{D}$, with probability $1-o(1)$, we have $F_{y}^{(T)}(\bm{X})>F_{i}^{(T)}(\bm{X}),\forall i\in[k]\setminus\{y\}$.

###### Proof.

According to Lemma D.11, we know that, for each data point $(\bm{X},y)\sim\mathcal{D}$ and time $T=\Theta(\operatorname{poly}(d)/\eta)$, with probability $1-o(1)$, it holds that

$$ $F_{y}(\bm{X})=\Theta(\operatorname{log}(d)).$ $$

However, the non-diagonal outputs can be upper bounded as:

$$ $\displaystyle F_{i}(\bm{X})$ $\displaystyle=\sum_{r\in[m]}\sum_{p\in[P]}\widetilde{\operatorname{ReLU}}( \langle\bm{w}_{i,r},\bm{x}_{p}\rangle)$ $\displaystyle=\sum_{r\in[m]}\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{ \operatorname{ReLU}}(\alpha_{p}C_{i,r,y}^{(t)})+\sum_{r\in[m]}\sum_{p\in \mathcal{J}_{\textit{NR}}}\widetilde{\operatorname{ReLU}}(\alpha_{p}D_{i,r,y}^ {(t)})$ $\displaystyle\leq m\left(\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{ \operatorname{ReLU}}(\alpha_{p}\operatorname{max}_{r\in[m]}C_{i,r,y}^{(t)})+ \sum_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{\operatorname{ReLU}}(\beta_{p} \operatorname{max}_{r\in[m]}D_{i,r,y}^{(t)})\right)$ $\displaystyle\leq\tilde{O}(1/d^{q/2}).$ $$

Where we use Lemma D.7 to upper bound the non-diagonal weight-feature correlations (they always lie within the polynomial part of activation function).

Thus, we derive that $F_{y}(\bm{X})>F_{i}(\bm{X})$ for each $i\in[k]\setminus\{y\}$.
∎

###### Lemma D.13 (Non-robust Features are Learned Well) .

For $T=\Theta(\operatorname{poly}(d))$ and each data point $(\bm{X},y)\sim\mathcal{D}_{\mathcal{F}_{\textit{NR}}}$, with probability $1-o(1)$, we have $F_{y}^{(T)}(\bm{X})>F_{i}^{(T)}(\bm{X}),\forall i\in[k]\setminus\{y\}$.

###### Proof.

Since we have that $\operatorname{max}_{r\in[m]}B_{y,r}^{(T)}=\Theta(\operatorname{log}(d))$ for each class $y\in[k]$, it suggests $F_{y}^{(T)}(\bm{X})=\Theta(\operatorname{log}(d))$. For non-diagonal outputs, we have results similar to Lemma D.12, i.e. $F_{i}^{(T)}(\bm{X})=\tilde{O}(1/d^{q/2})$, which immediately derives the lemma above.
∎

###### Lemma D.14 (Standard Training Converges to Non-robust Solution) .

For $T=\Theta(\operatorname{poly}(d))$ and each data point $(\bm{X},y)\sim\mathcal{D}$, let perturbation $\bm{\Delta}(\bm{X},y):=(\bm{\delta}_{1},\bm{\delta}_{2},\dots,\bm{\delta}_{P})$, where $\bm{\delta}_{p}:=-\beta_{p}\bm{v}_{y}+\epsilon\bm{v}_{y^{\prime}}$ for $p\in\mathcal{J}_{\textit{NR}}$; $\bm{\delta}_{p}:=\bm{0}$ for $p\in\mathcal{J}_{\textit{R}}$, and $y^{\prime}$ is randomly chosen from $[k]\setminus\{y\}$, then, with probability $1-o(1)$, we have $F_{y^{\prime}}^{(T)}(\bm{X}+\bm{\Delta}(\bm{X},y))>F_{i}^{(T)}(\bm{X}+\bm{
\Delta}(\bm{X},y)),\forall i\in[k]\setminus\{y^{\prime}\}$.

###### Proof.

By the definition of perturbation $\bm{\Delta}(\bm{X},y)$ that replaces all non-robust feature patches $\beta_{p}\bm{v}_{y}$ by non-robust feature $\bm{v}_{y^{\prime}}$ from another class $y^{\prime}$, we have

$$ $\displaystyle F_{y^{\prime}}^{(T)}(\bm{X}+\bm{\Delta}(\bm{X},y))$ $\displaystyle=\sum_{r\in[m]}\sum_{p\in[P]}\widetilde{\operatorname{ReLU}}(\bm{ w}_{y^{\prime},r},\bm{x}_{p}+\bm{\delta}_{p})$ $\displaystyle\geq\sum_{p\in[P]}\widetilde{\operatorname{ReLU}}(\epsilon \operatorname{max}_{r\in[m]}B_{y^{\prime},r}^{(T)}+O(\operatorname{polylog}(d) /\sqrt{d}))$ $\displaystyle\geq\Theta(\operatorname{log}(d))\gg\tilde{\Omega}(1/d^{q/2})\geq \operatorname{max}_{i\in[k]\setminus\{y^{\prime}\}}F_{i}^{(T)}(\bm{X}+\bm{ \Delta}(\bm{X},y)),$ $$

which shows this theorem.
∎

###### Lemma D.12 (Standard Accuracy is Good) .

###### Proof.

###### Lemma D.13 (Non-robust Features are Learned Well) .

###### Proof.

###### Lemma D.14 (Standard Training Converges to Non-robust Solution) .

###### Proof.

### D.2 Proof for Adversarial Training

First, we present the restatement of Theorem 4.4 under the simplified setting.

###### Theorem D.15 (Restatement of Theorem 4.4 Under the Simplified Setting, Adversarial Training Converges to Robust Global Minima) .

For sufficiently large $d$, suppose we train the model using the adversarial training algorithm starting with adversarial population risk from the random initialization, then after $T=\Theta(\operatorname{poly}(d)/\eta)$ iterations, the model $\bm{F}^{(T)}$ satisfies:

- •
Robust features are learned: $\mathbb{P}_{(\bm{X}_{\bm{f}},y)\sim\mathcal{D}_{\mathcal{F}_{\textit{R}}}}
\left[\operatorname{argmax}_{i\in[k]}F_{i}^{(T)}(\bm{X}_{\bm{f}})\neq y\right]
=o(1)$.
- •
Robust test accuracy is good:
$\mathbb{P}_{(\bm{X},y)\sim\mathcal{D}}\left[\exists\bm{\Delta}\in\left(\mathbb
{R}^{d}\right)^{P}\textit{ s.t. }\|\bm{\Delta}\|_{\infty}\leq\epsilon,
\operatorname{argmax}_{i\in[k]}F_{i}^{(T)}(\bm{X}+\bm{\Delta})\neq y\right]=o(
1).$

Proof Sketch. The proof of this theorem can also be divided into two stages (according to the activation regions of weight-feature correlations). Unlike standard training, the first phase of adversarial training involves a phase transition. In the initial phase, robust feature learning and non-robust feature learning exhibit behaviors similar to those in standard training. However, once non-robust feature learning reaches a certain magnitude, adversarial training suppresses non-robust feature learning through adversarial examples found by a gradient ascent algorithm, while robust feature learning continues to grow.

Now, we give the detailed proof as follows.

###### Theorem D.15 (Restatement of Theorem 4.4 Under the Simplified Setting, Adversarial Training Converges to Robust Global Minima) .

#### D.2.1 Weight Decomposition

Since our algorithm is based on gradient information (which runs one-step gradient ascent algorithm for finding adversarial examples and runs gradient descent algorithm for training the neural network model), we can derive a weight decomposition theorem similar to that of standard training.

###### Lemma D.16 (Weight Decomposition for Adversarial Training) .

For any time $t\geq 0$, each neuron $\bm{w}_{i,r}$ ($(i,r)\in[k]\times[m]$), we have

$$ $\bm{w}_{i,r}^{(t)}=\underbrace{\sum_{y\in[k]}\sum_{s\in[m]}E_{i,r,y,s}^{(t)} \bm{P}_{\mathcal{F}}^{\perp}\bm{w}_{y,s}^{(0)}}_{\textit{orthogonal to all features}}+\underbrace{A_{i,r}^{(t)}\bm{u}_{i}+B_{i,r}^{(t)}\bm{v}_{i}}_{ \textit{diagonal correlations}}+\underbrace{\sum_{j\neq i}(C_{i,r,j}^{(t)}\bm{ u}_{j}+D_{i,r,j}^{(t)}\bm{v}_{j})}_{\textit{non-diagonal correlations}},$ $$

where $A_{i,r}^{(t)},B_{i,r}^{(t)},C_{i,r,j}^{(t)},D_{i,r,j}^{(t)}$ and $E_{i,r,y,s}^{(t)}$ are some time-variant coefficients, and $\bm{P}_{\mathcal{F}}^{\perp}:=\mathcal{I}_{d}-\sum_{\bm{f}\in\mathcal{F}}\bm{f
}\bm{f}^{\top}$ projects a vector into all features $\bm{f}\in\mathcal{F}$’s orthogonal complementary space.

###### Proof.

Notice that the following update iteration:

$$ $\displaystyle\bm{w}_{i,r}^{(t+1)}$ $\displaystyle=\bm{w}_{i,r}^{(t)}-\eta\mathbb{E}_{(\bm{X},y)\sim\mathcal{D}} \left[\nabla_{\bm{w}_{i,r}}\mathcal{L}_{\textit{CE}}\left(\bm{F}^{(t)}; \widetilde{\bm{X}}^{(t)},y\right)\right]$ $\displaystyle=\bm{w}_{i,r}^{(t)}+\eta\mathbb{E}_{(\bm{X},y)\sim\mathcal{D}} \left[\left(1_{\{y=i\}}-\operatorname{logit}_{i}(\bm{F}^{(t)},\widetilde{\bm{X }}^{(t)})\right)\sum_{p\in[P]}\widetilde{\operatorname{ReLU}}^{\prime}(\langle \bm{w}_{i,r}^{(t)},\tilde{\bm{x}}^{(t)}_{p}\rangle)\tilde{\bm{x}}^{(t)}_{p} \right].$ $$

To prove Lemma D.2, we only need the following result that time-variant adversarial examples also align with the span of all features (Lemma D.17).
∎

###### Lemma D.16 (Weight Decomposition for Adversarial Training) .

###### Proof.

#### D.2.2 Time-variant Adversarial Examples

By analyzing the gradient ascent algorithm, we can derive the following decomposition theorem regarding adversarial examples.

###### Lemma D.17 .

For any time $t$ and data point $(\bm{X},y)\sim\mathcal{D}$, we have the following decomposition about the time-variant corresponding adversarial example $(\widetilde{\bm{X}}^{(t)},y)$, where we use $(\tilde{\bm{x}}_{1},\tilde{\bm{x}}_{2},\dots,\tilde{\bm{x}}_{p})$ to denote $\widetilde{\bm{X}}^{(t)}$. Then, it satisfies:

$$ $\tilde{x}_{p}^{(t)}=\tilde{\alpha}_{p}^{(t)}\bm{u}_{y}+\tilde{\beta}_{p}^{(t)} \bm{v}_{y}+\sum_{j\neq y}(\tilde{\lambda}_{p,j}^{(t)}\bm{u}_{j}+\tilde{\mu}_{p ,j}^{(t)}\bm{v}_{j})+\sum_{i\in[k]}\sum_{r\in[m]}\tilde{\gamma}_{p,i,r}^{(t)} \bm{P}_{\mathcal{F}}^{\perp}\bm{w}_{i,r}^{(0)},$ $$

where $\bm{P}_{\mathcal{F}}^{\perp}:=\mathcal{I}_{d}-\sum_{\bm{f}\in\mathcal{F}}\bm{f
}\bm{f}^{\top}$ projects a vector into all features $\bm{f}\in\mathcal{F}$’s orthogonal complementary space, and coefficients $\tilde{\alpha}_{p}^{(t)}$, $\tilde{\beta}_{p}^{(t)}$, $\tilde{\lambda}_{p,j}^{(t)}$, $\tilde{\mu}_{p,j}^{(t)}$ and $\tilde{\gamma}_{p,i,r}^{(t)}$ are updated by the following iterations

- •
For $p\in\mathcal{J}_{\textit{R}}$, we have
$\begin{cases}\tilde{\alpha}_{p}^{(t)}=(1-\operatorname{min}\{\frac{\epsilon}{
\alpha_{p}},\frac{\tilde{\eta}}{\alpha_{p}}\sum_{s\in[m]}\widetilde{
\operatorname{ReLU}}^{\prime}(\alpha_{p}A_{y,s}^{(t)})A_{y,s}^{(t)}\})\alpha_{
p}\\
\tilde{\beta}_{p}^{(t)}=-\operatorname{min}\{{\epsilon},{\tilde{\eta}}\sum_{s
\in[m]}\widetilde{\operatorname{ReLU}}^{\prime}(\alpha_{p}A_{y,s}^{(t)})B_{y,s
}^{(t)}\}\\
\tilde{\lambda}_{p,j}^{(t)}=-\operatorname{min}\{{\epsilon},{\tilde{\eta}}\sum
_{s\in[m]}\widetilde{\operatorname{ReLU}}^{\prime}(\alpha_{p}A_{y,s}^{(t)})C_{
y,s,j}^{(t)}\}\\
\tilde{\mu}_{p,j}^{(t)}=-\operatorname{min}\{{\epsilon},{\tilde{\eta}}\sum_{s
\in[m]}\widetilde{\operatorname{ReLU}}^{\prime}(\alpha_{p}A_{y,s}^{(t)})D_{y,s
,j}^{(t)}\}\\
\tilde{\gamma}_{p,i,r}^{(t)}=-\operatorname{min}\{{\epsilon},{\tilde{\eta}}
\sum_{s\in[m]}\widetilde{\operatorname{ReLU}}^{\prime}(\alpha_{p}A_{y,s}^{(t)}
)E_{y,s,i,r}^{(t)}\}\end{cases}$
- •
For $p\in\mathcal{J}_{\textit{NR}}$, we have
$\begin{cases}\tilde{\alpha}_{p}^{(t)}=-\operatorname{min}\{{\epsilon},{\tilde{
\eta}}\sum_{s\in[m]}\widetilde{\operatorname{ReLU}}^{\prime}(\beta_{p}B_{y,s}^
{(t)})A_{y,s}^{(t)}\}\\
\tilde{\beta}_{p}^{(t)}=(1-\operatorname{min}\{\frac{\epsilon}{\beta_{p}},
\frac{\tilde{\eta}}{\beta_{p}}\sum_{s\in[m]}\widetilde{\operatorname{ReLU}}^{
\prime}(\beta_{p}B_{y,s}^{(t)})B_{y,s}^{(t)}\})\beta_{p}\\
\tilde{\lambda}_{p,j}^{(t)}=-\operatorname{min}\{{\epsilon},{\tilde{\eta}}\sum
_{s\in[m]}\widetilde{\operatorname{ReLU}}^{\prime}(\beta_{p}B_{y,s}^{(t)})C_{y
,s,j}^{(t)}\}\\
\tilde{\mu}_{p,j}^{(t)}=-\operatorname{min}\{{\epsilon},{\tilde{\eta}}\sum_{s
\in[m]}\widetilde{\operatorname{ReLU}}^{\prime}(\beta_{p}B_{y,s}^{(t)})D_{y,s,
j}^{(t)}\}\\
\tilde{\gamma}_{p,i,r}^{(t)}=-\operatorname{min}\{{\epsilon},{\tilde{\eta}}
\sum_{s\in[m]}\widetilde{\operatorname{ReLU}}^{\prime}(\beta_{p}B_{y,s}^{(t)})
E_{y,s,i,r}^{(t)}\}\end{cases}$

###### Proof.

By substituting the weight decomposition expression into the formula of the gradient ascent algorithm and simplifying, we obtain this lemma.
∎

Now, we can derive the following feature learning iteration for adversarial training.

###### Lemma D.18 (Feature Learning Iteration for Adversarial Training) .

During adversarial training, for any time $t\geq 0$ and pair $(i,r)\in[k]\times[m],j\in[k]\setminus\{i\}$, the two sequences $\{A_{i,r}^{(t)}\},\{B_{i,r}^{(t)}\},\{C_{i,r,j}^{(t)}\}$, $\{D_{i,r,j}^{(t)}\}$ and $E_{i,r,y,s}^{(t)}$ satisfy:

$$ $\begin{cases}A_{i,r}^{(t+1)}=A_{i,r}^{(t)}+{\eta}\mathbb{E}\bigg{[}\big{(}1_{ \{y=i\}}-\operatorname{logit}_{i}(\bm{F}^{(t)},\widetilde{\bm{X}}^{(t)})\big{) }\sum\limits_{p\in[P]}\widetilde{\operatorname{ReLU}}^{\prime}\left(\langle\bm {w}_{i,r}^{(t)},\tilde{\bm{x}}_{p}^{(t)}\rangle\right)\tilde{\alpha}_{p}^{(t)} \bigg{]},\\ B_{i,r}^{(t+1)}=B_{i,r}^{(t)}+{\eta}\mathbb{E}\bigg{[}\big{(}1_{\{y=i\}}- \operatorname{logit}_{i}(\bm{F}^{(t)},\widetilde{\bm{X}}^{(t)})\big{)}\sum \limits_{p\in[P]}\widetilde{\operatorname{ReLU}}^{\prime}\left(\langle\bm{w}_{ i,r}^{(t)},\tilde{\bm{x}}_{p}^{(t)}\rangle\right)\tilde{\beta}_{p}^{(t)}\bigg{ ]},\\ C_{i,r,j}^{(t+1)}=C_{i,r,j}^{(t)}+{\eta}\mathbb{E}\bigg{[}\big{(}1_{\{y=i\}}- \operatorname{logit}_{i}(\bm{F}^{(t)},\widetilde{\bm{X}}^{(t)})\big{)}\sum \limits_{p\in[P]}\widetilde{\operatorname{ReLU}}^{\prime}\left(\langle\bm{w}_{ i,r}^{(t)},\tilde{\bm{x}}_{p}^{(t)}\rangle\right)\tilde{\lambda}_{p,j}^{(t)} \bigg{]},\\ D_{i,r,j}^{(t+1)}=D_{i,r,j}^{(t)}+{\eta}\mathbb{E}\bigg{[}\big{(}1_{\{y=i\}}- \operatorname{logit}_{i}(\bm{F}^{(t)},\widetilde{\bm{X}}^{(t)})\big{)}\sum \limits_{p\in[P]}\widetilde{\operatorname{ReLU}}^{\prime}\left(\langle\bm{w}_{ i,r}^{(t)},\tilde{\bm{x}}_{p}^{(t)}\rangle\right)\tilde{\mu}_{p,j}^{(t)}\bigg{ ]}\\ E_{i,r,y,s}^{(t+1)}=E_{i,r,y,s}^{(t)}+{\eta}\mathbb{E}\bigg{[}\big{(}1_{\{y=i \}}-\operatorname{logit}_{i}(\bm{F}^{(t)},\widetilde{\bm{X}}^{(t)})\big{)}\sum \limits_{p\in[P]}\widetilde{\operatorname{ReLU}}^{\prime}\left(\langle\bm{w}_{ i,r}^{(t)},\tilde{\bm{x}}_{p}^{(t)}\rangle\right)\tilde{\gamma}_{p,y,s}^{(t)} \bigg{]}.\end{cases}$ $$

###### Proof.

The proof method is the same as in standard training (Lemma D.4), we simply project the gradient descent recursion onto each feature direction to derive this lemma.
∎

###### Lemma D.17 .

###### Proof.

###### Lemma D.18 (Feature Learning Iteration for Adversarial Training) .

###### Proof.

#### D.2.3 Logit Approximation at Adversarial Examples

First, we give the following diagonal adversarial logit approximation lemma.

###### Lemma D.19 (Diagonal Adversarial Logit Approximation) .

For any adversarial data point $(\widetilde{\bm{X}}^{(t)},y)\sim\mathcal{D}$, suppose that $\operatorname{max}_{i\in[k],r\in[m]}A_{i,r}^{(t)}=O(\operatorname{log}(d))$ and $\operatorname{max}_{i\in[k],r\in[m]}B_{i,r}^{(t)}=o(1)$$\operatorname{max}_{i\in[k],r\in[m],y\in[k]\setminus\{i\}}C_{i,r,y}^{(t)}=O(
\operatorname{log}(d)/\sqrt{d})$ and $\operatorname{max}_{i\in[k],r\in[m],y\in[k]\setminus\{i\}}D_{i,r,y}^{(t)}=O(
\operatorname{log}(d)/\sqrt{d})$, and $F_{y}(\widetilde{\bm{X}}^{(t)})\geq c\operatorname{log}(d)$ for some $c\geq 0$, then we have the following approximation of logit:

$$ $1-\operatorname{logit}_{y}(\bm{F}^{(t)},\widetilde{\bm{X}}^{(t)})=\begin{cases }\Theta(1)&,\textit{if }c=0;\\ O\left(\frac{1}{d^{c}}\right)&,\textit{if }c>0.\end{cases}$ $$

###### Proof.

The proof logic is similar to Lemma D.5.
∎

Then, we give the following non-diagonal adversarial logit approximation lemma.

###### Lemma D.20 (Non-diagonal Adversarial Logit Approximation) .

For any adversarial data point $(\widetilde{\bm{X}}^{(t)},y)\sim\mathcal{D}$, suppose that $\operatorname{max}_{i\in[k],r\in[m]}A_{i,r}^{(t)}=O(\operatorname{log}(d))$ and $\operatorname{max}_{i\in[k],r\in[m]}B_{i,r}^{(t)}=o(1)$$\operatorname{max}_{i\in[k],r\in[m],y\in[k]\setminus\{i\}}C_{i,r,y}^{(t)}=O(
\operatorname{log}(d)/\sqrt{d})$ and $\operatorname{max}_{i\in[k],r\in[m],y\in[k]\setminus\{i\}}D_{i,r,y}^{(t)}=O(
\operatorname{log}(d)/\sqrt{d})$, and $F_{y}(\widetilde{\bm{X}}^{(t)})\geq c\operatorname{log}(d)$ for some $c\geq 0$, for $i\neq y$:

$$ $\operatorname{logit}_{i}(\bm{F}^{(t)},\widetilde{\bm{X}}^{(t)})=\begin{cases} \Theta(1/k)&,\textit{if }c=0;\\ O\left(\frac{1}{d^{c}}\right)&,\textit{if }c>0.\end{cases}$ $$

###### Proof.

The proof logic is also similar to Lemma D.6.
∎

###### Lemma D.19 (Diagonal Adversarial Logit Approximation) .

###### Proof.

###### Lemma D.20 (Non-diagonal Adversarial Logit Approximation) .

###### Proof.

#### D.2.4 Non-diagonal Terms are Small

###### Lemma D.21 .

For every time $t$, non-diagonal weight-feature correlations $C_{i,r,y}^{(t)},D_{i,r,y}^{(t)}$ ($(i,r)\in[k]\times[m],y\neq i$) satisfy that $\operatorname{max}_{r\in[m]}C_{i,r,y}^{(t)}=O(\operatorname{max}_{r\in[m]}C_{i
,r,y}^{(0)})$ and $\operatorname{max}_{r\in[m]}D_{i,r,y}^{(t)}=O(\operatorname{max}_{r\in[m]}D_{i
,r,y}^{(0)})$ for each $i\in[k],y\in[k]\setminus\{i\}$.

###### Proof.

The proof logic is also similar to Lemma D.7.
∎

###### Lemma D.21 .

###### Proof.

#### D.2.5 Analysis of Feature Learning Process for Adversarial Training

Stage I: Almost neurons lie within the polynomial part of activation $\widetilde{ReLU}$.

###### Lemma D.22 .

During adversarial training, there exists some time threshold $T_{0}>0$ such that, for any early time $0\leq t\leq T_{0}$ and pair $(i,r)\in[k]\times[m]$, the two sequences $\{A_{i,r}^{(t)}\}$ and $\{B_{i,r}^{(t)}\}$ satisfy:

$$ $\begin{cases}A_{i,r}^{(t+1)}\approx A_{i,r}^{(t)}+\Theta(\eta)\left(A_{i,r}^{( t)}\right)^{q-1}\mathbb{E}\bigg{[}\sum\limits_{p\in\mathcal{J}_{\textit{R}}} \alpha_{p}^{q}\big{(}1-\operatorname{min}\big{\{}\frac{\epsilon}{\alpha_{p}}, \tilde{\Theta}(\tilde{\eta})\sum\limits_{s\in[m]}\big{(}A_{i,s}^{(t)}\big{)}^{ q}\big{\}}\big{)}^{q}\bigg{]},\\ B_{i,r}^{(t+1)}\approx B_{i,r}^{(t)}+\Theta(\eta)\left(B_{i,r}^{(t)}\right)^{q -1}\mathbb{E}\bigg{[}\sum\limits_{p\in\mathcal{J}_{\textit{NR}}}\beta_{p}^{q} \big{(}1-\operatorname{min}\big{\{}\frac{\epsilon}{\beta_{p}},\tilde{\Theta}( \tilde{\eta})\sum\limits_{s\in[m]}\big{(}B_{i,s}^{(t)}\big{)}^{q}\big{\}}\big{ )}^{q}\bigg{]}.\end{cases}$ $$

###### Proof.

The proof logic is similar to Lemma D.4.
∎

Phase I: First, Network Partially Learns Non-Robust Features.

At the beginning, due to our small initialization, we know all feature learning coefficients $A_{i,r}^{(t)},B_{i,r}^{(t)}=o(1)$, which suggests that the total feature learning $\sum_{s\in[m]}\big{(}A_{i,s}^{(t)}\big{)}^{q}$ and $\sum_{s\in[m]}\big{(}B_{i,s}^{(t)}\big{)}^{q}$ are sufficiently small. Then, the feature learning process is similar to standard training until the non-robust feature learning becomes large.

Phase II: Next, Robust Feature Learning Starts Increasing.

By applying Tensor Power Method Lemma B.2, we have the following result.

###### Lemma D.23 .

For each $y\in[k]$, let time $T_{y}$ denote the first time when $\sum_{s\in[m]}\big{(}B_{y,s}^{(t)}\big{)}^{q}$ reaches $\tilde{\Theta}(\eta^{-1})$, then we have $\operatorname{max}_{r\in[m]}A_{y,r}^{(T_{y})}=O(\operatorname{polylog}(d)/
\sqrt{d})$.

###### Proof.

We choose $x_{t}=A_{y,r}^{(t)}$ and $y_{t}=B_{y,s}^{(t)}$. Then, by applying Lemma B.2, we can derive this result as the same way as the proof of Lemma D.9.
∎

Once the total non-robust feature learning $\sum_{s\in[m]}\big{(}B_{i,s}^{(t)}\big{)}^{q}$ attains an order of $\tilde{\Theta}(\tilde{\eta}^{-1})$, it is known that the non-robust feature learning will stop, due to $\frac{\epsilon}{\beta_{p}}\gtrsim 1$ and $1-\tilde{\Theta}(\tilde{\eta})\sum_{s\in[m]}\big{(}B_{i,s}^{(t)}\big{)}^{q}\approx
0$.

In contrast, the robust feature learning continues to increase since it always holds that $1-\operatorname{min}\big{\{}\frac{\epsilon}{\alpha_{p}},\tilde{\Theta}(\tilde{
\eta})\sum_{s\in[m]}\big{(}A_{i,s}^{(t)}\big{)}^{q}\big{\}}\geq 1-\frac{
\epsilon}{\alpha_{p}}\geq\Omega(1)$. Thus, the robust feature learning will increase over the non-robust feature learning finally, which can represented as the following lemma.

###### Lemma D.24 .

For each $y\in[k]$, let time $T_{y}^{{}^{\prime}}$ denote the first time when $\operatorname{max}_{r\in[m]}A_{y,r}^{(t)}$ reaches $\varrho/\alpha$, then we have $T_{y}^{{}^{\prime}}=O(\operatorname{poly}(d))$ and $\operatorname{max}_{r\in[m]}B_{y,r}^{(T_{y}^{{}^{\prime}})}=O(1/d^{c_{0}})$.

###### Proof.

The proof logic is similar to Lemma D.10.
∎

Stage II: Robust feature learning arrives at linear region of activation $\widetilde{ReLU}$.

###### Lemma D.25 .

For each $y\in[k]$ and $(\bm{X},y)\sim\mathcal{D}$, let time $T_{y}^{{}^{\prime\prime}}$ denote the first time such that $F_{y}^{(t)}(\widetilde{\bm{X}}^{(t)})\geq\operatorname{log}(d)$, then $T_{y}^{{}^{\prime\prime}}=\operatorname{poly}(d)\geq T_{y}$, and we have $\operatorname{max}_{r\in[m]}B_{y,r}^{(T_{y}^{{}^{\prime}})}=O(\operatorname{
polylog}(d)/d^{c_{0}})$.

###### Proof.

The proof logic is also similar to Lemma D.10.
∎

###### Lemma D.26 .

For all time $t=O(\operatorname{poly}(d))\geq T_{y}^{{}^{\prime\prime}}$ and each $(\bm{X},y)\sim\mathcal{D}$, we have $F_{y}^{(t)}(\widetilde{\bm{X}}^{(t)})=O(\operatorname{log}(d))$, and $\operatorname{max}_{r\in[m]}B_{y,r}^{(t)}=O(\operatorname{polylog}(d)/d^{c_{0}})$.

###### Proof.

The proof logic is similar to Lemma D.8.
∎

###### Lemma D.22 .

###### Proof.

###### Lemma D.23 .

###### Proof.

###### Lemma D.24 .

###### Proof.

###### Lemma D.25 .

###### Proof.

###### Lemma D.26 .

###### Proof.

#### D.2.6 Proof of Theorem D.15

###### Lemma D.27 (Robust Features are Learned Well) .

For $T=\Theta(\operatorname{poly}(d))$ and each data point $(\bm{X},y)\sim\mathcal{D}_{\mathcal{F}_{\textit{R}}}$, with probability $1-o(1)$, we have $F_{y}^{(T)}(\bm{X})>F_{i}^{(T)}(\bm{X}),\forall i\in[k]\setminus\{y\}$.

###### Proof.

The proof logic is similar to Lemma D.13.
∎

###### Lemma D.28 (Adversarial Training Converges to Robust Solution) .

For $T=\Theta(\operatorname{poly}(d))$ and each data point $(\bm{X},y)\sim\mathcal{D}_{\mathcal{F}_{\textit{R}}}$, with probability $1-o(1)$, we have $\forall\bm{\Delta}\in\left(\mathbb{R}^{d}\right)^{P}\textit{ s.t. }\|\bm{
\Delta}\|_{\infty}\leq\epsilon,\operatorname{argmax}_{i\in[k]}F_{i}^{(T)}(\bm{
X}+\bm{\Delta})=y$.

###### Proof.

For a given data point $(\bm{X},y)\sim\mathcal{D}$ and any perturbation $\bm{\Delta}=(\bm{\delta}_{1},\bm{\delta}_{2},\dots,\bm{\delta}_{p})\in\left(
\mathbb{R}^{d}\right)^{P}$ satisfying $\|\bm{\Delta}\|_{\infty}\leq\epsilon$, we calculate the perturbed margin as follows.

$$ $\displaystyle F_{y}^{(T)}(\bm{X}+\bm{\Delta})$ $\displaystyle=\sum_{r\in[m]}\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{ \operatorname{ReLU}}(\langle\bm{w}_{y,r}^{(T)},\alpha_{p}\bm{u}_{y}+\bm{\delta }_{p}\rangle)+\sum_{r\in[m]}\sum_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{ \operatorname{ReLU}}(\langle\bm{w}_{y,r}^{(T)},\beta_{p}\bm{v}_{y}+\bm{\delta} _{p}\rangle)$ $\displaystyle\geq\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{\operatorname{ ReLU}}(\Theta(\alpha_{p}\operatorname{max}_{r\in[m]}A_{y,r}^{(T)}))$ $\displaystyle\geq\sum_{p\in\mathcal{J}_{\textit{R}}}\Theta(\alpha_{p} \operatorname{max}_{r\in[m]}A_{y,r}^{(T)})$ $\displaystyle\geq\Theta(\operatorname{log}(d)),$ $$

where we use Lemma D.21 and Lemma D.26 and the first part of Assumption 2.3 (i.e. $\alpha_{p}\gg\epsilon$).

And for any $j\in[P]\setminus\{y\}$, we have

$$ $\displaystyle F_{j}^{(T)}(\bm{X}+\bm{\Delta})$ $\displaystyle=\sum_{r\in[m]}\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{ \operatorname{ReLU}}(\langle\bm{w}_{j,r}^{(T)},\alpha_{p}\bm{u}_{y}+\bm{\delta }_{p}\rangle)+\sum_{r\in[m]}\sum_{p\in\mathcal{J}_{\textit{NR}}}\widetilde{ \operatorname{ReLU}}(\langle\bm{w}_{j,r}^{(T)},\beta_{p}\bm{v}_{y}+\bm{\delta} _{p}\rangle)$ $\displaystyle\leq\sum_{p\in\mathcal{J}_{\textit{R}}}\widetilde{\operatorname{ ReLU}}(\Theta(\alpha_{p}\operatorname{max}_{r\in[m]}C_{j,r,y}^{(T)}))+\sum_{p \in\mathcal{J}_{\textit{NR}}}\widetilde{\operatorname{ReLU}}(\Theta(\beta_{p} \operatorname{max}_{r\in[m]}D_{j,r,y}^{(T)}))$ $\displaystyle\leq o(\operatorname{log}(d)),$ $$

where we also use Lemma D.21 and Lemma D.26.

Therefore, we derive the theorem.
∎

###### Lemma D.27 (Robust Features are Learned Well) .

###### Proof.

###### Lemma D.28 (Adversarial Training Converges to Robust Solution) .

###### Proof.

## Appendix E Proof for Section 4

### E.1 Proof for Standard Training

###### Theorem E.1 .

For sufficiently large $d$, suppose we train the model using the standard training starting from the random initialization, then after $T=\Theta(\operatorname{poly}(d)/\eta)$ iterations, with high probability over the sampled training dataset $\mathcal{Z}$, the model $\bm{F}^{(T)}$ satisfies:

- •
Standard training is perfect: for all $(\bm{X},y)\in\mathcal{Z}$, all $i\in[k]\backslash\{y\}:F_{y}^{(T)}(\bm{X})>F_{i}^{(T)}(\bm{X})$.
- •
Non-robust features are learned: $\mathbb{P}_{(\bm{X}_{\bm{f}},y)\sim\mathcal{D}_{\mathcal{F}_{\textit{NR}}}}
\left[\operatorname{argmax}_{i\in[k]}F_{i}^{(T)}(\bm{X}_{\bm{f}})\neq y\right]
=o(1)$.
- •
Standard test accuracy is good: $\mathbb{P}_{(\bm{X},y)\sim\mathcal{D}}\left[\operatorname{argmax}_{i\in[k]}F_{
i}^{(T)}(\bm{X})\neq y\right]=o(1)$.
- •
Robust test accuracy is bad: for any given data $(\bm{X},y)$, using the following perturbation $\bm{\Delta}(\bm{X},y):=(\bm{\delta}_{1},\bm{\delta}_{2},\dots,\bm{\delta}_{P})$, where $\bm{\delta}_{p}:=-\beta_{p}\bm{v}_{y}+\epsilon\bm{v}_{y^{\prime}}$ for $p\in\mathcal{J}_{\textit{NR}}$; $\bm{\delta}_{p}:=\bm{0}$ for $p\in\mathcal{J}_{\textit{R}}$, and $y^{\prime}$ is randomly chosen from $[k]\setminus\{y\}$ (which does not depend on the model $\bm{F}^{(T)}$ and is illustrated in Figure 2), we have
$\mathbb{P}_{(\bm{X},y)\sim\mathcal{D}}\left[\operatorname{argmax}_{i\in[k]}F_{
i}^{(T)}(\bm{X}+\bm{\Delta}(\bm{X},y))\neq y\right]=1-o(1).$

Proof Idea: Our proof is divided into the following three steps (the proof approach is almost identical to that of Theorem D.1, with the only difference being that we need to demonstrate that during the standard training process, the noise terms remain small at all times). Except for special mention, the logic and process of proving all lemmas are similar to the simplified case without noise.

###### Theorem E.1 .

#### E.1.1 Weight Decomposition for Standard Training

###### Lemma E.2 (Weight Decomposition for Standard Training) .

For any time $t\geq 0$, each neuron $\bm{w}_{i,r}$ ($(i,r)\in[k]\times[m]$), we have

$$ $\bm{w}_{i,r}^{(t)}=\bm{w}_{i,r}^{(0)}+A_{i,r}^{(t)}\bm{u}_{i}+B_{i,r}^{(t)}\bm {v}_{i}+\sum_{j\neq i}(C_{i,r,j}^{(t)}\bm{u}_{j}+D_{i,r,j}^{(t)}\bm{v}_{j})+ \sum_{(\bm{X},y)\in\mathcal{Z}}\sum_{p\in[P]}\sigma_{i,r}((\bm{X},y),p)\bm{\xi }_{p},$ $$

where $A_{i,r}^{(t)},B_{i,r}^{(t)},C_{i,r,j}^{(t)}$ and $D_{i,r,j}^{(t)}$ and $\sigma_{i,r}((\bm{X},y),p)$ are some time-variant coefficients.

###### Lemma E.2 (Weight Decomposition for Standard Training) .

#### E.1.2 Noise Terms are Small

Different from the simplified scenario, we need to prove that the noise terms are always small, which can be presented as the following lemma.

###### Lemma E.3 (Noise Correlations are Always Small) .

For any time $t=O(\operatorname{poly}(d))$ and each training data point $(\bm{X},y)\in\mathcal{Z}$ and for each patch index $p\in[P]$, we have $\langle\bm{w}_{i,r}^{(t)},\bm{\xi}_{p}\rangle=\tilde{O}(1/\sqrt{d})$.

###### Proof.

By analyzing the iterative process of the noise terms, we have the following lemma:

###### Lemma E.4 (Noise Correlation Update) .

For every $(\bm{X},y)\in\mathcal{Z}$ and $p\in[P]$, if $y=i$ then

$$ $\left\langle\bm{w}_{i,r}^{(t+1)},\bm{\xi}_{p}\right\rangle=\left\langle\bm{w}_ {i,r}^{(t)},\bm{\xi}_{p}\right\rangle+\widetilde{\Theta}\left(\frac{\eta}{N} \right)\widetilde{\operatorname{ReLU}}^{\prime}\left(\left\langle\bm{w}_{i,r}^ {(t)},\bm{x}_{p}\right\rangle\right)\left(1-\operatorname{logit}_{i}\left(\bm{ F}^{(t)},\bm{X}\right)\right)\pm\frac{\eta}{\sqrt{d}}$ $$

for similar reason, if $y\neq i$, then

$$ $\left\langle\bm{w}_{i,r}^{(t+1)},\bm{\xi}_{p}\right\rangle=\left\langle\bm{w}_ {i,r}^{(t)},\bm{\xi}_{p}\right\rangle-\widetilde{\Theta}\left(\frac{\eta}{N} \right)\widetilde{\operatorname{ReLU}}^{\prime}\left(\left\langle\bm{w}_{i,r}^ {(t)},\bm{x}_{p}\right\rangle\right)\operatorname{logit}_{i}\left(\bm{F}^{(t)} ,\bm{X}\right)\pm\frac{\eta}{\sqrt{d}}$ $$

Using the same line of reasoning as in the simplified case (Lemma D.5, Lemma D.6 and Lemma D.8), we can derive the following two lemmas:

###### Lemma E.5 .

For each class $i\in[k]$ and all time $t$ such that $\operatorname{max}_{(\bm{X},y)\in\mathcal{Z}_{i}}F_{y}^{(t)}(\bm{X})\geq
\operatorname{log}(d)$ and $\operatorname{max}_{r\in[m]}A_{i,r}^{(t)}=O(\operatorname{polylog(d)}/\sqrt{d})$ and $\operatorname{max}_{r\in[m]}C_{i,r,y}^{(t)}=O(\operatorname{polylog(d)}/\sqrt{
d})$ and $\operatorname{max}_{r\in[m]}D_{i,r,y}^{(t)}=O(\operatorname{polylog(d)}/\sqrt{
d})$ for each $i\in[k],y\in[k]\setminus\{i\}$, we have $\operatorname{min}_{(\bm{X},y)\in\mathcal{Z}_{i}}F_{y}^{(t)}(\bm{X})=\Omega(
\operatorname{max}_{(\bm{X},y)\in\mathcal{Z}_{i}}F_{y}^{(t)}(\bm{X}))$.

###### Lemma E.6 .

For some time $T_{0}$, we have $\sum_{t=T_{0}}^{T}\mathbb{E}_{(\bm{X},y)\sim\mathcal{Z}}\left[1-\operatorname{
logit}_{y}\left(\bm{F}^{(t)},\bm{X}\right)\right]=\tilde{O}(\eta^{-1})$.

Combined with Lemma E.4, Lemma E.5 and Lemma E.6, and $N=\operatorname{poly}(d)$, we can prove this lemma.
∎

###### Lemma E.3 (Noise Correlations are Always Small) .

###### Proof.

###### Lemma E.4 (Noise Correlation Update) .

###### Lemma E.5 .

###### Lemma E.6 .

#### E.1.3 Feature Learning for Standard Training

Theorem E.1 is a direct corollary of the following lemma:

###### Lemma E.7 .

For sufficiently large time $T=\Theta(\operatorname{poly}(d))$ , we have $\operatorname{max}_{r\in[m]}B_{i,r}^{(t)}=\Theta(\operatorname{log(d)})$ and $\operatorname{max}_{r\in[m]}A_{i,r}^{(t)}=O(\operatorname{polylog(d)}/\sqrt{d})$ and $\operatorname{max}_{r\in[m]}C_{i,r,y}^{(t)}=O(\operatorname{polylog(d)}/\sqrt{
d})$ and $\operatorname{max}_{r\in[m]}D_{i,r,y}^{(t)}=O(\operatorname{polylog(d)}/\sqrt{
d})$ for each $i\in[k],y\in[k]\setminus\{i\}$.

###### Proof.

Due to Lemma E.3, we can prove this lemma using the exact same logic as that used to prove Lemma D.8.
∎

###### Lemma E.7 .

###### Proof.

### E.2 Proof for Adversarial Training

###### Theorem E.8 .

For sufficiently large $d$, suppose we train the model using the adversarial training algorithm starting from the random initialization, then after $T=\Theta(\operatorname{poly}(d)/\eta)$ iterations, with high probability over the sampled training dataset $\mathcal{Z}$, the model $\bm{F}^{(T)}$ satisfies:

- •
Adversarial training is perfect: for all $(\bm{X},y)\in\mathcal{Z}$ and all perturbation $\bm{\Delta}$ satisfying $\|\bm{\Delta}\|_{\infty}\leq\epsilon$, all $i\in[k]\backslash\{y\}:F_{y}^{(T)}(\bm{X}+\bm{\Delta})>F_{i}^{(T)}(\bm{X}+\bm{
\Delta})$.
- •
Robust features are learned: $\mathbb{P}_{(\bm{X}_{\bm{f}},y)\sim\mathcal{D}_{\mathcal{F}_{\textit{R}}}}
\left[\operatorname{argmax}_{i\in[k]}F_{i}^{(T)}(\bm{X}_{\bm{f}})\neq y\right]
=o(1)$.
- •
Robust test accuracy is good:
$\mathbb{P}_{(\bm{X},y)\sim\mathcal{D}}\left[\exists\bm{\Delta}\in\left(\mathbb
{R}^{d}\right)^{P}\textit{ s.t. }\|\bm{\Delta}\|_{\infty}\leq\epsilon,
\operatorname{argmax}_{i\in[k]}F_{i}^{(T)}(\bm{X}+\bm{\Delta})\neq y\right]=o(
1).$

Proof Idea: Our proof approach is almost identical to that of Theorem D.15, with the only difference being that we need to demonstrate that during the adversarial training process, the noise terms remain small at all times.

###### Theorem E.8 .

#### E.2.1 Weight Decomposition for Adversarial Training

###### Lemma E.9 (Weight Decomposition for Adversarial Training) .

For any time $t\geq 0$, each neuron $\bm{w}_{i,r}$ ($(i,r)\in[k]\times[m]$), we have

$$ $\bm{w}_{i,r}^{(t)}=\bm{w}_{i,r}^{(0)}+A_{i,r}^{(t)}\bm{u}_{i}+B_{i,r}^{(t)}\bm {v}_{i}+\sum_{j\neq i}(C_{i,r,j}^{(t)}\bm{u}_{j}+D_{i,r,j}^{(t)}\bm{v}_{j})+ \sum_{(\bm{X},y)\in\mathcal{Z}}\sum_{p\in[P]}\sigma_{i,r}((\bm{X},y),p)\bm{\xi }_{p},$ $$

where $A_{i,r}^{(t)},B_{i,r}^{(t)},C_{i,r,j}^{(t)}$ and $D_{i,r,j}^{(t)}$ and $\sigma_{i,r}((\bm{X},y),p)$ are some time-variant coefficients.

###### Lemma E.9 (Weight Decomposition for Adversarial Training) .

#### E.2.2 Noise Terms are Small

Similar to standard training, we also need to prove that the noise terms are always small, which can be presented as the following lemma.

###### Lemma E.10 (Noise Correlations are Always Small) .

For any time $t=O(\operatorname{poly}(d))$ and each training data point $(\bm{X},y)\in\mathcal{Z}$ and for each patch index $p\in[P]$, we have $\langle\bm{w}_{i,r}^{(t)},\bm{\xi}_{p}\rangle=\tilde{O}(1/\sqrt{d})$.

###### Proof.

The proof logic is similar to Lemma E.3.
∎

###### Lemma E.10 (Noise Correlations are Always Small) .

###### Proof.

#### E.2.3 Feature Learning for Adversarial Training

Theorem E.8 is a direct corollary of the following lemma:

###### Lemma E.11 .

For sufficiently large time $T=\Theta(\operatorname{poly}(d))$ , we have $\operatorname{max}_{r\in[m]}A_{i,r}^{(t)}=\Theta(\operatorname{log(d)})$ and $\operatorname{max}_{r\in[m]}B_{i,r}^{(t)}=\tilde{O}(1/d^{c_{0}})$ and $\operatorname{max}_{r\in[m]}C_{i,r,y}^{(t)}=O(\operatorname{polylog(d)}/\sqrt{
d})$ and $\operatorname{max}_{r\in[m]}D_{i,r,y}^{(t)}=O(\operatorname{polylog(d)}/\sqrt{
d})$ for each $i\in[k],y\in[k]\setminus\{i\}$.

###### Proof.

Due to Lemma E.10, we can prove this lemma using the exact same logic as that used to prove Lemma D.26.
∎

###### Lemma E.11 .

###### Proof.

## Peer Reviews

confidence: 2
contribution: 2
initial_rating: 6
presentation: 3
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.
soundness: 3
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.
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.
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.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 4
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?
soundness: 3
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.
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.
weaknesses: - The complexity of the models and the heavy reliance on specific assumptions about data structure may limit the general applicability of the results.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
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.
soundness: 4
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
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.
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

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
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\)$.
soundness: 2
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).
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.
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.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
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.
soundness: 3
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.
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.
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.

Meta-review: 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.

Decision: Accept (Poster)