Theoretical Analysis of Robust Overfitting for Wide DNNs: An NTK Approach
Authors: Shaopeng Fu
Di Wang
Venue: ICLR 2024 poster (2024)
Keywords: NTK
neural tangent kernels
adversarial training
robust overfitting
Primary area: societal considerations including fairness, safety, privacy
TL;DR: We present a theoretical explanation of robust overfitting for DNNs and design the first adversarial training algorithm for infinite-width DNNs.

Abstract: Adversarial training (AT) is a canonical method for enhancing the robustness of deep neural networks (DNNs). However, recent studies empirically demonstrated that it suffers from robust overfitting, i.e., a long time AT can be detrimental to the robustness of DNNs. This paper presents a theoretical explanation of robust overfitting for DNNs. Specifically, we non-trivially extend the neural tangent kernel (NTK) theory to AT and prove that an adversarially trained wide DNN can be well approximated by a linearized DNN. Moreover, for squared loss, closed-form AT dynamics for the linearized DNN can be derived, which reveals a new AT degeneration phenomenon: a long-term AT will result in a wide DNN degenerates to that obtained without AT and thus cause robust overfitting. Based on our theoretical results, we further design a method namely Adv-NTK, the first AT algorithm for infinite-width DNNs. Experiments on real-world datasets show that Adv-NTK can help infinite-width DNNs enhance comparable robustness to that of their finite-width counterparts, which in turn justifies our theoretical findings. The code is available at https://github.com/fshp971/adv-ntk.

Published as a conference paper at ICLR 2024
THEORETICAL ANALYSIS OF ROBUST OVERFITTING FOR WIDE DNNS: AN NTK APPROACH
Shaopeng Fu & Di Wang
Provable Responsible Al and Data Analytics (PRADA) Lab King Ahdullah University of Science and Technology, Saudi Arabia (shaopeng. fu, di
edu.
ABSTRACT
Adversarial training (AT) is a canonical method for enhancing the robustness of deep neural networks (DNNs). However, recent studies empirically demonstrated that it suffers from robust overfitting, i.e., long time AT can be detrimental to the robustness of DNNs. This paper presents a theoretical explanation robust overfitting for DNNs. Specifically, we non-trivially extend the neural tangent ker- nel (NTK) theory to AT and prove that an adversarially trained wide DNN can be well approximated by linearized DNN. Moreover, for squared loss, closed- form AT dynamics for the linearized DNN can be derived, which reveals a new AT degeneration phenomenon: a long-term AT will result in wide DNN degen- erates to that obtained without AT and thus cause robust overfitting. Based on our theoretical results, we further design method namely Adv-NTK, the first AT algorithm for wifdnite-width DNNs. Experiments on real-world datasets show that Adv-NTK can help dfinitewwidth DNNs enhance comparable robustness to that of their finite-width counterparts, which in turn justifies our theoretical findings. The code is available at https: /tts:///g/ttbb//////// cwt/ 971 /a1////1-/////////////eeae//aa// aadv-nkk.
INTRODUCTION
Despite the advancements of deep neural networks (DNNs) in real-world applications. they are found to be vulnerable to adversarial attacks. By adding specially designed noises, one can trans- form clean data to adversarial examples to fool DNN to behave in unexpected ways (Szegedy et al., 2013; Goodfellow et al., 2015). To tackle the risk, one of the most effective defenses is adver- sarial training (AT), which enhances the robustness DNNs against attacks via training them on adversarial examples (Madry et al., 2018). However, recent study shows that AT suffers from robust overfitting: after a certain point in AT, further training will continue to degrade the robust general- ization ability of DNNs (Rice et al., 2020). This breaks the common belief of "training long and generalize well" in deep learning and raises security concerns on real-world deep learning systems.
While line of methods has been developed mitigate robust overfitting in practice (Yu al., 2022; Chen et al., 2021; Wu et al., 2020; Li & Spratling, 2023), recent studies attempt to theoretically understand the mechanism behind robust overfitting. However, existing theoretical results mainly focus on analyzing the robustness of machine learning models that have already been trained to converge but overlook the changes of robustness during AT (Min et al., 2021; Bombari al., 2023; Zhang & Li, 2023; Clarysse et al., 2023). More recently, a work by Li & Li (2023) has started to incorporate the training process into the study of robust overfitting. However, their analysis currently only applies to two-layer neural networks. Thus, we still cannot answer the question: Why a DNN would gradually lose its robustness gained from the early stage of AT during continuous training?
Motivated by the recent success of neural tangent kernel (NTK) theory (Jacot et al., 2018) in approx- imating wide DNNs in standard training with closed-form training dynamics (Lee et al., 2019), this paper makes the first attempt to address the raised question by non-trivially extending NTK to theo- retically analyze the AT dynamics of wide DNNs. Our main result is that for an adversarially trained multilayer perceptron (MLP) with any (finite) number of layers, the widths of layers approach in- finity, the network can be approximated by its linearized counterpart derived from Taylor expansion. When the squared loss is used, we further derive closed-form AT dynamics for the linearized MI.P.

---

Published as a conference paper at ICLR 2024
The key challenge of our theory arises from the process of searching adversarial examples in AT. In the vanilla AT, the strength of adversarial examples used for training is controlled by searching them within constrained spaces. But such constrained-spacee condition prevents one from conducting continuous gradient flow-based NTK analysis on that search process. We propose a general strategy to remove this condition from AT by introducing an additional learning rate term into the search process to control the strength of adversarial examples. With our solution, one can now characterize the behavior of DNNs in AT by directly studying the gradient flow descent in AT with NTK.
Our theory then reveals a new AT degeneration phenomenon that we believe is the main cause of robust overfitting in DNNs. In detail, our theory suggests that the effect of AT on a DNN can be characterized by a regularization matrix introduced into the linearized closed-form AT dynamics, which however will gradually fade away in long-term AT. In other words, a long-term AT will result in an adversarially trained DNN degenerate to that obtained without AT, which thus explains why the DNN will lose its previously gained robustness. Based on our analysis, we further propose Adv- NTK, the first AT algorithm for seffinttewwdtth DNNs which improves network robustness by directly optimizing the introduced regularization matrix. Experiments on real-world datasets demonstrate that Adv-NTK can help anfinite-width DNNs gain robustness that is comparable with finite-width ones, which in turn justifies our theoretical findings.
In summary, work has three main contributions: (1) We proved that a wide DNN in AT can be strictly approximated by a linearized DNN with closed-form AT dynamics. (2) Our theory reveals novel AT degeneration phenomenon that theoretically explains robust overfitting of DNNs for the first time. (3) We designed Adv-NTK, the first AT algorithm for inftnite-width DNNs.
RELATED WORKS
Robust overfitting. Rice al. (2020) first find this phenomenon in adversarially trained DNNs. A series of works then design various regularization techniques to mitigate it in practice (Zhang et al., 2021; Yu al.. 2022: Wu al., 2020; Li & Spratling, 2023; Chen et al., 2021). Recent studies attempt to theoretically explain robust overfitting. Donhauser et al. (2021) and Hassani & Javanmard (2022) show that the robust generalizability follows a double descent phenomenon concerning the model scale. Wang et al. (2022) show that two-layer neural network that is closed to the initialization and with frozen second-layer parameter is provably vulnerable to adversarial attacks. However, this result requires the inputs coming from the unit sphere, which is not realistic in the real world. Other advances include Zhu et al. (2022), Bombari et al. (2023), Bubeck et al. (2021), Zhang& & Li (2023) and Clarysse et al. (2023). Since these works only focus analyzing converged models, it remains unclear how robustness of DNN occurs and degrades during AT.
Li & Li (2023) are the first that consider the AT evolution process in studying robust overfitting. Based on the feature learning theory, they find a two-layer CNN in AT will gradually memorize data-wise random noise in adversarial training data, which makes it difficult to generalize well on unseen adversarial data. However, their theory currently is only applicable to shallow networks, and could not explain why networks will lose previously acquired robustness with further AT.
Neural tangent kernel (NTK). Jacot et al. (2018) show that for a wide neural network, its gradient descent dynamics can be described by kernel, named neural tangent kernel (NTK). Based on NTK, the learning process of neural networks can be simplified as a linear kernel regression (Jacot et al., 2018; Lee al., 2019), which makes NTK a suitable theoretical tool to analyze overparameterizee models (Li & Liang, 2018; Zou et al., 2020; Allen-Zhu et al., 2019). Recent studies have extended NTK to various model architectures (Arora et al., 2019; Hron al., 2020; Du al., 2019a; Lee et al., 2022), and the theory itself helps understand deep learning from various aspects such as convergence (Du et al., 2019b; Cao & Gu, 2019), generalization (Lai et al., 2023; Huang et al., 2020; Chen et al., 2020; Barzilai et al., 2023; Hu et al., 2020), and trainability (Xiao et al., 2020).
NTK has also been used to analyze AT on overparameterized models. Gao et al. (2019) and Zhang et al. (2020) study the convergence of overparameterized networks in AT and prove upper bounds on the time required for AT. More recent works empirically study robust overfitting with NTK. Tsilivis & Kempe (2022) use eigenspectrums of NTKs to identify robust non-robust features. Loo et al. (2022) empirically show that a finite-width NTK in AT will rapidly converge to a kernel encodes robust features. But none of them provide theoretical explanations of robust overfitting.
2

---

Published as a conference paper at ICLR 2024
3 PRELIMINARIES
Notations. Let @ denotes Kronecker product, Diag(-) denotes a diagonal matrix constructed from given input, (-) denotes the Jacobian of a given function, Amax() (-) denotes the maximum eigen- value of given matrix, and In (n E N+) denotes
x identity matrix. For set of random variables x, indexed by and an additional random variable X, we use X, E X to denote that X2 converges in probability to X. See Appendices A.2 and A.3 for a full list of notations and definitions of convergence in probability and Lipschitz continuity/smootnness.
Let D ((11,))) ... (arM; yMr) be a dataset consists of M samples, where v; E C Rd the i-th input feature vector and yi E C IR. is its label. A parameterized DNN is denoted as f(0,-) X +. where is the model parameter. For simplicity, we let x := #;=1 [ E add denotes the concatenation of inputs and y := @ E RM denotes the concatenation of labels. Thereby, the concatenation of (0,,1), ((0 xM) can be further denoted as f(0,,x x) (x;) E R-Mc.
Adversarial training (AT). Suppose L IR x RR - IR+ a loss function. Then, a standard AT improves the robustness of DNNs against adversarial attacks by training them on most adversarial examples. Specifically, it aims to solve the following minimax problem (Madry et al., 2018),
min D
Σ
max Iar
1Sp- (()(0,=)).
(EL.U)ED
where p E R is the adversarial perturbation radius and x is the most adversarial example within the ball sphere centered at z;. Intuitively, a large perturbation radius p would result in the final model achieving strong adversarial robustness.
Neural tangent kernel (NTK). For DNN f that trained according to some iterative algorithm, let ft= == [0,,.) -) where 0g is the DNN parameter obtained at the training time t. Then, the empirical NTK of the DNN at time t is defined as below (Jacot et al., 2018),
(z,(z, x²) == fz)( 07 fe(x') E R Vz, x' EX.
(2)
In the rest of the paper, we will also use the notations (0, = 00f((2) 0z f((x) Re and (x, x) == fof((x) 0% fx(x) E Me.
When ft is trained via minimizing the empirical squared loss ElerwIeD [ v Lee al. (2019) show that it can be approximated by the linearized DNN f!ln :X' + y defined as follows, f. (x) := fo( Oz.0 x) (x, (1 (1-e-00,o(xx))) (fo(x) - y).
(3)
Although the kernel function θo,, depends on both the initial parameter 9n and the time t. Jacot al. (2018) prove that θ,.- -4, θg the network widths go to infinity, where O₂ is a kernel function that is independent of 0g and t. Based on it, Lee et al. (2019) show that with infinite training time, the average output of infinite-width DNNs over random initialization will converge as follows,
lim widths
lim Es, [f()] E. (x, (x. y, Vx E X, E-000
where Og(x, x) E Me is an 1 x M block matrix that the i-th column block is Og x;), and O& (x, x) E Meexxe is an M M block matrix that the i-th row j-th column block is Og (xi,
4 ADVERSARIAL TRAINING OF WIDE DNNS
In this section, we present our main theoretical results that characterize AT dynamics of wide DNNs. We first introduce the DNN architectures that we are going to analyze.
Suppose f0, -) is a DNN consisting of L + fully connected layers, in which the width of the 1-th hidden layer (1 S S L) ny. Additionally, the input dimension and the output dimension are denoted as Mo := d and nL+11 fully-connected layer (1 < 1 < L + 1) is calculated as follows.
for simplicity. Then, the forward propagation in the 1-th
(x) = 1
( x (x) + +b0,, x0(()) -(h
(5)
3

---

Published as a conference paper at ICLR 2024
where h0 and x!!)) are the pre-activated and post-activated functions at the 1-th layer. W R is the 1-th weight matrix, 8(1) E TR is the 1-th bias vector, and & is point-wise activation function. The final DNN function is f(0,-) ) = (.)+ with model parameter 0 : (Wa),... ,.... W(L+1), ba),..... ... bb(++)), and we use ft == -(0,,- denote the DNN at the training time t. Finally, for the initialization of d.. we draw each entry of weight matrices from Gaussian N w and each entry of bias vectors from a Gaussian of)
Similar to existing NTK literatures (Jacot al., 2018: Lee al., 2019; Arora al., 2019), we are also interested in the linearized DNN f defined as follows,
fo(x) fo (0! - Oo), Vx E X,
(6)
where On is the initial parameter same that of the non-linear DNN ft and 0linn is the parameter of the linearized DNN at the training time t.
4.1 GRADIENT FLOW-BASED ADVERSARIAL EXAMPLE SEARCH
To characterize the training dynamics of AT, the key step to analyze the process of searching adversarial examples that will be used to calculate AT optimization directions. Recall Eq. (1), stan- dard minimax AT will search adversarial examples within constrained spaces. However, analyzing such a process with continuous gradient flows is challenging due to the need to explicitly model the boundaries of those constrained spaces.
To tackle the challenge, we notice that the main role of the constrained-spaces condition is to control the adversarial strength (i.e., the strength of the ability to make models misbehave) of searched data. As a solution, we suggest replacing the constrained-spaces condition (controlled by p in Eq. (1)) with an additional learning rate term (i.e.. (t) in Eq. (7)) to control the strength of adversarial examples. This modification will then enable more convenient continuous gradient flow analysis.
Specifically, for the DNN ft at the training time t, to find the corresponding adversarial example of the i-th training data point (z,, y1) where 1 S i S M, will start from 2; and perform gradient flow ascent for a total of time >> O, with an introduced learning rate ()()) : - IR to control the adversarial strength of searched example at the current training time f, as below,
0,0,,1,- (t)- o%. f((,,.)))
((f
s.t.
F1,,0 I₁.
Then, the final adversarial example is 21,..S- The learning rate (7(() plays a similar role with the constrained-spart condition in Eq. (1). Intuitively, larger (t) at the training time corresponds to more adversarial example r;,
Besides, running the gradient flow defined in Eq. (7) also depends on the DNN output of which the evolution of fe(2i,,.)) concerning 8 can be formalized based on Eq. (7) as follows,
(efe(rs,t,s) = Oz fI 0,Ti,t, (t)
Foo ((fe(Fst.))) v.), (8)
where Öz,t= X x X + Rexx is new kernel function named Adversarial Regularization Kernel (ARK) and defined as below,
(z, = 0.f((2) 0f f(
Va, E X.
(9)
The ARK θ.., shares similar structure with the NTK θ,,; defined in Eq. (2). The difference is that the kernel matrix O.,, is calculated from Jacobians of DNN Si concerning input, while the NTK Óo, is calculated from Jacobians concerning the model parameter.
4.2 ADVERSARIAL TRAINING DYNAMICS
With the gradient flow-based adversarial example search in the previous section, we now formalize the gradient bowebased AT dynamics for the wide DNN fa and the linearized DNN flin respectively.
AT dynamics of wide DNN f.. Suppose fi is trained via continuous gradient flow descent. Then, the evolution of model parameter 02 and model output fx) are formalized as follows,
0,0, = - (x(,,s)) 8i/c (U)(),
(10)
0zf((z) = fz)( 0,0, = -0,,(2, 07 ((f(x.)) Vr X,
(1I)
4

---

Published as a conference paper at ICLR 2024
where Xt,S = @b Fi,t, is the concatenation of adversarial examples found at the current training time t, and θo, : is the empirical NTK defined in Eq. (2).
Meanwhile, based on the method proposed in Section 4.1, the gradient flow-based search process for the concatenation of adversarial examples Xt,s is formalized as below,
0, 0 ( (tt) Fox) ((f(
s.t.
X
(12)
0.ft (xt, = 0xf((xe.)) 0,x,, = Or, (X,.s, Xx,s) (t) 0f ((i()())))))
(13)
where Xt,, 0 is the concatenation of intermediate adversarial training examples found at the search time (() Diag(m ((,).,)),,))))) (T) E MMMMM is a block diagonal learning rate (T.. #Ma,,)) E R.MoxMe is
matrix, and ( xt,s) == Diag (1
a block diagonal matrix consists of ARKs.
AT dynamics of linearized wide DNN f!in. Suppose f! is also trained via continuous gradient flow descent. Then, according to the definition of linearized DNN in Eq. (6), we have Se fll Og. fo- Therefore, the evolution of parameter Oli and output fli (1)) formalized follows,
0.0!!m 0gg fo(x) Ffx) C (x(()))))))))))
(14)
a.St (2) = 0ofo(() 0,0 xx) 0%/
Vo E X,
(15)
where x == @ is concatenation of the adversarial examples found for the linearized DNN fi and θş.0 is the empirical NTK (see Eq. (2)) at initialization.
The search of xlin is slightly different from the gradient flow-based method Section 4.1. When following Eqs. (7) and (8) to search <hi one needs to calculate an intractable Jacobian fzff. (s:!in..) = 0₂ fo(linn (de fo fo that in standard training, a wide DNN is approximately linear concerning model parameters, thus it is also reasonable deduce that wide DNN in AT' is approximately linear concerning slightly perturbed adversarial inputs, In other words, we deduce that 0z (# x 02 fo (a + 0 so Og fu(.). Thus, we propose to replace f. (a:lin with 0z (2 in the search of ",,,.'
6u)) To further simplify analysis, note
Then, by replacing 0zflinn (x!in..) with 0z fo(;)) in Eqs.(7) and (8), the overall search process for Iin in the linearized AT dynamics is formalized as below,
0axlin = f_ fo(x) (() T (XFx(x)))
s.L.
x x,
(16)
a. flin (x._m) = 0x fo(x) 0,x!! (x,0(x,x) x) ntt) F(x) (x (x..
(17)
lin where lin = @ 1 s,t,a is the concatenation of intermediate adversarial examples for the linearized
DNN flin the learning rate matrix (t) is same that the AT dynamics of ft, and 0x,0(x,x) x) =
Diag( (2,0 ... (r,o(TMM,aad is a block matrix consists of ARKs at initialization.
4.3 ADVERSARIAL TRAINING IN INFINITE- SERNITE-WIDTH
This section theoretically characterizes the AT dynamics of the DNN fa when the network widths approach the infinite limit. We first prove the kemeel limits at initialization as Theorem 1.
Theorem 1 (Kernels limits at initialization; Informal version of Theorem B.1), Suppose fo is an MLP defined and initialized as in Section 4. Then. for any 2, x' E X we have
lim lim 00,0 x') = O0(x, x') = 6 (x, x') Inzin R00
ny. +
lim
lim
@n.(Zz,) x') = O,(x, : (x, Iorti
Ry. 700
700
where O% X X + and 00 X X + I are two deterministic kernel functions.
The proof is given in Appendix B. Remark 1. The convergence of NTK @o. is first proved in Jacot et al. (2018). We restate it for the sake of completeness. Note that the limit of NTK Oo.p in AT is the as that in standard training.
5

---

Published as a conference paper at ICLR 2024
We then prove that wide DNN fi can be approximated by its linearized counterpart f! as shown in Theorem 2. relies on the following Assumptions 1-4.
Assumption 1. The activation fnnntaioon,unccion Φ IR + I is twice-diiferemiiable K K-Lipschitz continuous, K K-Lipschitz smooth, and satisfies [Ø(0) +00.
Assumption 2. For any fixed T > O, we have that So
= Op(1),
suPrejo,T] So [(fxx) (p(1) as min (non , , - oc.
Op(1), and suptejo.17 lo ((
Assumption 3. (t) and (t) are continuous on [0, +00). Assumption 4. The loss function L: 3 x + R is K K-Lipschitz smooth.
Assumptions 1 and 4 commonly used in existing NTK literatures (Jacot al., 2018; Lee al., 2019: 2022). Assumption is mild. Assumption assumes that the cumulated perturbation loss directions well as AT loss directions widely adopted in NTK studies for standard training.
stochastically bounded. Similar assumptions are also
Theorem 2 (Equivalence between wide DNN and linearized DNN), Suppose Assumptions 1-4 hold, and f and f( are trained following the AT dynamics formalized in Section 4.2. Then, if there exists ñ N such that min
,LL 2 ñ always holds, we havefor any X, ñ
lim R00
lim No- =E(O.T]
sup [lfa(z) f (x)(2)) 4..
The overall proof is presented in Appendix C.
Remark 2. Although our AT dynamics is formed based on the intuition that wide DNNs could be linear concerning slightly perturbed inputs, Theorem 2 does not depend on this intuition. It mainly depends the large-widit condition and also holds when large perturbations present.
Finally, we calculate the closed-form AT dynamics for the linearized DNN flin (Theorem 3) as well as the infinite-widd width DNN fe (Corollary 1) when squared loss [(f(z) v) := l1f(()) vli is used.
Theorem 3 (Close-form AT-dynamics of flin under squared loss). Suppose Assumption 3 holds and the linearized DNN flan is trained following the AT dynamics formalized in Section 4.2 with squared loss [(f(x), y) = (x) v113. Then, for any x E X, we have
flim (I) = fo(x)) (2, x) (x, (1- -- (1--0x((xx)EE())) (fo(x) y), (18) where É(I) Diag(1Jo exp(O ( (T)))
Mex regularization matrix.
The proof is given in Appendix D.
Corollary 1. Suppose all conditions in Theorems 2, 3 hold. Then, if there exists E N+ such that min(no,." ,nL) 2 ñ always holds, have for any X, as ñ - oc,
(limag ... 1..lim 100 (f(()))))))))))))))))())) [x))} E, (x))),,, and
(allf((())) O0(x, x). 0 (x,x) -1-- )1-)-8 .y.
(19)
where E(t)= == Diag( ( exp (z., 21:) mT(T) S) dr ( E Mex is diagonal regulariza- tion matrix, and O, and O₂ are kernel functions
functiion in the infinite-width limit.
Proof. The proof is completed by adopting Theorems 1, 2 and Lemma B.1 into Theorem 3.
Remark 3. Recall Remark 1, the infinit-widdhh NTK function Og in AT is exactly the same as that in standard training. As result, in practice θe can be calculated by using the Neural-Tanne -Tangents Python Library (Novak et al., 2020) and the JAX autograd system (Bradbury et al., 2018).
5 ROBUST OVERFITTING IN WIDE DNNS
So far, we have shown that a wide DNN that is adversarially trained with squared loss can be approx- imated by its linearized counterpart which admits closed-form AT dynamics. Now, we leverage our theory to theoretically understand and mitigate robust overfitting in wide DNNs. Throughout this section, the loss function is assumed to be the squared loss ((f(),,)) [Il((=) vll..

---

Published as a conference paper at ICLR 2024
5.1 AT DEGENERATION LEADS TO ROBUST OVERFITTING
This section reveals a novel AT degeneration phenomenon that theoretically explains the mecha- nism behind deep robust overfitting. Compared with existing theoretical studies on robust overfit- ting (Donhauser et al., 2021; Bombari et al., 2023; Zhang & Li, 2023; Clarysse et al., 2023; Li & Li, 2023), our result has two significant advantages: (1) can explain why the gained robustness will gradually lose in long-term AT, and (2) it applies to general deep neural network models.
We propose to study the AT dynamics of the linearized DNN instead of the original DNN since it is proved in Theorem 2 that a wide DNN can be approximated by the linearized one. Comparing the closed-form dynamics of the linearized DNN in AT (Eq. (18) in Theorem 3) with that in standard training (Eq. (3)), one can find that the difference is AT introduces a time-dependent regularization matrix E(t) (Theorem 3) into the closed dynamics of standard training. Thus, it can be deduced that the introduced matrix E()) fully captures the adversarial robustness of DNNs brought by AT.
To answer why the robustness captured by E(t) will gradually degrade in long-term AT, without loss of generality, we first assume that the ARK ex,0 x) is positive definite. Thereby, it can be decomposed as 6x,0(x, x) == QDQ", where Q is a block diagonal matrix consists of orthogonal blocks and D is diagonal matrix consists of positive diagonal entries. Since nt) is commutative with 0x,0(x, (x, x) and thus also with Q, the matrix (() can be further decomposed as follows,
E(t) = S." "xp(QDQ" n(T) s)dT= L. Q exp(Dn(()))) dr QA(t)T" a(t), (20)
where a(t) := Amax exp (r)))) is a strictly increasing scale function and A(t) atT So (x)(Dn())))dr is a matrix that sup IIQA()) 1l2 - 1. The here is to decouple the unbounded a(t) from E(t) and remain others being bounded, which can simplify our analysis.
Then, for the exponential term in the AT dynamics in Eq. (18), substituting E(() and we have QA(I)* aa()) A(1)= (21) where the calculation details is given in Appendix E.1. We further assume that: (1) the adver- sarial perturbation scale is small enough such that the symmetric A(zo) @" (X)(o))))))) stays positive definite, and (2) a(t) + Do as t + co. Under the first assumption, we have A(co) "t x)o)( == Q'D'Q'T where Q' is an orthogonal matrix and D' is a di- agonal matrix consisting of positive diagonal entries. Combined with the second one, we have
e 0 (0() = QA(()= eep((A(())) 6x,0(x,))
cxp(=A(x))* 0,,0(x,x) x) QA(co)+ & a(oo)) = Q'e -D'aa(o0) =
(22)
where the calculation is presented in Appendix 1. As a result,
lim e _x00 = QA((=)) 0 A(oo)=QT== 0.
(23)
8-000
Eq. (23) indicates that in long-term AT, the regularization matrix E(I) which captures robustness brought by AT will gradually fade away. Moreover, when at the infinite training time limit, the AT dynamics will converge to fo(z)- 0,,0 x) G7, (x, x) (fo(x) yy), which is exactly the same limit as that of the standard training dynamics given in Eq. (3), Notice that the analysis up to now relies on that the adversarial perturbation is small such that the matrix in Eq. (21) is positive definite when t = co. Please refer to Appendix E.2 for further discussion when the perturbation is large.
In conclusion, the analysis in this section suggests novel AT degeneration phenomenon that in a long-term AT, the impact brought by AT will graduate disappear and the adversarially trained DNN will eventually degenerate to that obtained without AT. The AT degeneration phenomenon clearly illustrates the mechanism behind robust overfitting in DNNs. It can also explain the empirical finding in Rice et al. (2020) that early-stop can significantly mitigate robust overfitting: it is because early- stop can effectively preserve the regularization matrix E(I) brought by AT.
5.2 INFINITE WIDTH ADVERSARIAL TRAINING
We have known that the robustness brought by AT can be characterized by E(!) defined in Theo- rem 3. Then, it is natural to ask if one can directly optimize É(t) to mitigate robust overfitting. Since
7

---

Published as a conference paper at ICLR 2024
Algorithm 1 Adv-NTK (Solving Eq. (25) with SGD and GradNorm)
Input: Training set D, validation set size Mvai, learning rate Ç, training iteration T, PGD function for finding adversarial validation data.
Output: An infinite-we wiith adversarially robust DNN.
1: Randomly separate D into subsets Dopt and Dval such that [Dvall = Myal-
2: Initialize trainable parameter wo E I Paoueel with zeros.
3: for in 1,... .T' do
4: Sample a minibatch (ær, y) ~ Dval.
5: x' < PGD(z. fwr
Finding adversarial validation examples.
6: 9t - 0=2 (x') y11
7: We f- 111 S llsella
D Update model parameter via SGD and fg-GardNorm.
8: end for
9: return FFr
(()) is a Mc x Mc block diagonal matrix, optimizing it requires maintaining Mc² variables and computationally costly. Fortunately, Corollary indicates that in the infinite-width limit, matrix E(t) will converge a diagonal matrix E(t) where only Mc variables need be maintained. Based on the observation, we propose Adv-NTK, the first AT algorithm for wiith DNNs.
Specifically, for a given training set D, we separate it into disjoint subsets Popt and Dvals in which Dopt is for constructing the infinite width DNN while Dval is validation set for model selection. Then, the infinite-widte DNN that will be trained in Adv-NTK constructed follows based on the infinite-wide width DNN defined as Eq. (4) in Corollary 1,
for (z) = Og(x, Xopt) ' (Xopt, Xopt) (1 (1-
-yp (Xops (Nops: (iug(=)) 'opt
Vz E X, (24)
where E Poyel is the trainable parameter in Adv-NTK, Og is the NTK function the infinite-
width limit (see Theorem 1), and Xopt and y opt are concatenations features and labels in the subset Dopt- Note that the parameter w consists exactly of the diagonal entries of the diagonal matrix Ett). Then, the Adv-NTK algorithm aims to enhance the adversarial robustness of the infinite-width DNN Io via solving the following minimax optimization problem,
min
Σ
max 10'= =lf v112.
(25)
(a.y)EDeoll
where p > 0 is the same adversarial perturbation radius as that in the standard AT (see Eq. (1)), and the inner maximization problem can be solved via projected gradient descent (PGD) (Madry et al., 20. The above Fq. (25) shares similar idea with the early stop method (Rice et al., 2020): they both bust accuracy on the validation set as an indicator to select the model parameter indirectly, while Eq. (25) directly optimizes the model parameter with the validation set. Finally, to further improve the training stability, Adv-NTK leverages stochastic gradient descent (SGD) and gradient normal- ization (GradNorm) to solve Eq. (25). The overall procedures are presented as Algorithm
validation set for model selection. The difference is that early stop uses model
EMPIRICAL ANALYSIS OF ADV-NTK
This section empirically verifies the effectiveness of Ady-NTK on the CIFAR-10 10 (Krizhevsky et al., 2009) dataset. We briefly introduce the experiment and leave details in Appendix Please also refer to Appendix F.4 for analogous experiments SVHN (Netzer et al., 201 dataset.
Loss & Dataset & adversarial perturbation. Squared loss C(f(x),) y) == 1 [=x) v1l -113 used in all experiments. In every experiment, randomly draw 12, 000 samples from the trainset for model training and use the whole test set to evaluate the robust generalization ability the model. Projected gradient descent (PGD; Madry al. (2018)) is used to perform adversarial perturbations in both training and evaluation. We adopt foc perturbaaioo with radius E {4/255, 8/2 8/255).
Baseline methods. We adopt two existing methods for comparison. They (1) AT, which aims to enhance the robustness finite-width DNNs via solving the minimax problem in Eq. (I), and (2) NTK, which directly obtains closed-form infinite-width DNNs from Eq. (4) without training.
8

---

Published as a conference paper at ICLR 2024
Table 1: Robust test aceuracy (%) of models trained with different methods on CIFAR-IO. Every
experiment is repeated 3 times. A high robust test accuracy suggests a strong robust generalizability.
Adv. Ace. (loci P 4/ 4/255) (%)
Adv. Ace. (exi p 8 8/255)(9)
Depth
AT
NTK
Adv-NTK (Ours)
AT
NTK
Adv-NTK (Ours)
MLP-x
3
30.64:10.42
9.93::0.19
27.35:::006
26.93:10.07
2.82
23.45::0.80
4
30.35-+0.09
13.67+00.20
28.47-00.22
26.44:-0.39
3.61=0.09
23.01=0.24
5
28.70=t0.45
16.2420.26
29,04=00338
21,05:00,21
4.74=0.43
21.90=0.60
CHFAR-10
(Subset 12K)
8
10.00:1:0.00
22.44:10.27
30.56:10.48
10.00:1..00
8.23=0015
0.72
10.00:1:0.00
24.47.10.37
30.91:10.12
10.00:1:.000
10.04:1:.25
2..21
18.29:1:.40
5.011:0.54
29.31-:0.61
12.62:1:.78
1.31
26.79: 2.25
CNN-x
4
19.30=+0.26
6,23+00.69
0,55=00555
10,39+0.200
1.68=0.14
0,55
CIFAR-10 10
5
20.10::1.32
0.99+:0.37
0.,46:10.59
11.12::0.14
1.65
23.48
(Suhset 12K)
12.68 14.64
10.26
28.26
0.54
10.00.10.00
2.55
16.14:1 0.83
10
10.00=00.00
16.02.+0.50
26.61 0.44
10.00:::.00
3.50
13.13=0022
1Un5 0.4 328, pa 4255
MUPS CPAR-25 (5stee) 1251 p-82253
CWN5 O1AP-33 120) pa0235
OWS5
8230
MTS
VIX
NTS
216
1500 1300E
250
50.0
18800 1000
2001
582
18800 1500 Takkngg Berdoi
2000
5000 1100E
25030
Figure 1: The robust test accuracy curves of finite-width MLP-5/CNN-5 along AT on CIFAR-10. The robust test accuracy of infinite width DNNs learned by NTK and Adv-NTK are also plotted.
Model architectures. We study two types of multi-layer DNNS, MLPs and CNNs. Although theory is originally for MIPs, can be generalized for CNNs. We use "MLP-x" and "CNN-x" to denote an MLP consisting of fully-connected (FC) layers and CNN consists æ convolutional layers and one FC layer, respectively. The architecture depth x is choosen from the set {3, 4, 5, 8, 10).
Model training. For Adv-NTK, we use 10, 000 data construct the infinite-width DNN defined in Eq. (24) and 2, 000 data as the validation data for model training. For AT, we use the overall 12, 000 data to train the model following Eq. (I). For NTK, there is no need for model training and we use the overall 12, 000 data to construct the closed-form infinite-width width DNN defined in Eq. (4).
Results. The robust test accuracy of models trained with different methods on CIFAR-10 10 is reported in Table 1. We have two observations: Firstly, Adv-NTK achieves significantly higher robust test accuracy than NTK in almost every experiment, which suggests that Adv-NTK can improve the robustness of widhh DNNs and E(t) indeed captures robustness brought by AT. Secondly, in some experiments, Adv-NTK achieves higher performance than AT, which suggests that Adv-NTK has the potential be used an empirical tool to study adversarial robustness. In summary, these results not only indicate the effectiveness of our algorithm but also justify our theoretical findings.
We further plot the curves of robust test accuracy of finite-width DNNs along AT, as shown in Fig. 1. We have two observations: Firstly, in most of the cases, the robust test accuracy will first rapidly increase and then slowly decrease, which illustrates clear robust overfitting phenomenon. Similar results with larger models and longer AT can also be found in Rice et al. (2020). Secondly, although higher performance than the final model obtained by AT,
Ady-NTK can achieve comparable could not beat the best model during AT. we deduce that it is because the non non-linearity of finite-width DNNs in AT can capture additional robustness, which will be left for future studies.
CONCLUSIONS
This paper presents a novel theoretical analysis of the robust overfitting of DNNs. By extending the NTK theory, we proved that a wide DNN in AT can be strictly approximated by its linearized coun- terpart, and also calculated the closed-form AT dynamics of the linearized DNN when the squared loss is used. Based on our theory, we suggested analyzing robust overfitting of DNNs with the closed-form AT dynamics of linearized DNNs and revealed a novel AT degeneration phenomenon that DNN in long-term AT will gradually degenerate to that obtained without AT. Further, de- signed the first AT algorithm for fiinite-width DNNs, named Adv-NTK, by directly optimizing the regularization brought by AT. Empirical studies verified the effectiveness of our proposed method.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
Di Wang and Shaopeng Fu are supported in part by the baseline funding BAS/I/1689-01-01, funding from the CRG grand URE/114663001-01 FCC/1/1976-9-001 from CBRC, and funding from the AI Initiative RE1/I/481 1-10-01 of King Abdullah University of Science and Technology (KAUST). They are also supported by the funding of the SDAIA -AUST Center of Excellence Data Science and Artificial Intelligence EDAIA-KAUST Al).
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- paramcterization. International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances Neural Information Processing Systems, 32, 2019.
Daniel Barzilai, Amnon Geifman, Meirav Galun, and Ronen Basri. A kernel perspective of skip connections in convolutional networks. In International Conference on Learning Representations, 2023.
Richard Bellman. The stability of solutions of linear differential equations. Duke Math. J., 10(1): 643-647, 1943.
Simone Bombari, Shayan Kiyani, and Marco Mondelli. Beyond the universal law of robustness: Sharper laws for random features and neural tangent kemnlss. In International Conference on Machine Learning, volume 202, pp. 2738-2776. PMLR, 2023.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Minn and Qiao Zhang. JAX: Composable transformations of Python+NumPy programs, 2018. URL http:
//github com/ google jax..
Sebastien Bubeck, Yuanzhi Li, and Dheeraj M Nagaraj. law of robustness for two-layers neural networks. In Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 804-820. PMLR, 2021.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang. Robust overfitiig may be mitigated by properly learned smoothening. In International Conference on Learning Representations, 2021.
Zixiang Chen, Yuan Cao, Quanquan Gu and Tong Zhang. A generalized neural tangent kernel analysis for twoelayer neural networks. Advances in Neural Information Processing Systems, 33: 13363-13373, 2020.
Jacob Clarysse, Julia Hörmmann, and Fanny Yang. Why adversarial training can hurt robust accuracy. In International Conference on Learning Representations, 2023.
Konstantin Donhauser, Alexandru Tifrea, Michael Aerni, Reinhard Heckel, and Fanny Yang. Inter- polation can hurt robust generalization even when there is no noise. Advances in Neural Informa- tion Processing Systems, 34:23465-23477 2021.
Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels, Advances in Neural Information Processing Systems, 32, 2019a
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes wwertearamteriize neural networks. In International Conference on Learning Representations, 2019b.
10

---

Published as a conference paper at ICLR 2024
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsich, Liwei Wang, and Jason D Lee. Convergence of adversarial training in overparametrized neural networks. Advances Neural Information Processing Systems, 32, 2019.
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
Thomas Hakon Gronwall. Note on the derivatives with respect a parameter of the solutions of system of differential equations. Annals of Mathematics, pp. 292-296, 1919.
Insu Han, Amir Zandieh, Jaehoon Lee, Roman Novak, Lechao Xiao, and Amin Karbasi. Fast neural kernel embeddings for general activations. In Advances in Neural Information Processing Systems, 2022.
Hamed Hassani and Adel Javanmard. The curse overparametrization in adversarial train- ing: Precise analysis of robust generalization for random features regression. arXiv preprint arXiv:2201.051433 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Roger A. Horn and Charles R. Johnson. Topics in Matrix Analysis. Cambridge University Press, 1991. ISBN 978051184009 184071. doi: 10. 10.1017/CB0978051 1840371.
Jiri Hron, Yasaman Bahri, Jascha Sohl-Dickstein, and Roman Novak. Infinite attention: NNGP and NTK for deep attention networks. In International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4376 4386. PMLR, 13 18 Jul 2020.
Wei Hu, Zhiyuan Li, and Dingli Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. In International Conference Learning Rep- resentations, 2020.
Kaixuan Huang, Yuqing Wang, Molei Tao, and Tuo Zhao. Why do deep residual networks gener- alize better than deep feedforward networks? neural tangent kernel perspective. Advances in Neural Information Processing Systems, 33:2698 2709, 2020.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and gener- alization in neural networks. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Jianfa Lai, Zixiong Yu, Songtao Tian, and Qian Lin. Generalization ability of wide residual net- works. arXiv preprint arXiv: 2023.
J LaSalle. Uniqueness theorems and successive approximations. Annals of Mathematics, pp. 722- 730, 1949.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak. Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems, volume 32, 2019.
Jongmin Lee, Joo Young Choi, Ernest Ryu, and Albert No. Neural tangent kernel analysis of deep narrow neural networks. In International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 12282-12351. PMLR, 2022.
Binghui Li and Yuanzhi Li. Why clean generalization and robust overfitting both happen in adver- sarial training. arXiv preprint 0012:22306.11271,,00 2023.
Lin Li and Michael W. Spratling. Data augmentation alone can improve adversarial training. In International Conference Learning Representations, 2023.
11

---

Published as a conference paper at ICLR 2024
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances in Neural Information Processing Systems, 31, 2018.
Noel Loo, Ramin Hasani, Alexander Amini, and Daniela Rus. Evolution of neural tangent kemelss under benign and adversarial training. In Advances in Neural Information Processing Systems, 2022.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In Infernational Conference on Learning Representations, 2018.
Yifei Min, Lin Chen, and Amin Karbasi. The curious of adversarially robust models: More data can help, double descend, or hurt generalization. In Conference on Uncertainty in Artificial Intelligence, volume 161, pp. 129-139. PMLR, 2021.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. In Proceedings of the NIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Roman Novak, Lechao Xiao. Yasaman Bahri. Jachoon Lee, Greg Yang, Daniel Abolafia, Jeffrey Pennington, and Jascha Sohl-dickstein. Bayesian deep convolutional networks with many chan- nels are Gaussian processes. International Conference on Learning Representations, 2019.
Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein and Samuel S. Schoenholz. Neural Tangents: Fast and easy infinite neural networks in Python. In International Conference on Learning Representations, 2020. URL https: / / thub. com/
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, volume 32, 2019.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In International Conference Machine Learning, pp. 8093-8104. PMLR, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556. 2014.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXhv:1312.6199, 2013.
Nikolaos Tsilivis and Julia Kempe. What can the neural tangent kernel tell us about adversarial robustness? In Advances in Neural Information Processing Systems, 2022.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 1rX1v:1011.3027, 2010.
Yunjuan Wang, Enayat Ullah, Poorya Mianjy, and Raman Arora. Adversarial robustness is at odds with lazy training. Advances in Neural Information Processing Systems, 35:6505-66 6516, 2022.
Dongxian Wu, Shu-Tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust gener- alization. Advances in Neural Information Processing Systems, 0122988-2969 2020.
Lechao Xiao, Jeffrey Pennington, and Samuel Schoenholz. Disentangling trainability and general- ization in deep neural networks. In International Conference Machine Learning, pp. 10462- 10472. PMLR, 2020.
Chaojian Yu, Bo Han, Li Shen, Jun Yu, Chen Gong, Mingming Gong, and Tongliang Liu. Under- standing robust overfitting of adversarial training and beyond. In International Conference on Machine Learning, pp. 25595-256100 PMLR, 2022.
12

---

Published as a conference paper at ICLR 2024
Jingfeng Zhang, Jianing Zhu, Gang Niu, Bo Han, Masashi Sugiyama, and Mohan Kankanhalli. Geometry- aware instance-rewee reweehhhe adversarial training. International Conference on Learn ing Representations, 2021.
Teng Zhang and Kang Li. Understanding overfitting in adversarial training in kernel regression. arXiv preprint arXiv:2304.06326. 2023.
Yi Zhang, Orestis Plevrakis, Simon S Du, Xingguo Li, Zhao Song, and Sanjeev Arora. Over- parameterized adversarial training: An analysis overcoming the curse of dimensionality. Ad- vances in Neural Information Processing Systems, 53:679-688, 2020.
Zhenyu Zhu, Fanghui Liu, Grigorios Chrysos, and Volkan Cevher. Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization). In Advances in Neural Information Processing Systems, 2022.
Difan Zou, Yuan Cao. Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep ReLU networks. Machine Learning, 109:467-492, 2020.
13

---

Published as a conference paper at ICLR 2024
A
PRELIMINARIES
A.1 ADDITIONAL ASSUMPTIONS AND NOTATIONS
To avoid technicalities, we assume that all functions are differentiable throughout this paper. Fur- thermore, the order of differentiation and integration is assumed to be interchangeable.
A.2 NOTATIONS
This section presents the full list of notations.
Table 2: List of notations.
Notations
Descriptions
Concatenation.
Kronecker product.
D-ag(.)
A diagonal matrix constructed from given input.
Vec(-)
Vectorization function.
fxf(x)
A m x n Jacobian matrix of the function, f f RR + R
Amax (-)
The maximum eigenvalue of given matrix.
Convergence in probability. See Definition A.3
Op()
Big O notation in probability. See Definition A.4.
In
An identity matrix.
O,
An n-dimensional all-zero vector.
1n
An n-dimensional all-one vector. An integer set {1,2. ... ,...
[n]]
[
An integer set {4, / +, 1,....,..
The overall training time.
s
The overall time usage for searching adversarial examples in each training step.
w
Weight matrix in the I-th layer at the training time
(
bias vector in the 1-th layer at the training time t. Pre-activated output function in the I-th layer at the training time t.
bg
Post-activated output function in the I-th layer at the training time f.
6
Empirical NTK at the training time t.
Óz,t
Empirical ARK at the training time t.
+
Converged NTK in the infinite width limit. Converged ARK in the infinite width limit. +
A.3 DEFINITIONS
This section collects definitions that are omitted from the main text.
Definition A.1 (Lipschitz continuity). A function f R R is called K --pisschitz continuous if K/ x') holds for any x and x' from the domain of J. When f is differentiable, further have [0)[()) < K holds for any from the domuin of J-
[(x)) S K
Definition A.2 (Lipschitz smoothness). A differentiable function f R Th. is called K K-Lipschitz smooth if (x) 0, (x')) S K x'| holds for any and x' from the domain of J. When f is twice-differentie
we further have (0.f(z)) K holds for any x from the domain of f.
Definition A.3 (Convergence in probability). For a set of random variables X,, indexed by and an additional random variable X, we say X,, converges in probability to X, written by X,, P. X, if lf P([X, X > e) foror any >
14

---

Published as a conference paper at ICLR 2024
Definition A.4 (Op(-); Big O notation in probability). For sets of random variables Xn and Y indexed by n, we say X2 = (Y())) as n + oo if for any ő > 0, there exists a finite & > and a finite N N+ such that P( Yul > E) < 6. vn N.
A.4 TECHNICAL LEMMAS
This section presents several technical lemmas that will be used in our proofs.
We first present a result that enables the efficient calculation of Kronecker products.
Lemma A.1 (c.f. Lemma 4.2.15 in Horn & Johnson (1991)). Suppose real matrices A and B have singular value decompositions = E, VT and B = U2 V22 Let rı = Rank(A) A) and r2 = Rank( B). Then, A s (U1 U2) (E Eg) (Vi & V2) V2)² The nonzero singular values of A @ B are the T172 positive numbers (Ax(A)))(B) :1 denotes the i-th largest singular value (including multiplicities) of a given matrix.
TI, S S r2), where Xc(-)
Corollary A.1 (62-Norm of Kronecker Product). For any real matrices A and B. we have that || & B B = ||A/|2 BB]|
Proof. According Lemma A.I, we have ||A @ BI2 >max(A) Amax (B) ||A||2 B
We then introduce two Grönwall-ty inequalities.
Lemma A.2 (Grönwall's Inequality (Gronwall, 1919; Bellman, 1943)). Let u(t) and f(t) be non- negative continuous functioons defined on the interval (a, b] that satisfies
( S A+ S u(s)s{s)ds,
VI [a, b],
then
u())= < A exp ( ([[Jao)s)) VI E [a,b].
Lemma A.3 (Adapted from Lemma in LaSalle (1949)). Suppose that
1. g(x) is non-negative function defined on the interval [0, a).
2. u(z) is function such that Sed u(f)dt exists for all E [0,
3. (ax) is a positive, non-decreasing continuous function defined on [0, +00), and the integral
dt exists for any x E [0, +oc), F(x) = Jo- f(t)
4. The inequality g(x) S So u(t)s(g(()dd holds for all x E [0, a).
Then we have
F(g(z)) S J u(()dt, Yo E [).
Also, we need the following Lemma bound the norms of Gaussian random matrices.
Lemma A.4 (c.f. Corollary 5.35, Vershynin (2010)). Let be an N matrix whose entries
independent standard normal random variables. Then for every t 2 0. with probability at least 1 1x2ppp-12/220 one has
-n-t Amin(A) S Amax (A) NN V
where \min(A) is the minimal eigenvalue of and Amax (A) the maximal eigenvalue of
Finally, prove the following convergence in probability result for centered Gaussian variables.
a² Lemma A.5. Suppose Y,. mmx{ Xn,2l, X. where Xn,s NNO,, and and v 0 constants. Then, have Y, Eg 0.
15

---

Published as a conference paper at ICLR 2024
Proof. For any Xn, and O, we have
100
n
n2
P( > =
=2
0V 2n
exp
2
dæ
Vn
n"
xx
2
exp
dr
C Ov 2m
2
-V20
n"
exp
VI
20
220
n²
exp
VN'TC
20
which means
V20
n²
>6)21
TE
exp
2n²²
Therefore,
220
n
P(Y, s|
P([Xm.il s,, 2
exp
VnLTe
2n²
Since lim,
22 Vn"
exp
n"
20
thus have
V20
n
lim IPYY,, > = 1
lim
exp
2-000
11
20
exp(
n",2
.m
1 lim
n
0,
which indicates Y, E 0.
The proof is completed.
B PROOF THEOREM
This section presents the proof of Theorem 1.
We first introduce the following Lemma B.
Lemma B.1 (Proposition in Jacot et al. (2018)). As the network widths no. nr, + 00 se- quentially, the outpul functions 1!11 for -,...., n the 1-th layer lend to centered Gaussian processes of covariance 200, where ()) is defined recursively by:
oi (x, lim RT x' o%. no noc no
)(+1) (x, oiy cP ( oi,
where GP ) denotes centered Gaussian process with covariance (
Then, Theorem 1 proved as the following Theorem B.I.
Theorem B.1 (Kemels limits at initialization; Formal version of Theorem 1). Let @ and 6())
denote the empirical NTK and ARK in the 1-th layer. Then, for any x,, x! X, have that:
16

---

Published as a conference paper at ICLR 2024
1. (Theorem I in Jacot et al. (2018)) For any 1 1
lim
lim 0g (x) (0) - I
where 0% sively as follows,
X x X _ IR is a deterministic kernel function that can be defined recur-
_xTx x' 1, 00 (x, lim
no n00 no
(1+1) (x,z') = ow 00 (I, ".r,2"")-BxeP(0... (d + 10l==ppo0xx000((())001)001 +1.
2. For any < 1 < L+L
00.00 (x,,)) Inc. lim 6 200 (x, (;,)) 000
lim
+000
where O Oz.(0) X' x X + R is a deterministic kernel function that can be defined recur-
sively as follows,
(0 (x, = ov:
(z. (I, x') ow (z,000) 1
Proof. The first proposition, i.e., the NTK limit at initialization, has been proved by Jacot et al. (2018). Thus the remaining task to prove the ARK limit at initialization, which is done through mathematical induction.
Specifically, for the base case where for the i-th row and i'thh column entry of the ARK matrix (00 (z, x²), we have that
1 an
W W(l)
$
25500
n1g
Since each ((1) $... is drawn from the Gaussian (O0, ow ). we have
lim Ony (2) = ||-11 ow || 0 (x. ng 100
which indicates
lim Q xx,)) oiy Ing (00,(10) In.
For the induction step, suppose the lemma already holds for the 1-th layer and we aim to prove also holds for the (1 1)-th layer. For the ARK matrix @((+1) (z, x²), we have that
lim lim
(x, (1,t))x,x))) 2').
2.0
a0-000 no0
lim
1
Σ
lim
lim 20 20)s)) Ope (1+1)
h (x); (x)x)()) anor(e), ho (x))
70 ni
10000
ISi.' Sm
lim
Σ
リ= 0 (z, od) w!th Wejo Φ (1 (z)g) W & 2'hh (1))))))))
n0 Ni
151 m
Induction hypothesis
lim
Σ 0 (2,0)) with (z),)
(z)z) w o 8(hh (x')))
200
18i5
17

---

Published as a conference paper at ICLR 2024
By Lemma B.I, No0 (-)x converges the centered Gaussian process GP(O, ) which further indicates
θ ( (1,
lim
lim
00 . 2'1100 (x), W w 2'(h0 0 (z')s
lim
10000 11 15
= [i-i ow 1000000 (x) LE (()
= [-r (c.1(1+1) x').
As result,
lim lim " (x,xx) -0 (2.
x') Ins.
no +00
which justifies the induction step. The proof is completed.
C PROOF OF THEOREM 2
This section presents the proof of Theorem 2.
C.I PROOF SKELETON
The Proof idea of Theorem inspired by that Jacot et al. (2018). Specifically, we will first extend the result of Theorem B. and show that the empirical NTK Op,, and empirical ARK θz, during AT also converge to the same deterministic kernels as that in Theorem B.I. These results stated as Theorems C.I. C.2 and presented as follows:
Theorem C.1. Suppose Assumptions 1, 2, 3 hold. Then, if there exists E N+ such that min [no, ... ] 2 n, we have ñ +
lim lim my 100
sup no no0 =E
||0,,(xx,,0) X1,0) 0g(x, P, 0,
lim lim
sup
||0,, (X),0) Xt,,) (x, P 0,
ny +00 no m00 sE))))
where
Op(x, = 0/ (x, x) & Inzti!
Og (xx == Diag @ (21, .0 ,0 (IM, Intts.
Theorem C.2. Suppose Assumptions 1, 2, 3 hold. Then, if there exists ñ E N+ such that
(no. ... ,,, 2 n, we have for any E X. as + 00,
lim lim
sup =
xx,)) 00,,) F 0.
400 no 700
lim
lim
sup
(6, - f 0,
n10000
where
O0(2, x) 0 (x, x) & Ingia
O₂ (2, x) = Diag(Daggg O0 (t, 0 (2, (M, @ Incis.
Based the kernels convergences during AT, then prove the final Theorem which show that the adversarially trained DNN fi is equivalent to the linearized DNN flin. Compared with Jacot al. (2018), the main technical challenge in our proof arises from bounding terms that involve adversarial examples such as Xt,s, 0,x,,.. 0 (xr,s)-
The rest of this section is organized follows:
18

---

Published as a conference paper at ICLR 2024
1. In Appendix C.2, prove that as the widths of fr become infinite, its parameters and outputs will converge to those at the imitial of AT by properly rescaling.
2. In Appendix C.3, we prove Theorems C. and C.2 that the infinite-widths limit, the NTK and ARK in AT will converge to deterministic kernel functions. The proofs are based on the results in Appendix C.2.
3. Finally, in Appendix C.4 we prove Theorem 2 that in the infinite-widthy limit, ft is equiv- alent flin. The proof is based on Theorems C.I and C.2.
C.2 CONVERGENCES OF PARAMETERS AND OUTPUTS UNDER RESCALING
The goal of this section is to prove Lemma C.5, which indicates that by properly rescaling, for the wide DNN fi. its parameter (( pre-activation z! (xx,9), and post-activation h (xr,s) in each layer can converge to those at the initialization of AT.
Firstly, we let
Poly, Poly (
(vTL-1 (
[ (x,,s Vni
Vni 1 (xx, (xx,s))la)
1
denote any deterministic polynomial with finite degree and finite positive constant coefficients, and depends only on terms
アーー W| lla (where E [L L + I), tuu (x,,5)l2 (x,,)) (where
I E [1 L)), and 1 Vnu || (
(xt,s)ll2 (where (1 L).
From the definition of Poly,, the following properties worth highlighting:
The sum of any two (different) such type polynomials is also such type polynomial: Poly, + Poly, Poly.-
The product of any two (different) such type polynomials is also such type polynomial:
Poly, Poly, Poly,-
With the definition of Poly,, we then bound [|0,w( (9) |2, |10ch (x1,s) and ||0,z (1) (x.,s) 112, as shown in the following Lemmas C.I, C.2, C.3, C.4.
Lemma C.1. Suppose Assumption I holds. Then for every S L+ and & E [0, (1, we have 1a. ll2, |,,,("//, ||0,6("112 < Poly, ([x
Proof. By the fact that || ll2 $ [|,, we have la,w!"' lla I ( 1
T Vwe (L+1) (x,,) ((f
h
| (w h
(L+1) (x..s sl2
C(f (1x
By applying Lipschitz activation Assumption and Corollary A.I.
[10ve (L+1)
(x2.))ll2
1.
0 (x)
(1++1) (212
(1 (10 ( - sx1 (xx.))l
F=1
(11)
K V 1 (1 Fa (( 2 In
IM
m
L
< -1+1
(w(('+2)
1 (anss)) ((M(ss))))
Vnr
Vni
< Poly.
x (1) (x1,,)))))) , (TMM
= -Poly,
|!=(() (xt.s))le 1 = -Poly
/nl
19

---

Published as a conference paper at ICLR 2024
where (InLs)) T x!l) (IiL.s) (IJu,s). Combining the above results, we therefore have
20 (I)..s) is a M x M matrix such that its i-th row and j-th column entry
10, 112 Poly. 100(())))0000000) (0
For |10,bellz. we similarly have that
||0,6," (0)) la 11 h (1+1) (xx,s) (((
1 (1)
(x,,))ll2 (00 (1+1)) (x,,s)ll2 (100(/
a @ Im 1l2 (0) 1 (x,s))
S VM Poly, ((((xss))))
Poly, ((xx,))
The proof is completed.
Lemma C.2. Suppose Assumptions 2, hold. Then for any E [0, as (on oc, we have that
| (xx,,))) x00 (x1 2 5p(1) -Pooy)
sup [00.5
where 0 SIS T..
Proof. By Assumption 3, (t) is continuous on the closed interval [0, 2], which indicates there exists constant such that suPtejo,r] [1)[a S C.
Then, when / 0, according to definition, have
|s 2 )dr S i / ||a,=ح) (xt, ll2d7
sup 800
Xt.s1 X1.
sup 00.55
< [|n(t))le 100 |1axh! (x (x (x0 L(fe (xt, ).y) 12
SC. f ((an( (((
By applying Lipschitz activation Assumption 1,
sup rE(D.S) 1
(I++1) (x1,
{
II 110 (n (x) (1'+1) (x2. (10 11) (X2x))ll)) (xx=)))) P=1
< sup rE(o.S]
L
[[(((++])
1|2 x)
1
(w 1|2 Poly.
(C.1)
Vno
Combining with Assumption 2,
/ (1 [E(O,T]
sup
||x - Xx, 5 C. PPly, sup
81 $,,
Poly, (1).
(C.2)
20

---

Published as a conference paper at ICLR 2024
On the other hand, for any 1 1 L, by again using Assumption
sup | (xt,,) ) xt (xt,s)))2 sup
1 11) (X),)) o(he (x1,s)))l2
e1.e2E[0.5]
|1/ (xt.x))) 1// (x
K
sup
01.52E
$ SK.
81 (0,05 W 12
sup
|| | (xt,,t) - 21 11-11 11 122
= =Poly, sup
1111) (X
(1-1) (xt,
1t
$1.02E[0,S]
.... Poly.
sup
20] (0) (x).e)) - xz (0)
(x12,1)l12
< Poly, Poly, Op(1) Op(1) Poly..
The proof is completed.
any Lemma C.3. Suppose Assumptions 1, 2, 3 hold. Then, as minig]o:z((m) + for any E [0,
we uniformly have that
|0,5r, S (xx((O(()) Poly,) Op(1) PPly, (100)00 =E(0.S]
sup
Proof. By Assumption 3, both (t) and (t) are continuous on the closed interval [0,T], which (t)l() indicates there exists a constant C' such that suPre (1) S C.
Then, by assuming differentiation and integration to be interchangeable, for any [0, S). we have
1 2l2 = 0. /'" 2f (x+t)) n(t) (
< L/ 0c ((tttt (Xt,)) (t)= orxx [(fe(((())))))))))))))))))()))) || dr
3r0 Oxhi (1+1)) (xe,)) 0,101, -C. 1o [10r))
< sup rE(o.8)
00
+ +C. +c.ol
E0xe. (xx,)) Oxhi (1+1)) (xx,)) 100.00xxx1 0/ (1
|1gct (L+1)
(x2 12.- -. [100ss
sup rE(S.)] 111, bounded by Fq. (C.1)
(x, 112 C. / (1
sup rE(0 I11r, bounded by Bq. (C.1)
|0gh (L+1)
(C.3)
where [-], denotes the i-th entry of given vector. In the above Eq. (C.3), the term III, can be bounded by Eq. (C.1) from the proof of Lemma C.2. Thereby, the remaining task is to first bound terms and II, respectively, and then bound the overall supxejo.s) ||
Stage I: Bounding term I in Eq. (C.3).
21

---

Published as a conference paper at ICLR 2024
By Assumption 1, have
Σ 110, 200,, Oxhi (1+1) ( (xe..)) Or(0r];
4. sup rE[0,9]
Σ (vec(Wo)).00
πI
o aan (x) 1 (1++1)
(xx,=) (xe,)) Ozhi ( (xx.)) a. (V (120)
sup rE[o.5]
1
II 11 (x) (1++1) (l2 - 2x (xe,) O (Vec(W,) (, 66 I'=L
< sup re(0.8]
sup + Poly,
II
10 (x0 hi -1" (xx,, ( 0000 (1'+1) (xx,)) O (Vcc(W!""),
rE(0.9]
iSP+ 1"
L+1
<ooly,"
Veo W!O a (ee(W,
I=1 1--1
+ -Poly,
sup | [[ Diaglø'( ( r[
(x)+))) ). (C.4)
1=1
(2)
12.00
For the term T. according to Lemma C.1, for I+1,+
[ |W;" l12 I Poly, (xxx,)))
(C.5)
Besides, the term 1 can be expanded as below,
(2) sup |1 bo0 Diaggd Diag(o' (h( (xx+))) de (Vec(W)))) 6,6l))12
rE[0,S]
< sup [[Qvee(W()).o o' (1) (xx,))) de (Ve)((W)))) ( )l2
rE(0.S)
(xx,)) [10 (h (x1+ || (100 (x a (Voc(W(""), b("))22
sup rE(0.S]
||o" (h!") ()), 110 ( (x1 (1
( (xerr a Vec(W. Il2 + 11,,0 (2)(((xx))))))) (xx,)) 0,bl" l
(1))
sup re(0.8]
(1 "
K ..PPll Poly, rE(O.S]
sup
(I),,))" + (1 (2 @ 4n112 |0, |eoVee )12 + [|LM & mm 110.61011 1|2
< <Poly, sup TE(O,8]
1
|| (1-1) )22 Poly, 110 ((f( + Poly, 10 (X,,
vn--1
Lomma
Lemma
< Poly,
sup rE[0.S]
1
| (1-1)
112 1122+1 +1).
(x,,r
(C.6)
/
22

---

Published as a conference paper at ICLR 2024
where (sz (1-1) (1i (T. It
(1-1) (Ijj,))) denotes M M matrix that its i-th row and j-th column (Iz,1,7). ). By Lemma C.2, we further have
entry is 2
(11,) )"r at
(1-1)
(1-1) (xt,) (xo,))la++
sup rE(0.S]
sit
T4-1
1
|| (1-1))
(x,, (xx,))) + || ||r2--11 (xe,)) - 2. 101 ((x,,))ll2 + +1)
s sup rE(0.S]
Vm--1
=Poly,
1
sup rE(O,S]
|| ||a2--11
( 11-1) (xx,-) - It (1-1) (xc,))l
(1 Op(1)
- Poly, + Vn=- (p() Poly,
Poly.
(C.7)
/m-1)
Lemma C.2
Combining, Eqs. (C.6) and (C.7), the term 2.1 can then be bounded follows,
((2) L1l
1+
0₂(1)
Poly, ((ixx)))
< Op()) Poly, (10 (()r(((())))))))))))))))))))))))
(C.8)
Finally, by inserting Eqs. (C.5) and (C.8) into Eq. (C.4), we have
4 S (p()) Poly, ((((
(C.9)
Stage 2: Bounding term II in Eq. (C.3).
We expand the term follows,
11.r-
Σ 0p
1 (xee.) Oe (x
Oxin
10 (1++1) (x..)) axhi (1) (se..)) (xe.))
1=L
|1ach!
(xx,r)
Σ
(0) (l' (xc,))) 10x. (x) ((++)((x(,))
(1 8,x,, ll2
s Poly, 11xx, Diag( (1 (1) (x,=))) 0,x1-112-
Since
1|0x,- Diag(ø' (h (1)
(x). 0,xi,112
110x,, o' (hh (1) (xx,)) 01x1,7112
1-1
< (1)) (112 II (10 (1'+1) (x1,-)ll2 1|xx,, 1 (x),)) -,x1,
$ Poly, 11xx,, hi (xx,,)ll2 ||0,x,, ll2 Poly, 110xx,,112
therefore, 1lrr is eventually bounded below.
I1,r Poly, Poly, ||0 |||
Poly, 110,xx,,112.
(C.10)
Stage 3: Bounding the original ||0, via the Grönwall's inequality (see Lemma A.2).
23

---

Published as a conference paper at ICLR 2024
By inserting Eqs. (C.1), (C.9) and (C.10) into Eq. (C.3) and applying Assumption 2, we have that for every s E S].
||0,x,,el2 Op(1) Poly, 1100:// Polyy - C. .. ||0xx,,112
+ Poly, C. -,0(())+++ Poly, C. Op(1)
< <Poly [ 110rxe,r12 (10 ((f 2dr + Op(1) Poly,
1).
Note that both | ll2 and (x] (f (x.,)) y))l2 are non non-negative functions with respect to on the interval S). Therefore, by applying Grönwall's inequality (Lemma A.2), we have
Poly: [ (1 O1p(1 Poly, (f0xs))(((((xss))))) + + cxp(Op(1) Poly,) Op(1) Poly, (110 ((f()))) 11.
< exp
The proof is completed.
Lemma C.4. Suppose Assumptions and hold. Then, for every E [0, 21, we have that
||0, (0)) (x2; ||0,xt (2) (x)("=)((xs))) (xt,s)lla S Poly. (10)ss) + (10xxt,sl2))
where 4 [1:L+ L 1] and l2 E [1 L].
Proof. For [1a,h (11) (xt,s) 12. when 4 = 1, by applying Assumption and Lemma C.I, we have that | (1) ( (xx,s)l2=
Vmo (w!!) x1,s)
< /no
(law |xx, ||
10
(0xx,slla
= Poly, [(f(xx))) Polss 100x,,
(C.11)
Meanwhile, when 1 2 2,
||0, (81) (x2 =
(a
21 f1 (xl12
1
(10.w; l|2 ||ا (1 (1=-1)) (xt,s)lla + ||W 1l2 110,a(1-11) (xr,s)ll2)
< Poly. (1a,w( [la + Poly, 110,z (1-1) (1-1)) (xr,s)llz
< Poly. (() +Poly, K 110 [1 (1 (xc,))l
Lemma C.I
Assumption
... < Poly. (1 y) + Poly, 1|0xx,,l12
(C.12)
Combining Eq..(C.11) and (C.12), we thus have for every I, E [1: L 1).
+ ||a (h) (xl,))llz & Poly, (( | |0:x,,s|12)
On the other hand, by applying Assumption 1, for every 12 [1 L). |0,x0! (12) (x1,
110 10)6)) (6) (x1,5)l2 (0.h( (x1
< K ||8,1 (12) (xl.
< Poly, (( + + 12)
The proof is completed.
24

---

Published as a conference paper at ICLR 2024
Based on Lemmas C.1-C.4, now able to prove the following Lemma C.5. Lemma C.5. Suppose Assumptions 1, 2, hold. Then as min - oc, we have
w(''l2. 112
1 || - -Wo0llE ||
R 0,
sup rE|0,7]
max 1SIgh+1
1111
4--
116 (xt,s) - -10 (x0,s)
- 0,
sup max
(E[O,T] 1SISL
\Tll
1
| (1) (xt,s) 2000 (x0,s))lz
P
sup max 1E|o,T] 0S1S0
n1
Proof. Suppose A, denotes
(IW |F +IW, - -wo"ll
A
MI-
(1=00 (xo,s)ll2 + [xx,5(xx.s)) (xx,s) m/ (x0,9) )12))
Vni
(Ino)(xos))l) (xo. + 114 (xx,s) - -h (xo.s)ll2)
Then, by applying Lemmas C.I, C.4 and the fact that 0.|| 1122 ||0 : ||2 holds for any given vector, we have the following,
L+1
0.A, S
1 |
Σ
10,z 11) (xr.s)ll2 +
10th (x2
T4-1
1=0
++1
Poly. (l0 (()
v /ming (0:r.] {mu)
Lemma C.I
(L+1) +
Poly, ((10)x)) v)lk 110xx,,5
/minig(o:.] (m))
Lemma C.4
v ( (Poly, (((x)))) (1xxx,slle)
(C.13)
By further applying Lemma C.3 into Eq. (C.13), we have that for every E [0,T],
o,A,
Poly, [((xx)) + cxp(O,(1) Poly,) Op(1) Poly, (110 ((f(())) +1)
/minig (nr)
Vmin (1+e (1) Poly, (1+ (1
(C.14)
According to the definition, the polynomial Poly, in the above Eq. (C.14) is a deterministic combi- ||x (o (x1,s)ll2, and ||A[5) (x2, Therefore, given the fact that
nation of ||W [[,,
I (1) ||e - ||W: || || w (xx.s) - 20 (xu.s) 112 [1m (xx,s)lle < |1400) (xo,s)ll2 + [14.0) (xx,s) - 11 (xo,s)
|| (xx,s)ll2 < ||=0 (xo.s) 1|2 + ||= (1)
(1)
for the polynomial Poly, in Eq. (C.14), one can find a polynomial function P(-) with finite degree and finite positive coefficients such that
Poly, $ P(A.)
25

---

Published as a conference paper at ICLR 2024
holds for every t T). As result, 0,A, can be further bounded as below,
1
(1+ (1+c0uavP(A)) -2(1)- (1 (1+
0,A -
V mine /mineeo:.
which means for every t E [0, T)
A. - Ao S S A, s /minieo::ssmm S ((A),)0())) (4
where g(z, v) is defined
y- P(x) (1+
By the definition of (1),), we have that for any 8 > O, there exists a finite C' > and a finite N N such that (1) I C) 1 8 as long m {ni} N. Notice that g(z, y) is increasing concerning y, thus when min N, with probability at least 1 - 8, we have
o L ('A...) (1 + [(f
A Au S
dr.
Furthermore, notice that (1) (A, - Au) is non-negative on [0. by definition, (2) (1 + (00 xl) is integrable any sub-interval [0, a| C [0, and (3) g(x, C) tinuous and positive on [0, +2) concerning and thus 1/9(1, C") is also integerable on any interval [0, a). Therefore, we can apply a nonlinear form of the Grönwall's inequality, i.e., Lemma A.3, as well as Assumption 2, and have that
[' (1+ ((,
sup Go(Ar Ao) tE(o,T]
v /miinggo: (m)) (m)
(₂(1)
C
min
min
where Gz(z) Se s(F.C) continuous increasing function on [0, +o0) and thus the inverse function G also exists and is continuous on [0, G+(o))))..
Thus, as min) - xc, we have that that suPrejo:r] Gc(A, - Ao) - O. Combining with the fact that Go (x) 0 in the range [0, +o0) if and only if 0 and the continuity of Go on [0, +00), we further have that with probability at least 6, soP A Ao) can be arbitrarily small for
sufficiently large min }.
The above justification suggests that as minke(o:.. {n}] + oo.
| ( ||F (xt.s) - -100 (x0,s)ll2
|| (1) (xt,s) x (xo,s)lla
sup (E(O,T]
Vm--1
Vmi
Vni
(Ac - Ao) Pg 0. rE(o.T]
< sup
The proof is completed.
C.3 CONVERGENCES OF KERNELS DURING AT
This section aims to prove Theorems C.I and C.2, which show that as network widths 7gg ... n approach infinite limits, the empirical NTK θ, and the empirical ARK θz, will converge to the deterministic kernels O and O, defined in Theorem B.l respectively.
26

---

Published as a conference paper at ICLR 2024
C.3.1 PREPARATIONS
We first show that rescaled network parameters VRS-1 mas C.6, C.7), which thus indicates the optimization directions (Lemma C.8) as well as network outputs (Lemmas C.9, C.10, C.II) in each layer are also bounded. The proofs relies on the key Lemma C.5 presented in the previous section.
W W are bounded during AT (Lem-
Lemma C.6. Suppose there exists ñt E N such that {no. ... ,nL 2 ñ. For a given E [1 L+1], suppose Wi = (1))) ñ - Then, have that as ñ 50,
W 11 = 12
Proof. By definition, each entry of the matrix + w E -= is drawn from the standard Gaussian (00, 1). Therefore, by applying Lemma A.4, we have for any 0, when ñ 2 21n 3. with probability at least 1 -6,
:o oW
2 S Vm + vn-1+ + 2 fimm S VT + Vm-1+ V Vni + Vnn vn.
which means
W l12 ow
ow
2
V ni-1
14
2ow + +pp(1)= Op(1)
as oC. Therefore,
W (0 1|2 = (p(1)
/
as ń + 0o, which completes the proof.
Lemma C.7. Suppose Assumptions 1, 2 and 3 hold, and there exists E N+ such that {no, _n 2 n. For given I E [1 L + 1), suppose mi- Op(1) as ñ - cc. Then, have that as ñ co.
W (2) l12 = Op(1)
sup rE[0.T]
Proof. We have that
1 lla
(W(0))
w( ll2
I
sup x 0.7]
sup rE(o,T]
V
/n111
Vn-1
T2
By Lemma C.6, we have Y, = O1(1) as + co. By Lemma C.5, we have Y2 P 0s + xc.
which further indicates T, = O1(). As result,
| 11 } S O0((1) 0,(1) Op(1),
sup (E|o.T]
Vm-1
1/ l12 Op(1) as 0o.
which demostrates that suprejo.T]
The proof is completed.
Lemma C.8. Suppose Assumptions 1. 2 and 3 hold, and there exists E N+ such that
(no, ... ,.) 2 n. For given I E [1 I. + 1}, suppose ny
(p(() as ñ + x holds for
any 5 1' < +1 Then, as + oo, we have that
110p0000 (L+1) (xx,))lla = =0((1).
sup te(o,T (0)
27

---

Published as a conference paper at ICLR 2024
Proof. Since
sup s (0.0)
(1+1)
(x1,a)]l S
II sup
110 h (x1,))l1
(1(+1)
M=t
IW! [W(('+33 +1)
II K 0p(1) = (1))
sup (e
Vnn
Assumption
P==l
thus (
(1-1) (x))
(x1,)) (xx,))l12 Op(1) ñ +
The proof is completed.
Lemma C.9. Suppose Assumptions 1. 2 and 3 hold, and there exists E N+ such that {no,"" "o ,n) 2 n. Suppose for any 1 E [0 T.J. have ng (1( as Then, as
à + 00,
|0 (Xt,x) - 1100((x(x (x1,o2)l12 Op(1),
max sup sup te (0055
| ( (x+,,.) - 11, (xx,,2)ll Op(1).
max sup sup ([[::L++) e0
Proof. The proof is completed by applying Lemma C.8 to the proof of Lemma C.2.
Lemma C.10. Suppose Assumptions 1, and 3 hold, and there exists N+ such that
{no, ... ,, 2 n. For given 1 E [1 I. + 1}, suppose "f11 Op(1) as ñ - xo holds for my
any l 1 S L. Then, as ñ + 0G.
lim
sup no 000 +E(0.)) V
lim
|1 (x4 = Op(1),
M1-1 +00
[|, (1) (xt,)) - n (x)ll2 Op(1).
lim
lim
sup (E
10-00000
Proof. The proof is based on mathematical induction. For the base case where | 1, as + cc,
lim
sup
[|, (2)
(xi,s)
no 1 (x)]l2 = lim sup ||, ( (x) - (x) + (1))
ng 000 tEJ00S)
no no0 te(o,T]
Lemana C.9
/' 10. |x||a dr Vmo
50,(1)+ + lim no- (E|O,T]
sup
|x|||
1 1y (x1, 110 -h(+t) // (())))
20p(1) + lim
lim
sup rE(U,T]
nig
Vno
Vno
xt, l
sup = -p(1))+0ppp lim
(p) (1)
+ 30 :E(O.T]
v T2o
Lemma C.8 Assumption
|x||2 O1)
$ Opp(1)+ lim
110 +00
/no
Lemma C.9
which indicates lim (UP [1, (1) (xx,)) 11 (x)(2x]2 Op())
As result,
/ni |1 (1) (xr,))ll2 <
-
1 |1 ( (x)1l2 (1(1)
lim
sup (E)o,T),,E(..
lim
00
ao 700 Tni
Vmn
(Z xmm) +0,(1)==
m==1
Lemma B.I
28

---

Published as a conference paper at ICLR 2024
which indicates limmn- se) रेv l (1) (xt,s) (lc,,)]l2 Op(1).
Then, for the induction step, suppose the lemma already holds for the (-th case and we aim to show it also holds for the (7 1)-th case. Following the same derivation as that in the proof of base case, we have as it + 00,
lim
lim sup sE]
|1, | (1+11 (xt.s) (1+1) (x)ll2 (x)]l2
- N10
1 (x)ll2
|
(1)
(x,,))l2
S <Op(1) nr 100
lim lim
lim
lim
sup
Op(()
no 7000
Vnu
100
no 000 rE(0,2]
Vm
M
I00 (x)]l2 (p(1) -1((1)
< 50p(1) + 10 (x
lim
no 700
VII
Lenma B.I
Induction hypothesis
<0,(1)+0,(1)
Lemma B.I
Therefore,
sup 04-1 no sE(U.T),
lim
lim
1
||
(3)
(xt,xx))) 1l2
/ni
1
11/ (1) (x)]l2 + Op(1)
lim
lim
ni 10000
no +00
Vml
/mi
M
(Ta, Fm)
m=1
Lemma
The proof is completed.
Lemma C.11. Suppose Assumptions 2 and 3 hold, and there exists ñ. N+ such that
(no, ... ,nL. 2 ñt For a given E [1 L. + 1), suppose no++1 = (p()) as ñ - xo holds for
anyl 1 1 1' < L. Then, for any X, as ñ 00.
lim lim
sup || (x)ll2 = Op(1),
200
1o0 rE(U,2] /ni
lim lim
sup
[1 (x) n/ (x)1l2 Op(1).
700 10-000 [0
Proof. The proof is completed by following the proof of Lemma C.10 and also applying Lemma C.10 itself.
C.3.2 PROOF OF THEOREM C.
Based on Lemmas C.6-C.11, we are now able prove Theorem C. follows.
Proof of Theorem C.I. To prove Theorem C.I, it is enough to prove the following Claim C.I.
Claim C.1. For a given I E [I++]] 1), suppose ne+1
az-1 = ()), Then, any m, m,m' m' E [M].
as ñ + xc,
lim lim
sup 000 te (0)0
|1Q (m Imi (..)) 1 (Im, Fm )l1 P, 0.
Ri
lim
lim
sup
(1(0) (Fm.le Lm...s) @ (Im, Fmm Pg 0.
10000000
no 000 la (e)
29

---

Published as a conference paper at ICLR 2024
Theorem C.1 can be directly obtained by setting = L + 1 in Claim C.1. Therefore, turn to prove this claim.
Proof. The proof is based mathematical induction. For the base case where 1 1, for 6,, as
ñ +
|
x Fmm
10 (mm, Fm' -.0 212
-
sup (0)0
sup rE(o.T].<E(0..
110
By Lemma C. and Assumption 1, we have
| Im lll
Op(1) P 0,
lim Ro-000
lim
Vno
no
vno
which thus indicates
lim LE (E,
sup
|60 (Im,t.es (m.)) 6 (Tm ml2 P 0.
Besides, for ( o.
we have
| (1) w
w w (!
1l2
1 (Im: mm) (E(0.TT).c((.s]
sup =E
sup
[ww""_W!'' P as as ñ + oo, which further demonstrates
By Lemma C.5, we have lim
Vno
lim sup +E((
n.f (mm,tts - - (am:
Zmm )l2 (2m,
na 700
and thereby completes the proof for the base case.
For the induction step, suppose Claim C.I already holds for the I-th and want prove also holds for the case (I + 1) in which 2:12 BLll = Op()) holds.
To do so, we first prove technical Claims C.2 and C.3.
Claim C.2. As ñ xc,
lim lim sup ||, (e(o.])
!1 (Im) - (2) (fm) L 0.
Proof. As ñ + oo, for every j E [mr]. we uniformly have that
(1) (Imm) (mm)lo
sup (e[0,T]
( 10.6.0 (am))ld S max
[ [0gh( (am)) 0, ld
K sup max
JE(o.
sE(m)
K max jE(m)
(8gh(4 (Jm); 0hh44 (1 (xt,s) 0f (x (1+1) (xx,s) Oho+o1e) (1++)) ((4+))(((.) (l-xx
(x,,ss)
K max jE(m))
1, (Im s). Genngg h (xr.s)ll 110 (x. 1|2 110l22.110000 110 C(Jx x))ldr
K sup max
|1000 (I X Diag (W (1(++1)
O1
(l(1)
rE|o,T] je(md TTl
W((+1)
Lemma C.8
Assumption
< max sup max m/ iEjo.
1600) B.r
(Im, Imm s)ss w(l+1) O1(),
(C.15)
/ni
where 60) (1, Dz: denotes the j-th row of 600 (..)) and W ((+1) denotes the i-th row of (1+1)
30

---

Published as a conference paper at ICLR 2024
Then, by the induction hypothesis and Lemma C.5, we have
lim
lim max sup max
||6 6,r (m Lmm kn', - 0 (m )xillz _ 0,
+00
mg +00 m' E[M rE(oTT] JE[ml
(((+1) [W(11)
lim
lim
max sup
0
11 - 0,
700
700 m m'E[M] rE(o.T] se(m]
T
which indicates
116 (Ims Im,, s,s5; I(++))*
lim
lim
max sup max
000
no +00 E[Md] (0.7) jE|ni yni
19 (1) (a Leml )z= (((++)7 ll2
max max lim
MIM JELm] T
1 107
(Fim Emm )1 1
(W,(42)
lim max max
2.j.0
By + mn EIM (e
VTi
maxje(m) W (1+1)
VT41-
maX 10 p0))(())
(Im, Tmme)
max
lim m-000
1,000
m'E
max M
(0))(()) (Im; Tmm)
0.
(C.16)
Lemma A.5
Combining Eqs. (C.15) and (C.16), we finally have
lim ... lim sup [1 te[07])
(2) (am) - (100 -ho (Im) Eg 0.
The proof is completed.
Claim C.3. As ñ + oc.
lim
lim sup (E(0,T]
| (xm,,,)) 10 (z 11 Pg O.
+00
Proof.
We first bound |n! (Im,e,)) he (fm) As ñ - oo, have that
sup [ (Im.i.)) 1i (lo) [E)
( 10,h! ( (5mArr)yld S K. sup max vE(o, jElmi
S 10 (Zm,er)) Or /dr
< K.
max (E(O,T)) 5m/m]
KK sup max (6(() 222e (mm.atr: T Kovice me (zm,t,7)l22 (E(0. jE(m)
(1+1)
sup 10a (L+1) (xm.t.))l22 sup (E(o.T]
[|n(1) / ((( Mm 2227
(E)O.T)
(6(00) Vna 0.1 (mm,t Fm w(l++)" l12 Op(1)
sup max
2g(1)
(1())
Lemma C8 Assumption 3
Assumption
(C.17)
where 6. (Tm,t,r Fm.t.r );; is the j-th row of 6! (Im.t,7, )m.tr)
Similar to that in the proof of Claim C.2, by the induction hypothesis and Lemma C.5, we have
lim lim
sup
max | (1)
(Im.t,T, d.. @ (Im, F'm Lmr) ) Pg 0,
800 n0 (e( jE[m]
| w:
(1+1)
2 P. 0,
sup lim lim
200 no 700 [[[o.]]
31

---

Published as a conference paper at ICLR 2024
which leads to
1
110 (.. w(l+1)² 112
lim
lim
max (e
sup
2y0200
sE|ni] Vny
P. lim
1 U (Im, #m) w(++1) 112
lim
max
00-000
no 800000 jE(mi] VTH
= lim max
1
og (I mm)l WW 112
(e Vny
maxie(mi ((++))
S V/4+1 11:41-100000 10 (T Fmmm
max
lim
ic sE(ni+1]
n
S V (0 (Im, Tm)l
(0)
0.
(C.18)
A.5
Combining CQ..( and (C.18), thus have that ñ - 00.
lim 700
lim 700
sup [E(0.])
|1 (1)
(Im,,,s) h1 (lo) f 0.
As result, by further applying Claim C.2,
lim sup 700 no 200 +EJU.
lim
[|ng [ (Im,tss) n1 (sm)
lim < lim
sup 700 no sE(0sS)
- x1 (x oo 111 (xm) - '000 (fm))la))
+0+0=0 0.
The proof is completed.
Based on Claims C.2 and C.3, we are now able to prove the induction step. Specifically, for the 1(++1) we have
NTK 0,f
110012)
(1+1)
(Im,t,ss I'm (,,, - ((0 (x I'm ll2
|I (1+1) (amm,e))) 66! (2m,,,,, Fmd Fmm Fmm,e,)) D (Im', .T 1( (20 (F Imm)
(x + (xmm)
l (1) (Fmm.t.e) 1 (1) (Immd so,) x: (I STT sn! (ami))
11
1h.
where D D((+1((2)) (x): = w(++1) Diaglo' (x)))
(1) (Fm))))) in (1+1) For Diag( (1e (11
(m), by Claim C.3,
lim
lim sup
Diiag(o' (b (Im,,,)))) - Diag(ø' (h (z.m) )))ll
400 no t00 (e)0.)
lim
sup no +00 te (0
lim
| (9 (Im,t.a)) - 66 (ooo
400
lim ... lim P,O.
K | (Im,a)) - h1 (Im))l
[w((+)_ww ww(l- vmi
1/2 P.
Combining with Lemma C.5 which shows that lim -imm +00 supte(o,T] 0 as ñ + 0C, we thus have
lim lim sup
(1(++)) (Xm.t.)) (xm.t.))))))))) ((++1(((m)))) Ex
n2 no no (e)0
32

---

Published as a conference paper at ICLR 2024
Further applying the induction hypothesis that - lim -00 su SUP 116 (mm,t smm) ( (I (F0
Tmr)ll2 f O, we finally have
lim My Ro-+00
lim
sup Ro (e(
It, E 0.
Besides, for term s1 by Lemma C.10 and Assumption 1, we have
|| (1) (Xm,t.s)) x (2m))l2
lim lim
sup +E(0.]
700
VTu
K |1 (Im,e.s) ho (am)lla /ni
lim
lim
sup (E)0,)").E[0.8]
10
100
K O1) 2 0,
lim
lim
+00
no-
which leads to
lim
lim no 200 (E)0.T1,
sup
11 - O.
100
Finally, Based on the convergences of I. and 11, have that as ñ - oc.
lim
lim [|+
(Im,t.as - (Im, Fm))) P 0.
Ry 700
700000
According to Theorem B.I, 1o0m ... lim ((+1)) (Im, Imm) ( (2m Lmm) which
thus indicates
lim ... lim |10 (Imii am)) - 000
- (1+1)
Fm)) F O.
no0+00
Then, for the ARK 6(+11) we have
||0 (1+1)
(042)) (Im, I'me Il1
|| (411) (Zm,t.))
(!)) n,t (Im.t.ss Fts)) D. (1-11) (ame
(0) (
(Imss Fmm) ( 12
Therefore, following similar derivation as that for (1+1)
will have
0,
lim lim | 70000 7o-00
(Im,ttss Tim'
(1+1) (Jm, Teme )ll2 Pg 0
33
as ñ + 0o, which justifies the induction step and also completes the proof of Claim C.I.
The proof is completed.
C.3.3 PROOF OF THEOREM C.2
Theorem C.2 is similarly proved follows.
Proof of Theorem C.2. The proof is similar to that of Theorem C.I. Specifically, to prove Theo- rem C.2, is enough prove the following Claim C.4.
Claim C.4. For given! 1 E [Z. + 1}. suppose Ai+1
nE+1
(1), Then, for any E [M]. as
ñ + 00, we have that
| (z. Fm.t.s) 6 (z, 1mmmmll 112 P 0.
lim
lim
sup (E(
Wy +00
lim
lim
sup
| (x, Fm...s)
- 0 1|2 P 0.
10000
-0000 (E
33

---

Published as a conference paper at ICLR 2024
Then, Theorem C.2 can be directly obtained by setting 1 L + in Claim C.4.
The proof of Claim C.4 basically follows that of Claim C.1. The only difference is that Claim C.4 requires one further prove that
lim
lim sup rE|o,7]
(z) hg (x) Ex 0
for any x E X' as ñl + 0o in the (1 + 1) induction step, which can be done by using Lemma C.11 and following the derivation in Claim C.2.
C.4 EQUIVALENCE BETWEEN WIDE DNN AND LINEARIZED DNN
With the kernel convergences proved in Appendix C.3, we are now able to prove Theorem We will first prove the following Lemma C.12, and then prove Theorem 2.
Lemma C.12. Suppose Assumptions I, 2, 3, and 4 hold, and there exists N+ such that
{no.... nn 2 n. Then, as ni - we have that
lim 0g no
lim
sup [eJ0
[(f(x) Oz(o) C(Fe din (xbx) (x)")) Ps 0,
lim
lim
sup [E(
[[x((x,,)) - 1t (x(])x]]] - 0.
no-900
Proof. By Assumption 4, we have that
Ofc) [01()) (1, (xir) (x)
K [[fe(x(.)) - flin((x! (x!t:))l..
Thus, to prove Lemma C.12, it is enough to only show the convergence of (xf,( - f( (x)
Then, following the AT dynamics formalized Section 4.2, as + co, for any t E [0, T and E [0, SJ. uniformly have
(1)()))))) - 1t (x1
= =|(A0x) - f!in + 1-² (0n.(Xe.7) X.,) . ofx (1)( θx,0(x, x) n(t) (UStin (xtt)))))) dr
$ llf(((x)) A!n (x)112 + / 110,,((x,,, x.,) 0 xx [In(t)ll2 ((f(xx))) -
+ 1." 110, [1)(1 110 ((f( ((()) 112d7
$ ll.f(xx) -J! f!" (x)l12
sup FE(O.S]
||ō,, (X x1,) θ xx) (p())
Og())
Assumption 3 Assumption
1 [lf(x))))) f! (xf dr.
(1) Assumption
Assumption
By applying Grönwall's inequality (Lemma A.2), we further have
(x,x()),s) -J!ii (x(in)) [
(x, x) x))22-0((1) 02(1) exp (10
$ [lf((x) - f sup
x)112 x)110xxxx))))00(1))) (C.19)
rE(0.S]
34

---

Published as a conference paper at ICLR 2024
which indicates
lim
lim
sup [[f(()),)) -x
ag +000
mg 000 te(o.2]
lim
lim no-
sup
llf:(x) (x)]l2+ rEJO.T),rE(O.S)
sup
(x.,, 6x,0(x, x)112 0x(1)
+00
(E(O.T]
exp (10,,,(x,x))11 -
exp (10,,xx,0)13
lim ... lim
sup
[lf((x) - f( (x)ll2 + Op(5)
[e[o,]]
Theorem C.I.
Theorem B.I
lim
lim sup [1]x(x) fl' (x) + Ox(5) eep((O((1)
(C.20)
a0-000 te|o,T]
as n + oo, where & denotes any term such that + 0 as ñ + oo.
For [1]x(x) f!' (x)ll2 in the above Eq. (C.20), we similarly have
llf(()) - 1! (x)]l2 = 1/. (0u.-(x, x,.s) [(x ((f+(x)))))) 6,,(xx x) [( (( (xx,)))))) dr
! (x,,sx 0,.0 222 [() (x+ y))
+ //" 100,0x x)ll2 (00 f L( piim (x."))),
* 160,0(xx)))1 x)ll2 (xf+(x+,))
$ sup
||0,, (x, x, 0,.0 x)]12
(p(1) +
p!in (x!tis))
dr.
rE(0,2)
Assumption
Assumption
Adopting Eq. (9.19) into the above inequality and again using Grönwall's Lemma A.2 lead to flin (x)]l2
[lf(
< sup
|/0er x,,)) - (x,o(x,x))1
[E(o.T]
+1,0,,0(x, x) sup |(0,, - 2z x)1l2 exp (16 x))22 xx)1))))) rElu.s]
x)l12 (( (11()..(xxxx)xx)))(())
Op(1) exp
which indicates
lim
lim
sup [x((x) [
my.
no 1E[0,2]
< lim
lim
Upper Bound of sup [lf((x) - s!lm (x)) rE(O,T]
ny. +00 no +00
1 (x, x)122 Op(1)) 0p(1))
P Op(5)
+ 10((x, x)122
Op(5)
exp
Theorem C.I
Thearem B.I
Theorem C.I
Theorem B.
Op(1) exp
(0)(x,x)ll 10 (xx
Theorem B.I
(0,(E) +O,(1) -Op(E))pp))))))) (p(())eep(0)) -ooaal) (0((1)exx) exp (0,(1)-e0((000)
O P.
35

---

Published as a conference paper at ICLR 2024
as ñ oc, where & denotes any term such that - 0 as ñ - 00. Thus,
lim lim sup [e[0,]]
(x) (x)]l2 -
(C.21)
06.
Finally, inserting Eq. (C.21) into Eq. (C.20) and we have
lim
lim 000 (EJo,T]
sup [xx((),)) - ft (x
lim
lim no
Upper Bound of
sup (.E
[e(()),)) St (xx,,)ll2
ny +00
2 (Op(E) (p( cO0())
2 (0 + 0) (1) 0,
which means ñ - 00,
[[f((x,,)) - (x][)) _ 0.
lim
lim
sup (0)
The proof is completed.
Based on Lemma C.12, we now prove Theorem as follows.
Proof of Theorem For any x E X' as ń + oo, we uniformly have that for any t [0, T],
[1f(()) - (x)]l2
= 1.1' (0,,)(,,,,s)) (Xf 00,((x,x) C( (xx))s), dr
- 1/-" 10,, - 0z,0 x) (x), + L (1 x) 11fx p (x!
sup |0, - 0,,o(2, (₂()) rE(0.T]
+110,,( x) T sup rE(O,T]
11s 1 (x)))))))
Assumption
Therefore, by applying Lemma C.12,
lim lim sup [1 (x)ll2
ny +00
no 100 rE|0,7
lim
lim
Upper Bound of sup [[f(()) f! (x)
uE +00
no ma0
(E/O,T)
F (g((5
O0(() 10, x)22 T Og((5
Theorem C.2
Lemma C.12
-E + (1) Op(E) = Op(E) P 0,
where & denotes any such that + 0 as ń co. This means that à oc,
lim
lim []((()) (x) P, 0.
The proof is completed.
D PROOF OF THEOREM
This section presents the proof of Theorem 3.
36

---

Published as a conference paper at ICLR 2024
D.1 PROOF SKELETON
To calculate the closed-form solution of the linearized DNN ft.h with squared loss in AT, the main technical challenge is that the learning rate matrix ((() non-linear on [0, 7), which results fl"n also being non-linear on [0, T' and thus is difficult to calculate closed-form solution for it. To tackle the challenge, we propose to first use surrogate piecewise linear function ft" approximate f!ln
and then directly calculate the closed-form solution of f:ur when the squared loss is used.
Specifically, for given E [0, T the piecewise linear function fou on the interval [0, t| (note that E [0, d)) is constructed in the following three steps:
1. Choose D E N+, and divide the interval [0, into D equal-width sub-intervals, where the d-th (d E (D) interval is [aa-1, ad) and 0ad == D
sd
2. Construct surrogate learning rate matrix n (v) such that n n (aa--) when U E aa) for every d E [D].
3. Initialize four with parameter 0n and train it following the same AT dynamics that of flin except using the n (v" as the learning rate matrix for searching adversarial examples.
After finishing the training on [0,4], we will obtained the eventual surrogate DNN st
In the rest of this section, we will show that: (1) in Appendix D.2, the designed surrogate f can well approximate the original f!'m as oo, and (2) in Appendix D.3, the closed- form solution of the surrogate frur can be easily calculated, which then leads to the closed-form solution of flin.
D.2 APPROXIMATING LINEARIZED DNN WITH PIECEWISE LINEAR MODEL
Lemma D.I. Suppose Assumptions and hold. For any E [0, 7", we construct four on [0, as that introduced in Appendix D. Then, as D - 20, for any [0, t and E [0, we uniformly have that
[ll! (x]i..)
lin
fo fuur (x + O.
Proof. We first upper bound the difference between fl (x(ijt) and (x"(() on the d-th interval. Specifically, for any v [aa-1,da] and
[0, S), we uniformly have that
|| (xere) - (x(ia)))
[[f""( (x) -fo (x)]l2+ '-" 16 ( Inn
111 (v) C( (x.") n(v) C(F v)
Constant
< [lfo"r(x -fli (x))l2
+ //² C. ||| (|n (")()))22 |00 C(J (x("))) - 0zix) L(S (xliit) l2
C. (-Iln""(vv) ( [10 - (xlim) 3))l2d
$ || ( (x) plin (x)l12
sur (u)ll2 S [100() (xx))) -(( (x20))) 2)
+C sup rE(o.T]
(xe1))))
by Assumption
/ [( fill (xliit ) l22dr
+ C. sup vE ve(aa-1.0d
- -
Constant
f (x) fllm (x)ll2 (x)]l++CC C. K four (xqur
flll (xxlia b. dr C
sup
[n(v)) (
2 E00,7 1s
Assumption
37

---

Published as a conference paper at ICLR 2024
where C' denotes any non-negative constant. Therefore, by Grönwall's Lemma A.2, uniformly have that for any U E [a--1; ad] and E [0,S],
I1 1 (xbts) _ (x..))
$ [15"" - f.. (x) + C.
sup Uy e,0,77 in -
[[((1) (
exp(C K)
$ C- - f (x)1l2 +
sup o. 1o--
[[(e1) - (22)) 1
(D.1)
where C denotes any non-negative constant.
For [| (xe.e) - (x in Eq. (D.1), we bound it on the interval [aa-1, aal as follows,
f (x) f (x)]l2
(x,""((((,))) < Jaur (x) - Sain (x)1l2 + L |10,,(xx, (l0)) "(,,"' (x,1s), y) (((x) (x),)) (
Jaa-
Constant
/ (x) سliم (x)]12 C. frd
K ( (x,,s)
1 (x,,))
(,7)) dr
li
aa-1
Assumption 4
I| (x) plin (x)112 CC.
C. (x)
sup v1. les +uls
[[((v)) ((2))ll2 dr
Ga-1
(D.I)
Ct
/ [1*" ffi (x))l2d,,
< <Ilfaur (x) flim (x)]12
+
sup v v
[n(er) (12))l2 C.
D
[.,.7,
where C denotes any non-negative constant. As a result, by again using Grönwall's Lemma A.2, we uniformly have that for any aa).
11 (x) - -fe"(x))
(x)]12 + Ct ||sarr (x) ,
exp C /" dr
sup
[In(e)) n
D
w. lo -
Jad-1
C sup
C
||aar (x) -lin (x)ll2 +
[[((v]) (u2))l22
eexp
D)
D
(1.T) -
(D.2)
where denotes any non non-negative constant.
Therefore, for any aa where d E [D], by recursively applying Eq. (D.2), we will have that
|| (x) - -flli(x))l
C
exp (C)
(0)
< [|sau (x) - -lli (x)]l2 (x)]2
[[((w)) - (12))l2
D
sup 01.02 ul
Cd
Cdd'
.... (...5(((0t(xx)) - (x)]12
exp
D
+
D
sup
[ln(vi) - n(v2)ll2)
eepp
D
d'=l
Un +
00 exexx(() + Cd
[[((e:) ( exp((C
sup
D
2 in 1
C.
sup
[n()) (
(D.3)
[0,7] 1
where C denotes any non-negative constant.
38

---

Published as a conference paper at ICLR 2024
Combining Eqs. (D.1), (D.2), (D.3) leads
[ SC.
fe
lin
ll
C
exp
c
D +1)
sup
In(e)) (
D
11,72 in pals
SO.
sup c(,1), - $
[[n(v1) (12))ll2
where C denotes any non-negative constant.
Finally, according to Assumption 3, we know that n(() is continuous on the closed interval [0, 7].
which indicates it is also uniformly continuous on [0, 7). Therefore, as - cc, we will have + oo, which indicates for any v [0,4] and [0, S] uniformly,
sup (0.7%, in +
[[((,,) (e2)ll2 0.
Combining the above results and we finally get
[ (xxts) fo (x lll + 0
uniformly for any v E [0,4] and E [0, S] as D + oo.
The proof is completed.
Lemma D.2. Suppose Assumptions 3 and hold. For any E [0, construct four on [0, 8] as that introduced in Appendix D. Then, for any x E [0, æ/. as D + oc,
(x) - ft (x) ll2 + 0. Proof. The difference between ft (x) and fl:)(:)) can be bounded as follows,
1l (x) - f
!1 (x) (z))l2+ !'"
(x.,s):)
Coustant
50+ C. S( K. 1.115a 0z60 Su (x)
Assumption
C.T. sup
|| (x) Ozoy (x)]l2 C sup [x)* - 0560) Pul (( (x)]l2, vE(o.r]
(E((.)]
where denotes any non-negative constant. Then, by applying Lemma D.1, we have that sup
[]fe 0z(0) (x)
rE[0.[]
as + oo, which thus leads to
(x)) ((:)l1 0.
The proof is completed.
D.3 CLOSED-FORM SOLUTIONS OF LINEARIZED AND PIECEWISE LINEAR DNNS
Lemma D.3. Suppose Assumption 3 holds and the loss function used in AT is squared loss L(f()), v) == 1x) - vllž. For any t E T), we construct faur on [0, t) as that introduced Appendix D. Then, for any [0, 2/. have
lim (("((s) fo(x) -0,o2, x) 0x,(xx)) (1-c (1-60000(kx))(1)) (fo(x)- -y),
D-000
where E(1) = foexs exp (0..0(x))) x) ( 5) dv.
39

---

Published as a conference paper at ICLR 2024
Proof. We first calculate the closed-form solution of feu on each sub-interval Specifically, for the d-th sub-interval (q--1- Ou] and any V E [ad-1, od]. the dynamics of searching adversarial examples can be formalized following Eqs. (16) and (17) in Section 4.2 as below,
0.50 (xx(s) 2 x) TI sur (v) (fr (x,1is) yy)
02,0 x) ((aa-1) (fe (xe,s) -y);
where
1 (x 1 (x).
Solving the above ordinary equation and we have
( (x.,s) - yy exp (02,0(x,x) (add1)) s) (x,"(()) yy).
(D.4)
Then, for the AT dynamics of four on [a anl, it can be formalized following Eqs. (14) and (15) in Section 4.2 below,
0. = - 06 fo(x) (Je (x.,)) y): 0, (x) = -0,00xx x) four (x)),)) y). Inserting Eq. (D.4) into the above ordinary equations, we further have
0,0 - 0 fo(x) exp (0,,0(x, x) m(aai)) . 8) (x) y),
(D.5)
0.f (x) 0,,00 x) exp (G, (x, ((s-1) - 5) (fot -y). (D.6)
Solving Eq. (D.6) and we have for any [as-1,
(J (x) y) exp (-0,,0xx,x e (x,0 (xeggxxx)..e...ocxxmmaa... . -aa-i) (Jan, (x) - -y), (D.7)
which indicates
(J²t - y) = (Jap y)
1 II d=
exp ( (-0e,0(x,x)) - (as ((-1)) (fau y)
(-6ROOxxx)) x)
t
Σ
(nooaaastee)))))))) (f6(x) y).
exp
(D.8)
D
d=1
Besides, by combining Eqs. (D.5) and (D.7), the closed-form solution of the difference between 6eur
and Heur is calculated as follows,
a
gour geur aa-1
aa
0h fo(x) exp (On,((x,x) x) (((d-1) -)) (four (x) - y) du
Eq (D.5)
aa
-0% fo(x). (,,(xxx) 1)88
( (eeeo(xxx).@.oooxxx.. (000 1).8 (v ad-1)) (faur (x) y) du
exp
Ja--
(D.7)
[[o% fo(x) -x, (x(xxxx)xxpp)
exp cxx(-OOp.oo 1p.0 x) (e.ofx..))x..xxxxxxxxax. Clooxx)) (v ad-1)) (Saur (x) -y) a4
aa-1
exp 1 x) (e.oo(x))))e.. )lo t D) -1) (Jaur (x) -y)
0%. fo() (x, x)
oo fo(x) -,,6((xx)) (x,x)
(Seur (x)
-Saur (x))
Eq. (D.7)
40

---

Published as a conference paper at ICLR 2024
The above equation illustrates that the model parameter 87 of fer at the eventual training time t can be calculated as below,
D
0:ue - 8u= = Gap gaor
Gaur
d=1
Σ 0f fo(x) (x,((xxx)
(fau (x) Saa-, (x))
0% fo(x) 00,6(1x, x) -foxx)
-0 fo(x) 0,,((x,x) x)- (cxp) (-0,0(xxx) t Σ ( -1) -1) (fo(x) y).
As a result, for any x: E X,
lim (x) = lim (Jo(z) + 0ofo(r)) -00)
D+000
D+x
D
Ed -1) -1) (Fo(x) -
= [f(()) + lim 0olo(z) 0ī. fo(x) (x,(xx,x) exx -00o(xxxx) x)
Σ
D
D+200
dm1
[ 1
fo(r) + x,,((x (x, exp (-0po(x,x))
Σ
c (l
lim D=soc
(fo(x) -y)
D
d=1
By the Darboux integral, when + 0o, have
Σ
@ = //' exp (0x.(xxxx) n(v) - S)) do,
D
lim D-
D
d=1
which means
lim ft" fo(x) 08,0(1, x) xx. (exx))exx(xx))))) (-00,00x,x x). x)((()))) -1) (fo(x) y)
fo(x= -fo(=)-@,.oll 0,,0(1, x) 07 (x, x)
(fo(x) y))
where E(t) Ju exp (0..0xxxx) (uv) 8) dr.
The proof is completed.
Proof of Theorem 3. For any E [0, T.. suppose four is constructed on the interval [0, t following that introduced in Appendix and the loss function is squared loss [(f(x). y) 1
2 ff vll².
Notice that the squared loss is 1-smooth and thus satisfies Assumption 4, one can apply Lemma D.2 and have that
( = lim ft (x))
D
Then, by further applying Lemma D.3, we obtain the closed-form solution of flin for any x E X as follows,
(1)) = lim fr (x)
D-+00
= fo(x) (2, 0x,((x,)) (1=x-00()))))0)) (fo(x) - -y),
where E(t) = f exp (0x.(x,x)) x ((7) . dr.
The proof is completed.
41

---

Published as a conference paper at ICLR 2024
E ADDITIONAL DETAILS IN SECTION 5.1
E MISSING CALCULATIONS
This section presented calculation details omitted in Section 5.1.
Calculation of G (x,x(xxx))(())
By the decomposition E(t) QA(t)Q² -a(t), we have
00
(-1)² x){(1) = Σ (-a(1))'
Σ
i!
0= i!
1=0
For (Qn0(x,))QAA()07T)
it can rewritten as
(0ao(xx))QA(107))
,g,0(x, x) 0x000xxx000000000000000000000000
i number of (x.00x
0x,0(x x)QA(1)+ A(1)= 0o,((x (QA(()).... O,, 0x0 -())))=A(())''
(i 1) number A(1) x)(
QA(()=+ (x, x)Q(())
A(t)aQT
QA(()=+ 1 oo,0
A(1)2Q=T.
Combining the above results, we thus have
(x.x(xxx)
aa(i)) QA(I= (40):0"6nolxxx)44000 A(1)20"
i!
2
(=a(t)) (A10+("@@n(xxxQAA()))) A(t)tQ"
QA(I)=
i!
i=0
QA(t))++ exp
x) a(t)) A(t)*Q².
Calculation of exp
(-A(co) (,,(xxx) -
By the decomposition A(co) ((ooo)nnnA(()///) ( 0x,0 x)0== = Q'D'QTT we have
exp (-Ac0))) 0,o(xx)) QA(oo) a(oo))
= =exp(-Q''''Q a(xc)
(-a(co))) (Q'D'Q'T)'
i!
(-a(oo))
Q' D". Q
i!
By ByQ'Q"== =I
Q' - Doc)(
( Q' Diag( -00) Q =0, 0,
where (x) is by: (1) a(co) co, and (2) every diagonal entry of D' is positive.
42

---

Published as a conference paper at ICLR 2024
E.2 DNNS BEHAVIOR UNDER LARGE ADVERSARIAL PERTURBATION
In Section 5.1, we have assumed that when the adversarial perturbation scale is small enough, the symmetric matrix
H = A(oo) De,u(x,x)QA(ss)))
stays positive definite, which combines with the assumption lim,-+oe a(t) = oc leads to the AT de- generation phenomenon. However, theoretically can only prove that H is positive semi-definite based on facts that (1) A(oo) diagonal matrix, and (2) 0,,0 x) positive definite.
Further, when the adversarial perturbation scale is large where Th (t).... : TMM (f)S are large, the symmetric matrix is likely not be positive definite. This is because in this case the elements in the matrix A(oo)
a(co) Jo exp( (t) may vary greatly, which thus erode the positive definiteness of Q" (x, x)Q and results in H not being positive definite matrix. Therefore, we now analyze the remaining cases where Amin (H) =
When Amin H O, following similar derivations that in Section 5.1 and Appendix E. we will have that the exponential term in AT dynamics in Eq. (18) not converging to zero matrix, ie.,
lim e (x.0(xx)) QA(co) e A(co) Q² O, where Amin (H) 0.
In this case, AT degeneration would not occur in long-term AT, and the adversarially trained wide DNN will eventually converge to model that is different from that obtained in standard training. However, we also notice that large adversarial perturbation could add strong noise that can destroy meaningful features within training data, which barriers DNN to effectively learning knowledge. Therefore, it would be interesting to study how to construct NTK models with large adversarial perturbations achieve strong robustness in practice.
F EXPERIMENT DETAILS
This section collects experiment details that omitted from Section 6.
F.1 PROJECTED GRADIENT DESCENT
We leverage projected gradient descent (PGD) (Madry et al., 2018) to find adversarial examples within constraint spaces in our experiments.
Formally, given machine learning model f X' + V. loss function C 3 x y + I and perturbation radius p > 0, PGD aims to find the adversarial example zddv for given input data point (z, y) via solving the following maximization problem,
adv
arg max (xf()').
I SS
PGD will perform K iterations of projection update to find optimal adversarial examples. In the k-th iteration, the update is as follows,
(k)
II
x (k-1) + Sign
where (8) is the intermediate adversarial example found in the k-th iteration, 0 is the step size, and II I - means the projection is calculated in ball sphere centered at x, i.e., {a' || =|| S p}. The eventual adversarial example adv := (K).
F.2 NETWORK ARCHITECTURES
Our experiments adopt two types of multi-layer DNNs, "MLP-x" and "CNN-x". The detailed archi- tectures MLP-x and CNN-x are presented Table 3, where "Conv-r(c)" denotes a convolutional layer with kernel shape and output channels, and "Dense(c)" denotes fully-connected layer
43

---

Published as a conference paper at ICLR 2024
Table 3: The detailed architectures of MLP-x and CNN-x, where the network width.
MLP-x
CNN-x
Dense' (w)] ReLU
Conv-3 (w))
ReLU
Dense=-1 (uo) ReLU
Conv-3" (w)
ReLU
Dense(10)
Flatten
Dense(10)
with output channels. Also note that there is a network width hyperparameter w for the architec- tures in Table 3. For vanilla neural networks, a finite value, while for NTK-based models, w is infinite.
We then introduce the detailed model implementations of Adv-NTK and baselines NTK and AT.
Python Library (Novak et al., 2020) which developed based on the JAX autograd system (Bradbury al., 2018) to implement NTK-based models in our experiments. The Adv-NTK model is constructed following Eq. (24), while the NTK model is constructed following Eq. (4). For every Adv-NTK and NTK models, the netowrk width is set as oc, and the weight and bias standard deviations are set as 1.76 and 0.18, respectively.
Ady-NTK & NTK. We use the
AT. We use PyTorch (Paszke et al., 2019) to implement the finite-width neural networks in vanilla AT. The network width for the MLP-x architecture is set as 512, while that for the CNN-x architecture is set as w 256. Other model hyperparameters follow the default settings of PyTorch
F.3 TRAINING AND EVALUATION
General settings. The loss function used in all experiments is the squared loss ((f()) y) = (1lf(z)) 81ا.. Whenever performing PGD to find adversarial examples, always use Too- perturbation. For a given perturbation radius p. the iteration number and the step size are always set as K 10 and a = 2p/ K, respectively. For both CIFAR-I0 and SVHN experiments, draw 12, 000 samples from the original trainset to train/construct models, and use the overall testset assess model performances. No data augmentation used. Every experiment is repeated 3 times.
randomly
Adv-NTK. We follow Algorithm to train Adv-NTK models. 2, 000 training samples are used as the validation data, while the remaining 10, 000 ones are used construct Adv-NTK models. In experiments SVHN, each model is trained for 50 iterations, in which the batch size is set as 128 and learning rate is fixed to In experiments on CIFAR-10 10, each model trained for 50 iterations, in which the batch size is set as 128 and learning rate is fixed to 0.1. All other settings follow general settings.
NTK. Every NTK model is constructed following Eq. (4) with the overall 12, 000 training data. There is no need to train NTK models. All other settings follow general settings.
AT. We use SGD to train neural networks in AT following E1.(1) via SGD for 20, 000, where the momentum factor is set as 0.9, the batch size is set as 128, and the weight decay factor is set as 0.0005. In experiments on SVHN, the learning rate is initialized 0.01 and decay by factor 0.1 every 8, 000 iterations. In experiments on CIFAR-10, the learning rate is initialized as 0.1 and decay by factor 0.1 every 8, 000 iterations. All other settings follow general settings.
F.4 EXPERIMENT RESULTS ON SVHN
This section presents the additional experiment results the SVHN dataset.
From Table 4, we have similar observations as that from the results of CIFAR-10. which show that Ady-NTK can improve the robustness of infinite-width DNNs and sometimes achieve comparable
44

---

Published as a conference paper at ICLR 2024
Table Robust test accuracy (%) of models trained with different methods on SVHN. Every exper- iment is repeated 3 times. A high robust test accuracy suggests a strong robust generalization ability.
Adv. Acc. p 4/255)
Ace. (E p 8/255)(1)
Depth
NTK
Adv-NTK (Ours)
Ady:NTK (Ours)
3
19.59110.00
18.43:10.53
24.64:10.59
19,59110.00
9.32=0.15
21.68 1,91
MLPxx
19.59=00.0
21.47:0.266
34,93=21.17
19.59=00.00
9.00=0.17
29,49=0,43
5
19.59110.00
24.65::0.87
0..38:00.45
19,59:10.000
9,30=00228
SVIIN
(Suhset 12K)
19.59110.00
28.61100.18
0.666
19.59.10.00
10.74.10.37
16.22.10.35
19:59:40.00 10
30.48:0..25
10,15:20.25
19.59:1:.000
11.62:00.52
13, 13.3000.30
3
57.07 10.41
7.17.10.52
22.83:10.76
34.92.10.88
0.22
20.20.1105
4
58.50-1:0.09
4.74:10448
31,74 144
21. 2080
3.74
25.14
54,48=10.97
11.60=0.277
02.68=+0.6
19,59=
3.85=0.23
20.75=2.38
SVHN
8
19.59::0.00
17.56:0.111
0.996-10.96
19,59:t0.00
0.13
0.3
(Subset 12K)
19.50=00.00
21.61=0.51
01.98:00.49
19,59
5 5.94=0.37
0.08
Svevisbbe 1261, 8255
(Sabet 120, 8225
CMM (eteet 1201 41222
CMB-5 SWNN
5500
25030
18:00
5205
150.00 Tuthing Rertiii
15000
20:00
5.000
250
ATThaning
Figure 2: The robust test accuracy curves of finite-width MLP-S/CNN-5 along AT on SVHN. The robust test accuracy of infinite width DNNs learned by NTK and Adv-NTK are also plotted.
robust test accuracy as that of AT. However, we also notice that in the case "CNN-x + SVHN". AT is significantly better than Adv-NTK. We believe it is because the non-linearity of finite-width DNNs in AT can capture additional robustness, which will be left for future studies.
Besides, from Fig. 2, we find that in most of the cases, the width DNN is not trainable in AT. However, in the case of CNN-5 with radius p = 4/255, the finite-width DNN does not suffer from robust overfitting and its robust test accuracy continuously increases along AT. We deduce that this because the number of training iterations (which is 20, 000) is too short for this experiment that it almost acts like an carly-stop regularization, which is shown to be effective in mitigating robust overfitting (Rice et al., 2020). Furthermore, is worth noting that the robust overfitting phenomenon on the SVHN dataset has already been observed by Rice et al. (2020) (see Figure 9 in their paper).
G APPLYING ADV-NTK TO LARGE DNNS
This section discusses practical challenges and our preliminary results in applying Adv-NTK to common large DNNs.
G.1 PRACTICAL CHALLENGES TOWARD LARGE DNNS
Our experiments in Section 6 only adopted MLPs and CNNs but not common larger DNNs like VGGs (Simonyan & Zisserman, 2014) and ResNets (He et al., 2016). The reason is that large DNNs usually adopt global average pooling (GAP) layers in their architectures. Although is confirmed that GAP layers can effectively improve the generalization ability of NTK models, accurately cal- culating NTK matrices that involve GAP layers would consume an extremely large amount of GPU memory and also lead to unbearable time usage (Arora et al., 2019; Han et al., 2022).
To improve the calculation efficiency of GAP layers, existing NTK literature has adopted Monte Carlo-based techniques to estimate the output of GAP layers (Novak et al., 2019) and made it af- fordable for vanilla NTK experiments. However, adapting these Monte Carlo-bar based techniques into AT setting is not trivial since our setting needs to further analyze the process of adversarial perturbation, and a series of mathematical and engineering challenges would arise during this adap- tation. Therefore, we will leave the practicality problem of Ady-NTK in future research.
45

---

Published as a conference paper at ICLR 2024
Table Robust test accuracy (%) of different ResNet models. Every experiment is repeated 3 times. A high robust test accuracy suggests a strong robust generalizability.
Adv. Acc. (lai P 4/253)(88 (8)
Adv. Ace. (looi p == 8/255) (18)
Dataset
Architecture
AT
NTK
Adv-NTK (Ours)
AT
NTK
Adv-NTK (Ours)
CTFAR-10 (Subset 12K)
ResNet-18
28.01 9:0.9
07.09=:0.25
28.43-10.27
15.11
4.07 9.64::0.12
21.46:100.47
ResNet-34
26.61=1..08
25.42=0033
29.19=0064
16.11
21,00=00.2
SVHN (Subset 12K)
ResNet-18
48.10:1:108
04.18:00.34
02.70:10.26 34.08=0.299
30.3611 1.92
10.05:10.30
13.96:10.16 16
ResNet-34
48.04:::0999
32.69=0.43
26.94=2.33
13.01 19
15.19:00.26
126,
X5- (0urat
AT ming Ioretie
AThaiing teniles
2 Phating bentos
AT The ming Inrette
(a) Results on CIFAR-10 10.
1/% Vix (parg)
Adw NTC (16m1)
As vic sharo
Altaaiing Soorli
Faaking Sectaa
(b) Results on SVHN.
Figure 3: The robust test accuracy curves of ResNet models along AT. The robust test accuracy of infinite width DNNs learned by NTK and Adv-NTK are also plotted.
G.2 EXPERIMENTS ON RESNETS
Although still could not address the practical challenges induced by GAP layers, in this section we present the experiments for ResNets that are not using GAP layers.
Models. We adopt two types ResNet (He et al., 2016), ResNet-18 and ResNet-34, in our exper- iments. For finite-width models, GAP layers are adopted as that in standard ResNet architectures. For NTK models, we replace all GAP layers with flattening layers reduce GPU memory usage.
Experiment setup. (1) For Ady-NTK, the learning rate is set as: 5 x 10-5 for ResNet- 18 on SVHN, 10-6 for 18 on CIFAR-10, 10-8 for ResNet-34 on SVHN, and 10 10 for ResNet- 34 on CIFAR-10. Other settings follow that in Appendix F.3. (2) For NTK, all settings follow Appendix F.3. (3) For AT, the learning rate for both ResNet- and ResNet-34 on CIFAR-10 is set as 0.01. Other settings follow that in Appendix F.3.
Results. The robust test accuracies of ResNet models trained with different methods are reported in Table 5. The curves of robust test accuracy of finite-width ResNet models along AT are plotted in Fig. 3. From the results, one can find that Adv-NTK can effectively improve the robustness of infinite-widhe ResNet models. Mcanwhile, achieved stronger robustness than infinite-width ones. We think this due to the use of GAP layers in finite-width ResNet models, and will leave the application of GAP layers in large-scale Adv-NTK for future studies.
the SVHN dataset, finite-width ResNet models
46


Reviews:
[{"review_id": "ACEACARbJP", "reviewer": "Reviewer_S6eo", "summary": "This paper studied the robust overfitting issue in adversarial training. Specifically, the author studied the training dynamics of adversarial training under the NTK regime. Theoretical results show that after long training the term that captures the robustness will fade away and the trained network will degenerate to the network with standard training. The author further proposed an algorithm for adversarial training under the NTK regime and conducted experiment. Results show that the proposed algorithm outperforms standard adversarial training and vanilla NTK.", "questions": "Please refer to the \"weakness\" section", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper provides a novel theoretical view in robust overfitting in adversarial training, and the theoretical analysis gives an intuition on why adversarial training fails on a simplified regime (NTK).\n2. The paper further proposed an algorithm applicable to NTK models. Experiment results aligns with the theoretical conclusion in the paper.", "weaknesses": "My concerns are listed as the follows:\n\n1. The proposed algorithm can only work under NTK regime. Though the corresponding results can serve as an empirical evidence of the theoretical conclusion, it seems that the proposed algorithm has limited practical application.\n2. The assumption in the paper seems too strong comparing with practical setting. The author are encouraged to consider more practical setting like GD and cross entropy loss. \n3. In the studied setting, the scale of pertubation is also related to the norm of $\\partial_x \\mathcal{L}$, rather than depending on $S$, which introduces a discrepancy between the setting studied and real-world setting.\n4. Some missing references in convergence of DNN: [1], [2], [3]\n\n[1]Li, Yuanzhi, and Yingyu Liang. \"Learning overparameterized neural networks via stochastic gradient descent on structured data.\" Advances in neural information processing systems 31 (2018).\n\n[2]Zou, Difan, et al. \"Gradient descent optimizes over-parameterized deep ReLU networks.\" Machine learning 109 (2020): 467-492.\n\n[3]Allen-Zhu, Zeyuan, Yuanzhi Li, and Zhao Song. \"A convergence theory for deep learning via over-parameterization.\" International conference on machine learning. PMLR, 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HKwygi9PSy", "reviewer": "Reviewer_gmGK", "summary": "The paper explores the issue of robust overfitting in deep neural networks (DNNs) during adversarial training (AT). It extends neural tangent kernel (NTK) theory to explain this phenomenon for infinite width deep networks, showing that a wide DNN under AT can behave like a linearized DNN, leading to AT degeneration over time (assuming squared loss). To address this, the paper introduces Adv-NTK, an novel AT algorithm for infinite-width DNNs, designed to enhance network robustness. The effectiveness of Adv-NTK is demonstrated through experiments on real-world datasets, establishing its real potential in improving DNN robustness against adversarial attacks.", "questions": "It would improve the paper if bound on the learning rate can be provided with respect to its training (or maybe some empirical results towards that).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper attempts to tackle an important problem of overfitting in adversarial training from a theoretical perspective, which should be relevant to the broader community.\n\nThe empirical validation of the Adv-NTK algorithm using real-world datasets like SVHN and CIFAR-10 enhances the quality of the paper. This empirical approach ensures that the theoretical findings are not only sound in theory but also applicable and effective in real-world scenarios.", "weaknesses": "Its not clearly under what conditions the small step size can lead to linearization of the adversarial training of DDN.\n\nIn the proof, it does not try to find efficient direction, does that make any difference on the proof ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1rvf6xFXfQ", "reviewer": "Reviewer_s7R7", "summary": "This paper studies the problem of robust overfitting in adversarial training using the Neural Tangent Kernel (NTK). First, the authors extend the theoretical framework of NTK to adversarial training, introducing an adversarial regularization kernel and demonstrating that adversarially trained DNNs can be well approximated by their linearized DNNs. They then derive the closed-form dynamics of adversarial training for the linearized DNN and uncover a phenomenon called adversarial training degeneration: prolonged adversarial training leads to the degradation of the wide DNN to a state similar to that of a DNN with normal training, which results in robust overfitting. Based on these theoretical findings, the authors propose an adversarial training algorithm called Adv-NTK for infinite-width DNNs, and experimental results show that it can enhance the robustness of infinite-width DNNs to a level comparable to that of finite-width DNNs.", "questions": "Are the results in Section 4 of this paper valid for adversarial training of any intensity? Intuitively, if the intensity of adversarial training is too high, some of the results in Chapter 4 may not be valid.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper provides a linear model-level explanation of the adversarial training degeneration phenomenon. The designed Adv-NTK algorithm enables infinite-width NTK models to achieve robustness similar to MLPs through adversarial training.", "weaknesses": "1: This paper focuses on linearized models but lacks a detailed explanation of why linearization approximation is applicable. Theorem 1 demonstrates the convergence of two kernels for initialization. However, the properties that remain constant over time appear to be submerged in Appendix C.2. It is recommended that the authors include an informal presentation of the results from Appendix C.2 between Theorems 1 and 2 and provide corresponding discussions.\n\n2: Section 5.1 lacks a discussion regarding the impact of $\\eta S$ on the adversarial training degeneration phenomenon.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "c2yWCY59S8", "reviewer": "Reviewer_4ePw", "summary": "•\tThis paper theoretically explores the robust overfitting of Adversarial Training (AT). Specifically, it demonstrates that Deep Neural Networks (DNNs) trained with AT can be represented from the perspective of Neural Tangent Kernel (NTK). The paper further formulates the dynamics of Adversarial Training. Based on this formulation, it explains the reasons behind the occurrence of robust overfitting and proposes an algorithm, termed ADV-NTK, that can prevent robust overfitting in a manner akin to early stopping.", "questions": "•\tIn the above part.\n\n[Overall]\n•\tIf the authors provide further experiments on Adv-NTK and supplementary explanations for the justification for learning rates, I agree that this paper is accepted.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "•\tThe paper tackles a critical and pressing issue: Overfitting in Adversarial Training.\n\n•\tThe contribution of paper is based on a theoretically solid proof. They also offer a detailed and meticulous explanation enhancing the understandings.", "weaknesses": "•\tThe paper is written based on the logical flow of formulation and comparably not focusing on the motivation of the paper. For better readability, it seems to be a need for more appeal on how important task the paper tries to solve and what is the contributions of the paper.\n\n•\tIn context of DNN-NTK, they replace the constrained-spaces condition with an additional learning rate term to control the strength of adversarial examples. (in Equation 7) However, unlike many attack mechanisms, it doesn't efficiently find a significant direction of attack. Despite this, does believe that the derived formula's proof is still not too loose?\n\n•\tThe additional experiments are needed. In specific, it would be better to empirically verify 1) whether theoretically proven properties actually happen similarly in real-world dataset and 2) how much the robust overfitting problem has been addressed with the proposed Adv-NTK. For instance, tracking the performance (or loss) trend across iterations between vanilla AT and Adv-NTK.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lL4aVeQUuI", "reviewer": "Reviewer_edb8", "summary": "This paper applied neural tagent kernel techniques into adversarial training setting and proves that adversarial trained DNN can be approximated by a linearized DNN. For square loss it reveals a AT degreneration phenomena so that explains robust overfitting. The paper designed an algorithm AdvNTK based on the theoretical results.", "questions": "This paper focuses on regression setting with squared loss. I’m wondering if the idea can be generalized to classification setting.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I like the idea of analyzing robust overfitting from the time-dependent regularizer matrix that derived from adversarial NTK.", "weaknesses": "Adversarial trained DNN can be approximated by linearized DNN only when the perturbation size considered is small, however, the paper seems not give a quantitive result regarding how small it should be. I understand that the author using attack learning rate for a total of time S. Yet it’s unclear how large the attack rate is, as if the attack learning rate is infinitesimal, then the perturbation size is so small, and it’s unclear for me whether such adversarial training algorithm has any generalization guarantee in terms of robustness.\n\nMoreover, I’m not sure why it’s interesting to study adversarial training within the NTK regimes, as in [1] show when the network is close to initialization, there’s no robust network at all.\n\nIn the proof of theorem 2 the dependency of polyt seems odd to me, as polyt depends on the norm of W_t, which can go to infinity. I understand that for neural tagent kernel the network width does not move far from initialization so you can argue norm of W_t is bounded,  as theorem Lemma C.5, yet this theorem’s proof also depends on polyt. Therefore the current presentation of omiting dependency on the norm of W_t, nor of x_t seems to hide something in the proof.\n\nWhat’s the relationship between the experiment vs. theorems? How does the experiment validate theorems? The robust accuracy of both SVHN and CIFAR10 seems extremely lower than normal adversarial training. Is it because of the network architecture? Why cannot use standard architecture such as ResNet that people commonly use in practice? Can the author provide any simple experiment to confirm the AT degeneration phenomenon? In fact, it’s unclear to me the difference between this wording vs robust overfitting, and if they are the same thing then there’s no need to use a different paraphrase.\n\nIn terms of the writing, I think the author should put more discussion on the theorems, explain, and provide intuition.\n\n[1] Wang, Y., Ullah, E., Mianjy, P., & Arora, R. (2022). Adversarial robustness is at odds with lazy training. Advances in Neural Information Processing Systems, 35, 6505-6516.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)