Theoretical Understanding of Learning from Adversarial Perturbations
Authors: Soichiro Kumano
Hiroshi Kera
Toshihiko Yamasaki
Venue: ICLR 2024 poster (2024)
Keywords: Adversarial Perturbations
Adversarial Examples
Adversarial Attacks
Non-Robust Features
Primary area: learning theory
TL;DR: We provide the first theoretical justification that neural networks can learn class features from adversarial perturbations.

Abstract: It is not fully understood why adversarial examples can deceive neural networks and transfer between different networks. To elucidate this, several studies have hypothesized that adversarial perturbations, while appearing as noises, contain class features. This is supported by empirical evidence showing that networks trained on mislabeled adversarial examples can still generalize well to correctly labeled test samples. However, a theoretical understanding of how perturbations include class features and contribute to generalization is limited. In this study, we provide a theoretical framework for understanding learning from perturbations using a one-hidden-layer network trained on mutually orthogonal samples. Our results highlight that various adversarial perturbations, even perturbations of a few pixels, contain sufficient class features for generalization. Moreover, we reveal that the decision boundary when learning from perturbations matches that from standard samples except for specific regions under mild conditions. The code is available at https://github.com/s-kumano/learning-from-adversarial-perturbations.

Published as a conference paper at ICLR 2024
THEORETICAL UNDERSTANDING OF LEARNING FROM ADVERSARIAL PERTURBATIONS
Soichiro Kumano
Hiroshi Kera Chiba University kera@chiba-u, ip
The University of Tokyo
jp
Toshihiko Yamasaki
The University of Tokyo
yamasaki@cvm. t. u-tokyo.ac. ip
ABSTRACT
It not fully understood why adversarial examples can deceive neural net- works and transfer between different networks. To elucidate this, several stud- ies have hypothesized that adversarial perturbations, while appearing as noises, contain class features. This supported by empirical evidence showing that net- works trained on mislabeled adversarial examples can still generalize well to cor- rectly labeled test samples. However, theoretical understanding of how per- turbations include class features and contribute to generalization is limited. In this study, provide a theoretical framework for understanding learning from perturbations using a one-hidden-layer network trained on mutually orthogonal samples. Our results highlight that various adversarial perturbations, even per- turbations of a few pixels, contain sufficient class features for generalization. Moreover, we reveal that the decision boundary when learning from perturba- tions matches that from standard samples except for specific regions under mild conditions. The code is available at https: https: :/ght///////ttt com/ a- kumano///////oo learning from- wdversariaaaaa.aa.. www.ssaaaaal-pettuuatttooooo.
INTRODUCTION
It is well known that small malicious perturbation, adversarial perturbation, change classifier's 's prediction from the correct class to an incorrect class (Szegedy et al., 2014). An inter- esting observation by Ilyas al. (2019) has shown that neural network, trained adversarial examples labeled by such incorrect classes, can generalize to correctly labeled test samples. Specif- ically, the training procedure is follows:
Definition 1.1 (Learning from adversarial perturbations (later redefined) (Ilyas al., 2019)). Let
D = {( Dn) ) be training dataset, where denotes an input (e.g., an image) and yo denotes the corresponding label. Let ff be a classifier trained on D. For each n, an adversarial
example addd is produced by imposing an adversarial perturbation on &, to increase the probability
for target label y * Yn given by f, constructing Dadv = {( yadv) ) J Training a classifier from scratch on Dadv is called learning from adversarial perturbations..
Notably, a training sample x addv appears almost identical to æ to humans, but is always labeled as a different class yadv * y (e.g.. an adversarially perturbed, yet semantically unchanged, horse image with a cat label). Counterintuitively, networks can learn to classify correctly labeled test samples (e.g., cat image with cat label) from such mislabeled adversarial samples.
The unexpected success of training on mislabeled adversarial examples suggests that adversarial perturbations may contain label-aligned features. For example, frog adversarial images labeled as horses have perturbations that appear as noises to humans but contain horse features. This feature
This neither adversarial training nor training with (partially) noisy labels (ef. Appendix A).

---

Published as a conference paper at ICLR 2024
hypothesis not only explains the counterintuitive generalization of learning from perturbations, but also sheds light on several puzzling phenomena of adversarial examples, such as why adversarial examples can fool classifiers and transfer among them (cf. Section 2).
While the feature hypothesis is considered a potential explanation for adversarial perturbations, a theoretical understanding of this hypothesis and its empirical foundation, learning from perturba- tions, remains limited. For example, it is still unknown how adversarial perturbations contain class features. The similarity in decision boundaries between the network trained on clean and mislabeled adversarial samples is also unknown.
In this study, we provide the first theoretical validation of the learnability from adversarial perturba- tions. Using recent results on the decision boundary of one-hidden-layer neural network trained on mutually orthogonal samples (Frei et al., 2023), we show that perturbations contain sufficient class features for generalization. In addition, we demonstrate that the decision boundary when learn- ing from perturbations is consistent with that from natural samples except for specific regions under mild conditions. While Ilyas et al. (2019) empirically considered only the case where Læ-constrained perturbations were superimposed on natural data, our theory covers broader settings. We reveal that even sparse perturbations, perturbations of few pixels, contain class features and enable gener- alization. Moreover, we show that the alignment of decision boundaries derived from adversarial perturbations and natural samples becomes stronger when perturbations are superimposed ran- dom noises. The main contributions are summarized as follows:
We theoretically justified the feature hypothesis and learning from perturbations with one- hidden-layer neural networks trained on mutually orthogonal training samples.
We showed that various adversarial perturbations including sparse perturbations can be rep- resented by the weighted sum of benign training samples. This suggests that perturbations, yet apparently uninterpretable, contain sufficient class features for generalization.
We demonstrated that classifiers learning from mislabeled adversarial samples produce consistent predictions with those from clean samples under mild conditions. Moreover, classifiers trained on random noises with perturbations provide accurate predictions for natural data even though the classifiers do not see any natural data during training.
2 RELATED WORK
Ilyas et al. (2019) first claimed that an adversarial perturbation contains class features, called non- robust features. These features are highly predictive and generalizable, yet brittle and incomprehen- sible to humans. This idea is supported by neural networks that learn from perturbations (cf. Def- inition 1.1) achieving good test accuracies on standard datasets (Ilyas al., 2019). The hypothesis that perturbations contain features elucidates several phenomena of adversarial examples (Szegedy et al., 2014). For example, models misclassify adversarial examples because they react to features in perturbations. Transfcrability (Szegedy et al., 2014; Goodfellow al., 2015) is also explained: dif- ferent models respond to the same features in perturbations. Moreover, adversarially robust models focus robust (semantic) features and ignore highly predictive non-robust (non-semantic) features, providing insights into the trade-off between robustness and accuracy (Su et al., 2018; Tsipras et al., 2019; Raghunathan et al., 2019; 2020; Yang al., 2020), the human-aligned image gradients of robust models (Engstrom et al., 2019b; Kaur et al., 2019; Santurkar et al., 2019; Tsipras et al., 2019; Augustin et al., 2020), and the enhanced transfer learning ability of robust models (Aggarwal al., 2020; Salman et al., 2020; Deng et al., 2021; Utrera et al., 2021).
Subsequent studies deepened the discussion of non-robust features. While llyas et al. (2019) con- sidered robust and non-robust features separately, Springer et al. (2021b) claimed their potential entanglement. Some studies have attempted to separate robust and non-robust features using the information bottleneck (Kim et al., 2021) and neural tangent kernel (Tsilivis & Kempe, 2022). En- gstrom et al. (2019a) provided a broad discussion about robust neural style transfer and feature leakage. Other studies have used the feature hypothesis to generate highly transferable adversarial examples (Springer et al., 2021ag,;c), understand the behavior of batch normalization in adversar- ial training (Benz et al., 2021), and degrade the robustness of adversarially trained models (Tao et al., 2022). However, the nature of adversarial perturbations as class features and the theoretical explanation for the counterintuitive success of learning from perturbations remain unclear.
2

---

Published as a conference paper at ICLR 2024
In this study, we justify learning from perturbations, which is essential foundation of the fea- ture hypothesis. Our results support the above studies based on the feature hypothesis. We do not consider whether adversarial perturbations robust non-robust. We discuss the nature of per- turbations as class features and why classifiers can obtain generalization ability from perturbations.
3 PRELIMINARY
3.1 SETTINGS
Notations. For positive integer N. let [n] := {L.... . n.. For vector æ E Rd, we denote the Euclidean norm by ||=||| We use Q O .), and O(-) for the standard big Omega, big Theta, and big O notation. To hide polylogarithmic factors, we use s?( ), O and ((-).
Network. Our network settings follow Frei et al. (2023). Let f Rdd - R one-hidden-layer neural network. The number of hidden neurons is even and is denoted by m. We assume that the hidden layer is trainable and the last layer frozen to constant weights a E RT The first half elements of are 1/ym and the latter half are -m/ Let W := (W)..... Wm) E mx be the weights of the hidden layer. Let ((2) = max(2, be the element-wise leaky ReLU for a Φ wW)). The assumption that the positive and negative values of a are equal is introduced for notational simplicity and is fundamentally unnecessary. In Appendix G, we derive
constant y E (0, 1). Namely, f(x)
results without this assumption.
Training. Let D = {( Ba) C Rd x {+1} be a training dataset. With the exponential loss {(z) ex) logistic loss {(z) In(1 + exp(-2)); loss DD is defined as L(W; DD) Σ [ W))/N. The network parameters are updated by gradient flow, gradient descent with infinitesimal step size, dW (t)//dtt training step. Finally, we summarize the training setting.
V w ((W(t); D). where t > 0 is continuous
Setting 3.1 (Training). Consider training one-hidden-lage layer neural network f on a dataset D. The network parameter W is updated by minimizing the exponential or logistic loss over the dataset, C(W; D), using gradient flow. The training runs for a sufficiently long time, i.e., + ao.
Learning from Adversarial Perturbations. formalize and extend Definition 1.1.
Definition 3.2 (Learning from adversarial perturbations). Let D == {< b 1 C Rd x }
training dataset. Let f= Rdd TR be me-hidden-layye neural network trained on following Setting 3. Let Nadv E N be the number of samples with perturbations. For each [Nady]] perturbed sample anddr E IRd targeting a new label yau {=1} produced as cither:
(a) (Perturbation on natural sample) Nadv - and aud := xx + Th
(b) (Perturbation on uniform noise) a :- Xx, 77, where X,, is sampled from the uniform distribution 1({=1,1)*) For any + k. X,, and X₃ independent. The target label ynd is randomly sampled from {=1}.
The perturbation 7n, is given by an adversarial attack. Training a classifier from scratch on a new Audv following Setting 3.1 called learning from adversarial perturbations. adv ) ) dataset {( ya
This definition has two differences from Definition 1.1. First, we added a noise data case. In this scenario, justify learning from perturbations under milder conditions than in the natural sample scenario. Second, we removed the restriction of yadv j to consider broader cases. In addition to the uniform noise case, examine the sub-Gaussian noise case in Appendix F.
3.2 DECISION BOUNDARY OF HIDDEN--LYYE NEURAL NETWORK
To understand learning from perturbations, we employ the following result on the implicit bias of gradient flow (Frei al., 2023).
Theorem 3.3 (Rearranged from Frei et al. (2023)). Let {(In yn N C Rdd x {+1} be train- ing dataset. Let Ruax == max, | Runn == min, I ll. and Praxx == maxn (In, xx).

---

Published as a conference paper at ICLR 2024
A one-hidden-layer neural network f Rd 4 R is trained on the dataset with Setting 3.1. If 72 (3N Rmaas 2 Pmax, then sgn(f(z)) sgn( (z)) holds with I + 0o, where pbdy (z) == -m=1 (nnn((nn: z) and Xn (2 2 R mnin
N
for every [N].
Appendix B provides a more detailed background. This theorem claims that the binary decision of f=) equals that of the linear function fbdy namely, f(x) has linear decision boundary. This theorem requires training samples to be nearly orthogonal, which is a common property of high- dimensional data. Although this theorem is not related to learning from perturbations, we utilize it to easily observe the decision boundary learning from perturbations as follows:
Corollary 3.4 (Decision Boundary when learning from perturbations). Let {(rady yadv) In be mislabeled training dataset with adversarial perturbations (ef. Definition 3.2). Let Rady max, Jo ||, Rand := min, || I|. and Pmax == maX24k (ar xot A one-hiddenn-lyer
neural network is trained on the dataset with Setting 3.1. If Rady" /(3.Naav Rady, ?) 2 prnl Naae Aadr yadv (xaaey 2))
then (g sgn( I Suayy (z)) holds with - co, where faay (z) = En=1
and Xadv E 2feedv T 2-y Ruudy min
3 7) for every E [.].
4 THEORETICAL RESULTS
4.1 PERTURBATION AS CLASS FEATURES
Recall that a one-hidden-layer network trained on orthogonal samples with Setting 3.1 has linear decision boundary (cf. Theorem 3.3). We focus adversarial attacks this boundary rather than the network itself, called geometry-inspired attacks (Moosavi-Dezleee et al., 2016; Croce & Hein, 2020), which simplify notation. Let O be the perturbation constraint. A geometry-inspired adversarial example and maximizes ya pbudy
fboly (x under || In S as follows:?
V pbdy (Ix)) I az (xx))l
adv ΣN A
adv Zn == In + Tms
nh == cyn
adv
cyn
(1)
E AAyKARal
Without loss of generality, we consider a single step of the gradient calculation because multiple steps also produce the same perturbation form due to the linearity of fbdyy The perturbation Th represented as a weighted sum of the training samples. Since the training samples [ are nearly orthogonal (i.e., H, and 2y do not negate each other for of k), the perturbation contains class features of the training samples. This observation supports the hypothesis that adversarial perturbations contain class features, enabling generalization from them.
J
4.2 LEARNING FROM ADVERSARIAL PERTURBATIONS ON NATURAL SAMPLES
We consider learning from -nnspire perturbations on natural samples. Appendix C pro- vides the proofs of the theorems. Using Corollary 3.4, the decision boundary can be derived as:
Theorem 4.1 (Decision boundary when learning from geometry inssired perturbations natural samples). Let ff be a one-hidden-layer neural network trained on coometry-inspired perturbations natural samples (ef. Eq. (1) and Definition 3.2(a)) with Setting 3.1. If N C² R and
(R min -2 C .N c 222
C c - Pmax
2
(2)
3N (R max +
C C
VN
In Appendix E, we discuss coometry-inspired La and Los attacks and a gradient- based Le attack that targets the network itself, such as fast gradient sign method (Goodfellow et al., 2015) and projected gradient descent (Madry al., 2018).
perturbations Eq. (1) can be defined only if A can be determined by Eq. (A11). training samples satisfy 7 HHiin/(3 R 2 Pmax. Eq. (Al1) is always consistent; thus, the definition is valid. Note that Fq. (A11) is consistent for some sample sets that do not satisfy 73 R /3N R 2 Prnax (cf. the proof of Lemma C.I).
"Geometry-inspee
4

---

Published as a conference paper at ICLR 2024
3Rd Jans + Renin
with C
7/th Rimin vI-7 then, with + oc, the decision boundary of f is given by
E==1 A yarl (I
fbud
Jadv (z) :=
(3)
Σx=1 Andv
E EE==1>mm An
Effect learning from mislabeled natural samples Effect learning from perturbations
The decision boundary, Eq. (3), includes components that explain the effects of mislabeled samples and geometry-inspired perturbations. The sign of the first term is determined by the sum of the weighted inner products, _n=1 w (at,, 2). Because yady is mislabeled, the sign (binary decision) of the first term not always consistent with human perception. The sign of the second term depends only the sign of the standard decision boundary (z) When the magnitude of the second term dominant, sgu(Sldv (z)) matches sgn( (f This suggests that although the dataset appears mislabeled to humans, the classifier can still provide a reasonable prediction. A more general version of Theorem 4.1, without assuming N C²² /²/Rpm RRmin is given in Theorem C.2.
Perturbation Constraint. The assumption, Ineq. (2), requires mutually orthogonal adversarial sam- ples, which restricts the perturbation constraint to O dddN). The perturbation constraint linearly increases the dominance of the perturbation effect. If we ignore the restriction, then adv (z)) = ff (z)) holds for any z with e + co. This aligns with the intuition that large perturbations restore the standard decision boundary.
sgn(fadv (bdy
Consistent Growth of Two Effects. Here, we provide a short summary of the limiting behavior of Eq. (3). A detailed analysis can be found in Proposition C.4. Let (NN, d) and h(N, d) be pos- itive functions of the number of training samples N and input dimension d. In addition, let T1(2) and (2) be the first and second terms of Eq. (3), respectively. Given the labels yn and yarl freely selected from {1 estimating the growth rate for Ti (z) and T2(z) is challenging. There- fore, we assume that En=1 Anyir (In: 2)1 = Ogg(N, d)) if N An Mn =)1 ((o(N,)) d)) and instead estimate the growth rate of Σ Am (ar: 2) rather than Σx Anyn (>). simi- lar assumption applies to EEA=y Aady yorv (x... 2)]. Note that these assumptions are removed in noise data scenarios. Interestingly, under these conditions, for any z, [Ti( = ((M(NN)) d)) <> [72(2) = ((h(N.)) d)) holds, indicating consistent growth of the two terms. For example, if test sample is weakly correlated with all the training samples, e.g., 2 Σn 0(1/VN)a,, then [x)] = (dd/ //d and [T2()) = Odd/VN). Note that the scaling factor @(1/VN) ensures @[[==]) = vd. This consistent growth implies that the effect of mislabeled data, Ti (z). is not dom- inant even with a large input dimension and sample size N. Thus, learning from perturbations is feasible for high-dimensional datasets with numerous samples.
Random Label Learning. Next, we consider the limiting behavior of Ti (z) and T2(2) when ya yadv is randomly sampled from [+1]. ).A. A detailed analysis is provided in Proposition C.8. Intuitively, if yau randomly takes 11 independently of the sample x,, and its original label ya. the magnitude of the nu- merator of Ti does not increase significantly, while the denominator consistently increases as the sample size N increases. Consequently, the growth rate of (z)) is lower than that of [2)).. Fol- lowing this reasoning, we can demonstrate that [T2(2) surpasses [Ti (z)) except for specific z. For N example, if is weakly correlated with all the training samples, e.g., Σ n== (1/v/N ( then [z)] = (d/NN and [T2(2)] = ((d With enough training samples, [Ta(2)] > (z)) and sgn( phdy (z)) = sbd( hold. That is, classifiers trained on an apparently mislaheled dataset produce reasonable decisions for samples that are weakly correlated with the training sam- ples. In contrast, if test sample has a strong correlation with particular training samples, e.g., = +(1)2))) )=,, the consistent growth of [2)) = Od/NN and [T((2)] = Odd/N) persists. These results can be summarized and generalized as follows:
Theorem 4.2 (Consistent decision of learning from geometry-inspired perturbations on natu-
ral samples). Suppose that Ineq. (2) holds. Assume |æ e @(vd) for any E [N] and ((vd). Suppose that yodv is randomly sampled from {+1} for each Assume x||| ΣN \n 2}} = O(g(N,d) d)) if ENN Anl(Zn, 2)1 O(g(N, d)), where g is a positive
5

---

Published as a conference paper at ICLR 2024
function of N and d. If there is such that ( z)1 (dd) or En ((e. 2 1 ا)ح (d)) does not hold, with N, d + then sgn(Sadv Sad (z)) sgn( (z)) holds with probability at least 99. 99.9%.
This theorem suggests that classifiers trained on an apparently mislabeled dataset can produce de- cisions consistent with standard classifiers, except for specific imputs that satisfy the following two conditions: (A) there exists such that (xx, =)1 = ((d), and (B) En: (x.))))))))) (((()) (m z) = (dd) holds. Such exceptional inputs could be, for example,
x)
21. 21 22 I3, and 21 + O(1NN),, where denotes an all-ones vector. Condition (A) represents a strong correla- tion with few samples. Note that strong correlation with many samples is invalid due to the orthogonality of { and ||=|| (vvd) (cf. Lemma C.5). Condition (B) indicates that has no weak correlation with many samples. For such z, the impact of learning from mislabeled sam- ples, Ti (z), becomes dominant, and the decisions are always aligned. Essentially, for inputs that do not strongly correlate with a few samples or weakly correlate with many samples, the network decisions align with those of a standard network. Because test datasets typically exclude samples similar to the training samples, a network learning from perturbations is expected to produce rea- sonable predictions for many test samples. This confirms the high test accuracy of learning from perturbations (Iyas et al., 2019).
Others. In Appendix E, we derive similar results for other perturbation forms. In Appendix G, we establish Theorem 4.1 without the assumption the last layer of network. Moreover, Theorem 4.2 explains the success of learning from perturbations using random labels. In Appendix H, we attempt to delve into flipped label scenario (i.e., yo -v,, through an empirically supported assumption that standard classifiers focus on non-robust features (Etmann et al., 2019; Tsipras et al., 2019; Zhang & Zhu, 2019; Chalasani al., 2020).
4.3 LEARNING FROM ADVERSARIAL PERTURBATIONS ON UNIFORM NOISES
In this section, we consider noise data scenario which adversarial perturbations are superim- posed uniform noises. The proofs of the theorems can be found in Appendix D. This scenario provides two advantages. First, this scenario prevents the unintentional leakage of useful features. For example, a frog image labeled
horse may contain horses in the background. Second,
this scenario can justify learning from perturbations without assuming N Anyn (xn. 2)1 (g((N, d)) if Σn=1 >n|(zn, 2) = ((g(N, d)). Similarly to Theorem 4.1, we can derive the following decision boundary in the noise data scenario:*
Theorem 4.3 (Decision boundary when learning from geometry innpired perturbations on uniform
moises). Assume 7 R / (3N R 2 Pmax. Let be a one-hidden layer neural network trained
ceometry-inspired perturbations on natural data (ef. Eq. (1) and Definition 3.2(b)) with Set- ting 3.1. For any n + k, if
d
VCd
VCd
< X
S
1(X,, Xx)l S V2Cd, (X., /2C, (4)
3
2
3
2
a2d 33Cdd 12 20 662)2
18Nadv (2d + 3VCd 12v 662) 2 V2Cd 2 2/2C2 (5)
e2
with C := In 1000, then, with xc, the decision boundary of f given by:
Enat Xady ym adv (X,; z) Nody Aadv
pbdy
pbaly (z) ==
(6)
IE An
Effect of learning from uniform noises
Effect learning from perturbations
'In Theorem 4.3, we assume 7 / (3. (2ax) 2 Pmax to define geometry ccometry-nnppired perturbations. To derive the decision boundary Fq. (6), we require only Ineqs. (4) and (5) and need not assume the orthogonality of natural training samples.

---

Published as a conference paper at ICLR 2024
Standard
Input dimensson d'
(Adversaria) nosse sample Nul
Noise
Noise Adversaris! Standard
100
1,000
10,000
10.000
N
Nair 20
Nacr 100
100%
100%
100%
100%
100%
100%
100%
100%
Positive
Nogative
63%
80%
90%
52%
65%
90%
49%
47%
50%
50%
40%
48%
50%
50%
Figure 1: Decision boundaries of classifiers trained multidimensional artificial datasets. The axis vectors and u are defined in Theorem B.1. Left: Boundaries from standard data and noises with and without adversarial perturbations (d 10, 000). The blue circles and orange crosses indicate standard data projections onto this plane. Right: Boundaries across varying input dimensions (fix Nadv 10, 000) and number of noise samples (fix d 10, 000). First row: results from standard data; second and third rows: results from noises with and without adversarial perturbations, respec- tively. Percentages indicate the classification accuracy for standard data.
Similar to Eq. (3), the decision boundary, Eq. (6), consists of terms, representing the effeets of uniform noises and coometry-inspiree perturbations. Although we assume Ineq. (4), each inequal- ity holds with probability least 99.8% (cf. Lemma D.1). Similarly to Ineq. (2), the assumption, Ineq. (5), requires the training adversarial samples to be nearly orthogonal and restricts the pertur- bation constraint to c (( d > Naadv?. Next, we examine the growth rate of the two terms in Eq. (6) and the alignment between the decision boundaries.
Theorem 4.4 (Consistent decision of learning from geometry-inspired perturbations on uniform noises). Assume 7 RRinn Rinnn/ /3N R,mx)) 2 Pmax- Suppose that Ineqs. (4) and (5) hold. Assume ||||| = @(vi). fbby (z) (11), and d Nadv?. Then, the following equations hold with probability at least 99.99%
Nady Aady yady (X =)
Vd Nadv
(bbd((2)
=0
(7)
EnSi Aadv
I An
Nadvy N
addition, if and Nadv are sufficiently large and Nadv 2 N holds, then for any z Rd sgn( (g (z)) = fudy holds with probability at least 99, 99.99%.
This theorem indicates strong alignment between the decision boundaries derived from natural samples and adversarial perturbations on uniform noises. Recall that the natural sample scenario, consistent decisions obtained, except for samples that strongly correlated with few training samples and not weakly correlated with many training samples (cf. Theorem 4.2). In contrast, Theorem 4.4 claims that consistent decisions can be obtained for any input with high probability, A large input dimension d and number of adversarial samples Nadv make the alignment stronger with the speed of Ộ / /adv d) at least.
The assumption bby (=)l 2(1) is mild due its definition (bdx(2) = Anyh (Na, z). We introduce this assumption because the order of pbdy (z) cannot be determined owing to the uncer-
tainty of yn- Note that assume Σm= An (xn, =) (gg(N, d)) if N A 2) (g((N, d)) in the natural sample scenario. Interestingly, even though we underestimate the order of pbdy (z), the effect of learning from perturbations still grows faster than that from uniform noises.
The theorem fails in at most 0.01 % of cases where the randomly generated X,, and the input z are strongly correlated. For example, the theorem does not hold if X,, is identical to However, these cases are rare d is sufficiently large.
In addition, corollary of Theorem 4.4, derive the following theorem:

---

Published as a conference paper at ICLR 2024
1.00
1.00
Accuracy
Accuracy
Adversarial
0.75
0.75
Noise
0.50
00
+X
0.50
0
2,000 4,000
6,000
8,000
10,000
0
2,000 4,000
6,000
8,000 10,000
Input dimension
(Adversarial) noise sample padv
Figure 2: Accuracy of classifiers trained on uniform noises with or without adversarial perturbations for standard data in artificial dataset. The blue solid and orange dashed lines represent the results from noises with and without perturbations (i.e., pure noises), respectively. We fix Nadv 10, 000 on the left and d = 10, 000 on the right.
Corollary 4.5 (Complete classification for natural training samples when learning from geome- try-inspired perturbations on uniform noises). Assume 7 R /3.N Reanx) Z Pmax- Suppose that
Ineqs. (4) and (5) hold. If d and Nadv are sufficiently large and Nadv? 2 VN holds, then a meehiddeen-laye neural network trained on geometry-inspire perlurbations on uniform noises with Setring 3.1 can completely classify the natural dataset {I yn)) with probability at least 99.99%.
This corollary claims that classifier learning from perturbations on uniform noises can accurately classify the natural training samples even though the classifier does not see any natural data during training. This result highlights abundant class features in adversarial perturbations and justifies learning from them.
EXPERIMENTAL RESULTS
In this section, we empirically verify our theoretical results. Detailed experimental settings and additional results for other norms (Lo and Lxx) and Gaussian noises can be found in Appendix I.
5.1 ARTIFICIAL DATASET
In this section, validate Theorem 4.4 and Corollary 4.5 using one-hidden-layer neural networks on artificial datasets. The standard dataset D := {< yn) consists æn and yn sam- pled from ((]- and U({+1)), respectively. Our theorems only require the orthogonality of training samples; thus, using uniform noises as training samples poses no problem. The noise data (X,, y.vad on which perturbations were superimposed, were also uniformly distributed, i.e., X, ([]. Using network trained on and Ing-constrained attack, we generated the Aodd with random target labels yauv E {=1}. Visual- adversarial dataset Dadv := ( godv) Jnmi
izations FF,, Xn, and anddv can be found in A3..A3 A3.
In Fig. 1, the decision boundaries for each scenario are shown in two-dimensional space spanned by the vectors v E Rdd and E Rdd (cf. Theorem B. Theoretically, t and u draw the stan- dard classifier's boundary diagonally from the top right to bottom left. The left panel shows the boundaries of the networks trained on various datasets with = 10, 000. Although the boundary derived from pure noises (orange) differed significantly from the standard boundary (light blue), the boundary derived from adversarial perturbations (blue, green, and red for Aaadv 10, 20, and 100, respectively) became more aligned with the standard boundary the number of samples increased. The right panel shows the decision boundaries across various input dimensions and numbers of noise samples. While the boundaries from noises deviated markedly from the standard, those from perturbations closely mirrored the standard. As the input dimension and ad adversarial noise samples increased, the alignment became stronger. This boundary alignment is consistent with Theorem 4.4.
'The standard boundary deviates from the theoretical prediction when d 100 because Theorem 3.3 is difficult hold in low-dimensional data.
8

---

Published as a conference paper at ICLR 2024
Table I: Accuracy in each scenario. "R" denotes random selection of adversarial target labels, while "D" denotes deterministic selection. In the noise data scenario, yndv is always chosen randomly from labels. Accuracies above 15% are highlighted in bold. The underlined scenarios were also considered in Ilyas et al. (2019).
On natural samples
On noise data
Lo (R)
Lo (D)
L2 (R)
L2 (D)
Loe (R)
Loo (D)
Loo
I.2
L
MNIST
28.4
0.71
92.9
38,4
89.1
10.3
33.2
27.9
31.9
FMNIST
10.5
1.31
54.8
25.1
61.4
22.9
26.2
30.2
26.2
CIFAR-10
54.9
16.8
77.1
42.8
77.2
51.5
9.87
10.2
9.74
In Fig. 2, we illustrate the accuracy of classifiers learning from perturbations on uniform noises for standard data. The accuracy improved the input dimensions number of adversarial samples increased. Given enough of these values, the classifiers could achieve near-perfect classification even though they had not seen any standard data. This counterintuitive success of learning from perturbations aligns with Corollary 4.5.
5.2
Table shows accuracy in each scenario for MNIST (Deng, 2012), Fashion-MNIST (Xiao et al., 2017), and CIFAR-I0 (Krizhevsky, 2009). We used six-layer convolutional neural network for MNIST and Fashion-MNIST and WideResNet (Zagoruyko & Komodakis, 2016) for CIFAR-10. Examples of adversarial images are shown Figs. A16 to A18. In the table, "R" indicates that target label was randomly chosen from the nine labels that differ from an original label and "D" indicates that a target label was deterministically chosen as the next sequential label after an original label. Random selection eliminates feature-label correlations, clarifying the learning impact from perturbations. Under deterministic selection, an anti-correlation between features and labels exists, and high test accuracy emphasizes that perturbations contain label-aligned features.
Table indicates that classifiers learning from perturbations can achieve high test accuracy, beyond the cases in Ilyas et al. (2019). Remarkably, even Lo perturbations, which appear to lack natural data structures, enable network generalization. These results support our theory that even sparse perturbations contain class features. Furthermore, successful learning in the noise data scenario is not limited to the artificial datasets in Section 5.1 but also extends to natural data distributions such MNIST and Fashion- supporting the validity of Theorem 4.3.
Consider counterexamples. For Fashion-MNIST, learning from To perturbations was successful in the noise data scenario, but not in the natural sample scenario. This may be due the nature of Fashion-MNIST, where few pixels may not sufficiently overwrite the inherent features of objects spanning large regions of an image. For CIFAR-10, the noise data scenarios were challenging, possibly because of the domain gap between noise data and natural images, and the classifier's 's inability to extract generalizable features for natural data from noises.
CONCLUSION AND LIMITATION
We provided the first theoretical justification for learning from adversarial perturbations for one- hidden-layer networks trained mutually orthogonal samples. We revealed that various perturba- tions, even sparse perturbations, contain sufficient class features for generalization. Moreover, we demonstrated that in natural sample and noise data scenarios, networks learning from perturbations produce decisions consistent with those of normally trained networks, except for specific inputs.
Our major limitations are the assumptions of simple model, i.e., one-hidden-layer neural net- work, and orthogonal training samples. In particular, the orthogonality assumptions, Ineqs. (2) and (5), restrict the perturbation constraint e to O /d/N). However, in practice, is typically set to O(vd). Relaxing these conditions enhances the applicability of our theorems. Nevertheless, our search provides the first fundamental insight and justification of learning from perturbations, which supports the feature hypothesis and various puzzling phenomena of adversarial examples.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We would like thank Huishuai Zhang for useful discussions. S. Kumano was supported by JSPS KAKENHI Grant Number JP23KJ0789, by JST, ACT-X Grant Number JPMIAX23C7, JAPAN, and by Microsoft Research Asia. H. Kera was supported by JSPS KAKENHI Grant Number 1222K19662 T. Yamasaki was supported by JSPS KAKENHI Grant Number JP22H03640 and Institute for Al and Beyond of The University of Tokyo.
REFERENCES
Gunjan Aggarwal, Abhishek Sinha, Nupur Kumari, and Mayank Singh, On the benefits of models with perceptually-alineed gradients. In ICLR WS, 2020.
Maximilian Augustin, Alexander Meinke, and Matthias Hein. Adversarial robustness on in-and out-distribution improves explainability. In ECCV, pp. 228-245, 2020.
Philipp Benz, Chaoning Zhang, and So Kweon. Batch normalization increases adversarial vul- nerability and decreases adversarial transferability; A non-robust feature perspective. In ICCV, pp. 7818-7827, 2021.
Prasad Chalasani, Jiefeng Chen, Amrita Roy Chowdhury, Xi Wu, and Somesh Jha. Concise expla- nations of neural networks using adversarial training. In ICML, pp. 1383-1391, 2020.
Francesco Croce and Matthias Hein. Minimally distorted adversarial examples with fast adaptive boundary attack. In ICMI, pp. 2196-2205, 2020.
Li Deng. The MNIST database of handwritten digit images for machine learning research. Signal Process. Mag.. 2946):141-142, 2012.
Zhun Deng, Linjun Zhang, Kailas Vodrahalli, Kenji Kawaguchi, and James Y Zou. Adversarial training helps transfer learning via better representations. In NeurIPS, volume 34, pp. 25179- 25191, 2021.
John Duchi. Lecture notes on statistics and information theory, 2023. URL nttps://wel stanford. edw/ cttssssaaassssaasaeeee
pdf.
Logan Engstrom, Justin Gilmer, Gabriel Goh, Dan Hendrycks, Andrew Ilyas, Aleksander Madry, Reiichiro Nakano, Preetum Nakkiran, Shibani Santurkar, Brandon Tran, Dimitris Tsipras, and Eric Wallace. A discussion of "adversarial examples are not bugs, they are features'. Distill, 2019a. doi: 10.2391 5/distill.00019.
http://diiiil.puh//1///aaaa
Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Brandon Tran, and Aleksander Madry. Adversarial robustness prior for learned representations. arXiv: 00945, 2019b.
Christian Etmann, Sebastian Lunz, Peter Maass, and Carola-Bibiane Schönlieb. On the connection between adversarial robustness and saliency map interpretability. In ICML, 2019.
Spencer Frei, Gal Vardi, Peter L Bartlett, Nathan Srebro, and Wei Hu. Implicit bias in leaky relu networks trained on high-dimensional data. In ICLR, 2023.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
Andrew llyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. NewrlPS, pp. 125-136, 2019.
Simran Kaur, Jeremy Cohen, and Zachary Lipton. Are perceptually-aligneed gradients a general property of robust classifiers? In NeuriPS WS, 2019.
Junho Kim, Byung- Kwan Lec, and Yong Man Ro. Distilling robust and non-robust features in adversarial examples by information bottleneck. NeurlPS, volume 34, pp. 17148-17159, 2021.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
10

---

Published as a conference paper at ICLR 2024
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
Apostolos Modas, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. SparseFool: few pixels make a big difference. In CVPR, pp. 9087-9096, 2019.
Seyed-Mohsen Moosavi-Dezfoolli Alhussein Fawzi, and Pascal Frossard. DeepFool: simple and accurate method to fool deep neural networks. In CVPR, pp. 2574-2582 2016.
Aditi Raghunathan, Sang Michael Xie, Fanny Yang. John C Duchi, and Percy Liang. Adversarial
training can hurt generalization. In ICML. WS, 2019.
Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, and Percy Liang. Understanding and mitigating the tradeoff' between robustness and accuracy. In ICML, 2020.
Philippe Rigollet and Jan- Chrrssiit Hütter. High-dimensional statisties. arXiv:2310. 2023.
Hadi Salman, Andrew Ilyas, Logan Engstrom, Ashish Kapoor, and Aleksander Madry. Do adver- sarially robust imagenet models transfer better? In NeurlPS, volume 33, pp. 3533-3545, 2020.
Shibani Santurkar, Andrew Ilyas, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Image synthesis with a single (robust) classifier. In NeurIPS, volume 32, 2019.
Roei Sarussi, Alon Brutzkus, and Amir Globerson. Towards understanding learning in neural net- works with linear teachers. In ICMI,, pp. 9313-9322, 2021.
Jacob Springer, Melanie Mitchell, and Garrett Kenyon, A little robustness goes long way: Lever- aging robust features for targeted transfer attacks. In NeurIPS, volume 34, pp. 9759-9773, 2021a.
Jacob M Springer, Melanie Mitchell, and Garrett T Kenyon. Adversarial perturbations are not so weird: Entanglement of robust and non-robust features in neural network classifiers. arXhv:2102.05110 2021b.
Jacob M Springer, Melanie Mitchell, and Garrett Kenyon. Uncovering universal features: How adversarial training improves adversarial transferability. In ICML WS, 2021c.
Dong Su, Huan Zhang, Hongge Chen, Jinfeng Yi, Pin-Ye Chen, and Yupeng Gao. Is robustness the cost of accuracy?-a comprehensive study the robustness of 18 deep image classification models. In ECCV, pp. 631-648, 2018
Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai. One pixel attack for fooling deep neural networks. TEVC, 2385)828--41,, 2019.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
Lue Tao, Lei Feng, Hongxin Wei, Jinfeng Yi. Sheng-Jun Huang, and Songean Chen. Can adversarial training be manipulated by non-robust features? In NeurlPS, volume 35, pp. 26504-26518, 2022.
Nikolaos Tsilivis and Julia Kempe. What can the neural tangent kernel tell us about adversarial robustness? In NewrlPS, volume 35, pp. 18116-18130 18130, 2022.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In ICLR, 2019.
Francisco Utrera, Evan Kravitz, N Benjamin Erichson, Rajiv Khanna, and Michael W Mahoney. Adversarially-trained deep nets transfer better: Illustration image classification. In ICLR, 2021.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fushion-MNIST: novel image dataset for bench- marking machine learning algorithms. arXiv:/708.07747,20000 2017.
Yua- Yang, Cyrus Rashtchian, Hongyang Zhang, Russ R Salakhutdinov, and Kamalika Chaud- huri. A closer look at accuracy vs. robustness. In NewrlPS, volume 33, pp.
2020.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In BMVC, pp. 1-12, 2016.
Tianyuan Zhang and Zhanxing Zhu. Interpreting adversarially trained convolutional neural net-
works. In ICML, pp. 7502-7511, 2019.
11

---

Published as a conference paper at ICLR 2024
A LEARNING FROM ADVERSARIAL PERTURBATIONS
In this study, we provide theoretical insights into learning from adversarial perturbations (cf. Defi- nitions 1.1 and 3.2). Here, we clarify our research focus in comparison with adversarial training and training with noisy labels, and delve into the implications of learning from perturbations.
A.1 COMPARISON WITH ADVERSARIAL TRAINING
Learning from perturbations, which aims to verify the feature hypothesis that perturbations contain class features, is not related adversarial training, which aims to train classifiers to be robust against adversarial attacks. Learning from perturbations does not focus on (adversarial) robustness. Their concepts and procedures are summarized follows:
Learning from adversarial perturbations (Ilas et al., 2019): Given a dataset D := { yn)} and a classifier f trained on D, we create adversarial examples arddv such that f's prediction becomes y ff Un. i.e., f(r,) yv and f(zddy) = =yal thereby forming a new dataset Dadv == {(x 3/2 () These adversarial examples æddv appear indistinguishable from natu- ral images to the human eye, making Dadv seemingly mislabeled. However, a classifier g trained from scratch on Dadv surprisingly yields high test accuracy on standard datasets that are correctly labeled from human perspective. This counterintuitive generalization suggests that adversarial perturbations, while appearing as noises, contain label-aligned features.
Adversarial training (Madry et al., 2018): Given dataset D := {( 3n)} and an initialized classifier f, adversarial training updates f's parameters to minimize losses over ( ((aad yn)}, which is regenerated at each training iteration. The trained classifier f achieves high test accuracy standard datasets under ad adversarial attacks.
Although both methods use adversarial examples, their goals and procedures are different. Our work attempts to provide a theoretical explanation for the success of learning from perturbations. This is a novel endeavor that differs from extensive studies on adversarial training. To the best of our knowledge, the reasons for the success of learning from adversarial perturbations have not been explained theoretically.
A.2 COMPARISON WITH TRAINING WITH NOISY LABELS
Learning from perturbations is training with noisy labels with adversarial examples. While in training with noisy labels, labels are partially mislabeled (e.g., 20% labels of whole data are misla- beled), learning from perturbations, all labels are mislabeled. In this study, we do not focus on obtaining classifiers with high accuracy under mislabeled adversarial examples. Our study provides a theoretical explanation for why classifiers can obtain generalization ability to correctly labeled test samples from completely mislabeled adversarial examples.
A.3 IMPLICATIONS LEARNING FROM ADVERSARIAL PERTURBATIONS
In this section, we introduce the implications of learning from adversarial perturbations using simple examples. The training, test, and adversarial datasets are defined follows:
D = ((frog img, frog), (horse img, horse), , (cat img, cat)),
(A8)
Drest (f(rr img+, frog), (horse img*, horse), (cat img*, cat));
(A9)
Dadv (f(rro img+ horse), (horse img+ cat), (cat img+ frog))
(A10)
trained classifier f can predict the correct labels for natural images (e.g., [frog img) frog and f (frog img*) frog) but not for adversarial examples (c.g., ffroo img+) horse). Note that frog img+ still appears to frog to humans. Counterintuitively, another classifier g trained from scratch on Dady can correctly predict the classes of the natural test images in Diest (e.g., g (frog img*) = frog).
Ilyas et al. (2019) hypothesized that adversarial perturbations contain imperceptible class features to humans. For example, frog img+ contains not only visible frog features but also invisible horse features.
12

---

Published as a conference paper at ICLR 2024
Table A2: Example of adversarial dataset.
Data index
Visible features
Invisible features
Label
1
Frog
Horse
Horse
2
Horse
Cat
Cat
3
Cat
Frog
Frog
4
Frog
Cat
Cat
5
Horse
Frog
Frog
6
Cat
Horse
Horse
Consider training on the adversarial dataset Dady defined as Table A2. Through training, clas- sifier g ignores visible features that are uncorrelated with labels and learns invisible features that are correlated with labels. Since natural test images contain invisible features of the correspond- ing classes (e.g., a frog image contains human-invisible frog features), this classifier can provide correct predictions for them. As result, the classifier trained on dataset that appears completely mislabeled humans achieves high accuracy on natural test datasets.
B DECISION BOUNDARY OF ONE-HIDDEN-LAYER NEURAL NETWORK
B. STANDARD TRAINING
To formulate learning from adversarial perturbations, we use the theorems presented Frei et al. (2023) (similar results are shown in Sarussi al. (2021)), which addresses the implicit bias of one-hidden-layer neural networks under gradient flow with an exponential loss. This theorem does not directly address adversarial attacks, adversarial examples, learning from perturbations. We leverage this because of the tractable form of a decision boundary. The main results of their study summarized as follows:
Theorem B.1 (Rearranged from Frei et al. (2023)). Ler := {(In, un) C. Rd x {+1}
be training dataset. Let Rmax max, |æ 11. Rmin
minn [ l. and Pmax
max,3 (K Rg)l. A one-hidden-layer neural network f Rd - is trained on D with Ser-
ting 3.1. 2 / /3N R 2 Pmax then gradient flow on f converges to lim4 [W(ll wal
W
waalpp where W = (V).-. mm/2; U1,.... umm/2) satisfies
Vn E [N] ynf Wsld) =1
(A11)
0i Unn/ 1
1
Σ
Xn
An
(A12)
Vm
Vm
n:
U1 Unn/
An
(A13)
m
m
where An E 2122 2n R
for every [N]. The binary decision of f(z; Watd) is also given
by:
N An (2n,
sgn (f(z; Wald) sgn (xb)) where pbdy (z) =
(A14)
n=1
The theorem provides three insights: (i) Although there might be many possible directions W W|| that can accurately classify the training dataset, gradient flow consistently converges in direction Wsstd regardless of initial weight configurations. (ii) Given that Wstd consists of maximum of two unique row vectors, its rank is constrained to two or less, highlighting the implicit bias of the gradient flow. (iii) The binary decision of (2; Wstd is the same as the sign of the linear
13

---

Published as a conference paper at ICLR 2024
function fody (z), indicating that f(; W has linear decision boundary. This theorem requires nearly orthogonal data, which is typical characteristic of high-ding sigh-dimensional data.
Note that in Frei et al. (2023), the binary decision boundary is given by:
pbdyalt (z)
Vm
(A15)
2
2
To derive Eq. (A14), we rearrange the above equation follows:
(bdyall (z) = V
Xn
(A16)
2
migga =+1
=-1
v m
1
An
An
(A17)
2
Vm
V
ntyn=
+
7
A Bn
An
(A18)
2
(i:30, 11
1+7 7
An Tn.
(A19)
2
Thus,
sgn (f(z; Wstd)) sgn (fbdyalt(x))) sgn
Σ Anyn
(A20)
B.2 LEARNING FROM ADVERSARIAL PERTURBATIONS
Theorem B.1 does impose any assumptions on training dataset other than orthogonality. Thus, it can be adapted to a dataset with adversarial perturbations as follows:
Corollary B.2 (Learning from adversarial perturbations). Let Dadv = {(xxddv yadv Naad
In=1 C
Rd x {+1} be training dataset. Let Raddy = max, [| [], Raddy min, [aaadv Ib and Pmax = maxny4 Karddy ask arddv)) one-hidden-layer neural network Rdd R is trained the
dataset with Setting 3.1. If " /(3N Rady 2) 2 pudyy then gradient flow on f converges to
lim4 [[((]] [[ where Wradv = (wddy ,..., yady uu 2odl)) satisfies
((t) Wade
Vn E [N] : yn
f(z adv, Wady =1,
(A21)
ugddv
m//2
Σ
aadv x
adv
Aady andy
(A22)
m
m
migadd =+1
n:
undv =
adv u m//
Σ
Addy adv ao
A adv xo
(A23)
Vm
naggadv =-1
Rayadv ++
where Xadv given by:
for every [N]. The binary decision of f(z; Wadv) is also
2Rudy " 2ny² Teway?
N
sgn (f(z: Wadv)) sgn (pball (=)). where
pbay (z)
Σ n=1
Aady y (p. 2). (A24)
=
This theorem establishes the foundation for learning from adversarial perturbations. The orthog- onality assumption, model weights, and decision boundary depend on a definition of adversarial perturbations.
14

---

Published as a conference paper at ICLR 2024
C PROOFS OF THEOREMS IN SECTION 4.2
C.I DECISION BOUNDARY OF LEARNING FROM GEOMETRY-INSPIRED PERTURBATIONS ON NATURAL SAMPLES
In this section, derive the decision boundary when learning from seometry-inssiieee perturba- tions on natural samples, Theorem C.2. Theorem 4.1 is a special case of Theorem C.2 with the assumption of many training samples. Lemma C.I shows an orthogonality condition of training samples with geometry-inspired perturbations, which required to derive the decision boundary using Corollary 3.4.
Lemma C.1 (Orthogonalitty condition for learning from geometry-inspired perturbations on natural samples). Consider the geometry-insping perturbations defined in Eq. (1), Let
3R max + 72 RRmin
C ==
(A25)
7 283 Rim VI
Suppose that the following inequalities hold:
(Buin -)) [N(Hnaete]²
2ERimax - 2 Pmax
N S
C²
H
3N( 8N ctcc
(R -e)a
-2 -2 - 6² 2 Pinx
VN
Te
C²
<
<
S
R
(A26)
7a PReiio
-2 --ggete) 2
2 - 22 Pmaax
N >
3N "ggetee cte))
VNC
Remin
Then, the following inequality holds for any {(In, Br Mim and f2 Jom=
3 padv
2 P
adv
(A27)
3N
Rady
max
Proof. The proof flow is as follows:
1. Ineq. (A27) does not hold for some {(I,, bn) and fondy J if c >> Ruin.
2. Ineq. (A27) does not hold for some ((x,, Vn J and Loady N if Pmax
20 R
Rygia
3N I
3. Ineq. (A27) holds for any {E Mn) ) and (vndy L if Ineq. (A26), e S Rmin and 7 rea Regin hold.
Pmax
I
3N R
maax
4. Ineq. (A26) includes e S Rmin-
5. Ineq. (A26) includes Pmax
Riuon 3N Reax
With = DM An we can represent the geometry-inspired adversarial example as follows:
adv z
E. + cyn
adv
(A28)
||
Assume > Rmin: Let l == arg mina ||
We show that Ineq. (A27) does not hold
In = ys yadv = yadv uady = sgn( (I)) qi) = UI, and Pmax = 0. A lower bound of the maximum inner product
adv 2 (or .e egg
Tba ||
q
+ eg
adv
on. ||q||
+ 2 adv adv 2 2 (A29)
y y/
For example, 21 : 0, 02 = 20, 0, 0), 33 = (0, 0, 1, 0). 24 = (0, 2), 31 = 1, 32 == 1
83 1, f/ 11 yf adv
1, adv
adv
1, V
1,
2, and
1
15

---

Published as a conference paper at ICLR 2024
Note that
1)
8gi
nn
|
sgn (gnnnalllllaaa ||x = Dn-
(A30)
An upper bound of the minimum norm
Radnn
R2 Rinin
2:
01:
q
>
+ S R +
(A31)
We can rearrange Ineq. (A27) using the above two bounds as follows:
7a8 Radv 4
Redv&
R² Ro +
3N Radv 2 max
P adv
P Pmax
adv
3
2<
3 < 0.
(A32)
Assume Pmax 7 R /3N R Note that the decision boundary of a classifier trained on such samples does not always converge to fbdy == Σ Anyn (2n, since the assumption of Theorem C.2 is not satisfied. However, for the definition of geometry-inspired perturbations, irrelevant whether the decision boundary converges to fbdy, We can define coometry-inspired perturbations long A, is (uniquely) determined by Eq. (A11).
Let 21 := 1, Ø2 == -1, 1, y1 == 1, and y/ == -1, which satisfy Pmax > 7
3R4 B /3N R As
defined in Theorem C.2,
A1 + 7d2
A2 1
u.
(A33)
vm
vm
Thus,
f(x) = (((), + 722)a)
p(-(A2 + td1)a)
(A34)
2
2
As defined Theorem C.2, A and A2 satisfy the following simultaneous equations:
((A))))a) o( (A2t-22))1)
Φ (((A)
al a(A2t7d1)
(A35)
-1
2
2
Solving this,
1
A = A2 = 2
(A36)
Note that these satisfy \1, d2 E (1/2Rg
max: 3/2,2R2 R2min). Let y == -1 and y = 1. Then,
q/1l4/l = 1, _gdd := := e, zadv ;= 11++ e, pady Rndy = |1 el. and pady (1 2) this
situation, Ineq. (A27) does not hold for any > O.
Assume e < Rmin and Pmax < 73 R24 mijn /3N We write the lower and upper bounds A Amin 1/2R and Amax = 3/2 R respectively (cf. Theorem B.1).
(Preliminary) A lower bound of the norm of q is
|qll
An
An An|1
Σ kigtnn
AA. (arns arx))
(A37)
V N NAmin (Amin R2
*mmaxPmax)
(A38)
Rmin v(1 - N)N
(A39)
2R2 2aa
An upper bound of the inner product between x, and q is
N
3R2 max
RR2 Piin
(Dn, Aa σa) SAmax (n N Npmax)
+
(A40)
2- R2
2
16

---

Published as a conference paper at ICLR 2024
A naive upper bound of the inner product between En and q/l|gl is
Up
S Rmax.
(A41)
That be also obtained follows:
q
3 7 R
C
nn
(A42)
722 12
1(1 (1->)N
VN
Note that
2 Riuax
N
C²
VN
Rminn
S
C
Rmax
C²
<
C²
(A43)
VN
Raax
VN
<
Rauin
N
R2
C²
Thus,
Rmax
SNS
In
max
(A44)
qqq]
(otherwise)
(Upper bound of inner product) An upper bound of the inner product is
adv
adv) Spmax + 2c Ik
(e(e xn,
q
+
(A45)
||
Pmax + 2e Rmax +
(N
C2 Rias
(A46)
Pmax + 2 C
VN + 6²
(otherwise)
(Lower and upper bounds of norm) The norm of the geometry -emmeerry-nssiree adversarial example is
| + 2eyadv
Ini
||ll|
q
+
(A47)
Under S Rminn trivial lower and upper bounds of the above norm S || [edd I
Rmin
Rmax +E.
(A48)
Now, we have the following three lower bounds of the norm of x. (i) V R
2c 2cRumax 2
C Re (iii) Rmin - for 6 S Rmin- Since (Rmin - c)² (R2 2eRRmax + +22 O, (iii is always tighter than (i), addition, since
C² for N S Re (ii) / R
VN + 2 for N
C
(Rmin c)² (R2 2 /N 2) under
C²
N
(iii) is always tighter than (ii). min
C²
TP
Thus, under S Rmmnn
Rmin
(N
Pin
(A49)
R2 R -2 -2C
C
(otherwise)
VN
An upper bound of the norm is
Rmax +
(N (otherwise)
adv n
(A50)
(V REnxx + +2C VN
C
+ 62
(Orthogonality condition) Using the above bounds, always holds for any {(x,, yn.) W and {yndv N
derive Ineq. (A26) where Ineq. (A27)
Inml-
4. We prove that Ineq. (A26) implies < Rmin- A common upper bound of the left term of Ineq. (A26) is 72 (R + 2)/3N e2. This bound monotonically decreases with e and below zero at Rmin- Thus, Ineq. (A26) does not hold for > Rmin-
17

---

Published as a conference paper at ICLR 2024
5. Here, prove that Ineq. (A26) implies Pmaxx S 70 Kminn/ /3N R From the above discussion, assumne S Rmin- In this case, Rmin- -E I Rmin. Rmax Rmaxte R I Rmaxx +2 C e+
VN
Pmax S Pmax 2 max +6², and Pmax S Pmmx +2 VN s+e² are trivial. Thus, the first two inequalities include Pmaxx S 70t R m /3N Renax. Then, we consider the following inequality:
3 R
min
( 2 2// + =22²
2
C C-
(A51)
3N 3NI2
3N max + +2 + +22)
VN
max
VN
With = 2 2 (2 0).
VN
71th R Rinn
7
A)2
2 min
2 VN
22)2
A 2
A.
(A52)
3N R
3.N (R + A)
3N 3N + A)
Rearranging this,
7 R min + (3N Riax 27 RT2 )R + (3N - ) R A > O.
(A53)
Thus, the above inequality holds. Finally, the claim established.
We have represented an upper bound (In, q/llgl)) as C/VN. Alternativlly, we can use Punax to represent upper bound of (In, q/l/gl)> as follows:
3R
(Reax Npmax)
C²,
(A54)
R v N 2 3N R2 R maxpmax)
Using this bound, for a sufficiently large N, we can obtain a similar result as follows:
7 min + 20' 2 Pmaxx
(A55)
3N R2 max + +C'
As Ineq. (A54) tighter than Ineq. (A42), Ineq. (A55) is tighter than Ineq. (A26). However, to interpret the restriction Pmaxx. we employ Ineq. (A26), which contains Pmax only in the right term. The left and right terms of Ineq. (A55) include Pmax, and more complex to determine the constraint Pmax-
Theorem C.2 (Decision boundary when learning from -inspirr- perturbations on natural samples). Let of be a one-hidden-layer neural network trained on geometry-inspire perturbations on natural samples (cf. Eq. (1) and Definition 3.2(a)) with Setting 3.1. If Ineq. (A26) holds, then, with t + oo, the decision boundary of f is given by Eq. (3).
Proof. By Lemma C.I, Ineq. (A26) holds, we can use Corollary 3.4. The decision boundary is
N
(gn(f(z; Wadv)) = sgn
X udv addv yadv (anidv 2)
(A56)
N
adv apd (Irn, 2) + sgn
Σ
Aady
y eyjadv
||qli 1
(A57)
n
n=l
sgn
A Un
adv adv (10m: 2)
Aadv
e
||al|
)
(A58)
-= Xady your (anns 2)
N
{q, xx)
sgn
ΣN Andv
+
||q1l
(A59)
N Aadv yodd (In.,
pbdy
sgm
MN Aadv
|1q
(A60)
18

---

Published as a conference paper at ICLR 2024
Theorem 4.1 (Decision boundary when learning from geometry-inspired perturbations natural
samples). Let be a one-hidden-laye layee neural network trained on geometry-inspired perturbations natural samples (cf. Eq. (1) and Definition 3.2(a)) with Setting 3.1. If C² R
and
7 R V + 622
C
-e e Pinax
(2)
(N + VN (
VN
3R Run
R
with C: =
then, with + oo, the decision boundary of f is given by
Σ Aadv padv (Ins z)
pbdy (2)
plady (z) ==
(3)
Σx= Aadv
| An
Effect of learuing from mislabeled natural samples
Effect of learning from perturbations
Proof.
This is the special case of Theorem C.2 for N C /a/
C.2 LIMITING BEUAVIIR OF LEARNING FROM GEOMETRY-INSPIRED PERTURBATIONS NATURAL SAMPLES WITH DETERMINISTIC LABELS
In this section, we consider learning from geometry-inspired perturbations on natural samples with deterministic adversarial labels. In Proposition C.4, we show that the effects of perturbations and mislabeled natural samples grow
same speed with respect to an input dimension and the num- ber of training samples, suggesting that learning from perturbations is feasible on high-dimensional dataset with many samples. To prove Proposition C.4, we first prepare Lemma C.3.
Lemma C.3 (Order of norm of weighted sum of training data). Assume 7 Ri /3N R2 max 2 Pmax
and [ || O(vd) for any E [N]. Then,
N d
An Ur D
V
(A61)
Proof. By definition in Theorem 3.3, An = ((1/d). By the assumption, Piax = Odd/N). A lower bound is
Σ
A Un
An
An An||z 12 + Σ
(A62)
n=1
Σ An
An Anl1an 112
Σ
AePinax
(A63)
N
(A64)
Similarly, upper bound is O (/N/d). because the following incquality holds:
Note that the radicand of the lower bound is positive
R22 Minin
722
(1 R) O.
Az 11122111
AePmax 2
(A65)
2R2
2 max
2 max
Proposition C.4 (Limiting behavior of learning from geometry-inppreed perturbations on natural samples (deterministic label)). Suppose that Ineq. (2) holds. Assume ||œ,||| = +(vd) for any
19

---

Published as a conference paper at ICLR 2024
n E [M] and ||||| = (Vvd). Assume
N
N
(an 2)1 = (N), =
Anyn (n 2)
= ( (N, .d),
(A66)
= (((2((N Σ Anyn (m 2)
(g2 d)).
(A67)
where 9i and 92 are positive functions of N and d. Then, the following statements hold:
(a) For any [Tı(z)] = (gs((N + [T2(z)] = O(os(N, d)), where 93 is a positive
function of N and d.
(b) For Σn
= ((d/ and [T2(2)) (dd/VN). (c) For (1) [T) (2)) = (dd/N) and [T(()) = O(d/N).
Proof. Under Ineq. (2), - d/NN) Because we can set freely under Ineq. (2), we consider == O ((/d//)) which maximizes the effect of learning from perturbations.
(a) By An ((1/d) and Aadv = (11/d) (cf. Theorem 3.3 and Corollary 3.4),
N
An 2)1 = =O(((N,) +
Aa (ar 2)1 ((g(N,
(A68)
1=
Under the assumption,
= O(g(NN Aa =
adv ((0 z)11 [[gg(N,
(A69)
1=1
==1
An Un [nn 2) = =O(g(N,
Aady yad (I x)
=O(g(N,d))
(A70)
By Σ> Anyh Rnl1 = O( N/d) (ef. Lemma C.3)
[T(()] ( d))
θ dg(
(A71)
(
(gg(N, d)) = - Mg(NNdl
[2(2)] =0
(A72)
N
N
(b) Since Σ An (2n, 2) = O(vN) and >n Xady ( 2)1 O(VN), T1(2) O(d/VN)
and (x ((d/vN)
.N (c) Since Σm Azl , 2) (1)) and >
bm= Aady ( ((1,, O(d/N) and
(2) (d/N).
C.3 LIMITING BEHAVIOR OF LEARNING FROM GEOMETRY-INSPRER PERTURBATIONS ON NATURAL SAMPLES WITH RANDOM LABELS
In this section, we consider learning from geometry-inspired perturbations on natural samples with random adversarial labels y ~ (+1).. To prove the key theorem, Proposition C.8, we prepare Lemmas C.6 and C.7. In addition, we consider Lemma C.5 to prove Lemma C.6. Finally, based on Proposition C.8, we demonstrate the matching of decision boundaries between learning from standard samples and adversarial perturbations, Theorem 4.2.
First, show that assumptions ||ж||| @(vd) and (x,, æx)1 OddNN) restrict the correla- tion between & and {x, 1. In other words, z cannot be strongly correlated with many training samples. This lemma is used prove Lemma C.6.
20

---

Published as a conference paper at ICLR 2024
Lemma C.3 (Restriction on correlation). For any n, k E [M * k. assume || = @(vd). || = ((vd). and (æn, 24)1 O(d/N). Then, there exist at most O(min(N 2a, 1omin(NN22,,00 NN) instances of n that satisfy (2 2) (N d with a S 0 and 1.
Proof. For each let th,, == (gn((an; 2)). For a S 0 and B < 1, denote the number of samples such that (mm, z)| = ((Nad) holds by [N],, == {n E [N] (T =) = ((N=d))) We define
8 S 1 such that [[N]a.sl = @(N*). Then,
(an, z) = Σ REIN]a.
Σ
())
E
-(N% = D(Natàd d
(A73)
ne(N]a.e
nE[M]a.e
By the Cauchy- Cauchy-Schwarz inequality,
E N
(Un 2)
Σ
Un
S
Σ
Un
||=||
(A74)
MEIN]a,
Note that
Σ No,
un
Σ
|
+ Σ
Σ
(A75)
nEiN]a.e
NE nE(N]s.e kznf
=
(A76)
=o(V
(A77)
Thus, E EnENNoa (Dn = O( O(V Comparing this with Eq. (A73), + 8 s 6/2 +
-2a.
Then we compare the growth rates of Σ (X z\| and Ex (wns z)² evaluate the growth rates of [Ti (z)l and [z)) in Proposition C.8.
Lemma C.6 (Comparison between sums of absolute and squared inner products). For any n, k E [N], n + k, assume |æ,||| @(vd), || @(vd), and (x xx)) Odd/N). Then, the growth
rates of Σ ( 2)I and ((1/d) Σm (In: 2)² are the same and only if (Ix, 2)1 for every n, there exists such that ( z)1 ((d) and Em.(...=)) *((d) ((0,, 2)] Od).
Otherwise, Σn (Bn, z) grows faster than (1/dd) E (wn, z)2.
Proof. First, we summarize the content this proof as follows:
(A) If (x,,, =) = 0 for every n, then Σ (an, z} = ((1d)) (Mn, 2)2 0.
(B) Assume that there exists n such that (In, z) 0.
(B-a) If there is no such that (a,, z) (dd), then ΣN (2 x)1 grows faster than ((/d)) Σn ()m,2)²
(B-b) Assume that there exists such that (xn 2\| O(d).
(B-b-I) If Emilee (x))((..))))))) ( ((on z)) s(dd), then Σ, (In, grows faster than
(LLdd) Σ 2)2
(B-b-II) If Ems 211 (20n, 2)
O(d), then Σ (10 z)1 O(d) and
(1/d) Σ (D 2)² (dd).
21

---

Published as a conference paper at ICLR 2024
We use [Ma in the proof of Lemma C.5. Denote the number of elements in [M] 3 by C(a, 9) || Denote the set of (a, (3) by = {(o, 3) : C(a, 93 > 0}. We can write Σ (Tn= 2)1
and ( (1) En= (Fn, z)² as follows:
N
Enn 2) =
Σ ((,,
(A78)
n=1
(a,0)ES
N
θ
nn 2)²
Σ
C(a, ((a,3)0(N20
(A79)
#=1
(0,8)ES
(A) This is trivial.
(B-a) Assume that there exists such that (1r > 0. Because Nod grows faster than or equal to N2a for a S and B S 1, Σ (amns 2)1 grows faster than or equal to (1/d)) Σn (In,22 2)² The growth rates of Nod and 220 d28-1 are consistent if and only if 0 and 3 = Thus, there is no n such that (ax,, z)1 = ( i.e. C(O, 1) > 0, then Σ Kx =} grows faster than ((1dd) E 2)²
(B-b-I and -II) Assume that there exists such that Kan,, z)1 (d)). By Lemma C.5, C(O, (1). Let S' = SS {(0, 1)}. The above equations can be rearranged as follows:
( =0(d+
Σ
Cla,3)0(N4)))
(A80)
(a.8)ES'
N
Pnn 2)2 +
Σ
(la,,))
(A81)
(a,D)ES'
Since d grows faster than N2 for 0 and 3 < 1, E E(a Cla, 3)0 grows faster than E(a,))Ss C(a, (N 28-1). La, C(a, ( d determines the growth rate of Σm (T,, 2)), i.e., E(a,))S Cla, ()=( ((d), then Σ (In, =) grows faster than ((1/d) E (Zn, 2.? In contrast, E(a C(a, () dd) does not change the growth rate of ΣN (K,, 2)1, i.e., E(a,))s C(a, ()) = (d)), then EN (T,,, 2) = (d) and ((1/d) EN= (In, 2)² (d)); namely, their growth rates are the same.
Then we prepare concentration inequality to evaluate an upper bound of Ti (z) in Proposition C.8.
Lemma C.7 (Concentration inequality). Let LN be N E N independent random variables. Assume that Cn is sampled from [an, bn]] and B[æn) for each n E [N). Then, for I >> 0,
N
IP
t
2 exp
Σ bb, an)2 22n)-11 -t- n=1
(A82)
Proof. By Markov's 's inequality, for L. >
O.
E
exp
Em= I.n)
IN E [x)p(aw))
F
(A83)
el
By Hoeffding's lemma,
N
N
exp((bn - a
1 N
an,) -1)
P
1
<
exp
(bn
(A84)
et
p=
n=1
We derive the same inequality for TP[- >N F. 2 1..
22

---

Published as a conference paper at ICLR 2024
While the concentration inequality, Lemma C.7, is weaker than Hoeffding's inequality, use it for a simple proof of Proposition C.8. The proof of Proposition C.8 requires us to consider the probabil-
ity PP[ PP And yaul
nI z)
>
2n=1 An ka z)[]. Using Lemma C.7, this can be represented
follows:
P
Σ
adv
(Inn z)
Am I =3ا|
n=
exp
1
Σ
An
xpdv?
(ann 2)²
Anl Anl(ann x3)1
(A85)
Using Hoeffddingss inequality, it can also be represented as follows:
N Ar XI 2)|
s 2ccxp (- (ENY Aa (a 2)1)
adv adv (In; 2) n
(A86)
2 m= Aadv (sin: 2)2
In the former case, the growth rates of En Aadv? (I,,, and En Au (an 2)1 are the main concern (cf. Lemma C.6). In the latter case, the focus on the growth rates of Σx=1 spdva (oo 2)²
and (En=) An / =) which present more complex scenario than the former. Thus, we use Lemma C.7 to prove Proposition C.8.
Proposition C.8 describes the limiting behavior of the two components of the decision boundary: the effect of learning from mislabeled natural samples (z) and from perturbations T2(2).
Proposition C.8 (Limiting behavior of learning from inopprer-inspired perturbations on natural samples (random label)). Suppose that Ineq. (2) holds. Assume ||x.,]] || = @(vd) for any n E [N]
and |||| = O ((V)). Suppose that yadv is randomly sampled from { for each n. Assume
N
Xn 2)1 -(g(NN
Σ
An (xn, 2) (g([N, d)).
(A87)
n=1
n=1
where is a positive function of N and d. Then, the following statements hold with probability at least 99%
(a) Assume that there exists such that (W 2>}>>
> O. If there is no n such that [ 2) (d) or Ens =1)00))))) (K 2) O(d) does not hold, with N, d + co, then
[2(2)] > [T](
(b) For N O(1 / NN) [T](2] OddNN) and =
(c) For O(1)=1, (=)) = Odd/N) and [T2(=) = Odd/N).
Proof. Similarly to the proof of Proposition C.4, if if NY An 2)1 = ((g(N,d)),
N
[2(2)] = 0 [dg(N.))
(
[T) = o
adv adv
(Iin 2)
(A88)
N
N
(a) By Lemma C.7,
N
P
adv yody (In, 2)
> t < 2exp
1
aadv
(En, xx2 -t)
(A89)
2
n=1
Thus, EN Xady gadd (In, 2)1 Okh(N, d)) Eny Aadva (x,,, 2)2 O(h(N, where
h(N, d) is a positive function of N and d, with sufficiently high probability. By Lemma C.6, if there is no n such that (a,,, 2) (dd) or =l K 2) O(d) does not hold, g(N, d) grows faster than A(N, d). Thus, [T)) grows faster than (z)]; namely, if N, d + oc, [72(2) becomes larger than [7 (T)).
23

---

Published as a conference paper at ICLR 2024
(b) The proof of [2(2)] = ((d/VN) can be found in the proof of Proposition C.4. For
m= Na. Σx= Andv² (a z)² = (1). Thus, h(N, d) = O1), and [Ti()) =
(c) The proof of [T2(2) = (dd/N) can be found in the proof of Proposition C.4. For 2 = (1)
E 2ndv? (In, 2)² (1)) Thus, ((N, d) (1), and [T> O(d/N).
In Proposition C.8, we show that if N, d + oc. the effect of learning from perturbations (x)) exceeds that from mislabeled samples (2) except for specific inputs. Consequently, we can
justify learning from perturbations on natural samples as follows:
Theorem 4.2 (Consistent decision of learning from geometry-inspired perturbations on natu-
ral samples), Suppose that Ineq. (2) holds. Assume |I = @(vd) for any n E [N] and ||||| ((v)). Suppose that yadv is randomly sampled from {+1} for each n. Assume Em= An.nn(an 2) ((g(N,d) d)) if " An (ann 231 ([g(N, d)), where g is a positive function of N and d. If there is no n such that (0 z)1 = (dd) or En: (2e(( (() (2 2)1 =
(dd) does not hold, with N, d + oo, then sgn( pbdy (=)) = sgn( pbdy (z)) holds with probability at least 99.99%.
adv (z) = [Ti = [T((2)] = fbay = 0. As- sume that there exists n such that K x)]l (a z)1 = ((d) or Ex: =)))))))))) (En, x)1 = O(d), with N, d + co, then [T((2] > (2)
Proof. If (a,n, =)1 = O for every n, then pbdy
By Proposition C.8, if there is no n such that
with sufficiently high probability; thus, sgn(S obiyy (z)) sgn( pbdy (z)).
D PROOFS OF THEOREMS IN SECTION 4.3
In this section, we prove Theorems 4.3 and 4.4 and Corollary 4.5. The proof flows of Theorems 4.3 and 4.4 follow Appendix C. In addition, we derive Corollary 4.5 as natural consequence of Theo- rem 4.2.
First, we summarize the properties of uniform random variables, which are required to consider the orthogonality condition of perturbations on uniform noises.
Lemma D.1 (Properties of uniform random vectors), Let n IN C |1 be N N inde-
pendent random variables sampled from the uniform distribution ((-1,11)*. Let z E Rd be a constant vector. Then, for positive constant > 1/N, the following inequalities hold:
d
VdlntN
2
N
(a) P
max
X
(A90)
3
2
tN
2
(b)
IP
max (X n, Xxa1 S /2d In
1
(A91)
iN
2
N
(c) PP max
(Xns x) S 1ntNN|1
1
(A92)
tN
Proof. Let a > 0 be a positive constant.
(a) By Hoeffding's 's inequality with E[x², n
= 1/3,
2a²
X
> a
< 2 exp
(A93)
3
Thus,
d
(pl
2
P max ||x
< =
|x,]
X 112
a
(A94)
3
3
24

---

Published as a conference paper at ICLR 2024
d
1 - P
(A95)
3
2u0² (-d) d ))
1 2 exp
(A96)
For a = (dl((N)/22 with > 1/N,
2 (1 1
N
PP max
Xn 1|
3 2 VdlntN
(A97)
LN
(b) Similarly to (i),
a²
Pl((X, Xx)
52exp
(A98)
2d
a
max (X Xx) sa
1
2
exp
(A99)
2d
2
N
P max (Xn, Xx)l S V2dln 2 1 LN
(A100)
(c) Similarly to (i)
a
Pll(X nn 2)1 2 a) < 2exp
(A101)
21
a²
P max (X z)| Sa sa) 1- 1xxp
(A102)
211211
2
N
max (Xn, 5 //2nntN
2
(A 103)
tN
Theorem 4.3 (Decision boundary when learning from geometry-inspired perturbations on uniform
noises). Assume x3 R (m) Z Pmax: Let be one-hidden- layer neural network trained
on geometry-inspirer perturbations on natural data (ef. Eq. (1) and Definition 3.2(b)) with Set- ting 3.1. For any n F k, if
d
VCd
VCd
X
11 S
3 +
1(X,, Xx) S V2Cd, (/nn S V2C,
(4)
3
2
2
(2d -3VCd - 12 662)2
2 V2Cd 2 2022 + e²
(5)
18Nadv (2d + 3v 3vCd + 12222c 662)
with C In 1000 then, with cc, the decision boundary of f is given by:
M Nadv Xadv yady (Xn,2)
pbdy (z)
pbdy (z) ==
(6)
ENuidy Aadv
D An
Effect learning from uniform noises
Effect learning from perturbations
Proof.
Let q = >N
I An The norm and inner product are
( =11 X 2eyant adv
X
q
+
+
(A (A104)
|aal
agv ; agdev =(x,, Xx) + ey adv
Xx.
+
ey
Xxx
q Tall
+ 2yndy yoddaapa
(A (015
[ql
25

---

Published as a conference paper at ICLR 2024
Thus, under Ineq. (4),
R 2
VCd -2V20e +
d 3
vCd
2v 2Ce +C
(A106)
3
2
Pmax Iv2Cd + 22/2c+ + c.
(A107)
Using these bounds, can rearrange 7 Radi 4 /3Naad Radax as follows:
Rady min
(2d - 112d-3/CCa 3/Cd 12/20 6e2)2
(A108)
3/ddv Radv max
18Nadv (2d + 33 12v 6e
Thus, if Ineq. (5) holds, then 70 Read'' A /3/Nadv "max 2 Pinax holds, and we can use Corollary 3.4. The decision boundary can be derived similarly to Theorem C.2.
Lemma D.2 is used in the proof of Theorem 4.4.
Lemma D.2 (Upper bound of sum of squared inner products). If || = 0(vd), ||||| || = e(va).
and (I,, mbmi = (dd/N) for any k E [N]. + k, then E (In 2)² = O(d²).
Proof. With vi sgn (enn((2g) (In 2)), by the Cauchy-Schward Snwaaraauanuil inequality,
(Bns z)1
Bn z)
(A109)
2n
|||||
(A110)
N
|| | 11
Σ
Σ kg
Unnta (was a2)
(A111)
(d)
(A112)
By the Sauchy-Schward inequality,
N
N
Σ n=l
ans 2)²
((In; W). z)
(A113)
n z)mr
(A114)
n=1
(n 2)
1
Σ
(a 2) (arx. 2) (2 2x)) |=11
(A115)
Now,
N Σ
N N
(nn z) (ark: () xx)) <
Kn 2) 2))1(0nn ax)
(A116)
72
n=
k=1
=0 d
Σ (x 2}}
(A117)
=d(d²).
(A118)
Thus,
Dnn 2)²
(dd²) Σ
mny 2)2 + (dd))
(A119)
26

---

Published as a conference paper at ICLR 2024
Let E (I:: 2)² dfN for constant Ç E R Using this,
N
Un 2)² = (m dd)).
(A120)
n=1
((NddP)
If < S O.
the left term grows faster than the right term, which contradicts the equation. Thus,
Theorem 4.4 (Consistent decision of learning from geometry-inspired perturbations on uniform noises). Assume 7 R /3N (iuax) Z Pmax. Suppose that Ineqs. (4) and (5) hold. Assume
||=|| = @(vd), Iffdd (z) (2(1), and d > Nadv?, Then, the following equations hold with
probability at least 99, 99%:
Nwidy m==
Ande yadyyaat (X z)
Vd Nadv
f (2)
-0
(7)
EN Aadv
I An
VNad N
In addition, if d and Nadv are sufficiently large and Nadv 2 N holds, then for any z E Rd
sgu(Jadv pbay (z)) = sgu(sbdy, (z)) holds with probability at least 99%..%
Proof. By the definition in Theorem 3.3 and Corollary 3.4, A, ((1dd) and Aadv O(1dd)
Left term. Consider the limiting behavior of |Ea= Xadv ya (Xn: 2)1- First, we provide an incorrect idea for clarity. By Hoeffding's inequality with respect by Nar and ( for
t > 0,
Nadv
1 2 Nadd n=1
IP
Σ
adv adv (Xn, 2) 2 t
<2exp
(A121)
n
Nady
Σ Aadv 2?
n=1
=2exp
(A122)
2 2I Nadr
2adv211z11?
I=
=o exp
(0xxpp
di2
(A123)
Nadv
From this incquality, one might consider that |En=1 Aady gadv (X,, z)1 = O( Nad /d) holds with sufficiently high probability. This is incorrect because the above rearrangement does not take into account the orthogonality assumption on {X,] Naddy i.e. (X,,, X Od/N) for n # k. We then provide a correct estimation. By Hoeffding's 's inequality with respect to {g ad Nadv Jn=l
Nadv
t Aadv? (X 2)2
P
add yadv (Xn,2) 2t
22 exp
(A124)
2 >
I==
Nadv
By Lemma D.2 with the assumptions, En= aadv?
(X,, 2)² = O(1d)). Thus, we obtain
E Xady (Xn,z) I O(1VVd) with sufficiently high probability. Because the growth rate Naad Aadv| is ( /d), the claim established.
Right term. Under Ineq, (5) and Nadv2 _ Odd/Nadv). Since we can freely under (d/NNavv), we consider (dd/Nadv). By Lemma C.3 and the assumption fhdy(z)) 2(11),
the claim is established.
Consistent decision. This is trivial by the growth rate of two terms.
27

---

Published as a conference paper at ICLR 2024
Corollary 4.5 (Complete classification for natural training samples when learning from geome-
try-inspired perturbations on uniform noises). Assume 7 Rmina R maxx Z Pmax- Suppose that
Ineqs. (4) and (5) hold. If d and Nadv are sufficiently large and d > Nadv2 2 vN holds, then a one-hidden- layer neural network trained on ceometry-inspired perturbations on uniform noises with Setting I can completely classify the natural dataset {T bn) with probability at least
99.99%.
Proof. We can rearrange fbdd (2n) as follows:
gbdy = Σ
Akya (ox, vn) An9n|11,,1
- (as,
(A125)
k=1
By Ineq. (A65), (ybdy (arn)) (1)) By Theorem 4.4, the claim is established.
E OTHER PERTURBATIONS
In the main text, we consider learning from geometry-inspired L2 perturbations, which simplify notation. In this section, consider learning from geometry-inspinge Lo and Loo and gradient- based Le perturbations.
E.1 GEOMETRY-INSPIREH Lo PERTURBATIONS
Let ds E Nea be the number of modified pixels. An adversarial example restricted to ||> nn llo ds. Following one pixel attack (Su et al., 2019) and SparseFool (Modas et al., 2019), do not constrain the distance between original and perturbed pixels. We define a geometry-inspired Lo perturbation as follows:
a., bby (In)
④ Mn.
AEVLER O M ΣN 1 AEURETA O M
77n ayd adv
cyfdv
(A126)
a. fbdy (xn) O Mnll
where @ denotes the Hadamard product and Mn E (0, 13dd denotes mask vector. Let S, be the set of the top-dl elements where V V.,,. pbay (Ix,)) is the largest. The i-th element of M,, is set to one
i is contained in Sn and zero otherwise. Since V =n fbdy does not depend on n, M,, does not depend on n. Thus, we denote M == M1
MN. Rearranging the above equation,
EN A O M
7h = EVe
(A127)
Em ARyNEER MI
Similar to Eq. (1), this perturbation is represented as the weighted sum of benign training samples, and thus contains class features. This result indicates that even sparse perturbations, which seem to lack natural data structures, enable networks generalize.
Consider the decision boundary when learning from Ly perturbations. To employ Corollary 3.4, we first construct an orthogonality condition for Lo perturbations. As a preliminary, refer the proof of Lemma C. The norm is
ΣN
(2x @ M, xx)) +
|| [ 1|2 = =||x,1
2ey
(A128)
INN AuyEER C M
ds
=Q(d) +
E c
(A129)
Note that
NN Σ ==1
Σ Aayna
M
2 O M
Σ Σ
An
M, O M) (A130)
28

---

Published as a conference paper at ICLR 2024
Nd =
(A131)
de
In addition,
Aeah (aok 2 M, = =6 dds
((a)) (A132)
(ay @ M, vn) =xn (In @ M, xn) + E'A
The inner product is
( xddv)
Di=1 (x) M,
N
adv E Aayi ① M, x..)
=m Ik)
+ cyn
ndv
+ + (A133)
E Anyaa @ M]
|| A1y
M
V dg N
=0
θ
E
(A134)
N
The orthogonality condition can be rearranged as follows:
e²) + (N) + O 2)
(
d
d8
o
-
e² 0.
(A135)
Thus, is constrained ((vd)). Moreover, similarly Theorem 4.2, the following decision boundary can be derived using Corollary 3.4:
phay (2) Σn Aady yady (D Z)
En AnDaa (x,, 2 M,
(A136)
Σ Aadv
|E An C M
Finally, under the condition of Theorem 4.2, we consider the limiting behavior of this boundary for z == EN= 0(1/VN)z,, Since the left term of this boundary equals that of Eq. (3), the left term grows with (d/N). Similarly to Lemma C.3, the right term grows with O (dvdss/ dds/N). d/ds = @(1), the right term grows faster than the left; namely, the effect of learning from perturbations dominates the classifier decision. Thus, learning from Lo perturbations succeeds for samples that are weakly correlated with many training samples.
E.2 GEOMETRY-INSPREEE Loo PERTURBATIONS
Similar to fast gradient sign method (Goodfellow et al., 2015) and projected gradient descent (Madry et al., 2018), we define an Los adversarial perturbation as follows:
Tn == cy adv sgn J bdy (Ixn) = cyn
adv
sgn
Σ A
(A137)
Assume (sgn( kk Anynoa)), xx) orders of the norm and inner product are
@(vd) for any Similarly the above discussion, the
adv -O()) ((Vā)e +(d)), (m on ady) -o
-0(4) @(Vī)e - O(d)e. (A138)
Assuming d/N = @(1), the orthogonality condition requires (1/vV)) The decision boundary
pbyy (z)
2
A E
adv yn
(w z) +
sgn
(A139)
Aadv
Consider the limiting behavior of this boundary for = O(d/VN) EN I A Similarly to the discussion above, the left and right terms grow with (d/N) O(1) and ((Vā), respectieely.. Note that (sgn(E k= >R)) Σx- \B = @(vN). Thus, learning from Lxs perturbations succeeds for samples that are weakly correlated with many training samples.
29

---

Published as a conference paper at ICLR 2024
E.3 GRADIENT-BASEE BASDEN Lg PERTURBATIONS
In the main text, we consider geometry-inspired perturbations that target the decision boundary fbdy instead of the network f itself. In this section, we consider L2 gradient-based perturbations that target the network f itself. Similar concepts are employed in fast gradient sign method (Goodfellow al., 2015) and projected gradient descent (Madry et al., 2018).
Attack on Network Directly, First, we consider an attack on the network f. Since gradient flow on 00, we can represent the network as
converges in direction to W (ef. Theorem B.I), with
If (2; cWstd) with > 0. Note that xn)) > O and (u, 2n, < 0 if 1, and (u, xn)) > 0 and Of yn (Frei al., 2023). By Theorem B.1, yn 1,
(v, In)
m/
m/2
[mmn wWotdd
(cos, Lnd
Σ
7
(cus, an)
(A140)
mm
m
k=1
v m1
7V
(cv, (n))
(ou, D.n)
(A (A141)
2
c(1 + 72)
Σ
(m,,
Σ
(A142)
2
2
kzya=-1
Thus,
(wn; c Wstd)
(1 + 72) Σ k-m=+11 Auynaa Eneye - A
(A143)
(Tn csstd)]
[I(1 72) E Ekm AGc - Ek.n==1 2
We denote this by 84. Similarly, for negatively labeled samples, we define s.. An adversarial example targeting the network can be represented as follows:
eynity s+
(yn=1) =
Fn == Fn +
eyyay 8_ (ya --)=
(A144)
To consider the orthogonality condition, we evaluate the order of (s+ æn)) Similarly Lemma C.3, the denominator of 8 grows with (N)/)) In addition, the inner product between the numerator and F,, grows with (11) (cf. Lemma C.1). Thus, similar to Lemma C.I, the orthogonality condition
requires = O(Vd/N), By Corollary 3.4, the decision boundary is
bbdly (z)
Σn Xadv adv (In, 2) + Emoh= (8+, 2) + En Apray (s_, (
(A145)
EN=1 Aadv
E Aadv
Consider the limiting behavior of this boundary for == En 0(1/VN)zz,. Because the left term of this boundary equals Eq. (3), it grows with (d/NN) Since A = @(1/d) (ef. Corollary 3.4) and (8+,2) z) = vNd, the right term grows with (d/vN) Thus, learning from L2 perturbations that target the network itself also succeeds for samples that are weakly correlated with many training samples.
Attack on Network with Loss Function. Then, we consider an attack on the network f with the exponential loss. The gradients of the exponential loss for Dn can be calculated as follows:
Vz,,, exp( Un (xx cWatd))
yn exp exp(-Bn (z,,; (w V... a... f cWstd) yn
(A146)
yn exp( Cop--)Vaa.. (xx.; cWstd).
(A147)
This indicates that the normalized gradients with the exponential loss are consistent with those of the network without loss function. Thus, the case of the direct attack on the network can be applied to the case of the exponential loss. The same discussion applies to the logistic loss.
F SUB-GAUSSIAN NOISE SCENARIO
In this section, we consider learning from perturbations on sub-Gaussin Gaussian noises. A sub-Gaussian random variable is defined as follows:
30

---

Published as a conference paper at ICLR 2024
Definition F.1 Sub-Gaussiam). A random variable X is called sub-uaussiie Gaussian if there exists some d² 0 such that for every R, X satisfies E[e*(X-B/X)] I e 22
We write sub-Gaussie Gaussaas random variable as X subG(o²). Sub-Gaussian random variables include Gaussian and any bounded random variables such as Rademacher (or symmetric Bernoulli) and uniform random variables. In addition, define sub-exponential random variable follows:
Definition F.2 (Sub-exponential). A random variable X is called sub-exponential if there exist some such that for every |s] < 1/b, X satisfies [[ex[] S 60
2² > 0 and
We write a sub-exponential random variable as X subB[o?, b). Sub-Gaussian and -exponential have the following properties:
Lemma F.3 (Properties sub-Gaussian and -exponential).
(a) X follows sabG(o²)). then PP[ E[X] 1) s 2exp(- holds for any > O. (iaiint///// /o? / /2) holds
(b) If X follows subE(o?, b), then P [[X] S for any t O.
(c) If X1 and X2 are independent and follow subG(af) and subG(o respectively, then 01X1 + 22222fllooe subG(a + a for any 01, 02 R.
(d) If X1 and X2 are independent and follow subE(oī, b1) and subE(a b2). respectively,
then ta21+ follows subE(a,o} tozo2, max[|a] [ax{]ai]bi |a2]b2) } for any a1 02 R.
(e) If X follows subG(o²),, then X" follows subE(256o 16o²).
( Suppose that (i) X1 and X2 are independent. and subG(a2), respectively. (ii) R[X1] [x[2]] = 0. Then, X,X2 follows
(ii) Xı and X2 follow subG(af)
subE(8ofoj, V20)
Proof. For (e)- refer to Duchi (2023); Rigollet & Hütter (2023). We consider (f). For any IR,
E (x X Ex, [x, [e*X1
X₂ = x2]]
(A148)
SEx, (x330/22
(A149)
(ofx3s²))
=xx,
(A150)
n!2n
By [[X3"1 s 22(oo))"n! for any N (Rigollet & Hütter, 2023),
Ele 5 Σ
(A151)
For any |s| $ 1/V220002.
Ele $1+ =1+407038
8080082212
(A152)
Thus, X2X, follows subF(Soff3, V20102)
Similarly to Lemma D. we consider the properties of random vectors with sub-Gaussian entries.
Lemma F.4 (Properties of sub-Gaussian random vectors). Let (X, IN C Rdd be N E N indepen- dent random variables sampled from the sub- Gaussian distribution subG(1). Assume E[X,.,] for any n E [N) and E [d]. Let z E RRd be a constant vector. Then, the following statements hold: (a) d 2 2 In 1000N,
xx,12 d < 16v 1000N >
P max
(A 153))
500N
31

---

max Published as a conference paper at ICLR 2024
(b) If l111000N)/4.
N
P max (X,,, Xx)l S 2v 1000
2
(A154)
500
(c)
1
max (X 2)1 S /2 1000
|=1|
1
(A155)
500
Proof. As a preliminary, refer Lemma F33 and the proof of Lemma D.I.
(a) X,, 2 follows subE(256d, 16) with mean For > 0,
f
t
S
+ tt S 16d.
(A156)
256d
16
If d 2 2n 1000.N,
12, d 2 16v 26v2dln 1000N
WA
(A157)
500N
Thus,
N
|x,|| 11 - al S 16
(A158)
n
500N
(b) Xx) follows subbi(8d, v2) with zero mean. Fort 0,
12 1
et54ved.
(A159)
8d V2
If d 2 In(1000.V)/4,
I Xx)l 2 2d 1000N
(A160)
500N
(c) (Xn: 2) follows subG([|>|( with zero mean. For fort= /2 1000N]||
IXx,, n. 2)1 2 12 10000/111 < 500N
(A161)
By Lemma F4, for ||=|| the following inequalities hold with probability at least 99.8%:
X 1|2 = (d)),
(X,, Xx) Ö(va),
(Xn, 2) Ō
(A162)
These orders are consistent with those for uniform noises (ef. Lemma D.1). Thus, similarly to Theorems 4.3 and 4.4, if e is constrained to ((Vd//Ndv)) the decision boundary Eq. (6) and consistent decisions can be obtained for learning from perturbations on sub-Gaussian noises.
G THEOREM 4.1 WITHOUT ASSUMPTION OF LAST LAYER OF NETWORK
In this section, we derive Theorem 4.1 without the assumption that the positive and negative values of a are equal. Let m and m_ be the numbers of positive and negative neurons in the hidden layer, respectively. In this setting, Frei et al. (2023) provides the decision boundary as follows:
f bby (z) = (m+ + +m-
Σ
Xn - (ym4 + m_
Xn
(A 163)
m.. =11
32

---

Published as a conference paper at ICLR 2024
With 4, (m+ + ym_) if yn +1 and A, (ym+ + +m_) otherwise,
pbay (z) Σ Andnyn
(A164)
Similar to Eq. (1), perturbation is defined as follows:
Σ A
Th cy
(A165)
Σ Aдdxyaaa
Since A, (1), the growth rate of nn with respect and N is the same as the original definition of 7h- Thus, similarly to Theorem C.2, i olle=O(////) the decision boundary is
Padd (z) Σ Andy yadyyady (I x)
En n== ( z)
(A166)
N
Andv Aadt
| Andnynan
where Andv (m+ + -m-) if uo +1 and Andv (ym+ + m_) otherwise.
H FLIPPED LABEL LEARNING
In this section, explain the success of learning from perturbations under the flipped label scenario, ie., yn = yn for every n E [N]. with assumptions about a data structure and learning bias. First, assume that nn consists of two features: robust and non-robust features, which is based on the hypothesis from llyas et al. (2019). Second, we suppose that standard trained classifiers focus only non-robust features, which is empirically supported by Etmann et al. (2019); Tsipras et al. (2019); Zhang & Zhu (2019); Chalasani et al. (2020). In other words, we assume that the decision boundary of the classifier consists of the learning effect only from non-robust features. Formally, these assumptions are summarized as follows:
Assumption H.1. (a) For every n [N]. natural sample x. can be represented an wx:ob anon (b) For * k; (arto xbb) = (d/N), (orto .xtoo) = OddNN), and (arnon, xhou) O(d/N). (c) Under the setting of Theorem 3.3, the decision boundary given by pbdy(2) E Anzn (xehoon z).
Consider perturbations to the decision boundary f Eq. (1), an adversarial example and perturbation are defined as follows:
ΣN
AnHn (whon, z). Similarly to
Σ
k= Autiaatton
adv Bn qn:
On :-ey/ arlv
(A167)
Σ =k=1 Akyiaa
Under these settings,
d 1dvv| 1|2 O(d) + (v + 2
(e(v
(xn , sadl) Pmax θ
(VN
e (A168)
Similarly to Theorem C.2, if = (d//N), the decision boundary is
2m Aady yady (In, 2)
N
pbdl (2)
pbdy (z)
(A169)
Em Agdv
=
- d. N
(bbl(())) Σ dady youd (Imn)
(A170)
For = = ΣN W(1//N())))) )annn pbd (z)) = O(VN) and EN Aady adv (æn, 2) = O(1)
Thus, if N. d co, then sgn(fldd (z)) s holds. Finally, under Assumption H.1, we can explain why even a flipped learning scenario (corresponding deterministic label scenarios in Table 1) yields moderately high accuracy natural test datasets.
33

---

Published as a conference paper at ICLR 2024
1 EXPERIMENTAL SETTINGS AND ADDITIONAL RESULTS
In this section, we present detailed experimental settings and additional empirical results. First, we introduce the settings that are consistent across experiments on artificial and real-world datasets.
We used an NVIDIA A100 GPU. A scheduler reduced learning rate to 10% of its original value a training loss did not decrease over 10 consecutive epochs. Uniform noises were sampled from ([]-
As adversarial attacks, we employed projected gradient descent (Madry et al., 2018). The step sizes of projected gradient descent 0.3 for Lo attacks and c/5 for L2 and L attacks, respectively. The number of steps is 100 for L2 and Lo attacks.
In Lo attacks, the number of modifiable pixels was limited, but the distance between altered and original pixels was not restricted. Sparse attacks employ the following procedures in each step: (i) select the pixel with the highest gradient magnitude from the masked region, (ii) remove the mask for the selected pixel, and (iii) update the perturbations for unmasked pixels. Thus, the number of steps corresponds
the maximum number of modified pixels. Note that the modified pixels shown in Figs. A16 to A18 may not always match the number of steps because we selected the adversarial example with the highest loss over all steps for the final output.
Although we primarily considered geometry- inspired perturbations (cf. Eq. (1)) in the theoretical discussion, we employ gradient-base perturbations (cf. Eq. (A144)) in the experiments. This is due to the practical difficulty of obtaining the decision boundary of a one-hidden-layer neural net- work (cf. Eq. (A14)) and the value of X,, (cf. Theorem B. making seometry-inspiiee perturbations infeasible in practice.
1.1 ARTIFICIAL DATASET
The procedure for generating artificial data based on uniform noises can be found Section 5.1. Similarly, dataset based on the Gaussian noises (0, Ia) was created. Examples of standard, noise, and adversarial samples are shown in Fig. A3. The experimental settings followed the theoretical settings, Section 3.1. We used one-hidden-layer neural networks and stochastic gradient descent with a learning rate of 0.01, momentum of 0.9, and exponential loss. Considering f - co, we set the epochs to 100,000. The vectors and used to illustrate the decision boundary are defined in Theorem 3.3. In practice, these values are incalculable due to the uncomputable nature of Xn- Therefore, we approximated as the average of the first half of the weights in W and as the average of the latter half.
The experimental results for artificial datasets based on uniform and Gaussian noises with Lo, La- and Loc adversarial perturbations are provided in Figs. A4 to A15. We can confirm a strong align- ment between the decision boundaries when learning from standard samples and perturbations (cf. Theorem 4.4). High classification accuracy for standard training data (cf. Corollary 4.5) was also observed across variety of noise and perturbation forms.
I.2
10
Examples of standard and adversarial samples for each dataset are shown in Figs. A16 to A18, A six-layer convolutional neural network was used for MNIST and MaSHion-MNIST. WedeResNet-28- 10 with a dropout ratio of 0.3 was used for CIFAR-10 10. The batch size was set to 128. While no data augmentation was applied
MNIST and Fashion-MNIST random cropping and horizontal flipping were applied to CIF We used stochastic gradient descent with Nesterov momentum of 0.9, weight decay of 5 x 10-4, and cross-entropy loss. The initial learning rates can be found in Table A3, The perturbation constraint to Table A4. We set the epochs to 100 for MNIST and 200 for Pashion-MNIST and CIFAR-I0. However, in the experiments for Fig. A19, we set the epochs to 300, considering large number of training samples.
number of modifiable pixels ds set according
For MNIST and Fashion-MNIST Fig. A19 shows the accuracy of learning from perturbations with various adversarial sample sizes. In several cases, we observed a general increase in the accuracy the number of samples increased. However, in some cases, while the accuracy did not decrease,
34

---

Published as a conference paper at ICLR 2024
Table A3: Initial learning rates in each learning scenario.
On natural samples
On noise data
Lo (R)
Lo (D)
L2 (R)
L2 (D)
L (R)
Loe (D)
Lo
L2
Loo
MNIST
0.1
0.1
0.01
0.01
0.01
0.01
0.1
0.1
0.1
FMNIST
0.1
0.1
0.01
0.01
0.01
0.01
0.1
0.1
0.1
CIFAR-1O
0.1
0.1
0.1
0.1
0.01
0.1
0.1
0.1
0.1
Table A4: Perturbation constraint e or number of modifiable pixels da for MNIST, Fashion-MNIST, and CIFAR-10.
MNIST
Fashion-MNIST
CIFAR-I0
Lo
L2
Lo0
Lo
L2
Loo
Lo
L2
Loo
10
2.0
0.3
35
2.0
0.3
150
0.5
0.1
there was no significant improvement in the accuracy. These inconsistencies could potentially be resolved through extensive experiments and tuning of learning and architectures.
35

---

Published as a conference paper at ICLR 2024
Standard
Noise
Adv. Lo
Adv. L/
Adv. Loo
Figure A3: Artificial data based uniform noises. Standard images were drawn from the uniform distribution U[, 1)²), and their corresponding labels from ({{+))). We treated them as natural images. Noise images are similarly drawn from U[[-1, 1J Adversarial examples were generated to superimpose adversarial perturbations on the noise images to fool a classifier trained on the stan- dard (but seemingly noisy) images. The labels below the adversarial examples indicate target labels that were randomly sampled from [1] Those below the noise images were used for comparative experiments in training classifiers on these noises.
36

---

Published as a conference paper at ICLR 2024
Input dimension d
(Adversarial) noise sample Nadv
100
500
1,000
10,000
10
100
10,000
Standard
100%
100%
100%
100%
100%
100%
100%
100%
Adversaria
90%
65%
73%
93%
62%
78%
91%
93%
Noise
49%
47%
50%
50%
49%
48%
50%
50%
Natural sample N
Modified pixel ratio ds/
1,000
2,000
5,000
10,000
0.0001
0.0004
0.001
0.05
Standard
100%
100%
100%
100%
100%
100%
100%
100%
Adversarial
93%
82%
68%
62%
51%
58%
64%
93%
Noise
50%
49%
50%
49%
50%
50%
50%
50%
Figure A4: Decision boundaries of classifiers trained on artificial datasets based on uniform noises and La adversarial perturbations. Each variable was varied based on 10, 000, Nadv 10, 000, N 1000, and da d = 0.05. The description is the same as Fig. 1.
37

---

Published as a conference paper at ICLR 2024
Input dimension d
(Adversarial) noise sample Nadv
100
500
1,000
10,000
1
10
100
10,000
Standard
100%
100%
100%
100%
100%
100%
100%
100%
Adversarial
94%
59%
61%
76%
60%
71%
75%
76%
Noise
49%
48%
46%
49%
51%
51%
50%
49%
Natural
sample N
Modified pixel ratio /
1,000
2,000
5,000
10,000
0.0001
0.0004
0.001
0.05
Standard
100%
100%
100%
100%
100%
100%
100%
100%
Adversarial
76%
67%
60%
56%
50%
56%
61%
76%
Noise
49%
51%
49%
50%
49%
49%
49%
49%
Figure A5: Decision boundaries of classifiers trained on artificial datasets based on Gauss noises and Lg adversarial perturbations. The description is the same Fig. A4.
38

---

Published as a conference paper at ICLR 2024
Input dimension
(Adversarial) noise sample Naavv
100
500
1,000
10,000
100
10,000
Standard
100%
100%
100%
100%
100%
100%
100%
100%
Adversarial
63%
69%
80%
99%
52%
544%
65%
99%
Noise
49%
47%
50%
50%
49%
48%
50%
50%
Natural sample N
Perturbation constraint
1,000
2,000
5,000
10,000
0.01
0.05
0.1
0.78
Standard
100%
100%
100%
100%
100%
100%
100%
100%
Adversarial
99%
98%
90%
80%
51%
59%
67%
99%
Noise
50%
49%
50%
49%
50%
50%
50%
50%
Figure A6: Decision boundaries of classifiers trained on artificial datasets based on uniform noises and L2 adversarial perturbations. Each variable was varied based on d 10, 000, Nadv 10, 000, N 1000, and = 0.78. The description is the same as Fig. 1.
39

---

Published as a conference paper at ICLR 2024
Input dimension d
(Adversarial) noise sample Nadv
100
500
1,000
10,000
10
100
10,000
Standard
100%
100%
100%
100%
100%
100%
100%
100%
Adversarial
59%
62%
70%
97%
50%
53%
59%
97%
Noise
49%
48%
46%
49%
51%
51%
50%
49%
Natural sample N
Perturbation constraint
1,000
2,000
5,000
10,000
0.01
0.05
0.1
0.78
Standard
100%
100%
100%
100%
100%
100%
100%
100%
Adversarial
97%
91%
79%
71%
50%
55%
59%
97%
Noise
49%
51%
49%
50%
49%
49%
49%
49%
Figure A7: Decision boundaries of classifiers trained on artificial datasets based on Gauss noises and La adversarial perturbations. The description is the same Fig. A6.
40

---

Published as a conference paper at ICLR 2024
Input dimension d
(Adversarial) noise sample Naavv
100
500
1,000
10,000
100
10,000
Standard
100%
100%
100%
100%
100%
100%
100%
100%
Adversarial
70%
73%
80%
99%
52%
544%
64%
99%
Noise
49%
47%
50%
50%
49%
48%
50%
50%
Natural sample N
Perturbation constraint
1,000
2,000
5,000
10,000
0.001
0.005
0.01
0.03
Standard
100%
100%
100%
100%
100%
100%
100%
100%
Adversarial
99%
98%
87%
78%
53%
71%
86%
99%
Noise
50%
49%
50%
49%
50%
50%
50%
50%
Figure A8: Decision boundaries of classifiers trained on artificial datasets based on uniform noises and Lae adversarial perturbations. Each variable was varied based on 10, 000, Aadv 10, 000, N = 1000, and 0.03. The description is the same as Fig. 1.
41

---

Published as a conference paper at ICLR 2024
Input dimension d
(Adversarial) noise sample Nadv
100
500
1,000
10,000
10
100
10,000
Standard
100%
100%
100%
100%
100%
100%
100%
100%
Adversarial
62%
63%
71%
95%
50%
53%
57%
95%
Noise
49%
48%
46%
49%
51%
51%
50%
49%
Natural sample N
Perturbation constraint
1,000
2,000
5,000
10,000
0.001
0.005
0.01
0.03
Standard
100%
100%
100%
100%
100%
100%
100%
100%
Adversarial
95%
90%
78%
69%
52%
60%
70%
95%
Noise
49%
51%
49%
50%
49%
49%
49%
49%
Figure A9: Decision boundaries of classifiers trained on artificial datasets based on Gauss noises and Tog adversarial perturbations. The description is the same Fig. A8.
42

---

Published as a conference paper at ICLR 2024
1.00
Accuracy
Accuracy
Adversarial
0.75
Noise
0.50
*X
2,000
4,000
6,000
8,000
10,000
2,000
4,000
6,000
8,000
10,000
Input dimension d
(Adversarial) noise sample Naavv
1.00
1.00
Accuracy
Accuracy
0.75
0.75
0.50
20mh
30
0.50
X00 X0X 30:0
2,000
4,000
6,000
8,000
10,000
0.00
0.01
0.02
0.03
0.04
0.05
Natural sample
Modified pixel ratio do /d
Figure A10:
Accuracy of classifiers trained on artificial datasets based on uniform noises and Lo adversarial perturbations. The description is the same Figs. and A4.
1.00
Adversarial
Accuracy
Accuracy
Noise
0.75
0.50
X og>
XX
0.50
x X =X
2,000
4,000
6,000
8,000
10,000
2,000
4,000
6,000
8,000
10,000
Input dimension d
(Adversarial) noise sample pravv
1.00
1.00
Accuracy
Accuracy
0.75
0.75
0.50
X
X0
-30
0.50
300
300 9020
2,000
4,000
6,000
8,000
10,000
0.00
0.01
0.02
0.03
0.04
0.05
Natural sample
Modified pixel ratio da //d
Figure All: Accuracy of classifiers trained on artificial datasets based on Gauss noises and Lo adversarial perturbations. The description is the same Figs. and A5.
43

---

Published as a conference paper at ICLR 2024
1.00
Accuracy
Accuracy
Adversarial
0.75
0.75
Noise
0.50
0.50
2,000
4,000
6,000
8,000
10,000
0
2,000
4,000
6,000
8,000
10,000
Input dimension d
(Adversarial) noise sample Nady
1.00
1.00
Accuracy
Accuracy
0.75
0.75
0.50
X
X-X
2,000
4,000
6,000
8,000
10,000
0.2
0.4
0.8
Natural sample N
Perturbation constraint é
Figure A12: Accuracy of classifiers trained on artificial datasets based on uniform noises and L2 adversarial perturbations. The description is the same Figs. and A6.
Accuracy
Accuracy
Adversarial
0.75
0.75
Noise
0.50
X
gg
xX
0.50
30% X0m
2,000
4,000
6,000
8,000
10,000
2,000
4,000
6,000
8,000
10,000
Input dimension d
(Adversarial) noise sample padd
1.00
1.00
Accuracy
Accuracy
0.75
0.75
0.50
*X
R0X
2,000
4,000
6,000
8,000
10,000
0.2
0.4
0.8
Natural sample N
Perturbation constraint e
Figure A13: Accuracy of classifiers trained on artificial datasets based on Gauss noises and L2 adversarial perturbations. The description is the same Figs. and A7.
44

---

Published as a conference paper at ICLR 2024
1.00
Accuracy
Accuracy
Adversarial
0.75
0.75
Noise
0.50
OX
0.50
2,000
4,000
6,000
8,000
10,000
0
2,000
4,000
6,000
8,000
10,000
Input dimension d
(Adversarial) noise sample Nadv
1.00
1.00
Accuracy
Accuracy
0.75
0.75
0.50
X
2,000
4,000
6,000
8,000
10,000
0.00
0.01
0.03
Natural sample N
Perturbation constraint é
Figure A14: Accuracy of classifiers trained on artificial datasets based on uniform noises and Log adversarial perturbations. The description is the same Figs. and A8.
Accuracy
Accuracy
Adversarial
0.75
0.75
Noise
0.50
X
gg
xX
0.50
30% X0
2,000
4,000
6,000
8,000
10,000
2,000
4,000
6,000
8,000
10,000
Input dimension d
(Adversarial) noise sample paddy
1.00
1.00
Accuracy
Accuracy
0.75
0.75
0.50
*X
2,000
4,000 8,000
6,000
10,000
0.00
0.01
0.03
Natural sample N
Perturbation constraint
Figure A15: Accuracy of classifiers trained on artificial datasets based on Gauss noises and Loe adversarial perturbations. The description is the same Figs. and A9.
45

---

Published as a conference paper at ICLR 2024
Natural
4
4
2
5
4
9
2
3
Lo (R)
/
2
1
3
0
5
S
8
7
5
8
Lo (D)
/
2
1
3
6
5
2
0
3
2
4
2
La (R)
0
2
1
3
7
7
0
5
8
8
7
5
8
L2 (D)
7
1
3
6
5
2
0
3
2
4
2
Lo (R)
9
/
9
2
1
3
0
5
8
8
7
5
8
Do (D)
S
4
/
9
2
1
3
6
5
2
0
2
4
2
Lo
2
La
2
7
7
2
Figure A16: Natural images, perturbations natural images, and perturbations uniform noises for MNIST. Below the natural images and adversarial examples are their respective original and target labels in adversarial attacks. The "R" indicates that target label was randomly chosen from the nine labels that differ from an original label. The "D" indicates that target label was determin- istically chosen the next sequential label after original label.
46

---

Published as a conference paper at ICLR 2024
Natural
Boot
Top
Top
Dress
Top
Pullover Sneaker Pullover Sandal
Lo (R)
Shirt
Sneaker
Trouser
Sandal
Boot
Bag
Shirt
Sandal
Bag
La (D)
Top
Trouser Trouser
Coat
Trouser
Dress
Bag
Dress
Shirt
Lg (R)
Shirt
Sneaker Trouser Sandal
Boot
Bag
Shirt
Sandal
Bag
La (D)
Top
Trouser Trouser
Coat
Trouser
Dress
Bag
Dress
Shirt
Do (R)
Shirt
Sneaker Trouser Sandal
Boot
Bag
Shirt
Sandal
Bag
Le (D)
Top
Trouser
Trouser
Coat
Trouser
Dress
Bag
Dress
Shirt
Lo
Sneaker
Boot
Snea ker
Sandal
Trouser
Coat
Sneaker
Pullover
Boot
La
Sneaker
Boot
Snea ker
Sandal
Trouser
Coat
Sneaker Pullover
Boot
Loo
Sneaker
Boot
Sneaker
Sandal
Trouser
Coat
Sneaker Pullover
Boot
Figure A17: Natural images, perturbations on natural images, and perturbations uniform noises for
The description is the same as Fig. A16.
47

---

Published as a conference paper at ICLR 2024
Natural
Frog
Truck
Truck
Deer
Car
Car
Bird
Horse
Ship
Lo (R)
Horse
Frog
Plane
Dog
Truck
Ship
Horse
Deer
Horse
La (D)
Horse
Plane
Plane
Dogg
Bird
Bird
Cat
Ship
Truck
Lg (R)
Horse
Frog
Plane
Dog
Truck
Ship
Horse
Deer
Horse
La (D)
Horse
Plane
Plane
Dog
Bird
Bird
Cat
Ship
Truck
Do (R)
Horse
Frog
Plane
Dog
Truck
Ship
Horse
Deer
Horse
Lee (D)
Horse
Plane
Plane
Dog
Bird
Bird
Cat
Ship
Truck
Lo
Bird
Frog
Ship
Truck
Truck
Plane
Ship
Dog
Deer
La
Bird
Frog
Ship
Truck
Truck
Plane
Ship
Dog
Deer
Loo
Bird
Frog
Ship
Truck
Truck
Plane
Ship
Dog
Deer
Figure A18: Natural images, perturbations on natural images, and perturbations uniform noises for CIFAR-10. The description is the same as Fig. A16.
48

---

Published as a conference paper at ICLR 2024
Max. validation accuracy
Lo
0.5
0.5
1/2
Loo
0.4
0.4
KACA
0.3
0.3
0.2
0.2
60K 240K
480K
720K
960K
1.2M
60K
240K
480K
720K
960K
1.2M
MNIST
FMNIST
The number of samples
Figure A19: Accuracy of classifiers trained MNIST and Fashion-MNIST in uniform noise sce- nario. The vertical axis represents the maximum validation accuracy across all epochs. The hori- zontal axis represents the number of adversarial samples Nadv
49


Reviews:
[{"review_id": "iCEdt1yYIC", "reviewer": "Reviewer_K8gK", "summary": "This paper theoretically studies the learning of adversarial perturbations generated by geometric-inspired attacks with respect to a one-hidden-layer neural network and orthogonal training data. Specifically, two settings are considered for learning from adversarial perturbation: 1) perturbation on natural data and 2) perturbation on uniform noise. Theoretically, they show that the decision boundaries of models learned from adversarial perturbation are consistent with clean decision boundaries, except for examples strongly correlated with many natural samples.", "questions": "Apart from the above questions, I would like to know how the degree of orthogonality of training data affects your theoretical results. If the underlying data distribution only partially satisfies this assumption, can you use similar proof techniques to characterize the learning from adversarial perturbations?\n\n\n============ Post Rebuttal Comments ===========\n\nI appreciate the authors' feedback. In summary, I will keep my score unchanged. I think the authors misunderstood my major concern, which has nothing to do with adversarial training or adversarial robustness. What is unconvinced from my perspective is the motivation for studying the setting of learning from adversarial perturbations. I do not find a convincing answer in the rebuttal, and I can hardly understand the benefits gained from studying this problem. The final conclusion drawn from the paper is that standard learning from adversarially perturbed inputs (with possibly incorrect labels) yields consistent predictions. Because of the assumptions on how the adversarial perturbations are generated, I am not sure if the paper's theoretical evidence is sufficient to support such general conclusion. In my opinion, the way adversarial perturbations are generated and the perturbation budget will highly affect the final conclusion.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Theoretical understanding of how neural networks learn in the presence of adversarial perturbations is a challenging but important task. The paper is technically solid, with clearly presented assumptions and theoretical results. Theoretical results are accompanied by adequate discussions and high-level explanations of the proof idea. The considered setting where adversarial perturbations are added to uniform/Gaussian noise is new, which nicely supports the paper's key argument that generated adversarial perturbations contain abundant information about the underlying data structure.", "weaknesses": "While I appreciate the theoretical nature of this paper, the motivation and some considered settings for studying adversarial perturbations in the context of learning need to be more convincing from my perspective. In the abstract, the paper claims that the phenomenon “neural networks trained on mislabeled samples with adversarial perturbations can generalize to natural test data” is counter-intuitive.  I do not understand why this is a counter-intuitive phenomenon and how this phenomenon motivates the problem of learning from adversarial perturbations. If I understand correctly, the adversarial perturbations are generated with respect to some pre-trained neural networks and are not necessarily “mislabeled” (unless the perturbation size is large). In addition, the definition of mislabeled data needs to be clarified because, typically, human is considered the underlying ground truth in judging whether an input image is mislabeled. However, you use a pre-trained neural network as the reference model for defining whether an input is mislabeled. I am also confused by the statement in the introduction, “A classifier, trained on natural samples with adversarial perturbations labeled by such incorrect classes, can generalize to unperturbed data,” which I believe is not the key message that Ilyas et al. (2019) wants to convey. From my perspective, the learnability of adversarially perturbated natural data is because the added perturbation is not large enough to destroy the useful generalizable features of the natural data. I hope the authors can clarify my concerns in the rebuttal on why the learnability from the added adversarial perturbations is worth studying, which will largely decide my judgement on whether this paper reaches the ICLR acceptance bar or not.\n\nMoreover, the imposed assumptions of orthogonal training data and the use of geometric-inspired attacks need to be better discussed. What is the mathematical definition of orthogonal training data? I do not understand the claim that the orthogonality of training data is a common property of high-dimensional data. Does this claim hold for any high-dimensional data distribution or specific distributions? In addition, I believe geometric-inspired attacks are less commonly studied in the adversarial ML community. How will the conclusion of your theoretical findings change if the perturbations are generated by PGD attacks (Madry et al., 2018)?", "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": "cjtvmqxD0Y", "reviewer": "Reviewer_qaZD", "summary": "The paper investigates learning from adversarial perturbations, which is motivated by the observation that neural networks trained on adversarial examples can generalize to natural test data. To that end, recent results on the implicit bias of the gradient flow of training single-hidden-layer networks are employed to show that, under certain assumptions, the decision boundaries of natural examples and adversarial examples align with each other.", "questions": "- In the limitations paragraph it is mentioned that model is simple (one-hidden layer network and orthogonal training data). Could the authors extend their discussion on the limitations (e.g. attack model), and if possible, mention ideas on how to overcome the limitations in the future (e.g. $\\epsilon \\in O(d/N)$)?\n- The paper expands on established settings on 'learning from adversarial perturbations' (Definition 1.1. and Definition 3.2) by also discussing perturbations on uniform noises. In this 'perturbation on uniform noise' setting, i.e. $x_n^{adv} = X_n + \\eta_n$, with $X_n$ being uniform noise instead of a natural data point. What is the motivation for studying this setting? Why not considering $x^{adv}_n = x_n + X_n + \\eta_n$ (with $x_n$ the actual data points), which would be a more practical setting?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The idea to apply the implicit bias results to learning from adversarial perturbations is novel.\n- The theoretical results admit interesting and relevant interpretations (eg. effect of learning misslabled data vs perturbation data).", "weaknesses": "- It is unclear what the motivation for studying the uniform perturbation model is.\n- Overall, the investigated model seems to be quite simple and theoretical assumptions restrictive (see also questions below).\n- The text is rather densely written (e.g. subsection 4.2 and 4.3), which makes understanding main statements and insights rather difficult (e.g. Theorem 4.2).", "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": "wwxAQVVXcq", "reviewer": "Reviewer_doyy", "summary": "This paper consider orthogonal training data, and prove that one hidden layer neural network trained with mislabeled data should have the sae dicision boundary with training on the natural data. Moreover, the adversarial perturbation can be treated as the weighted sum of benign training data.", "questions": "I believe the writing of the paper can be largely improved. Most of the questions I have here and in the previous section are mainly because of the unclear writing or cannot find any pointers.\n\n1. Can the author provide any intuition as to why mislabeled data provide the same classifier direction as clean data? Is it mainly because of the orthogonality of training data so that even if the label is noisy the data is still orthogonal?\n\n2. For the discussion of theorem 4.1 ``Consistent Growth of Two Effects”, it’s unclear to me whether estimating the growth rate of T1, T2 by switching the absolute operator and the summation is reasonable. The magnitude could have a huge difference with proper label $y_n$, so why assume the rate of switching the operator is reasonable?\n\n3. It’s unclear from a theoretical perspective in Appendix G why the standard decision boundary only depends on non-robust features as shown in equation A157.\n\n4. For Figure 2, and other figures, does the accuracy clean accuracy or adversarial robust accuracy? What’s the procedure to generate adversarial perturbation? Does it relate to the decision boundary? What’s the point of considering random selection vs. deterministic selection? Does the perturbation size actually align with what indicates by the theorem such as $O(d/N)$ or $O(\\sqrt{d/N})$?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "This paper provides a theoretical justification regarding an empirical phenomenon that first observed in Ilyas et a. 2019. To the best of my knowledge there’s no theoretical work has been focused on this direction before.", "weaknesses": "I’m not exactly following the motivation of this work. Normally when people consider adversarial training to gain robustness, at each iteration the adversarial training examples is generated based on the current model weight, yet in this paper, from the definition 3.2, it seems that the adversarial examples of training samples is generated beforehand and independent of the current model weight, and it’s fixed during the latter training procedure. Therefore it’s unclear to me whether the perturbation considered in this paper is actually adversarial or not. The author claims the motivation comes from Ilyas et a. 2019, whereas in that paper there’s also a math formulation of generating the designed adversarial perturbation, which seems different from the procedure described in definition 3.2. \n\nIt seems this paper’s theoretical results largely build on the result from Frei et al 2023. Yet the discussion of the existing result and the corollary is limited. It’s unclear to me why corollary 3.4 can be directly derived from Theorem 3.3. Theorem 3.3 requires clean training data to be nearly orthogonal, then for corollary 3.4 you should also prove that the adversarial example is almost orthogonal. Moreover, the adversarial perturbation considered depends on the decision boundary, but it’s unclear to me whether the coefficient $\\lambda$ in the decision boundary is computable. The network only considers Leaky ReLU, yet it’s unclear why cannot generalize to other activation functions and what’s the technical difficulty.\n\nThe statement of each theorem is not self-contented. If $R_{min}, R_{max}, p_{max}$ is used all over the place, then they should be introduced in the notation part. The explanation of each theorem and corollary is not clear. Why we require equation (3)? Any intuitive explanation or simply one requirement for the proof to go through? When N goes to infinity, equation (3) is saying $p_{max}$ is negative, which is kind of counterintuitive. Similarly, what does equation (6) hold mean intuitively?", "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": "5rxlJAoS7H", "reviewer": "Reviewer_75Lo", "summary": "In this paper, the authors focus on the embedded information in adversarial perturbations. Motivated by the prior work (Ilyas et al. 2019), they theoretically demonstrate that the adversarial perturbation can be represented as a weighted combination of the natural datapoints. And the model trained on these adversarial perturbations (with incorrect labels) can efficiently learn the data features and generate well on the natural data. Specifically, they provide some theorems showing the boundary of the model learning from the purturbations is partially determined by the model learning from the natural data. Some experiments are conducted to validate their theory.", "questions": "Please refer to the Weakness part.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "* The writing is generally clear.\n* Although there are some assumptions about the dataset and they only focus on one-hidden-layer neural network, the authors provide some insights into this research field.\n* The problem of why network learning from perturbation can generate well is worth exploring. This can shed some light on other interesting phenomena, such as the transferability of adversarial examples.", "weaknesses": "My main concerns about this paper are:\n* In Section 4.1, the authors generate the adversarial examples according to the linear model. I understand the decision boundaries of the linear model $f^{bdy}(z)$ and the one-hidden-layer neural network are the same (Theorem 3.3). However, I don't think we can directly replace the neural work with the linear model to generate adversarial examples since adversarial examples are generated by optimizing the loss, which is different. Can the authors provide more theoretical explanations for this?\n* Although the authors claim that they focus on one-hidden-layer neural networks, they make some approximations and actually focus on linear models. So the contribution of this paper is reduced.\n\nSome minor concerns:\n* In the third paragraph of the introduction, the authors say, \"Nevertheless, neural networks can learn to accurately classify benign samples from such adversarially perturbed samples with seemingly incorrect labels\". Can you provide more explanation for this? Does it mean we can train a model that can accurately distinguish the adversarial examples from the clean sample?\n* In this work, the authors show that the model trained on adversarial perturbations with incorrect labels (i.e., $y^{adv}$) can generate well on the clean data. But as we know, traditional adversarial training is based on adversarial examples with correct labels (i.e., $y^{natural}$). So, why do these two methods both generate well on the clean data? \n* I would like to know the adversarial accuracy of the method in your experiments.\n* In Eq. (2), does $x_n$ refer to the training data $x_n$? It seems that $x_n$ here is new test data that is different from the training data $x_n$. Otherwise, the gradient calculation in Eq. (2) should be reconsidered. Please check this out.\n* The assumption in Theorem 4.2 is somewhat strong: $|\\sum\\lambda_n y_n <x_n,z>|=\\Theta(g(N,d))$ if $\\sum\\lambda_n  |<x_n,z>|=\\Theta(g(N,d))$. It is intuitive that the first term is much smaller than the second term. What would your theorem be without this assumption?\n* In Section 5.1, I have some confusion about some statements. For example, in Fig 1, the authors mentioned standard data and noisy data. But in their setting, there are two kinds of noisy data: the dataset is generated randomly and can be viewed as some noises; the adversarial perturbations are superposed on random noises. I am confused as to what \"standard data\" and \"noise\" refer to. I strongly recommend the authors make more clear clarifications in the paper.\n* As the authors claim in the experiments, there are some counterexamples. I think more discussions about these counterexamples are needed. Is it because the effect of learning from mislabeled natural data dominates the effect of learning from perturbation?\n* Since there are negative effects of learning from natural data or noises, why doesn't the learner solely learn from the perturbations?", "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)