On the (Non-)Robustness of Two-Layer Neural Networks in Different Learning Regimes
Authors: Elvis Dohmatob
Alberto Bietti
Venue: Submitted to ICLR 2023 (2023)
Keywords: robustness
adversarial robustness
over-parametrization
lazy training
parent-student
regression

Abstract: Neural networks are known to be highly sensitive to adversarial examples. These may arise due to different factors, such as random initialization, or spurious correlations in the learning problem. To better understand these factors, we provide a precise study of the adversarial robustness in different scenarios, from initialization to the end of training in different regimes, as well as intermediate scenarios where initialization still plays a role due to “lazy” training. We consider over-parameterized networks in high dimensions with quadratic targets and infinite samples. Our analysis allows us to identify new tradeoffs between approximation (as measured via test error) and robustness, whereby robustness can only get worse when test error improves, and vice versa. We also show how linearized lazy training
regimes can worsen robustness, due to improperly scaled random initialization. Our theoretical results are illustrated with numerical experiments.

Under review as a conference paper at ICLR 2023
ON THE (NON-)ROBUSTNESS OF TWO-LAYER NEURAL NETWORKS IN DIFFERENT LEARNING REGIMES
Anonymous authors Paper under double-blind review
ABSTRACT
Neural networks are known to be highly sensitive to adversarial examples. These may arise due to different factors, such as random initialization, or spurious corre- lations in the learning problem. To better understand these factors, we provide a precise study the adversarial robustness different scenarios, from initializa- tion to the end of training in different regimes, as well as intermediate scenarios, where initialization still plays a role due to "lazy" training. We consider over- parameterized networks in high dimensions with quadratic targets and infinite samples. Our analysis allows us to identify new tradeoffs between approximation (as measured via test error) and robustness, whereby robustness can only get worse when test error improves, and vice versa. We also show how linearized lazy training regimes can worsen robustness, due to improperly scaled random initialization. Our theoretical results are illustrated with numerical experiments.
INTRODUCTION
Deep neural networks have enjoyed tremendous practical success in many applications involving high- dimensional data, such images. Yet, such models are highly sensitive to small perturbations known as adversarial examples (Szegedy et al., 2013), which are often imperceptible by humans. While various strategies such adversarial training (Madry et al., 2018) can mitigate this vulnerability empirically, the situation remains highly problematic for many safety-critical applications like autonomous vehicles and health, and motivates a better theoretical understanding of what mechanisms may be causing this.
Various factors are known to contribute adversarial examples. linear models, features that are only weakly correlated with the label, possibly in a spurious manner, may improve prediction accuracy but induce large sensitivity adversarial perturbations (Tsipras et al., 2019; Sanyal et al., 2021). On the other hand, common neural networks may exhibit high sensitivity to adversarial perturbations at random initialization (Simon-Gabriel et al., 2019; Daniely & Shacham, 2020; Bubeck al., 2021). While such settings already capture interesting phenomena behind adversarial examples, they are restricted to either trained linear models, or nonlinear networks at initialization. Trained, nonlinear networks may thus involve multiple sources of vulnerability arising from initialization, training algorithms, as well as the data distribution. Capturing the interaction between these different components is of crucial importance for more complete understanding of adversarial robustness.
In this paper, we study the interplay between these different factors by analyzing approximation (i.e how well the model fits the data) and robustness properties (i.e the sensitivity of the model's outputs w.r.t perturbations in test data) of two-layer neural networks in different learning regimes. We consider two-layer finite-width networks in high dimensions with infinite training data, asymptotic regimes inspired by Ghorbani et al. (2019). This allows us to focus on the effects inherent to the data distribution and the inductive bias of architecture (choice of activation function, number of hidden neurons per input dimension, etc.) and training algorithms, while side-stepping issues due to finite samples. Following Ghorbani et al. (2019), we focus on nonlinear regression settings with structured quadratic target functions, and consider commonly studied training regimes for two-layer networks, namely (i) neural networks with quadratic activations trained with stochastic gradient descent the population risk which finds the global optimum; (ii) random features (RF, Rahimi & Recht, 2008), (ii) neural tangent (NT, Jacot et al., 2018), as well as (iv) "lazy" training (Chizat et al., 2019) regimes for basic RF and NT, where we consider first-order Taylor expansion of the

---

Under review as a conference paper at ICLR 2023
network around initialization, including the initialization term itself (in contrast to the standard RF and NT regimes which ignore the offset due to initialization). Note that, though the theoretical setting is inspired by Ghorbani et al. (2019), our work differs from theirs in its focus and scope. Indeed, we are concerned with robustness and its interplay with approximation, in different learning regimes, while they only concerned with approximation. We also note that the lazy/linearieed regimes we study as part of this work were not considered by Ghorbani et al. (2019), and help us highlight the impact of initialization on robustness.
Note that unlike the other regimes, SGD exhibits a kind of feature learning, whereby the first layer weights are learning specific directions by approximating the matrix B. In particular, this involves non-trivial feature selection via non-linear learning, while the other regimes (RF and NT) are linear estimators on top of non-linear but fixed features.
Main contributions. Our work establishes theoretical results which uncover novel tradeoffs be- tween approximation (as measured via test error) and robustness that are inherent to all the regimes considered. These tradeoffs appear to be due to misaligmment between the target function and the input distribution (weight distribution) for random features (Section 4), or the inductive bias of fully-trained networks (Section 3 and Appendix E). We also show that improperly scaled random initialization can further degrade robustness in lazy/linearized models (Section 5), since the resulting models might inherit the nonrobustness inherent to random initialization. This raises the question of how small should the initialization be in order enhance the robustness of the trained model. Our theoretical results are empirically verified with extensive numerical experiments on simulated data.
The setting of our work is regression in a student-teacher setup where the student is a two-layer feedforward neural network and the teacher is a quadratic form. We assume access to infinite training data. Thus, the only complexity parameters are the coefficient matrix of the teacher model, the input dimension d and the width of the neural network m, assumed to both "large" but proportional to one another. Refer to Section 2 for details. In Appendix I, we also show similar but weaker trade-offs for arbitrary student and teacher models. The infinite-sample setting allows us to focus the effects inherent to the data distribution and the inductive bias of architecture (choice of activation function) and different learning regimes, while side-stepping issues due to finite samples and label noise. Also note that in this infinite-data setting, label noise provably has no influence on the Iearned model, in all the learning regimes considered. The observation that there is tradeoff between robustness and approximation, even in this infinite-sample setting, is one of the surprising findings of our work. This complements related works such as (Bubeck et al., 2020b; Bubeck & Sellke, 2021), which show that finite training samples with label noise is a possible source of nonrobustness in neural networks.
Related works. Various works have theoretically studied adversarial examples and robustness in supervised learning, and the relationship to ordinary test error accuracy. Tsipras et al. (2019) consid- ers a specific data distribution where good test error implies poor robustness. Shafahi et al. (2018); Mahloujifar et al. (2018); Gilmer et al. (2018); Dohmatob (2019) show that for high-dimensional data distributions which have concentration property (e.g., multivariate Gaussians, distributions satisfying Sobolee incqualities, etc.), an imperfect classifier will admit adversarial examples. On the other hand, Yang al. (2020) observed empirically that natural images well-separated, and so locally-lipschiz classifies shouldn't 't suffer any kind of test error vs robustness tradeoff. How- ever, gradient-descent is not likely to find such models. Our work studies regression problems with quadratic targets, and shows that there are indeed tradeoff's between test error and robustness which are controlled by the learning algorithm regime and model. Schmidt et al. (2018); Khim & Loh (2018), 8); Yin et al. (2019); Bhattacharjee et al. (2021); Min et al. (2021b;a study the sample complexity of robust learning. In contrasts, our work focuses on the case of infinite data, so that the only complexity parameters are the input dimension d and the network width m.
Gao et al. (2019); Bubeck et al. (2020b); Bubeck & Sellke (2021) show that over-paramette veerpaaraettiizaaioon may be necessary for robust interpolation in the presence of noise. In contrast, our paper considers a structured problem with noiseless signal and infinite training data, where the network width m and the input dimension d tend to infinity proportionately. In this under-complete asymptotic setting, our results show a systematic and precise tradeoff between approximation (test error) and robustness in different learning regimes. Thus, our work nuances the picture presented by previous works by exhibiting a nontrivial interplay between robustness and test error, which persists even in the case of infinite training data where the resulting model isn't affected by label noise.
2

---

Under review as a conference paper at ICLR 2023
Dohmatob (2021); Hassani & Javanmard (2022) study the tradeoff's between interpolation, predictive performance (test error), and robustness for finite-width over-parameterized net- works in kernel regimes with noisy linear farget functions. In contrast, we consider structured quadratic target functions and compare different learning settings, including SGD optimization in non-kernel regime, well lazy/linearized models.
Robustness has also been studied from a causality perspective. For example, Rothenhausler et al. (2021) studies tradeoffs between test error and robustness in linear regression under distributional shifts on the marginal distribution of the covariates.
We provide more detailed discussion of the related work in Appendix A.
Remark 1.1. Note that the term "over-parrmetricatto""" is not used our paper in the same sense as in Bubeck et al. (2020b); Bubeck & Sellke (2021); Hassani & Javanmard (2022). In those works, the setup is finite samples (n <, 0o), and over-parametrization means that m. is substantially larger than n/d, where d is the miput-dinension, and m is the network with (i.e number of neurons in the hidden layer). In our work, we focus on the infinite-sample case (n = =0),, and over-parametiization means m/d large. Finally, the findings of Bubeck al. (2020b); Bubeck & Sellke (2021) -namely, that over-parametrization is beneficial for robustness, and of Hassani & Javanmard (2022) -namely, that over-paramelrization is detrimental robustness, are nuanced by Zhu et al. (2022) which shows that as the width m of a neural network is increased, there transition from over peee-parametiizttoon being detrimental, to being benificial for robustness. More precisely, they derived upper-bounds for robustness error which show that there critical value ma such that the robustness error is an hurts) and decreasing function of width in the interval (ma, oo) (i.e overrparanttiitttoonn becomes beneficial). Overall, the exact role of over--oranne purammaarmttiiiatiion in robustness remains partly unclear, even though progress is being made on the subject.
increasing function of width the interval [1, mo)
PRELIMINARIES
Notations. We use standard notations in our manuscript. A cheat sheet is provided in supplemental / appendix.
2.1 THE TEACHER MODEL: A QUADRATIC FORM
We consider the following regression setup proposed by Ghorbani et al. (2019). Let be a fixed d x d psd matrix and let bp E IR be a fixed unknown scalar. Consider the quadratic teacher model
fx(x) = x Bx + bo, for any x E Rdd
(1)
We assume the input data is distributed according to (0, Ia), the standard Gaussian distribution in dimensions. Thus, the structure of the problem of learning the teacher model f. in (1) is completely determined by the unknown d x d matrix B. We assume an idealized scenario where the learner has access to infinite number of iid samples of the form (x., fxx) width
P. = N(O, Ta). For simplicity of analysis, we will further assume as in (Ghorbani et al., 2019) that the teacher model f. defined in (1) centered, i.e (0 (x) = 0. This forces the offset bo (B).
2.2 THE STUDENT MODEL: TWO-LAYER NEURAL NETWORK
Consider two-layer student neural network
m
fw.z,(s)) (==== Σ 20 T wy) +
where m is the network width, i.e., the number of hidden neurons each with parameter vector wy E IRd, output weights (21,..., 2m) RM and activation function IR - R. We define W as the m x matrix with jth row wy. The scalar s is an offset which we will sometimes set to 0, in which case we will simply write fw.z, fw. Note that the teacher model f. is itself a two-layer
3

---

Under review as a conference paper at ICLR 2023
neural network with output weights fixed to 1, quadratic activation function, and d hidden neurons with parameters W. : B1/2, where B1/2 is the unique psd matrix such that (B!/2)2 B.
The aim of learning is to approximate the teacher model f. as closely as possible with the student model fW,,.s. We will consider the following nigh-dimensional setup:
Infinite training data, wherein the sample size n is equal to oo, i... the learner has access to the entire data distribution, allowing us to step-aside issues linked with finite samples.
Proportionate scaling of input dimension d and student network width m, wherein and m are finite, and large of the same order, i.e..
m, d 0o, m/d + p E (0, 20).
The parameterization rate p (which corresponds to the number of hidden neurons per input dimen- sion), will play erucial role in analysis. The case p 1 corresponds to ander--prametrization while > 1 corresponds to over paeeppaaaattiiitioonn Occasionally, we will also consider the extreme over-paramettrization regime corresponding to p 1, more precisely, the limiting case p -+ oo.
2.3 METRICS FOR TEST ERROR AND ROBUSTNESS
Test error. The test / approximaaion error of a student model R + IR is defined by (f) := ||f fulliz(r.) = (f(x) fx))))
(4)
where Pa is the distribution of the features. (4) measures how well the student f approximates the teacher model f.. Except otherwise explicitly stated, this article we will always consider the isotropic case where the distribution of the features is Pa = (O, Ia), as in Ghorbani et al. (2019).
will be instructive to compare the test error of f to that of the null predictor which outputs on every input, namely [/ Thus, consider the normalized test error,
(5) This quantity was studied in Ghorbani et al. (2019) where explicit analytic formulae were ob- tained for two-layer networks in various regimes of interest: networks fully trained by stochastic gradient-descent (SGD) the population risk, random features (RF), and neural tangent (NT). We shall consider these same regimes and establish tradeoffs between test error and robustness of the corresponding models. This will paint a picture complementary Ghorbani al. (2019).
Evest (f) == Etest 11
Mcasure of robustness / sensitivity. We will measure the robustness of a smooth student model f: IRd R (e.g., the two-layer neural net (2)) by what we call its robustness error, defined as the square-root of its Dirichlet energy Exob (f) w.r.t. to a random test point x ~ Ps, that is
ETob (fo == V (l Ep, az)
(6)
Smoothness here is in the very general sense of Gigli & Ledoux (2013, Section 4.1) with euclidean structure. The smaller the value of Grobs() the more robust / less sensitive f is to changes in a measure of robustness in Appendix D, where we will link it to more classical notions of robustness error (Madry et al., 2018). In particular, the teacher model has Erob (f.) 4 B l. Finally, note that, measures of robustness based on notions of sensitivity have been considered in other works like Bubeck et al. (2020b); Bubeck & Sellke (2021) for regression, and Wu et al. (2021) for classification settings.
test data point, on average. We justify the choice of this quantity
It will be convenient to compare the robustness of a student model f to that of the baseline quadratic teacher model f+ defined in (1). To this end, consider the normalized robustness error f defined by
Frob(()) == Grob (f)
(7)
which measures the relative robustness error of the student. The objective of our paper is to study the quantity (f) (f) for neural networks (2) in various regimes in the limit (3), and put to light interesting
phenomena. In particular, we will establish tradeoff's between test error and robustness error, in the form of a nontrivial relationship
Exest (f) + (f) =1 1,
(8)
for different learning regimes. This paints picture complementary to Ghorbani al. (2019).
4

---

Under review as a conference paper at ICLR 2023
Remark 2.1. Note that it might be tempting thing that
If - fAlleaeP, =0 [V (AALL()))
(9)
Such an implication would automatically lead to (at least) heuristic explanation of our tradeoff's (8). However, (9) is false in general. Indeed, a smooth function (small || fll(r))) can be approximated very well in Lt² by functions by very rough functions (large [ This point is elaborated in Appendix K. To establish our tradeoffs, exploit the fine structure of two-layer neural networks in the different learning regimes considered.
3 RESULTS FOR TWO-LAYER NEURAL NETWORKS TRAINED VIA SGD
Consider student neural network model with quadratic activation FSGD F. - R. i.
fSGD(Z) == x T wx) +
(10)
j=1
Here, W = (Wi,.... Wm) E R is matrix of learnable parameters (one per hidden ncuron), and E R a learnable offset. The output weights vector fixed to 1 == (l..... .......)) 1), while W and s are optimized via SGD (hence the subscript), where each update is on single new sample point. It is shown in Theorem 3 of Ghorbani et al. (2019) that if W. E Rmxxd is the matrix of hidden parameters after / steps of SGD, then in the limit (3), the matrix W.W, E Rm=x converges a.s to the best rank-m approximation of B. Thus, by continuity of matrix norms, we deduce that [|WW,," || converges a.s to [B p. in the infinite data limit +
Combining with Lemma G. establishes the following asymptotic formula for the (normalized) robustness of the resulting model fSGD, in the high high-dimensional limit (3).
| B
IMAd \B(
Theorem 3.1. In the limit (3), it holds that Trob EJst(J))D)
a.e.
S with
ΣS (B)2
equality iff (BankBB)= S m. In particular, p p 2 1, then in the limit (3), it holds that Too (JSGD) 0.
Tradeoff' approximation and robustness. We see from the above theorem that if m 2 raak (B), then the robustness error for the learned student converges to that of the true model if m 2 d, namely (foD()) & Σ AB = Erob (f.). This is the case m 2 d, for example. Otherwise (i.e m < rrank( (B)) then the limiting value of Srob Grob (/SCD) can be arbitrarily less than (rot)()))) i.e. the learned student will be much more robust (i.e., stable) than the ground truth model. Comparing with Theorem 3 and Proposition of Ghorbani et al. (2019), we can see that any decrease in robustness error of the learned student (compared to the teacher model) and vise versa. Indeed, it was shown in that paper that the normalized test error ētest (JSCD) verifies
the expense of increased test error.
Frest (JsG)) - - lim
B12 in the limit (3)
(11)
Combining with our Theorem 3.1 above, we deduce that
Frest (fsGD) + (foCn))) P in the limit (3).
(12)
The above formula highlights tradeoff between test error and robustness error. Thus, we have identified a novel tradeoff between approximation and robustness for the neural network model (2) trained via SGD. In the sequel, we shall establish such tradeoffs for other learning regimes.
4 RESULTS FOR THE RANDOM FEATURES MODEL
Consider the two-layer model (2) with hidden neuron parameters W1,..., t0m sampled iid from a d-dimensional multivariate Gaussian distribution N(0, I') with covariance matrix I'. We denote this so-called random features (RF) student model fRF, defined by
(2)()) SWWERE (x) = (Wr:).
(13)
5

---

Under review as a conference paper at ICLR 2023
where 2RF E R solves the following linear regression problem
arg min N(,, ((Wx) fz))) # Rm
(14)
It is easily seen that for r ~ (0, Ia). one has 2RF = U- u, with
U, = E., (o W3 ( wx)) Vj, E [mm],
(15)
1/j = (f) wy)] Vj [m].
(16)
The covariance matrix I' encompasses the inductive bias of the neurons at initialization to different directions feature space. Define the alignment a = a r) of the hidden neurons to the task at hand, namely learning the teacher model [.. as follows
Lr (BT
a =
B || - 1.
(17)
As we shall see, the alignmeig a plays erucial role in the dynamics of prediction performance (test error) and robustness JRF-
4.1 ASSUMPTIONS AND KEY QUANTITIES
As in Ghorbani et (2019), we will need the following mild technical conditions on r. Condition 4.1. The covariance matrix satisfies: (A) tr(T) 1 and d ||T|lop= O(1). (B) The empirical eigenvalue distribution of d converges weakly probability distribution D on R..
This condition quite reasonable, and moreover, allows us to leverage standard tools from random matrix theory (RMT) in our analysis. We will also need the following technical condition on the activation function a.
Condition 4.2. is weakly continuously-diffreentte
and satisfies the growth condition a at)) S
Cpe for some Co > and e1 1, and for all I. R. Moreover, a is not a purely affine function.
The above growth condition is a classical condition usually imposed for the theoretical analysis of neural networks (see, e.g., Ghorbani et al., 2019; Mei & Montanari, 2019; Montanari & Zhong, 2020), and is satisfied by all popular activation functions used in practice. One of its main purposes is to ensure that all the Hermite coefficients (Ae) of the activation function exist. Refer to Section G.2 for precise definition of Hermite coefficients. We will also need the following condition.
Condition 4.3. (A) Ao == Ao(o) 0. (B) X2 == >2(0) + O.
Part (A) of this condition was introduced by Ghorbani et al. (2019) to simplify the analysis of the test error of the random features model SRF. Part (B) ensures that the random features model SRF does not degenerate to the null predictor.
Definition 4.1. With ~ N00, 1). define the following scalars
A = E [[) 27. K := 0-=--/11 22 + := A2tr(BT)
(18)
X = Ejo
- - k
x211
These coefficients will turn out to "sufficient statistics" which will completely capture the influence of activation function on the robustness of the random features model fnr. Note that by construction, X, K, X, and ne' are nonnegative. Now, consider the random psd matrices Ag and Do defined by
Ag = Xlm + 270, Do == Xmm + (n//d+ x7)
(19)
with e = WWT E mm These matrices appear upon linearizing the expressions for the test error and the robustness error of the RF model, using RMT techniques from El Karoui (2010). By employing the so-called Silverstein fixed-point equation (Silverstein & Choi, 1995; Ledoit & Péché, 2011; Dobriban & Wager, 2018), one can show that there exist positive constants t and th such that
tr(A5') )/d 5 2h1 (rA 2 " the in the limit (3).
(20)
Moreover, the the 's only depend on (i) the parametrization rate p. and (ii) the limiting eigenvalue distribution D of the rescaled covariance matrix d I of the hidden neurons initialization. Also, since Ā and X are strictly positive (thanks to Condition 4.2), so are the tha 's by definition of Do and Ao in (19). These scalars together with those defined in (18) will play crucial role in our analysis.

---

Under review as a conference paper at ICLR 2023
4.2 TEST ERROR / PREDICTION PERFORMANCE IN RANDOM FEATURES REGIME
We recall that the (normalized) test error éost (/RF) of the random features model /RF was completely analyzed in Ghorbani et al. (2019). Indeed, the following was established that
(
1/17
Eeest (frr) =
| (2ke1 +2) + (d.((1), in the limit (3).
(21)
See Theorem 1 of the said paper. Thus, the normalized test error only depends on the aspect ratio the limiting spectral distribution D of d I, and the scale parameters (X, k. T) defined in (18). It was further that, if the task aask-alignment a of the hidden neurons defined in (17), admits limit a:so when d + co, then w.p
lim
lim Exest (fur) = 1 a²
(22)
P-+00
m000+00
m//d-p
Thus, (21) predicts that the normalized test error ētest (JRF) vanishes if (i) I x B and (ii) the number of neurons per input dimension m/d diverges, corresponding to extreme over over-parametrizatoon
4.3 ANALYSIS OF ROBUSTNESS IN RANDOM FEATURES REGIME
The following result establishes analytic formula for the robustness in the RF regime.
Theorem 4.1. Consider the random features model fRE (13), with covariance matrix I' satisfying Condition 4.1 and activation function satisfying Conditions 4.2 and 4.3.
(A) In the limit (3), we have the following approximation
72(2k00 + v22 |B 2)2
(roD(JRF)
+ 0a.((1).
(23)
(B) Moreover, if lim a = Osgor then lim lim Erob = azo wap 1. In particular, for the p-000 m.d-ioc
d-se0
m/dd>p
optimal choice ofT in terms of test error, namely I x B, one has lim lim (ob((ar) = 1 w.p 1.
p-oco m.00+00
m/d->p
Thus, the robustness only depends the aspect ratio P. the limiting spectral distribution 'D of dl T (via ti and v and the scale parameters defined in (18). The theorem is proved in the Appendix G.4.
Tradeoff between approximation and robustness. We deduce from the above theorem that in the limit (3), the random features model fRF is more robust (i.c., less sensitive to perturbations) than the teacher model f.. Interestingly, we see that this gap robustness between the two models closes with increasing alignment between the covariance matrix of the random features I and the coefficient matrix B. Comparing with (22), we obtain the following relationship (provided || > 1/m).
ētest (fRE) ro (fRF) & a² + a = 1, in the limit (3),
(24)
which trades-off between the normalized test error ētest (fnr) (defined in (21)) and the normalized robustness (JRP) of fRF. Thus, we have identified another novel tradeoff between the test error and the robustness in random features models.
Theorem 4. I and Corollary H.1 are empirically verified in Fig. 1. Results for the ReLU activation function are also shown. Notice the perfect match between our theoretical results and experiments.
5 NEURAL TANGENT REGIME
Consider two-layer network width output weights 29 fixed to 1, and hidden weight wy E Rd drawn from N (0,,1 1).. For the quadratic activation (t) = e², the neural tangent (NT) approximation (Jacot al., 2018; Chizat et al., 2019) w.r.t. the first layer parameters is given by
m
fw) R (x) + (vV w fw (x)
finit (x) +2
Σ (a (2fa;)) wy). TTy))
(25)
7

---

Under review as a conference paper at ICLR 2023
Quadratic
ReLU
1.0
Ecest )
Erall .)
0.5
Erestlaa
Erobllo)
0.0
500
1000
1500
500
1000
1500
width m
width m
Figure 1: Empirical validation of Theorem 4.1 and Corollary H.1. Showing (normalized) test test error Evest and robustness Eob of random features model (13) as a function of the number of the network width, for different choices of the covariance matrix I' of the random weights of the hidden neurons: the optimal choice I', x B and the naive choice Ia. Here, the input-dimension is 450 and the regularization À zero. Horizontal broken lines correspond to asymptotes at a at a where Otee- == lim tr( (BT)/ BII [[]]] is the level of task tusk-alignmen of the covariance matrix I' of hidden neurons, w.r.t learning the teacher model f. defined in (1). Broken curves are theoretical predictions, while solid curves correspond to actual experiments.
where finit is the function computed by the neural network initialization (see Appendix for details), and A = (a1..... am) = (Awi..... Awm) Rmxd is the change in W. We will see that the initialization term finit might have drastic influence on robustness of the resulting model.
5.1 NEURAL TANGENT APPROXIMATION WITHOUT INITIALIZATION TERM
We temporarily discard the initialization term fini (z) from the RHS of (25), and consider the simplified approximation
m fNT A:c) == Σ (x (ay)(x w)) c, j=1
(26)
where, WLOG, we absorb the output weights zj in the parameters aj in the first-order term. In (26), A E Rx and e E I are model parameters that are optimized. In terms of test error, let ANt and eNT be optimal fNT(; A, c). and let SNT = SNT(: ANT, CNT) for short. In Thm. 2 of Ghorbani et al. (2019), it is shown that the (normalized) test error of the linearized model fNT is given by
Ew (Erst (JNT)] (1 p) B) (1 p) B oa(1).
(27)
where B(B) == LrB)) (0, 1]. We now establish an analytic formula for the
robustness eтror of fxr.
Theorem 5.1. Consider the neural tangent model fNT in (26). In the limit (3) it holds that,
Ew (f(Ero = (e 222 - g/) o1()), where = min(p, 1).
(28)
Further observe that because < 3 < 1, the RHS of (28) further upper- upper-bounder bounded by p S with equality when 3 = 1 (e.g., for B x Ia). We deduce that in the NT regime, the student neural network at least as robust as the teacher model f.. Comparing with (27), we obtain the following tradeoff between test eπrоr and robustness, stated only for 3 for simplicity of presentation.
Corollary 5.1. If3 = 1 (iee,, if B x Ta), then in the limit (3), it holds that
Ew [iess (fNr) + Erob (fvr) = 1 + oa(1).
(29)
5.2 NEURAL TANGENT APPROXIMATION WITH INITIALIZATION TERM
We now consider the neural tangent approximation (25) without discarding the initialization term finit from the RHS of (25). Also, let 2 T be the output weights, drawn iid from ( 1/m) and frozen, and let Q be the x diagonal matrix with 2d as its diagonal. This corresponds to what
8

---

Under review as a conference paper at ICLR 2023
(fell
Rnol//oo
Fros (6m))
1000
1500
500
1000
1500
500
1000
1500
0
500
1000
1500
width
width
width m
witth
(a) NN at large random
(b) NT regime
(c) Lazy, small random (d) Lazy, large random init
Figure 2: Showing curves of (normalized) test error Etsst and robustness EDO for a two-layer neural
network in different learning regimes of the hidden weights. Here, the input dimension is d' = 450 and the width m sweeps a range of values from to 1500. Dashed curves correspond to theoretical predictions, while solid curves correspond to actual values observed in the experiment (5 runs). We use n = 10 training samples as a proxy for infinite data. The covariance matrix of the hidden neurons fixed
/d) la- For simplicity of this experiment, we also take the coefficient matrix B of the teacher model to proportional to l7. (c) "Small random init" means B is much larger than r. (d) "Large random init" means that B (1/d)Ta, and thus is of the same order as (in Frobenius norm). In this case, the initialization degrades the robustness, as predicted by Thm. 5.2. Note that, as predicted by Thm. 5.2, random initialization has no impact the test error of the NT approximation. Results (a) the neural network at initialization (Thm. E, and E.2) and (b) In the NT regime (Thm. 5.1) are also depicted for reference.
(L/vd)Ls, so that
could be referred to as lazy training Chizat et al. (2019) regime of the hidden layer. Let fNTIL (x; A, be RHS of (25),
JNTI(U;;
wy) == -W. (z) (=)T())))))))) (zT)x))a) a,) = finit (2) + SNT (z; c),
(30)
where finit (x) := E ww) TT QW defines the neural network at initialization.
Theorem 5.2. Suppose the output weights z initialization iid from (0, 4m. Then, in
the limit (3), the following identities hold
[w (Erest (fNTL.) Ew (Feest (étest (fNT)) + oa(1), E (eot:
(31)
(Erooo((fNT) + LE [eo::o) oa(1).
(32)
Thus, average (over initialization): (i) fNTL and fNT have the same test error, i.e., the initialization term finit in fNIL does not affect its test error. (ii) On the other hand, fNTL is less robust than fxr: the deficit in robustness, namely the term (1+ ||T||//)/ 13... corresponds exactly the contribution of the initialization. The situation is empirically illustrated in Fig. 2. Notice the perfect match between our theoretical results and experiments.
CONCLUDING REMARKS
In this paper, we have studied the adversarial robustness of two-layer neural networks in different high-dimensional learning regimes, and established a number of new tradeoffs between prediction performance and robustness, in the form (8). Our analysis also shows that random initialization can further degrade the robustness in lazy training regimes: for "large" random initialization, the trained neural network inherits additional vulnerability already present initialization. Our work can be seen as a first step towards a rigorous thcoretical understanding of the robustness of trained neural networks, important subject which is still understudied.
REFERENCES
Alnur Ali, Edgar Dobriban, and Ryan J. Tibshirani. The implicit regularization of stochastic gradient flow for least squares. In Proceedings of the 37th International Conference on Machine Learning, ICML, volume 119 of Proceedings of Machine Learning Research, pp. 233-244, PMLR, 2020.
Peter L. Bartlett, S S'ebastien Bubeck, and Yeshwanth Cherapanamjeri. Adversarial examples in multi-layer random relu networks. NewrIPS, 2021.

---

Under review as a conference paper at ICLR 2023
Robi Bhattacharjee, Somesh Jha, and Kamalika Chaudhuri. Sample complexity of robust linear classification on separated data. In Proceedings of the 38th International Conference on Machine Learning (ICML). PMLR, 2021.
Sébastien Bubeck and Mark Sellke. universal law of robustness isoperimetry. Advances in Neural Information Processing Systems, 2021.
Sébastien Bubeck, Yuanzhi Li, and Dheeraj Nagaraj. A law of robustness for two-layers neural networks. arXiv e-prints, art. arXiv:2009. 100009...444 14444, September 2020b.
Sébastien Bubeck, Yeshwanth Cherapanamjeri, Gauthier Gidel, and Rémi Tachet des Combes. A single gradient step finds adversarial examples on random two-layers neural networks. In Advances in Neural Information Processing Systems, 2021.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. 2019.
Amit Daniely and Hadas Shacham. Most relu networks suffer from \ell'2 adversarial perturbations. In Advances in Neural Information Processing Systems, volume 33, pp. Associates, Inc., 2020.
Curran
Edgar Dobriban and Stefan Wager. High-dimensional asymptoties of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247 - 2799, 2018
Edgar Dobriban, Hamed Hassani, David Hong, and Alexander Robey. Provable tradeoff's in adversar- ially robust classification. arXiv preprint arXiv:2006. 2tt.:20000.05666. 0611, 2020.
Elvis Dohmatob. Generalized no free lunch theorem for adversarial robustness. In Proceedings of the 36th International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research. PMLR, 2019.
Elvis Dohmatob. Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes. arXiv preprint arXiv:2106.02664 2021.
Noureddine El Karoui. The spectrum of kernel random matrices. Ann. Statist., 2010.
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsich, Liwei Wang, and Jason Lee. Convergence of adversarial training in overparametrized neural networks. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of lazy training of two-layers neural network. Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Nicola Gigli and Michel Ledoux. From log Sobolev Talagrand: quick proof. Discrete and Continuous Dynamical Systems, 1977 2013.
Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Wattenberg, and lan J. Goodfellow. Adversarial spheres. CoRR, abs/ 180.00744,,,77, 2018.
Hamed Hassani and Adel Javanmard. The curse of overparametriiation in adversarial training: Precise analysis of robust generalization for random features regression. arXiv preprint arXiv:2201.05/4 2022.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems 31. 2018.
Justin Khim and Po-Ling Loh. Adversarial risk bounds via function transformation. arXiv preprint arXiv:1810.09519, 2018.
Olivier Ledoit and Sandrine Péché. Eigenvectors of some large sample covariance matrix ensembles. Probability Theory and Related Fields, Oct 2011.
10

---

Under review as a conference paper at ICLR 2023
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. 2018.
Saeed Mahloujifar, Dimitrios I. Diochnos, and Mohammad Mahmoody. The curse of concentra- tion in robust learning: Evasion and poisoning attacks from concentration of measure. CoRR, abs/ 0ass/800..33000 00090, 2018.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv e-prints, art. arXiv: 998.05355, August 2019.
Yifei Min, Lin Chen, and Amin Karbasi. The curious case of adversarially robust models: More data can help, double descend, hurt generalization. In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence. PMLR, 2021a.
Yifei Min, Lin Chen, and Amin Karbasi. The curious case of adversarially robust models: More data can help, double descend, or hurt generalization. In Uncertainty Artificial Intelligence ( (UAI), 2021b.
Andrea Montanari and Yiqiao Zhong. The interpolation phase transition in neural networks: Memo- rization and generalization under lazy training. CoRR, abs/2007. 12826, 2020.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, Pascal Frossard, and Stefano Soatto. Analysis of universal adversarial perturbations, abs/1705.09954, 2017.
Ali Rahimi and Benjamin Recht. Uniform approximation of functions with random bases. 2008.
Dominik Rothenhausler, Nicolai Meinshausen, Peter Buhlmann, and J. Peters. Anchor regression: Heterogeneous data meet causality. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 83, 2021.
Amartya Sanyal, Puneet K Dokania, Varun Kanade, and Philip HS Torr. How benign is benign overfitting? In International Conference on Learning Representations (ICLR), 2021.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adver- sarially robust generalization requires more data. CoRR, abs/1804 1285, 2018.
Ali Shafahi, W. Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adversarial 2018.
examples inevitable? CoRR,
J.W. Silverstein and S.I. Choi. Analysis of the limiting spectral distribution of large dimensional random matrices. Journal of Multivariate Analysis, 1995.
Carl-Johann Simon-Gabriel, Yann Ollivier, Leon Bottou, Bernhard Schölkopf, and David Lopez-Paz. First-order adversarial vulnerability of neural networks and input dimension. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5809-58099 -817. PMLR, 09-15 Jun 2019.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 2013.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In International Conference on Learning Representations (ICLR), volume abs/1805. 12152, 2019.
Roman Vershynin. Introduction the non-asymptotic analysis of random matrices, pp. 210-268.
Cambridge University Press, 2012.
Boxi Wu, Jinghui Chen, Deng Cai, Xiaofei He, and Quanquan Gu. Do wider neural networks really help adversarial robustness? In A. Beygelzimer, Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021.
Yao-V Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Russ R Salakhutdinov, and Kamalika Chaud- huri. A closer look at accuracy vs. robustness. In Advances in Neural Information Processing Systems, volume 33, pp. 8588-8601 Curran Associates, Inc., 2020.
11

---

Under review as a conference paper at ICLR 2023
Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. In International conference on machine learning, 2019.
Zhenyu Zhu, Fanghui Liu, Grigorios G Chrysos, and Volkan Cevher. Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization), 2022.
12

---

Under review as a conference paper at ICLR 2023
Appendix Supplementary Materials
CONTENTS
A Further related work
14
Notations
14
Warm-up: An insight from linear regression
15
D Justification of our proposed measure of robustness
15
D.I Why not use Lipschitz constants to measure robustness ?
16
D.2 Proofs for Dirichlet energy measure of adversarial vulnerability
17
Neural networks at (random) initialization
18
F
Miscellaneous
19
F.1 Lazy training of output layer in RF regime
19
F.2 Effect of regularization in RF regime
19
Technical proofs
20
G.I A useful lemma
20
G.2 Hermite coefficients...
G.3 Approximation of random matrices
G.4 Proof of Theorem 4.1: Analytic formula for robustness of RF model
24
H Proofs of main results
25
H.l Proof of Theorem E.1: Robustness eπrоr of neural networks at initialization
25
H.2 Proof of Theorem E.2: test error neural network at initialization
26
H.3 The special case of quadratic activations
27
H.4 Proof of Theorem F.1: Random features lazy (RFL) regime
27
H.5 Proof of Theorem 5.1: Neural tangent (NT) regime
28
H.6 Proof of Theorem 5.2: Neural tangent lazy (NTL) regime.
29
I General nonlinear teacher and student models
31
J Proof of Theorem L.1
31
K Approximating function values doesn't amount to approximating grandients
31
K.1 Disproving (9) .9).............................
K.2 Some exceptional cases where (1) holds
32
13

---

Under review as a conference paper at ICLR 2023
A FURTHER RELATED WORK
Various works have theoretically studied adversarial examples and robustness in supervised learning, and the relationship to ordinary predictive performance / test error. We present a detailed list here
Tsipras et al. (2019) considers a specific data distribution where good accuracy implies poor robustness. Shafahi et al. (2018); Mahloujifar et al. (2018); Gilmer et al. (2018); Dohmatob (2019) show that for high- nigh-dimensional data distributions which have concentration property (c.g., multivariate Gaussians, distributions satisfying log- tog-Sobolev inequalities, etc.), an imperfect classifier will admit adversarial examples. Dobriban et al. (2020) studies tradeoffss in Gaussian mixture classification problems, highlighting the impact of class imbalance. On the other hand, Yang et al. (2020) observed empirically that natural images well-separated, and so bocally-lisschin classifies shouldn't suffer any kind of test error vs robustness tradeoff. However, gradient-descent is not likely to find such models. Our work studies regression problems with quadratic targets, and shows that there indeed tradeoffs between test eтror and robustness which are controlled by the learning algorithm / regime and model.
Simon- Matoonl al. (2019); Daniely & Shacham (2020); Bubeck al. (2021); Bartlett et al. (2021) study adversarial vulnerability of neural networks at initialization, but do not consider the effects of training the model, in contrast to our work.
Schmidt et al. (2018); Khim & Loh (2018); Yin et al. (2019); Bhattacharjee et al. (2021); Min et al. (2021b;a) study the sample complexity of robust learning. contrasts, our work focuses on the case of infinite data, so that the only complexity parameters are the input dimension d and the network width m. Bhattacharjee et al. (2021) studies robustness vs accuracy for data distributions which are well-separated (e.g., say the two classes are supported on disjoint balls). The main finding in that paper is that (i) the robustness vs aceuracy tradcoff doesn't exist for well-separated datasets. The work also posits that (ii) real-world datasets are well-separated. We think (i) is only an artifact of the well-separatedness assumption (an assumption which fails for Gaussians (as noted in the paper), say, due to infinite support). Also, (ii) is likely due to the fact that most real datasets are limited in sample size, and so, deceptively appear to be well-separated. Indeed, in the real world, there are cats which look like dogs (e.g. Siamese cats), even though such data might be under-represented in ML datasets.
Gao et al. (2019); Bubeck et al. (2020b); Bubeck & Sellke (2021) show that over-parameteriiatton may be necessary for robust interpolation in the presence of noise. In contrast, our paper considers a structured problem with noiseless signal and infinite-data n = oc, where the network width m and the input dimension tend infinity proportionately. In this under-complete asymptotic setting, our results show a precise picture of the tradeoffs between approximation (test error) and robustness in different learning regimes. Our work nuances this picture by exhibiting nontrivial interplay between robustness and test error which persists even in the case of infinite samples, where the model isn't 't affected by label noise.
B NOTATIONS
Linear algebra. The set of integers from 1 through d will be denoted [d]. We will denote the identity matrix of size d by Ia. The euclidean norm of a vector x E IR will be denoted || The kth largest singular-value of matrix A will be denoted sx(A),, and equals the positive square-root of the kth largest eigenvalue of the positive-semiddefnite (psd) matrix AAT, In particular, ||Al] == si (A) is the spectral norm of A. If A is itself psd, then its singular-values coincide with its eigenvalues.
The Frobenius norm of is denoted ||A||[ and defined by ||A|| == | More
mad generally, we define || v Eme Su (A)?, so that F|] = ||A|]] Fr in particular. Note that
m - Fm is nondecreasing function which is upper-bounded by || The Hadamard / element-wiis product of two matrices A₁ and Ag of the same shape will be denoted A₁ o Ag. The squared L2-norm of a function f Rdd + R w.r.t distribution P on Bd will be denoted II. and defined by [[]l[ == Ep [x))],,,,, whenever this integral exists. Given a psd matrix of size d, we denote by (O, Σ) the d-dimensional multivariate gaussian distribution with covariance matrix E.
Asymptotics. The usual notation Ox(1) (resp. Osp(1)) is used to denote a quantity which remains bounded (resp. bounded in probability) in the limit d co. Likewise oa(1) 1) (resp. (1r( denotes
14

---

Under review as a conference paper at ICLR 2023
quantity which goes to zero (resp. which goes to zero in probability) in the limit d - co. As usual, the acronym "a.s" stands for almost-surely, while "w.p p" stands for with probability at least p.
C WARM-UP: AN INSIGHT FROM LINEAR REGRESSION
Before providing complete proofs in the sequel, in this section we will use linear regression develop an intuitive understanding for the tradeoffs established in the paper.
Consider sample points (1), y1), ......................... (In, yn. in Rd x R. Now, let X = ( z.,) E Raxd be the design matrix and == (.i,..., Un) IR" be the response vector. For any nonempty subset S of [n], let X Rl8|xd (resp. ys E ) be the version of X (resp. y) with all rows (resp. columns) not in removed. For (possibly random) sequence of nonempty subsets (S,) of [n], and sequence of sufficiently small stepsizes (uv))= the following discrete dynamics
W 0,X5, (Xs, WT-1 ys.)/(S.)
(33)
represents GD or SGD initialized at wo E Rd. In particular, GD corresponds to taking St = [n]] for all t 2 1. By construction, it clear from (33) that at any iteration t,
Wt - wo E span X) == I=ER]=
(34)
On the other hand, suppose w. E IR is interpolant, i.e Xw, converges to point Wio which the orthogonal projection of wi onto the affine space interpolants kern(X) X). where kern(X) C Rd is the kernel of X. Thanks to
It is well-known that
I: (w E IRd Xw = y) (34) and the closedness of the subspace span (X), it is clear that Wee - wp E sxan(X). We conclude that wee w, is orthogonal to W wo, and so l|w. wo 2 w|,, w 2 ||wo woll by Pythagoras' Theorem. particular, taking Wp = 0, the previous identity becomes
lest error of 1 +
[xx
[ 1|
(35)
rob. of
constant
where the test error is w.r.t to test data generated according to the linear model ~ P. == N(0, Ia).
y = Sw. (z), with (x) == x Tw for all w, x E IRd. Dividing through by ||w,|l" 12 = [lS ll (
we deduce the following result which can be seen as the inductive bias of GD and SGD on linear regression.
Proposition C.1. For GD SGD started at wp 0, it holds that Erest (w Erob (fob(fw:))) 1.
This is tradeoff between the test error and the robustness error for GD and SGD! It is valid for all sample sizes n 2 1. In contrast, the tradeoffs established the nonlinear settings of the previous sections persist hold for infinite samples where co. Perhaps, sufficiently large but finite is sufficient, but this investigation left for future work.
D JUSTIFICATION OF OUR PROPOSED MEASURE OF ROBUSTNESS
Let us begin by explaining why our proposed measure of robustness based on Dirichlet energy (6) is actually measure of robustness.
Unless otherwise stated, in this section the feature distribution will be any distribution Pz on R Given smooth Fdd I, consider the d x d psd matrix J(f) and scalar G(f) 2 0 defined by
J(J) Er, [V<))> 6() = tr(
(36)
Note that (f) 2 The following lemma shows that G(J) measures the sensitivity of f to random local fluctuations in test data, on average.
Here, derivatives are allowed to be defined only almost-everywhere, as in neural networks with ReLU activation function. This notion of smoothness is completely subsumed by the more general notion presented in Section 4.1 of Gigli & Ledoux (2013).
15

---

Under review as a conference paper at ICLR 2023
Lemma D.1 (Measure of local sensitivity). We have
lim Pr, (a; G(), 6-0++
(37)
where (x; == S (x + v) [(
This lemma is a direct corollary to Lemma D.3 proved later below.
The next lemma shows that || measures the (non)robustness of f to universal adversarial perturbations, in the sense of Moosavi-Dezfooli et al. (2017).
Lemma D.2 (Measure of robustness to universal perturbations), We have the identity
lim A |
(38)
6-
where A,(8)² = sup s Ep. (f(x + (xx))
In particular, the leading eigenvector of J(J) corresponds to (first-order) universal adversarial perturbations of in the sense of Moosavi-Dezfoole Dezffoli et al. (2017), which can be efficiently computed using the Power Method, for example.
A rough sketch of the proof of the above lemma is as follows. To first-order, we have ((+t))-f(a 2 v (z). Thus,
Ay( = sup Ep, ((f(x + f(x))
|
sup Er, VVf()))
sup v J(fv== (1)
|
The first lemma is proved via similar argument.
D.1
WHY NOT USE LIPSCHITZ CONSTANTS TO MEASURE ROBUSTNESS!
Note for any that smooth function, G()) is always a lower-bound for the Lipschitz constant ||/T of f. Recall that I is defined by
-f())-((x))
|l == sup
(39)
ayaa
| x'1
One special case where there is equality G(J) = I pp when f is linear function. However, this is far from true in general: || is worst-case measure, while G(f) is an average-case measure for each q. If [| If is small (i.e., of order ((1)). then a small perturbation (i.e., of size ((1)) can only result in mild change in the output of (i.e., of order (())). However, large value of [| Ll uninformative regarding adversarial examples (for example, one can think function which is smooth everywhere except that, on average, it is possible for an adversarial to drastically change the output of f via a small modification of its input.
set of measure zero). In contrast, large value for G(f) indicates
An illustrative example. Consider a quadratic function f(x) := (1/2)x Br + e with isotropic feature distribution P. (O, Ia). Note that the teacher model f. defined in (1) is of this form. A direct computation reveals that Vf(x) = Br and so 6(f)² = Ep, | [=)]] Ep, |B] ||]] e. However, the Lipschitz constant of f restricted to the ball of radius v is?
||
|V/(2)] sup v
sup
|xx Vd|BBlpp |
which can be up to vd times larger than G(f) B||.. For example, take B to be an ill-conditioned, e.g., rank-1, matrix.
For fair comparison with our measure of robustness, we restrict the computation of Lipschitz constant to this ball since vd is the length of typical random vector from N(0, Ta)-
16

---

Under review as a conference paper at ICLR 2023
D.2 PROOFS FOR DIRICHLET ENERGY AS MEASURE OF ADVERSARIAL VULNERABILITY
Let || || be any norn on R with dual norm || |l.. Given function Rd + R, tolerance parameter & 2 (the attuck budget), and scalar q 2 1, define R&( by
s = P, | (2;
(40)
where (y == sup|='->||s ff(2)( - fax) is the maximal variation of f in neighborhood of size ā around x. For 2, we simply write Rs(L.) for (.. In particular, Gs(J)
(f.)) is adversarial test error and Go(f) == (J: f.)] the ordinary test error of f. where the expectations are w.r.t all sources of randomness in and f.. Of course G&(f) is an increasing function
Define (f) (S. f) and Rs(S)= = R2, which measure the deviation of the outputs of f w.r.t to the outputs of f. under adversarial attack. Note Rg (f) = O. Also note that in the case where || is the euclidean Lg-norm: if ff is near perfect model (in the classical sense). meaning that its ordinary test error Go(S) is small, then Rs(f) is a good approximation for G&(f). Finally, (at least for small values of a),, we can further approximate Ra (and therefore Gs(f), for near perfect f) by 8 times the Dirichlet energy G(f)². Indeed,
Lemma D.3. Let E (o), and f Rd + R be smooth function. Define (f( by
6,(0) (Er;
(41)
Note that, in particular, if 1| is the euclidean L2-norm and q- 2, then 6, is the Dirichlet energy defined in (6) as our measure of robustness. We have the following
(A) General case. Gylf) is the right derivative of the mapping 8 + Ro(f) at = 0. More precisely, we have the following
R
lim 6-30-
8 =f(),
(42)
or equivalently, Rq, 89 G(f)*+ + Higher order terms in 85.
(B) Case of Dirichlet energy In particular, | is the euclidean L2-norm, and we take q = 2,
Ro(f) 52 -G,5)² Higher order terms in 52.
(43)
Remark D.1. A heuristic argument was used in Caaooel et al. (2019) to justify the use of aver- age (dual- norm of gradient (i.e the average local Lipschitz constant) R.,, [IIV (corresponding
in the above) as a proxy for the adversarial generalization.
The proof of Lemma D.3 follows directly Fubini's 's Theorem and the following lemma.
Lemma D.4. If f is differentiable at then the function 6 + A,(r;)) = sup
If(x') f(x)
|| ||
right-differentiabl at 0 with derivative given by (2; 0) |Vff())]
Proof. As f is differentiable, f(x') f(x) (f x)) + 00|20 - æI)) around x. Therefore for sufficiently small 6, if B(x; 8) is ball of radius 8 around x, then
A (z; 8) = sup x';
Vf(x) T (a' - x) + o(Ia=' - 2(1)
Vf(x) (a' - -x)++ sup o[| - x())
sup
<'E((2:8)
ye B(
al|aa' - x||) A م 8)
(44)
=|VV/<>)|10 + sup ;
5
a||ar - x:
sup
z
17

---

Under review as a conference paper at ICLR 2023
ol|x' - xl))
Note that sup='e Similarly, computes
- 0. This proves lim so (1/0)))) z [VV((=))..
A 6) sup Vf(x) -z) + x|1)
2 sup fz))) (a' x)1 sup o(I - x1)
(45)
= [>](2>]] supallla' - =ll)
Hence lim g-t (1/0) (1; 6) 2 (+) and we conclude that ö - Ay(x; (x; differen- tiable at ā = 0, with derivative 2 (2; 0) [V)(z) +| as claimed.
Proof of Lemma D.3. By basic properties of limits, one has
R
Rg
lim 6-00+
lim
5"
6-+0+
6
Ep, || ((;; 8)
lim 6-:01
5
(x; 8)197 lim
Er.
(46)
6-+01
5
5 8)| 97
Ep.
lim
6-+0+
Ep, [+=
= (f),,
where the 3rd line is thanks Fubini's Theorem. and the 5th line is thanks lemma D.4 (and the fact that (x; 0) = 0). Noting that Rg, = 0 then concludes the proof.
E NEURAL NETWORKS AT (RANDOM) INITIALIZATION
We now consider networks at initialization, wherein the hidden weights matrix W = [W....., Wm) a random d matrix with iid rows from (0, I') in the random features regime (13), but freeze the output weight vector 2 = E R at random initialization, with random iid entries from N (0, 1/m), following standard initialization procedures. Let fini denote this random network, i...
finit
(x) fin
((22) (Z Ezjo(ss w.).
(47)
Theorem E.1. Under the Conditions 4.1 and 4.2, we have the identity in the limit (3),
|| (oo'I(ee(()o)))
>1 T + od,z o1,)(1), where X is the kth Hermite coef-
To (fiit) =
B|B
ficient of the activation function a. In particular, for the quadratic activation function o(t) = t2 we have (fmit)
| ||
+ o1,((1).
Analogously, the test error for the NN at initialization is given by the following result. Theorem E.2. Under the Conditions 4.1 and 4.2, we have the following identity in the limit (3),
ētest (fini) = = 10112>((0011 X D12 (1), In particular, for the quadratic activation
B
(1) 12 1, we have the following identity ēreat (fiitt) 1 | + oa,,(1).
B
Combining Thm. E.2 with formula (11), deduce that training randomly initialized neural network always improves its test error, as one would expect. On the other hand, combining Thm. 3.1 and Thm. 1. deduce that fully training the networks (10) via SGD:
18

---

Under review as a conference paper at ICLR 2023
(1) Degrades robustness if | 2 ||[| + This is because in this case, the parameters of the model align to the signal matrix B, which has much larger energy than the parameters at initialization. Indeed, SGD tends to move the covariance structure of the hidden neurons from I' to B.
(2) Improves robustness if B & +1
F MISCELLANEOUS
F.1 LAZY TRAINING OF OUTPUT LAYER IN RF REGIME
We now study the influence of the initialization (wi...., wm) E Rmxd with random rows drawn iid from N(O, P) as in the RF model (13), and let the output layer be initialized at 2 ~ (0, (I/m)Ta) and updated via single-pass gradient-flow on the entire data distribution (infinite data). In this so-called random features lazy (RFL) regime, we posit the following approximation neural network (2)
the random features regime. Let W
fREL == (Wz))
(x) + 82 (WWz)
(48)
where ZRFL, 2 52 and 82 R solves the following ridge-regression problem
arg min 1 ((Wx) (x) f=)) x||81| SER"
(49)
The use of the ridge parameter here be thought of proxy for early-stopping at iteration t x 1/A Ali et al. (2020); x = 0 corresponds to training the output layer to optimality.
Theorem F.1. We have the following identities
tr tr(PRU)/m
B Etest (JREL,)) Etest (/RF) +
+ 0a,p(1)
(50)
B
tr(P oa.((1),
E,0 (JRFLAA) (FRR(
(51)
4||B13
where U = (W) and C C(W) are the random matrices defined in (15) and (54) respectively,
Because PR. U, and C' are psd matrices, the residual terms tr( (r(PPU) / and tr( PPC))// /m in the above formulae nonnegative. We deduce that random initialization of the output weights hurts both test error and robustness, as long as the RFL regime is valid.
Infinitely regularized case X co. Note that PA converges in spectral norm a.s the identity matrix Tm in the limit À >> co. Thus, in this limit, ZRF, converges almost-surely to the all-zero m-dimensional vector and so, thanks to (91), the output weights 2RFL, of JRFL,X converge the value initialization 2º. Therefore, fRFL, and all its derivatives converge point-wise its state finit at initialization (47). We deduce that in the - oo limit, the neural network in the lazy regime is equivalent an untrained model finit in terms of test eтror and robustness. This does not come as much of a surprise, since À + 0o, corresponds to early-stopping at / = 0, i.e., no optimization.
Unregularized case À 0+. By analogous argument as above, PA converges m x m matrix in the limit À - 0+, and so thanks to (91), we have the almost-sure convergence ||RrlL, - A || + O. We deduce that in this limit, the unregularized lazy training regime exactly equivalent to the unregularized vanilla RF regime. Thus, the random features lazy (RFL) regime corresponding to the approximation fREL is an interpolation between the random features regime (corresponding to fRF) and the untrained regime (corresponding to fuit).
to the all-zero
Although this is not useful in our infinite data regime, we remark that non-zero amount of regulariza- tion is often crucial for good statistical performance with finite samples. In this, case, Px is non-zero, and we expect both the test error and robustness to become worse this lazy RF approximation, compared to vanilla RF.
F.2 EFFECT OF REGULARIZATION IN RF REGIME
Suppose the estimation of the output weights of the RF model regularized. i.e., for fixed À 2 consider instead the model /RF, (x: Z or (W.r, where #nF,A is chosen to solve the following
19

---

Under review as a conference paper at ICLR 2023
ridge-regularized problem
min zERm
fw. - fAllEP(N((O,O)) + +||2]|?
(52)
A simple computation gives the explicit form
2RF,A = U 1x!,
(53)
where UΛ := U + Alm. U = UW) is the random matrix defined in (15), and u E Rd is random vector defined in (16). An inspection of the proof of Theorem 4.1 (see Appendix G.4) reveals that the situation in the presence of ridge regularization is equivalent to the unregularized case in which we replace À by X+ À in the definition of the matrix Ag which appears (20). This has the effect of decreasing 1 and t/2, and thanks to (23), decreasing the robustness of the random features model. That is, Tooh (/RF,A) is a decreasing function of the amount of regularization of X, and in fact, lim Erob (fRF.)) A-000
G TECHNICAL PROOFS
Before proving the main results the manuscript, we first state and prove some auxiliary results which will be instrumental.
G.1 A USEFUL LEMMA
Recall the definitions of the approximation error and robustness metries from Section 2.3. The following lemma used express the measure of robustesus Frob(fw.zz.j) of two-layer neural network fw.z.= as quadratic form the output weights, with coefficient matrix which depends the distribution of the hidden weights.
Let us start by deriving an analytic formula for the robustness measure for the neural network general model (2). This result will be exploited in the sequel in the analysis of the different learning regimes we will consider.
Lemma G.1. For the neural net fw.z.s defined in (2), we have the analytic formula Exob (fw,z,)) =
= =T Cz, where C = C(W) is the m X psd matrix with entries given by (with La)
Cj == [w] wt E. Jo "wy)o' (x wx)] Vj, k E [m]] In particular, for quadratic activation o (f)) = 12 + 8, we have Cj = 4(wJ wx) Vjjk k: E [m].
(54)
Proof. One directly computes V vz,
د== (x T wy)w;, and so the Laplacian of fw.z.s
at is given by
V (z)1
[w) wx)'o(x' uyyo'' (x ww).
(55)
1=k=1
Thus, ((f.,e,)) evaluates to
(rob(f..2.)) == E( V=Jw..
Σ 2 wE Eu wy)o''x" [xx)] = 2 C(W)2, d.k==
where the m X m psd matrix C(W) is as defined in Lemma G.I. In particular, for the activation function (t) == t² s, one computes
Cj == (w] wn wo lo' (xJ wy)o (=T wx)]
[w]] wn) Emwn (aT wx)((x wx)l = 4(wJ wx)
where the last step is due to the fact that
E wy )x"
T [x]] = E, TlTTTyyee wwww x] = tr(Cov(z)w,, = w. wk.
by a standard result on the mean of a quadratic form.
Corollary G.1 (Robustness error of teacher model). It holds that (fob(f.) 11
Proof. For the first part follows directly from Lemma G.1 with activation function (tt) = t² + bo/d and fixed output weight vector 1m = (1,...,1) 1).
20

---

Under review as a conference paper at ICLR 2023
G.2 HERMITE COEFFICIENTS
For any nonnegative integer k, let Hes- : R + R be the (probabilist's) () kth Hermite polynomial.
For example, note that (en == O, Hei (1) == I, Hez(() 12 1. Heg (() == ( 31, etc. The
sequence (He)) forms an orthonormal basis for the Hilbert space 1 = (N 1)) for functions
IR which are
w.r. the standard normal distribution (V, 1). Under suitable
integrability conditions (refer to Section 4.1), the coefficients of the activation function in this basis are called its Hermite coefficients, denoted Aς. and are given by
A {x = EG-N(O (e) (G)]-
(56)
Finally, || ( = BG (G)²) defines the squared T-2-norm of a w.r.t the standard Gaussian distribution N(0, 1). Note that by construction, one has ||0|| = - (()).
G.3 APPROXIMATION OF RANDOM MATRICES
This section establishes some technical results for "linearizing" number of complicated random matrices which occur in our analysis. We will make heavy use of random matrix theory (RMT) techniques developed in Silverstein & Choi (1995); El Karoui (2010); Ledoit & Péché (2011);
Dobriban & Wager (2018)
We begin by recalling the following definition for future reference. Definition 4.1. With 2 ~ (0, 1). define the following scalars
À [[a(2) X7. := ==> / == (Btr(
(18)
X E|o' ((d(()))==0 X2 K² = 1//
Let U be the random m x m psd matrix defined in (15) and let E RT be the random vector defined in (16). Recall that A = (a) is the Hermite coefficient of the activation function a. Also recall the definition of the scalars X, K, T, X, and n from (18). The following result was established in Ghorbani et al. (2019).
Proposition G.1 (Lemma of Ghorbani et al. (2019)). If No 0 and Conditions 4.1, 4.2 are in place, then in the limit (3), it holds that
IU - Vollop = odP (1),
(57)
| - (T/Vd)Lmll = os,
(58)
where the random m psd matrix Uo is defined by
Uo == Xlm + XWWWT + (K//) Im IT + uu
(59)
and μ = (M1...., Pm) E Tm with μ4 == X2 11)/22
A careful inspection of the proof of the estimate (57) reveals that we can remove the condition Ao 0, at the expense of incurring rank-1 perturbations the matrix Up. Indeed, let us rewrite a = ग + An and with Ao(G)) = [G)] = 0 with G ~ (0, 1) independent of the w, 's. Let To be the m m matrix with entries (To), == \n (nn)))) where o; is the function defined by
(z) = a ([] =|=== dz(2) + Ao, with (1[u:|]=>= = a( [|w> [2). Thus, we have the decomposition T To = To + Ao m + 1m u T) 1m mm
(60)
where u = (Ao(o.)) Let To be the m X m psd matrix with entries (To) == \o(F..)o(O,)).
Using the arguments from Ghorbani et al. (2019) (since >o = 0), one has
ITo pp llop = (1))
(61)
Furthermore, observe that one can write J, = Rul, T where R is the m x m diagonal matrix with R, := (o(o.))/u 14. Now, for large d and any E [m]], computes
m
a [[]u;][GG- - (G) EG
[o[[u;]]G)- - (G) de (I[w;]) + 1)/2
R4 = EG
Ao -[1,,,11= 1)/2
||:|||
(62)
Eg Go (G)]
A2 = 1.
X 2/2
X2
21

---

Under review as a conference paper at ICLR 2023
We deduce that -R-Imllo (1,, and so ||u1 - - llop = odp(1). This proves the following extension of the above lemma which will be crucial in the sequel.
Lemma G.2 (Linearization of without the Condition )o(or) = 0). Suppose Conditions 4.1 and 4.2 are in place. In the limit (3), it holds that
IIU Uollop oar((),
(63)
where Uo is the x random psd matrix given by
Un = XI + X@WW (k/d)) juji with j == /a + mm and Ā = X Xa BG-N((..) -
(64)
- >0 X7.
Let C C(W) be the random x m psd matrix with entries given by
Ctj == (w: w/ E(o,N( (x w;)o''aa (x w,)]-
(65)
Thanks to Lemma G.I, we know that Erob (fRF) = The CZRF = -U-- form in v. We start by linearizing the nonlinear random coefficient matrix C.
u, a random quadratic
Lemma G.3 (Lincarization of C). Suppose Conditions 4.1 and 4.2 are in place. Then, in the limit (3), we have the following approximation
||C Collop od,
(66)
where Co is the m x m random psd matrix given by
Co = XIm + (K' /d WW + (2x/d)1ml ms
(67)
with K²' = d. 13 O, and X = lo' ('( XT.
Proof. Note that C (WWT) @ U. where U is the m x random psd matrix with entries given by U/J Ee Tw,, wo))o((' Tw
SSee 1: Linearization. Invoking the previous lemma with o' in place of a, we know that
||U Upllop od,r(1),
(68)
where U/ is the m x m random matrix given by
U X'I, Wn + +k((') + (++ \o(o')lm)(( 2o(o))mmm
(69)
= =Imm + + + +k'/dd)mm (p + (1) (((0))))+++((00))))) (1(0)mm)
and we have used the fact that
Xo((o')3) >o(0')2 - >2 = >o((o')2)- \1(0)² - ~2200²² - X.
Now, since ||WWT| llop = (1. by standard R.T,, we deduce that from (68) that,
||C ) ](WWT) @ (U' 0%) lop
<WWWT 1lop ||U" Upllop
(70)
= -1).(1).
Step 2: Simplification. Let E == di:g(([w;;]))))) (()m)) and F:= (WWT) o (WW Then
(WW T o Ug = X' + + + (o)diiaa + WW
(71)
+ = XX + (x (22 (r)
Further, because max,g(n] ||| 2 1| o by basic concentration, we have E - Im Ilop. diag(u))l (1).
(72)
22

---

Under review as a conference paper at ICLR 2023
Also, thanks (El Karoui, 2010, Theorem 2.3), we may linearize F like
F - (Im + || Mlpp od.r(1).
(73)
Combining with (71) gives (recalling that x: = d. A2(0 22(7)11111322
(WW TU = (X + mm ( " + m + A XI + wd/d+>((0))WW))) + (2x/dd)mm +A
(74)
Co +4,
where 1o = o1p(1).
Let us rewrite Uo - Ai + up1 and Co = Do + (2x/d) d) Im I where
A == Ao + (x/d))mm
Ao Xlm + XWWWT,
(75)
Do = XI (w'/d /d WWW.
We will need the following lemmas.
Lemma G.4. We have the following approximation
(rob(fRr) u Cou o1r(11
= 1T TCTToooCu Im
1
(76)
+ osp(11,
where u :-= U h, with h: (T/v (T/Vd)) A2 tr(Br)) and Ug is defined as in Proposition G.1 and Cu is as defined in Lemma G.3.
Proof. Thanks to Proposition G.I, the fitted output weights vector 2RF E R concentrates around = Up h. On the other hand, we know from Lemma G.1 that Erob (fRF) ZRF C2RF. The result then follows from Lemma G.3.
Lemma G.5. Under Condition 4.3, the following holds in the limit (3)
T U, 2mm
4/1
+ ou.((1),
(77)
d
1 1+ 1K0I
T A
00,7(1),
(78)
Vd
|| 'lops |oolop = Od.((1).
(79)
where 1i is defined in (20).
Proof. Formula (77) was established in the proof of (Ghorbani et al., 2019, Theorem 1), whilst (78) was established the proof Lemma 5 of the same paper.
As for (79), we note that
|| = 1( + XWWWT>-"Ilop Our(I/A, Oar(1),
since π = (a(1) under Condition 4.3. Similarly, one computes Doolop = Oa(WWT)== = Oar(1), by standard RMT arguments Vershynin (2012).
We will need one final lemma.
Lemma G.6. Let A1, Ag, and Do be the random matrices defined in (75). Then, it holds that
1 A Im =
Do
4/12
+ os,2(1),
(80)
(1 + k2b1)2
where vi and 2/2 defined in (20).
23

---

Under review as a conference paper at ICLR 2023
Proof. By
formula, have
A 1m 1 An /d
A Ag K (1 + m Ao m
1 A DD 1m
and so
2ab - ab² a(1 b)² ac? where
d
a: TT Ap Do A0 10-11 1 m/dd
b b: k1. Ap 1m//d /d
1 + 11 An 1mm
(81)
c:= 1 -
+ k.1, Ap 1m/d
Now, one has TT. 1m tr(A5")/d + (1,, thanks to Lemmas 5 and 6 of Ghorbani et al. (2019). By an analogous argument, one can show that A,,45" 4 Do Im/d = tr(A," (e(A2)))/ + (1,((1). Finally, the fact that tr(Au)= /d and tr tr(Ap22op Do)/d converge to deterministic values 1 and de respectively, be established via standard RMT arguments Silverstein & Choi (1995); Ledoit & Péché (2011)-
G.4 PROOF OF THEOREM 4.1: ANALYTIC FORMULA FOR ROBUSTNESS OF RF MODEL
We are now ready prove Theorem 4.1, restated here for convenience.
Theorem 4.1. Consider the random features model fRF (13), with covariance matrix I' satisfying Condition 4.1 I and activation funtatioooonnion satisfying Conditions 4.2 and 4.3.
(A) In the limil (3), we have the following approximation
72 72(2k007 + 12)
(rob(JRF) =
| + 2)² + 0a.((1).
(23)
(B) Moreover, if lim a = Ozs, then lim lim (rob(fRr) = aze wap 1. In particular, for the d-000
p m.d++00
m//dap
optimal choice of T in terms of test error, namely T x B, one has lim lim (ab(ffr) = 1 w.p 1.
p-00 m.00 m/d-op
Proof. From Lemmas G.1 and G.3, we know that
Crob(fur) = C2FF = u Cou 0dr((1) = 1.m Lm CaUo 1m + od,
(82)
d
where u := h, with (T/vd)1m A2 tr( and Up defined as in Lemma G.2 and C, Co are as defined in Lemma G.3. Let A1, Ag, and Do be the random matrices defined in (75). Since, Co Do + (2x/d)1,, m TT one computes
U CoUo I
U DoU,
1m
U
1m
U
m
22x
m
dc
U, DoUp'L1 1m
1 U 1m
2x
(83)
1 T DoU 1m
2xa
+ od.z
d
(1 + x2/1)2
where the last step is thanks to Lemma G.5. It remains to estimate the first term in the above display. Using the Sherman-Morrison formula, we have
A uu A-1
- A
(84)
1 A
24

---

Under review as a conference paper at ICLR 2023
We deduce that
U DOUT 1m
d12 d21 022 + Od, (1),
(85)
d
where ail, 012, 021, and 022 are defined by
Q11 == A DoAm '1 1m
d
DOA AT uul Ai A 1m AT
Q12
(1+ v A 11)
(86)
A Aj "upp" A
(1 x AT A 1
AT up DDA'' uu JTpTAA A
a22
(1 +1+) nT 2
Now, one easily computes
1T MT up T 1m ATAAT//Vaj
max([a12l: (221l) < ||DolloplAAT 4T
= our(1),
(1 nT A (1+ AT' p))
where we have used Lemma G.5 in the last two steps. Similarly, we have,
AT
0g2
[DolloplAT
llop T.AT'u/Vd
1m/d= odr(1),
p1+N AT 2)2
Oa.(11)
01.((1)
oaF(1)
Oa
again thanks to Lemma G.5. We conclude from (85) that
I UT! DOU an + oar(1).
(87)
d
Finally, we know from Lemma G.6 that
411 == A DOAT
1m
(1 + k1)))) + 0d.(1)).
d
part (A) of the theorem them follows upon dividing (85) by Erob(f.) B| For part (B), one notes that t/1 and so
(2ce/ + 222
(r(B))dd((II) + 2222 (
tr + oa(1)
[2 2
B1
(1111) + B1?
tr(BT)²
+ +oa(1) + a ||
which completes the proof.
H PROOFS OF MAIN RESULTS
H.1 PROOF OF THEOREM E.I: ROBUSTNESS ERROR OF NEURAL NETWORKS AT INITIALIZATION
We restate the result here for convenience. Let finit. be the function computed by the neural network at initialization, as defined in (47).
Theorem F.1. Under the Conditions 4.1 and 4.2, we have the identity in the limit (3),
(fiit) ||0'1(2 + 1/
1 + o1, where X is the kth Hermite coef-
B|2
ficient of the activation function a. In particular, for the quadratic activation function o()) = 12 ||
we have (imitt)
+ oa,r(1).
|
25

---

Under review as a conference paper at ICLR 2023
Proof. Thanks to Lemma G.I, know that Erob = 2 C2, where Cs the random psd matrix defined in (65). By standard RMT, x1 C2 = tr(C)//m + 0ar(1).. Now, let Co be the random matrix introduced in Lemma G.3. Since ||C Collop (a,((1 (thanks to the aforementioned lemma), one has tr(C)/m tr + 01,((1). Let Do == Xlm (w/d+ W be the matrix defined in (75) so that Co Do + (2x/d)lm m We deduce that in the limit (3),
Erab (init)
= -tr(Do)/m +
= =(k//d+
+ 2k/d (1,
-k/d+ A + X 2x/d
(88)
-I1o' -10''l22( + +
/d 2x/ od (1)
(1o'(i2(N(oo1)) 23 [
|1 + oa.((L)
where the third line is because (r(WWT))/ 11mm(1/m) ا
||, which converges in probability
to tr(T) 1, by the weak law of large numbers. Dividing by both sides of the above display by Grob (f.) = 4 B then gives the result.
In particular, in the case of quadratic activation o (l) := 12 - 1, we have X2 2, || |
A = 0, and so we deduce that Tob (fimit) = (4 + 4|| 1111111))/11111111111 = (1+ + |||11B/ O
H.2 PROOF OF THEOREM E.2: TEST ERROR OF NEURAL NETWORK AT INITIALIZATION
Theorem E.2. Under the Conditions 4.1 and 4.2, we have the following identity in the limit (3),
Eestt (Fmit) = + | T/
+ 0s,e(1). In particular, for the quadratic activation
B
(t) = +2 - 1, we have the following identity Etest (frnit) =1- 1+ 14 || |
+ o1,r
Proof. For random initial output weights 2" N(O, (1/m)) independent of the (random) hidden weights matrix W. one computes
Eg EE (fmit) = E, Ez,Ez~N(,.n (f)m - (x)) ( E.E. [f
(89)
where we have used the fact that |I B| Let Q be the x m diagonal matrix with the output weights on the diagonal, and let U be the m x m matrix with entries Uig Ez[a(x wy (o [ wy)] introduced in
0. The second term in the rightmost expression equals
(15), and let Uo == Xlm, + XWW + (k/d)lm 1T + uq" with == w 12 - jem E R",
be its approximation given in Proposition G.I. Then
Eg [fiit (x)²] [o( [o = =
zUZz = tr(U)/m + (1), by concentration random quadratic forms tr(Uo)/m (1,, thanks to Proposition G.1
= - X2 (r(WW k/d X2
_ (l) [|w - +0a(())
(90)
1+02,((1)
o1,((1)
x x/d (1)
= || + || (1)
The first part of the result then follows upon dividing through by [lf= = B| In particular, if is the quadratic activation, then ||0112 = = 2, and the second part of the result follows.
n
26

---

Under review as a conference paper at ICLR 2023
H.3 THE SPECIAL CASE OF QUADRATIC ACTIVATIONS
We now specialize Theorem 4.1 to the case of the quadratic activation function and obtain more transparent formulae.
Corollary H.1.
Consider the random features model JRF with covariance matrix P satisfying Condition 4.1 and quadratic activation functionn o(1) == Then, in the limit (3), holds that tr (r(BB))
Frob(RRE (1/m+ B + (1,((1). Furthermore, part (B) of Theorem 4. holds.
Proof. For quadratic activation, one easily computes
d = A = 0, A2 2, A 2, X = 4, k = / 2| 2tr(BB)/
(O(BBT/VVL. Vd, K' =0,
and Ao 22 and Do ml In this casc, deduces
V/ = lim tr 1 1/d p/2 and che = lim tr(A,² Do)/d
m.d- df mmp
m.0000
d/m-t7
Plugging these into formula (23) of Theorem 4.1 yields
4tr(BD) 2 2| 2 (n/2)²
Erob (rob(Jur)=
+ 01,
2- 2 p/ | B|
4tr(Br)² (
+ 01,((1)
(2 + pd
tr( 2 1
(1/m ||| + o1r(
which proves the first part of the corollary. The second part follows directly from the second part of Theorem 4.1.
H.4 PROOF OF THROREM F.1: RANDOM FEATURES LAZY (RFL) REGIME
Theorem F.1. We have the following identities
tr tr(P2U)/m
Egoerest (JRFL.A)] Exost (/RF) +
+ oap((1)
(50)
2 B1
Eg Erob (fRFLA)) = =foob(fRF) + (r(PpC)mm od,
(51)
B|
where U = UW) and C C(W) are the random matrices defined in (15) and (54) respectively.
Proof. By construction, note that the vector dx is equivalent to the output weights of a RF approxima- tion with true labels (x) == (2:) - finit (x:) If U and
defined in (15) and (16) respectively,
then we have the frosed-form solution (with Ux = U + AIm)
8^ = U (E. - f [=o(x))
= t Ez oW (W)))))))W()))
-v Uz 2RF, U².
Thus, for a fixed regularization parameter X 0, the output weights vector in this lazy training regime is given by
ZRFL.A = 5x + ZRF.A + PA2".
(91)
where PA :- Im U. We deduce that in the presence of any amount of ridge regularization. the lazy random features (RFL) regime is equivalent to the vanilla random features (RF) regime, with an additive bias of = E TT on the fitted output weights vector. In particular, note that if À = 0. then 2RFL.0 = 2RF .o- that is in the absence of regularization, the RFL and RF correspond to the same regime (i.e., the initialization has impact the final model).
27

---

Under review as a conference paper at ICLR 2023
test enror. From formula (91), and noting that 20 is independent of W. one computes the test error of flazy.A averaged over the initial output weights vector 20 as
EgoeErest (flaay,)) a))
E. finey fo (N
= IlRRF - f. (11 + E.ollww.r.. (llecoo.
Eteat (JRF + Boo (T PAUP32
Etest (fRF,)) + tr Ur(PAU))m)
where U = UW) is the matrix defined (15).
-NNon)robustness. From formula (91), computes
G(JRFL; 2)2 FREL, CERFLAA = 2RF CERFAA + 22R x + PACPA
= =((RF()) 22RF 2 CP + (z PACPA
where C(W) the matrix defined in (65). Taking expectations w.r.t 20 and noting that 20 is independent of Px and C' only depend on W and are therefore independent of 20, we have
E. (go(G(rnae)) ) 6(fnF,))2 + tr(P2C)/m.
(92)
H.5 PROOF OF THEOREM 5.1: NEURAL TANGENT (NT) REGIME
Theorem 5.1. Consider the neural langent model JNT in (26). In the limit (3) it holds that,
(w(Eros(fNT] = (e+ - + oa(1), where & min(p, 1).
(28)
Let S min(m, d) be the rank of W. is clear that r min(m, d) w.p 1. Let
W = P.SVT
(93)
be the singular-valle value decomposition of W where P1 Rdxr (resp. V E Rmxr) is the column- orthogonal matrix singular-vectors of W (resp. W), and S E gx is the diagonal matrix of nonzero singular-values. For any A E R= set G(A) SV A Brxd In their proof of (27), Ghorbani et al. (2019) showed that optimal (in terms of test error) to chose ANT such that G(ANT) = P,T B/2. Multiplying through by the orthogonal projection matrix P1 gives
P.P B/2 PiG(ANT) = PiSV ANT = W ANT.
(94)
For the proof of Theorem 5.1, we will need the following lemma. Lemma H.l. Erob (fNT)) 4 WT A A
Proof. Note that we can rewrite
fNT(2) 2tr((t" A)rx
which is linear in xr T Rddd One then readily computes [NT( R(WTAC A A W)x, from which we deduce that [V]((=))] 4x T (W A+ A W Averaging over x ~ NO,, then gives
Crob (JNT) :- [< Eg (WT A A
= = | A+ A W
T
which completes the proof.
We will also need the following auxiliary lemma.
28

---

Under review as a conference paper at ICLR 2023
Lemma H.2. Let P1 be in (93) and let B == tr(B)) as usual. In the limit (3), we have the identities
Ew EwIlPP B [l]]3(2+aa(1)),,
(95)
Ew PT BP BPI || [ p3 oa(1))
(96)
where p= mi)
Proof. WLOG, let B a diagonal matrix, so that B = Ej XzezeJ where ej the jth standard unit-vector in Rd, Then, with P = PiP.T we have
IPPP tr(PB²)= = [(PB3) = Σ
(By(Ba)
i
(97)
Σ Pb)(B Σ
X.Poo Σ
ApP33
Therefore, EEw [|] B11
mim dd -
where have used the fact that Ew P3j = (1/d)Bwir(( for all due to rotation-invariance. This proves (95).
The proof of (96) is completely analogous the proof of formula (69) in Ghorbani et al. (2019), with therein replaced with 1 and is thus omitted.
Proof of Theorem 5.1. From Lemma H.I and formula (94)), we know that
Erob(fNT)
4|[W NIWTAnp ANT + A W li P B/2 BP /21 2 B + P1 BP
(98)
The result then follows upon taking expectations w.r.t the hidden weights matrix W and applying Lemma H.2.
H.6 PROOF OF THEOREM 5.2: NEURAL TANGENT LAZY (NTL) REGIME
Theorem 5.2. Suppose the output weights 20 initialization are iid from No, (1/m)) Then, in the limit (3), the following identities hold
(uee: = (E + oa(1),
(31)
E EqW.so//Erab((TTT = Ew (Ero (/NT)] +
+ oa(1).
(32)
Proof. First observe that fx( fNTI( A, F.(x)) fNT (2; A, where,
f.(z) = fx(x) - (ini(()) = x Bx + bo.
(99)
and the x d matrix B defined by
: B WT
(100)
Thus, fitting the model /NTI( (:: A, e) to the teacher model fs with coefficient matrix B is equivalent fitting fvr(:; A, e) to the modified teacher model f. with coefficient matrix B.
In terms of test error (4), let ANTL, CNTL be optimal in (Nr(: A, c), and for simplicity of notation define
(NT = fNTL ANTI, CNTL..
(101)
We split the proof into parts. In the first part, establish (32). The second part handles (31).
29

---

Under review as a conference paper at ICLR 2023
Robustness error. Proceeding in the same way as in the paragraph leading to (94), one has
(rob(fNTL.) 2 P B 23 1/:
(102)
where P1 E RdxT is the column-orthogona matrix in (93) and min(m, m,, d) is the rank of W (w.p 1). Now, by definition of B, one has B (B W TTTTTTQWWW QB) WTQW and so WWW.....W..
P PIP 1² PIP BW NWTTQW QW P W QWB P.P. WTRTTTTWW TWW QW. (103)
We now take the expectation w.r.t (W, ="), of each term on the RHS. Thanks to Lemma H.2, we recognize the expectation w.r. W of the trace of the first term in (103) as
Ew [tr( B Ew [I P B (g+
(104)
Now, since W and 2 are independent and 20 has zero mean. the second and third terms in (102)
have zero expectation w.r. (W, = because they are linear Q diag(=").
Finally, one notes that
Pi W QWW QW PiSV DWW" QVSP W TWwTQQw Qw,, and so taking expectation w.r.t W and D (i.e 20) yields
(105)
(tr.,o](t(PP,PPT TWNTTTQWTTR QW)) 1 (troo//tttWWrWr QWW
(WW Q))
= Ey [[W.:o)<=(((WWT]]
((WWT) (WWT))a)
(106)
(ero::))erob(fmmt)))
where the last step is thanks to the second part of Lemma G.1. Putting things together, we have at this point established that
[w PIPPPB || oz()))) - [w (Erob (fiite])
(107)
Similarly, noting that PIP W T by definition of Pt, one has
P. BP 1 tr(P BP B) tr(((1P) B W
QW))
= P
BW wwwTwwwww--- -t WT WTWP WQWB)
(108)
+ +tr(WTQWw QWWTQW).
Taking expectation w.r.t W and 20 then gives
E(w,:9) [P BP 1| Ew ||| P| BR | + E 2 |t(WW QWWTQ)
(109)
| 0² (1 8) + p3 oa)))) + (ew (fau))
Combining (102), (107), (109), and (28) then completes the proof of (32).
test error. The proof of formula (31) build on the proof of Theorem Ghorbani et al. (2019).
Let Ps be d (d min(m, d)) matrix such that the combined columns of P1 and Pa form orthonormal basis for Rd. Then, one computes
Exest (FNTL) [| f-ll (x) [4())
( min
2| - T A A WWI
AcRmxd
( 2| BP = = P3 B W TWW)P113
P| BP Etest (.NT)).
where (a) and (b) are due to arguments analogous to arguments made in the beginning proof of Theorem in Ghorbani et al. (2019) (except that our B plays the role of B in Ghorbani et al. (2019)) and (c) is because P,T P; = 0 E (d min,)))) by construction of Pz. Dividing through the above
display by Grab(()) 4| 1 then gives (31).
30

---

Under review as a conference paper at ICLR 2023
1 GENERAL NONLINEAR TEACHER AND STUDENT MODELS
The results we established so far are for student-teacher models which are two-layer neural networks in certain learning regimes with Gaussian data. In this section, consider much more general scenarios, and show lower-bounds that display similar tradeoffs between test error and robustness.
Suppose the distribution P. of the features is any distribution on IR which satisfies a Poincaré inequality with constant c² > O. This means that for any smooth function f R + R, one has Varp, (f) & e² @VV where Varp, (f) == Ilf Allia(p.) is the variance of f and f ==
Ep. f E R is its mean Pz. For example, N(0, Σ) verifies Poincaré inequality with c2 ||E|lop- Consider teacher model f. which now any function in (?x))) with mean f. =.
Theorem 1.1. For every smooth student model f IRd R (neural network not!), it holds that V Etesst (f) + c. Verab(f) 2 |1 (LP((P))
The nature of Theorem 1.1 is tradeoff since it directly implies that the test error cannot be decreased without increasing the robustness error. In the particular case of isotropic features where Pa = (0, Ia) considered in the preceding sections, a Poincaré inequality with constant c² 1 is satisfied, and we deduce from the above theorem that, for any smooth student model f, one has
Euest (f) (f) N Ilf (ea()))
(110)
Of course, apart from being only one-sided, the inequality (110) is weaker than the tradeoff's estab- lished in the preceding sections, due to the square-roots in the former. However, (110) holds without any real restriction the teacher model S., student ʃ model, or learning algorithm regime; it is solely consequence of the high-dimensiooal geometry of the distribution of the features, manifested via the Poincaré incquality. In contrast, the tradeoffss established in the preceding sections where for student-teacher models which where two-layer neural networks in various learning regimes.
J PROOF OF THEOREM I.1
Theorem I.1. For every smooth student model f RRd + R. (neural network or not!), it holds that Etest (J) + c (frab(f) 2 11
Proof. WLOG, assume Erett (f) < I[ (1)()))))) since the claimed lound-bound trivially holds other- wise. By the Poincaré inequality, we have
2 Erobb() == 22 2 (P.)))) 2 Varr, (f) = |I - - where J E R is mean of
2 - - 11 Sall by the triangle inequality.
In particular, we have
cvErob(f) llf. - -1112(1)) 115 f-ll
2 / Varr, (f+) - / testt (/) = || - V Veecst(f)
where the last line follows from Ilf= Varr. (f+) < llf+ Fllia(r)) The result then follows from a simple rearrangement of the terms in the above display.
K APPROXIMATING FUNCTION VALUES DOESN'T AMOUNT TO APPROXIMATING GRANDIENTS
K.1 DISPROVING 9
Henceforth, for student model f. consider the residue function h f- Thus. Vf-Vf. Vh. In the srudent-teacher setup considered our work, the student ff is in general mis-specified w.r.t to the teacher f+ (for example, because the students activation is arbitrary while the teacher's activation
31

---

Under review as a conference paper at ICLR 2023
function is fixed to quadratic), and so the residue function h has specific structure in general. Mindful of the previous remark, to disprove (I), it is sufficient to construct a subspace H of the weighted Sobolev space W ( Ia)) (consisting of functions g R + R which are square- integrable w.r.t [0, Ia) with weak-derivatives which are square-integrable w.r.t N(0, Ta)), such that:
for every 6, C >> O, there exists ho E H with [MolLE<(N((LL))) S e and (/holl > C.(II))
Indeed, take H (N,, Ia),, and for fixed a (0, 1), consider the sequence of residue functions (hm)m in H given by (z) == (1/n²) sin(nxr), for every positive integer n, and z = (21...., ..d) Rd. Note that constructive way for realizing such residue functions is by taking B = 0 in the teacher model S., and activation function (1) sin(t) in the student model f. Now, simple computation gives Vh, (a) = (1/n²) cos(nxr)en where 3 == - a E (0, 1) and ej jth standard basis vector in Rdd Furthermore,
| LA = n 20 "Bi (0.1)|sin Isin (nZ1)] = n 20 sinh(n?)
(sin))
= =a e 2nd 1/2 2 0,
| = EE (N(1 20 cos (nx))n = n cm cosh(n²)
= = (1 (1+ e-2 1/2 3 oc.
Thus, (2) holds and we conclude that the implication (1) claimed by the reviewer fails in general.
K.2 SOME EXCEPTIONAL CASES WHERE (1) HOLDS
Let roundup by noting that (1) can be true in very specific circumstances. For example, if the activation function a of the student is quadratic, just like the teacher model f.. Indeed, in this case the set of all residue functions/ f- f. is contained in the set of polynomials of degree most 2 in d real variables; this is a finiteddimensional subspace H = (I of L (0, Ia)). In fact, it is easy to show via a simple counting argument that dim = dim (2 = d = (d+2))) & df Thus, the gradient operator V is finite-rank, and therefore compact operator on H. follows that the H H-restricted operator norm V loop defined by
V
V H olop == sup
(112)
NEHV/0) [
is finite and thus the implication (1) holds in this case. This argument is valid whenever the linear span // of the residue functions f- is finite-dimensional subspace of L (N (0, L2)), for example linear models, or more generally, polynomial models of degree I D (corresponding to the case where the activation function a of the student is a polynomial of degree S D), for some fixed integer D 2
indeed H Pp (R:d) in this case, and has dimension (2+P) (d+ (d 1) ... (d+ 11/ d
32


Reviews:
[{"review_id": "y4ObolRcVV", "reviewer": "Reviewer_qTks", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper analyzes generalization and robustness properties (measured by gradient norm) of two-layer neural networks in different learning regimes under the high dimensional setting with Gaussian data. The tradeoff between them is theoretically given for such two-layer neural networks trained by SGD, the random features regime, and the NTK regime. Besides, a lower bound between the test error and the robustness over general data is given, which implies that the test error cannot be decreased without increasing the robustness error.\n", "summary_of_the_review": "This paper give a rigious theoretical evidence on the trade-off between robustness and generalization in high dimensional settings under two-layer neural networks. I vote for acceptance of this paper but strongly suggest the authors re-organize this work for better presentation.", "strength_and_weaknesses": "**Pros:** \n\n1. In two-layer neural networks with polynomial activation functions trained by SGD, random features, the neural tangent kernel for two-layer networks, the tradeoff between the generalization (excess risk) and the robustness (gradient norm) is given.\n2.  a lower bound between the test error and the robustness over general data is given. \n\n**Cons:**\n\nI’m familiar with this topic equipped with high dimensional statistics, and like this theoretical result on the trade-off between generalization and robustness. Nevertheless, I don’t like the writing style: mixing with Ghorbani et al. (2019) throughout this paper, e.g., problem settings, generalization results, random features regime and neural tangent kernel regime. \nFor example, Section 4.2 has already been studied in Ghorbani et al. (2019) or can be easily obtained (e.g., Eq. 20).\n\nI strongly suggest the authors rewrite this paper to emphasize their main contribution on robustness. Besides, a table is needed to summarize the problem settings and results presented in Section 3, 4, 5. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "cevDHEi0ewG", "reviewer": "Reviewer_vJwo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the trade-off between the test accuracy and robustness of two-layer neural networks, specifically concerning regression. More precisely, they focus on using a 2-layer network to learn a quadratic form. \nTheoretically, it is shown that there is a clear trade-off between robustness and test accuracy for some variants of the above setup where the initialization is taken into account, as well as the neural tangent regime. \nThe simulations verify the findings for this specific setup.", "summary_of_the_review": "The compromise between test accuracy and robustness has been studied before in the regression and classification setting, but this work sheds light on more detailed discussions that include initialization and other regimes, specifically for regression given quadratic form. \nWhile broadly the question is relevant, it is not clear if these findings can be extended to the more relevant classification setting.", "strength_and_weaknesses": "This paper studies the robustness of two-layer neural networks in different learning regimes and proves that there is a compromise between robustness and test accuracy. \n\nPros:\n- the paper is well structured and, (albeit dense) it is relatively clear \n- to my knowledge, understanding the tradeoff on this particular setup is novel and well motivated\n- it is particularly nice that the considered setup is simple so that it can be studied thoroughly.\n\nCons:\n- while I agree with the soundness of the robustness measure used, and I appreciate the additional details in the appendix, I am not sure to which extent the results of this paper (in the regression setting) can be generalized to the more standard classification setting.\n- there are missing comparisons with existing works (see below)\n\n## Missing comparisons with existing works\n- The work of Zhang et al. (TRADES) which focuses on the classification setting is also discussing the tradeoff between robustness and accuracy\n- Specifically for the regression case,  [Rothenhäusler et al., 2018.] rigorously show the trade-off between robustness and test accuracy in a linear setting; it is necessary to discuss the differences.  \n\n[Zhang et al, 2019] *Theoretically Principled Trade-off between Robustness and Accuracy* -- https://arxiv.org/abs/1901.08573\n[Rothenhäusler et al., 2018.] *Anchor regression: heterogeneous data meets causality* -- https://arxiv.org/abs/1801.06229", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LofdUIUMAKq", "reviewer": "Reviewer_7Nsv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies the trade-off between robustness and test error in a setting in which (i) the teacher is a quadratic function, (ii) infinite training data are available, and (iii) a proportional scaling between the input dimension and the neural network width is assumed. The authors provide results for 3 different regimes: (i) two-layer networks trained via SGD (Theorem 3.1), (ii) random features (Theorem 4.1), and (iii) neural tangent approximation, with and without initialization (Theorem 5.1-5.2). The test error in such models was computed in previous work by Ghorbani et al. (2019) and the contribution of this paper consists in computing a certain metric of robustness/sensitivity using rather similar tools (coming from high-dimensional statistics). By doing so, the authors are able to exhibit an interesting balance between the generalization error and the robustness to perturbation. Finally, a lower bound is provided for a general non-linear teacher/student model (Theorem 6.1). This lower bound is a relatively simple consequence of the concentration of measure phenomenon. ", "summary_of_the_review": "Overall, the paper demonstrates an interesting and novel trade-off between test error and robustness. At the technical level, the analysis is a bit incremental, as it appears to resemble closely that of Ghorbani et al., (2019). My borderline (leaning positive) score is due to the several weaknesses I pointed out above, which can potentially be resolved (at least partially) after the rebuttal.\n", "strength_and_weaknesses": "Strengths:\n\n(1) The problem is well motivated and the particular measure of robustness/sensitivity is well discussed (in Appendix C).\n\n(2) The trade-off exhibited is, to the best of my knowledge, novel.\n\n(3) Even though the assumptions are sometimes strong (see the weakness (2)), it is always remarkable to have an exactly solvable model, leading to a closed-form expression for the robustness.\n\n\nWeaknesses:\n\n(1) From the technical standpoint, the paper is somewhat incremental, since the tools are essentially those of Ghorbani et al., (2019). If that's not the case, I would like to encourage the authors to highlight their technical innovations in the rebuttal.\n\n(2) The assumptions on the model are rather strong, although I understand that they are taken from Ghorbani et al., (2019). In particular: \n\n(a) Having a teacher model which is a quadratic function is rather restrictive.\n\n(b) I am actually wondering how crucial Condition 4.3(A) actually is. If I understand correctly, it basically ensures that the activation function is centered. In Appendix F.3, the effect of centering is discussed. Given this discussion, I wonder about what happens when Condition 4.3(A) is violated. Is the model less robust (as in the case of the neural tangent approximation with an initialization)?\n\n(3) The authors show that having an initialization term in the neural tangent approximation (and potentially not being able to fulfil Condition 4.3(A), see remark above) leads to less robustness. It is not clear to me whether this actually means a worse resistance to adversarial examples or whether this is just an effect of the particular setting taken into account (and, more specifically, of the particular metric for robustness being chosen). Can the authors comment on this point? \n\n(4) One of the key messages of the paper seems to be that the trade-off between generalization and robustness is of the form $\\tilde\\varepsilon_{\\rm test}+\\tilde\\varepsilon_{\\rm rob}=1$. I have three comments about this. \n\n(a) This same trade-off is proved for the three settings taken into account. Does this mean that training with SGD, doing random features or the neural tangent approximation makes no difference as far as robustness is concerned? This would be a bit strange.\n\n(b) As a matter of fact, if I understand correctly the paper, $\\tilde\\varepsilon_{\\rm test}+\\tilde\\varepsilon_{\\rm rob}=1$ holds for random features and neural tangent only in some corner cases ($\\rho\\to\\infty$ for random features and $\\beta=1$ for neural tangent). Can the authors comment on why, in these corner cases, one would expect that the trade-off is the same in different models?\n\n(c) Finally, can the authors comment on the trade-off when it does not have the form $\\tilde\\varepsilon_{\\rm test}+\\tilde\\varepsilon_{\\rm rob}=1$? Theorem 4.1 and 5.1 hold more in general and should allow to discuss a more general trade-off.\n\n(5) How does Theorem 6.1 relate to the body of literature that uses concentration of measure to show the inevitability of adversarial examples, see e.g. Mahloujifar et al., (2018)?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "5kuF36ExUg", "reviewer": "Reviewer_d515", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the trade-off between robustness and test error for learning a quadratic target function. The models considered include two-layer quadratic nets, random feature models, and the neural tangent one. The sample size is assumed to be infinite and thus, the test error is essentially the approximation error. \n\nThe authors show that there exist a trade-off between approximation error and robustness of approximant: $robust(f) + error(f) = 1$. The authors argue that these theoretical findings can contribute to the explanation of why there exists a  trade-off between clean accuracy and adversarial robustness, a phenomenon observed in practice. ", "summary_of_the_review": "This paper provides a precise characterization of the trade-off between robustness and approximation error for a few models. Unfortunately, I find the result is kind of irrelevant. Please correct me if I misunderstandard the result. ", "strength_and_weaknesses": "I do not know how to assess the results of this paper. I feel that it is **not even wrong** since the result has nothing to do with adversarial robustness. If I understand correctly, the theoretical result basically means that when $f-f^*$ is small, $||\\nabla f||$ is close to $||\\nabla f^*||$.  Here $f$ and $f*$ are our model and target function, respectively. In other words, the relative robustness approaches $1$ when the approximation error is decreasing toward zero. \n\nFirst, this result is kind of irrelevant, since we only need the approximant and the target function to satisfy a **coercive condition**: that the smallness of $||f-f^*||$ can imply the smallness of $||\\nabla f - \\nabla f^*||$. This can be seen in Section 6, where the authors actually prove the trade-off for any functions that satisfy the Poincare inequality. \n\nSecond, I think the result has nothing to do with the vulnerability of ML models. As the approximation error is small, we have $||\\nabla f||\\approx ||\\nabla f^*||$, which in fact suggests that our model is as robust as the ground truth. This is almost the best we can expect. The vulnerability issue should be the case that the learned model is much more vulnerable than the ground truth but the test error is small. This is obviously not the case studied in this work.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject