Wide Two-Layer Networks can Learn from Adversarial Perturbations
Authors: Soichiro Kumano
Hiroshi Kera
Toshihiko Yamasaki
Venue: NeurIPS 2024 poster (2024)
Keywords: Adversarial Perturbations
Adversarial Examples
Adversarial Attacks
Non-Robust Features
Perturbation Learning
Learning from Adversarial Perturbations
Primary area: learning_theory
TL;DR: Justify the feature hypothesis and perturbation learning.

Abstract: Adversarial examples have raised several open questions, such as why they can deceive classifiers and transfer between different models. A prevailing hypothesis to explain these phenomena suggests that adversarial perturbations appear as random noise but contain class-specific features. This hypothesis is supported by the success of perturbation learning, where classifiers trained solely on adversarial examples and the corresponding incorrect labels generalize well to correctly labeled test data. Although this hypothesis and perturbation learning are effective in explaining intriguing properties of adversarial examples, their solid theoretical foundation is limited. In this study, we theoretically explain the counterintuitive success of perturbation learning. We assume wide two-layer networks and the results hold for any data distribution. We prove that adversarial perturbations contain sufficient class-specific features for networks to generalize from them. Moreover, the predictions of classifiers trained on mislabeled adversarial examples coincide with those of classifiers trained on correctly labeled clean samples. The code is available at https://github.com/s-kumano/perturbation-learning.

Wide Two-Layer Networks can Learn from Adversarial Perturbations
Soichiro Kumano
Hiroshi Kera
The University of Tokyo kumano@cvm. t. u-tokyo ac. jp
Chiba University, Zuse Institute Berlin kera@chiba-u.
Toshihiko Yamasaki
The University of Tokyo
yamasaki @cvm. tww.tt..o..occc.. ac.
Abstract
Adversarial examples have raised several open questions, such why they deceive classifiers and transfer between different models. A prevailing hypothesis to explain these phenomena suggests that adversarial perturbations appear as random noise but contain class-specific features. This hypothesis is supported by the success of perturbation learning, where classifiers trained solely on adversarial examples and the corresponding incorrect labels generalize well to correctly labeled test data. Although this hypothesis and perturbation learning are effective in explaining intriguing properties of adversarial examples, their solid theoretical foundation is limited. In this study, we theoretically explain the counterintuitive success of perturbation learning. We assume wide two-layer networks and the results hold for any data distribution. We prove that adversarial perturbations contain sufficient class-specific features for networks to generalize from them. Moreover, the predictions of classifiers trained on mislabeled adversarial examples coincide with those of classifiers trained on correctly labeled clean samples. The code is available https: : //t///giitt titt.u..... com/s s kukkkuuaoooaa tureeruuraiioon on- learning.
Introduction
Adversarial examples [41], which are imperceptibly perturbed inputs designed deceive machine learning models, have raised significant concerns about the robustness and reliability of these models. Despite their importance, the underlying mechanisms of adversarial examples are not yet fully understood. A prevailing hypothesis to explain the intriguing properties of adversarial examples is the "feature hypothesis" [22]. This hypothesis posits that adversarial perturbations, while appearing as imperceptible noise to humans, contain class class-specific features. The feature hypothesis provides unified explanation for several puzzling phenomena associated with adversarial examples, such as their ability to deceive classifiers, transfcrability across models, and so on (cf. Section 2.
Perturbation learning [22) provides empirical evidence supporting the feature hypothesis. In this leamn ing, classifiers are trained solely on adversarial examples that are mislabeled in human perception, yet they demonstrate remarkable generalization clean data (Fig. 1). For example, classifiers achieved 77% accuracy on the correctly labeled clean test dataset of CIFAR-10 [27], even though they
'This the critical difference hetween perturbation learning and adversarial training or training with noisy labels. Perturbation learning shows the learnability solely from adversarial examples (e.g., cal adversarial image) that always have incorrect labels (e.g.. the bird label) to classify clean test images with the correct labels (i.e., bird clean images to the bird class). Perturbation learning does not aim to learn robustly against adversarial examples or noisy labels. Refer to Appendix A in [28) for further clarifications.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Training on adv. examples Duily from /(=;0v.i trained on clean samples
Test clean samples in test datasct
hird/ horse/ cat
cat
hird
horse
cat
g(a; Ow:.)
cat
s(m; Owa)
(Entirely mislabeled)
(Correctly labeled)
Figure 1: Counterintuitive generalization of perturbation learning." A classifier is trained solely on mislabeled adversarial examples Dudv : {( 1/2 ) ) to mislead classifier f. which is trained on correctly labeled clean samples D == {( Dr.) }n) Jn= into predicting y (# yn). Surprisingly, despite being trained only on mislabeled data, the classifier g generalizes well to clean test samples. This counterintuitive result suggests that adversarial perturbations contain label-aligned class features, enabling the classifier to generalize from them.
These examples æi are generated
were trained on entirely mislabeled adversarial examples (e.g., a cat adversarial image labeled as a bird) [28]. This surprising result suggests that adversarial perturbations encode class-relevant features that enable classifiers to learn meaningful representations. However, despite the empirical support, the theoretical foundations of the feature hypothesis and perturbation learning remain limited. While a recent study [28] provided theoretical justifications, their results rely on stringent assumptions about data distribution, perturbation design, training procedure, and model architectures.
In this study, we theoretically address the understanding and justification of the feature hypothesis and perturbation learning. First, support the feature hypothesis, we show that adversarial perturbations, while appearing as random noise, are parallel to the weighted sum of all training samples. This result suggests that single perturbation derived from a classifier and input can potentially contain information about the entire training dataset. In particular, for some specific cases (e.g.. when training samples are mutually orthogonal), perturbations include all training data and labels without loss of information. We then reveal that class features within perturbations enable classifiers to generalize from them. Specifically, under three mild conditions, the predictions of a classifier trained on adversarial perturbations are consistent with those of a classifier trained on correctly labeled clean samples. These three conditions can be interpreted from geometric and quantitative perspectives. Finally, we demonstrate that under similar conditions, the prediction agreement is observed between a classifier trained on mislabeled adversarial examples and one trained on correctly labeled clean samples, justifying the empirical success of perturbation learning.
Our analysis assumes two-layer neural networks with sufficient width but does not impose any assumptions on data distribution, which is a substantial progress from prior work [28] that considered mutually orthogonal training samples. In addition, our perturbation design, training procedure, activation functions, and bias availability are milder. In short, as shown in Tab. 1, except for the wide width assumption, our analysis requires milder conditions than prior work. Our contributions can be summarized as follows:
We provide a theoretical justification for the feature hypothesis and perturbation learning using wide two-layer neural networks, considering any data distribution and realistic problem settings. Except for the wide width, our assumptions are substantially milder than [28].
We demonstrate that adversarial perturbations parallel to the weighted sum of training samples, suggesting that single perturbation can potentially contain information about the entire training dataset. This result supports the feature hypothesis.
We prove that under three mild conditions, the predictions of a classifier trained on pertur- bations are consistent with those of classifier trained on correctly labeled clean samples. Moreover, under similar conditions, the prediction agreement between a classifier trained on mislabeled adversarial samples and one trained on clean samples is observed, providing a theoretical justification for the empirical success of perturbation learning.

---

2 Background and Related Work
2.1 Feature Hypothesis and Perturbation Learning
It has been hypothesized that adversarial perturbations contain class-specific features, although appearing as random noise [22]. This hypothesis, or feature hypothesis, offers unified expla- nation for several open questions related to adversarial examples. For example, misclassification by classifiers and transferability across models [21, 41] can be attributed to the response to fea- tures within perturbations. Furthermore, according to this hypothesis, adversarially robust models achieve robustness by discarding brittle yet predictive features and focusing on more stable and semantically meaningful features. This interpretation explains the phenomena observed with robust models, such as the trade-off between accuracy and robustness [13, 32, 34, 35, 40, 42, 46, 47], perceptually--alinee gradients [1. 4, 7, 17, 18, 26, 38, 39, 42, 48], and enhanced transfer learning capabilities [1, 12, 37, 43).
Perturbation learning' [22] provides empirical support for the feature hypothesis. In perturbation learning, the dataset appears entirely mislabeled to human perception. However, the hypothesis suggests that adversarial perturbations in the dataset include label-aligned class features. Indeed, it has been observed that classifiers trained through perturbation learning can extract generalizable features from these perturbations and achieve high test accuracy (e.g.. 92% for MNIST [11], 54% for Fashion- MNIST [45], and 77% for CIFAR-10 [27]). empirically justifying the feature hypothesis [22, 28).
While the feature hypothesis and perturbation learning are empirically effective in understanding adversarial examples, their theoretical foundations are very limited. Only one recent study [28] theoretically demonstrated that perturbations contain class features and that classifiers can generalize from them. However, their results relied on stringent conditions (e.g.. mutually orthogonal training samples), which might not fully explain the success of perturbation learning in diverse settings.
In this study, for wide two-layer networks, we obtain results equivalent those in [28] under more relaxed conditions (cf. Section 3.4). We provide the first theoretical justification for the feature hypothesis and perturbation learning under any data distribution and in a mild training setting.
2.2 Theoretical Framework: Lazy Training
Theoretical amalysis of neural networks is generally challenging due to the non-convex nature of the loss surface. To address this, recent studies have focused on the lazy training regime, where the parameters of neural networks hardly change during training [5, 6, 9, 20, 25, 30, 33, 44, 49]. In this regime, neural networks behave almost linearly around their initialization, simplifying the learning dynamics. One of the key observation in lazy training is that, in wide two-layer neural networks, most derivatives of hidden outputs through (Leaky-) ReLU activation remain constant during training [30], which forms the basis of our theoretical framework (cf. Section 3.3). This observation has been extended to show that the neural tangent kernel remains invariant during training [2, 3, 14, 15, 23, 29].
In contrast, the feature learning regime, where parameters move significantly away from their initialization, has been explored in various studies [9, 20, 44]. Prior work on justifying perturbation learning [28] employs the feature learning regime, building related findings in this area [19, 24, 31]. In our study, we adopt the lazy training regime and relax several conditions assumed in previous work [28] by introducing a wide width assumption (cf. Tab. 1). This adjustment is enabled by differences in the theoretical tools used.
3 Theoretical Results
Notation. For n E N, let [n] := (L....,
n.. ..]........... and the inner product by (z1, Z2). Vectors 21 and Zạ are called parallel and are denoted by 2 // 22 if there exists C' E R such that 21 Czy. Le 0²) be the Gaussian distribution with mean / E IR
For 21, Z2 E IRd, we denote the Euclidean norm by ||=|
and variance o² 2 0 and (S) be the uniform distribution on set S C R. We use Ω( O -). and
OC-) only to hide constant factors, and Ộ(( @(-). ). and Ō .) hide polylogarithmic factors.
3

---

Table 1: Comparison with existing work [28]. With wide network assumption, we improve the existing results from the perspective of data distribution, perturbation design, training time, loss function, and network architecture. Note that the non-bias and leaky-ReL.U assumptions of [28] are critical for deriving their results. A detailed comparison can be found in Section 3.4.
[28]
Ours
Training samples
Mutually orthogonal
Any
Perturbation type
Dracle-based
Standard gradient-based
Perturbation budget
Unrealistically tight
Any
Training time
Infinite
Any
Loss function
Exponential or logistic Not available
Differentiable, non-decreasing
Network bias
Available
Activation
Leaky-ReL.U
ReLU and Leaky-ReLUU
Network width
Any
Sufficiently wide (but finite)
Theoretical framework
Feature learning
Lazy training
Common
Binary classification,, two-layer network, gradient flow
3.1 Problem Setup
In this study, we consider the dynamics of perturbation learning in binary classification problem with a two-layer neural network trained by gradient flow. First, we formally define the perturbation learning framework. The outline of perturbation learning is as follows: (i) train a classifier on correctly labeled clean samples, (ii) create adversarial samples based on the trained classifier, and (iii) train another classifier on the mislabeled adversarial samples.
Network trained on correctly labeled clean samples. We consider two-layer neural network f F' + R. Let V := (V1...., Dm) um) E Rmxd and a := (a1,..., an) E R be the hidden weight and bias, respectively. We also deseribe V == (V.)) be the readout weight. While V and
Let a == (ar1...., .m. E R trainable, fixed during training. Denote the trainable parameters by 0v vv.a= == [V.a). We initialize Vij (O, 1/d). a; ~ (0, 1), and a, ~ (0, 1/m) for each i E [m]] and E [d]. The activation function is either ReLU or Reaak--eLUU ((x) max(yæ, 2)) for y E [0, 1). Finally, the network is given by f(z; 0, 0v == E az (v., x) + a;).
Network trained on mislabeled adversarial samples. Similarly to f. we define network trained on mislabeled adversarial samples as g( 0w.r) := m ( x) + b,). Note that the initial- izations of I and g are independent.
Loss function. We consider differentiable, non-decreasing loss function e IR - IR, satisfying (2) 2 0 for any E R. Examples of such loss functions include the identity loss {(z) = exponential loss {()) == exp(2), and logistic loss {(2) == In(1 + exp(z)).
Training. We here describe the training process of the network f on correctly labeled clean samples. The training of g is similarly defined. Let D = {(I,, yn) )n)) W training dataset. The loss over 'D defined as L(Ov D)) == (1/N) E f(-yn.f (mr a))- The network parameters are updated by gradient flow d0v
C Rd x {+1} be correctly labeled
:= dc (t); D) 100 where 2 0 is the training time. We consider T, > training steps, producing f(,;; 0v (T₁)). For
(t) (t)
notational simplicity, we write f(-;t) : f( (t)).
Note that we do not consider whether f(:;Ty) perfectly classify D. We discuss whether the classifier trained on adversarial examples crafted via f(,;;Ty), can mimic the predictions of TT;))
Ad Adversarial perturbations. We consider single-step gradient- pradient-based perturbation, which is common perturbation design [21]. An adversarial example x E Id and its corresponding adversarial perturbation r. E TRdd are defined as follows:
V 2., e f(ani Ty)) Tn | an (l- f(x Ty))ll
adv I. + Tay
(1)
where e > 0 is the perturbation constraint and gady E {+1} is the target label. The adversarial perturbation T. on x, is designed to increase y (( :Ty) under the constraint ||r,]] S e.

---

Mislabeled dataset. We consider two configurations of a dataset Dadv for training First, we follow the original perturbation learning approach, where classifiers are trained on adversarial perturbations superposed on natural images, i.e., DDavv := {(ar u/ )) m==1- This setting helps to understand the prior perturbation learning process. Second, we directly consider learning from perturbations rather than adversarial examples, i.e., Dadv == {(Tn. vodv) ) This setting directly addresses the question whether classifiers can generalize from class features in perturbations.
Summary. The problem setting is summarized as follows:
Setting 3.1 (Perturbation learning). Independently initialize Vi ~ (0, Wy ~ ~N 1/d).
a, (0, 1), by (O0 1), a; (0, 1/m),, and B; ~ (0, 1/m) for each i [m] and j E [d] Train a two-layer neural network f parameterized by 8v.a with (7-scaled Leaky-) ReLU on a dataset
D = {( Vr.) i using gradient flow with a loss Liθv,ai (10vva:D) D) for training time Ty > 0. Create
1.N dataset Dady by one of the following procedures with {u Jn=1 E {+1}%
Scenario (a)
Dadv := ((rn (art))) ]
(2)
Scenario (b)
Dudv := (x Vn )
(3)
Train a two-layer neural network parameterized by Ow.b on the dataset Dady using gradient flow with a loss L(Ow, Dadv) for training time Tg > O.
Our interests are (i) the relationship between pwwceppuullly nowttealllllllooo-eeeeeeeeeeeeee noise-like adversarial perturbations (rn J and clean training samples {I yn (n)]kne (ef. Theorem 3.3), and (ii) whether the classifier g(;;Ty) trained on the adversarial perturbations samples Dady can mimic the predictions of the classifier TT) trained on the clean samples (cf. Theorems 3.4 and 3.5).
3.2 Main Results
For æ1, 22 Idd we use ((21 (7(1 71, (1++))))111)))))))))))) +)/2 defined as (cf. Lemma C.4):
(211, x2) = Bu- lo' =1) + a)ø ((v, #2) + a)),
(4)
where d'(x) do(x)/dz: First, introduce assumption network width.
Assumption 3.2 (Wide network). Network width m satisfies
(
N N
J"e ((((nn((zntt)) dt 1- el-vrry pdv fla',; t)) dt )
m >
8
(5)
where æ', Tn for Scenario (a) and x', zadv for Scenario (b) in Setting 3.1. In particular, (dd T)) for {(s) =
This assumption requires sufficiently large width that regularizes the variations in parameters and forms the basis lazy training (cf. Section 3.3). The width is always required to grow with the speed of the squared input dimension d2, The relationship between the width and two training times, T'y and Tg, depends on the training set { }r)) and loss function f. For example, if the training set is easily separable and the loss has an exponential tail, the derivative of the loss function might decrease rapidly with training time and small m is enough to satisfy the assumption. For the identity loss, m is consistently required to satisfy f2(d2(T) + T, 2)). Note that the required values of I's and T, (and the corresponding m) for desirable loss value remain an open question in the community. Our experimental results show that m ss 100 is sufficient to verify our theorems for high-dimensional Gaussian distributions. Under this assumption, we consider the direction of the adversarial perturbation.
Theorem 3.3 (Direction of adversarial perturbation). Let 8 = ((1) be a small positive number. Under Assumption 3.2, for any [N], with probability at least 5, the adversarial perturbation
5

---

f(z)
a(
(()) >
f(z).(())
20
(a) Func. margin cond. 1
(b) Func. margin cond.
(c) greement cond.
(d) Intersection
Figure The regions where Ineqs. (9) and (10) and Eq. (11) hold (colored areas) and their intersection.
is parallel to the weighted sum of training samples as follows:
N
yn ( wa )a (¹d
Tnll
E
e(-w>s(aax: ()) di + En,
(6)
N
k=1
where En satisfies |E..|| = (1). In particular, for ((s) =
Tr N
N
Σ
yk b (T. T& Da + En.
Note that the confidence level 8 only logarithmically affects the norm of the remainder term &n. This theorem indicates that the direction of a single perturbation can be represented as the weighted sum of y& and remainder term &... Interestingly, this result suggests that single perturbation derived from classifier and sample can potentially contain information about the entire training dataset {(xr, Vn.) ( Particularly, in some cases (e.g., training samples mutually orthogonal), #x are not cancelled out by each other, and thus the single perturbation rn contains all training data and labels without loss of information." These results theoretically support the feature hypothesis.
Consider the case with the identity loss. While the norm of the first term OTT vd), the norm of the remainder is constrained to (1), suggesting that larger training time Ty and input dimension strengthen the alignment between the perturbation and weighted sum.
Then, we consider the learning solely from these perturbations. The following theorem is a special case of Theorem D.17, which addresses a broader loss class and any sampling of yadv E {=1}.
Theorem 3.4 (Perturbation learning, Scenario (a), special case of Theorem D.17), Consider Sce-
mario (a) in Setting 3.1. Assume {(s) and gadv ~ ((+1)) for every E [N]. Let 5 (1) be small positive number and
N
N
N
f(z) =
Σ n=1
Un Da 2)(2n1 2), (x(2)=
4 (T z)
yk (a (x)( (8)
N2 n=1
Under Assumption 3.2. for any z Rdd if
1+ (1++7)) -
(Functional margin condition 1)
15(=)1 Ö
(9)
1
+ Vd
(Functional margin condition 2)
[b.(2)) δ
(10)
Tj
T
(Agreement condition)
sgn(f(=)) = sgn(
(11)
then, with probability least 8, sgn(f(2:Ty)) = =gnng]))))))
2; T,)) holds.
Note that the confidence level å only logarithmically affects the right terms of Ineqs. (9) and (10).
which is why these terms appear independent of 6. This theorem states that the predictions of
classifier g trained solely on adversarial perturbations {[Tr. y yavv ) coincide with those of
classifier trained on standard training samples ((x,, Vn) ) if the three conditions hold. The two
Reeall @ ((x,, æx) 0.

---

functions, ff and ÿ. which govern these conditions, can be viewed as key components that significantly influence the predictions of and (cf. Section 3.3). The conditions can be interpreted as follows.
Geometrical perspective. The functional margin conditions, Ineqs. (9) and (10), require the func- tional margins of If and to exceed certain thresholds. In the input space 2 E Id,, these conditions correspond to regions far from the decision boundaries f(z) 0 and ((=) = 0 (Fig. 2(a) and (b)). In d-dimensional space, Lz-distance scales with vd, making the right terms of Ineqs. (9) and (10) relatively small when the perturbation size (vdd); hence, a larger d facilitates the satisfaction of these conditions. Furthermore, Eq. (11) necessitates the agreement of the signs of these two decision boundaries (Fig. 2(c)). Consequently, the region where all conditions hold, ie.. where the prediction match occurs, can be characterized by the two piecewise linear functions (Fig. 2(d)).
Quantitative perspective (functional margin conditions). A large perturbation size c facilitates the satisfaction of Ineq. (10). In digendimensional spaces, achieving the required margin conditions demands perturbations of at least Q ((v)) in magnitude, aligning with empirical scaling laws for L2 perturbations. However, increasing alone is insufficient for the satisfaction because the right term of Ineq. (10) has e-irrelevant term ( Assume @(vd). The absolute values of f and 9 grow with (d) due to (x. z), while the right terms of Ineqs. (9) and (10) are independent of d. Thus, a larger d consistently facilitates the satisfaction. The training times Ty and T. can reduce the right terms, but these terms contain iume-independent terms ((1) and ((1/VN), indicating that longer training times do not necessarily guarantee the satisfaction. A large sample size N also helps to satisfy Ineq. (10), but similarly, it is not sufficient. In summary, while a larger input dimension d consistently support the success of perturbation learning, a larger perturbation size sample size N, and training times Ty, To provide partial, but not definitive, benefits.
Quantitative perspective (agreement condition). It is difficult interpret the agreement condition, Eq. (11), in its current form. We consider the following sufficient condition (cf. Lemma 1.19):
1 Un (En. 2)1
Eq. (11),
(12)
max (att,, # En=1 X(xn, x) (Ea, z)
++7
X(21, 22) =
e
22
|| (21. )2 + 21 22112
O().
(13)
2x
|
22
+ (z1, )2 + | + x2 2d
Note that the left term exceed one A(21, z2) lies in (0.34, 1). It clear that large negative slope of Leaky-Rel.U y facilitates the satisfaction. The magnitude of the left term depends on the consistency of the correlation (inner product) between and ,, for every n. For example, when consistently exhibits a positive or negative correlation with yn the left term exceeds one, and the condition is satisfied. with the other half, the left term may output a small value, and the condition is not satisfied. In summary, the agreement condition depends on the consistency of the correlation between z and Ya
contrast, if positively correlates with half of the samples and negatively
Finally, we justify the success of perturbation learning in Scenario (b).
Theorem 3.5 (Perturbation learning, Scenario (b), special case of Theorem D.18), Consider Sce- nario (b) in Setting 3.1. Assume {(s) = and you ~ U({+1)) for every n E [N]. Let O1) be small positive number and
N
N
1
go(z) =
Σ
2
adv
z)
Σ
yk (# (x 2).
(14)
N2
Under Assumption 3.2. for any z E Rdd if the functional margin condition (Ineq. (9)),
(Func. margin cond. 2) [dn(2)] > θ ( T
v VEN ((En, z) + 1)2
+ Vd
Tg +
(15)
N
(Agreement condition)
sgn(f(z)) sgn (g))))))
(16)
One can analyze the agreement condition by using the relationship between & and the arc-cosine kernel [10].
7

---

then, with probability at least - 8, sgn(f(2;Ty)) = (gn(o(2;Tg)) holds.
This is a special case of Theorem D.18, which addresses differentiable, non-decreasing losses and
any sampling of yn yarv E {=1}. Similarly to Theorem 3.4, this theorem states that the predictions of a classifier g trained on randomly labeled adversarial examples ((x0 My )>== coincide with
those of a classifier f trained on standard training samples (In, In } if the three conditions hold.
Functional margin condition 1 is consistent with that in Theorem 3.4, i.c., Ineq. (9). The dcfinition of
(=(z) is slightly different from (z) in Theorem 3.4, with Tn replaced by an Due to this change
in the definition of (z), functional margin condition 2, Ineq. (15), and the agreement condition, Eq. (16), slightly differ from those in Theorem 3.4.
Assume e = ((va). Similarly to Ineq. (10), the left term of Ineq. (15) grows with (d)) due to the inner product. In contrast Ineq. (10), the right term of Ineq. (15) includes a term that grows with
VE ((xn: 2) + 1)2/N = Odd/VN). This suggests that Scenario (b) necessitates a larger sample size N than Scenario (a) to mitigate the effect of d.
Furthermore, Eqs. (11) and (16) hold simultancously (i.c., sgn(f(z)) (g = sgn( (z))) if Ek= (,x, Zxt) (xxx z) outputs the same sign for any n. This indicates that there might exist regions where the prediction match is observed regardless of the scenarios, and these regions are partially determined by the n linear boundaries. Note that Ineq. (12) also serves as sufficient condition for Eq. (16), and the quantitative analysis for Eq. (11) can be applied to Eq. (16) as well.
3.3 Sketch of Proof
In this section, for simplicity, we provide a sketch of the proof for Theorems 3.3 and 3.4 with infinite network width m - oc, networks without biases, and identity loss. A proof for the general case can be found in Appendix D.
Lazy training. First, we introduce the concept of lazy training, where network parameters and outputs of hidden neurons change negligibly during training when the network width is sufficiently large [9, 30J. Since readout weight a; is sampled from NN 1/m), from gradient flow, for any E R
(v)(t) dt
N Σ (nn 2) 1" d'((,((t),
CTTs (
dt,
ō
(17)
Therefore, m - co, the inner product between the time variation of hidden parameter and an input approaches zero. This suggests that the sign of the output of a hidden neuron do not change:
= sgn (1o.(0) 2) + (T." dt
)
dt 2
m0000 (gn((v((0),,)) (18)
dt
Therefore, o' <'((0) (Ty) 2)) = (0), 2)). Recall ((2) = max(?z,2)
Theorem 3.3. From the perturbation definition Eq. (1), the perturbation On is parallel to V fI (TT))). Using d' ((((u,TTy),)) = (() z)),
Tn Ve. f(x V (TT)) = Σ a ((v, x.,)) 2,(0) /0' Ty dvv((t)
m
df dt).
(19)
The first term is constrained Õ(1). Let o ( wx) Ee (d' ((v, x..) ( xx)))]
(f; ((v;) xb)) + 4( x4)) as m + co, the second term becomes Using Em a
dt: dt dl
Ti
N
and (v:)( x.,))
yk ((x, æx xx
(20)
N
Theorem 3.4. Similarly to the above, we can represent the adversarial perturbation r, as follows:
V Ve, (wni (TT)) =
N ye T (z,,, 2xx) (Ixk, z).
Tn := cy adv
(21)
|/ a. f(x ((Ty))I
N
8

---

Assuming Ei= (1), - Ō(1) = 0 for simplicity. the network prediction f(z; V(Tz)) trained on [(En, )n)] can be represented as follows:
Tj
N
((z)V(T))) = Σ og ((00((
E
yn Da (ann
(22)
and (z; ((T))) = sgn Ex=1 yn (( 2) (zn,
In addition, g(z; ((y)) trained on
(Fnnyan ) can be represented as follows:
Tg
g(z; (Tx)) 12
Σ
yu 2 (z ax) [b)) x),
(23)
N2vd
n=1
and sgn(g(>; (T,))) sgn N o condition Eq. (11) holds, then sgu ((T)))
Ex= Us $ ( 22 (2x,, Thus, if the agreement
sgn(g(z; sgn(((z W (T,)).
Formal proof. In the above sketch of proof, we have introduced several approximations. Rigorous evaluations are provided in Appendix D. For example, in the sketch, we assumed m - oc, ensuring that the signs of all hidden layer outputs remain unchanged. In contrast, the formal proof derives bound on the width m that ensures that the number of hidden neurons with flipped signs is at most ((ym) which makes the discussion (e.g., about Eqs. (18) and (19)) more complicated. Moreover, in Eq. (21), we neglected the first term of Eq. (19), but the formal proof carefully considers the impact the subsequent steps. The functional margin conditions arise from the evaluation of these remainder terms.
3.4 Comparison with Prior Work and Limitations
In this section, we compare our results with [28] and discuss the limitations of our work. In summary, our results justify the feature hypothesis and perturbation learning under substantially milder conditions than [28], except for network width (ef. Tab. 1). The assumption of wide two-layer networks is our main limitation.
Goals, results, and tools. The goals of our work and [28] are the same: justifying the feature hypothesis and perturbation learning. The conclusions drawn are also equivalent. However, our assumptions are much milder than theirs. This is due the differences the analytical approaches. While they leverage research on feature learning [19, 24, 31], we utilize the concept of lazy training [9, 30]. which enables us substantially relax the conditions.
Data distribution. Prior work imposes strong assumption that training samples with/without adversarial perturbations mutually orthogonal, i.e., (m.,, ax) As O and (aradv arddv) for any # k. This condition is stringent and is hard to hold for real-world datasets. Moreover, it may not even hold for data sampled from a zero-mean Gaussian distribution in some common situations (e.g.. the sample size is sufficiently larger than the dimension). We do not impose any assumptions on the data distribution. This the first result that theoretically supports the feature hypothesis and the success of perturbation learning on realistic data distribution.
Perturbation design. Prior work defined the perturbation form using the decision boundary of classifier. However, this is not only uncommon but also theoretically computable only in limited problem settings. Additionally, they constrained perturbation size to c = O(vd/N), which becomes unrealistically small for a large sample size and is far from the practical constraint @(v7). We employ a single-step gradient- brase method [21], which is commonly used in practice, and the perturbation constraint can be set arbitrarily.
Training time, loss function, network bias, and activation. First, it should be noted that these constraints are critical for deriving the results in [28]. This is because their theoretical framework [19, 24, 31] substantially requires the above conditions. We consider arbitrary training time, wide class of loss functions, and (Leaky-) ReLU networks with bias availability. In contrast, they considered infinite training time, loss functions with exponential tails, homogeneous neural networks (thus requiring no bias), and Leaky-Rel.U networks (the theorem becomes harder to hold as the negative slope of Leaky-Rel.U approaches zero), which are essential for deriving their results (cf. the proofs of Theorem 4.4 in [31] and the proof of Theorem 3.2 in [19]).

---

1.00
1.00
Accuracy
0.75
0.75
Standard
0.50
0.50
Perturbation
10
20
30
40
50
60
70
80
90
100
10
10'
10
10a
Input dimension d
Hidden dimension
Figure 3: Accuracy on the mean-shifted Gaussian dataset in Scenario (a). The blue lines represent accuracy of the classifier f on D, i.e., training aceuracy. The orange lines represent accuracy of the classifier on DD
Limitations. Compared to [28], our main limitation is the requirement for sufficient, though finite, network width. Moreover, our analysis is confined to two-layer networks, a common constraint in previous work. In practice, perturbation learning often employs deeper, and not necessarily wider, networks, which limits the direct applicability of our theoretical insights to more complex architectures. This assumption of a shallow network introduces another limitation. While deep neural networks typically capture high-level features from images and adversarial attacks are considered to exploit them, our framework focuses solely the low-level features (i.e., F, itself) in adversarial perturbations and their extraction through perturbation learning, as shown Theorems 3.3 to 3.5. Relaxing the shallow network constraint may allow to capture a broader set of features present in adversarial perturbations. Despite these limitations, our work is the first to rigorously support the feature hypothesis and validate perturbation learning under realistic data distributions, perturbation designs, and training settings, marking a substantial advancement in the theoretical understanding of adversarial examples.
4 Experiments
comprehensive set of experiments conducted to validate our theorems can be found in Appendix B. In this section, briefly present results that confirm Theorem 3.4. As a training dataset D: = {(I,. yn) ) we employed a synthetic training dataset to easily change the input dimension, which effectively helps perturbation learning in both scenarios, as predicted by our theorems. Note that the perturbation learning on real-world datasets can be found in the literature [22, 28). We generated synthetic data and labels from the mean-shifted Gaussian distribution as follows: {ar, ) are independently sampled from (0.3 X X 1. I). and is set to one if r2 E [N/2] and minus one otherwise. The experimental settings are as follows: d 100, N {(s) == s, 0.01, and the number of training steps is set to 1,000 for both f and experimental results for perturbation learning under Scenario (a) are shown Fig. 3. A high input dimension facilitates the alignment between f and g. Our theoretical results assume wide network width, and Fig. indicates that sufficiently large width consistently stabilize the alignment.
000, m 100, 7 The
5 Conclusion
We provided a theoretical justification for perturbation learning and the feature hypothesis. We demonstrated that adversarial perturbations contain class-specific features sufficient for networks to generalize from. Moreover, we revealed that the predictions of classifier trained solely on these perturbations or mislabeled adversarial examples coincide with those of a classifier trained on correctly labeled training samples under three mild conditions. Except for wide two-layer networks, our assumption is substantially milder than prior work [28].
Acknowledgments and Disclosure of Funding
S. Kumano was supported by JSPS KAKENHI Grant Number JP23KJ0789 and by JST, ACT-X Grant Number JPMJAX23C7, JAPAN. Kera was supported by JSPS KAKENHI Grant Number JP22K17962. T. Yamasaki supported by JSPS KAKENHI Grant Number JP22H03640, JST
10

---

ASPIRE Program Grant Number JPMJAP2303, and Institute for Al and Beyond of The University of Tokyo.
References
[1] G. Aggarwal, A. Sinha, N. Kumari, and M. Singh. On the benefits of models with perceptually- aligned gradients. In ICLR WS, 2020.
[2] Z. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via over- parameterization. ICML, pages 242-252, 2019.
[3] S. Arora, S. Du, W. Hu, Z. Li, and R. Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In ICML, pages 322-332, 2019.
[4] M. Augustin, A. Meinke, and M. Hein. Adversarial robustness on in-and out-distribution improves explainability. In ECCV, pages 228-245, 2020.
[5] Y. Cao and Q. Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In NeurlPS, volume 32, 2019.
[6] Y. Cao and Q. Gu. Generalization error bounds of gradient descent for learning over- parameterized deep relu networks. In AAAI, volume 34, pages 3349-3356, 2020.
[7] P. Chalasani, J. Chen, A. R. Chowdhury, X. Wu, and S. Jha. Concise explanations of neural networks using adversarial training. In ICML. pages 1383-1391, 2020.
[8] S.-H. Chang, C. Cosman, and L. B. Milstein. Chernoff-typp bounds for the gaussian error function. IEEE Transactions on Communications, (9(11):299-2944,, 2011.
[9] L. Chizat, E. Oyallon, and Bach, On lazy training in differentiable programming. In NeurIPS, volume 32, 2019.
[10] Y. Cho and L. Saul. Kernll methods for deep learning, In NeurlPS, volume 22, 2009.
[11] L. Deng. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 1961)114-114,, 2012.
[12] Z. Deng, L. Zhang, K. Vodrahalli, K. Kawaguchi, and J. Y. Zou. Adversarial training helps transfer learning via better representations. NeurIPS, volume 34, pages 25179-25191, 2021.
[13] E. Dobriban, H. Hassani, D. Hong, and A. Robey. Provable tradeoffs in adversarially robust classification. IEEE Transactions Information Theory, 2023.
[14] S. Du, J. Lee, H. Li, Wang, and Zhai. Gradient descent finds global minima of deep neural networks. In ICML, pages 1675-1685, 2019.
[15] S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes parameterized neural networks. In ICLR, 2019.
[16] J. Duchi. Lecture notes on statistics and information theory, 2023.
[17] L. Engstrom, A. Ilyas, S. Santurkar, D. Tsipras, B. Tran, and A. Madry. Adversarial robustness as prior for learned representations. arXiv: /000009906.0045 2019.
[18] C. Etmann, Lunz, P. Maass, and C.-B. Schönlieb. On the connection between adversarial robustness and saliency map interpretabiliity In ICML, 2019.
[19] S. Frei, G. Vardi, P. L. Bartlett, N. Srebro, and W. Hu. Implicit bias in leaky relu networks trained on high-dimensional data. In ICLR, 2023.
[20] M. Geiger, S. Spigler, A. Jacot, and M. Wyart. Disentangling feature and lazy training in deep neural networks. Journal of Statistical Mechanics: Theory and Experiment, 1020(11):11) 13301, 2020.

---

[21] J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
[22] A. Ilyas, Santurkar, D. Tsipras, L. Engstrom, B. Tran, and A. Madry. Adversarial examples are not bugs, they are features. In NeurlPS, volume 32, pages 125-136 2019.
[23] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In NeurIPS, volume 31, 2018.
[24] Z. Ji and M. Telgarsky. Directional convergence and alignment deep learning. NeurIPS, volume 33, pages 17176-17186, 2020.
[25] Z. Ji and M. Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. ICLR, 2020.
[26] S. Kaur, J. Cohen, and Z. C. Lipton. Are perceptually- gradients a general property of robust classifiers? In NewrIPS WS, 2019.
[27] A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[28] S. Kumano, H. Kera, and T. Yamasaki. Theoretical understanding of learning from adversarial perturbations. In ICLR, 2024.
[29] J. Lee, L. Xiao, S. Schoenholz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and J. Pennington. Wide neural networks of any depth evolve linear models under gradient descent. In NeurIPS, volume 32, 2019.
[30] Y. Li and Y. Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In NeurlPS, volume 31, 2018.
[31] K. Lyu and J. Li. Gradient descent maximizes the margin of homogeneous neural networks. In ICLR, 2020.
[32] M. Mehrabi, A. Javanmard, R. A. Rossi, A. Rao, and T. Mai. Fundamental tradeoff's in distributionally adversarial training. In ICML, pages 7554, 2021.
[33] A. Montanari and Y. Zhong. The interpolation phase transition in neural networks: Memorization and generalization under lazy training. The Annals of Statistics, ((V5):2816-2844 2022.
[34] A. Raghunathan, S. M. Xie, F. Yang, J. Duchi, and P. Liang. Understanding and mitigating the tradeoff between robustness and accuracy. In ICML, 2020.
[35] A. Raghunathan, S. M. Xie, F. Yang, J. C. Duchi, and P. Liang. Adversarial training can hurt generalization. In JCML WS, 2019.
[36] Rigollet and J.-C. Hütter. High High-dimensional statistics. arXiv:2310.19244 2023.
[37] H. Salman, A. Ilyas, Engstrom, A. Kapoor, and A. Madry. Do adversarially robust imagenet models transfer better? In NeurIPS, volume 33, pages
2020.
[38] S. Santurkar, A. Ilyas, D. Tsipras, L. Engstrom, B. Tran, and A. Madry. Image synthesis with single (robust) classifier. In NeurIPS, volume 32, 2019.
[39] Srinivas, S. Bordt, and H. Lakkaraju. Which models have perceptually-aligne gradients? an explanation via off-manifold robustness. In NeurIPS, volume 36, 2023.
[40] D. Su, H. Zhang, H. Chen, J. Yi, P.-Y. Chen, and Y. Gao. Is robustness the cost of accuracy?-a comprehensive study on the robustness of deep image classification models. ECCV, pages 631-648, 2018.
[41] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. In ICLR, 2014.
[42] D. Tsipras, S. Santurkar, I.. Engstrom, A. Turner, and A. Madry. Robustness may at odds with accuracy. In ICLR, 2019.
12

---

[43] F. Utrera, E. Kravitz, N. B. Erichson, R. Khanna, and M. W. Mahoney. Adversarially- deep nets transfer better: Illustration on image classification. In ICLR. 2021.
[44] B. Woodworth, Gunasekar, D. Lee, E. Moroshko, P. Savarese, I. Golan, D. Soudry, and N. Srebro. Kernel and rich regimes in overparametrizee models. In COLT, pages 3635-3673, 2020.
[45] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-MNIST: novel image dataset for benchmarking machine learning algorithms. 170V:7700..07477, 2017.
[46] Y.-Y. Yang, C. Rashtchian, H. Zhang. R. Salakhutdinov, and K. Chaudhuri. A closer look accuracy vs. robustness. In NeurIPS, volume 33, pages 8588-8601, 2020.
[47] H. Zhang, Y. Yu, J. Jiao, E. Xing, L. El Ghaoui, and M. Jordan. Theoretically principled trade-off between robustness and accuracy. In ICMI., pages 7472-7482, 2019.
[48] Zhang and Z. Zhu, Interpreting adversarially trained convolutional neural networks. ICML, pages 7502-7511,201
[49] D. Zou, Y. Cao, D. Zhou, and Q. Gu. Gradient descent optimizes pereparameteri deep relu networks. Machine Learning, 109:467-499 492, 2020.
13

---

A Comparison with Prior Work
In this section, we compare our findings with those of prior work [28] and highlight new insights beyond technical contributions.
A.1 Feature Hypothesis (Theorem 3.3)
Our result offers new insight into the alignment between perturbations and training samples through the residual term &.- The direction of perturbation vector comprises two components: a weighted sum of the training samples (the main term) and a residual term. Our result suggests that as the input dimension increases, the residual term becomes smaller than the main term, thereby enhancing the alignment. In other words, perturbations more robustly encode class-specific features. This insight is unattainable in prior research due to the absence of residual term in their limited problem setting.
Additionally, our finding suggests that extended training time reinforces the directional alignment between perturbations and training samples. This concept is supported by practical intuition and experience but not addressed in prior work.
Our result further introduces coefficient, (x Tg2), for each adversarial perturbation. The coeffi- cient Φb n 2t depends on the slope of the activation function and the similarity between æ, and 2t (cf. Eq. (4)). This suggests that training samples with higher similarity each other exhibit a stronger influence within a perturbation. Although prior work includes similar coefficients, they cannot be explicitly computed.
A.2 Perturbation Learning (Theorems 3.4 and 3.5)
Our result establishes an explicit connection between the success of perturbation learning and training factors, such training time T, perturbation size e, input dimension d, sample size N, and confidence level 8. This result enhances our understanding of how these factors influence perturbation learning. For example. perturbation learning more likely to succeed with larger input dimension d and sample size N. Notably, our findings indicate that while a larger d consistently facilitates successful perturbation learning, a larger N alone is insufficient. In contrast, existing research does not elucidate the roles of these variables, merely showing that success is achievable when both d and N approach infinity.
B
Experimental Settings and Other Results
B.1
Datasets
We utilized two synthetic datasets and two widely used datasets, MNIST [11] and Fashion- MNIST [45]. The first synthetic dataset is derived from a zero-mean Gaussian distribution: {
independently sampled from (0, I) and [ym are independently sampled from ({+1]))
The second synthetic dataset is based on a mean-shifted Gaussian distribution: { J are indepen- dently sampled from (0.3 yn 1, I) and yn set one for [N/2] and minus one otherwise. We used data only from classes and 2 in MNIST (i.e., digits and 2) and those from classes 0 and 9 in Mussion-MNISST (i.e., T-shirt and ankle boot). To measure the agreement ratio between network predictions from standard training and perturbation learning, for the real-world dataset cases, we used standard test datasets, and for the synthetic dataset cases, we used 1,000 samples independently and identically sampled according to the training data distribution.
B.2 Settings
In this section, for notational simplicity, we denote the number of training epochs in standard training by Tj and in perturbation learning by Tg- Note that the original definitions of Ty and T, are continuous training steps in gradient flow, i.e., gradient descent with an infinitely small learning rate (cf. Section 3.)., which is conceptually distinct from the discrete steps in gradient descent with finitely small learning rates practice. addition, we denote the learning rates in standard training and perturbation learning ny and 7/. respectively.
14

---

We used non- stochastic gradient descent (i.e., each gradient calculation uses the entire dataset) with 0.9 momentum and the learning rate scheduler that multiplies a learning rate by 0.1 when a training loss has stopped improving during 10 epochs. For Figs. 3 to A12, we selected the best accuracy, agreement ratio, and cosine similarity from training with multiple initial learning rates.
In Figs. A4 to A11, the blue lines represent the accuracy of the classifier from standard training on the training dataset ((x,; Mnn n= Namely, these mean the training accuracy of f(-;Ty). The orange lines represent the accuracy of the classifier from perturbation learning on the standard (clean) training dataset { ((x, yn 3m)) rather than the perturbed dataset {(>= yn ) ) Namely, these mean the ratio that counterintuitive generalization occurs. Note that the orange lines stay around fifty percent (chance accuracy) if adversarial perturbations are not included in { / (cf. 0 in Figs. A4 to AI1). The green lines represent the agreement ratio between predictions f(;;Ty and o(:TT (Tyg
on a test dataset.
The cosine similarity in Fig. A12 is the average one between the experimentally calculated adversarial perturbation and the theoretically predicted one (cf. Eq. (1)) across all n. The blue lines are the same as those in Figs. A4 to All.
The two axes in Fig. A13 are the normalized average vectors of samples from the positive and negative classes, respectively. The blue circles and orange crosses correspond to the projections of positive and negative samples onto these axes. The gray and green areas indicate regions where two predictions are consistent and inconsistent, respectively. The red solid lines represent f() = 0. The
black dashed lines represent Ga (z) = 0 in Scenario (a) and (z) = O in Scenario (b).
Mean-Shifted Gaussian and Scenario (a). A common experimental setting for the mean-shifted
Gaussian dataset and Scenario (a) in Figs, A4 and A12 is as follows: input dimension d = 100, hidden dimension m 100, activation function slope 7 0, number of training samples N = 1, 000, loss function {()) = s, training epochs in standard training Ty = 1, 000 and in perturbation learning
T, = 1, 000, perturbation size = vd x 0.001 = 0.01, and learning rates in standard training Mf = 1 or 0.1 and in perturbation learning fl = 1 or 0.1. However, for the comparison of T'y (i.e., the graph in the fourth row and the first column in Fig. A4), we set f, only to 0.1. For the comparison of d (i.c., the graph in the first row in Fig. A4), we employed = vd 0.0012. In Fig. A13, we used d 100, = 100, 7 = 0, N 1, 000, {(s) = s, T3 = 100, T. 100, /d x 0.001 = 0.01, ff = 1, and 77- = 1.
Mcan-Shifted Gaussian and Scenario (b). A common experimental setting for the mean-shifted Gaussian dataset and Scenario (b) in Figs. A5 and A12 is as follows: d = 5, 000, m 100, y
N = 10, 000, {(s) s. T, = 1, .00,0. Tg = 1, 000, e = vd x 0.01 0.7, ny = 1 or 0.1, and My = 1 or 0.1. However, for the comparison of T (i.c.. the graph in the fourth row and the first column in Fig. A5), we set 1y only to 0.01. In addition, for the comparison of Ty (i.c., the graph in the fourth row and the second column in Fig. A5), we set My only to 0.01. Furthermore, we set my = 10, 5, 1, 0.1, 0.01 and 7/ = 10. 5, 1, 0.1, 0.01 for the evaluation with the logistic loss (i.e., the graph in the first row and the second column in Fig. A5). For the comparison of d (i.e., the graph in the first row in Fig. A5), we employed = v dd x 0.01². In Fig. A13, we used d = 100, m = 100, = 0, N = 5, 000, E(s) = s, T3 = 100, T3 = 100, = Vd x 0. = 0.1, ff = 1, and f/g = 1.
Zero-Mean Gaussian and Scenario (a). A common experimental setting for the zero-mean Gaussian dataset and Scenario (a) in Figs. A6 and A12 is as follows: d = 10, 000, m = 100, = O. N = 10, 000, {(s) = s, T = 1, 000, Tg = 1, 000, e = vd x 0.001 = 0.1, ny = 1 or 0.1, and Mg = 1 0.1. However, for the comparison of T'y (i.c., the graph in the fourth row and the first column in Fig. A6), we set 17 only to 0.1. For the comparison of d (i.e., the graph in the first row in Fig. A6), we employed e = vd x 0.001 In Fig. A13, we used d' = 1, 000, m = 1, 000, 7 0. N = 2, 000, {(s) = s, Tý = 1, 000, T3 = 1, 1,000, e = vd x 0.001 = 0.031, nT = 1, and nn = 1. Zero-Mean Gaussian and Scenario (b). A common experimental setting for the zero-mean Gaussian
dataset and Scenario (b) in Figs. A7 and A12 is as follows: d = 10, 000, m = 100, 7 = 0. N = 10, 000, {(s) = s, T, = 1, 000, T, = 1,000, e = vd x 0.12 = 10, ny = 1 or 0.1, and n2 = 1 or 0.1. However, for the comparison of Ty (i.c., the graph in the fourth row and the first column in Fig. A7), we set f7 only to 0.1. In addition, for the comparison of T, (i.c., the graph in the fourth row and the second column in Fig. A7), we set Mg only to 0.1. For the comparison of d (i.e., the graph in the first row Fig. A7), we employed e = vd x 0.12, In Fig. A13, we used 1, 000, m = 000.
15

---

0, N 10, 100, ((s) s, s, = 000, T3 = 100, c vd 0.01 = 0.31, 0.1, and fg 0.1.
MNIST and Scenario (a). A common experimental setting for MNIST and Scenario (a) in Figs. A8
and A12 is as follows: m = 100, 7 = 0, {(s) s, 7 100, Tg = 100, < = v784 x 0.01 /2 = 0.14, f/ 0.01 0.001, and 7y 0.01 0.001. In Fig. A13, used
1, 000, 7
{(s) s, = 100, T3 100, v784 0.01 /2 0.14, f/ 0.01, and 7/ 0.01.
MNIST and Scenario (b). A common experimental setting for MNIST and Scenario (b) in Figs. A9 and A12 is as follows: m = 100, 7 = 0, {(s) s, T = 100, Tg = 100, < < v784 0.01 /2 = 0.01 or 0.001, and 7, 0.01 or 0.001. In Fig. A13, used 0.14, f/ =
1, 000, 7
000, T, 1, 1,000.
v784 0.01 /2 0.14, f] 0.01, and 7/ 0.01.
Fashion-MNIST and Scenario (a). common experimental setting for Fashion-MNIST and 100, y 0, {(s) 5, Ty 100, Tg 100, 0.14, 7s 0.01 or 0.001, and f/ 0.01 or 0.001. In Fig. A13, we used
Scenario (a) in Figs. A10 and A12 is as follows:
v/88 x 0.012/2
m 1, 000, 7 = 0, ((s) = 8, T3 = 100, T = 100, 7784 x 0.01 /2 = 0.14, V, = 0.01, and
Mg 0.01.
Fashion-MNIST and Scenario (b). common experimental setting for Fashion-MNIST and Scenario (b) in Figs. All and A12 is as follows: m = 100, = 0, {(s) 8, Ty 100. T. = 100,
v/84 x 0.012/3 /2 0.14, f} 0.01 or 0.001, and f/ 0.01 or 0.001. In Fig. A13, used
m 1, 000, 7 0, {(s) T 100, T 100, /784 0.1 1.4, ny 0.001, and
Mg = 0.001.
C
Lemmas
In this section, we derive fundamental properties of random variables.
Lemma C.1 (Properties of Gaussian random variables). Let a² be positive constant. Let Xi,..., Xm E IR be m E N ii.d. Gaussian random variables that follow (0, o2).
(a) For < < 1, with probability at least 1 - 6,
max Xil 20 (2mm/8))
(A24)
(b) Let YI...., Yn E [72,1] be m independent random variables with 0 I 9² < 1. Suppose
that Y1, 11 1 Yn m are independent of X1...., Xm- For 0 < 6 < 1, with probability at least
1 8,
Σ XPY. o² Σ E|Y] < max 160 In (2)
128mo In (2)
(
(A25)
(c) For exp( eexp(=((n))))) 2(nmmmmm 1)2mmm) < with probability at least m/m (m instances such that
6, there are most
2
TO² In
nV m/m +
In
X
<
1
(A26)
2
m
2m
Proof. Let be a positive constant. (a) From [36].
C2
P/max [Xal 2 C7
2m exp
(A27)
2
Thus,
P max Xil > /20² In (2(2m/
(A28)
16

---

1.00
1.00
0.75
0.75
Standard
Perturbation
0.50
0.50
Agreement
10
20
30
40
50
60
70
80
90
100
10
15
20
25
30
35
40
45
50
Input dimension d
Input dimension d (logistic)
Accuracy (bluc and orange) Agreement (green)
1.00
1.00
0.75
0.75
0.50
0.50
0.000
0.002
0.004
0.006
0.008
0.010
10
10
10a
10
Perturbation size
Hidden dimension
1.00
1.00
0.75
0.75
0.50
0.50
0.00
0.25
0.50
0.75
0.99
10a
10a Sample size N
10
10
Slope y
1.00
1.00
0.75
0.75
0.50
5
9
10
10
10a Perturbation training time T.
10a
Standard training time T'y
Figure A4: Accuracy and agreement ratio on the mean-shifted Gaussian in Scenario (a). The blue lines represent the accuracy of the classifier f on 'D = {(xr yn)) ] i.e., training accuracy. The orange lines represent the accuracy of the classifier g on D. The green lines represent the prediction agreement between f and g the test dataset.
(b) For any i [m].
00
(X?YY, YY)
exp -
=E
(A29)
n!
(A30)
('EY + EX
<1 +
(A31)
nd!
n=
By Jensen's inequality,
(X?Y, + +
2n-
[E
+ -X
(A32)
n!
n
B=2
n=2
17

---

1.00
1.00
Standard
0.75
0.75
Perturbation bation
Agroement
0.50
0.50
10a
10
10a
10a
10
10a
Input dimension d
Input dimension d (logistic)
Accuracy (bluc and orange) Agreement (green)
1.00
1.00
0.75
0.75
0.50
0.50
0.0
0.1
0.4
0.5
10"
10
10
10
Perturbation size
Hidden dimension
1.00
1.00
0.75
0.75
0.50
0.50
0.00
0.25
0.50
0.75
10a
10a
10
10
Slope 7
Sample size N
1.00
1.00
0.75
0.75
0.50
0.50
5
8
9
10
10a Perturbation training time T3
10a
Standard training time Tf
Figure A5: Accuracy and agreement ratio on the mean mean-shinee shifted Gaussian in Scenario (b). The description is the same as Fig. A4.
(A33)
n!!
Since E[X?"] = 22n 1)1! < 2n 2n no! and E[Y,1] 1
2 YY?"
8
16t
1+ Σ
(A34)
n!
4to2
n=2
For |4| < 1/(80²),
16t 4
1+ 4lo2 < 1 12122 <exp(3212
(A35)
Thus, X²Y, follows SE(6404 802), where SE(a, b) is a sub-exponential random variable with parameters a, b > O. Note that random variable is called sub-exponential with parameters a, b > SE b), if its moment generating function satisfies
tta
Elexp(t(Z-- - -|Z)) < exp
(A36)
2
18

---

1.00
1.00
0.75
0.75
Standard
Perturbation
0.50
0.50
Ag Agreement
10a
10
10
10a
10
104
Input dimension d
Input dimension df (logistic)
Agreement (green)
1.00
1.00
30
3000000
0.75
0.75
0.50
0.50
0.00
0.04
0.08
10"
10
10
10
Accuracy (bluc and orange)
Perturbation size
Hidden dimension
1.00
1.00
X-XXX X- X0300X
30
0.75
0.75
0.50
0.50
0.00
0.25
0.50
0.75
10a
10a
10
10
Slope 7
Sample size N
1.00
1.00
0.75
0.75
0.50
0.50
10"
10a
10a
10
10a Perturbation training time T
10a
Standard training time Ty
Figure A6: Accuracy and agreement ratio on the gero-mean Gaussian in Scenario (a). The description is the same as Fig. A4.
By [16), Σ." XPY, follows SF(64mo 80²). In addition, by [16), Z SF b) satisfies
C1 < 2 exp (-2 min
C C (
)
PIlZ E
(A37)
Therefore, with probability at least 5,
2 8
Z B|
max 26 In
2a In
(A38)
(c) Let & [m - 1] Bernoulli distribution with p E (0, (k: + 1)/m). By Hoeffding's inequality,
be positive integer. Let Bi(m, p) be the Binomial distribution and Be(p) be the
Σ 1+11
m (
p'(
m- =P Bi(m Y 2 k +1
(A39)
m
P Pu..... Be(p)
2m
Σ 1
(A40)
19

---

1.00
1.00
0.75
0.75
Standard
x
Perturbation
k-ww
0.50
0.50
Agreement
10a
10
10
10a
10
104
Input dimension d
Input dimension d (logistic)
Agreement (green)
1.00
1.00
X
N 2x00000 XXXXX
0.75
0.75
0.50
0.50
4
8
10"
10a
10
10
Accuracy (bluc and orange)
Perturbation size
Hidden dimension
1.00
1.00
0.75
0.75
0.50
0.50
0.00
0.25
0.50
0.75
10
10a
10 Sample size N
10
Slope 7
1.00
1.00
XXXXXX
0.75
0.75
0.50
0.50
10"
10a
10a
10
10a
10a
Standard training time TỤ
Perturbation training time Tg
Figure A7: Accuracy and agreement ratio on the zero-meat Gaussian Scenario (b). The description is the same as Fig. A4.
2(k + mp)?
S exp
(A41)
k +
= exp
-2m
(A42)
Now,
P there are at least le + instances such that [X|] < C
Σ
m
m
P
CT 2 mm
(A43)
k +++1.
< <
< exp
-2m
- -
(A44)
For 8 > exp(
2(k+1) m
and P
C7
In 5
m
P there at least k + instances such that [X,| < C < 8.
(A45)
20

---

1.00
1.00
0.75
0.75
Standard
Perturbation
Accuracy (bluc and orange) Agreement (green)
0.50
0.50
Agreement
0.028
0.056
0.084
0.112
0.140
0.028
0.056
0.084
0.112
0.140
Perturbation size
Perturbation size (logistic)
1.00
1.00
0.75
0.75
0.50
0.50
10
102
10a
0.00
0.25
0.50
0.75
0.99
Hidden dimension
Slope
1.00
1.00
0.75
0.75
0.50
0.50
xX
10
10a
102
10
20
60 70
100
Standard training time T
Perturbation training time T,
Figure A8: Accuracy and agreement ratio on MNIST in Scenario (a). The description is the as Fig. A4.
Since the areas of square with sides of length r and quarter- circle with radius of 2x / are the same, and because 5² t² is always larger in the square than in the quarter-circle outside the common area, an upper bound of erf(x) can be computed as
crf(x)²
exp( exp(-(s² +1)) ds dt
(A46)
π
4
22/VT
rexp(-r²) d0 dr
(A47)
π
- x =1 exp
(A48)
Thus,
C
(
2C
P|X
< C]
erf
1
exp
(A49)
22
Therefore.
2
k +
In
k+1
In 8
O
In
-
PI
<
Cl
(A50)
2
2m
m
2m
Lemma C.2 (Hoeffding's inequality). Let $1..... SN RR. be real numbers and X1....,X, E {=1} be i..d random variables. Suppose that E[X, for every n E [N]. Then, for 0 < 8 < 1.
X,
21

---

1.00
1.00
0.75
0.75
Standard
Perturbation
Accuracy (bluc and orange) Agreement (green)
0.50
0.50
Agreement
0.000
0.028
0.056
0.084
0.112
0.140
0.00
0.28
0.56
0.84
1.12
1.40
Perturbation size
Perturbation size (logistic)
1.00
1.00
0.75
0.75
0.50
0.50
10a
102
10
0.00
0.25
0.50
0.75
0.99
Hidden dimension
Slope Y
1.00
1.00
0.75
0.75
0.50
0.50
10
10a
102
10
10a
10a
Standard training time T
Perturbation training time Ty
Figure A9: Accuracy and agreement ratio on MNIST in Scenario (b). The description is the same as Fig. A4.
with probability at least - 6,
2
Σ
SnX
X
2ln
$2
(A51)
Proof. By Hoeffding's inequality, the claim is established.
Lemma C.3 (Expectation of product of derivatives of activation functions, part 1). Denote a symmetric positive definite matrix by
a 6
Σ
(A52)
where a, C > 0 and ac 12 > Then,
(0(z1)0'(a)) (x2)
(1 + 7)²
Σ x dr
2x Σ
exp
-
2
(1 + (1+>) 7)
12
1
(A53)
2 ac 12
Proof. The inverse of Σ is
E-1
c
(A54)
ac 1
-h
ac 12
22

---

1.00
1.00
0.75
0.75
Standard
Perturbation
Accuracy (bluc and orange) Agreement (green)
0.50
0.50
Agreement
0.000
0.028
0.056
0.084
0.112
0.140
0.000
0.028
0.056
0.084
0.112
0.140
Perturbation size
Perturbation size (logistic)
1.00
1.00
0.75
0.75
0.50
0.50
10
102
10a
0.00
0.25
0.50
0.75
0.99
Hidden dimension
Slope
1.00
1.00
0.75
0.75
0.50
0.50
10
10t
102
10
20
60
70
100
Standard training time T
Perturbation training time T,
Figure A10: Accuracy and agreement ratio Fashion-MNIST in Scenario (a). The description is the same as Fig. A4.
Using y ar/vacc b2, the quadratic form can be represented
x -
x Σ
x
x y.
y T
(A55)
ac
b
Because |0x/Oyl ac- 12
(1
(x'(2))
exp
-
1
x
dx
000
Σ
Vac- B
8 ('())) exp
- T5-1gg
dy
(A56)
2π
-00
With 2 = by2/c,
by2
2
+ a b2
62
y
T = C 1/1
v c2 +
y
(A57)
Now,
1 T -ク
0 (12))
E y yyy dy
-1 d'(12) ( 8'(z d'(z+byz/ byz/c) exp
- =
dz
exp
ac 62
2c 1ž
du
(A58)
The integral along can be computed as
d'(=+byz/0) + L
exp ( c
x22))
dz
23

---

1.00
1.00
0.75
0.75
Standard
Perturbation
Accuracy (bluc and orange) Agreement (green)
0.50
0.50
Agreement
0.000
0.028
0.056
0.084
0.112
0.140
0.00
0.28
0.56
0.84
1.12
1.40
Perturbation size
Perturbation size (logistic)
1.00
1.00
0.75
0.75
0.50
0.50
10a
10a
10
0.00
0.25
0.50 Slope Y
0.75
0.99
Hidden dimension
1.00
1.00
0.75
0.75
0.50
0.50
10
10a
102
30
40
50
80
90
Standard training time T
Perturbation training time Tμ
Figure All: Accuracy and agreement ratio on Fashion-MNIST in Scenario (b). The description is the same as Fig. A4.
- expl
(xp(-
(-=²)
byz/c
(
C 22)
dz
+
exp
-
dz
(A.59)
bysic
2
2
1r exp
C 2
dz ( byz/c
exp
[ 2
C 2
dz
0 + 7
_222 dz -7 {
exp
exp
2
dz
(A60)
-bys/c
=2 dz (1 (1-?) ( -bus/c
( --2
=(1 (1+
exp
exp
2²²
dz
(A61)
bys/c
π =(1+7)
C 2
+ (1 7)
exp
dz.
(A62)
2c
2
Using the above equation,
8
1 Σ 1-1
I' (w))))(
dy
2
-(1 + VV
π
6'(z)cxp
ac 6²
v
dgy2
2c
2c
bozlc
b2
+(1 7))
6((2) Jo
expl
2
dz exp
1/2
dyz
(A63)
2
2c
T(1 + 3)
00
byz/c
C 2
ac
12
+ (1 + (1 7)
exp
dz
exp
y
dyz
(A64)
2/cc 12
0
2c
24

---

1.0
1.0
Standard training accuracy (blue) / Cosine similarity (orange)
0.5
0.5
Standard training accuracy
Cosine similarity
0.0
0.0
x
10
20
30
40
50
60
70
80
90
100
1
4
9
Input dimension d (shifted Gauss)
Std. training time Ty (shifted Gauss)
1.0
X
X- XXxxxXXXXXXXXX
1.0
888888880000
+ +
0.5
0.5
0.0
0.0
10a
10a Input dimension d (Gauss)
10
10
10
10a
Std. training time Ty (Gauss)
1.0
1.0
x + +4++
0.5
0.5
0.0
0.0
10a
10a Std. training time Ty (MNIST)
10a
10
10t
10a
Std. training time Ty (FMNIST)
Figure A12: Standard training accuracy and cosine similarity. The blue lines represent the accuracy of the classifier f on D = { yn ) J i.e., training accuracy. The orange lines represent the average cosine similarity between the experimentally calculated adversarial perturbations and the theoretically predicted ones.
Thus.
('1)) (x2)
1 dr
exp
--# Σー1
x
/ ΣΣ
(1 7)
4
(1 + (1 - 7) Vac - 62
1
0
punt
exp (opp--x0) dzexp
(- ac b²
dyz
(A65)
2T
Using t:= s
byz/c
2 [-22] dz sgn(b)
exp
J
exp ( dt
(A66)
c
122
sgn(b)
1 erfc
(V 2c
(A67)
2c
From [8], with a (et(2
122 1/
1/2
a exp
S erfc
V 22202
(A68)
1 buzlc
(-
_b2
122 (--²²)
exp
<
a exp
(A69)
2
2c
25

---

Shifted Gauss (a.
Shifted Gauss (b)
Gauss (a)
Gauss (b)
0.
00
-5-
-25
-25-
MNIST (a)
MNIST (b)
FMNIST (a)
FMNIST (b)
7.
733
2.5
2.5
0-
(z)( sgn (gn(g(z) (z())
f(2)
Positive samples
sgn(f(=)) (gn(g(z))
0(2) =0 Negative samples
Figure A13: Prediction matching between the classifiers from standard training and perturbation learning, and g. The two axes the normalized average vectors of samples from the positive and negative classes, respectively. The blue circles and orange crosses correspond to the projections of positive and negative samples onto these axes. The gray and green predictions are consistent and inconsistent, respectively. The red solid lines represent f(z) ) 0. The black dashed lines represent Ga (z) = 0 in Scenario (a) and (z) 0 in Scenario (b).
indicate regions where two
Thus,
byzlc
exp
x-
de
exp
ac
6²
y2
dyz
2c
exp
ac
122
12
dyy
x
exp
ac +
V/
du2
(A70)
2c
2c
2c
2
2Tc
(A71)
2c
2
1/2
2
+
62
π
a
(A72)
2
8
Vac + bz
Finally,
6'(x1)0'(2)
1 T
(1 + 7)2
2x 2
exp
2
Σー
dr
000
(1+ - 7) ac
B
π
a
(A73)
2T
2
Vac
12
Vac B2
(1+7)(1 - -7)
ac 122
a
(A74)
4 ac + 82
26

---

Lemma C.4 (Expectation of product of derivatives of activation functions, part 2). For any 21 F
#2 E Rdd
(221, x2) (1 + 7)²
1 (1 (++)(1-77) )(21,
(A75)
4
Proof. By the reproductive property of Gaussian distributions, (v, 21) + follows. (0, || /11//d+1). Since any linear combination of (v, 21) + and (w, 22) + has a univariate Gaussian distribution, (v, 21) a and 22) + follow a multivariate Gaussian distribution. The covariance matrix Σ can be computed as
| /2 (2), 22)
(21, z2)
Σ
(A76)
| /dd+1
Thus, by Lemma C.3, the claim is established.
D Main Proof
For notational simplicity, we use the following abbreviation for E [m]] and n E [N]]
(z) (t), (t),,
(z) := (w (t), x) b;(1),
(A77)
(z),,()) ==)(h),((z))
(z))((2) (
(A78)
(=)(=) =0
(z) = (hy, (z));
(A79)
ffmm = (nn Ov (t))),
ynd
- gnnt = Un adv g(arnty tw (1))),
(A80)
mms= = [ (-vnn (an θv . (f))),
" gmmtt = =- ady glanai Ow (())),
(A81)
1 (t(t) :- N Σ fm,,
(t()) 1
C g.n.t.
(A82)
Moreover, denote the subset of [m]] consisting of the smallest n E [m 1] elements in terms of [=)], by Sz)).. Similarly, we define (z) based on (M...0(2) The function (z,((z) returns one if i E (=) and zero otherwise. Similarly, we define (g.a(z). For exp(-2(n))) / + 1)2 /m)m < 5 < 1, let
2
Czhr(z,)) 6) = -T |=|| + +11 In 1
7 m
In
6(1)
(A83)
m
2m
D.1 Assumptions Properties of Neural Networks and Their Justifications For reference, we state the following assumption on the network f:
Assumption D.1 (Properties of neural network f). Let Rd be real-valued vector and -m)mm/++1)mmmm d < 1 be a positive value.
exp
(a) For any i [m] and j [d], Iv., (0) / (2/d) In (2dmm//))
(b) For any i E [m]. |os| < (22m) (2mm/8).
(c) For any E [m]] [(,
(2/d) 0n(2m/0) |
(d) For any E [m]] ((,,,,(())) < / 0))
(e) [f 0)l < /2(l=////44+]]]m((///)
(f) For any j [d].
m
2 m
Σ
an (0,))
In
Σ
V Wrnolon))uu.
(A84)
m
27

---

2 In
and (o)))(()) x)
<
w 1 11,0 (z,))(( 2)².
(A85)
(h)
16
2
Σ (0 (2 2)
In
(A86)
m
8
(i) There are at most 7 m instances such that [hg,),(z2] < Cehr 01/v2
Assumption D.1 is justified follows:
Lemma D.2 (Justification of Assumption D.I).
(a) With probability at least 1 8. Assumption (al(a) holds.
(b) With probability at least 1 8. Assumption D.1(b) holds.
(c) With probability at least 8, Assumption D. (c) holds.
(d) With probability at least 5, Assumption D. ((d holds.
(e) With probability at least 1 8, Assumption (e) holds.
(f) With probability at least 1 8. Assumption D. D.f(f) holds.
(g) With probability at least 1 8. Assumption D. [(g) holds.
(h) With probability at least 1 Assumption D. (h) holds.
With probability at least 8, Assumption D. (i) holds.
(i) With probability at least 96, Assumption D. holds.
Proof.
(a), (b) and (h) See Lemma C.I.
(c) to (g) and (i) By the reproductive property of Gaussian random variables, (0, 2). hz,,o(z), f(z; 0), Σx agt% (0,,), and Σ; m agall f.,00 (Z,)) (=,, (w:(()))) follow the Gaussian
N(0, /d), (0, 2 + WO,, ||2l2/d + 1), (/ (1/m) Σn (2,,)
and ((0,, L//) V0,00 (e, 2)²). respectively. By Lemma C. the claim is established.
(j) By Bonferroni's inequality, the claim is established.
Similarly, consider the following assumption on the network and its justification:
Assumption D.3 (Properties of neural network g). Let Rd be real-valued vector and exp (-2(1 1)²/m) d < 1 be a positive value.
(a) For any i [m] and (w,, < (2/d) In(2dm/8),
(b) For any i E [m]] |3,| < (2/m) (22mm)
(c) For any i E [m]] [w,; =) < (n z|1.
(d) For any E =22l: (2m//5))
(e) [g(2; 0)l /2(l==///d++1]lm(2//
(f) For any j [d].
Σ
m
Biri 1.0.00000 (2 )w),
In
2
2
20,500 (xnd) Pur (0)2. (A87)
m
28

---

g
2
>
Bo G. 9,2.0
(00, x)
<
In
2
2,1,0
(20, (0), 2)2.
(A88)
(h)
Σ Vas,0 ) (1x
Tb (a:adtv 2)
<
16 2
In
(A89)
vm
8
(i) There are at most 7ym instances such that [2),)0(z)] < Cthr 8)/v2.
Lemma D.4 (Justification of Assumption D.3). holds.
With probability at least - 96, Assumption D.3
D.2 Wide Width Assumptions
Then, consider the condition of network width for lazy training.
Assumption D.5 (Wide width for neural network f). Let E Rd be real-valued vector and exp(-2(()/n)) + 1)2 /3)m inequalities:
be positive value. Network width m satisfies the following
4 4ln(2m/0 ( N (1 2)1 1) f,m, dt) = o m
0 ( (0(o(f. efme di) (feeemmed
Senade))
(A90)
N2C (z,
4 4E mi (a Ikyl So Enm dt So Er dt ò dF m
de ("eemma ( dt )
(A91)
N²
Note that only Ineq. some rearrangements of equations. This assumption restricts the transitions of the derivatives of hidden outputs during training.
(A90) is required satisfy lazy training. We impose Ineq. (A91) simplify
Lemma D.6 (Lazy training in network f). If Assumptions D.I and D.5 hold, then 1z))(()) =
f))=)) for any i E [m]] Sy(z) and < t < Ty.
Proof. By Assumption D.I, the time evolution of (z),,(()) from t= = 0o Ty can be computed as
C, (Vv: - Va, Vi,,(Ov,a())DD))
Ah A
(A92)
04
Un E V 2) + +1)++000 dt
(A93)
N
(Diny 2) + +11 ( Enmade dt
(A94)
N
2
2m
f Eyme dt.
In
(xnn 2) +11
(A95)
m
By Assumption D.1, if the right term of Ineq. (A95) is smaller than Cir 82,5)/2 then the largest m 7ymm instances in terms of [=))),(z)] satisfy sgn (gn(h),,((2)) = sgn(h),ao(z)) for 0 S $ T
This condition can be represented as Ineq. (A90).
29

---

The same discussion can be applied to the network
Assumption D.7 (Wide width for neural network g). Let E R be real-valued vector and exp(-2(n))) + /)///mmm))))mmmm)m)))) < be positive value. Network width m satisfies the following inequalities:
4 (m(22m0)) En (1aa .2) 1) 10 e.m. dt)²
δ 0 dz
To an )
(A96)
N2
m 2mn (anddy (ellla So" ey g.n, dt fo & g.k.t
dt δ d
(ce(f Come Cameet) )
2
(A97)
N2
Lemma D.8 (Lazy training in network g). If Assumptions D.3 and D.7 hold, then (z))((z) oy (=) for any [m] \ (z) and S g
can integrate Assumptions D. and D.3 into Assumption 3.2.
D.3 Main Part
Lemma D.9 (Representation of network f). If Assumptions D.I and D.5 hold, then the network output at the training time T can be represented as
m
f(z;Ty) =((;00 +
Σ
Ja.,y (2) axk
N
yra (( 2) + 1) 1/" Ty
Ena dt [oVersooonWWsolee 2(xn, x)
+
N
Un (2 ((2 2) + 1) foa Ts
Σ
N
m Σ Un ((2n) 2) 1) Σ (z
T1
x
- Wr dt.
(A98)
Proof. First, see Lemma D.6. The time evolution of vt( from t = to t = Ty can be computed as
T, V (tvv))))))
(T;(T)) =
dt
(A99)
Ti
Σ Anl //seen )an dt
(A100)
N
Un (TH) CmmaWhaar de
06
(A101)
N
N
(1 (.5((1,,)) Bn In (l 1"r Crmn
0
0
N
(zg,s(nn)ue (nnntnn)nnnnnnnnn) 1"1 (imee/aaaann) dt
(A102)
N
n
30

---

N
Un /.,0(( 10" Ennade
a:
Σ
N
N
a
Σ
( Wn
N
N
)nnnn 9' (nneWreelan) di
04
+
(A103)
N
N
(2) En
0%
Un 1/ 1,10 (In)
dt
N
N
[-" ()mell)sssann) ((ol(z)) dt.
0
Kf, (z)((nn)un Unn yn
(A104)
Similarly, the time evolution of (1) from 0 = Ty can computed as
Vn 1-'
(T,
Cnmeeha dt
(A105)
N
("1 In
Un (nolnn))))))
N
(ss(an))nn 1-" (mmelW)aeeee) - (ls)o(an))
(A106)
Thus.
AhyAr, (z)
N
yn (x 2) + f"d (mmeWtaraaa) dt
03
(A107)
N
N
yn ((xn, x) + 1)00/ 1-" "r dt
N
( ((m 2) 11 S-" (mmellsseaan )(x,l((n)) de.
(A108)
N
The original network at the training time Ty can be computed as
[<;TT)) = Σ aCpaaT,
(A109)
Σ
+ Σ Cawaar (z)Ahf.r,
(A110)
The first term of Eq. (A110) can be rearranged as
Σ m
anb a (z))).0(=))
- 0001--kn1)))//..o22)h..... > m
(A111)
=f(2; 0) +
Σ (o 2)
(A112)
31

---

The second term of Eq. (A110) can be rearranged as
0n J.I., (z)AN
Σ a1 Ki (, + oa (aw
(x)))
(A113)
Σ /,00)s,()) ,,, (z) + Σ [= (z) - - (A114)
The first term of Eq. (A114) can be rearranged
Σ
Σ ynl( 2) 1)0) 1/r Ts
En dt
N
(z,:(an))n ((nr 2) +1) L/" (mmelWssseaaa ()aolom)
+
04
Σ
(A115)
N
1
Σ
N
In (( 2) + 10¹ Th
m
N
N
+
yro (I z) +
N
m
Σ
of (mn
(A116)
The first term of Eq. (A116) can be rearranged
1
Yn (a 2) 1) (" "nm dt
Σ at (o
(A117)
N
1
Σ Un Un((xn 2) +1] (") eymee dt Σ
m
at afVtxoltn)) (().
(A118)
N
N
1"d dt
+
Σ
Un (xn, (Zn, +)
(A119)
N
The second term of Eq. (A114) can be rearranged
( (z) (1),o(z))A/...r))
m
Σ
v()),((z))
N
In ( ((In, 2) +1) f: "ImaWrraaann dt
x
a
Σ
(A120)
N
n
N
Σ
Un ((xn, (()n,2) 2) + 11
N
m
o (2) ()xo(z)) 1" (mnib/aaa dt.
(A121)
32

---

The sum of the second term of Eq. (A116) and Eq. (A121) can be rearranged
N
akk I."' (meel(sseaan) (t)))())))
Un (2 2) + _
N
1
N
m
a - )/)xo(z)) J/² (e dt
In ((0 2)
N
m
yn (a 2) + Σ (f
N
7
(oaal () dt.
(A1 (212))
Lemma D.10 (Upper bounds of terms in Lemma D.9). Assume Assumptions D.I and D.5.
(a)
m
auk 5 ( (z) -/)))//)))))) Σ
2mm11 /122mm000111/////++1111 0(1)
(A123)
(b)
1 N
ynl (2 2) 2)+ + +1] 1-'
Σ
Lyn dt Σ af Eai - +(xx 2)
N
8Cthr 8) ln(200) Ō(1).
(A124)
1n((2m 2m/
(c)
m
In (2 2) +1) Σ agnz((Zn))
S'd Ti
<n(1 (2 = Ö(1)
(A125)
Proof.
(a) By Assumption D.I,
m
m
a (, (z) (1xx(()))))a((2
<(1 5(1-7) 7) Σ (
(A126)
2nn
(A127)
(b) By Assumption D.I,
N yn ((xns 2) + 1"1 Em EoiVinooewwnnole - (b(xn 2)
N
Σ
n
16
22
(Wn, z) +11 1" dl Σ
N
In
(A128)
N mm
33

---

By Assumption D.5,
16
2
(an 2) + 11 So (
In
E En dt
N Wym m
8
NC (C
2 2v
In 2mm00m
Σx (1 z)1 So" Lnn dt
16
N
Kons 2) + +11 1/" Efa dt
x
In
(A129)
N
She z, 8) (2/66
(A130)
Vln(2m/0
(c) By Assumption D.I,
Σ (p 1-" Th
- ((20(==))/x0033))
5(1 (1- (/) 21
m Ey di Σ (F
(A131)
2m(1 - -22)
(2m)
T1
In
(A132)
Vm
By Assumption D.5,
2my(1 72) N Nym
2m Σ
(x 2)+ + 111 L'" enn dt
In
N (2,
N
2/ In 1n(2mm/ Σn (1<xe z)1
+ 1) So Eyme dt
211(1 72)
2m In
N
( 2) + 1/ T3
x
Emn dt
(A133)
N
8
1n(1 Cthe (2n2 (2m//8))
(A134)
Lemma D.11 (Network prediction of f). Assume Assumptions D. and D.5. If
1 N
Σ Yn (I 2) (Z 1-/ Cra dt 20(1+ f"r
1+
Tt
(A135)
then
yn (xx, x) 2)) 1- efmedt) Σ
N
sgn(f(>;TT) = sggn
(A136)
N
Proof. By Assumption D.1 and Lemmas D.9 and D.10, if
yn (xn, (2 x) 10 Cimeet dt Σ N
N
n
m
2 215(200) +
Σ
aan (on ())s0()))(ss0(3)
34

---

N
In ( ( 2) + 10" em dt
(
2(En)) 2)
N
Bn (n(( 2) + +1) Σ a (f(3))(()))
N
Ty
(2) Vr2solenV dt
x
N
Un (2 Lo¹ El
(A137)
N
Ts
0
1 +
(A138)
then
sgn(f(z:Ty)) sgn
E
Un (( 20 2)
(A139)
N
Lemma D.12 (Adversarial perturbation). If Assumptions D.I and D.5 hold, then the adversarial perturbation defined as Eq. (1) can be represented as
Σ F ( (TT))
Tn = cyn
adv
and
(A140)
1 m an (1, v. (Ty))l
a J&T, (In)v:(TT)
Σ a (2,)),) + Σ
(xn) - (2
1
m Σ y (") Eraadt dt DaiVinooonn - 1(xx, xxs)
N
Σ Yi (Bn 2: ) 1'H Cr
+
N
N
Σ
y Σ
N
(A141)
Proof. The main term of the adversarial perturbation can be computed as
l F.n.Ty
Vadv El f.n.T
Va. f(x Oy a (Ty)) V a. f Ov (Ty)) 11
(A142)
En an F.,,T, (In) )o, (Ty)
adv
(A143)
1E ag 13, (x )u, (Ty)
The leading term can be rearranged as
m
m
m Σ
Σ (wn)) = Σ
av aoyyA (x,) (0))
a a. (1,)))))))), Ax,))
(A144)
35

---

The first term of Eq. (A144) can be rearranged as
m
- (,00 v( + Σ anii ( (an) - (xs)((a))))(0)))
(A145)
The second term of Eq. (A144) can be rearranged as
m
Σ ,,,, (m.)),
= aue f1,0 (o) +
E a Lann (0)o(())) (A146)
The first term of Eq. (A146) be rearranged
Σ [o
m
N yoowWhsaoos 1-d de
Σ
0g (3.0((nn)))
Of
Σ
N
N
1"h ( - V ()),)(()x))
(2 K3 (T.(ar))ue
(A147)
N
1"1 E,R. dt Caj 02V/ ( ((ll()))
Σ yk.
m W
( f ((sel()reeet))) - -8/xo(ox))d dt. (A148)
The second term of Eq. (A146) can be rearranged as
Σ Ca (ax) w/ss(emn)Ao
Σ yhot 1 Ti
N
ai Σ a (x (Zn) (xx) [xx),
(A149)
N
1"1 (rseVessaaa dr.
yg Σ a (w.) (2mn) Vraolon))
(A150)
The sum of the second term of Eq. (A148) and Eq. (A150) can be rearranged
Σ Lonss,laaW/nnole S"" C. - (6),,((0))) di
Σ
N
Σ yk Σ (a (In) )(ro(Zn)) ("r Comeehaan dt
+
N
m
D Σ (xn
N
fo
T₁
CraalWers (In) () dt.
(A151)
36

---

Lemma D.13 (Upper bound of norm adversarial perturbation). Assume Assumptions D.I and D.5.
(a)
Σ
< <4ln(2dmm00)l((/// O().
(A152)
(b)
m
03 (I (2n) (2.) -0),,(00))))
47 7)² In (2m /6) In(2mm = Ō(1)
(A153)
(c)
1 N
Σ yk !
Ti En dt aa - ( Iix))
<64In 2 (2/8) = Ō(1)
(A154)
(d)
m
Bk Σ aanzs(ZZ))
S0" Ti
(. R,,,, (2n) (r dt
<1 2 (1 - 21- (2 O(1).
(A155)
(e)
Σ a. ( < <0 voval
1" Ts
(A156)
(f) Let
m
m a (2,0 + Σ
r/
any Lam (Tea(=n)));(0))
+
Σ
N
Yk ( C.n.e dt
(attssnoo 2( IKk)
m
N
h
N
1
Σ
EaZknalan)
N
k
f-" Ti
('aal (an)) - (/sole)))//,s0( dt. (A157)
x
Then. ||r/,||| O(1)
Proof.
(a) The given left term can be rearranged as
m
m
Σ
Σ
a asy (((rs((a)))ss())
(A158)
37

---

By Assumption D.1,
Σ aart (adisslonaaas1))
<(2/m) In(2/6) Σ (
(A159)
(4/d) (2(00m/22mm0000mm lm(2/6).
(A160)
(b) The given left term can be rearranged
02ky (z (zn) ()ss((n))))
2
O4k ) ,E3 (an) -
(A161)
<(1 7)²
(A162)
By Assumption D.I,
2 Σ Jaaks (1m))))) < (4n2 (2(2//6) In(2dm/8).
(A163)
(c) By Assumption D.I,
N Σ
Jo
TJ
Cree dt ( oow (xx xik)
Bk
N
256 m. 2n2
2
(1mns auil 1-' Eime f"h de.
Σ n,
(A164)
8
By Assumption D.5,
256
(2
N
KIn, xKحi 1-" Erme dt f"r Cr dt
TT)
In
Σ n.k
N2
N
EN (e 2k) S Enne dt fo yym. dt
<64 l2/5).
(A165)
(d) The given left term can be rearranged
m
(ax)) S."
Σ
CynlVian (2 (an) - (/so(on)))),,000 de
<(1 ?)) Σ (Zmsu(or)) 1"1 dt
m
(A166)
By Assumption D.1,
2n
2m
Σ [2))) <
In
(A167)
/m
8
Thus.
N m
Ck Σ ofke)((ss) S0 Tt
38

---

(1 =
2m
NV
(Ty Ka wail 10" Crandd L-d Crade.
In²
Σ
(A168)
m.N
By Assumption D.5,
4r7
72
2m
N
Ts 1e xbni 1/² Eng dt Sor Er dt
In
m.V²
8
n,k
41/²
72)2
2m
N
xmحi 1"d Enm dt 1o1 Eree dt
In²
N2
8
n.
N22
x
(A169)
4 En,i (2n, xxa)
So
fn dt So Erre, ct
= (1 2)2 In (2m/2mmm)))
(A170)
(e) As 81 +
82 + 83 + 84 + 85|2 1 25 max((1(1))) [|82111 ||.a||l 1|s.1111111 -1s1|211<ss//? for any
81, 82, $3, 84, 85 E R4
4 (2)(22mm))ln(22)))
4n7 - 7/) 1n(mm/8) In(2dm/8),
64 (2/8),
Σ ag YT,,, (In) (
25 max
1 (1 - 722 (2m/88))
(A171)
Uk t nn 26 )ox ("' Gy di
Σ
N
(f) Similarly to (e),
4 In 2dmm0) l2(20)),
4n² 7)² 1n(2m/0 (n(2dm/5)
|| < 16 max
(A172)
64 1m (2/6),
172 - 10 (2m/8)
Lemma D.14 (Upper bounds of inner products with adversarial perturbation). Assume Assump- tions D.1 and D.5.
(a)
m Σ
aa oo0 =2/00/00122///))m2mmmm//1//111/1 Ō
(A173)
(b)
m
Σ
< 2n
(A174)
(c)
Σ (x 2) 1'1 Ti Cy dt
( D( 2xk)
8Cthr
(2,hr(z,,) (z, 8) In(2/0) Ō(1)
(A175)
v In 2m/dm
39

---

(d)
N
yk (ak, z) Σ a5
N
T
".,.el (a, - - dt
<n(1 72 Cthr 6) 1n(2mmmm200 Ö(1)
(A176)
Proof.
(a) By Assumption D.I,
2
2
Σ an (0/
In
d
(.,00( (e,, 2)
(A177)
m
2
2
In
(0)
(A178)
m
(1/d) In (22/0) In (1
(A179)
(b) By Assumption D.1,
m Σ 033 (z (1 (,,,,, (2nn) - -
<(1 7) Σ 0, (2x) 2)
(A180)
<2 - 7) lm(2m/0)) [=]2m/))[[=///3
(A181)
(c) and (d) Similarly Lemma D.10.
Lemma D.15 (Representation of network g). Suppose that Assumptions D.I, D.3, D.5 and D.7. (a) In Scenario (a), i.e., xddv = Tn.
g(z:Tg)
=9(2;0) +
Σ ( (z) (aso(=))))a00(2
1
Σ
adv undv((( ((r,, 22= + +1) 1/" eg lymed dt
+
Un
N
Σ B. V...io((m)) (Fm)) D(
1
N
add (( 2) S Camn
+
N
n
N
+
1
Σ
ym
uadv(rr ((rm; 2) + 11 > 83 (ri((r))
adv
N
n
To
1
by
(z) (eso((r)e dt
40

---

Σ ((r:))) 1/² ann dt
N EI (an)u
Σ ( (v;
Σ
(1mn) - ()solo z)
1
Σ
N
Uk (a0k 2)
10² Cymeedl (
ol ( 32k)
m
N
&
1
N
m
Σ yk (a0k) 2)
Σ afKg,(IIX)
N
1-" TT
C. (2n)) Vy (anku ( de
x
N
क (rn, 2) (- Cnm de > un (x Dx.) mx (o0k, foa epa (A182)
N
Σ
N
n
(b) In Scenario (b), ie., wad = nn + Vmn
g(z;Tg)
=g(2;0) +
Σ BiKi.g (2) g.i.,, (z) ) (2
1
+2)+1) 1) /0 bn dt Σ Vady (fxady 22) +
N
+
N
W.5i,,000 adv (...l(z) (( 2)
1
Σ undy alaaad (z) + 1%1 dt
N
1
m
+
Σ Un ((x
22) + 1) Σ 39 k (uv))))
N
To
x
W (z) Vag
addd (o )x)x((())) de
Σ (anadr 22) ( Camedtt
N 2T (.
Σ and
m
Σ aiKis (Z) (2n)) (/)a((n))(
1
Σ
N
yl (o 2)
1"H
Cr dt Σ
22WWr,:o@nW)W D( xxk)
N
N
1
Mls ( z)
Σ ai (1x)
N
41

---

I
G. (2n) (25))))) (1 dt
1
Σ ((x0 , //² Eg tn
N
Σ yk 2 (Bn, o&)) (10R) 2) So¹ elarde
N
(A183)
Proof. Similarly to Lemma D.9,
m
g(z:T,) =g(=;0) E (z) (z) o0))
N +
1
adv (( .2) +2)+ + 1) 1/² bg dt
Σ
N
7
// (x (..2.0(z) )e0 @(x ,22)
adv (( (xed .2) 1/" bgme dt
+
N
1
Σ
N
adv
((< ,2) f'r gg dt
Un
N
1
Σ Un ((ar 22) + +1) > 07 Ki, (2x2
N
1/²
(or.e W (z) - Vos,l(a ) ()))
(A184)
By Lemma D.12,
1
Σ jarty (2x (onn),,)((r)))) 2) 2) f de dt
N
e Σ. N (( 2) 1o- eg g.n.t di E. and J,,TT (x (on))
(A185)
NI Er oce J,TT, (2n
The numerator can be also rearranged as
N
(ax adv
.z) Ca di
Σ ave (an))
Σ (ax adv .2) de (I
("' To
+
Cii ( ( (mon) -
2)
1
yk ( 2) 1" Cl FatV'noooe EaNWnooteu)ee/so0022))) D(2,,, xb6) Σ
N
N
m
yk (2 2) Σ affE,1(16))
42

---

S-" CEsalWaan (2n)0
dt
Σ aaa ,22) /%8 gnn di Σ y1 (m Ds (o0k
N
N
(A186)
Lemma D.16 (Network prediction of g). Suppose that Assumptions D.I, D.3, D.5 and D.7.
(a) In Scenario (a). if
1
Σ
N
((ra, 2)
Too
N ann dt
Σ yk Dl [n. D& (a /-" Ernnad
N
Vd S f. dl
1
yad o ( 2) 1/0 Eomeatt
>
1
N
1'² Comeet))
(A187)
then
1
Σ (r 1'h ag dt
sgn(g(z:(g)) sgn
N2
( (0 2) 1/¹ ((aode)
x
U/ Da 2
(A (A188)
(b) In Scenario (b). if
N
frr
Io
N Σ
yo (x,, Dx (Iok 2) f¹a & Ennn dt
4 ((x
2)
&e
N2
gnn
72
Va So &.M.e dl
1
madt (z (2) 2) + 11 1'd Come
1+
Σ
N
1
To le
+
(A189)
then
1
T Σ ( 2) 1- bnmed dt
sgn(g(z;TT)) sgn
N2
ye De 2x)) (ark 2) f" (naade)
(A190)
Proof. We prove (a). Similarly, (b) can be established. By Lemmas D.10 and D.13 to D.15, if
(( 2) 1"t Cy dt Σ P( ax) 2) 1" Cyp. dt
N2
Σn oweeyy J.iTy (Ie (amm)u((TT))
m
10(2;0)| 0)|
Σ (
(2) (. (2) ((
43

---

N
adv ((rns 2) + J/ dn
Sk ( s.),0=) 2(rn 2))
N
adv ( 2) 1/² Eomade
N
12
N
1
+
Voa ((r 2) +1 Σ Bi PRrisg(ri
adv
N
To
Ey g. (V ( (z) (ax
Σ p((m)))) 2) J/ T aa {
1
N
m
Σ
(2ng (Zn) Wraole
N
Egnddd (E (ofthnoooe.)W.oooee - o o(xn xxk)
+
Σ
yk (ork 2)
N
k
N
1
+
Uk (Ick z)
Σ 20
N
1-"
TT
Cp (zem) (x2 dt
(A191)
(ova Prue dt)
(011+
1
adv ( 2) 100 Eaaaet)
Σ
yn
N
To +0(f-
(A192)
then
sgn(g(>;; (g))
= sgn
1
Σ
( 2)
N 1"1 byne di
Σ
1"d eraade) ).
(A193)
N2
Theorem D.17 (Perturbation learning, Scenario (a), general case). Consider Scenario (a) in Set- ting 3.1. Let = (11) be a small positive number and
N
S-" Ts
igem (z)
Σ
Ur (x
Jn,
2) x)
ey dt,
(A194)
N
n
(r 2) /- To Co Com di Σ ua (a an ( 2) 1"1 dl.
(A195)
N2
Under Assumption 3.2,for any z E Rdd if
0(1+)
1+ {( Ti
()modt)
jggn (z)1
(A196)
Iggen
(2)l (2)]
44

---

( vaSo" e e,me dt
Σ yddy (( 2) 1 pn dt +
I ggn at dtt.
>Ō
(A197)
e
sgn(fuen (z)) = (gg (2));
(A198)
then, with probability at least 8, (g; = sgn(g(z;Tg)) holds.
Proof. By Bonferroni's inequality and Assumptions D.5 and D.7 and Lemmas D.2, D.4, D.11 and D.16, the claim established.
Theorem D.18 (Perturbation learning, Scenario (b), general case), Consider Scenario (b) in Set- iigg 3.1. Let ò (1) be small positive number and
1
Un ( 2)(en; 2) L/ dn
8gen (z) : N
Σ
(A199)
N
adv ,2) ( en di
N Σ
Dc ax (oxk) Sor de (A200)
96
gon
(2)
Σ
((
N
T2
k
Under Assumption 3.2, for any Rdd if
δ 0(1 1+ (- Emmade)
facm (z)]
(A201)
105mm
(z)
Vd J
Pra. dt
( (1+
yad D( 22) x) +1) f'h To
1+
N
1000 l Egmmett dtt
(A202)
sgn( faee (z)) sgu(0h" (z)), then, with probability least 6, sgn(s(=;;]] sgn(s(2;T,)) holds.
(A203)
Proof. By Bonferroni's inequality and Assumptions D.5 and D.7 and Lemmas D.2, D.4, D.11 and 16, the claim is established.
Theorem (Direction adversarial perturbation). Let 5 = O(1) a small positive number.
Under Assumption 3.2, for any [N], with probability at least 1 8, the adversarial perturbation Tn is parallel to the weighted sum of training samples as follows:
N
yk (I 2 )x 1" e' e'-vaf di En.
Tnll
(6)
N
where en satisfies || (1). particular, for E(s) = 8,
T N
N
Tn ll
Σ yk ( xx) + En-
(7)
Proof. By Bonferroni's inequality and Assumptions D.5 and D.7 and Lemmas D.2, D.4, D.12 and D.13, the claim established.
45

---

Theorem 3,4 (Perturbation learning, Scenario (a), special case of Theorem D.17), Consider Sce- ([{=1]]())))) for every n E [N]. Let (1))
mario (a) in Setting 3.1. Assume {(s) and yn gadv be small positive number and
N (a
N 2
N yk o ( (x) (8)
f(z):= = N ==
2) (xn (z( =
(Tn: n.
N22 n=
k=1
Under Assumption 3.2, for any R.A if
(Functional margin condition 1)
[f(=)1 Ô
1+ T
(9)
Tj + Vd
VN )
(Functional margin condition 2)
[a(2)) > Ô
(10)
T
(Agreement condition)
sgn(f(z)) = sgn (z)),
(11)
then, with probubility least 6, sgn(s(2;Ty)) = sgn(g( z; Tg)) holds.
Proof. By Bonferroni's inequality and Lemma C.2 and Theorem D.17, the claim is established.
Theorem 3.5 (Perturbation learning, Scenario (b), special case of Theorem D.18), Consider Sce-
mario (b) in Setting 3.1. Assume {(s) and yodv ~ (({+1)) every n E [N]. Let O(1) be small positive number and
9o(2) = N2
Σ
(m
adv
Σ k=1
y fan, T.. (x 2).
(14)
Under Assumption 3.2, for any E B.a, if the functional margin condition (Ineq. (9)),
VEN ((2rs 2) + 1)2
vd
(Func. margin cond. 2)
[ob(z)| δ
(15)
T₁ e
Tg
N
(Agreement condition) sgn(f(z)) = sgu (ās (z)),
(16)
then, with probubility least 8, sgn (z;; Ty)) = sgn(g(z; Ty)) holds.
Proof. By Bonferroni's inequality and Lemma C.2 and Theorem D.18, the claim is established.
Lemma D.19 (Sufficient condition of agreement condition). If
ΣN (In, 2) S f, dt max.ee ............. ΣN X(xn, (T 2)1 fo e,me de
1-7
(A204)
7
then freu = sgn( sgn(ifnn holds.
Proof. By Lemma C.4,
N
1
Tr Enm St dt (2(2n) x) (1 7)2
Σ Un (I xx)
4
(1 + (1 - 77)
N
M(x,, 2) 2) 1"h El
Σ
(A205)
4
46

---

In addition,
(1 (1+2)*
Σ (a x) 1/d Ein dt
N
4
72
(1 + 7) 7)
X(xns (eEns z3) So¹ Ty
emelll
(A206)
4
En Un (2 2) So f dt
1 7-7 +
(A207)
Xaxn 2) 2)) 2) 2) fim dt
Thus, Ineq. (A207) holds, then
N
100 2 Simadt) sgn
N vnlaans 2) 1/0 (mmade)
sgn
Σ
Un ( (2 2)
(A208)
n
Similarly, for any [N]. if
En (20 z) So E en
1 1-7
(A209)
Σn N X(Ens Ix (2E 2) So En dt
1 1+
then
N Σ
Un 2 on, xx.) (20,s z) 1-' Eymeet sgn
N
Un (En 2) 1'd eemade)
sgn
Σ
(A210)
n
When Ineq. (A209) holds for every k: E [N].
(T 2) 1/" To ag dt Σ (i) 2) S'" eredde)
N
sgn
B (ar((an (mm mi)( 2) f"d Cpaade)
sgn
(A211)
Bn (ai,, 2) ("' emmedd)
8gn
(A212)
By integrating Incqs. (A207) and (A209), the claim established.
47

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We have accurately described the contributions and limitations in Abstract and Introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are described in Section 3.4.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
48

---

Justification:
The assumption is described in Assumption 3.2 and a brief proof is provided in Section 3.3. The complete proof can be found in Appendix D.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
The experimental setup is described in detail in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
49

---

Answer:
[Yes]
Justification: All datasets we used are either openly accessible or can be artificially generated. The code is provided as supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/pu
blic/ga gugdee/e///// Codeeubmiii oesionnniccyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https: /CodeSubmia // /nipp..ccocc https/cccppbbc///iceeeec/c S ssion ssionPolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental setup described in detail in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Error bars were not measured due to computational costs. However, we provide extensive experimental results to support our theoretical findings in Appendix B.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
50

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our experiments were conducted on an NVIDIA A100.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //te://pee...eeeeeeeeeee http///rrps.cppppllipp/pppppp//t ctt.ppppblcctttiiiiccieeeeeeeee ines?
Answer: [Yes]
Justification: Our paper strictly adheres to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This does not apply as it is theoretical study.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
51

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Our theoretical research does not involve such releases.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have accurately cited credits.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswil thcode. com/ hmm/dataeets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
52

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not provide such assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We did not conduct such experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We did not conduct experiments that require this.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
53


Reviews:
[{"review_id": "xuyQRuO8Sv", "reviewer": "Reviewer_MQtT", "summary": "Perturbation learning, where classifiers are trained on adversarial examples with their associated incorrect labels, results in non-trivial generalization. This work theoretically tackles the perplexing former phenomenon for wide two-layer networks in the kernel regime. The authors first prove that adversarial perturbations are parallel to a meaningful feature vector (that can contain whole dataset information under some additional assumptions) up to an error term. Second, the authors provide some conditions on when the predictions with perturbation learning match those of standard learning.", "questions": "1. Could you discuss again the choice of kernel regime vs. feature learning for your analysis after my comments in the Weaknesses section?\n2. Could you provide references or evidence towards why $\\epsilon$ should scale with $1/\\sqrt{d}$?", "limitations": "I think the authors overclaim by saying, \"We provided a theoretical justification for perturbation learning and the feature hypothesis\" (L293). Their analysis is limited to the kernel regime, which is acknowledged, but its implications for the feature hypothesis are not well explained. In addition, scaling with $\\delta$ in main theorems is not discussed, and as I pointed out, it points to other limitations towards infinite width.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The problem is a very interesting one and lacks more analysis, so this paper addresses a significant problem in an original way.\n\n2. The setting and assumptions are very well described and clear.", "weaknesses": "1. I am overall confused about the choice of kernel regime to explain perturbation learning. As the authors acknowledge, there is no feature learning for the choice of width in this paper (the output of hidden units remains the same). It's not clear how such a framework can explain perturbation learning and, in particular, the \"feature hypothesis,\" which authors claim that they do. Since there is no feature learning in this regime, there should not be any \"feature hypothesis.\" This is not to say the analysis is uninteresting; it applies to perturbation learning with kernels. But this requires a completely different contextualization than the authors provide, one that focuses on the adversarial robustness of kernels rather than neural networks. And for the reasons above, I find the comparison with prior work a bit misleading as they tackle perturbation learning for different scenarios.\n\n2. It is difficult to judge the validity of the assumptions in the paper.\n\n* Assumption 3.2. is very convoluted, and I don't see how one can justify this assumption in finite width settings. I equate this assumption to an infinite-width assumption, which is perfectly reasonable, but as I discussed above, I believe it changes the object of study.\n\n* The assumptions of Theorem 3.3. and Theorem 3.4. are discussed, and some intuitions are provided. But it is not discussed why they would hold for a small $\\delta$.\n\n3. The $\\delta$ dependencies in Theorems 3.3, 3.4, and 3.5 are confusing. Let's focus only on Theorem 3.3. When we take $\\delta \\to 0$ while everything else remains fixed, the statement is trivial. So, the interesting part of the statement is when $T_f$ or $d$ scales with $\\delta$. I believe it is more reasonable to consider $T_f \\to \\infty$. So, this verifies that Assumption 3.2. is an infinite width assumption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's insightful comments. The reviewer seems to highly evaluate our problem and analysis as interesting but also has concerns about the theoretical principle, which results in a low initial score.\n\nRegarding the concerns, the reviewer seems to have several fundamental misunderstandings about the kernel regime. We would like to address this in the rebuttal. \n\nIn short, a) network parameters change during training, b) feature learning occurs in the kernel regime, and c) our claim does not require infinite width, $\\delta \\to 0$, and $T \\to \\infty$. We elaborate on each below.\n\n**Network parameters change during training.**\n\nIf the reviewer considers that the outputs of hidden units remain the same during training as at initialization, this is not correct. In our framework, hidden weights are trained and updated during training. Thus, the outputs of hidden units change from their initialization.\n\n**We employ gradient flow.**\n\nThe reviewer might misunderstand that we employ a kernel method. We use gradient flow. Our training scenario is the same as in prior work [18].\n\n**Feature learning occurs even in a kernel regime**\n\nIn our framework, i.e., a kernel regime, feature learning occurs. In other words, network parameters are updated and learn class features from training samples.\n\nFor clarity, we offer the following definitions:\n\n- Feature learning: A process in neural networks where parameters change during training according to the training dataset via gradient flow, extracting class features, and determining predictions.\n- Kernel regime: A situation where parameters in neural networks change within a small (but not infinitely small) margin from their initialization in a (finitely) large width setting.\n\nThe key distinction between our work and previous studies is that prior work considers weights that can change freely (unrestricted feature learning), while our work examines weights that can change freely only around their initialization point (feature learning in a kernel regime).\n\n**Our assumptions and theorems do not require infinite network width.**\n\nAssumption 3.2 does not imply infinite width. For the identity loss, it requires $m > O(d^2T^2)$, where $d$ is the input dimension and $T$ is the continuous training time. Given the finiteness of $d$ and $T$, $m$ remains finite.\n\nOur theorems also do not necessitate infinite width. Let us consider simplified Assumption 3.2 and Theorem 3.4.\n\nAssumption 3.2: Network width $m$ satisfies $m > T^2$.  \nTheorem 3.4: Let $\\delta$ be a small positive number. Under Assumption 3.2, for any $z \\in \\mathbb{R}^d$, if $g_a(z) > 1 / T \\delta$ holds, then, with probability at least $1 - \\delta$, perturbation learning succeeds.\n\n$\\delta = 0$ leads to $T = \\infty$ and thus $m = \\infty$. However, for any small $\\delta > 0$, we can choose finite $T$ such that $g_a(z) > 1 / T \\delta$. Furthermore, for any $T > 0$, we can select finite $m$ such that $m > T^2$. Thus, for any $\\delta > 0$, a finite width is sufficient to consider Assumption 3.2 and Theorem 3.4. Note that strict positivity of $\\delta$ is assumed in these theorems.\n\nWe also note that $\\delta$ is the confidence level, and it is not necessary to consider it as $0$ or infinitesimal. For example, with $\\delta = 0.01$, we can choose a finite width $m$ that guarantees the success of perturbation learning with probability at least 99%. We believe that the impacts of $T$, $d$, and $N$ on perturbation learning with a fixed $\\delta$ are more insightful than considering the dynamics as $\\delta \\to 0$. The primary implication of Theorem 3.4 is that a large $T$ leads linearly, and $d$ and $N$ lead sublinearly, to more pronounced prediction matching with the same probability (fixed $\\delta$).\n\n**Our results hold even for infinite network width.**\n\nThe reviewer might consider that in sufficiently wide width, weights do not change from initialization, and thus networks do not learn class features. This is not correct.\n\nFor any $m$ and $T$, trained weights can be represented as $v_i(T) = v_i(0) + \\Delta_i(T)$ with $\\\\|\\Delta_i(T)\\\\| = O(T/\\sqrt{m})$. $\\Delta_i$ is not $0$ and aligns with data patterns, indicating that feature learning occurs. While $\\\\|\\Delta_i(T)\\\\|$ approaches zero as $m \\to \\infty$, it does not become zero for any $m$. If $\\\\|\\Delta_i(T)\\\\| = 0$ for every $i$, the trained network output $f(T)$ would be identical to the initialized output $f(0)$, meaning training would not work at all. For any $m$ (even infinitely large), each hidden weight changes slightly, and network outputs as the summation of outputs of hidden units change significantly during training. Therefore, neural networks learn class features, and our theorems are not invalidated for any width.\n\n**Feature learning is not necessary to justify the feature hypothesis.**\n\nThe reviewer suggests that theoretical approaches without feature learning dynamics cannot explain perturbation learning and the feature hypothesis. However, we consider that feature learning is not necessary to explain them. The key requirement to justify them is that the image gradients through a classifier (i.e., the direction of the perturbation) contain data information (like Theorem 3.3). For example, we believe that for kernel methods (which our analysis is not), we can empirically and theoretically justify them because the image gradients contain training sample information. Note that feature learning and the feature hypothesis are unrelated concepts.\n\n**Scaling of $\\epsilon$ (Question 2)**\n\nAs shown in Theorems 3.4 and 3.5, the L2 perturbation size $\\epsilon$ needs to scale with $\\sqrt{d}$. This scaling is a consequnce of the property of the L2 norm, which scales with $\\sqrt{d}$. To maintain the signal-to-noise ratio, L2 perturbation sizes must scale accordingly. For example, please refer to Table 2 in [1].\n\n[1] V. Sehwag et al., Robust Learning Meets Generative Models: Can Proxy Distributions Improve Adversarial Robustness? ICLR22.", "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": "AQYrQO5rKH", "reviewer": "Reviewer_5BXU", "summary": "This work aims to provide an alternative theoretical analysis to justify feature hypothesis and perturbation learning. The analysis is based on approximation theory in the kernel regime (i.e., infinite width). They show that the adversarial perturbation contains sufficient data information, which can be retrieved by the perturbation learning when y labels are uniformly sampled.", "questions": "See weakness.", "limitations": "Yes. The limitation is clearly statement in the paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is theoretically sound and relaxed certain conditions required by prior works.", "weaknesses": "What is the contribution beyond technical novelty? Are any new insights obtained via the new analysis compared to existing results?\nThe conditions in the main theorems lack interpretability. I can understand the technical reason behind them, but how reasonable are these conditions, especially the agreement condition? The author argues that the agreement condition depends on the consistency of the correlation between z and y_nx_n. This statement is not rigorous, since z is a function argument, but not a r.v. and there is no correlation involved. I suppose a more meaningful question will be, if z follows the data distribution of x (e.g., a mixture of two Gaussian), what is the chance these conditions hold?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer's suggestive questions. The reviewer seems to appreciate our technical contributions, and the questions are thus more posed on the high-level understanding of the results. We here address this concern. We are willing to address any feedback and requests for further clarification upon your response during the discussion period, which will hopefully lead to improved the reviewer’s understanding and evaluation of our work.\n\n> What is the contribution beyond technical novelty? Are any new insights obtained ... compared to existing results?\n\nIndeed, our work not only proposes a technically advanced analysis but also provides many insights into perturbation learning as follows:\n\n- A large dimension and longer training time strengthen the alignment between perturbations and training samples.\n- Similar samples in the training set are emphasized in perturbations.\n- Our results explicitly reveal the dependncy between the success of perturbation learning and each variable (dimension $d$, sample size $N$, perturbation size $\\epsilon$, and confidence $\\delta$)\n\nWe elaborate on them. \n\n**Feature hypothesis (Theorem 3.3).**\n\nOur results offer three new insights regarding the feature hypothesis.\n\nFirst, the residual term $\\xi_n$ in our result offers new insights into the alignment between perturbations and training samples. The direction of the perturbation vector is described by two components: the weighted sum of the training samples (main term) and the residual term. Our results suggest that as the input dimension increases, the residual term becomes smaller than the main term, and the alignment strengthens. In other words, perturbations more robustly contain class features. This insight was not obtainable from the existing research due to the absence of a residual in their limited problem setting.\n\nSecond, our result suggests that longer training time strengthens the directional agreement, which is supported by intuition and experience but has not been addressed in existing research.\n\nThird, we identify the coefficient $\\Phi(x_n, x_k)$ for each training sample. Our explicitly derived $\\Phi(x_n, x_k)$ reveals that the coefficient of each training sample is determined by the slope of the activation function and depends on the similarity between $x_n$ and $x_k$ (cf. Eq. (4)). This implies that the more similar samples are included in the training set, the stronger their influence is reflected in the perturbations. While similar coefficients existed in previous research, they are could not be explicitly obtained. \n\n**Perturbation learning (Theorems 3.4 and 3.5)**\n\nThe last insight is the explicit connection between the successful perturbation learning and training factors, including training time $T$, perturbation size $\\epsilon$, input dimension $d$, sample size $N$, and confidence level $\\delta$, enhancing our understanding of their impacts on perturbation learning. For example, perturbation learning succeeds more easily with a sublinear speed with respect to the dimension $d$ and sample size $N$. Furthermore, our findings indicate that either a large $d$ or $N$ alone is insufficient since Eqs. (9) and (10) include $d$- and $N$-irrelevant terms. In contrast, existing research does not explain the impact of these variables, only demonsrtating that it succeeds when both $d$ and $N$ are infinite.\n\nAdditionally, technical improvements in data distribution, perturbation design, training procedures, and network settings directly contribute to understanding the broad applicability of the feature hypothesis and the success of perturbation learning. These improvements are insightful in their own right.\n\n> The conditions in the main theorems lack interpretability. ... how reasonable are these conditions, especially the agreement condition? ... if z follows the data distribution of x ..., what is the chance these conditions hold?\n\nIn this context, we used \"correlation\" only to abbreviate (the sign of) the inner product of two vectors (not necessarily random variables). We will improve our manuscript to reduce any misleading.\n\nWe consider $z$ as an arbitrary $d$-dimensional vector rather than a random variable to provide general results that do not depend on a specific probability distribution. This approach allows for easy consideration of $z$ as a random variable in subsequent analyses.\n\nLet us consider the agreement condition in the following setting.\n\n1. The positive sample size is $N/2$, and the negative is $N/2$.\n2. $x_1, \\ldots, x_N$ are i.i.d. and sampled from $\\mathcal{N}(y_n\\mu, I_d)$, where $\\mu$ is a $d$-dimensional vector.\n3. $z$ follows $\\mathcal{N}(\\mu, I_d)$; namely, $z$ is positive.\n\nIn this setting, informally, the following holds:\n\n1. $\\langle x_n, z\\rangle = y_n \\| \\mu \\|^2 \\pm O(\\sqrt{d}\\ln(1/\\delta))$\n2. $\\Phi_+ = \\Phi(x_n, z)$ if $y_n = +1$, otherwise $\\Phi_- = \\Phi(x_n, z)$\n3. $\\Phi_+ = \\Phi(x_n, x_k)$ if $y_ny_k = +1$, otherwise $\\Phi_- = \\Phi(x_n, x_k)$\n\n(1) is derived from a concentration inequality, where $\\delta$ is the confidence level. Since $x_n$ has the same probabilistic properties within each class, $\\Phi(x_n, z)$ should have similar values for all $n$ satisfying $y_n = 1$ (or $y_n = -1$). While there would be probabilistic fluctuations, for simplicity, we fix $\\Phi_+ := \\Phi(x_n, z)$ if $y_n=1$, and $\\Phi_- := \\phi(x_n, z)$ if $y_n = -1$. Similarly, we fix $\\Phi(x_n, x_k)$ as in (3).\n\nNoting that $\\Phi_+ = \\Theta(1)$ and $\\Phi_- = \\Theta(1)$, and if the sign of $\\sum_k y_k \\Phi(x_n, x_k) \\langle x_k, z \\rangle$ is the same for all $n$, then the sign of $\\hat{g}_a(z)$ is equal to it, we can derive:\n\n- $sgn(\\hat{f}(z)) = (\\Phi_+ + \\Phi_-) \\| \\mu \\|^2 \\pm O(\\sqrt{d}\\ln(1/\\delta)) = \\Theta(d) \\pm O(\\sqrt{d}\\ln(1/\\delta))$\n- $sgn(\\hat{g}(z)) = (\\Phi_+ + \\Phi_-) \\| \\mu \\|^2 \\pm O(\\sqrt{d}\\ln(1/\\delta)) = \\Theta(d) \\pm O(\\sqrt{d}\\ln(1/\\delta))$\n\nThis implies that if the input dimension $d$ is large, the agreement condition easily holds with high probability.", "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": "JxfuzFS3vV", "reviewer": "Reviewer_fzgX", "summary": "In this paper, the authors theoretically investigate the perturbation learning phenomenon from a future hypothesis perspective. Perturbation learning means that a classifier can be learned from adversarial examples with incorrect labels (the labels used to generate adversarial examples, but seems to be incorrect in human eyes). Their theory includes two parts. First, they show that the adversarial perturbations are the linear combination of training samples, thus containing the information of the clean training dataset. This theorem provides an intuition for the feature hypothesis. Then, they show that, under some conditions, the predictions of a classifier trained on adversarial perturbations (or adversarial examples) are consistent with those of a classifier trained on a clean dataset.\n\nSome experiments on a synthetic Gaussian dataset are provided to show the effect of the input dimension and hidden dimension, validating their theorem.", "questions": "Experimental Questions:\n* What is the effect of the sampling of adversarial labels on the accuracy of the model $g$? If we set the adversarial labels of all negative data to be positive and vice versa, will the accuracy of $g$ be very low?\n* What is the effect of the structures of $f$ and $g$? When these two networks have more divergent structures, I think the accuracy of $g$ must be lower. Is it correct in experiments? If it is, this is similar to the transferability of adversarial examples, i.e., the adversarial examples are easier to transfer to similar networks.\n\nTheoretical Questions:\n* What do the functions $\\hat{f}$ and $\\hat{g}$ mean? What are the relationships between $f$ and $\\hat{f}$, $g$ and $\\hat{g}$?", "limitations": "The authors state the limitation on the assumption of the width of the network in the paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* Understanding perturbation learning and the feature hypothesis is quite important in the domain of adversarial learning. This paper provides a deeper understanding of this problem.\n* In this paper, the authors provide a more general theory about perturbation learning compared to prior work. The theory is based on fewer constraints in training data distribution, training time, etc.", "weaknesses": "My main concern is whether the kernel regime is a suitable and extensible tool to study the feature hypothesis in adversarial training and explain other interesting phenomena such as the transferability of adversarial examples and the trade-off between robustness and accuracy. \n\nAccording to the feature hypothesis of adversarial training, the data contains a set of features that could used for prediction. Humans and all kinds of neural networks use different feature subsets to classify the image (the subsets have overlaps). The feature hypothesis may provide a **unified** explanation for several open problems in adversarial training. However, it seems that the theory in this paper only focuses on perturbation learning and is difficult to extend to explain other phenomena. In my opinion, the framework should have a deeper exploration of the feature subsets that are used by the trained models to make predictions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's constructive comments.\n\n> My main concern is whether the kernel regime is a suitable and extensible tool to study the feature hypothesis in adversarial training and explain other interesting phenomena such as the transferability of adversarial examples and the trade-off between robustness and accuracy. ... The feature hypothesis may provide a unified explanation for several open problems in adversarial training. However, it seems that the theory in this paper only focuses on perturbation learning and is difficult to extend to explain other phenomena. In my opinion, the framework should have a deeper exploration of the feature subsets that are used by the trained models to make predictions\n\nFirst, we would like to emphasize the following: **the target of this study is perturbation learning, not others**, such as adversarial training or transferability. While the feature hypothesis and perturbation learning are foundational for understanding several phenomena of adversarial examples and training, they are originally different research topics. We would appreciate it if the reviewers evaluated our work fairly, taking into account its scope.\n\nNevertheless, we found the questions insightful for our future work because our analysis is compatible with the setups of adversarial training and other related topics. Recall that all of our discussions stem from the update equation of gradient descent (flow), which is a fundamental and common component of deep learning. In addition, the main assumption is only wide width, which is only used to control each gradient descent step and not specific to perturbation learning. These advantages of our framework generally do not confxlict with the analysis of adversarial training and examples. Therefore, we consider that our framework is helpful for considering the features (subsets) of adversarial examples and adversarial training. If there are specific barriers that the reviewer foresees, we would greatly appreciate if they could be shared during the discussion period.\n\nFor these reasons, we believe our theoretical framework has the potential to address other problems and phenomena, including adversarial training and examples. However, we would like to respectfully emphasize that the primary focus of our research is perturbation learning and the feature hypothesis. We kindly ask the reviewer to consider evaluating our work from this perspective. We believe that our research offers novel and profound theoretical insights into perturbation learning.\n\n> What is the effect of the sampling of adversarial labels on the accuracy of the model $g$? If we set the adversarial labels of all negative data to be positive and vice versa, will the accuracy of $g$ be very low?\n\nEmpirically, the accuracy of $g$ decreases along with the increase of label flips (i.e., negative to positive and vice versa). However, it is known that deep neural networks can sometimes achieve above-chance accuracy even in such environments. Detailed experimental results are presented in [13] and [18]. On the other hand, for simpler models like two-layer networks, it is empirically difficult to achieve accuracy significantly above chance in such environments. Indeed, our theoretical results, similar to prior work [18], indicate that two-layer networks are unlikely to achieve prediction matching under flipped label conditions.\n\n> What is the effect of the structures of $f$ and $g$? When these two networks have more divergent structures, I think the accuracy of $g$ must be lower. Is it correct in experiments? If it is, this is similar to the transferability of adversarial examples, i.e., the adversarial examples are easier to transfer to similar networks.\n\nThe more different the structures of $f$ and $g$ are, the lower the accuracy of $g$ tends to be. As the reviewer pointed out, this behavior is similar to that observed in transferability, suggesting that the features captured by models during learning (and exploited by adversarial attacks) are dependent on the structure. These results are provided in Figure 3 [13].\n\n> What do the functions $\\hat{f}$ and $\\hat{g}$ mean? What are the relationships between $f$ and $\\hat{f}$, $g$ and $\\hat{g}$?\n\n$\\hat{f}$ and $\\hat{g}$ can be interpreted as the main components of $f$ and $g$ respectively. Specifically, $f(z) = \\hat{f}(z) + \\Delta_f(z)$ and $g(z) = \\hat{g}(z) + \\Delta_g(z)$, where $\\Delta_f(z)$ and $\\Delta_g(z)$ are, in many cases, relatively smaller than $\\hat{f}(z)$ and $\\hat{g}(z)$. Therefore, if the signs of $\\hat{f}(z)$ and $\\hat{g}(z)$ match (i.e., the agreement condition holds), in most cases, the signs of $f(z)$ and $g(z)$ also match (i.e., perturbation learning succeeds). The functional margin conditions represent the conditions under which $\\hat{f}(z)$ and $\\hat{g}(z)$ become sufficiently large relative to $\\Delta_f(z)$ and $\\Delta_g(z)$.", "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:

Meta-review: The paper presents a significant theoretical contribution by analyzing perturbation learning in wide two-layer networks within the kernel regime. The reviewers recognized the originality and importance of this work, with Reviewer MQtT noting that the paper addresses a “very interesting problem” and provides a “significant problem in an original way.” Despite initial concerns about the kernel regime’s applicability to feature learning, the authors clarified that feature learning does occur in this regime and emphasized that their results hold for finite-width settings, which is more practical. Reviewer 5BXU highlighted that the paper is “theoretically sound” and praised its relaxation of certain conditions from prior works, noting the explicit connections the authors make between training factors and the success of perturbation learning. Reviewer fzgX appreciated the deeper understanding the paper provides for the feature hypothesis in adversarial learning, though they suggested exploring extensions to other adversarial training phenomena in future work. The authors’ responses effectively addressed the reviewers’ concerns, leading to score improvements and demonstrating the paper’s potential to make a strong impact on the field. Given the theoretical depth, novel insights, and the thorough clarifications provided, I recommend accepting the paper.
Decision: Accept (poster)