Adversarial Training Can Provably Improve Robustness: Theoretical Analysis of Feature Learning Process Under Structured Data
Authors: Binghui Li
Yuanzhi Li
Venue: ICLR 2025 Poster (2025)
Keywords: deep learning theory
feature learning
adversarial robustness
adversarial training
non-convex optimization
Primary area: learning theory
TL;DR: In this paper, we provide a theoretical understanding of adversarial examples and adversarial training algorithms from the perspective of feature learning theory.

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.

Published as a conference paper at ICLR 2025
ADVERSARIAL TRAINING CAN PROVABLY IMPROVE ROBUSTNESS: THEORETICAL ANALYSIS OF FEATURE LEARNING PROCESS UNDER STRUCTURED DATA
Binghui Li
Yuanzhi Li
Center for Machine Learning Research Peking University
Machine Learning Department
Carnegie Mellon University yuanzhi @@andrew... cmu edu
libinghui @pku. edu. .n
ABSTRACT
Adversarial training is a wipely-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 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 the adversarial examples that are generated by perturbations aligned with negative non-robust feature directions. Then, consider the gradient-based based adversarial training algorithm, which runs gradient ascent to find adversarial examples and runs gradient descent over the empirical risk 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 improve the network robustness. Finally, we also empirically validate our theoretical findings with experiments on real- real-image datasets, including MNIST, CIFARIO and SVHN.
INTRODUCTION
Recently, large-scale neural networks have achieved remarkable performance in many disciplines, especially in computer vision (Krizhevsky et al., 2012; Dosovitskiy et al., 2021; Kirillov al., 2023) and natural language processing (Kenton & Toutanova, 2019; Brown et al., 2020; Ouyang et al., 2022; Achiam et al., 2023). 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., 2013; Szegedy et al., 2013; Goodfellow et al., 2014), which can confuse well-trained network classifiers. This potentially leads 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., 2014; Madry et al., 2018: Shafahi et al., 2019; Zhang et al., 2019; Pang et al., 2022; Wang et al., 2023), 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, 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 bibeeraariall--erttthe data?

---

Published as a conference paper at ICLR 2025
Robust/Non-Robust F Feature Decomposition
Mersar I: Prodominently Learning Non-Rabust Fesuures
Mesagt 3: Adversurial Examples
Good Standard A ocuracy Bad Robust ocuracy
Eleptant
From Non-Rabust Feanurey
Standard Training
Robustness
Improvemen
Adversarial Training
Mevege Suppress Non-Rokust
Memsgr d: Enhance Robust
Feature Learning
Good Standard A ocuracy
Good Robust A ccuracy
Images
Sunentically-A1ge -lignnd
Festures
Nataed Bee Nan-labust Featurne
Froture Leurning
Figure I: An overview of our paper: robust/non ronbust cettttt-fcttre----ee decpurosicdooootiiiionn based framework and key messages about standard/adversariaa training. And the robust/noon-oot roouuttttorrrotttooooo features of elephant and cat are generated in the same way of Ilyas et al. (2019) from random noise to ImageNet instances.
Q2: How does the adversarial training algorithm assist in optimizing neural networks to enhance their robustness against udversarial perturbations?
Indeed, emphasize that common challenge in analyzing adversarial robustness is the gap between theory and practice, primarily attributed to the data assumptions theoretical frameworks (see detailed discussion in Section 1.1), which motives 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 series of previous studies (Tsipras et al., 2019; Ilyas et al., 2019; Kim et al., 2021; Tsilivis & Kempe, 2022; Han et al., 2023). Furthermore, we mathematically represent this concept the patch-struee natch-structured data proposed in the recent work of Allen-Zhu & Li (2023a), in which they utilize multi- view-based patch-structure
data to provide a fruitful setting for theoretically understanding the benefits of ensembles in deep learning. Specifically, inspired by Allen-Zhu & Li (2023a) and Ilyas et al. (2019), we propose a novel patch-structured data model based on robust/non-robut feature decomposition (Definition 2.2), and show our patch data model enables us 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 structured data. More precisely, the main results in our work are summarized as follows:
By analyzing the feature learning process on robust/non- 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, CIFARIO, 10, and SVHN). Detailed results be viewed in Figure 4.
1.1 RELATED WORKS
Theoretical Explanations for Adversarial Examples. A line of works (Daniely & Shacham, 2020; Bubeck al., 2021a; Bartlett et al., 2021; Montanari & Wu, 2023) demonstrates the existence of adversarial examples in handom-weight neural networks with various architectures. Another line of works (Bubeck et al., 2021b; Bubeck & Sellke, 2021; Li et al., 2022; Li & Li, 2023) suggests that
2

---

Published as a conference paper at ICLR 2025
over paramettttttiinooonnnn is necessary to achieve robustness, and that non 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. (2024) and Li et al. (2024) proved that, for two-layer ReLU networks, gradient method leads to -ell-generalizing but non-robust solutions under 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 al. (2019). Indeed, we not only prove that standard training causes two-layer neural network to converge to 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., 2020; Javanmard & Soltanolkotabi, 2022; Chen et al., 2023) demonstrate that linear classifier trained through adversarial training can achieve robustness under the Gaussian-mixtun 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., 2013; Szegedy et al., 2013; Goodfellow et al., 2014). For example, as noted in Chen et al. (2023), similar to standard training, adversarial training also directionally converges to the maximum & ma-mar solution when considering a Gaussian-mixtun data model with &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).
data model. However,
Feature Learning Theory of Deep Learning. The feature learning theory of neural networks, as proposed in various recent studies (Wen & Li, 2021; Allen-Zhu Li, 2022; Chen et al., 2022; Jelassi et al., 2022; Chidambaram et al., 2023; Allen-Zhu & Li, 2023b;a; Lu et al., 2024; Chen et al., 2024; Li et al., 2024), 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., 2018; Du et al., 2019b;a; Allen -Zhu et al., 2019; Arora et al., 2019). Based on the sparse coding model, Allen-Zhu & Li (2022) consider binary robust classification problem and proposes a principle called feature purification to explain the workings of adversarial training. In our paper, we focus on multiple robust classification problem by leveraging more image-like, patch-structured data with an assumption of robust/non-robus 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 letters for scalars and bold letters for vectors. For any given two pc sequences [A and { we denote An = =0 (B,) if there exist some absolute constant C > 0 and N1
such that [n S C1 [.]] for all n 2 N1. Similarly, we denote An = 52 (B,) if there exist C2 > 0 and N₂ > O such that [A, 2 C2 B.,l for all n > N2. We say A, = θ (B,) if A, (B,) and A,, = Ω (B,.) both holds. We use Ō(-), (2)). and é(-) to hide logarithmic factors in these notations respectively. Moreover, we denote A. = poly (B,) if A,, = 0 ((*)) for some positive constant K, and A, polylog (B,) if B, = poly (log (B.)). We say A, = ((B,) (or An < Bn or Bn >> A,) if for arbitrary positive constant C3 > O, there exists N3g 0 such that [An] < Cn| for all n > N3. And we also use An RV B, to denote A, B. + o1).
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 dimension of d. Specifically, each labeled data point is represented by (X. v), where X = (a) Iz.... xp) E (Rd)* denotes the data vector, and y E [k] signifies the data label. We first present the formal definition of robust and non-robust features follows.
3

---

Published as a conference paper at ICLR 2025
Mr Prrerttttee a (A)), S4
As Sumple
Dons youring (ostersen
of
frattii dis aus Aussss Wooh
Ocgial
-0
wetk
nare.
Amr
Adrmrrii Euoppe Arass
Aents
Foced Fate
4+
An +G
Foeter Toth
Non RicoRo Fatt
Figure 2: Illustration of our patch data: Each patch in data point (X, y) has the form Z, = up (robust-feature patch) or zp 5, &p ca--robstt-eettun patch), where u, are the corresponding features for class y. For reutt patches, adversarial perturbation A replaces non-robust feature o with other non-robust feature v' (corresponding to other class y'). which causes adversarial example with incorrect label y' when the network learner trained by standard training mainly learns non-robust features v, v' rather than robust features u, u'. And we construct robust-ccature/non- robust-feature data X., X. by replacing v/ with all-zero vector 0.
u
(Robust and Non-robust Features). We assume that each label class j [k] is associated with two types of features, for the sake mathematical simplicity, represented as two feature vectors u, (robust feature) and by (non-robust feature), both in Re For notation simplicity, we also assume that all the features are orthonormal and parallel to the coordinate axes. Namely, the of all features defined as
Definition 2.1
F: {uj, Uybeek
which satisfies that
Yf FFF, 1f = and ffF.FFf
For simplicity, we focus on the case when the dimension of patch d is sufficiently large (i.e. we assume poly(k) for a large polynomial) such that all 2k features can be orthogonal the space Rd And we use "with high probability" to denote with probability at least 1 - -Olog" d)
Now, we give the following distribution and some assumptions about it.
patch-structured data
Definition 2.2 (Patch Data Distribution). Each data pair (X,y) E (R.)) the distribution D with latent distributions (DJ Da.y: ) where DJ.y v is probability distribution over all 2-partitions of [P] and Da.y Dr. are distributions over the positive real number. Then, it generates data points as follows.
P x [k]] generated from
1. The label y is uniformly drawn from [k:]
2. Uniformly draw the two-type patch index sets (JR, JNR) C [P] x [P] from the distribution DJ.,y where JR and JNR corresponds to the robust-feature patches and non-robust feature patches such that JR INR [P] and JR n JNR 0.
3. For each [P], the corresponding patch vector is generated as
xp = aap + Ep, i E JR
(robust-feature patch) (non-robust-feature patch)
10 + Ep. if E JNR
where ap. 8p 0 are the random coefficients sampled from the distribution Da.y. De.y respectively, and & NO0,, TaTa) is the random Gaussian noise with variance of
4

---

Published as a conference paper at ICLR 2025
Assumption 2.3. We suppose that the following conditions holds for the data distribution D. In data point yX sampled from D, with high probability. it satisfies:
Robust feature is stronger than non-robust feature: V(p.p') E In x JNN, Op >>
Byr.
Non-robust feature is denser than robust feature: 3r 2 0, EpEJh oz < Epeci 5p.
Regarding the first condition of Assumption 2.3, We further assume that ap, Sp concentrate on their expectations (i.e., w.h.p. Op R E[ap), Sp x E[$p) and B[[p]] > 3 = (a vd) for simplicity. Then, we know, with high probability over a sampled data, holds that ((p.p') JR x JNR, ap > 3, ~ |e ll2 s ||Ep le Rs on, v vd, which means that robust-feature patches Bp = ap u + E. se ap appear more prominent, but non-robust-feature patches Ty' 8p Ey are noise-like.
Regarding the second condition of Assumption 2.3. Here, T is an absolutely constant. We notice that when 0, it implies w.h.p. [Jx] < [Tvæl which manifests that waa---oouufftttuee patches are denser than robust-feature patches. And we assume T 2 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 kemne size, high-magnitude good features that easily perceivable by humans in 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 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 llyas et al. (2019); Kim et al. (2021) characterize robust features as useful for both clean and robust classification, whereas non 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 {ur heej act as robust classifiers, while those relying on non-robon non-robust features {v; Joiie perform well on clean data but not on perturbed data, as detailed in Propositions 3. and 3.2 in Section 3.
2.3 NETWORK LEARNER
We consider the setting of learning the data distribution D by applying the same two-layer convolu- tional architecture used in Allen-Zhu & Li (2023a) with the following smoothed ReLU activation.
Activation. For integer g 2 2 and threshold a. the smoothed ReI.U is defined as ReLU(=) = 0 for
2 $ 0; ReRLU(()= = qe x for 2 E [0, Øl: and ReLU(2) = = (1 o for 2 2 0.
ReLU addresses the non-smoothness of original ReLU function at zero. We focus on the case when
q 3 and 0 polylog(aj for simplicity, while our result indeed applies to other constants g E [3, T).
Network Model. For the k-class classification task, consider the following two-layer convolutional
neural network as F(X)= = (Fi (X), (2. Fx(()))))))))))))))))))))))))) (Re)) P - TR and (x( denotes
Fx(x: = Σ ReLU ((0;,,)..
rE[m] PE[P]
where (wi,r E Rdd (()()))))))) are learnable weights for different convolutional filters. We set the
width m = polylog(d) d) to achieve mildly over- peeeparamettiiiiionnn for efficient optimization purpose.
2.4 STANDARD TRAINING
Training Objective. During the standard training. we learn the concept class (namely, the labeled data distribution D) by minimizing the cross-entropy loss function LeE using N = poly(d) train- ing data points Z {(X,, vt) JeIN] randomly sampled from D. By denoting (cx(F; X y) :=
-log
y)) as objective. Eyejy (x0) we use the empirical loss (F)(F)= := Exxw> X,y)
e2(())
Network Initialization. We randomly initialize the network F by letting each w (0) ~ N (0, [I) for of 3. which is the standard Xavier initialization (Glorot & Bengio, 2010).
5

---

Published as a conference paper at ICLR 2025
Training Algorithm. To train the model, at each iteration update using the gradient descent
(GD) with small learning rate 7) S poly(d)* un (t+1)
wi,r (x Vew,,. (F x,y]]
(t)
where we run the algorithm for == poly(d) iterations. We use F(O) to denote the model at iteration t.
2.5 ADVERSARIAL TRAINING
tp Advvraaaai Robustness. In our work, we consider ep-robustness within a perturbation radius 0, especially the -norm on which we focus henceforth for notation simplicity. Our main results can be easily extended to other f--norm case (p 2 2).
Small Perturbation Radius.
In our setting, we choose
(d). Then, for two data points
(X, (X', v/) ~ 'D with distinct labels y + y E [k:], it can be checked that w.h.p. || - -XX- x1 >
Vd), ((c), which is consistent with the empirical observation that typical perturbation radius often much smaller than the separation distance between different classes (Yang al., 2020).
. F&) and a data point (X.y), we say that X is an adversarial example (Szegedy et al., 2013) if the classifier predicts wrong label for it ||| S.
Adversarial Example. For a given network F := (F1, F2....,
(i.e. argmax)e(s (X) A y) and the perturbation A X X satisfies
Adversarial Training Algorithm. During adversarial training. we first find the adversarial examples y) by one-step gradient ascent with learning rate r (>> 17) over the margin loss Emargin [F; X y) using training data points (X, v) E Z. Here, we choose Lmargin [F; (xx3x) y) == - (x)) for simplicity. and our theoretical analysis can also be extended to the standard margin- based adversarial-attack objective function Lmorgia F; v) == (F, (X) max,e((]) (M) (x))) (Carlini & Wagner, 2017; Gowal et al., 2019; Sriramanan al., 2020). And then we train the network parameters
(wi,r (1.)) [m]] by taking gradient descent over the adversarial loss (x,=>>> (LEK (F:X.U)
Concretely, the adversarial examples {(X(1, (0,,)) and the network F(t) are updated alternatively as
X X + Clipoe,e (nVV x Lmargin (F(1); X, x,y)) V(X, E (++1) (8) w wor [1xx21)~ Vur, F(tt;; (()) ((xx)))))) :)) v(irr) E [X] [m].
where > is the Eoo pertuurrbaato radius and patch-wise clip function Clip (-) is used to enable X E (X, E). which is defined as, for the clip radius p >> and given flattened patch data Z (E1, 151,22.-1 22...., ZPa)== E (124)* P. Clipoc,p == (ž1, ...... EPs), 2 = max 2,
Vj E [Pd].
Remark 2.5. Indeed, 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.
x = argmax Al Emargin (F x+
However, different from some previous works (Li et al., 2020; Javanmard Soltanolkotabi, 2022: Chen el al., 2023) 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-ecnyyxity of the objective function Lmargin F A.y) over A. To overcome this challenge, we use one-step gradient ascent method to approximate the optimal solution.
WARM UP: THERE EXIST BOTH NOB-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 Lcr(F) over the parameters (w.rr(ttr)) x|m] Proposition 3.1 (The Existence of Non-robust Global Minima). We consider the special case when m and Wi,1 = -V,, where 7 > O is scale coefficient. Then, it holds that the standard empirical risk satisfies lim (CF(F) = o(1), but the adversarial test error satisfies
AA E (RR)& P s.1. |||| Joo S argmax F((X + A) = =1 o(1).
1om P(X,)>>

---

Published as a conference paper at ICLR 2025
Proposition 3.2 (The Existence of Robust Global Minima). We consider the special case when m and 1 = yyu, where Y > is a scale coefficient. Then, it holds that the stan- dard empirical risk satisfies lim (F) o(1), and the adversarial test enror satisfies
P(x A E (R+)*
P s.t. | &o I argmax, F((X A) + - o(1)
Proposition 3.1 and Proposition 3.2 demonstrate that network is vulnerable adversarial perturba- tions it relies solely on learning non-robust features. Conversely, a network that learns all robust features achieve 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
Wi,r Uu B + Noise,
where Ai,,, B represent the coefficients for learning robust and non-robust features, re- spectively, and the 'Noise' term encompasses elements learned from other non-diagonal features uj i), as well random noise Ep-
Therefore, we know that the network learns the i-th class if and only if either Ai, or B y is sufficiently large. However, robustly learn the i-th class, the network must primarily learn the robust feature u. rather than the non-robust feature v, which motivates us to analyze the feature learning process of standard training and adversarial training understand the underlying mechanism why adversarial examples exist and how adversarial training algorithm works.
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 H. CF (F is all feature set as the same as Definition 2), H-extended feature representative distribution Dz and classifier model F, we define the feature learning accuracy as ()) argmax{e(1] F = y where , E H) is the f-extended representative and y is the label which feature f corresponds to.
Here, we choose FR := he(k)) FNR == {Vc]ie(k) C. F as vobust/non-robuse feature sets. We construct Drx/DFn by sampling (X,y) ~ and setting X, to X with all instances of feature vi/u, replaced by all-zero vector (a figurative illustration is presented in Figure 2).
Remark 4.2. We define feature learning accuracy based whether the model F can accurately classify data points when presented with only a single signal feature f. which indeed generalizes the notion of weight-feature correlation (wirr f) to general non-linear models and non-linear featurrs.
Now, 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 (d))y(d)/n) iterations, with high probability over the sampled training dataset 2, the model (()) satisfies:
Standard training is perfect: for all (X,y) E 2, all (4] F (x).
Non-robust features are learned: P(X
argmaxxE|j F. (T) (X,) # サ = (1).
Standard test accuracy is good: P(X. argmax F!
((T) (X) + y/ = o())
Robust test accuracy is bad: for any given data (X, v). using the following perturbation A == (δ1, 82,..., 5p), where 6, - -B, + tey for p E JNR; ó, == 0 for TR. and yf is randomly chosen from [k]] \ {u} (which does not depend on the model F(T) and is illustrated in Figure 2), we have
P ((X,))~D argmax F. (T)
A(X, w)) {4) = 1
7

---

Published as a conference paper at ICLR 2025
Theorem 4.3 states that standard training of neural network achieves good standard aceuracy but poor robust performance. This is due to the dominance of non-robust feature learning during the training dynamics. Moreover, we notice that perturbation based on non-robust features is sufficient to confuse the network. This implies that adversarial examples may stem from non-robust features, which could also help explain the transferability of adversarial attacks (Papernot et al., 2016).
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 training dataset Z, the model F(T) satisfies:
((poly(d)/n)) iterations, with high probability over the sampled
Adversarial training is perfect: for all (X, Z and all perturbation A satisfying A & c, all E (k]Mu)) F
(X + A) > ( (X + A)
Robust features are learned: P(X argmax F, F(T) (Xy) # y o(1).
Robust test accuracy good:
P ((xx))
3A E
(R=))
P
s.t. | S G,rgmax F (!T) (X + A)
+
v = (11)
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.
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. on 0, w.h.p. Op >>>>>>>>>>>> 2 3p. Z D).
By analyzing gradient descent dynamics of the model F. we know that there exists time-varians coefficient sequences (A()) and (Bir) such that, for any pair (i, E [k] [m], holds that w!! (t) u, BB(0 vg. Then, we focus on dynamics of these two coefficient sequences.
5.1 LEARNING PROCESS ANALYSIS FOR STANDARD TRAINING
For standard training, by denoting logit, Dogit,(F,a. (F Σsem SxT we have the following lemma.
((())
Lemma 5.1 (Feature Learning Iteration for Standard Training). During standard training, for any
time 2 O and pair (i,r) E [k) [m), the two sequences {4) and (B(2) satisfy:
(111) (10 + VED, D..i
(1 logit,(F()) X)) Σ ReLU
(ap, (.r ap
(1)
PEJA
B((+1) = [3(1] + g
(1 logit,
X)) peJun
Σ
ReLU
(g, Bp
Approximation Near Initialization. At the start of training, due to our random initialization, i.c.. wir ~ (0, Ia/ (d)y.d)), we have a constant loss derivative, namely 1 - logit, (F((,,(F(),, (F() = O(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 EE Epee 89
E [[EpEs. ag), which implies that the non-robust feature learning maX+e[m] (.O) increases more rapidly than the robust feature learning max+e[m] 1,r. Moreover, by applying Tensor Power Method Lemma (Allen-Zine Zhu & Li, 2023a), we know that maxre(m) Bi²) attains an order of é(1), while maxre[m] A still maintains 5(1 o(1)errder. Afterward, the loss derivative approaches zero (i.e. 1 logit, (F()) x) o(1)), and the network ultimately converges within the linear region of the ReL.U.
8

---

Published as a conference paper at ICLR 2025
S0d Train
Than
Train
AdV Trais
Vantard
Kobest Text kct
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.
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 To 0 such that, for any early time 0 s To and pair ri, E
[k] x [m], the two sequences { and {B satisfy:
A A 0(1) (A())
4-1
og
min
< O(7) E (4
Dp
PEJA
dE(ml
B((+1) se _. + O(n) (B!0)
(1)) Σ (B())))) 3p
E
Σ PEJAR
min
sE(m
Phase I: First, Network Partially Learns Non-Robust Features. At the beginning, due to our small initialization, we know all feature learning coefficients A!.) B10 = o(1), which suggests that the total feature learning EeE[m]] (A!!)) and EeE()] (B!!)) are sufficiently small. Then, the feature learning process is similar to standard training until the non-robust feature learning becomes large.
Phase I:: Next, Robust Feature Learning Starts Inereasing. Once the total non-robust feature learning Em][m)] (B!))²
? attains an order of G(ū-1). 1), it is known that the non-robust feature learning will stop, due to _ 3 2 and é( Eeeim| (D( O. In contrast, the robust feature learning continues to increase since always holds that min { o Ô Exe(m] (4())) 2 1- o 2(1). Thus, the robust feature learning will increase over the non-robust feature learning finally, and the network converges to robust regime, i.e. max,e[m] (17) >> maxre(m) B(T) for large T.
EXPERIMENTS
6.1 SIMULATIONS ON SYNTHETIC DATA
Experiment Settings. We first perform numerical experiments on synthetic data verify our theoretical results. Here, our synthetic data is generated according to Definition 2.2. We choose the hyperparameters as:
2, 100, P 16.g = = 3, 1,e 1.2, N 100, m 100, Tu = 0.010 J. = 0.1, = 0.1, fj 10 T = 1000, and [Jxl = 1, JNw 15. ap = 2, 8, = 1 for each (X, y) 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: max/e|m] ( (w:, (t)//l//u,l2.+ = 1,2 (robust feature learning), and max,e[m] (wr,r. n.)) /|l l|,, = 1,2 (non-robust feature learning). We calculate the robust test accuracy by the standard PGD attack.
The numerical results are reported in Figure 3. We observe that, in standard training, non-robust feature learning dominates during training process. There exists 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.
Experiment Results.

---

Published as a conference paper at ICLR 2025
Std Training
Accuracy R.
Accuracy
Accuracy
-4-
Non robust Reature Leaming Robust festure Leariing
52
Non robust Feature Loarnnng
Non robust Feoture Loorning
Robund Feature Leurning
Robual Fueture Learning
Epoch
Epoch
Epach
Adv Training
Accuracy
Accuracy
Accuracy
wa Joall" "My "
Non ritust Feature Leaming Robust Feature Learning
22-
Non mbust Feature Leaming
Non-robust Festure Learning
Rooust Featura Leaming
Robust Feature Leaming
05
15 00
Epoch
Epoch
MNIST
CIFARIO
SVHN
Figure 4: Feature learning process on real-image datasets. Top row: feature learning accuracy during standard training. Bottom row: feature learning accuracy during adversarial training.
6.2 EXPERIMENTS ON REAL-WORLD DATASETS
Experiment Settings. Instead of weight-feature correlation used synthetic data setting, here on MNIST, CIFARIO and SVHN datasets, apply feature learning accuracy in Definition 1 to measure non-robust/robust feature learning during training dynamics. Similar to the method proposed in Ilyas et al. (2019), we reconstruct datasets DRe. Dg as the feature representative distributions by a one-to-one mapping X + X. Specifically, we solve the following optimization problem to derive X": min [G(()- G(X)] where X E 'D is the target data point, and G is the mapping from input X to the representation layer for network learners. When G chosen from a standard/adversarrial trained network, we derive the non-robust/robust representative dataset DDx Then, we run the standard training and adversarial training algorithms and record the dynamics of feature learning accuracy w.r.t. DNR and DR. For MNIST, we choose ResNet18 8 and eerperturbationn with radius 0.3, and we run algorithms for 30 iterations. For CIFARIO and SVHN, we choose WideResNet-34-UU and -ertturrubiiion with radius 8/ 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 theoretical results in Section 4.
CONCLUSION, LIMITATIONS AND FUTURE WORKS
In this paper, we provide 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. However, we also believe that our results can be significantly improved if we build on a more realistic setup. For example, an important future direction is extend our theoretical analysis deep neural networks. Another interesting direction is to extend our theoretical analysis method to adversarial training based on multi-step gradient ascent algorithms, such as PGD.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Binghui Li is supported by the Elite Ph.D. Program in Applied Mathematics for PhD Candidates in Peking University. We thank Yuhui Li, Zhongao Wang, Zixin Wen, Zean Xu and Qinhan Yu for helpful discussions and anonymous reviewers for their valuable suggestions.
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, 1lge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprini www.xv:333.087722 2023.
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. In 202/ IEEE 62nd Anmual Symposium on Foundations of Computer Science (FOCS), pp. 977-988. IEEE, 2022.
Zeyuan Allen-Zhree Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self- distillation in deep learning. In The Eleventh International Conference on Learning Representations, 2023a. URL ht https: //pppeeevvv review. net/ forum? d=0uff2u9 FXGA.
Zeyuan Allen-Zht and Yuanzhi Li. Backward feature correction: How deep learning performs deep (hierarchical) learning. In The Thirty Sixth Annual Conference on Learning Theory, pp. 1599-4598.
PMLR, 2023b.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019.
Peter Bartlett, Sébastien Bubeck, and Yeshwanth Cherapanamjeri. Adversarial examples in multi- layer random relu networks. Advances in Neural Information Processing Systems, 34:9241-9253 2021.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šmdić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Machine Learning and Knowledge Discovery Databases: European Conference, ECML. PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III 13, pp. 387-402. Springer, 2013.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot leamners Advances in neural information processing systems, 33:1877-1901, 2020. 2020.
Sébastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. Advances in Neural Information Processing Systems, 34:28811-288222 2021.
Sébastien Bubeck, Yeshwanth Cherapanamjeri, Gauthier Gidel, and Remi Tachet des Combes. A single gradient step finds adversarial examples on random two-layers neural networks. Advances in Neural Information Processing Systems, 14:100011-1099 2021a.
Sébastien Bubeck, Yuanzhi Li, and Dheeraj M Nagaraj. A law of robustness for two-layers neural networks. In Conference on Learning Theory, pp. 804-820. PMLR, 2021b.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp), pp. 39-57. leee, 2017.
Jinghui Chen, Yuan Cao, and Quanquan Gu. Benign overfitting in adversarially robust linear classification. In Uncertainty in Artificial Intelligence, pp. 313-323 PMLR, 2023.
Siyu Chen, Heejune Sheen, Tianhao Wang, and Zhuoran Yang. Training dynamics of multi-heas softmax attention for in-context learning: Emergence, convergence, and optimality, arXiv preprint arXiv:2402. /9442, 2024.
11

---

Published as a conference paper at ICLR 2025
Zixiang Chen, Yihe Deng, Yue Wu, Quanquan Gu, and Yuanzhi Li. Towards understanding the mixture-of mixture-of-expert of-eeterts layer in deep learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https: /eppereeevveeeeeeeeeeeeeeeeeeeee ew net/ / forum? d= zugDnQV.
Muthu Chidambaram, Xiang Wang, Chenwei Wu, and Rong Ge. Provably learning diverse features in multi-view data with midpoint mixup. In International Conference on Machine Learning, pp.
3663.5599. PMLR, 2023.
Amit Daniely and Hadas Shacham. Most relu networks suffer from \.ell2 adversarial perturbations. Advances in Neural Information Processing Systems, 33:6629 0236629-666,, 2020.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021. URL httpp:://ppettte /ppnnreeee......ee net/ / forum? iid dodd--icbbee ciNTTyyTTy.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp. 1675-1685. PMLR, 2019a.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterizze neural networks. In International Conference on Learning Representations, 2019b. URL httpt:tt//// /tapp::///peeee http://ppppeeeeeeee/eee/eee/eeep http://iwwweeeettteeeeeeeeeeee id- S1eK33110.
Spencer Frei, Gal Vardi, Peter Bartlett, and Nati Srebro. The double-edged sword of implicit bias: Generalization vs. robustness in relu networks. Advances in Neural Information Processing Systems, 36, 2024.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256. JMLR Workshop and Conference Proceedings, 2010.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and hamnessing adversarial examples. arXiv preprint arXiv:1412.6577 2014.
Sven Gowal, Jonathan Uesato, Chongli Qin, Po-Sen Huang. Timothy Mann, and Pushmeet Kohli. An alternative surrogate loss for pgd-based adversarial testing. arXiv preprint 1rXiv:191.003330 2019.
Sicong Han, Chenhao Lin, Chao Shen, Qian Wang, and Xiaohong Guan. Interpreting adversarial examples in deep learning: A review. ACM Computing Surveys, 55(1s)):11338 2023.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. Advances in neural information processing systems, 32, 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Adel Javanmard and Mahdi Soltanolkotabi. Precise statistical analysis of classification accuracies for adversarial training. The Annals of Statistics, 50(4):2127-2156, 2022.
Samy Jelassi, Michael Sander, and Yuanzhi Li. Vision transformers provably learn spatial structure. Advances in Neural Information Processing Systems, 35:37822-37836 2022.
Jacob Devlin Ming-Woi Wei Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of naacL-HLT, volume 1, pp. 2, 2019.
12

---

Published as a conference paper at ICLR 2025
Junho Kim, Byung- Kwan Lee, and Yong Man Ro. Distilling robust and non-robust features in adversarial examples by information bottleneck. Advances in Neural Information Processing Systems, 34:17148-1787 17159, 2021.
Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yee Lo, et al. Segment anything. In Proceedings of the IEEE/CVE International Conference on Computer Vision, pp. 4015-4026, 2023.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolu- tional neural networks. Advances in neural information processing systems, 25, 2012.
Binghui Li and Yuanzhi Li. Why clean generalization and robust overfitting both happen in adversarial training. arXiv preprint arXiv:2306.01271, 2023.
Binghui Li, Jikai Jin, Han Zhong, John Hopcroft, and Liwei Wang. Why robust generalization in deep learning is difficult: Perspective expressive power. Advances in Neural Information Processing Systems, 35:4370-4366 2022.
Binghui Li, Zhixuan Pan, Kaifeng Lyu, and Jian Li. Feature averaging: An implicit bias of gradient descent leading non-robustness in neural networks. arXiv preprint arXiv:2410.10322, 2024.
Yan Li, Ethan Xang Huan Xu, and Tuo Zhao. Implicit bias of gradient descent based adversarial training on separable data. In International Conference on Learning Representations, 2020. URL
net forum? id- HKgTTh4FDB.
Miao Lu, Beining Wu, Xiaodong Yang, and Difan Zou. Benign oscillation of stochastic gradient descent with large learning rate. In The Twelfth International Conference on Learning Representa- tions, 2024. URL http:::t///e htttp:://ppeereeeee
net / forum? id-wYmwN3 sQpG.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant adversarial attacks. In International Conference on Learn- ing Representations, 2018. URL ht http//pennvveeeeeeeeee n forum J
Andrea Montanari and Yuchen Wu. Adversarial examples in random neural networks with general activations. Mathematical Statistics and Learning. 6(1):143-200 2023.
Long Ouyang, Jeffrey Wu, Xu Jiang. Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744, 2022.
Tianyu Pang, Min Lin, Xiao Yang, Jun Zhu, and Shuicheng Yan. Robustness and accuracy could be reconcilable by (proper) definition. In International Conference on Machine Learning, pp. 17258-17277. PMLR, 2022.
Nicolas Papernot, Patrick McDaniel, and Ian Goodfellow. Transferability in machine learning: from phenomena to black-box attacks using adversarial samples. arXiv preprint arXiv: 1.V::1605.0727,, 2016.
Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! Advances in Neural Information Processing Systems, 32, 2019.
Gaurang Sriramanan, Sravanti Addepalli, Arya Baburaj, al. Guided adversarial attack for evaluating and enhancing adversarial defenses. Advances in Neural Information Processing Systems, 33: 20297-20308, 2020.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint 131i: 2013.
Nikolaos Tsilivis and Julia Kempe. What can the neural tangent kernel tell us about adversarial robustness? Advances in Neural Information Processing Systems, 35:181 16-18130, 2022.
13

---

Published as a conference paper at ICLR 2025
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Tumne,, and Aleksander Madry. Ro- bustness may be odds with accuracy. In International Conference on Learning Representations, 2019. URL https:
Zekai Wang, Tianyu Pang, Chao Du, Min Lin, Weiwei Liu, and Shuicheng Yan. Better diffusion models further improve adversarial training. In International Conference on Machine Learning, pp. 36246-362222 362663 PMLR, 2023.
Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self-supervised contrastive learning. In International Conference Machine Learning, pp. 11112-11122. PMLR, 2021.
Yao- Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Russ R Salakhutdinov, and Kamalika Chaud- huri. A closer look at accuracy robustness. Advances in neural information processing systems, 33:8588-8601, 2020.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint 4rXiv:1605.07146. 2016.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference machine learning, pp. 7472-7482. PMLR, 2019.
14

---

Published as a conference paper at ICLR 2025
CONTENTS
1
Introduction
1.1
Related Works
2
Problem Setup
2.1
Notations
2.2
Data Distribution
2.3
Network Learner
2.4
Standard Training
2.5
Adversarial Training
3
Warm Up: There Exist both Non-Robust and Robust Global Minima
4
Main Results
5
Technique Overview: Learning Process Analysis
5.1
Learning Process Analysis for Standard Training
5.2
Learning Process Analysis for Adversarial Training
Experiments
6.1 Simulations Synthetic Data
6.2 Experiments on Real-world Datasets
10
7 Conclusion, Limitations and Future Works
10
A Additional Experiment Results about Real-Image Datasets
17
A.I Feature Learning Process on Real-world Datasets
17
A.2 Targeted Adversarial Attack on Real-world Datasets
18
Preliminary for Proof Technique
19
B.I Notations
19
B.2 Preliminary Lemmas
19
B.3 More Detailed Data Assumption
19
Detailed Proofs for Section 3
21
C.I Proof of Proposition
C.2 Proof of Proposition 3.2
22
Analyzing Learning Process via Weight-Feature Correlations
................................
22
Detailed Proof for Section 5
23
D.I Proof for Standard Training
23
D.1.1
Weight Decomposition
23
15

---

Published as a conference paper at ICLR 2025
D.1.2
Logit Approximation
25
D.1.3
Non-diagonal Terms are Small
26
D.1.4
Analysis of Feature Learning Process for Standard Training
26
D.1.5
Proof of Theorem D.1
28
D.2
Proof for Adversarial Training
29
D.2.1
Weight Decomposition
29
D.2.2
Time-variant Adversarial Examples
30
D.2.3
Logit Approximation Adversarial Examples
D.2.4
Non-diagonal Terms are Small
31
D.2.5
Analysis of Feature Learning Process for Adversarial Training
32
D.2.6 Proof of Theorem D.15
33
Proof for Section 4
E.1
Proof for Standard Training
34
E.1.1
Weight Decomposition for Standard Training
................................
34
E.1.2
Noise Terms are Small
34
E.1.3
Feature Learning for Standard Training
................................
35
E.2
Proof for Adversarial Training
35
E.2.1
Weight Decomposition for Adversarial Training
35
E.2.2
Noise Terms are Small
35
E.2.3
Feature Learning for Adversarial Training
36
16

---

Published as a conference paper at ICLR 2025
A
ADDITIONAL EXPERIMENT RESULTS ABOUT REAL-IMAGE DATASETS
A.1
FEATURE LEARNING PROCESS ON REAL-WORLD DATASETS
Std Training
Accuracy
Accuracy -..
Accuracy
Non-rbbutt Feature Leariing Robus fear teaming
Ron-robust Feature Learning Robunt Feature leaming
Non robust Feature ning Robust Festure learning ab
20
ale 25
Epoch
Epoch
Epoch
Adv Training
Accuracy
Accuracy
Mon-rabust Teature Learning
Non-mbust Teature Leamiin
haneeobunn Feelure Learting
Robust Feature Leariing
Rocust Feature Leaming
Robust Feature Leaming
15
15
Epoch
Epoch
Epoch
MNIST
CIFARIO
SVHN
Figure 5: Feature learning process on real-image datasets. Top row: feature learning accuracy during standard training. Bottom row: feature learning accuracy during adversarial training.
Table I: Feature learning results on real-world datasets
Test Accuracy
Feature Learning
Dataset
Algorithm
Standard
Robust
Non-Robust
Robust
Std Train
99.56
0.04
88.11 18
44.61
MNIST
Adv Train
99.41
94.43
39.49
69.19
Std Train
95.74
0.00
91.79
61.26
CIFAR10
Adv Train
86.28
45.13
10.88
67.88
Std Train
96.84
0.16
73.91
65.38
SVHN
Adv Train
91.99
58.55
35.50
77.04
Experiment Settings. Instead of weight-feature correlation used in synthetic data setting, here MNIST, CIFARIO and SVHN datasets, we apply feature learning accuracy Definition 1 to measure non-robust/robust feature learning during training dynamics.
Definition A.1 (Feature Learning Accuracy). For given feature subset H. F (F is all feature set as the same as Definition 2.1). H-extended feature representative distribution Dix and classifier model F, we define the feature learning accuracy as I ((Xx,)))DD argmax,e(N) F.(X,) - y where Xf H) is the feetendee representative and y is the label which feature f corresponds to.
Remark A.2. We define feature learning accuracy based on whether the model F accurately classify data points when presented with only a single signal feature f. which indeed generalizes the notion of weight-feature correlation (wirr f) to general non-linear models and non-linear features.
Similar to the method proposed in Ilyas et al. (2019), we reconstruct datasets D Dr e as the feature representative distributions by a one-to-one mapping X + X Specifically, we solve the following optimization problem to derive X:
min ||G(X) G(X)|
17

---

Published as a conference paper at ICLR 2025
where X E D is the target data point, and G is the mapping from input X to the representation layer for network learners. When G chosen from a standard/aaveersariil-raaa non-robust/robust representative dataset DNR DR. Then, run the standard training and adversarial training algorithms and record the dynamics of feature learning accuracy w.r.t. DNR and DR. For MNIST, we choose R (He et al., 2016) and & -errturrbation with radius 0.3, and we run algorithms for 30 iterations. For CIFAR 10 and SVHN, we choose WideResNet-344 (Zagoruyko & Komodakis, 2016) as network architecture and fsx -errturrbatii with radius 8/255 and run algorithms for 200 iterations by using a single NVIDIA RTX 4090 GPU.
network, we derive the
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.
Experiment Results.
A.2 TARGETED ADVERSARIAL ATTACK ON REAL-WORLD DATASETS
Table 2: Targeted attack success rates on CIFARIO
Source + Target
Model
Attack
Cat + Dog
Dog - Cat
Car + Plane
Plane - Car
NRF-PGD
71.41 + 1.17
80.36 + 0.28
54.08 + 0.99
76.74 + 0.77
Std Trained
RF-PGD
11.30 0.55
9.58 + 0.58
1.24 + 0.10
2.63 + 0.13
NRF-PGD
9.60 + 0.18
15.16 0.23
0.34 + 0.04
0.40 0.00 1.96 + 0.13
Adv Trained
RF-GGD
19.38 + 0.29
26.00 + 0.67
2.64 + 0.18
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 (-)(.)) ()) and G.tt(-) ) to denote the mapping from input X to the representation layer for standard-trained network and adversarially-trained network, respectively. Similar to the previous section and llyas et al. (2019), we can regard G-u(-) and (-) 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 A:
min > Se | A)
(X')ll,
where X is the original image from the source class, X' is random image sampled from the target class, and e is the perturbation radius. Similarly, we can define RF-PGD by using PGD method to solve the following optmization problem over the perturbation A:
min MainAAllo Se [G + +) -Gad (X) 1|2.
Then, we evaluate the performance of the two attack methods on the standard-trained network Fns( and the adversarially-trained network (-) (they are different from the reference networks from which we choose our Gaa(-) and G=v(-)). For CIRAFIO dataset, we apply WideResNet-34-10 (Zagoruyko & Komodakis, 2016) as our learner networks, and choose the typical perturbation radius c 8/255 for -attakk. And all experiments are repeated over 5 random seeds.
Experiment Results. We select two pairs ((cat, dog) and (car, plane)) 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 7 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 aeersarially-ttrinee 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.
18

---

Published as a conference paper at ICLR 2025
B PRELIMINARY FOR PROOF TECHNIQUE
B.I NOTATIONS
Throughout this work, we use letters for scalars and bold letters for vectors. For any given two sequences {An JaJnng and {Bn J n- we denote A, - (B,) if there exist some absolute constant C > and N1 > such that A S C₁ [B.] for all n 2 Ni. Similarly, we denote A. = 52 (B,) there exist C2 > 0 and N2 0 such that |An C2 [ for all
N2. We say A, θ (B,) if A = 0 (B,) and An = (B,)) both holds. We use O()). (2))) and ( to hide logarithmic factors in these notations respectively. Moreover, denote A, poly (B,)) if An = (B,) for some positive constant K, and A,, polylog (B,) if B,, poly (log (Bn)). We say A. of ((B.,) (or
An < Bn or Bn > An) if for arbitrary positive constant C3 > O, there exists N23 > 0 such that |An C3 Bal for all N3. And we also use A, Ri Bn denote A, B, o(1)
B.2 PRELIMINARY LEMMAS
Lemma B.I. Let X = (X,,,..,,x)). where X; ~ NO0, 1) are ii.dd, then we have
P |1x 2 (2log(2n) +1| S exp (-t//2) (t 0), and
P |Ix S / (2log(22) -0 S exp
(2 2og(())))()) where we can take =
6/2
loglog(n) for large such that this probability is small.
Lemma B.2 (Tensor Power Method, from Allen-Zhu Li (2023a)). Let q 2 be a constant and To: Uo o(1). ).).)..)))) Let (5t, Ut Vih220 be two positive sequences updated as
T++1 2 xt C for some C. (1), and
Ut+1 S + SSSCtt for some constant $ = ((1.
where 7 = 0(1 pdly for a sufficiently large polynomial d. Suppose To 2 For every A O(1), letting Te be the first iteration such that
S0S+- 1 (1+0 polylogid)
J; 2 A, must have that
yr, = (yo polylog(d)
B.3 MORE DETAILED DATA ASSUMPTION
Assumption B.3 (Choice of Hyperparameters), We assume that:
d = poly(k) > 2k, p= +(),,, a a: inf ap. = inf 3pp
1
σ0 Vd a, 0(1), a><> 8,
m = polylog(d),
N poly(d,, q= T 3, 0 polylog(d)
1 poly(d)
where co E 10, any positive constant.
Discussion of Hyperparameter Choices. While the choices of these hyperparameters are not unique, we make specific selections above for the sake 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 = poly(k) (k) for a suitably large polynomial) to ensure that all 2k features be orthogonal within the space IRd. The number of patches P is held constant. The conditions a > e > 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
19

---

Published as a conference paper at ICLR 2025
= polylog(d) to achieve mild over wwr-parraetteiizationn for efficient optimization. Furthermore, the adversarial learning rate rj is significantly larger than the weight learning rate 7), aligning with practical implementations (Carlini & Wagner, 2017; Gowal et al., 2019; Sriramanan et al., 2020).
20

---

Published as a conference paper at ICLR 2025
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 more detailed discussion about it.
C.I PROOF OF PROPOSITION 3.1
Theorem C.1 (Restatement of Proposition 3.1). We consider the special case when m = 1 and Wi,1 = -yo,, where y > O is scale coefficient. Then, it holds that the stan- dard empirical risk satisfies limy-xx FCE(F) o(1), but the adversarial test error satisfies
1im P ((X))D
=A E (IR")*
P s.L. | S aegg R(( A) =1 =1-0(1) o(1)
Proof Sketch. For given data point (X. y) E E and sufficiently large we calculate the
margin and derive w.h.p. (X) >> ( ) Vj [k]] {y), which implies FcF(F) - o(1) However, if we choose the perturbation Á(X, y) = (6), 82..... 8p), where åp := --0--,,,,
3, + evn for p JAR; 6, = 0 for p E JR. and y/ is randomly chosen from [A:] \ {v), we know w.h.p. Fe (X A > ( A), Vj [k] \ {B'), which suggests the adversarial test error is 1 o(1).
Now, we give the detailed proof as follows.
Proof. For given data point (X, y) E Z and sufficiently large y, calculate the margin follows. With probability 1 - (11, it holds that
Fx(x)= Σ ReLU a, Ep)) +
Rev Ep))
PETA
pe
= Σ
(e Ep)))
Σ
ReLU(r(3p + (wy Ep)))
PEJa
peJ.R
Σ Re, ((on)) 2 20
Σ Bp
pEJux
PEJuR
And for any j E [P] {y}, we have
F2(X) = Σ ReLU((rO,, apt,, + Ep)) +
Σ ( + Ep)
PEJx
PEJNu
(ReT.U()((rn) S 70(a))-
Since EpeJm Bp >> on we know lim Lcx =
Let (XX.)) (01, . 5p), where 5p == -Bp + cvy for JNR: 5p : 0 for p E Ja. and y/ is randomly chosen from [k] \ {v). then we derive that, with probability o(1), satisfies that
(X + A(X v)) = Σ ReLU ap + Ep)) + Σ
ReLUU(r cuyy + Ep))
PEJ
DE
Σ
2(a)))))
peJuR
However, for other class j E [A]] \ {v'}, we know
Fx + A(X, u)) = Σ ReLU((ro, ap Ex)) +
Σ
ReLU((rU),eoy + Ep))
pE
Σ
ReL,U 70(on).
PE[P]
Due to >> on. we know Fx + A(X v)) > F + A(X vj E [K] {
Thus, we have
3A (Rd)" P s.t. | arggaa F(X + A) { = =1-o
lim P P(x (DD 700
21

---

Published as a conference paper at ICLR 2025
C.2 PROOF OF PROPOSITION 3.2
Theorem C.2 (Restatement of Proposition 3.2). We consider the special case when m 1 and Wi,1 yyu, where ? > 0 is a scale coefficient. Then, it holds that the stan- dard empirical risk satisfies limy-oo LCE(F) = =(1), and the adversarial test error satisfies
1im P( P(X
A E (RR) s.1. || no S,, e.argaax P(( + A) # = P
+) =(1).
Proof Sketch. For a given data point (X 1) ~ D. sufficiently large y and any perturbation
A E (Rd)² P satisfying | oo S. c, we show that w.h.p. Fy + A) ス >pEE, Op > (0(an)) +
<) 2 (X + A), Vj E [k] {v}, 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 (X,y) ~ D. sufficiently large and any perturbation A (81, ...... , 6p) E (R4) satisfying || e, calculate the perturbed margin as follows. With probability 1 ((1), it holds that
( + A) Σ ReLUU((Y Up E. +p))
E
ReI.U((yu, Bp + Ep + óp))
pEJ+
pEJuv
= Σ
ReLU(r(a, + (u Ep) + (u, 6p)) + Σ
(eLU()(((u,;: En) + (uk .,,))
pE.Jx
pEJaR
ReT.U(((ap-)())) -c) 7
Σ
Op
PEJu
PEJx
And for any j E [P] \ {y}, we have
+((+A)) Σ ((LU, + 8p)) + Σ ReLU + Ep + +8,))
PEJR
PEJ.R
(ReeU()(O((,)) + +c)) x (0(()) + +c).
Since Epech ap (( tG, we know lim Ler (F) o(1) and
lim P(X,)~D 3 E (R²)" s.l. A S S, aragnnax P(( + A) + u) =0(1) 7-000
C.3 ANALYZING LEARNING PROCESS VIA WEIGHT-FEATURE CORRELATIONS
Proposition 3.1 and Proposition 3.2 demonstrate that network is vulnerable adversarial perturba- tions it relies solely on learning non-robust features. Conversely, a network that learns all robust features can achieve state of robustness, In general, by calculating the gradient of empirical loss, seems that the whole weights during gradient-based training will have the following form
Wir A, B, + Noise,
where Ai,,, Bi, > represent the coefficients for learning robust and non-robust features, re- spectively, and the 'Noise' term encompasses elements learned from other non-diagonal features Uj 0, # i), as well as random noise Ep.
Therefore, we know that the network learns the i-th class if and only if either Ai, B is sufficiently large. However, to robustly learn the i-th class, the network must primarily learn the robust feature u, rather than the non-robust feature v, which motivates us 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.
22

---

Published as a conference paper at ICLR 2025
D DETAILED PROOF FOR SECTION 5
In this section, we provide detailed proof for Section 5, considering the simplified setting where the data is noiseless and we 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 can demonstrate that noise terms always sufficiently small under setting, 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 Con- verges to Non-robust Global Minima). For sufficiently large d, suppose train the model ing the standard training starting with population risk from the random initialization, then after T = O (poly(d))/ iterations, with probability 1 o(1) the randomness of weight initialization. the model F(T) satisfies:
Non-robust features are learned: P(X, P(Xy argmax,e(M
F.
(Xx) + =
Standard test accuracy good: ()x.D)>D argmax,e(() F. ((TT
+ y
0.
Robust test accuracy is bad: for any given data (X, using the following perturbation A y) (61,82..... .2....,5pp. where 6p :-= -Bp + tuy for p E INRi 8p f p JR. and of is randomly chosen from [R) \ {y} (which does not depend the model F(T) and is illustrated in Figure 2), we have
P P(X argmax F E!T) (X A(X.
+ =1
Proof Sketch. To prove Theorem D.I, study the feature learning process of standard training by decomposing the weights of the neural network into linear combination of all features (f E F). We then demonstrate that non-diagonal weight- feature correlations (i.e., (W.rr: u,) and (Warrs 02), where j / i) are always smaller than their diagonal counterparts (i.e., (wirr us) and (wirr vt)). Next, by applying the Tensor Power Method Lemma (Allen-Zhu & Li, 2023a), 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.
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 2 0, each neuron
Wirr (i,rr) [k] x [m]), we have
w p w (0) +
B(0 diagonal correlations
Elo Woryy ty D Pyr
orthogonal inis
non-diagonal correlations
where ( ( (it)) and ( are some time variant coefficients, and P := Ia Ef projects vector into all features f = F's orthogonal complementary space.
Proof. Notice that the following update iteration:
w (1+1)
w (x()D)
Vw,, Lcs
x,))
= w (1) + 1B
-1o-i)-logit,,
- xx)
Σ PE[P
ReLU (f mp)) xxp))
23

---

Published as a conference paper at ICLR 2025
Due to the definition of patch data Tp, 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 F and each i [k]. with probability 1 o(1), we have
m/ (w) f) = ((log(m)/VD)
Proof. Due to the definition of all features and random initialization wi, NO ŞZz), we know that, for each i E [Kt] f E F, it holds that (w f) are 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 2 O and pair (i, E [k] x [m],y E [k] \ {i}, the two sequences (A (B()),
(o } and (D satisfy:
(141)
A19) ir + D..
(1 - logit, X)) Σ ReLU (op-1.0)
(1)
Op
PEJa
B(tt1) (0()) + y Ds..
(1 logit, (F(0,x) ,))
Σ
ReLU (3, 32
pēJuu
c( C.. + I.D.D Da.
Logit;(F(t), ())(
Σ
ReLU (ap0
app
PeJe
D(++1) = 1 ira k.n.
+ HDDS
logit, (F(1), X)
Σ
ReLU
(8pD!.)))
k 3p
PE.JAR
Proof.
Notice that we have the following update iteration:
(+O==) - logit, x))
w WHt 1++1) = w + 1
Σ
ReLU ((w x xpp)
pE[r)
Then, project the iteration above onto the directions of features to derive
.f) = ( +n WDND (Im==) (F()), xx)
(wer (++1)
Σ
ReLU ((w)) xx)) (Zpp f)
PE[P]
where feature vectorf E F.
For feature f E {u,, e (diagonal features), according to the definition of patch data Zp, we know that (xp, f) is not zero if and only if data point (X, y) belongs to class i. Thus, we derive
(041)) (1 "
(1 (F()),((()),, X))
Σ ReLU (ap ap
PEJa
(((++1) Bl00) + + EE Do.
(1 logit, (F(1), x))
Σ peJhu
ReLU
(8, Bp
For feature f E (uz, 1y (E())))))) (non-diagonal features), according the definition of patch data Tp, we know that (Ip, f) is not zero if and only if data point (X, belongs class j. Thus, derive
c((-1)
irr = (() + EED
logit, (F(t),
(F(t), ((())x X) Σ ReLt (apolt))) Op
i.r.y
k
PEdo
((+11)
(1)
iry + DDD
logit; (F(t), X) E
ReLU (B,D 8p
pEJva
24

---

Published as a conference paper at ICLR 2025
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 rate proportional to O (zz) ). where с reflects the order of the diagonal function
output F (X). First, we give the following diagonal logit approximation lemma.
Lemma D.5 (Diagonal Logit Approximation). For any data point (X, v) D. suppose that (M [ Ollog(d) and max.eMMrrelmlleeMMMt C O(log(d) / Vd) and re D (log(d)) /d), and (X) Z clog(d) for some 0, then we have the following approximation of diagonal logit:
(0(1)
jifc 0;
1 1 logit, (F(t), x)= l
10
.ffc O.
Proof. By assumptions, we know that all of the off-diagonal correlations are at most (log(d)) / /vd). Thus, we have, for each class E [k] \ {v).
(X) Σ
Σ
ReLU (ww,,, Hp))
rE[m) pE[r)
at Σ Σ
909-1 ",r.y)"
(C(()
+
Σ
909-1 y,r.y) )
3g (D
(1)
rE[m] PEJe
rE(m] PEJ
S m
a 904-1
(maxre(m)
(((t)
19+ + Σ
3 (max, [m]] 10 )
909-1
PEJR
PEJAR
s ((1/dt),
which implies that
exp(E("(() (X)) S 1 O(L/dt),
where we use the inequality e" < 1 11 x² for S 1.
Now by the assumption that (x 2 c clog(d), we know
exp(F,(2)
1 - logit, (F(() x) 1
exp(F,(X3 (X)) + Ei (X))
de
1
de (k: 1) + o(1) 011/8))
Then, we give the following non-diagonal logit approximation lemma. Lemma D.6 (Non-diagonal Logit Approximation). For any data point (X, y) ~ D, suppose
that ma ((O) O(lo(dd) and [ax c O(log(d)/ Vd) and
max (1) ( Olog(d)) and Fy(X) (X) 2 elog(d) for some 2 0, then we have the following approximation of non-diagonal logit, for + y:
(0(kk) logit (F(1,, X): 10 +
ifc = 0; if > 0.
Proof. Similar to the diagonal case, we have, for each class
[K] (v).
(x) < Ö(1/a3).
25

---

Published as a conference paper at ICLR 2025
Then, know
exp(F) (X))
logit,(Fi) ()) ())
ex)(Ff(XX)) exp(F((X) + -iryy exp(F;(X)) +xxxxxxxp((((((
1+ (11/8) = ((1/d))
de + (k -)
D.1.3 NON-DIAGONAL TERMS ARE SMALL
Then, 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.ty D sry ((,,r) E [k] x [m],y # i) satisfy that max C.. O(maxye(m) Clpy) and max,e(m) D(0) =
s,r.y
(mmaxe[[m] D.rry) for each E [k], y E [A] \ {i}-
Proof. Notice that, for each pair E [M], [m], y E [K] \ {i), we have
iry irryy
o(442) (1())
+
a R Pa..
logit, (F(1) X) Σ ReLÚ (apc100) ap
PEJa
((++1) ( DEDD...
logit, X) Σ
ReLU
(B, ap
Since logit, , (F(t), X) is negative and ReLU (2) for 2 can prove the above lemma by induction.
D.1.4 ANALYSIS OF FEATURE LEARNING PROCESS FOR STANDARD TRAINING
Now, we present an enhanced analysis the feature learning process for standard training scenarios. In fact, the learning process can be conceptualized 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 ReLU function. Subsequently, once the diagonal outputs (X) have scaled to an order of log(d), we demonstrate that the increase all weight-feature correlations arrested due to the diminishing impact of small logits.
Stage I: Almost neurons lie within the polynomial part of activation ReLU.
Lemma D.8. During standard training, there exists some time threshold To > 0 such that, for any early time 0 < t To and pair (i.r) E [k] [m]), the two sequences { and (B. satisfy:
A((11) A!0 + (()) (4!9)
9-1
E
Σ
0
PEJ
B(H B + (()) (B(0)
E
Σ
67
JN.
Proof. According to Lemma D.4, know that, for early time f, it holds that
]
1 (04111 = A + LEDS..... D... (1 logit, (()), X))
Σ ReLU (ap-110) app
PeJn
B((+1) B DEDD
(1 logit, (1) X))
Σ ReLU (gr Br
peIn
And also holds that which implies that the activation is within polynomial part now. Combined with Lemma D.5, we derive the lemma above.
( 0 1.r 3y (00 < 0
26

---

Published as a conference paper at ICLR 2025
Now, by applying Tensor Power Method Lemma B.2, can derive the following result. Lemma D.9 (Non-robust Feature Learning Dominates at Early Stage). For each y [k]. let (3y)
time Ty denote the first time when maXye[m] B reaches g/3. then have maxre[m] Ay. Oppolylog(d)/Vd)
Proof. We consider the following sequences (xz), {ve} and {Ce}:
E
Σ
og
Jt [[mm [ Ur max A
C. =
Σ
S
PEJA
PEJAR
Σ
8p
PEJuR
Then, we have
1+41 2 v1 + O(n)
Mt+1 S y/ SCn)
And we also know that, with high probability - o(1), we have
E
Σ pm
B
B max+E(m) A
max [m]
1
1 + polylog(d)
S
Σ PEJ..
Where we use Lemma D.3 and Assumption 2.3.
Finally, by directly applying Tensor Power Method Lemma B.2, derive the conclusion.
Stage II: Non-robust feature learning arrives at linear region of activation ReLU.
Lemma D.10. For each E [kc] and (X,y) D, let time Ty denote the first time such that Fy (x) 2 log(d), then T (oly(d) 2 Ty. and we have m|
ATT)) O(polylog(d)//))
Proof. Now, according to Lemma D.9, we know that maxye[m] B > e/B, which manifests that there exists at least one neuron r" E [m]] has been within the linear regime of activation function.
Thus, so long as Fy (x(X)()) < log(d) now, we have
yrr = y.r- + 7 E
(1 logit, (F(t) X) Σ
ReLU (8 )8p
PEJJN
2 y.r- + 0
E
3p
PE
Therefore, we know that we can upper bound Ty by the number of iterations it takes B to grow to (log(d)). Indeed, we clearly have that Ty = (llog(d)/)) poly(d) for some polynomial in d. However, contrast with ((() y.r., for r E [m] (10) we can lower bound the number of iterations takes for (()) grow to by a fixed constant factor from initialization:
A (0)
9-1
TO
(C'
1)
(0)
g
g.rl
which implies that
G1-1
log(d) (TT,). w
T2O
θ
> 0
(0)
71
r
27

---

Published as a conference paper at ICLR 2025
The final remaining task is to show F.y (X) will keep (dpoly(d)) for all polynomial time L.
Lemma D.11. For all time = (ppoly(d) (d)) 2 Ty and each (X,y) ~ D, we have F (X) =
O(log(d)), and maxre[m] Ag. (ppolylog(d)/
Proof. Firstly, we can form the following upper bound for the gradient updates
B((+1) p.r Mir
B(()
+ 7 E
(1 logit, (Fit, X)
Σ
ReLU (8
PEJmu
B(() Vir
17 1: (1- logit, (F(0, x))
2
+
Then, we know that it follows that it takes at least Od ((d())() (d)/)) iterations (since the correlations must grow least log(d)) from T, for (X) to reach 2 log(d). Now Tye) denote the number of iterations takes for (X) to cross clog(d) after crossing (c - logg(d) for the first time. For
< 2, we necessarily have that cyc) ((dT( by induction.
Let us now further define T to be the first iteration at which Fy TTT)(X) 2 f(d) log d for some fdd) (1). However, we have from the above discussion that:
f(d)
de log
Ty 2 ((poly(d)) +
Σ Ω
"1
2 Ω log (d/(a)-1 -
2 (ppoly(d)
So F (X)
Ollo(()) for all O(poly(d)). An identical analysis also works for the robust
feature correlations A so we are done.
D.1.5 PROOF OF THEOREM D.1
Now, we will prove Theorem D.I, which includes the following three parts.
Lemma D.12 (Standard Accuracy is Good). For T (ppoy((d) and each data point (X, D.
with probability o(1), we have F(() (x) F (T) (X), Vi [k] \ {y}.
Proof. According to Lemma D.11, know that, for each data point (X,y) ~ D and time T @(poly(d)/v) with probability 1 o(1), it holds that
(X) = (llo(d)).
However, the non-diagonal outputs can be upper bounded as:
F(X)= Σ
ReLU((W:. xp))
re(m)] PE
Σ Σ
ReL (1) (.r
Σ
Σ (a,
re(m) PEJR
rE(m) DeJ
< m
Σ PE
ReLUUap max,e[m]
+
Σ
ReI.U(p maxre(m) D(o
PEJu
< ((1/
Where Lemma D.7 upper bound the -ia-oiaao weight-feature correlations (they always lie within the polynomial part of activation function).
Thus, derive that F, (X): Fx(X) for each E [ \ (v)-
28

---

Published as a conference paper at ICLR 2025
Lemma D.13 (Non-robust Features are Learned Well). For T = (poll(dd) and each data point (X,y) ~ Din with probability - o(1), we have Fy FTT) (x) (!T) Vi [k] {v).
Proof. Since have that mmx B ((log(d)) for each class y E [1]] it suggests F (X) (log(d)). For non-diagonal outputs, we have results similar to Lemma D.12, i.e. F F (X) = (11/d//2), which immediately derives the lemma above.
Lemma D.14 (Standard Training Converges to Non-robust Solution). For T = ((poly(d)) and each data point (X. y) DD let perturbation A (XX3) y) := (61, 52..... åp). where 6p := -3 + cuty for p JNRi 8p 0 for p JR. and is randomly chosen from [k:] \ {y}, then, with probability
1 1 o1)), we have F. F(T) (x + A(X,8)) > F.") (T (X,, u)), Vi E [k] {s'}.
Proof. By the definition of perturbation ( (X,, X, 2) that replaces all non-robust feature patches v, by non-robust feature Vy from another class 3/, we have
F (X ((X,)))
Σ
ReLU W yrr By +oy+o 0p)
rE [m]] PE(P)
Σ
ReLU max, B B + O(polylogdd)/VD
PE[P]
(log(d)) (1(1/d9/2) max,elMM (X A(X,))) v)),
which shows this theorem.
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 = (pply(dd) (d)//)))))) iterations, the model ((T) satisfies:
Robust features are learned: P(X):))>DF argmax F. F!TT
= o(1). # (X))
Robust test accuracy is good:
P(xx)>
3A
(R4)
| C, (rggaax F
(X + A) + v) o(1).
Proof Sketch. The proof this theorem can also be divided into two stages (according to the activa- tion 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 gradient ascent algorithm, while robust feature learning continues to grow.
Now, we give the detailed proof as follows.
D.2.1 WEIGHT DECOMPOSITION
Since our algorithm 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 weight decomposition theorem similar to that of standard training.
Lemma D.16 (Weight Decomposition for Adversarial Training). For any time t 2 0. each neuron Wsrr r() E [k] x [m)), we have
Σ Σ
(t) u.
P
w
(0) 1.
Alyu: + 1L000 diagonal correlations
Eioly + Di
WE(M] 8E(m)
orthogonal all features
non-diagonal correlations
29

---

Published as a conference paper at ICLR 2025
where A B A... Dirs and E Birry. are some time-variant coefficients, and Pj Ia
Ejer ff projects a vector into all features f E F's orthogonal complementary space.
Proof. Notice that the following update iteration:
un; -miir (X.WDD
(1+1)
Vu,,, fAE (F(t); x(1)) x.)]
(8) w + (X)
(1(==)) -lggit, (F(1), x(1))
Σ
ReLU (ww )
PE[P]
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).
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 and data point (X,9) we have the following decomposition
about the lime-variant corresponding adversarial example ( (1), y), where we use (á:1, ...,..,, 5.p))
,......,,,
denote X Then, it satisfies:
a uuy (1() aap My + 36 By
19
Σ
Σ
10 p.s
P
(0) w
jøU
iE(M]
rE(m)
where Pj- I=II--Ees ff projects a vector into all features f E F's orthogonal complementary
spuce, and coefficients a,"), 36. X() p.j' m and z(t) ((t) ppirr are updated by the following iterations
.For p E TR. we have
ap (1 min -. á. Exe(m) ReLU A
(1)
Pp min(e, 7 Exc(m)
ReLU (a.
{()) minfc, Σ Em
ReLU (a (1p y.
P.
PPJ min E [m(m]
(())
ReLU (a, A (1)) (! (())
U,S.j
((t) min 7 Eee(m] parr
ReLU (a. (ap. (t) ((()) 1
For p E JNR, we have
0p min ( E EeEm
ReLU (S, (
3 (1 min o. Dp
Exe(m) ReLU (3, (3,
X())
P. min(e, 7 [
ReLU (B, (B, c
P minfe, i [m|m ReLU (8, B (0) ) y.s.}}
(t)
(0)
P.r min(e, E ReLÜ (3, B ((()) 3
Proof. By substituting the weight decomposition expression into the formula of the gradient ascent algorithm and simplifying, we obtain this lemma.
Now, derive the following feature learning iteration for adversarial training.
30

---

Published as a conference paper at ICLR 2025
Lemma D.18 (Feature Learning Iteration for Adversarial Training). During adversarial training, for any time 2 and pair (i, r) E [k)] [m].j E [b] \ {i), the two sequences (A [B {C and Fi.ry. satisfy:
Lng
(D(9) Gnig
A(+11) - n
(1v=)) - logit, (F"")
Σ
ReLU
( (. dp
pE[r)
B 1, + n/B
(1 - logit, (F10, x
Σ ReLU
(w.r. 2000) 360
(1)
pE[P]
((00 + nB
(1(v=)) - logit, (F(1), ()))
Σ ReLU
( f.r 2/11) {
pE|P|
(( (00 1in' + 1/B
(Ly=i) logit,( (F(), ,
Σ ReLU
(w
(t) a(1)) Pp.
pE[PI
p(++1)
FE(1)
P,r.g.s + v (1(v=t) logit,(F() x())
Σ pE[P]
ReLU
(w (,r
((11) 7p..
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.
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 (X("))) .8) ~ D, suppose that ma A Ollg(d)) and maxie([) B(t)
ma)) (e iirg = O(log(d)/V/ and max) ( Olog(dd) (d), and (x) 2 elog(d) for some 2 0, then we have the following approxi- mation logit:
((1)
.ife= O; ifc> 0.
- logit, (F(), ,x())) = 0 de
(F"),
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 (X(1,,) .y) D. suppose that max A O(lo((d) and max]e[M) B(() o(1 (e) Cira O(log(d) (d) /d) and max D
(t)
O(log(d)VVi) and Fy (x())) 2 clog(d) for some 0, for i y:
(0(kk) 10 (#)
ife 0;
logit, (F()) x(()
ifc 0.
Proof. The proof logic is also similar to Lemma D.6.
D.2.4 NON-DIAGONAL TERMS ARE SMALL
Lemma D.21. For every time t. non-diagonal feature correlations Cary D (i,r) [k] [m],y y * i) satisfy that max,e[m)) C O(maxrgjm) 0,00) and max D
((maxre(m) DioPy) for each E [k],3 y [K] {i}.
Proof. The proof logic is also similar Lemma D.7.
31

---

Published as a conference paper at ICLR 2025
D.2.5 ANALYSIS OF FEATURE LEARNING PROCESS FOR ADVERSARIAL TRAINING
Stage I: Almost neurons lie within the polynomial part of activation ReLU. Lemma D.22. During adversarial training, there exists some time threshold To such that, for any early time S t I To and pair (i,r) E [k)] x [m]] the two sequences { and {B satisfy:
A (1+1)
~ A + (()) (A
9-1
E
Σ 08 (1
min ( Σ (A)
8E(m]
B [ + (n) (B())
9-1
E
Σ
min { ((m) Σ (1)"
PE
sE(m]
Proof. The proof logic is similar to Lemma D.4.
Phase First, Network Partially Learns Non-Robust Features.
At the beginning, due to our small initialization, we know all feature learning coefficients 1 B (11), which suggests that the total feature learning Exe(m) (A())) and E. (B!")) are suffi- ciently 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 E [k), let time Тy denote the first time when Exe(m) (B reaches
11n then we have maxre[m] A (Ty) (polylogg(d)/ (dd).
Proof. We choose da Ag.r and y1 BBl Then, by applying Lemma B.2, derive this result as the same way as the proof Lemma D.9.
(t)
Once the total non-robust feature learning E.em) (B()) attains order of O 1), it is known that the non-robust feature learning will stop, due to 3 2 and ((n) Exe(m) (B. 0.
In contrast, the robust feature learning continues to increase since it always holds that 1 min { -__ (()) [m]m (A) 2 1- ap 2(1). Thus, the robust feature learning will in- op crease over the non-robust feature learning finally, which can represented as the following lemma.
Lemma D.24. For each E [k), let time T', denote the first time when max,g|m) A reaches g/o, then we have I ((poly(d) and max/e[m] BSTT) O(1
Proof. The proof logic is similar to Lemma D.
Stage II: Robust feature learning arrives linear region of activation ReLU.
Lemma D.25. For each y [k] and (X,y) D. let time T denote the first time such
(TT)
that ( (x()) 2 log(d), then T" poly(d) 2 Ty and we have maxre(mi Byr Oppolyoo(dd)/d)))
Proof. The proof logic is also similar to Lemma D.10.
Lemma D.26. For all time t = (ppoy((d) 2 T and each (X.y) ~ D, we have F (x(1)
Ollog(d)) and max,e[m] B(t) (ppolylog(d)/d))
Proof. The proof logic is similar to Lemma D.8.
32

---

Published as a conference paper at ICLR 2025
D.2.6 PROOF OF THEOREM D.15
Lemma D.27 (Robust Features are Learned Well). For T ((poly(d) and each data point (X,y) ~ Fgg with probability o(1), we have F(T) (X) (x), vi E [k] {v}
Proof. The proof logic is similar to Lemma D.13.
Lemma D.28 (Adversarial Training Converges Robust Solution). For T ((poly(d) and each data point (X, y) Drw, with probability o(1), we have VA E (RR") s.t. lco S
( ((T) (X + A)
Proof. For given data point (X, v) D and any perturbation A (8,,82,.... .p) E (124) P satisfying | S e, we calculate the perturbed margin as follows.
F(T)
X +
A = Σ
Σ
Rew (2) yir Mir ag + 5p)) - Σ
ReLU(( (T) g. Bp + 8p))
TE
PEJ
rE[m) PE
2 Σ
Rea max A(P))
PETR
2 Σ O(ap max+ A7)
PEJR
2 (log(d)))
where Lemma D.21 and Lemma D.26 and the first part of Assumption 2.3 (i.e. ap > e).
And for any j E [P] \ {y}, we have
E(T) (
Σ
Σ
ReWU((W (T) dor up + +8p) + Σ Σ
RewU((w (T)
Jor Bppy + 8p))
rElm PEJT
rE/m] PE
Σ ReLU((((a max ()r)))
Σ ReLU max (
PEJR A <oloo(d)),
PEJRR
where we also use Lemma D.21 and Lemma D.26. Therefore, we derive the theorem.
33

---

Published as a conference paper at ICLR 2025
E PROOF FOR SECTION 4
E. 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 = (opoly(d)/m) iterations, with high probability over the sampled training dataset Z, the model ( satisfies:
Standard training is perfect: for all (X,9) E Z, all [K] : Fx > F. (T( (X).
Non Non-robust features are learned: P P(Xx,.))DD
argmax,e|w F. ( # (1).
Standard test accuracy is good: I ()x argmax,e(M) P. ((T) (x) + y/ o
Robust test accuracy is bad: for any given data (X, .y) using the following perturbation ((X.)) := .,....,6 where 8p :-= -Bp + Evy for p E JNR: 8 0 0. JR.
and of is randomly chosen from [R]] \ {y} (which does not depend on the model F(T) and illustrated in Figure 2), we have
P P(x.))~D argmax F (X++(XXX A(X,
+ =1 V)
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.
E.1.1 WEIGHT DECOMPOSITION FOR STANDARD TRAINING
Lemma E.2 (Weight Decomposition for Standard Training). For any time t. 2 0, each neuron way ((ir) E [k] x [m]). we have
w w + u. Bl0
E(C
Ung + D 0;)+ +
Σ
Σ
our oxr(((X,)), p))
(X PE(P!
where 1 B(t)
c(t) and ((t), ing and or, ((X,()) are some time-variant coefficients.
inn
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 = (poly(dd) and each training data point (X, y) E Z and for each patch index p E [P], we have (w Ep) = ((1/Vd).
Proof. By analyzing the iterative process of the noise terms, we have the following lemma:
Lemma E.4 (Noise Correlation Update). For every (X,y) E Z and E (P), if then
(w(tt)) Ep) T. Ep) +
(N [N) ReLU
(ww (w().)p)) (1 logit, (F()) x)) + Vd
for similar reason, if + then
(1+1) "1ll Ep = 10 5o)
θ (12 ReLU
((w()) (p)))))))))))) logit, (F x) + 1
Vd
Using the same line of reasoning as in the simplified case (Lemma D.5, Lemma D.6 and Lemma D.8), derive the following two lemmas:
34

---

Published as a conference paper at ICLR 2025
Lemma E.S. For each class E [k] and all time I such that max(xx))e2, F3 (X) log(d) and m| A (ppolylog(d) /vd) and maxre[m] C O(polylog(d) /Va) and maxre[m] Diry Oppolylog(d) /V)) for each E [k].y [K] \ (i), have (xn)) Fy (X) (Xmma(Xx.))e) F.) (X)).
Lemma E.6. For some time To, we have Ei=n, B ((x [1 logit, (F(t) x)] = Ö(
Combined with Lemma E.4, Lemma E.5 and Lemma E.6, and N = poly(d), we can prove this lemma.
E.1. FEATURE LEARNING FOR STANDARD TRAINING
Theorem E. is direct corollary of the following lemma:
Lemma E.7. For sufficiently large time T = ( (d)) we have max/e[m] B = (log(d))
and max]e[m] A (polylogg() /vd) and maxye[m] Ciray O(polylog(d) /vd) and (polyyog(() /Vd) each i E [k], E [4] (i).
max+E[m] (1t) i,r.y
Proof. Due to Lemma E.3, we can prove this lemma using the exact same logic as that used to prove Lemma D.8.
E.2 PROOF FOR ADVERSARIAL TRAINING
Theorem E.8. For sufficiently large d, suppose we train the model using the adversarial training algorithu starting from the random initialization, then after T ((poly(d)/n iterations, with high probability over the sampled training dataset 2, the model F satisfies:
Adversarial training is perfect: for all (X, v)
and all perturbation A satisfying
| S c, all i E [k] F1 F (X + A) > F (T) (TT)
(X + A).
Robust features are learned: (X), argmax F. ((TT (X₂) # f = o(1)
Robust test accuracy good: (TRd)*
3A
P s.1. | S araggaxx F (T) (X + A) * y = o(1)
PP p(x'))>D
Our proof approach almost identical 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.
Proof Idea:
E.2.1 WEIGHT DECOMPOSITION FOR ADVERSARIAL TRAINING
Lemma E.9 (Weight Decomposition for Adversarial Training). For any time t 0. each neuron
Wsrr (i,r) E [k] x [m)). we have
( i + A B Us
(1) (0)
E(cly + D oy) +
Σ
Σ oi, o.
(X.y)EZ
where ( ((t)) Clo and (()) and (i,(((X,)) p) are some time-variant coefficients.
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 O(poly(d)) and each training data point (X,y) y) E 2 and for each patch index p E [P]. we have (w Ep) = Ó(1/Vā).
Proof. The proof logic is similar to Lemma E.3.
35

---

Published as a conference paper at ICLR 2025
E.2.3 FEATURE LEARNING FOR ADVERSARIAL TRAINING
Theorem E.8 is direct corollary of the following lemma:
Lemma E.11. For sufficiently large time T = (ppolydd)
have ma A (log(d)) and max+e|m) B O(1/dm)) and ma C O(polylog(d) / Vd) and maxxe[m] ( (pplyyogg(d) for each i E [k], E [4] (i).
Proof. Due to Lemma 10, we can prove this lemma using the exact same logic as that used to prove Lemma D.26.
36


Reviews:
[{"review_id": "SRFDDXWYax", "reviewer": "Reviewer_wbRQ", "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.", "questions": "My major questions are already pointed out in the \"weakness\" section above, in addition to that, I have the following minor questions:\n\n1. 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$?\n\n2. 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.\n\n>>> 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.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper has the following strengths and contributions:\n\n1. 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.\n\n2. The theoretical analyses are consistent with numerical experiments on various datasets.", "weaknesses": "I have the following major questions or concerns regarding the current manuscript:\n\n1. The title is a bit misleading. Usually, 'provable robustness' means 'robustness verification', the conclusion of this work does not involve robustness verification.\n\n2. 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$.\n\n3. 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.\n\nBased 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "izxsDL7x3g", "reviewer": "Reviewer_UbB1", "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.", "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.\n\nMy 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?\n\nA few specific questions are listed below:\n\n1. 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)?\n\n2. 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?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 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.\n\n+ The paper is well-structured and easy to follow. The assumptions, theoretical statements, and proof techniques are clearly presented.\n\n+ The theoretical findings are well-supported by experiments on real-image datasets like MNIST, CIFAR10, and SVHN, enhancing the credibility of the results.", "weaknesses": "- The complexity of the models and the heavy reliance on specific assumptions about data structure may limit the general applicability of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "c54qT6gAGa", "reviewer": "Reviewer_gMkj", "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.\n\nMore 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.", "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?\n\nOverall, 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.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "+ Bringing a new perspective on a very core and extremely well studied topic\n+ Establishing the result required a major technical effort and delivered some interesting insights into underlying training dynamics of two-layer convnets", "weaknesses": "- The considered data distribution is quite interesting and has a clear motivations but at the end of the day it is really heavily stylized, especially the choice to make the class signal be essentially a (scaled) one-hot vector\n- 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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PjIm0adQml", "reviewer": "Reviewer_cqxX", "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.\n\nTo 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.\n\nUsing 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.\n\nFinally, 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.", "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.\n\n2. 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?\n\n3. 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\\)$.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper provides a compelling theoretical explanation for a well-known empirical phenomenon, as demonstrated in prior work [1].\n\n[1] Ilyas, Andrew, et al. \"Adversarial examples are not bugs, they are features.\" Advances in neural information processing systems 32 (2019).", "weaknesses": "The theoretical framework relies on several significant assumptions:\n- **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.\n\n- **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\\))$.\n\n- **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.\n\n- **Definitions of Robust and Non-Robust Features (Assumption 2.3):**\n  - Robust features are defined as stronger than non-robust features.\n  - Non-robust features are defined as denser than robust features.\n  - However, these definitions lack interpretability, which would be beneficial for a more complete understanding.\n  - Under this assumption, standard training picks up denser features, while adversarial training picks up stronger features, assumed to be robust features.\n  - The paper lacks experiments to demonstrate the existence of these properties (strength and density) in real-world datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QUIlhSkWR9", "reviewer": "Reviewer_XDz5", "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,\n* standard training of gradient descent learns non-robust features. Therefore, adversarial perturbations exist along the negative non-robust feature directions. \n* adversarial training with one step gradient ascent provably learns the robust features, thus improving the robustness of the network. \n\nEmpirical results on MNIST, CIFAR-10 and SVHN demonstrate the above theoretical findings.", "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}$. \n2. 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.\n3. 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? \n4. Minor comment: in line 179, 'where $u,v$ are the corresponding' - u,v should be boldfaced.\n\n[P1] Tsipras et al. \"Robustness May Be at Odds with Accuracy.\" ICLR 2019.\n\n[P2] Tsilivis and Kempe. \"What can the neural tangent kernel tell us about adversarial robustness?.\" NeurIPS 2022.\n\n[P3] Singh et al. \"Robust Feature Inference: A Test-time Defense Strategy using Spectral Projections.\" TMLR 2024.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 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.\n2. 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.\n3. Experiments also support the theoretical findings.", "weaknesses": "1. Extending the analysis beyond the two layer smoothed ReLU convolution network to realistic, deeper neural networks seems difficult. \n2. The adversarial training is with just one step gradient ascent which is usually not the case in practice. \n3. The definition of robust and non-robust features require parallel to the coordinate axis along with orthonormal condition which is restrictive.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)