The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks
Authors: Spencer Frei
Gal Vardi
Peter Bartlett
Nathan Srebro
Venue: NeurIPS 2023 poster (2023)
Keywords: adversarial robustness
neural networks
implicit bias
generalization

Abstract: In this work, we study the implications of the implicit bias of gradient flow on generalization and adversarial robustness in ReLU networks.  We focus on a setting where the data consists of clusters and the correlations between cluster means are small, and show that in two-layer ReLU networks gradient flow is biased towards solutions that generalize well, but are vulnerable to adversarial examples. Our results hold even in cases where the network is highly overparameterized.  Despite the potential for harmful overfitting in such settings, we prove that the implicit bias of gradient flow prevents it.  However, the implicit bias also leads to non-robust solutions (susceptible to small adversarial $\ell_2$-perturbations), even though robust networks that fit the data exist.

The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks
Spencer Frei"
Gal Vardi
UC Davis sfrei@ucdavis. edu
TTI-Chicago and Hebrew University galvardi@ttic.co
Peter L. Bartlett
Nathan Srebro
UC Berkeley and Google DeepMind peter@berkeley. edu
TTI-Chicago
nati@ttic. edu
Abstract
In this work, we study the implications of the implicit bias of gradient flow on generalization and adversarial robustness in ReLU networks. We focus on a setting where the data consists of clusters and the correlations between cluster means are small, and show that in two-layer ReLU networks gradient flow is biased towards solutions that generalize well, but are vulnerable adversarial examples. Our results hold even in cases where the network is highly overparameterized. Despite the potential for harmful overfitting in such settings, we prove that implicit bias of gradient flow prevents it. However, the implicit bias also leads to non-robust solutions (susceptible to small adversarial &g 2--petuurbaiinn), even though robust networks that fit the data exist.
Introduction
A central question in the theory of deep learning is how neural networks can generalize when trained without any explicit regularization, and when there are more Iearnable parameters than training examples. In such optimization problems there many solutions that label the training data correctly, and gradient descent seems to prefer solutions that generalize well [Zha+17]. Thus, is believed that gradient descent induces implicit bias towards solutions which enjoy favorable properties 17)+ Characterizing this bias in various settings has been subject of extensive research in recent years, but it is still well understood when the implicit bias provably implies generalization in non-linear neural networks.
An additional intriguing phenomenon in deep learning is the abundance of adversarial examples in trained neural networks. a seminal paper, Szegedy et al. [Sze+14] observed that deep networks extremely vulnerable to adversarial examples, namely, very small perturbations to the inputs can significantly change the predictions. This phenomenon has attracted considerable interest, and various attacks (e.g., GSS15 CW17 1ap+17| AACW18 CW18 Wu+20) and defenses (e.g., (Pap+ 16 KGB17) Mad+18] WK18; CH20 WRK20) were developed. However, the fundamental principles underlying the existence of adversarial examples still unclear, and is believed that for most tasks where trained neural networks suffer from a vulnerability to adversarial attacks, there should exist other neural networks which can be robust to such attacks. This is suggestive of the possible role of the optimization algorithms used to train neural networks in the existence of adversarial examples.
In this work, study the implications of the implicit bias for generalization and robustness in ReLU networks, in a setting where the data consists clusters (i.c., Gaussian mixture model) and the
"qqual contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

correlations between cluster means are small. We show that in two-layer ReLU networks trained with the logistic loss or the exponential loss, gradient flow is biased towards solutions that generalize well, albeit they are non-robust. Our results are independent of the network width, and hence they hold even where the network has significantly more parameters than training examples. In such an overparameterized setting, one might expect harmful overfitting to occur, but we prove that the implicit bias of gradient flow prevents it. On the flip side, in our setting the distances between clusters are large, and thus one might hope that gradient flow will converge to robust network. However, we show that the implicit bias leads to non-robust solutions.
Our results rely on known properties of the implicit bias in two-layer ReLU networks trained with the logistic or the exponential loss, which were shown by Lyu and Li (LL20] and Ji and Telgarsky (TT20. They proved that if gradient flow in homogeneous models (which include two-layer ReLU networks) with such losses reaches small training loss, then it converges (in direction) to KKT point of the makimuu--mrriin problem in parameter space. We show that in clustered data distributions, with high probability over the training dataset, every network that satisfies the KKT conditions of the maximum-man marggn problem generalizes well but is non-robust. Thus, instead of analyzing the trajectory of gradient flow directly in the complex setting of training two-layer ReLU networks, we demonstrate that investigating the KKT points is powerful tool for understanding generalization
and robustness. We emphasize that our results hold in the rich (i.e.. feature learning) regime, namely, the neural network training does not lie in the kernel regime, and thus we provide guarantees which go beyond the analysis achieved using NTK-based results.
In bit more detail, our main contributions are the following:
Suppose that the data distribution consists of k clusters, and the training dataset is of size n 2 (kk)). We show that with high probability over the size-n dataset, if gradient flow achieves training loss smaller than 1 at some time to. then it converges in direction to a network that generalizes well (i.e., has small test error). Thus, gradient-flow-triine networks cannot harmfully overfit even if the network is highly overparameterized. The sample complexity Ω(k) in this result is optimal (up to log factors), since we cannot expect perform well on unseen data using training dataset that does not include at least one example from each cluster.
In the same setting as above, we prove that gradient flow converges in direction non- robust network, even though there exist robust networks that classify the data correctly. Specifically, we consider data distributions on Rd such that the distance between every pair of clusters is 52( (VV)), and we show that there exists two-layer ReLU network where flipping the output sign of a test example requires w.h.p. an fz-perturbation of size ((vd). but gradient flow converges to network where we can flip the output sign of a test example with an fg-perturbation of size much smaller than vd. Moreover, the adversarial perturbation depends only on the data distribution, and not on the specific test example trained neural network. Thus, the perturbation is both universal [Moo+17] Zha+21 and transferable [Liu+17] AMI8). We argue that clustered data distributions are a natural setting for analyzing the tendency of gradient methods to converge to non-robust solutions. Indeed, if positive and negative examples are not well-separated (i.e., the distances between points with opposite labels are small), then robust solutions do not exist. Thus, in order to understand the role of the optimization algorithm, we need a setting with sufficient separation between positive and negative examples.
The remainder of this paper is structured as follows: provide necessary notations and background, and introduce our setting and assumptions. In Sections 3 4 we state our main results generalization and robustness (respectively), and provide some proof idcas, with all formal proof' deferred to the appendix. We conclude with a short discussion (Section 5)
Below discuss related work. In Section 2 we
Related work
Implicit bias in neural networks. The literature on implicit bias in neural networks has rapidly expanded in recent years, and cannot be reasonably surveyed here (see Vardi [Var22 for a survey). In what follows, we discuss results that apply to two-layer ReI.U or leaky-Rel.U networks trained with gradient flow in classification settings.
2

---

By Lyu and Li [L200] and Ji and Telgarsky [T20)., homogeneous neural networks (and specifically two-layer ReLU networks, which are the focus of this paper) trained with exponentially-taie -talled classification losses converge in direction to a KKT point of the maximum-margin problem. Our analysis of the implicit bias relies on this result. We note that the aforementioned KKT point may not be a global optimum of the maximum- extended this result by showing bias towards margin maximization in a broader family of networks called quasi-homogeneens.
problem [VSS22]. Recently, Kunin et al. [Kun+22]
Lyu et al. [y Sarussi, Brutzkus, and Globerson SBG21 and Frei et al. [Fre+23b] studied
implicit bias in two-layer leaky-ReLU networks with umearly-separae data, and proved that under some additional assumptions gradient flow converges linear classifier. Chizat and Bach [CB20) studied the dynamics of gradient flow on infinite-width homogeneous two-layer networks with exponentially-taile losses, and showed bias towards margin maximization w.r.t. a certain function norm known as the variation norm. Phuong and Lampert [PI.20) studied the implicit bias in two-layer ReLU networks trained on orthogonally separable data.
Safran, Vardi, and Lee [VL222 proved implicit bias towards minimizing the number of linear regions in univariate two-layer ReLU networks, and used this result to obtain generalization bounds. Similarly to our work, they used the KKT conditions of the maximum-margin problem in parameter space to prove generalization in overparameterized networks. However, our setting is significantly different. Implications of the bias towards KKT points of the Makimum--arrhh problem were also studied in Haim al. [Hai+22], where they showed that this implicit bias can be used for reconstructing training data from trained ReL.U networks.
Theoretical explanations for non-robustness in neural networks. Despite much research, the reasons for the abundance of adversarial examples in trained networks are still unclear (GSS1)
FFF18 1ha+19; Sch+18; KHI8: 1ub+19; [A22]] [Wn++20; [Sha+20] [SMB21] [in++21 Wan+22 DB22 Below we discuss several prior theoretical works on this question.
In one line of work, it has been shown that small adversarial perturbations can be found for any fixed input in certain neural networks with random weights (drawn from the Gaussian distribution) (DS20: [Bb+21 BBC2T; MW22]. These works differ in the assumptions about the width and depth of the networks well as the activation functions considered. However, since trained networks are non-random, these works are unable to capture the existence of adversarial examples in trained networks.
The result closest to ours was shown in Vardi, Yehudai, and Shamir [VSS2]]. Similarly to our result, they used the KKT conditions of the maximum-marne margin problem in parameter space, in order to prove that gradient flow converges to non-robust two-layer ReLU networks under certain assumptions. More precisely, they considered a setting where the training dataset S consists of nearly-orthogonn points, and proved that every KKT point is non-robust w.r.t. S. Namely, for every two-layer network that satisfies the KKT conditions of the maximum- margin problem, and every point x; from S, it is possible to flip the output's ' sign with a small perturbation. Their result has two main limitations: (1) It considers robustness w.r.t. the training data, while the more common setting in the literature considers robustness w.r.t. test data, as it is often more crucial to avoid adversarial perturbations in test examples; (2) Since they assume near orthogonality of the training data, the size of the dataset S must be smaller than the input dimension ? Thus, they considered a high dimensional setting. We note that high-dimensional settings often have a different generalization behavior than low-dimensional settings (e.g., overfitting can be benign in the high- high-dimensional setting, but harmful in a low low-dimensional setting KYS23)). ). Our result does not suffer from these limitations, since we consider robustness w.r.t. test data, and the size of our training dataset might be very large. In our results, we essentially require near orthogonality of the cluster means, as opposed to near orthogonality of the training dataset in their result.
maximum-marrinn
Finally, in Bubeck, Li, and Nagaraj (BLN21 and Bubeck and Sellke [BS2T). the authors proved (under certain assumptions) that overparameeerizzation is necessary if one wants to interpolate training data using neural network with small Lipschitz constant. Namely, neural networks with small number of parameters are not expressive enough to interpolate the training data while having a small
'They also give a version of their result, where instead of assuming this upper bound on the size of the dataset, they assume an upper bound on the number of points that attain the margin in the trained network, but it is not clear priori when this assumption is likely to hold.
3

---

Lipschitz constant. These results suggest that overparameterization might be necessary for robustness. In this work, we show that even the network highly overparameterized, the implicit bias of the optimization method can prevent convergence to robust solutions.
2 Preliminaries
We use bold-face letters to denote vectors, c.g., x= (ZI...., Fa). For E E we denote by | the Euclidean norm. We denote by [[:] the indicator function, for example L[t 2 5| equals if t 2 and 0 otherwise. We denote sign(z) .d.. For a set A we denote by (A) the uniform distribution over A. We denote by
if 0 and -1 otherwise. For an integer d 2 1 we denote
[d] = .l....d), N(J, o²) the normal distribution with mean μ R and variance o², and by N(H, Σ) the multivariate normal distribution with mean il and covariance matrix Σ. The identity matrix of size is denoted by [a. We use standard asymptotic notation (-) and 2(-)) to hide constant factors, and (-), (.)) to hide logarithmic factors. We use log for the logarithm with base and In for the natural logarithm.
In this work, we consider 2epth-2 ReLU neural networks. The ReLU activation function is defined by o(z) = max 2}. Formally, a depth-2 network No of width m is parameterized by 0 = [Wi...., Wm. b, v] where w, E Rdd for all i E [m]] and b, v E R", and for every input x E R we have
(x -je(m) [ x,)
We sometimes view I as the vector obtained by concatenating the vectors Wi...., Wms b, V. Thus, ||0| denotes the lz norm of the vector O. We note that in this work we train both layers of the ReLU network.
We denote $(0; x) == (x)... We say that a network is homogeneous if there exists L. > such that for every a > 0 and 0, x we have o x) = a ( x). Note that depth-2 ReLU networks as defined above are homogeneous (with L 2).
We next define gradient flow and remind the reader of some recent results on the implicit bias of gradient flow in two-layer ReLU networks. Let S {(x:, M:))== S Rd x [-1,1] be binary classification training dataset. Let (0; RRd - R be neural network parameterized by O. For loss function & TR + R the empirical loss of -): on the dataset S is
[( = : Σ (())))
We focus on the exponential loss E(g) - and the logistic loss {(q) - log(1 (10(1++7)) )
We consider gradient flow on the objective given in Eq. (I. This setting captures the behavior of gradient descent with an infinitesimally small step size. Let O(t) be the trajectory of gradient flow. Starting from an initial point 80). the dynamics of (t) is given by the differential equation
di E - ()))))) Here, d denotes the Clarke subdifferential (Cl++08), which is a generalization of the derivative for non-differentiable functions.
do(t)
We now remind the reader of a recent result concerning the implicit bias of gradient flow over the exponential and logistic losses for homogeneous neural networks. Note that since homogeneous networks satisfy sign( ((a0; = sign ( (0; x)) for any a > O, the sign of the network output of homogeneous networks depends only on the direction of the parameters 0. The following theorem provides characterization of the implicit bias of gradient flow by showing that the trajectory of the weights (t)) converge in direction to first-order stationary point of a particular constrained
optimization problem, where 0 converges in direction to Ô means lim,
O(L)
à
Note that
T
since ReLU networks are non-smooth, the first-order stationarity conditions (i.c., the Karush- Kuhn- Tucker conditions, or KKT conditions for short) are defined using the Clarke subdifferential (see Lyu and Li [L20 and Dutta et al. [3ut+13] for more details on the KKT conditions in non-smooth optimization problems).
Theorem 2.1 (Paraphrased from Lyu and Li [L200] and Ji and Telgarsky (T20)) ). Let (0:-)) be a homogeneous ReLU neural network parameterized by O. Consider minimizing either the exponential or the logistic loss over a binary classification dataset {(x;, br using gradient flow. Assume that there exists time to such that (((()))) < n (and thus y (O((t)) xx) >> 0 for every x.). Then, gradient flow converges in direction to a first-order stationary point (KKT point) of the following

---

maximum margin problem in parameter space:
ming 2 |012 s.t. [i (0;x0 21.
(2)
Moreover, [(e(t)) + 0 and ||((t]] - oc as cc.
Theorem 2.1 gives characterization of the implicit bias of gradient flow with the exponential and the logistic loss for homogeneous ReLU networks. Note that the theorem makes no assumption on the initialization, training data, or number of parameters in the network; the only requirement is that the network is homogeneous and that at some time point in the gradient flow trajectory, the network is able achieve small training loss. The theorem shows that although there are many ways configure the network parameters to achieve small training loss (via overparameterization). gradient flow only converges (in direction) networks which satisfy the KKT conditions of Problem (2). is important to note that satisfaction of the KKT conditions is not sufficient for global optimality of the constrained optimization problem [SS222.. We further note that if the training data are sampled i.i.d. from distribution with label noise (e.g., a caass-coniiionall Gaussian mixture model, or a distribution 3) with some nonzero probability), networks which have parameters that are feasible w.r.t. the constraints of Problem (2) have overfit to noise, and understanding the generalization behavior of even globally optimal solutions to Problem ( in this setting is the subject of significant research [Mon+19] CL22 [re+23a]
where labels y/ are flipped
Finally, we introduce the distributional setting that we consider. We consider distribution Delusters On R x {-1,1) 1} that consists of is clusters with means 2x()) ...., (h E R and covariance o (i.e., Gaussian mixture model), such that the examples in the j-th cluster are labeled by yاو (-1,1))
More formally, (x, y) Delusters is generated as follows: we draw j ~ U((k) and N(H00)o²1a))
and set y y(), We assume that there exist j. [k] with y * y(5), Moreover, we assume the following:
Assumption 2.2. We have:
||00||| vd all E [k].
0<05L.
k (maxiz)) (1, [(0)) 4o + 1) =d= d-lovaln(dd)+
Example 1. Below we provide simple examples of settings that satisfy the assumption:
Suppose that the cluster means satisfy ( ا O(Vd) for every i + j. This condition holds, e.g., if we choose each cluster mean i...d from the uniform distribution on the sphere -d-gi=1 (see, e.g., Vardi, Yehudai, and Shamir [VYS22 Lemma 3.1 Let
a = 1, namely, each cluster has a radius of roughly Vd. Then, the assumption can be satisfied by choosing =(Vd).
Suppose that the cluster means are exactly orthogonal (i.e., (4(() (100)i00)) ) = 0 for all i + j), and a = 1//dd. Then, the assumption can be satisfied by choosing k = (d).
If the number of clusters is k = Ö(1. then the assumption may hold even where maxi75 (1 | = ((d) (for any a 1).
few remarks are in order. First, the assumption that ||00| is exactly v is for convenience, and we note that it may be relaxed (to have all cluster means approximately of the same norm) without affecting our results significantly. Note that in the case where a = 1, the radius of each cluster roughly of the same magnitude the cluster mean. Second, we assume for convenience that
the noise (i.e., the deviation from the cluster's 's mean) is drawn from a Gaussian distribution with covariance matrix x² L2 However, we note that this assumption can be generalized any distribution Daoise such that for every unit vector the noise E ~ Dnoise satisfies w.h.p. that () Ô(L) and Ell = Ö(V)). This property holds, e.g., for didimensiionl Gaussian distribution N(O, E), where [r[=] = d and ||E|| = O(1) (see Frei et al. [Fre+23b] Lemma 3.3]), and more generally for a class of sub-Gaussian distributions (see Hu et al. (Hu+20) Claim 3.1.). Third, note that the third part of Assumption 2.2 essentially requires that the number of clusters & cannot be too large
5

---

and the correlations between cluster means cannot be too large. Finally, we remark that when k is small, our results may be extended to the case where o > 1. For example, if l: = ( and maxizi (4 10)) = Ö(vd), our generalization result (Theorem 3.1 can be extended to the case where = 88) We preferred to avoid handling 1 in order simplify the proofs.
Moreover, it is worth noting that Assumption 2.2 implies that the data is w.h.p. linearly separable (see Lemma 2.J below, and proof in Appendix B). However, in this work we consider learning using overparameterized ReLU networks, and it is not obvious priori that gradient methods do not harmfully overfit in this case. Indeed, it has been shown that ReLU networks trained by gradient descent can interpolate training data and fail to generalize well in some distributional settings [Kou+23].
Egelk) g p()), Then, with probability at least 1 - 2d" (n(d)/2 = 1 - (1((1) over (x, y) D Delustera we have y = sign(uTx)
Lemma 2.1. Let u
3 Generalization
In this section, show that under our assumptions the distribution Delustess gradient flow does not harmfully overfit. Namely, even if the learned network is highly overparameterized, the implicit bias of gradient flow guarantees convergence to a solution that generalizes well. Moreover, show that the sample complexity is optimal. The main result of this section is stated in the following theorem:
Theorem 3.1.
Let c, (0, Let S {(x, W)] S x x be training set drawn i.dd from the distribution D Delusters where 2 Inn"(d) Let be a depth-2 ReLU network such that = [W1,.... Wm, b, v] is a KKT point of Problem (2). Provided d is sufficiently large such
L d and S min {V 4/32 vB dinld)/4 , ddddd//2)
that ô < 3
then with probability
at least 8 over S, we have
Pr(x.o)~Demm. [xNo(x) S Sc.
The sample complexity requirement in Theorem 3.1 is n Š((k). Essentially, it requires that the dataset S will include at least one example from each cluster. Clearly, any learning algorithm cannot perform well on unseen clusters. Hence the sample complexity requirement in the theorem is tight (up to log factors).
The assumptions in Theorem 3.1 include upper bounds on 8-1 and n. Note that the expressions poly(d), then
in these upper bounds are super-por soper-polynomial d, and in particular if n, 8-1 c- these assumptions hold for a sufficiently large d. Admittedly, enforcing an upper bound on the training dataset's ' size is uncommon generalization results. However, if n is exponential in d, is not hard to see that there will be clusters which have both positive and negative examples within radius a of the cluster center, essentially introducing a form of label noise to the problem. Since KKT points of Problem (2) interpolate the training data, this would imply that the network has interpolated training data with label noise-in other words, it has 'overfit' to noise. Understanding the generalization behavior of interpolating neural networks in the presence of label noise is very technically challenging problem for which much unknown, especially if one seeks to understand this by only relying upon the properties of KKT conditions for margin maximization. It is noteworthy that all existing non-var voc-ouu generalization bounds for interpolating nonlinear neural networks the presence of label noise require < d [FCB22 Cao+22 XG23 Fre+23a Kou+23)
Combining Theorem 3.1 with Theorem 2.1 we conclude that w.h.p. over training dataset of size n 2 k In (d) (and under some additional mild requirements), if gradient flow reaches empirical loss smaller than 1 then it converges in direction to a neural network that generalizes well. This result width-indee aafth-inddpenddett thus, it holds irrespective of the network width. Specifically, even if the network is highly overparameterized, the implicit bias of gradient flow prevents harmful overfitting. Moreover, the result does not depend directly on the initialization whenever gradient flow reaches small empirical loss after some finite time. Thus, by relying on the KKT conditions of the max-margin problem instead of analyzing the full gradient flow trajectory, we can prove generalization without the need to prove convergence.
gradient flow. That is, holds

---

3.1 Proof idea
The proof of Theorem 3.1 is given in Appendix [Wi...., Wm. b, v] be KKT point of Problem 2
Here we discuss the high-level approach. Let 0
Thus, we have (x( = Z uy0(w, x x+b)).
Since A satisfies the KKT conditions of Problem then there are λι,..... An such that for every j E [m] we have
EiE(n] As Vw, (xxNV(Xx)) SiE(M) ,
w
where d'.5 is a subgradient of & at w x; + by. i.e., if w x4 + # 0 then 0/ = 1 1[w] x; +b; 2 0).
and otherwise d(j is some value in [0, 1]. Also we have X; 2 0 for all i, and X; = 0f yx,o $ 1. Likewise, we have
bj = Eietn de Vo, (v,No(x;))= = Exe(m) Aanoydl
(4)
In the proof, using careful analysis of Eq. 3 and we show that w.h.p. Ng classifies correctly
fresh example. More precisely, the main argument can be described as follows. We denote J : [m]
J :- (j E J vy 0}. and J_ Uj E J U. < OJ. Moreover, we denote / == [r] and Q = [k]. For q E Q we denote T(o)- (i E T x, is in cluster q) Consider the network's output for an input
from cluster r E Q with y(r) 1. Since Since.No(x) EjEr, uy0(w]]x+t)) x,)
b,)+ Σjer 2/0(w]] xb)
and (0z) 2 2, we have
No(x) 2 Ejer, (5(W]x bb) Ejes [ b,).
(5)
This suggests the following possibility: if we can ensure that Eje,, uw( x + bj) is large and positive while Ejer uyo(w] x x b;) is not too negative, then the network will accurately classify the example x. Using Eq. 3 and (4) and that yrr) (so y = for i E (())), the first term in the above decomposition is equal
Ejer, (y(w) x + bz) = Ejer, Bj [Eier Aanry xx]x+1))
= -Eje,, (Eienoo Anool (xF (xxx+ x 1)) + Eneou() Eiero A x + +)]
2 (ierro) EjEr, A17o (x] x - Enerres Everin Ese,, o x 1/.
Since comes from cluster r and the clusters are nearly orthogonal, the pairwise correla- tions x, x will be large and positive when E ((r) but will be small in magnitude when i E I(9) for g A r. Thus, we can hope that this term will be large and positive if we can show that the quantity Eieno, Ejes+ >roooly is not too small relative to the quantity EgERUEt (rl EiEro Σjer, Ar1f By similar arguments, in order to show the second term in Eq. (5) not too negative, we need understand how the quantity EiEro Ejer_ de130% varies across different clusters 9 E Q. Hence, in the proof we analyze how the quantities Eiero Eje,, X15%, Eigra Ejer X113% relate to each other for different clusters q Q, and show that these quantities are all of the same order. Then, we conclude that w.h.p. x is classified correctly.
Robustness
We begin by introducing the definition of -
Definition 4.1. Given some function R(-), we say that neural network No is R(d)-robust w.r.t. distribution Dx over _dd for every r = o()), with probability 1 - oa(1) over x ~ Dx for every x' E Rd with Xx x'1 S r we have sign(No(x')) = (ig)(No(x)).
Thus, neural net Ng is R(d)-robust if changing the label of example cannot be done with perturbation of size of R()). Note that we consider here l, perturbations.
For the distribution Delusters under consideration, it is straightforward to show that classifiers cannot be R(d -rouutt if R(d) w(Vd): since the distance between examples in different clusters is w.h.p.
7

---

O(vd), it is clearly possible to flip the sign of an example with a perturbation of size ( In particular, the best we can hope for is v dd-robustness. In the following theorem, we show that there exist two-layer ReLU networks which can both achieve small test error and the optimal level of vd-robustness.
Theorem 4.1. For every r 2 there exists a depth-2 ReLU network N : Rd - R of width such that for (x, u) ~ Delusters. with probability at least 1- we have (x(()) 2 1, and flipping the sign of the output requires perturbation of size larger than La S (for a sufficiently large d). Thus, N
classifies the data correctly w.h.p., and it is Vd-robust w.r.f. Dxx
Thus, we see that Vd-robust networks exist. In the following theorem, we show that the implicit bias of gradient flow constrains the level of robustness of trained networks whenever the number of clusters k is large.
Theorem 4.2. Let c, E 1). Let S ((x,, y6
D==1 C Rdd x {-1,1} be training set drawn i.i.d.
from the distribution Delusters, where 2 Inn (d). We denote Q+ - (9 E [k] s/99) = 1} and Q-
{g E [k] :y(1) =1], and assume that min Q-1 [0-1]
} 2 efor some > O. Let No be depth-2
ReLU network such that O = [W1,..., Wm, b, v] is a KKT point of Problem
2 Provided d is suf-
ficiently large such that 8-1 < (dla(d)-1 and n S min V 4/32
vB 3
dinld//, o ddu(d)/2
with probability at least 1 - 5 over S, there is a vector 2 EjE(h) اوو) n0) with n > 0 and
|z|| S ((V4(k)) such that
Pr(x.g))Deeaon (sign(No(x)) + sign(No(x yz)) 21
Note that the expressions in the upper bounds on and 8-1 are super-polynomial in d, and hence these requirements are mild (e.g.. they hold for a sufficiently large when n, 8-.6, 0011_-- c- = poly(d)) (d)). As mentioned in the discussion following Theorem 3.1 believe removing the requirement for an upper bound on n would be highly nontrivial.
Theorem 4.2 implies that if ch wa(1), then w.h.p. over the training dataset, every KKT point of Problem ( is not Vd-robust. Specifically, if is constant, namely, at least constant fraction of the clusters have positive labels and a constant fraction of the clusters have negative labels, then the network is not Vd-robust if = (1). Recall that by Theorem 3.1 we also have w.h.p. that every KKT point generalizes well. Overall, combining Theorems 2.1
4.1 and 4.2 we conclude k In (d), if gradient flow reaches
3.1
that for e²k = (1), w.h.p. over a training dataset of size empirical loss smaller than 2. then converges in direction to a neural network that generalizes well but is not Vd-robust, even though there exist v Vd-robust networks that generalize well. Thus, in our setting, there is bias towards solutions that generalize well but are non non-robust.
Example 2. Consider the setting from the first item of Example 7 Thus, the cluster means satisfy @(vd). Suppose that @(1), namely, there is at least a constant fraction of clusters with each label { {-1,1}, Then, the adversarial perturbation z. from Theorem 4.2 satisfies ||z|| = O (Vdia = Ô (d'/4) = o(va).
Kn ااأفور (VV)) for every i + j. and we have a = 1 and k
Similarly to our discussion after Theorem 3.1 we note that Theorem 4.2 is widtt-inndependent, i.e., it holds irrespective of the network width. It implies that we cannot hope to obtain a robust solution by choosing an appropriate width for the trained network. As we discussed in the related work section, Bubeck, Li, and Nagaraj [BL22]] and Bubeck and Sellke [BS2I] considered the expressive power of neural networks, and showed that overparameterization might be necessary for robustness. By Theorem 4.2 even when the network is overparameterized, the implicit bias the optimization method can prevent convergence robust solutions. Moreover, our result does not depend directly on the initialization of gradient flow. Recall that by Theorem 2. gradient flow reaches small empirical loss then it converges in direction to KKT point of Problem (2). Hence our result holds whenever gradient flow reaches a small empirical loss.
Note that in Theorem 4.2 the adversarial perturbation does not depend on the input (up to sign). It corresponds to the well-known empirical phenomenon of universal adversarial perturbations, where one can find a single perturbation that simultaneously flips the label of many inputs (cf. [Moo+17]
8

---

Moreover, the same perturbation applies to all depth-2 networks to which gradient flow might converge (i.e., all KKT points). It corresponds the well-known empirical phenomenon of transferability in adversarial examples, where one can find perturbations that simultaneously flip the labels of many different trained networks (ef. [Liu+17] AM18).
Zha+21].
It is worth noting that Theorems 3.1 and 4.2 demonstrate that trained neural networks exhibit different learning rule, irrespective of the number of parameters in
properties than the the network. For example, consider the case where a vd namely, the examples of each cluster are concentrated within a ball of radius O(1) around its mean. Then, the distance between every pair of points from the same cluster is O(1), and the distance between points from different clusters is 22( (V)d). In this setting, both the 1-nearest-neighhour classifier and the trained neural network will classify a fresh example correctly w.h.p., but in the 1-nearest-neighhour classifier flipping the output's ss sign will require perturbation of size (()d), while in the neural network much smaller perturbation will suffice.
Finally, we remark that in the limit σ + O, we get a distribution supported on ()),,....
(k), Then,
a training dataset of size n 2 k (d) will contain w.h.p. all examples in the support, and hence robustness w.r.t. test data is equivalent to robustness w.r.t. the training data. In this case, we recover the results of Vardi, Yehudai, and Shamir (VYS22) which characterized the non-robustness of KKT points of ReLU networks trained nearly orthogonal training data. In particular, Theorem 4.2 a strict generalization of their Theorem 4.1.
4.1 Proof ideas
Here we discuss the main ideas in the proofs of Theorem 4.1 and 4.2 (see Appendices C and for the formal proofs).
The proof of Theorem 4.1 follows by the following simple construction. The robust network includes k neurons, each corresponding to a single cluster. That is, we have N(() Σ5= uyo(wT + b,),
where 8y = y w d j-th cluster and has negative bias term, such that the neuron is active on points from the j-th cluster, and inactive on points from the other clusters. Then, given a fresh example (x, y) ~ Delusters we show that the network classifies it correctly w.h.p. with margin at least 1. Also, there is w.h.p exactly one neuron that is active on x, and hence the gradient of the network w.r.t. the input is affected only by this neuron and is of size O(1/VZ). Therefore, we need a perturbation of size 22( ((Vdd) in order to flip the output's 's sign.
02 and by- = 22 Note that the j-th neuron points at the direction of the
The intuition for Theorem 4.2 can be described as follows. Recall that in our construction of a robust network above, an example (x. y) Delusters is w.h.p. in an active region of exactly one neuron, and hence in the neighborhood of x the output of the network is sensitive only perturbations in the direction of that neuron. Now, consider the linear model x ++ w T x, where w = Σ 2 fa(9),
is not hard to verify that for (x, ~ Dehusters we have w.h.p. that 0 < yw x S O(1). Moreover, the gradient of this linear predictor is of size ||w|| (V/kd)) Hence, a perturbation of size O(Vd/k), Thus, the linear classifier is non-robust if k: = wa(1). Intuitively. the difference between our robust ReLU network and the non-robust linear classifier is the fact that in the neighborhood of x the robust network is sensitive only to perturbations in the direction of one cluster, while the linear classifier is sensitive to perturbations in the directions of all & clusters. In the proof, we analyze ReLU networks which are KKT points of Problem (2). and show that although these ReLU networks are non-linear, they still sensitive to perturbations in the directions of all k clusters, similarly to the above linear classifier. The formal proof follows by a careful analysis of the KKT conditions of Problem 2 given in Eq. and
flip the output's sign with
We remark that in the proof of Theorem 4.2 we use some technical ideas from Vardi, Yehudai, and Shamir [VYS22). However, there are significant differences between the two settings. For example, they assume that the training data are nearly orthogonal, which only holds when the dimension is large relative to the number of samples; thus, it is unclear whether the existence of small adversarial perturbations in their setting is due to the high-dimensionality of the data or a similar phenomenon exists in the more common n > d setting. At more technical level, their proof relies on showing that

---

in KKT point all inputs must lie exactly on the margin, while in our setting they are not guaranteed lie exactly on the margin.
Discussion
In this paper, considered clustered data, and showed that gradient flow in two-layer ReLU networks does not harmfully overfit, but also hinders robustness. Our results follow by analyzing the KKT points of the max-margin problem in parameter space. In distributional setting, the clusters well-separated, and hence there cxist robust classifiers, which allows us to consider the effect of the implicit bias of gradient flow both generalization and robustness. Understanding generalization and robustness additional data distributions and neural network architectures is a challenging but important question. As possible next step, it would be interesting to study whether the approach used in this paper can be extended to the following data distributions:
First, our assumption cannot be too large, and as a result the data is linearly separable (Lemma 2.1). We conjecture that results hold even for significantly larger number of clusters, such that the data is not linearly separable.
the data distribution (Assumption 2.2) implies that the number of clusters
Second, it would be interesting to understand whether our generalization result holds for linearly separable data distributions that are not clustered. That is, given a distribution that is linearly separable with some margin y 0 and training dataset that is large enough to allow learning with a max-margin linear classifier, are there KKT points the max-margin problem for two-layer ReLU networks that do not generalize well? In other words, do ReLU networks that satisfy the KKT conditions generalize at least as well as max-margin linear classifier??
Acknowledgments and Disclosure of Funding
SF, GV. PB, and NS acknowledge the support of the NSF and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through awards DMSS2031882 and #814639, and of the NSF through grant DMS-2023505.
References
[AM18]
Naveed Akhtar and Ajmal Mian. "Threat of adversarial attacks on deep learning in computer vision: A survey". In: Ieee Access (2018), pp. 14410-14430 (Cited on
pages 2 9
[AL21]
Zeyuan Allen-Zhu and Yuanzhi Li. "Feature purification: How adversarial training performs robust deep learning". In: JEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). 2021 (Cited on B)
[ACW18] Anish Athalye, Nicholas Carlini, and David Wagner. "Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples". In: International conference on machine learning (ICML). 2018 (Cited on page D..
[BBC21] Peter Bartlett, Sébastien Bubeck, and Yeshwanth Cherapanamjeri. "Adversarial examples in multi-layer random relu networks". In: Advances in Neural Information Processing
Systems (NeurIPS) (2021) (Cited on page 3
[Bub+21] 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 (NeurIPS) (2021) (Cited on page
[Bub+19] Sébastien Bubeck, Yin Tat Lee, Eric Price, and Ilya Razenshteyn. "Adversarial examples from computational constraints". In: International Conference Machine Learning (ICML). 2019 (Cited on page 3).
[BL221] Sébastien Bubeck, Yuanzhi Li, and Dheeraj M Nagaraj. "A law of robustness for two- layers neural networks". In: Conference on Learning Theory (COLT). 2021 pages
2021 (Cited on
g).
10

---

[BS21]
Sébastien Bubeck and Mark Sellke. "A universal law of robustness via isoperimetry".
In: Advances in Neural Information Processing Systems (NeurIPS) (2021) (Cited on
pages
3
88.
[Cao+22]
Yuan Cao, Zixiang Chen, Mikhail Belkin, and Quanquan Gu. "Benign Overfitting in
Two-layer Convolutional Neural Networks". In: Preprint, arXiv:2202.06526 (2022)
(Cited on o)
[CW17] Nicholas Carlini and David Wagner. "Adversarial examples are not easily detected:
Bypassing ten detection methods". In: Proceedings of the 10th ACM workshop on artificial intelligence and security. 2017 (Cited on page I.
[CW18] Nicholas Carlini and David Wagner. "Audio adversarial examples: Targeted attacks on speech-to-text In: IEEE Security and Privacy Workshops (SPW). 2018 (Cited on page
[CL21] Niladri S. Chatterji and Philip M. Long. PFinite-sample analysis of interpolating linear classifiers in the overparameterizze regime". In: Journal of Machine Learning Research 22. 129 (2021), pp. 1-30 (Cited on page(5).
[CB20]
Lenaic Chizat and Francis Bach. "Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss". In: Conference on Learning Theory (COLT). 2020 (Cited on page 3
[Cla+08]
Francis H Clarke, Yuri S Ledyaev, Ronald Stern, and Peter R Wolenski. Nonsmooth analysis and control theory. Vol. 178. Springer Science & Business Media, 2008 (Cited on page
[CH20]
Francesco Croce and Matthias Hein. "Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks". . In: International conference on machine learning (ICML). 2020 (Cited on page]].
[DS20]
Amit Daniely and Hadas Shacham. "Most ReLU Networks Suffer from & Adversarial Perturbations". In: Advances in Neural Information Processing Systems (NeurIPS) (2020) (Cited on page(3)
[DB22]
Elvis Dohmatob and Alberto Bietti. "On the (non-) robustness of two-layer neural networks in different learning regimes". In: arXiv preprint arXiv:2203.1186. (2022) (Cited on page 3
[Dut+13]
Joydeep Dutta, Kalyanmoy Deb, Rupesh Tulshyan, and Ramnik Arora. "Approximate KKT points and a proximity measure for termination". In: Journal of Global Optimiza- tion 56.4 (2013), pp. 1463-1499 (Cited on page(4)
[FFF18]
Alhussein Fawzi, Hamza Fawzi, and Omar Fawzi. "Adversarial vulnerability for any classifier". In: Advances in neural information processing systems (NeurIPS) (2018) (Cited on page 3).
[FCB22]
Spencer Frei, Niladri S. Chatterji, and Peter L. Bartlett, "Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data". In: Conference on Learning Theory (COLT). 2022 (Cited on page 6
[Fre+23a] Spencer Frei, Gal Vardi. Peter L. Bartlett, and Nathan Srebro. "Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization". In: Preprint, arXiv:2303.0 2302.01622 (2023) (Cited on pages 5 6).
[Fre+23b] Spencer Frei, Gal Vardi, Peter L. Bartlett, Nathan Srebro, and Wei Hu. "Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data". In: International Confer- ence on Learning Representations (ICLR). 2023 (Cited on pages 3
[GSS15] Ian J Goodfellow. Jonathon Shlens, and Christian Szegedy. "Explaining and harnessing adversarial examples". In: International Conference on Learning Representations (ICLR). 2015 (Cited on pages 3
[Hai+22] Niv Haim, Gal Vardi, Gilad Yehudai, Ohad Shamir, and Michal Irani. "Reconstruct- ing training data from trained neural networks". In: Advances Neural Information Processing Systems (NeurIPS) (2022) (Cited on 3).e
[Hu+20]
Wei Hu, Lechao Xiao, Ben Adlam, and Jeffrey Pennington. "The surprising simplic- ity of the early-time learning dynamics of neural networks". In: Advances in Neural Information Processing Systems (NeurIPS). 2020 (Cited on page(5).
[JT20] Ziwei Ji and Matus Telgarsky. "Directional convergence and alignment in deep learning". In: Advances in Neural Information Processing Systems (NeurIPS). 2020 (Cited on pages 4
11

---

[KH18]
Mare Khoury and Dylan Moddield-Menelle "On the geometry of adversarial examples". In: Preprint, arXiv:1811.000 0.0525 (2018) (Cited on page().
[KYS23]
Guy Kornowski, Gilad Yehudai, and Ohad Shamir. "From Tempered to Benign Overfit- ting in ReLU Neural Networks". In: arXiv preprint arXhv:2305./5141 (2023) (Cited on page
[Kou+23]
Yiwen Kou, Zixiang Chen, Yuanzhou Chen, and Quanquan Gu. "Benign Overfitting for Two-layer ReLU Networks". In: International Conference on Machine Learning (ICML). 2023 (Cited on page()).
[Kun+22]
Daniel Kunin, Atsushi Yamamura, Chao Ma, and Surya Ganguli. "The Asymmetric Maximum Margin Bias of Houasi-Hmoggeeouss Neural Networks". In: arXiv preprint ar wrXiv2220000822 (2022) (Cited on 3)
[KGB17] Alexey Kurakin, Ian Goodfellow, and Samy Bengio. "Adversarial machine learning at scale". In: International Conference on Learning Representations (ICLR). 2017 (Cited page
[LM00]
Beatrice Laurent and Pascal Massart. " "Adaptive estimation of quadratic functional by model selection". In: Annals of Statistics (2000), pp. 1602-1338 (Cited on page (5).
[Liu+17] Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. "Delving into transferable adversarial examples and black-box attacks". In: International Conference on Learning Representations (ICI.).. 2017 (Cited pages (..).
[LL20] Kaifeng Lyu and Jian Li. "Gradient descent maximizes the margin of homogeneous neural networks". In: International Conference on Learning Representations (ICLR). 2020 (Cited on pages 4
[Lyu+21] Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, and Sanjeev Arora. "Gradient descent on two-layer nets: Margin maximization and simplicity bias". In: Advances in Neural Information Processing Systems (NeurIPS). 2021 (Cited on page
[Mad+18]
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. "Towards Deep Learning Models Resistant Adversarial Attacks". In: Interna- tional Conference on Learning Representations (ICLR). 2018 (Cited on page DI
[Mon+19]
Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. "The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime". In: Preprint, arXiv:1911.011 1.01544 (2019) (Cited page 5} Andrea Montanari and Yuchen Wu. "Adversarial Examples in Random Neural Networks with General Activations". In: arXiv preprint arXiv:2233. 17209 (2022) (Cited on page 3) Seyed-Mohsen Moosavi-Dezfoolli Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. "Universal adversarial perturbations". In: Proceedings of the IEEE conference on com- puter vision and pattern recognition (CVPR). 2017 (Cited on pages 2
[MW22]
[Moo+17] 17]
[Ney+17]
Behnam Neyshabur, Srinadh Bhojamapalli,, David McAllester, and Nati Srebro. "Explor- ing generalization in deep learning". In: Advances in Neural Information Processing Systems (NeurIPS). 2017 (Cited on page D.
[Pap+17] Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. "Practical black-box attacks against machine learning". In: Proceedings of the 2017 ACM on Asia conference on computer and communications security. 2017 (Cited on page [].
[Pap+16]
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. "Distillation as a defense to adversarial perturbations against deep neural networks". In:
IEEE symposium on security and privacy (SP). 2016 (Cited on page [T.
[PL20]
Mary Phuong and Christoph H Lampert. "The inductive bias of ReLU networks on orthogonally separable data". In: International Conference on Learning Representations (ICLR). 2020 (Cited on [3.
[SVL22]
Itay Safran, Gal Vardi, and Jason D Lee. "On the Effective Number Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias". In: Advances in Neural Information Processing Systems (NeurIPS) (2022) (Cited on page
[SBG21] Roei Sarussi, Alon Brutzkus, and Amir Globerson. "Towards understanding learning in neural networks with linear teachers". In: International Conference on Machine
Learning (ICML). 2021 (Cited p
12

---

[Sch+18]
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. "Adversarially robust generalization requires more data". In: Advances in neural information processing systems (NeurIPS) (2018) (Cited on page
[Sha+19]
Ali Shafahi, W Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. "Are adversarial examples inevitable?" In: International Conference on Learning Representa- tions (ICLR). 2019 (Cited page(3).
[Sha+20] Harshay Shah, Kaustav Tamuly, Aditi Raghunathan, Prateek Jain, and Pranceth Ne- trapalli. "The pitfalls of simplicity bias in neural networks". . In: Advances in Neural Information Processing Systems (NeurlPS) (2020) (Cited on p)ge
[SMB21] Adi Shamir, Odelia Melamed, and Oriel BenShmuel. "The dimpled manifold model of adversarial examples in machine learning" . In: Preprint, 100::1006.10111 (2021) (Cited on page 3)
[Sin+21] Vasu Singla, Songwei Ge, Basri Ronen, and David Jacobs. "Shift invariance can re- duce adversarial robustness". In: Advances in Neural Information Processing Systems (NeurIPS) (2021) (Cited on page
[Sze+14] Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. "Intriguing properties of neural networks". In: Interna- tional Conference on Learning Representations (ICLR). 2014 (Cited on page D.
[Var22]
Gal Vardi. "On the Implicit Bias in Deep-Learning Algorithms". In: Preprint, arXiv:2208. /259/ (2022) (Cited on page 2
[VSS22]
Gal Vardi, Ohad Shamir, and Nathan Srebro. "On Margin Maximization in Linear and ReLU Networks". In: Advances in Neural Information Processing Systems (NeurIPS). 2022 (Cited on 3
[VYS22]
Gal Vardi, Gilad Ychudai, and Ohad Shamir. "Gradient Methods Provably Converge to Non-Robust Networks". In: Advances in Neural Information Processing Systems (NeurIPS). 2022 (Cited on pages 51.
[Wan+20]
Haohan Wang. Xindi Wu, Zeyi Huang, and Eric P Xing. "High-freqeency component helps explain the generalization of convolutional neural networks". In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). 2020 (Cited on page 3)
[Wa++22]
Yunjuan Wang, Enayat Ullah, Poorya Mianjy, and Raman Arora. "Adversarial Robust- ness is at Odds with Lazy Training". In: Advances in Neural Information Processing Systems (NeurIPS) (2022) (Cited on page
[WK18]
Eric Wong and Zico Kolter. "Provable defenses against adversarial examples via the convex outer adversarial polytope". In: International Conference on Machine Learning (ICML). 2018 (Cited on page I].
[WRK20]
Eric Wong, Leslie Rice, and Zico Kolter. "Fast is better than free: Revisiting adversarial training". In: International Conference on Learning Representations (ICLR). 2020 (Cited on page I].
[Wu+20] Zuxuan Wu, Ser-Nam Lim, Larry S Davis, and Tom Goldstein. "Making an invisibility cloak: Real world adversarial attacks object detectors". In: European Conference on
Computer Vision (ECCV). 2020 (Cited on page D
[XG23] Xingyu Xu and Yuantao Gu. "Benign overfitting of non-smooth neural networks beyond lazy training".. In: International Conference on Artificial Intelligence and Statistics
(AISTATS). Ed. by Francisco Ruiz, Jennifer Dy, and Van-Willem van de Meent. 2023 (Cited on (o.
[Zha+21]
Chaoning Zhang, Philipp Benz, Chenguo Lin, Adil Karjauv, Jing Wu, and In So Kweon. "A survey on universal adversarial attack". In: International Joint Conference on Artificial Intelligence (IJCAI) (2021) (Cited on pages 2 9
[Zha+17] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. "Delv- ing into transferable adversarial examples and black-box attacks". In: International Conference on Learning Representations (ICLR). 2017 (Cited on page
13


Reviews:
[{"review_id": "DieIflkW6E", "reviewer": "Reviewer_DAg1", "summary": "This paper studies the generalization and robustness of solutions obtained by gradient flow on two-layer ReLU networks. Under a distributional setting where the data is sampled from a Gaussian mixture distribution, this paper shows that the gradient flow is biased towards solutions that generalize well, but are vulnerable to adversarial examples. The theorems are built on LL20 and JT20 (Theorem 2.1). The authors also show the existence of a robust solution in this setting and prove that any solution obtained via gradient flow is non-robust.  Although the assumption is a bit restrictive, the result is novel and interesting. The authors also provide a few examples which help to understand the assumptions.", "questions": "1. The authors emphasize that the result hold in the rich regime. Could the authors be more specific, as there is no discussion about the rich regime in the results?\n2. Does such a result hold for regression, in other words, what about other loss functions, such as squared error?", "limitations": "The authors assume that the data is clustered and the number of clusters is not too large, therefore the data is linearly separable. This is a relatively strong assumption. The relaxation of this assumption and extensions to other settings would be interesting.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. This paper is well-written and easy to follow. The problem is well-motivated. The authors provide a thorough discussion of the related work.\n2. The theoretical results are solid and interesting, the proof ideas help to understand the results.\n3. This is an active area of research. The contribution is relevant.", "weaknesses": "1. The authors assume that when the training loss is small, the gradient flow will start to converge to a KKT point of some maximum margin problem. What if we have a random initialization, how is this small training loss guaranteed?\n2. This might be relatively minor, but numerical experiments would help to demonstrate the vulnerability (non-robustness) of the training of two-layer ReLU networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions.  We respond to specific points below.\n\n### Assumption of small training loss:\n\nIndeed, the implicit bias result kicks in when gradient flow reaches a sufficiently small training loss. One of the advantages of relying on the KKT conditions of the max-margin problem instead of analyzing the full trajectory of gradient flow is that it allows us to separate the convergence question from the generalization and robustness questions. Hence, even in settings where proving convergence is difficult, we may prove generalization and non-robustness.  Nevertheless, as the reviewer mentioned, proving convergence in our setting is an interesting question. For wide networks convergence can be shown by an NTK analysis, and in the general case this question is open. We will add a discussion on this issue.  \n\n\n### Experiments: \nAlthough we agree that a thorough experimental investigation of our results would be beneficial, we are not convinced the time and paper-space needed to do them well would be worthwhile.  In particular, although it would be easy to verify the generalization properties and that the universal perturbation $z$ we discover indeed succeeds in adversarial attacks, we believe that simply verifying our theorems are correct with experiments would add little value.   \n\nMore broadly, we think it is worth emphasizing that this work is a part of a series of works on understanding the theoretical foundations of robustness in deep learning.  Many of these works do not include experiments and have been published at NeurIPS, including Bubeck and Sellke’s Outstanding Paper Award-winning work at NeurIPS 2021.  However, we agree that a thorough empirical study that extends our setting and evaluates whether the \"double-edged sword\" effect of the implicit bias occurs more generally is an intriguing topic for future research.\n\n\n### Rich regime: \nHere we are re-using the terminology from, e.g., [1], where by \"rich regime\" refers to neural network training which does not lie in the \"kernel regime\".  The \"kernel regime\" requires a number of assumptions regarding the network width, initialization, etc, and since our setting makes no such assumptions our results hold for networks in the \"rich regime\".  We shall clarify this in the camera ready.\n\n### Other losses:  \nWe are quite interested in exploring the questions in this paper in the regression setting.  However, one difficulty is that there is a much less developed theory about the implicit bias of gradient flow/descent in neural networks with regression losses, which is provably not the minimum-l2 loss in relu networks [2].  This makes it difficult to use our approach which relies upon rather explicit characterizations of the implicit bias of optimization algorithms to characterize the behavior of trained neural nets.    \n\n\n[1] Blake Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, Nathan Srebro. Kernel and Rich Regimes in Overparametrized Models. COLT 2020\n\n[2] Gal Vardi and Ohad Shamir. Implicit Regularization in ReLU Networks with the Square Loss. COLT 2021\n"}, {"review_id": "G0LQsBIL09", "reviewer": "Reviewer_8zLE", "summary": "The authors show under a special data cluster model, the implicit bias of gradient flow converge to KKT points that generalize well but are not robust under l2 perturbations, when robust solutions of the problem exists. Their results are built upon earlier works on KKT points by LL20 and JT20, and the more recent work by VSS22, and extend these results further. \n", "questions": "- Although not strictly necessary for a theroy paper, it would be nice to have some simulations on synthetic data since it is easy to set up with the data model the authors assume. \n\n", "limitations": "- The authors state clearly the assumptions used for their results. Negative societal impacts not applicable here. \n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The authors study the gradient flow solution of 2-layer ReLU network on a mixture of Gaussian distribution, and prove that while the solution generalizes well (classifies almost every test point correctly with high probability), it is not robust (can change its classification with perturbation much less than \\sqrt{d}, the optimal achievable robustness). This is a very nice result following up on the previous line of work on this topic. \n\n- The paper is well-written and clear. While the result is technical the presentation is easy to follow and main proof ideas succinctly presented in the limited space. \n", "weaknesses": "- Given the assumption on large cluster separation (\\sqrt{d} between cluster centers) and small variance of the clusters (\\sigma<1), it feels like the clusters behave very much like individual isolated points/samples. In view of this, the differentiation with the results of VSS22 in the introduction section appear to be weaker than the authors claim, as the cluster means take the role of training samples in VSS22, which still requires near-orthogonality. Also, results wrt test data is also easier under the data assumptions used in this paper because test data essentially takes the same label from their respective cluster means. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review of our work.  We respond to two comments/questions below:\n\n### Difference with VYS22: \nAt a high-level, the reviewer is correct that there are parallels between clusters in our setting and samples in their setting. However, there are a few important differences.  The first is that when $\\sigma=1$ the distance between points in the same cluster is of the same order as the distance between points in different clusters (or the distance between cluster means). So the clustered setting is significantly different from the isolated points from VYS22.  The second is a more conceptual difference, which is that their results require that the ambient dimension $d$ is much larger than the number of samples $n$; the high-dimensional setting often has different generalization behavior than in the low-dimensional setting (e.g., overfitting can be 'benign' in the high-dimensional setting, but harmful in low-dimensional setting [1]).  Moreover, their analysis held for arbitrary labels $y_i$ of the training data, and it was unclear how an underlying distribution over $x$ and a signal (in the form of a conditional distribution of $y|x$) would affect both generalization and the existence of adversarial test examples.\n\n\n\n### Experiments: \nAs we mention to Reviewer DAg1, although we agree that a thorough experimental investigation of our results would be beneficial, we are not convinced the time and paper-space needed to do them well would be worthwhile.  In particular, although it would be easy to verify the generalization properties and that the universal perturbation $z$ we discover indeed succeeds in adversarial attacks, we believe that simply verifying our theorems are correct with experiments would add little value. However, we agree that a thorough empirical study that extends our setting and evaluates whether the \"double-edged sword\" effect of the implicit bias occurs more generally is an intriguing topic for future research.\n\n\n[1] Guy Kornowski, Gilad Yehudai, Ohad Shamir. From Tempered to Benign Overfitting in ReLU Neural Networks. arXiv preprint 2305.15141\n"}, {"review_id": "e4GowltFy5", "reviewer": "Reviewer_kUQf", "summary": "The paper studies the implicit regularization brought by the neural network itself. The authors theoretically prove that in two-layer ReLU networks trained with the logistic loss or the exponential loss, the implicit bias would lead to the solutions that generalize well but non-robust, regardless of the size of the network.", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The topic is valuable and may shed some light on the field.\n- The theoretical proof seems to be sound.", "weaknesses": "- Lacking of even toy experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "zYXWuneZKx", "reviewer": "Reviewer_ZRWm", "summary": "In this paper the authors study the implicit bias of two layers neural networks with ReLU activation, in the setting where the data is composed of independant clusters that \"dont' overlap\" (i.e the probability of having the point of a cluster falling outo the support of another is small, e.g Gaussian of subgaussian). They study both the generalization properties and robustness of the solution obtained by training such network on those data.\n\nThey show that if the network suceed to fit the data (i.e the train loss falls below some threshold) and if we follow the gradient flow:\n* then the weights converge *in direction* \n* the network generalizes well \n* however it converges to a non robust solution (if the dimension is high, the number of clusters is small, and the number of points is small too)\n* whereas in the same setting robust solutions exist! But they are not \"found\" by following the gradient flow\n* the adversarial attack associated is universal and transferable\n", "questions": "## Suggestion\n\nBased on the quality of the literature review, I think a \"summary\" table that contains a high level description of some significant prior works, with their associated hypothesis and main conclusions, would help to situate the paper better, in the spirit of:\n\n| Paper | Hypothesis on model | Hypothesis on data |  Conclusion\n| ----------- | ----------- |  -----------   | ----------- \n| Paper 1|  two-layers ReLu | none | converges\n| Paper 2| homogeneous | almost orthogonal | converges and generalizes\n| Our | etc... | clusters  | generalizes but not robust\n\n## Question\n\nHow much do the results depend on the hypothesis that the activation is a ReLU ? This is part of the requirements of prior work, and clearly the  case of $\\phi(z)\\geq z$ (l236). Do you think that extension to similar shaped activations is straighforward, or very difficult?\n\n\n", "limitations": "The limitations of the hypothesis are discussed, but this part can be detailed in more depth. I have a few remarks and questions.\n\nl207 : I think the formula can be simplified as\n\n$$k(\\max_{i\\neq j} |\\langle \\mu_i,\\mu_j\\rangle|+C+1)\\leq \\frac{1}{10}(d - C + 1)$$\n\nwhere $C$ depends on $d$ and $\\sigma$. An interpretation can be given: \"The centroids must be almost orthogonal to each other, and there shouldn't be too much of them.\". Note sure if $\\frac{1}{10}$ plays a special role, or if any other constant small than $1$ could have done the trick in the proofs. It is worth mentioning it, because this condition is hard to interpret.\n\nWe see that \"it is worth noting that Assumption 2.2 implies that the data is w.h.p. linearly separable\" shows that the hypothesis that the clusters are almost orthogonal is quite strong.\n\nWhat I understand from \"Finally, we remark that when k is small, our results may be extended to the case where σ > 1.\" (l227) hints that what you need is a \"almost orthogonal clusters that don't overlap, so they are separable\" kind-of hypothesis. I am not sure how much additional insights it brings compared to the work of  Vardi, Yehudai, and Shamir [VYS22].\n\nIn particular, the upper bound on $n$ in Thm3.1 is quite surprising, fortunately the discussion l265 \"It is noteworthy\nthat all existing non-vacuous generalization bounds for interpolating nonlinear neural networks in the\npresence of label noise require n < d [FCB22; Cao+22; XG23; Fre+23a; Kou+23].\" helps to understand why this is required.  ", "rating": 5, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper does a good job at explaining the technical hypothesis, their significance, and the practical consequences.  \n  \nThe \"proof idea\" sections contain the right level of details to grasp the ideas.  \n  \nThe paper is easy to read despite its technical content.  \n  \nWhile I am not familiar with the topic, the literature review seems thorough, in particular the contributions of the paper compared to existing works are clear.  \n\nThe main conclusion is significant in my opinion: \"However, the implicit bias also leads to non-robust solutions (susceptible to small adversarial 2-perturbations), even though robust networks that fit the data exist.\", with the additionnal properties that \"the adversarial attack associated is universal and transferable\".\n\nDefinition 4.1 seems to be new, and it is an interesting concept to define robustness.  ", "weaknesses": "The main weakness of the contribution lies in the hypothesis, that are extremely restrictive, and sometimes even more than it seems at first glance.\n\nIt is not clear if those hypothesis have a chance to hold on high dimensional image space, and if the main steps of the reasoning can be adapted to this setting, or if this is just specific to this particular setting and problem (see the section \"Limitations\" below about the setting).\n\n## Thm 4.2\n\nIn Thm 4.2 the quantity is $\\min{(Q_{+}/k,Q_{-}/k)}\\geq c$ can be discussed a bit. In essence, the condition $c^2k=\\omega(1)$ (l332) means that the number of clusters should be **big**, especially if a lot of clusters have the same labels (in which case $c\\approx 0$). But on the other hand assumption 2.2 (third item) tells that the number of clusters should be small.\n\nMoreover the dimension in which the theorems hold should be high (from what I understand of theorem 3.1), but there shouldn't be too much points per clusters (otherwise $n$ would be too big).\n\nIn overall, beyond artificial example 2., is there practical settings that fulfill those hypothesis? I'm scared that the results only apply to a high dimensional setting with very few points per cluster, that are all orthogonal, and that do not overlap. \n\n ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed review.  We respond to their main questions and comments below.\n\n### Assumptions on $Q_{\\pm}$, $k$ and $c$:\n\n We apologize for the confusion here.   Although our analysis can accommodate non-constant $c$, for simplicity one can take $c$ to be a constant, in which case the assumption that $\\min(Q_+/k, Q_-/k)\\geq c$ means that at least a constant fraction of the clusters have positive labels and a constant fraction of the clusters have negative labels. The comment about $c^2 k= \\omega(1)$ can then be thought of as a statement about the number of clusters $k$ rather than $c$.  Thus, the lower bound on $k$ is $\\omega(1)$, while the upper bound on $k$ from Assumption 2.2 is typically much larger (see the first two items in Example 1). We will be sure to revise our manuscript to make this more clear. \n\n\n### Assumptions: high-dimensionality, orthogonality etc.\n\nThe reviewer is concerned that the results only apply to high-dimensional settings with few points per cluster that are all orthogonal and non-overlapping. We want to emphasize that our assumptions can accommodate low-dimensional settings (i.e., where $n \\gg d$) with correlated clusters and many points per cluster. For instance, as in the first bullet in Example 1 and in Example 2, we can permit $k = \\tilde{O}(\\sqrt{d})$ clusters with cluster correlations of order $\\tilde{O}(\\sqrt{d})$ and with $\\sigma=1$.  Since $\\sigma=1$, the cluster radius is roughly $\\sqrt{d}$, so that the cluster radius is of the same order as the distance between clusters. And as we mention in lines 253--255 and 328--330, our results hold when $n = \\mathrm{poly}(d)$ for any polynomial $\\mathrm{poly}()$, so we for instance could have $n = d^{50}$ which is far from a `high-dimensional’ setting. The only setting not covered is when $n$ is super-polynomial in $d$, which we think is a fairly restricted setting but which also would require significant new technical innovations as we mention in line 265. Of course, one can obtain many additional examples such as the above, that satisfy our assumptions. \n\nRegarding practicality of our assumptions, we agree that the setting we consider is somewhat stylized, but we wish to emphasize that in order to characterize whether or not KKT conditions for margin-maximization imply generalization or susceptibility to adversarial attacks for test data, we must make some type of distributional assumption. We think that any distributional assumption comes with benefits and pitfalls, and we are not aware of widely-accepted definitions of ‘real-world distributions’ or ‘practical’ settings. We think the assumptions in our work are fairly natural and uncontrived.  We believe the possibility of a ‘double-edged sword’ of the implicit bias of GF in this setting is a novel and remarkable finding that would be of interest to the NeurIPS community.\n\n### Suggestion on the ​​literature review: \nWe thank the reviewer for the suggestion. In the camera-ready version we will try to situate the paper better in the spirit of the suggested table.\n\n### Assumption of ReLU activation:  \nWe think it would be relatively straight-forward to generalize our results to the leaky ReLU, which is also homogeneous and satisfies a similar inequality to the one you state ($\\phi(z) \\geq \\gamma z$ for $\\gamma >0$ would suffice in many places), at the expense of additional notation and dependence on the $\\gamma$ parameter.  However, we think there would be significant difficulties with extending the result to non-homogeneous settings, since there are essentially no known characterizations of the implicit bias of gradient flow/descent for such cases.\n\n\n### Additional remarks:  \nThank you for your additional suggestions.  We will elaborate more on Line 207 in the camera-ready as the reviewer suggested.  \n\n\nRegarding the comparison with VYS22, as we have mentioned to Reviewer 8zLE, at a high-level the reviewer is correct that there are parallels between clusters in our setting and samples in their setting. However, there are important conceptual differences. First, their results require that the ambient dimension d is much larger than the number of samples n; the high-dimensional setting often has different generalization behavior than in the low-dimensional setting (e.g., overfitting can be 'benign' in the high-dimensional setting, but harmful in low-dimensional setting [1]).  Second, their analysis held for arbitrary labels $y_i$ of the training data, and it was unclear how an underlying distribution over x and a signal (in the form of a conditional distribution of $y|x$) would affect both generalization and the existence of adversarial test examples. We will be sure to add details in the revision which make this more explicit. \n"}, {"review_id": "VxC4fouOB9", "reviewer": "Reviewer_rYUh", "summary": "This paper studies the implicit bias of gradient descent for two-layer ReLU networks for cluster data distribution, and shows the implicit bias towards solutions that generalize well but are vulnerable to adversarial examples. \n", "questions": "1. I'm wondering whether assumption 2.2 (3) can be further simplified by a relationship between k and d, currently the LHS has both d and k.\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper builds upon previous work by Vardi et al, removing the orthogonality assumption of the training data, and considering the robustness of test data instead of training data. Although the analysis is via understanding the KKT points, leveraging the previous work result that the implicit bias of gradient low for homogeneous NN given over exp or logistic loss, such regime belongs to the rich regime instead of the lazy regime, which should be more interesting to understand. Therefore I believe the paper provides good contributions to understanding the generalization and robustness of two-layer NN via gradient methods.\n\nMoreover, the paper provides a complementary result of Bubeck and Sellke, showing that even if the network is overparameterized, the implicit bias of gradient flow prevents convergence to robust solutions. This paper gives concrete examples in which the network generalize well but is non-robust, and the perturbation is independent of the network width. Note that Bubeck and Sellke paper consider regression setting whereas this paper consider classification setting.", "weaknesses": "Instead of the orthogonality of the training samples as assumed by Vardi et al, this paper turns out to have a clustered assumption on data distribution. I understand such an assumption comes from the proof technique, but it still restricts the setting too much that cannot capture the real scenario.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the positive feedback.\n\nRegarding the reviewer’s question: Assumption 2.2 (3) essentially requires that $k$ cannot be too large and the correlations between cluster means cannot be too large. We will discuss this inequality in the camera-ready version to make it a bit easier to digest.\n\n"}]

Author rebuttal:

Meta-review: The paper studies how gradient descent in over-parameterized ReLU networks leads to solutions that generalize well, but lack robustness. Reviewers found the theoretical results interesting and useful, and the paper well written.
Decision: Accept (poster)