Benign overfitting in leaky ReLU networks with moderate input dimension
Authors: Kedar Karhadkar
Erin George
Michael Murray
Guido Montufar
Deanna Needell
Venue: NeurIPS 2024 spotlight (2024)
Keywords: benign overfitting
leaky relu
optimization
generalization
hinge loss
margin
overparameterization
Primary area: learning_theory
TL;DR: We investigate the conditions under which leaky ReLU networks generalize well beyond the regime of near-orthogonal training data.

Abstract: The problem of benign overfitting asks whether it is possible for a model to perfectly fit noisy training data and still generalize well. We study benign overfitting in two-layer leaky ReLU networks trained with the hinge loss on a binary classification task. We consider input data which can be decomposed into the sum of a common signal and a random noise component, which lie on subspaces orthogonal to one another. We characterize conditions on the signal to noise ratio (SNR) of the model parameters giving rise to benign versus non-benign, or harmful, overfitting: in particular, if the SNR is high then benign overfitting occurs, conversely if the SNR is low then harmful overfitting occurs. We attribute both benign and non-benign overfitting to an approximate margin maximization property and show that leaky ReLU networks trained on hinge loss with gradient descent (GD) satisfy this property. In contrast to prior work we do not require the training data to be nearly orthogonal. Notably, for input dimension $d$ and training sample size $n$, while results in prior work require $d = \Omega(n^2 \log n)$, here we require only $d = \Omega(n)$.

Benign overfitting in leaky ReLU networks with moderate input dimension
Kedar Karhadkar Erin George
Michael Murray'
Guido Montúfar 12
Deanna Needell'
(kedar, ,ggeo, mmurray montuffa aratuaa,, deanna) @math. ucla. edu UCLA
Max Planck Institute for Mathematics in the Sciences 'Equal contribution
Abstract
The problem of benign overfitting asks whether is possible for model to perfectly fit noisy training data and still generalize well. We study benign overfitting in two- layer leaky ReLU networks trained with the hinge loss a binary classification task. We consider input data that can be decomposed into the sum of a common signal and random noise component, that lie on subspaces orthogonal to one another. We characterize conditions on the signal to noise ratio (SNR) of the model parameters giving rise benign versus non-benign (or harmful) overfitting: in particular, if the SNR is high then benign overfitting occurs, conversely if the SNR low then harmful overfitting occurs. We attribute both benign and non- benign overfitting to an approximate margin maximization property and show that leaky ReLU networks trained on hinge loss with gradient descent (GD) satisfy this property. In contrast to prior work we do not require the training data to be nearly orthogonal. Notably, for input dimension d and training sample size n, while results in prior work require d Q(n² log n)), here require only d = Ω (n).
1 Introduction
Intuition from learning theory suggests that fitting noise during training reduces a model's perfor- mance on test data. However, has been observed in some settings that machine learning models can interpolate noisy training data with only nominal cost to their generalization performance ZZhang ett al. 2017 [Belkin et al. 2018 2019), phenomenon referred as benign overfitting. Establishing theory that can explain this phenomenon has attracted much interest in recent years and there is now a rich body of work on this topic particularly in the context of linear models. However, the study of benign overfitting in the context of con-linear models, in particular shallow ReLU or leaky ReLU networks, has additional technical challenges and subsequently less well advanced.
Much of the effort in regard to theoretically characterizing benign overfitting focuses showing, under an appropriate scaling of the dimension of the input domain d, size of the training sample number of corruptions k and number of model parameters p that model can interpolate noisy training data while achieving an arbitrarily small generalization error. Such characterizations of benign overfitting position it high dimensional phenomenon indeed, the decrease in generalization error achieved by escaping to higher dimensions at some rate relative to the other aforementioned hyperparameters. However, for these mathematical results to be relevant for explaining benign overfitting as observed in practice, clearly the particular scaling of with respect to n, and needs to reflect the ratios
in practice. Although a number of works, which discuss in Section 1.2 establish benign overfitting results for shallow neural networks, a key and significant limitation they share is the requirement that the input features of the training data least approximately
We provide formal definition of benign overfitting a high dimensional phenomenon in Appendix E
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

orthogonal to one another. To study benign overfitting, these prior works typically assume the input features consist of a small, low-rank signal component plus an isotropic noise term. Therefore, for the near orthogonality property to hold with high probability it is required that the input dimension d scales as d = (2 log n) or higher. This assumption highly restricts the applicability of these results for explaining benign overfitting in practice.
In this work we assume only d = (n) and establish both harmful and benign overfitting results for shallow leaky ReLU networks trained via gradient descent (GD) on the hinge loss. In particular, we consider n data point pairs (xt, Ut) IR x {+1}, where, for some vector
gd-1 and scalar Y E [0. 1], the input features are drawn from a pair of Gaussian clusters I; ~ V(=,Vu, vI- 7aa wo²)) and y/ = sign (B [a.),, v)). The training data is noisy in that & of the points in the training sample have their output label flipped. We assume equal numbers of positive and negative points among clean and corrupt ones. We provide full description of our setup and assumptions in Section Our proof techniques are novel and identify a new condition allowing for the analysis of benign and harmful overfitting which we term approximate margin maximization, wherein the norm of the network parameters is upper bounded by constant of the norm of the max- max-margin linear classifier.
1.1 Summary of contributions
Our key results are summarized as follows.
In Theorem 3.1 we prove that leaky ReLU network trained on linearly separable data with gradient descent and the hinge loss will attain zero training loss in finitely many iterations. Moreover, the network weight matrix W at convergence will be approximately max -argin
in the sense that | = O function, m is the width of the network, and w" is the max-margin linear classifier. We apply this result to derive generalization bounds for the network on test data.
[|="|| av where a is the leaky parameter of the activation
In Theorem 3.2 we establish conditions under which benign overfitting occurs for leaky ReLU networks. If the input dimension d, number of training points n, number of corrupt points k and signal strength y satisfy d (n)) and y 2()). ). then the network will exhibit benign overfitting. We emphasize that existing works on benign overfitting require d = R(n log n) ensure nearly orthogonal data.
In Theorem 3.3, find complementary lower bound for the generalization error to show that, for gradient descent classifiers, the bound in Theorem 3.2 is tight up to a constant in the exponent that can depend on a.
In Theorem 3.4. we find conditions under which non-benign overfitting occurs. If d 2()) and 7 O.)) then the network will exhibit non-benign overfitting: in particular its generalization error will be at least g.
1.2
Related work
There is now a significant body of literature theoretically characterizing benign overfitting in the
context of linear models, including linear regression (Barllttt et al.] 2020 Muthukumar al. 2020
Wu & Xu 2020; Zou et al. 2021] Hastie et al.) 2022 Koehler et al., 2021 Wang et al. 2222
Chatterji & Long 2022 Shamir (002)), logistic regression (Chatterji Long 202 I
Muthukumar
et 20.1 Wang et al.
2021b), max -argin classification with linear and random feature models
(Montanari et al.
2023b Mei & Montanari, 2022] Cao et al. (022) and kernel regression (Liang
& Rakhlin 2020
Liang et al. 2020 Addam & Pennington 2020). However, the study of benign
overfitting in non-lineat linear models is more nascent.
Homogeneous networks trained with gradient descent and an exponentially tailed loss are known to converge in direction
Sarush-Kuhn-Tuckee (KKT) point of the associated max-margin problem Lyu & Li 2020: Ji & Telgarsky, 2200 2 This property has been widely used in prior works to prove benign overfitting results for shallow neural networks. Frei et al. (2022) consider shallow, smooth Ieaky ReLU network trained with an exponentially tailed loss and assume the data is drawn from a mixture of well-separated sub- Lab-Gaussian distributions. A key result of this work is, given
One also needs to assume initialization from position with low initial loss.

---

sufficient iterations of GD. that the network will interpolate noisy training data while also achieving minimax optimal generalization error up to constants in the exponents. Xu & Gu (2023) extend this result to more general activation functions, including ReI.U, as well as relax the assumptions on the noise distribution to being centered with bounded logarithmic Sobolev constant, and finally also improve the convergence rate. George et al. (2023) also study ReLU as opposed to leaky ReLU networks but do so in the context of the hinge loss, for which, and unlike exponentially tailed losses, characterization of the implicit bias is not known. This work also establishes transitions on the margin of the clean data driving harmful, benign and no-overfitting training outcomes. Frei et al. (2023) use the aforementioned implicit bias of GD for linear classifiers and shallow leaky ReLU networks towards solutions that satisfy the KKT conditions of the margin maximization problem to establish settings where the satisfaction of said KKT conditions implies benign overfitting, Kornowski et al.. (202)) also use the implicit bias results for exponentially tailed losses to derive similar benign overfitting results for shallow ReLU networks. [Cao et al. (2022); Kou al. (2023) study benign overfitting in two-layer convolutional as opposed to feedforward neural networks: indeed, whereas in most prior works data is modeled as the sum of signal and noise component, in these two works the signal and noise components are assumed to lie in disjoint patches. The weight vector of each neuron applied to both patches separately and a non-linearity, such as ReLU, is applied to the resulting pre-activation. In this setting, the authors prove interpolation of the noisy training data and derive conditions on the clean margin under which the network benignly versus harmfully overfits. follow up work (Chen et al., (202)) considers the impact of Sharpness Aware Minimization (SAM) in the same setting. Finally, and assuming d = (2(n)). ). Xu et al. (2024) establish benign overfitting results for a data distribution which, instead of being linearly separable, is separated according to an XOR function.
We emphasize that the prior work on benign overfitting in the context of shallow neural networks requires the input data be approximately orthogonal. Under standard data models studied this equates to the requirement that the input dimension d versus the size of the training sample n satisfies d 2nn² log n)) or higher. Here we require only d = (2)). The weaker dimensionality requirement requires substantially different proof techniques. George et al. (2023) study setting most similar to the one studied here, however, the techniques are very different. In particular, the results presented in this other work are derived by carefully tracking neuron activation patterns. While in high dimensions this is feasible due the near orthogonality of the noise in low dimensions this far more challenging as noise vectors can be highly correlated leading to coupling effects.
Finally, we remark that our proof technique for the convergence of GD to global minimizer in the context of a shallow leaky ReLU network (Theorem is closely related to the proof techniques used by Brutzkus al. (2018). While this work does establish generalization bound, the bound assumes that population dataset is linearly separable rather than just the training dataset. Hence, it cannot be applied when the training dataset has label-flpping noise, which is the setting that we are interested in for benign overfitting.
Preliminaries
Let [n] = (1,,2..... n) denote the set of the first natural numbers. We remark that when using big-O notation we implicitly assume only positive constants. We use c, C1, C2,.. to denote absolute constants with respect to the input dimension d, the training sample size n, and the width of the network m. Note constants may change in value from line to line. Furthermore, when using big-O notation all variables aside from d, n,, and m considered constants. However, for clarity we will frequently make the constants concerning the confidence ó and failure probability e explicit. Moreover, for two functions f.g : NN + N, if we say f = O(g) implies property p. what we mean is there exists an N E N and a constant C' such that if fn) & Cg(n) for all n 2 N then property holds. Likewise, if we say f 2(g)) implies property p. what we mean is there exists an N N and a constant C' such that if f (m) 2 Cg(n) for all n 2 N then property holds. Finally, we use || to denote the l² norm of the vector argument or , + f² operator norm of the matrix argument.
2.1 Data model
We study data generated as per the following data model.
3

---

Definition 2.1. Suppose d,n, k E N. (0,1) and v E Sd- (X, ~ D(d,n,k,n.
then
1. X E Raxd is a random matrix whose rows, which we denote 24, satisfy 2; viyio+ v Mi, where n. ~ (Oa. ā (I==vv")) are mutually i...d.
2. y E {+ is random vector with entries yi that are mutually independent of one another as well as the noise vectors (ni))e(n) and are uniformly distributed over {+1). This vector holds the true labels of the training set.
3. Let B C [m] be any subset chosen independently of such that [B] = k. Then ÿ E {[11" is random vector whose entries satisfy ÿ, # ys for all E B and ÿs y: for all i B G. This vector holds the observed labels of the training set.
4. y is random variable representing a test label which is uniformly distributed over {
5. x Rd is random vector representing the input feature of test point and satisfies x = Viyu + -I- yn, where n ~ NN(ss, L vv")) is mutually independent of the random vectors (n.))e(m))
We refer to (X, () as the training data and (æ.1) v) as the test data. Furthermore, for typographical convenience we define y ① ÿ =: E (=1]".
To provide some interpretation to Definition 2.1 the training data consists of points of which have their observed label flipped relative to the true label. We refer to and n. as the signal and noise components of the i-th data point respectively: indeed, with > O then for E g y (a;, v) VT > O. The test data is drawn from the same distribution and assumed not to be corrupted. We say that the training data (X, g) is linearly separable if there exists w E Rd such that
(w xx) 1, for all i [ni]
For finite n, this condition is equivalent to the existence of a w with (e(w, æ.)) > 0 for all i E [n]. We denote the set of linearly separable datasets Xin = {=1]". For a linearly separable dataset (X, ÿ), the max-margin linear classifier is the unique solution to the optimization problem
arg min |o||| such that (w, mx) 2 for all i E [n].
wERd
Observe one may equivalently take a strictly convex objective || and the constraint set is a closed convex polyhedron that is non-empty iff the data is linearly separable. The max- max-margin linear classifier w* has corresponding geometric margin 2/ 2/|[=*||| When 2 and y >> 0, input feature matrices X from our data model almost surely have linearly independent rows æ; and thus (X, g) is almost surely linearly separable for any observed labels ý E {+1)".
2.2 Architecture and learning algorithm
We study shallow leaky ReLU networks with forward pass function f Rm2x x Rd R defined as
2m
J(W x) = Σ
x)),
where W E 2d are the parameters of the network, a - R is the leaky ReLU function, (0, 1] is referred to as the leaky parameter. We remark
defined as (xx) max(x, az), where that we only train the weights of the first layer and keep the output weights Although is not differentiable at 0, in the context of gradient descent we adopt a subgradient and let (()) = for z 2 and let (=) = a otherwise. The hinge loss IR + Rzo is defined as
each neuron fixed.
f(=) = max max 2).
Again, is not differentiable at zero; adopting a subgradient we define for any j E [2m]
Vw, (n.:(jf(WW = ( (-1)++2 (ww, ( x) < 1,
00
of x) 2 1.

---

The training loss L R 22mxd x Rnxd x R + R is defined as
L(W X, 9) (W,
(3)
Let W E 2mxd denote the model parameters at initialization. For each E N we define W
recursively as
W = ((-1) r/V w (. ;)))
where > is the step size. Let F()) S [n] denote the set of E [r]] such that ÿ: (WV()) mi) Then equivalently each neuron is updated according to the following rule: for E [2m]
f GD(W (t-1), == w (1 + +
Σ (EF(+-1)
0,0,0((W0) a.)).
(4)
For of reference we now provide the following definition of the learning algorithm described above.
Definition 2.2. Let AGD 1aad x {+1}" R 2m2 1m2xx return AGD(X, D, n, W =:
W. where the j-th row wy of W is defined as follows: let w be the j-th row of ( and generate the sequence (w))))es )220 using the recurrence relation wj GD(W(t-1), n) as defined in equation 4
1. for E [2m], lime-soo w/ does not exist then we say AGD undefined.
2. Otherwise we say Agn converges and wj = -lim- w
w for all t T, then say 3. If there exists a T E N such that for all e [2m] w (1) (T)
AGD converges in finite time.
We often find that all matrices in the set
(AGD X U. W Vj 1 s X}
agree on all relevant properties. In this case, we abuse notation and say that AGD (X, 9, W where W is generic element from this set.
Finally, in order derive results make the following assumptions concerning the step size and initialization of the network.
Assumption The step size ni satisfies 1) S (0) network at initialization satisfies || S /a/ (m min [|=,]]).
[< and for all j [2m] the
Under our data model the input data points have approximately unit norm; therefore these assumptions reduce to 7 < mm and 1 (0)
Cva
2.3
Approximate margin maximization
We now introduce the notion of approximate margin maximizing algorithm, which plays key role in deriving our results. Although the primary setting we consider in this work is the learning algorithm AGD (see Definition 2.2). derive benign overfitting guarantees more broadly for any learning algorithm which fits into this category. Recall Xin. denotes the set of linearly separable datasets (X,9) Boxd x {
Definition 2.3. Let f IRP - R denote predictor function with parameters. An algorithm
A: Baxd x R + IR approximately margin maximizing with factor M. 0 on I if for all
(X. () Xisn
j. 9). xx) 2 for all E [n]
(5)
and
|IA[X, 9) S M M|w"|| where w is the max-mi max-margin linear classifier of (X,9). 9). Moreover, if is an approximate margin maximizing algorithm define
(6)
A inf > 0: A is approximately margin maximizing with factor M).
(7)
5

---

In the above definition we take the standard Euclidean norm on RP. In particular if IR = 22mxd is space of matrices we take the Frobenius norm.
3 Main results
In order to prove benign overfitting it is necessary to show that the learning algorithm outputs a model that correctly classifies points in the training sample. The following theorem establishes this for AgD and bounds the margin maximizing factor |AGp|-
Theorem 3.1. Let f R x R" + be leaky ReLU network with forward pass as defined by equation 7 Suppose the step size 1) and initialization condition X satisfy Assumption [ Then for any
linearly separable data set (X, 9) AGD [X, y. A) converges after iterations, where
C1
T
na2m
Furthermore AGD is approximately margin maximizing on f (Definition 2.3 with
AAbl S aym
A proof of Theorem 3.1 can be found in Appendix D.1 Note also by Definition 2.3 that the solution W AGD (X, 9) for (X, ÿ) Min is global minimizer of the training loss defined in equation with L(W X, 7) = 0. Our approach to proving this result is reminiscent of the proof of convergence of the perceptron algorithm and therefore is also similar the techniques used by Brutzkus et al. (0018).
For training and test data as per Definition 2.1 we provide an upper bound the generalization error for approximately margin maximizing algorithms. For convenience we summarize our setting as follows.
Assumption 2. Setting for proving generalization results.
f 2aaxd x Rd IR is shallow leaky ReLU network as per equation 1
A: x (+1)" + Rmdx is a learning algorithm that returns the weights W E 2max of the first layer of f-
We let u E gd-1 and consider training data (X, () and test data (x. distributed accord- ing to (X, Ú. y. v) ~ D(d, n. 2,,), as per Definition 2.1
Under this setting we have the following generalization result for an approximately margin maximiz- ing algorithm A. Note this result requires y, and hence the signal noise ratio of the inputs, to be sufficiently large.
Theorem 3.2. Under the setting given Assumption let (0, 1) and suppose A approximately margin- maximiiing (Definition 2.3 If Ω (log 8 ). = 2 (n), k 0 14 ) and y Ω (1)
then there is a fixed positive constant C such that with probability at least 1 - over (X, X.9)
4(1+ A|2)) (-c-
d
P(yf(W,z) < X. S eex
proof of Theorem 3.2 is provided in Appendix D.2] To comment informally on the relationship between k and 7, we require 7 28k in order to guarantee that any network which achieves zero hinge loss does so by focusing on the signal component v rather than the noise components n; We use the projection of the model weights onto the signal subspace as a measure of the strength of the signal the model has learned and derive our generalization results based on this measure. In Section 4 we provide proof sketch of this framework in the simpler, linear model setting. Combining Theorems 3.1 and 3.2 we arrive the following benign overfitting result for shallow leaky ReLU networks trained with GD on hinge loss.
Corollary 3.2.1. Under the setting given in Assumption 2 let 8 E (0.1) and suppose A = AGD where y) X E Ry satisfy Assumption 7 If n (log 1), 2 (n), O(a")), and 7 = (+) then the following hold.

---

1. The algorithm AGD terminates almost surely after a finite number of updates. If W AGD(X.)) then L(W, X, 9) =0.
2. There is fixed positive constant C' such that, with probability least 1- 6 over the training data (X, 9),
P(yS(W, x) 000 x, x. S exp (-c- a²d
h
We remark that the upper bound is at most exp (-Cd/n) for different constant C' as we assume = (a)
If & is large enough, this bound is tight up to constants and factors of a in the exponent. This is given by the following theorem, proven Appendix [.2]
Theorem 3.3. Under the setting given in Assumption 2 let ō E (0, 1) and suppose A AGD where 7) x x>0 satisfy Assumption If = (k), d = 52 (m), and k = (loog + d), then there is fixed positive constant C such that with probability at least 1 over (X, y)
P(yS(W, , œ) 00 exp (-c- d odk
In addition to this benign overfitting result also provide the following non-benign overfitting result for AGD- Note that conversely this result requires 7, and hence the signal to noise ratio the inputs, to be sufficiently small.
Theorem 3.4. Under the setting given in Assumplion 2 let 5 E (0, and suppose A = =AGD. where 4,, x E R2o satisfy Assumption If' = 2(1), S2 (n + log b) and = O then the following hold.
1. The algorithm AGD terminates almost surely after finitely many updates. With W AGD(X, (). L(W, X, O.
2. With probability at least 8 over the training data (X, 9)
Ply/(W, x))
< X y 2 8
proof of Theorem 3.4 is provided in Appendix D33
Approximate margin maximization and generalization: insight from linear models
In this section we outline proofs for the analogues of Theorems 3.2 and 3.4 the context of linear models. The arguments are thematically similar and clearer to present. We provide complete proof's of benign and non-benign overfitting for linear models Appendix C
An important lemma is the following, which bounds the largest and n-th largest singular values (a1 and on respectively) of the noise matrix N:
Lemma 4.1. Ler N Raxd denote random matrix whose rows are drawn mutually i.i.d. from NOa. 1 (Is vo )) d f2 (n + log })) then there exists constants C₁ and C2 such that, with probability at least 8.
C S an (N) sai S C2.
We prove this lemma in Appendix using results from Vershynin 2018) and Rudelson Vershynin (2009). A consequence of this lemma is that with probability at least 8, the condition number of N restricted to span N can be bounded above independently all hyperparameters. For this reason, refer to the noise being well-conditioned.
Now
A(X, 9) be the linear classifier returned by the algorithm. Observe that we can decompose the weight vector into signal and noise component
a +
where z 1 v and a, R. Based on this decomposition the proof proceeds as follows.
7

---

1. Generalization bounds based on the SNR: For test data as per the data model given in Definition 2.1 we want bound the probability of misclassification: in particular, we want bound the probability that
x==
v + 1I-7(n, 0.
As the noise is normally distributed, X ~ N (V7ar, - ||| and the desired upper bound therefore follows from Hoeffding's 's inequality.
yd
P(X S 0) exp
2(1 - >) ||
Using Gaussian anti-concentration,, we also obtain a lower bound for the probability of misclassifica- tion:
dy
av
6d
7
d
P(y(w, x) 50 2 max
exp
2T - 7)
|||||
1 π
=
2. Upper bound the norm of the max-margin elassifier: In order to the approximate max- margin property we require an upper bound on |/wl|- As by definition || I || suffices to construct vector ú that interpolates the data and has small norm. Using that the noise matrix of the data is well-conditioned with high probability, we achieve this by strategically constructing the signal and noise components of w. This yields the bound
(V n
|w=|| <
|
s C min
where the arguments of the min function originate from small and large y regime respectively.
3. Lower bound the SNR using the approximate margin maximization property: Based on step I the key quantity interest from a generalization perspective is the ratio a ///||==|, which describes the signal to noise ratio (SNR) of the learned classifier. To lower bound this quantity bound 0g- In particular, ag is small, then the only way to attain zero loss on the clean data is for || to be large. However, under appropriate assumptions
first lower
d, n, and y this be shown to contradict the bound ||||| < [|||| S |A|l|/=]|, [|. and thus a, must be bounded from below. A lower bound a ||=|| then follows by again using | |
Hence obtain lower bound for the
SNR and establish benign overfitting.
Upper bound the SNR using the zero loss condition: For the generalization lower bound, we compute an upper bound for the ratio a,/ |=/||=]| rather than a lower bound. Since the model perfectly fits the training data with margin one,
< je (w, 2.) VT3,a, + / 70: (z, n2))
for all i E [n]. The above inequality implies that -1- (n,, 2) is at least v7a, for all corrupt points. Since the noise is well-conditioned, this gives a lower bound on ||>||| in terms of a, and hence upper bound on the SNR a. /l/. By the second generalization lower bound in step the generalization error bounded below at a similar exponential rate to the upper bound.
5. Upper bound the SNR using the zero loss condition and maximum margin property: To prove non-benign overfitting, we again compute an upper bound for the ratio a. a,/||=|| We return to the zero loss condition:
(ww 2.) = viBaa + -I- (0, m2))
for all i E [n). I is small and Vya.l is large, then | will be large, contradicting the approximate margin maximization. Hence the above inequality implies that /I -I-7ijh ( z) is large for all i [n]]. Since the noise is well-conditioned, this can only happen when |||||| large. This gives us lower bound on ||||| As before, we can also upper bound o,, by ||w/] giving us an upper bound on the SNR a./ /|/ By the first generalization lower bound in step the classifier generalizes poorly and exhibits non-benign overfitting.
8

---

4.1 From linear models to leaky ReLU networks
The proof of benign and non-benign overfitting in the linear case uses the tension between the two properties of approximate margin maximization: fitting both the clean and corrupt points with margin versus the bound on the norm. To extend this idea to a shallow leaky ReLU network as per equation we consider the same decomposition for each neuron j E [2mm],
3 = 02 + 2j.
where dj E and 2; 1. In the linear case b. can be interpreted as the activation of the linear classifier on to respectively: in terms of magnitude the signal activation is the same in either case and thus we measure the aligmment of the linear model with the signal using la,l. For Ieaky ReLU networks we define their activation te respectively and then define the alignment of the network as Amia = min A-1} Considering the alignment of the network with the noise, then if Z E R2mxd denotes matrix whose j-th row 2,, then we measure the alignment of the network using | As a result, analogous to / the key ratio from a generalization perspective in the context of a leaky ReLU network is Amin/ / [[. The proof Theorems 3.2 3.3 and then follow the same outline as Steps 1-3 above but with additional non-trivial technicalities.
A f(W, v) and A -f(W, -)).
Conclusion
In this work have proven conditions under which leaky ReLU networks trained binary classification tasks exhibit benign and non-henign overfitting. We have substantially relaxed the necessary assumptions
the input data compared with prior work; instead of requiring nearly orthogonal data with d = S2n22 log n) or higher, we only need d = (2(n). We achieve this by using the distribution of singular values of the noise rather than specific correlations between noise vectors. Our emphasis was on networks trained by gradient descent with the hinge loss, but we establish new framework that is general enough to accommodate any algorithm that is approximately margin maximizing.
There are few limitations of results which would be natural questions to address in future work. While we improve upon existing results in our dependence on the input dimension of the data, still require that the training dataset is linearly separable. This leaves open the question of whether an overparameterized network will perfectly fit the training data and generalize well for lower dimensional data, satisfy similar margin maximization condition. We also focus mainly two-layer networks with fixed outer layer weights trained with the hinge loss. It would be interesting investigate whether analogous results hold for deeper architectures different loss functions and data models.
Acknowledgments
This material is based upon work supported by the National Science Foundation under Grant No. and by the Alfred P. Sloan Foundation under grant G-2021-16778, while the authors EG and DN were in residence at the Simons Laufer Mathematical Sciences Institute (formerly MSRI) in Berkeley. California, during the Fall 2023 semester. EG and DN were also partially supported by NSF DMS 2011 140. EG was also supported by NSF Graduate Research Fellowship under grant DGE 2034835. GM and KK were partly supported by NSF CAREER DMS 21 2145630 and DFG SPP 2298 Theoretical Foundations of Deep Learning grant 464109215 GM was also partly supported by NSF grant CCF 2212520, ERC Starting Grant 757983 (DLT), and BMBF in DAAD project 5761681 (SECAI).

---

References
Ben Adlam and Jeffrey Pennington. The neural tangent kernel in high dimensions: Triple descent and multi-scale theory of generalization. In Hal Daumé IIII and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 74-84, PMLR, 2020. URL httptt//rrroceediingg mlr wwwpppressvviii v119/ amlam20a.. htm
Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):3003333007 2020. URL
https://www pnas. org/ doi/ aaab//abb/0//0 10. 1073 pnas/ 1907378117
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 541-549. PMLR, 2018. JRLptttp://prroeeainn
mlr prress/vv00/elliin11.. html
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proceedings of the National Acudemy of Sciences, 116(32)158899-1554 2019. URL //doi. org/ 10. 10733/173ppsss. 190307011
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns over- parameterized networks that provably generalize on linearly separable data. In International Conference on Learning Representations, 2018. URLhtttps. htttps://openreviee nwt.:/mmmfmm
rJ33wwxRb
Yuan Cao, Quanquan Gu, and Mikhail Belkin. Risk bounds for wer-parameterized maximum margin classification on sub-gause gabssiasniann mixtures. M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), ), Advances in Neural Information Processing Systems, volume 34. pp. 8407-8418, Curran Associates, Inc.. 2021. URL httpps: neurips...p..p...p cc/ paper_ f
pdf
Yuan Cao, Zixiang Chen, Misha Belkin, and Quanquan Gu. Benign overfitting in two-layer convolu- tional neural networks. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 25237-25250. Cur- ran Associates, Inc., 2022. http.ttttt::///rceeeeeee neur 2002:/7hh22222322227777777772822
httpppperrflleppppepeeeeee Conperr-oooffeenceeeeee pdf
Niladri S. Chatterji and Philip M. Long. Finite-sample analysis of interpolating linear classifiers in the overparameterrized regime. Journal of Machine Learning Research, 22(129): 2021. URL
http://jmlr wttgppppes///2/ wtt//////022220 974 html
Niladri S. Chatterji and Philip M. Long. Foolish crowds support benign overfitting. Journal of Machine Learning Research, 23(125):1-12, 2022. URL http:://jmlr.... wwtp:ttpr/ppppp/eeee.ae.
21 1111.199.0 html
Zixiang Chen, Junkai Zhang, Yiwen Kou, Xiangning Chen, Cho-Jui Hsich, and Quanquan Gu. Why does sharpness-aware minimization generalize better than SGD? In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL htttps://ppenreeieee wwt.iiiwwwe.eeeeeeee net.forumfiftt 3WAnGWLpSQ
Spencer Frei, Niladri S Chatterji, and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 2668-2703. PMLR, 2022. URL https:// proceedings mlr. ppress/v18//fre.l/// html
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 Gergely Neu and Lorenzo Rosasco (eds.). The Thirty Sixth Annual Conference Learning Theory, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pp. 3173-3228. PMLR, 2023.
mlr. ppress/v195/freii/ html
10

---

Erin George, Michael Murray, William Swartworth, and Deanna Needell. Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign? In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 35139-35188 Curran Associates, Inc., 2023. URL https:://prrceedddggg newrsdd newrips.e.... cc wwwppppppp.ppeppppppppccccpeeeep 66776659802288044444805555553333 Paper Soaper--oofeeence.. pd
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949-986 2022.
URL https://doi. 1ttp///1..11121-AA55001 1214/21-A02213
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 17176-17186. Curran Associates, Inc., 2020. URL httpp:: CT664222884860771166666666600000
wwwppperpppppppcc.p files/ (ttpppperffllepppppr////0//000/0 /app://00//o///1l///////// pdf
Frederic Koehler, Lijia Zhou, Danica J. Sutherland, and Nathan Srebro. Uniform convergence of interpolators: Gaussian width, norm bounds and benign overfitting In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL http:///pppeeeeeeeeeetetttrrrrrr
Guy Kornwskii, Gilad Yehudai, and Ohad Shamir. From tempered to benign overfitting in ReLU neural networks. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
URL htt.ttts://pperreiiieeee htt.://w....eeeommmmmooo/ouuuuu
Yiwen Kou, Zixiang Chen, Yuanzhou Chen, and Quanquan Gu. Benign overfitting in two-layer ReLU convolutional neural networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning. volume 202 of Proceedings of Machine Learning Research, pp. 17615-17659. PMLR, 2023. URL BoLLhtttss:/procceddinn httppp/oo..o.aaaooooooooooooo//.
mlr. presss/202/kou22a...ss.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernl regresion can gen- eralize. The Annals of Statistics, 48(3):1329 1347, 2020. URL htttp:::/dii.rrg////
regression
19 AOS1849
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai On the multiple descent of minimum norm norm interpolants and restricted lower isometry of kernels. In Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learming Research, pp. 2683 -611- PMLR, 2020. WtRlhhtttss//ppoeeeee press/v125// 11m5//20...2..... html
.mlr
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2020. URL httpps://oppeereeiiee www.forrmmiddSJeelggp..
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022. URL htttps://onllnellibreeee halliibbrrrr.wieeeyy..........ee wiley. wwt. htc///oi//aaaa abs// 10. 10..1002/ccm cpa 22008
Andrea Montanari, Feng Ruan, Basil Saeed, and Youngtak Sohn. Universality of max max-margin classifiers. arXiv preprint arXiv:2310.00176, 2023a.
Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max max-margin linear classifiers: Benign overfitting and high- dine-niienii asymptotics in the overparametrized regime. arXiv preprint arXiv:1911.01544. 2023b.
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpo- lation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 1(1): 67-83, 2020. URL U //i.i org/ 1109/ 1099/SAATT 2020 2984716
11

---

Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparameterrized regimes: Does the loss function matter? J. Mach. Learn. Res., 22(1), 2021. URL htRt:tt::///mlr http://iw..rrpppppp///////////// 2000320060...... html
George Pólya. Remarks on computing the probability integral in one and two dimensions. In Proceedings of the Berkeley Symposium on Mathematical Statistics and Probability, number 1, pp. 63. University of California Press Berkeley, 1949.
Mark Rudelson and Roman Vershynin. Smallest singular value of random rectangular matrix. Communications on Pure and Applied Mathematics, 62(12):1707-1739, 2009. URL https //doi.org// 1002/ cp2p/
Ohad Shamir. The implicit bias of benign overfitting. In Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings mll
of Machine Learning Research, pp. 448 478. PMLR, 2022. URL URL press/v178/ wwtss//v////////// http/rhaaaaaaaaaaaa html
Roman Vershynin. High- Dinie--Dimenionall Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
URL https: org/10. 1117/11711118211111000
Guillaume Wang, Konstantin Donhauser, and Fanny Yang. Tight bounds for minimum formr interpolation of noisy data. In International Conference on Artificial Intelligence and Statisties, mlr. wwwpppresssssee. https//vv11/waaggg20 html
2021a. URL.httts://prrceeddnn
Ke Wang. Vidya Muthukumar, and Christos Thrampoulidis. Benign overfitting in multiclass classifi- cation: All roads lead to interpolation. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 24164 24179. Curran Associates, Inc., 2021b. URL https::sp: /ttp:oees///poooediigg// neurips. cc/ sopperrpdf..
Denny Wu and Xu. On the optimal weighted l regularization in overparameterized linear re- gression. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 101 10112-10123, Curran Associates, Inc., 2020. URL https://prooeeeddnng www.eeedddiiinnnnnnieeeeeeeeeeee httpppcccppppppee files wwteerfflleepppppee pttpae/s//ppper//////1aaaee 7256222881111111222ocaa2222aa000
.df
Xingyu Xu and Yuantao Gu. Benign overfitting of non-smooth neural networks beyond lazy training. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent (eds.), Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 11094-11117. PMLR, 2023. URL https:://p/ooooo https://prooceednngs mlr. wttpppesssv//xx22222 html
Zhiwei Xu, Yutong Wang, Spencer Frei, Gal Vardi, and Wei Hu. Benign overfitting and grokking in ReLU networks for XOR cluster data, In The Twelfth International Conference on Learning Representations, 2024. http: wttpriiwwweeettteeee
?id PidiidgggBBBFWyy
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017. URL https:://pperrevier www.:eeee/otnniiemmm .ett/foorumidddyyyddBBxs
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Benign overfitting of constant-stepsize SGD for linear regression. In Mikhail Belkin and Samory Kpotufe (eds.), Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of
Machine Learning Research, pp. 4633-4635. PMLR, 2021. URW.https://///// UtL/httss:/pprceeeeeee stttps://prooeeeingg. mlr fress/v14//zou11 html
12

---

Appendix A Preliminaries on random vectors
Recall that the sub-exponential norm of a random variable X is defined
X b1 := inf (1>> 0: E[exp([XX//t) s 2]
(see Vershynin 2018
Definition 2.7.5) and that the sub-Gaussian norm is defined as
| == inf (1 Ejexp(X²/()) 2).
random variable Sab-Gaussian and only if X²2 is sub-exponential. Furthermore, ||
||| Uia"
Lemma A.I. ~
NV d ~ (La )) and suppose that Z E Rxxd Then with probability
least 6,
Zn|l - C|
log
Proof. Let P Ia vv- be the orthogonal projection onto span(()))* that Zn is identi- cally distributed to d 1/2 Z.'', where n' has distribution (0s,,, Ia). Following Vershynin 2018 Theorem 6.3.2),
Zn|l - ||d_ 1/2 z
= -111ad1/22
1/2 1/111/2222'
||d 1/2 2
S SCIId-1/2221
- <Cd'1/31 / P||
C/2 |
< Cd-1/2
where we used that P an orthogonal projection in the fourth line and that the operator norm by bounded above by the Frobenius norm in the fifth line. As result the sub-Gaussian norm of Zn bounded
Zn
$ Zn||
||d
1/2 ZP
+ 1
< Cd Cd 1/2 /||F + [(2](F)
Cd 1/
where the last line follows from the calculation
LZ = |P 2 ||
PPZ 1F
< |P|||Z ||
1TT |F
Z ||.
This implies a tail bound (see Vershynin 2018
Proposition 2.5.2)
dt
P(1 Zn 2 t) < 2xxp
for all 2 0.
Setting & C|| Z PP
log 2 the result follows.
Lemma A.2. Let NNa, d (Ia vvT)) and suppose z E span((u))+ There exists C such that with probability at least 1 - 5
(n, 2)1 S C|
log g
Furthermore, there exists such that with probability at least 1
c||=||
(nn, x)1 2
/d
13

---

Proof. Let X = (nz, z). Then X is Gaussian with variance
E[x E|z Inznnn z]
nnn
x E'(nnn" 1
2 (Id vv )z
=d
121??
Note the third line above follows from the fact that span( Therefore by Hoeffding's inequality, for all /. 0
dt
(( 2)1 2 - 2 exxp
C||2||2
Setting / = 21 log J. we obtain
P(Kn,, z) 21) S 6,
which establishes the first part the result.
Since d'/2 =|| standard Gaussian, there exists constant such that
P(Id4/31211 x 2 c) 2
Rearranging, we obtain
P(Kn,, 2) cd cd 1/21|=11) S
This establishes the second part of the result.
Appendix Upper bounding the norm of the max-margin classifier of the data
Here we establish key properties concerning the data model given in Definition 2. our main goal being to establish bounds the norm of the max-margin classifier. To this end first identify certain useful facts about rectangular Gaussian matrices. In what follows we index the singular values of any given matrix in decreasing order as o, (A) Z (2 .... Furthermore, we denote the i-th-row of a matrix A as a;,
Lemma B.1. Let G E R be a Gaussian matrix whose entries are mutually i.i.d. with distribution (0. If d Ω (n + log }). then with probability at least 1 - 8 the following inequalities simultaneously true.
1. (G) s C(vd Vn).
2. on (G) 2 c(dd-mm) vn).
Proof. We proceed by upper bounding the probability that each individual inequality does not hold.
To derive an upper bound on 01 (G) we use the following fact (see Vershynin 2018 Theorem 4.4.5). For any 0,
Pl (G) Ci(++++ va+c)) s 2exx((-
With v Vd d log 4 then
à
(P(r)(G) 2 2CI(V Vd)) < 2exp(-l)
8
2
14

---

2. To derive lower bound on on (G) we use the following fact (see Rudelson & Vershynin 2009 Theorem 1.1). There exist constants C₁, C2 such that, for any e 0,
P(on(G) S <(vd vn 1)) s (Cie) + e
Let o. and let d 2n + (2 dz) log t.4 Then
(A) S <(vdd vn) exp(-d/2) exp(-
8
6
+
8
2
Hence both bounds hold simultaneously with probability at least 1 - 6.
The next lemma formulates lower and upper bounds on the smallest and largest singular values of noise matrix under our data model.
Lemma 4.1. Let N Ra denote a random matrix whose rows are drawn mutually i.i.d. from NOa, (La vo )). If d = 52 (n + log }), then there exists constants Ci and C2 such that, with probability at least 8,
(ison(N) (o) S C2.
Proof. Let HI span((v))+ = Rd-1 Let N' H R2 be random matrix whose rows drawn mutually i..dd from (O,,, In). Since d Ω (n + log }). with probability at least 1 6, we have
dvd- vn) s o (N') S ( s c(Va+ VR).
We denote the above event by w. Let J : H - IRd be the inclusion map and let P= La any random vector n with distribution A(0O,, Ix). Jn is a Gaussian random vector with covariance matrix JJ P. Therefore, d'1 N'' is random matrix whose rows are drawn mutually i..d. from ((a, PP) That is, d'1//2 N'J J is identically distributed to N. For the lower bound on 4n
vo"" For
J
the n-th largest singular value, d 2
e then conditional on w we have
T 2d2 = d 1/2 0 (JNT)
2 d //2 1/2 1/20 min (J (J)omin (NT)
= d 1/2 min (N'T)
d 11120nn (NV)
m d
IV
2
Note here we define mmin be the smallest singular value of matrix. In the first line used J ' a linear map R + Rd and d 2 n, and in the third line we used the fact that is an inclusion map. For the upper bound on the largest singular value, if d > C.. then conditional on we have
a. (22
< d (
d 1/ (N')
4C + /
$ 2C
15

---

Note here that again we used the fact that J is an inclusion map in the first line, Therefore, if (n log ))
P C S ( $ 22) 2 P(w)
2 1
L
The following lemma useful for constructing vectors in the noise subspace with properties suitable for bounding the norm of the max-mane max-margin solution. We remark that the same approach could be used the setting where the noise and signal are not orthogonal by considering the pseudo-inverse ([N, yf instead of N
Lemma B.2. Ler I S [n]] be an arbitrary subset such that [ = L. In the context of the data model given Definition 2.1 assume == Ω (n+ log }) Then there exists E R2d such that with probability at least 8 the following hold simultaneously.
1. (n 2) = 1 for all I.
2. D. (n;,,2 z) = O for all i I.
3. # L..
4. C1 S ||||| S Cz.
Proof. Recall that N E Raxd is a random matrix whose rows are selected i.i.d. from M0s,, d (Ia ve )). By Lemma 4.1 with probability at least 8 we have
es (N) S (N.
Conditioning this event, will construct vector which satisfies the desired properties. Let w E R" satisfy w; = û if E I and w; = otherwiis. Let Now, where N (NN'" is the right pseudo-inverse of N. Then Nz 0. This establishes properties and 2. Since N is in the span
In particular, for i I, 9s (n. z) y,w; =
and for i I, (n; 2) of the set {n, he(mj it is orthogonal to v. This establishes property 3. Finally, we can bound
| = || |
IN [||
|
nn (N)
|z2||
/i
and
| || w/l
a (N
||w|
(N)
|wll
C
Vi
C
which establishes property
16

---

With Lemma B.2 in place we are now able to appropriately bound the max mar-mn norm.
Lemma B.3. In the context of the data model given in Definition 2.1 ler w² denote the max-mane max-margin classifier of the training data (X, ÿ), which exists almost surely. If d = Q2 (n + log }) then with probability at least
1 C
k
7
1-7
where C' > 0 is a constant.
Proof. Under the assumptions stated, the conditions of Lemma B.2 hold with probability at least 1 - 8. Conditioning this let
2
V
v
where z is the vector constructed in Lemma
B.2 with I = B. For any E [n]] we therefore have
de (a w)
35 + 2ÿj, (n,, 2)-
As result, for i
v. (a,, w) (1 2)
while for E B
1i (a,, w) 1 + 2íj (ne 2) As result de (z,, w) for all E [n]. Furthermore, observe
un || 1- | 2
SC 1 k
1-7)
for universal constant C. To conclude observe ||"|| I [ by definition of being max- max-mann margin.
Lemma B. constructs classifier with margin using appropriate linear combination of the signal vector and a vector in the noise subspace which classifies all noise components belonging to bad points correctly. This bound is useful for the benign overfitting setting in which y is not too small. However, for small 7, as is the case in the non-benign overfitting setting, this bound behaves poorly the only way the construction can fit all the data points by making the coefficient in front of the component large. For the non-benign overfitting setting we therefore require a different approach and instead fit all data points based their noise components alone. In particular, the following bound behaves better than that given in Lemma B.3 when approaches O.
Lemma B.4. In the context of the data model given in Definition 2.1 let w= denote the max-mane margin classifier of the training data (X, ÿ), which exists almost surely. If d = Q (n + log 1)) then with probability least
||=||| S C 1
Proof. Applying Lemma B.2 with I = [n]] then with probability 1 - 5 there exists E Rd such that ||||| (VT)), 2) for all i [n]] and 1 v. Conditioning on this event, let
Then for all i [m].
(2,, w) D (n,, 2) 1.
Furthermore, there exists a constant > 0 such that
| < n
1-7
To conclude observe ||w"|] < |/w|] by definition of being margin.
17

---

Appendix C Linear models
C.1 Sufficient conditions for benign and harmful overfitting
We start by providing lemma which characterizes the generalization properties of linear classifiers. Lemma C.1. In the context of the data model given in Definition 2.7 consider the linear classifier
w = O₂U U + 2. where au E R and (z, O. If a. 2 0, then the generalization ervor can be
bounded as follows:
d 7 ?
a
P(y(wu, a)) 5) I exp
|| 112
and
P(y(w, x) 0) 2 max 2
dr
ag
exp
6d
a
2n [1 7) ||||| 4
1
2
Proof.
Recall from Definition 2.1
that a test pair (az y) satisfies
x y(vrv= + v1 7m))
where n NoOa,, d (La vo a random vector. Let X = y(u, x), so
X = (a, + z, T + -
Vaa / - (n2, 2).
Then X a Gaussian random variable with expectation
E = viae 11,, =>}
and variance
Var(X) = (1 7) Var((n x))
(1 3) "nn"" 2]
IJ (Id vo0 )z
d
1 7 z²= z
d
(1 - 7) |z
d
By Hoeffding's inequality, for all t 2 0,
1dd
P(X < V5a - t) < exp
2(1 1|
Setting t = Vaa,, we obtain
P(X < 0) S exp
2(1 - >||
which establishes the upper bound on the generalization error. To prove the lower bound, we integrate a standard Gaussian pdf:
V7ax
7d
P(( 50)= =P
||=||
1
1/
2m
J-V -
(v/
1
7d
ag
>
/ 2π
V
11- 7
18

---

Another bound can be obtained using the following inequality Polya 1949 (1.5)):
[
12
2-- S V1
V 2T
J
We proceed
11/2
P(X
& 0)
2
2
1//2
2
2
1
27da
2
exp
T(1 7) 1|
2yda
2
2
1
2
exp
1T(1 7)
1
27da
4
exp
TT(
1)
The following result establishes benign and non-benign overfitting for linear models and data as per Definition 2.1 with a phase transition between these outcomes depending on the signal noise parameter
Theorem C.2. In the context of the data model described in Section 2 let w" be a max-margin linear classifier of the training data, Let A: Rnd [#1} + IR be learning algorithm which is approximately margin-maximizing Definition 2.3 For 8 E (0, 1]. let d = Q (n +log })). Then with probability least 1 - 8 over the randomness of the training data (X ÿ). the following hold with denoting the generalization error of A(X, 9).
(A) If 7 = (((AA(n)))) and k = n() then exp (-Cidk- S c exp (-Oadh: 1[A2ak-1|A100 2) for fixed positive constants C1 and Cz.
S
CCd for a fixed positive constant C. (B) y 0(141 1d- then 2 2
Proof. For training data (X, 9) let w A(x, 9) be the learned linear classifier. First, recall 2; = Vy..0 + -1-111100 yn, for all i E [n]. |b|| = 1. and observe that we can decompose the vector w as w a + z, where a I. and 1 v. As result, for each i [n]]
(x, w) V vI (n, z).
(8)
First we establish (A). As d = Ω (n + log }), Lemmas 4.1 and B.3 show that with probability at least 1 - 8 2. || || ||5
< C and ||='|| C / + 1-y- Here Ng and Ng denote the matrices formed by taking only the rows of N which satisfy
A
and 8 = -1, respectively, We denote this event and condition it in all that follows for the proof of (A). As A is approximately max margin then given equation we have for all illic E
Vya, V1 YŪx Tū:( 2).
Suppose that /7a, < 1. Then the above inequality implies 7i 2) 2 for all i E g. Squaring and then summing this expression over all E G it follows that
k
S (1 ?) Σ
Kn,, 2)12
iEG
< (1 - (1- No 2|
< (1 7) Ng. 1|
19

---

Since is approximately margin- margin-maximiin maximizing,
n k
(1-7)C1|=]1
4
< - 21
(1 200
- k
s C| >)
1-
CLAP2 CLAISK
?
which further implies CLA22 + C|A for some other constant C. For this inequality to hold,
either C/AA/2 2 2 or C|A 2 R
With s 4ctAp and y Z 1 neither of these can be true and
2'
therefore we conclude that via 2
Then
a
2
4 1|
4 || w 1|
4 [ 12
C
+ d
7
C 1 1-Y
222
k
for positive constant C. Letting (æ, y) denote a test point pair, then by Lemma C. for a different constant C
follows that
d γ ag
P(y(w, 2) <0 w) S exp
21 - Y ||
Cd
S exp
[A|21
Hence the generalization error is at most when w occurs, which happens with probability at least 1 - 8. This establishes the upper bound of (A).
For the lower bound of (A), since w is a linear classifier,
7 1- Y
(ni, 2) 2 v1 (1 + a 2 au
for all i E B, from which we conclude (mz; 2)1 2 au 77 This implies
K- ||NB2|| 2 av
1-7
Along with || S || S C||=|| we conclude
Og
by
|
2 C
With this bound we then bound
1-?
z
<
C
V
ky
20

---

By Lemma C.1
we then can bound
1
(-
6d ?
a
P(y x)) 50
exp
(- π
4
- ? ||
Cd
2 exp
k
for a new constant C, provided a, is positive. the last line we can bound & below as d 2 n and
k = (n). If ag is negative then the generalization error is at least 1. which is still bounded below by exp(-Cd/k).
We now turn our attention to (B). As d = 12(n + log H.. from Lemmas 4.1 and B.4 with probability
least 8 holds that N S C' and ||w*|| S Cvū on in all that follows for the proof of (B). In particular,
We denote this event w' and condition
vI-7
a ||=||
||/l
W L 1 w 1=
2 C|AA|²n
7
For all i E [n].
1 V1Baa - /1 (ni,
For this incquality to hold, either 1/aal 2 1/2 or vI - -ii x) 2 1/2 for all i E [n].
|VT0.l 2 1/2, then with S TCC1]]AP we have
a 2 20 2C1AR22
However, from equation 9 we have
CLA n
2C|A|33
1-7 2 d
which is a contradiction. Therefore, under the regime specified there exists C such that with Y Cl have vI (n;, 2) 2 1/2 for all E [n.] Rearranging, squaring and summing over all E [n]] yields
n
(n, 2) < || < C|
i=1
where the final inequality follows from conditioning on w. Then
tu
2 2
L w
|
C C|
< C|A22
where the constant C > 0 may vary between inequalities. Letting (æ, y) denote test point pair, by
Lemma C.I follows that
dy
ag
PP xx)
50
w)
2
2
2x - 7)
||
1
Cdyl
2
V
2
ACd
2
Hence the generalization error least 1
/
Ad when w' occurs, which happens with
probability least 1 - d. This establishes (B).
21

---

Appendix D
Leaky ReLU Networks
In this section we consider leaky ReLU network
R Rd
R with forward pass given by
2m
f(W, x) = (-1)o(((u) xi)),
1=1
where (2)) max (2z, 2) for some E (0, For any such network, we may decompose the neuron weights w, into signal component and noise component,
= 0g + Zj.
where E IR and 2; E Rd satisfies 2; 1. V. The ratio a,/ ||z||| therefore grows with the alignment of w, with the signal and shrinks if w, instead aligns more with the noise. Collecting the noise components of the weight vectors, let Z (22m) xd be the matrix whose j-th is zj. In order to track the alignment of the network as whole with the signal versus noise subspaces we introduce the following quantities. Let
2m
A = f)W,u)= = Σ
(11ol(a)),
==1
2m
A-1 = f(W, - (-1 ((-a))
j=1
be referred the positive and negative signal activation of the network respectively. Moreover, define
Amia (i, A-1)
as the worst-case signal activation the network, and
2m
Alin
Σ (-11/
j=1
as the linearized network activation. To measure the amount of noise the network learns we define
2m
Σ (-1222
Plin
1=1
D.1 Training dynamics
Theorem 3.1. Let I X R
be leaky ReLU network with forward pass as defined by equation! [ Suppose the step size and initialization condition X satisfy Assumption 7 Then for any linearly separable data set (X,, ÿ) AGD (X,) D. n. converges after iterations, where
Cl
T
na2m
Furthermore AGD approximately margin maximizing on f (Definition 2.3 with
AGGl S aym m
Proof. Our approach is to adapt classical technique used for the proof of convergence of the Perceptron algorithm for linearly separable data. This also the approach adopted by Brutzkus et al. 2018). The key idea of the proof is to bound in terms of the number of updates both the norm of the learned vector as well as alignment with any linear separator of the data. From the Cauchy-Schwarz inequality these bounds cannot cross, and this in turn bounds the number of updates that can occur. Analogously, we track the alignment of (+) with the max-man max-margin classifier along with the Frobenius norm of the ((1), To this end denote
G(t)
w (1)
22

---

and
2mm
F(I)
(-1)
(1) w=),
where w" a max-margin linear classifier of the dataset. Recall that F( {a E [n]
(.f( x.) < 1 denotes the number of active data points at training step t. We also define to be the number of data point updates between iterations 0 and t. First, by Cauchy-Schward
U(t) = E |F(1]
(w0 xxi S || 100"
||as|||
for all E [n]. Therefore,
|ww1 minsefn] <
By Assumption
[ for all j [2m].
w
|
(0)
||
<
(10)
m
mm]
am
For all t 2 0, the update rule of GD implies
2m
G(t
w
112
j=1
2m
w + 7 111
(1)
Σ
d((w))) (t) <;)),;
j=1
(EF(())
2m
2m
2m
|100 112 + 2m
(-1))((1w)) (0 x. (w)) (9) 2s) + + Σ
Σ
ō((wo) (Brao,, Bc00s)
1=1
1= (EFR()
5=1
i,EE
2m
2m
<
Σ 3=1
(1)
112 + 21
Σ
(1))) (-1))((ww)) (=)))(()) 2s)) + 2mn p
max |0:11
sc|n
1=1 iEFF())
Observe that for all 2 2E RR (8) = o())2, so can rewrite the second term of the above expression as
2n
Σ (11))((1))) m. a.))d ( m.)
2n
Σ Σ
(-1)a((w))) .m:))a
iE
5=1 iEF())
Σ (W(()) ,x;)
= 2n
iEF(
< 2m Σ 1
(EF((
2ny [()
where the inequality in the second-to-last line follows as we are summing over F(t), which by definition consists of the E [n] such that (W ax)) < 1. As result we obtain
2m
G(I + 1) <
(1
27 | + 2mm (=())) 2
max ||
(E(m)
G(t) + 2n| [F)) + 2
max ||; ||
sE[n]
< G(t) 4n
where the last line follows since
[2 S [F()) m max ||x: 1?
mn maxie(ml
23

---

By equation 10. the initialization satisfies
2m G(O)
(0)
/=1
|w0" 1|
a m2
j=1
2 120 11?
a²m
So by induction, for all
2 21'""1
2 2/2²' 11?
G(t)
S a2m
+ 3n
[+()|
+ (t).
(11)
a2m
8=0
Next we find a bound for F(t). For all
2 0 then by definition the GD update
2m
F(++
1) (w)
(t-1) w00)
f=1
2m
2m
1)d (w
w²)
Σ 6(11,) (6)
((:,, ,.)))i a.)-
iEFiO
Since ÿr (w" 23,) for all i E [m]. the above expression is bounded below by
2m
2m
2m
1) (20
w > +
Σ
H(wu)) 2,)))0= = F(t) + n Σ Σ
.xx))
5=1 SE
iEFO
2m
2 F(t) + 7
Σ a
j=1 iEF(
2 F(t) + 2mma ((1)
Hence unrolling the update for GD for all / 2 0 it follows that
F(t 1) 2 F(0) + 21yma
[(()
At initialization, by equation 10 then
2m
F(0) = _
(-1) 1) (w w00)
j=1
(0)
||
2m
|R0011 1|
C077
j=1
2 3||
1|2
a
Therefore by induction, for all t 2 0 we have
N 2 10' 12
F(t)
+ 2mma
[E(0
a
2 1ww1
2mmau(t).
24

---

Combining our bounds for F(t) and G(t), we obtain
2 1n I + 21mau((t) F(t)
2m
1 (20 (8)
w")
j=1
2m
< ||00|1
|10 (t)
|
j=1
1/2
2m
S ||2*|| ||
2m
| 10
j=1
||w0||
(2mG(t))
[4|/2"112
1/2
||0||
+ (m)nU(t)
a²
This implies that either
2| w 1
+ 21mmaU(t) S <0
(12)
or
2| 1wwl1
2 21maa((1)
[411001 1
S 1| ||=2
a² + 6m)
(13)
a
If 12 holds, then
Utt) S | 1I?
na2m
If 13 holds, then rearranging yields
Ar2² a UT() < 14|| 11ppU()) (1)
U(t) < 7|| ||2
2maam
Therefore, in both cases there exists a constant such that
C'Il 1|2 n
U(t) <
(14)
This holds for all t N and therefore
C' C'Il0" 1|
|200
n02m co.
This implies that there exists E N such that [f(+)| = 0. Let T E N be the minimal iteration such
that [FF(T] = O. Then for all E [m] (T))), xx;) 2 1. So the network achieves zero loss and also has zero gradient iteration T', In particular,
T-1 T
ClIw*1
T=
na2m
t=
1=0
To bound AAGl we combine equations
14
and obtain
2/u001 1|2
G(T)
+ (t)
am
2 2|0011
+ 11|20*122
am
ma2m
C I ||2
a2m
25

---

As result for all linearly separable datasets (x, ())
W
F
|'
aym
and therefore
C
AGDl
aym
as claimed.
The training dynamics of gradient descent also give us the following result relating the linearization of the noise component of the network to the noise component of the network itself.
Lemma D.1. Let X, ā > O. Suppose that d 2 Ω (n + log z). In the context of training data (X, 9) sampled under the data model given in Definition 2.1 ler W AGD (X. ÿ. 17 2). Then with probability at least - 8 over the randomness of [X
C am
2\v 2m
Z
2m1² 2 x
(1 + 2mx)²
Proof. At each iteration of gradient descent,
/
(1+1) = -//0+
+ +n(-1)² Σ
b 0,
i=1
where
0 (f x.)) 2 1
6/
1
if (.f( x,) < 1 and (wff) x;) 2 0.
otherwise.
Let T be the iteration at which gradient descent terminates. Then for each j E [2m].
T-1
w w (T)
2
(0) +
n
1)²
g.a.
Then the noise component of w, is given by
Zj w - (w., w)y
T-1
1 (0) (w0)
(0) v) U 7 13
Bi (x; -(x;, 0)
(0)
3 (10)
(0) (0) ..) n 11
i
genz
-==
Define
= w j
(0)
+ (w))
(0)
and let
2m
2
Σ (1102
/=1
Then for all j E [2m],
(1 || - 11= S || - 12
= m|0 (w (0)
< w (0) 12
s X².
26

---

Furthermore, if | $ ||ر then the above implies || || - ||z||| + X while if ||,|||| 2 |2 then
this inquuality holds trivially. As a result,
|| 112 - ||
1 || + | I)) (I|=]] || 1>
< ||| + || ||| - -1,z1|
S (2 + ()()
|z 2
|| then the above implies
|| z || x(21|z)1 + 2), if ||ا S || this
inequality is trivially true. As result,
2m
2m
(||2|1| 1 X(2122]11 + X))
==1
21n
2m
| 12 -2 Σ
|| 2mm2
j=1
j=1
1/2
2th
2m
| 1| - 2m
Σ
||=ا|| 11?
-2mA2
j=1
2Xv
2m
2md2
(15)
where the third line is an application of Kauchy-Schwarc Moreover,
2m (-1)(E2 - 23))
|| 8tin
Zlin
2m
<
|| 2,11
/=1
2m
j=1
< 2m2
80
1in 2 || |iil|| || - 2md.
(16)
Let N' E [gxx to be the matrix whose i-th column is Son, equivalently N' = Ndiag (ū). Then
21 3>=n(-1)N'e
where Cj E R" is given by
(c)) = Σ D t=0
Due to symmetry of the noise distribution then the columns of N' are i.i.d. with distribution
N( "Ia v)""). Therefore by Lemma 4.1 (and the assumptions = (n + log !)), with
probability at least - 8 over the randomness of the training data there exist positive constants C², such that C" S (Ni' I Tmax (N') < C. As result
C'nlles s || S Cnlleyll-
(17)
We claim that for any j.j E [2m] and i e [n]. (c,); 2 a(cy); Indeed, if (W.(( (0,)) 2 1, then b(0) 3j ij' 0. and if ū.f(W x;) < then both b5)) and bl are elements of {a, 1}. This in
((())
particular implies that
(c 2 a(c,,
27

---

Let us define
Clin
Cj+
Then
2m
Stin 1
1)
j=1
2m
7 I/'', Cj
j=1
I Cnn
Cn²² cial?
(18)
where we used that ||]]|| & C' in the third line. We also have
||ctn
ce,
cgt)
j=1y"
2m
2m
2
(c,cc))
j=1j==1
2m
2am
Σ
||c,112.
(19)
j=1
Finally combine our bounds for c, z, and 2:
2m
Z 1/ 2Av2m
Z F
2m 5 Σ
|| 11
j=1
2m
$ Cr²²
|c ||
j=1
C1
| 1|
|| 2
Z|z + 2m2)2
Here applied equations 15 in the first line, 117 in the second line, 19 in the third line. (8 the fourth line, and (16) in the fifth line. This establishes both the bounds claimed.
in
D.2 Benign overfitting
To establish benign overfitting in leaky ReLU networks, we first determine an upper bound on the generalization error of the model in terms of the signal-to-noise ratio of the network weights.
Lemma D.2. Let E (0. 1). Suppose that
Amin | F
(1 7) ) log 1
C2p
7d
Then for test data (x, y) as per Definition 2.1
Plyf(W, x)) < 0) Se
28

---

Proof. Recall that test point (x, y) satisfies
x - v(v + v1- 31-770 mm);
where n ~ (0s, (La - v) yf x) - 0, then
0 2 uf(Waa x))
x1))))((13..
20
(-1) (a) mm))
2
1 + v1 - 72,, m)))
j=1
2m
2m
(-1yyo(uv/aa)) Σ
v1 7 (z), n2)
2m
= A - Σ
v 7 (zj. m)]-
==1
When Amin 2 0, this implies that
2
2m Σ
742 S (11 (1-
(ス mil
/=1
2m
< 22m1 - 7)
Σ
(2,, 12)1
j=1
2m 7) Zn|l1
s 2m(1 - 7) 2 n2
where the second inequality is an application of Caachy-Schward So
7 |Zn] 2 N 2m (1 7)
P(yf(W, Φ) S P
By Lemma A.I the above probability is less than if
7 2m(1 -7) Amni C1|Z p log e'
or equivalently,
Amin | F
(1 - 7) log
1
C2p
7d
We will also need the number of positive labels to be (mildly) balanced with the number of negative labels.
Lemma D.3. Let 8 > 0 and suppose that f. Ω (log 1). Let C [m]] be an arbitrary subset such that [[] = l. Consider training data (X, y) as per the data model given Definition 2.1 Then with probability at least - 8.
i Elie S:y: 171 < 38 4
4
29

---

Proof. For i E Z let Y, be random variable taking the value 1 if = 1 and 0 if -1. Then the
Y are i.i.d Bernoulli random variables with P(Y; 1) Let
Y= Σ == s 1H
IE
so that B[Y] 2. By Chernoff's inequality, for all / E (0, 1),
(( Y
2 1 8
S 2e
Cuu
2
Setting & = 2. we see that $ S S Y < with probability at least
Cl
1 exx
2 8
when ( = Ω (log )
We are now able to prove our main benign overfitting result for leaky ReLU networks.
Theorem 3.2. Under the setting given Assumption 2 E (0, 1) and suppose approximately
margin-mant maximizing (Definition 2.3 If Q (log 1 d S2 (n), k O [+m|Ap=) and y (1)
then there is a fixed positive constant C such that with probability at least 1 - over (X, ..
P(yS(W, 50 0) S sexp (-c-
d
1(1 m|
Proof. Since d = ((n) Ω (n + log 2). by Lemma B.3 with probability at least 1 & 3 randomness of the data, the max-margin classifier w²* satisfies
over the
k
| '1 C
We denote this event by w1. For s {1, 1.1, let G. denote the of such that (V, s.
12 (3) and k On), then [ = Ω (log })) Under these assumptions, by Lemma D.3
|9.1 2 | 2 On
for both E (1.-11 -1] with probability least S. We denote this event by W2. For s E {1, 11,
let Ng. E gg xd be the matrix whose rows are indexed by G. and are given by the vectors n; for i G.. As d Ω (n) = 52 (n + log })) and the rows of Ng, are drawn mutually i.i.d. from df - )))), the following holds by Lemma 4.1 With probability at least 1 5 3 over the randomness of the training data, ||, C. for both s (1,-) We denote this event by wg- Let proof.
n O w3. By the union bound P(w) 2 1 - 8. We condition on w for the remainder of this
Since W = A(X, 9) and A is approximately margin maximizing,
||]| - [A| ||w")
1 s sIAl//
k
= +
(20)
7
30

---

Let s E {-1.1) be such that A, Amin. Since the network attains zero loss, for all E G..
S WW mi)
2m
1) ((0(((
(a V v1 ym.))
2m
1 + VT 72z n2,))
2m
2m
<
y ( (5ay)h) +
V1 - 7z); n.yl
j=1
/=1
vT
> j=1
(-1)s80(s0,, ss()s)) + /1 7 > |2 n2)l
2m
= V5A. + /1
1zj n:)l
j=1
2m
A + v ?
Kzzz n.)l.
j
Hence, we have either two cases separately.
774, 2 2 or / 1I Σ
1=1 Kz n2 2 3 for all i Gs. We consider these
2m
Amin 2 1.4 then
Amin
A
W I|F
2 2/7 W|
1
2 0
VTLAI / + 1-7
=C
A 1 + I-
kr
1
A + AA
Then by Lemma D.2 the network has generalization error less than when
1
(1 7 m log
2 C
AA| + 1A
V
by
d
or cquivalently
(1 7) 1
mk log 1 C
yd
d
A
This is satisfied for e = exp(-O k[+m for some different constant C' when y = = which true by assumption. So if Amim 2 2. then the network has generalization error less than whenever occurs, which happens with probability at least 1 6.
31

---

Now suppose that vT- 2m (zz, n.)l 2 for all i E Gg. Squaring both sides of the inequality and applying Cauchy-Schwarz we obtain
2
2m
1/4 s (1
(1-)) -7)
Σ |=1
(z
2m
- 2m - 7)
Σ
(z m2)l?
j=1
Summing over all i Gs, we obtain
[
2m
S 2m(1 7)
Σ
n.?1
iEG. j=1
2m
2m(1 -- 7) Σ
|1N 2,
j=1
Applying W2 and W3, we obtain the bound
2m
S Cm(1 - 7)
Ng. 2,11
j=1
2m
5Cm(1 - 7)
Σ
NNg. 1|,11
j=1
S C0m(1 - 7) Σ
|z 1|
j=1
= =Cm(1 - 7) 2
Cm - 7) W 1
Then applying 20
S Cm(1 7) W1
s Cm(l - A) (1
1-
S Cm|Ap (++
This implies that
Cm A
7
Cn
k 2 m A|2
Neither of these conditions can occur if y = Ω (t) and ks = 0 (14p)))
p. Thus, in all cases, the network has generalization enror less than C k(+mm|Ap5) when occurs, which happens with probability at least 8.
We are also able to show the lower bound for the generalization error stated in the main text.
Theorem 3.3. Under the setting given in Assumption 2 let ō (0, 1) and suppose A = Acn where
7. A E Ry satisfy Assumption / Ifn. = Ω (k), d = 52 (m), and l: = 2llog + 2), then there is fixed positive constant C such that with probability at least 1 over (X, 4)
Plyf(W, x) 50 4 2 exp (-c d
ak
32

---

Proof. We proceed along the lines of Theorem 3.2 For s (1, let B, denote the set of i E B
such that (v, xz)) = 8. Note [3] = ? (log })- Under these assumptions, by Lemma D.3
[&
4 [ Ck
for both E (1,-1} with probability least 1 /. We denote this event by w1. For 8 E (1,-1,
let No, E 1x be the matrix whose rows are indexed by B, and are given by the vectors ni for i E B, As = Q (n) = Ω (k + log 5) and the rows of Ns. are drawn mutually i.idd from Ni d - 1 )) the following holds by Lemma With probability at least - 3 over the randomness of the training data, ||.VB.I| Il S C for both E {1, -13. We denote this event by w2. By
Lemma D.I. there is a constant C' such that
Z f 2Av 2m Z F 2m
< am
( + 2mA)"
(21)
with probability at least 1
á We denote this event by wa. Let w wt 2wz n wg. By the union bound (P() 2 1 5. We condition on w for the remainder of this proof.
3-
Let & E {1,-1] be such that A₂- = m, A-13. Since the network attains zero loss, for all i E B..
(WW(W, x.)
2m
(((),
1) 10 2j, -V v1- (mi))
==1
2m
+ 11-11111 n.))
2m
2m
v + 1y (- -
Σ j=1
7 [z ntح
1=1
11 (sa,) + v1 7
1(2 n.)l
1=1
2m
-A
V
(2, ni)l
1=1
From which we conclude
2m
K2j n.) 2 1 VTA. 2 ViA.
j=1
for all such i. Squaring both sides of the inequality and applying Cauchy-Schwarz, we obtain
2
74, S (1
Σ K= n2)
2m
S 22m - Σ
(2,, mii??
1=1
Summing over all i B,, obtain
2m
|B.7 S 2mm(1 -7) Σ
(zz n2))
iEB, j=1
2m
= =2m(1 - 7) Σ
|| Ng, 12
1=1
33

---

Applying We and w3. we obtain the bound
2m
Ky S Cm(11 - -7)
Σ
|BB 2
j=1
Cm(1 7) Σ
||N ||1 12
2m
S Cmm(1 - 7)
Σ
|,
]=1
CmC(1 ->> l
For (2)), this inequality along with Assumption Iimplies that
2
1 2Xv2m | + 2m22
for a different constant C. With the last two inequalities and equation 21 we obtain the bound, for new constant C.
Ay S C
(|) + 2mA)²
We then apply = 2 and Assumption again to conclude that for some C,
kya,a
> || 2 C
1 1-7
Note that
A1 + A_1
Ain
S 2Ag
1+a
We then bound
Ann
Ag
00
Zinn
kyA,a
T-7
1-?
SC
kya
for some constant C. Now consider test point (ær, y). which satisfies
v(
where n N0s,, (Laa - -vo²)). Since the data distribution is symmetric,
P(yS(W, x)) s 50) P(y/(W .)) s 0 -y(W, 0)
> Pluf(W, x)) wf xx) s 0).
We see that
vf(W x) - v/(W, -x) (1 a (yAinv + (Ztin: n. / -7)
By Lemma
we then can bound
P(y(w, 20 =0)(w,))s([w) N exp
6d
?
A Ina
Cd
exp
ak
for a new constant C. provided An is positive. In the last line we can bound d below as ((n) = 2(k). If Ani negative, then the generalization error least 1 which is also at least exp(-Cd/(ak)).
D
34

---

D.3 Non-benign overfitting
In this section we show that leaky ReLU networks trained on low-signal data exhibit non-benign bennggn overfitting. As in the case of benign overfitting, we will rely on a generalization bound which depends on the signal-to-noise ratio of the network.
Lemma D.4. Let W 22mxdd be the first layer weight matrix of a shallow leaky ReLU network given by equation 7 Suppose (z, y) is a random test point sampled under the data model given in Definition 2.1 If W such that Alin and
Ali 0
Zlin
y'
then
P(y/(W, x) <0) g"
Alternatively, if Atin S O then
1
P(ys(W a)) < 0) > 4
Proof. By Definition 2.1 x, -) is identically distributed to (xz, y). therefore
P(O wW x))
(P((0 v/(W, x)) PP(O -w))))
2 P(0 uf(W x)) U0 > -yf(W. -x))
2 2
PO> w/( x)) - W/ -x))
Next we compute
vf( x) wf(W. -x)
2m
19' y'y(o((w)) x²) - o((10;;- -x)))
=
j=1
2m
= (1 + a)
1) x)
2m
= (1 a))
(11) Zj, v/o + /1 -m)
2m
2m
= (1 a) 7
+ (1+a) -1 1-7
n. Σ (-1)22
j=l
= -11+ aL+a) + (1+ / - 7 (nn 2mm)
The above two calculations imply that
P(0 > yf(W,x)) > P(O
x) of =x))
2
P(O > (1+ (1+a) + (1+ a)
(n2, zim))
P (-n, zim)
7 2 Atin
2
1 1
Suppose that Ajm 2 0. As the noise distribution is symmetric (n, Blin) d (-n, 2mm) Therefore,
4 Sp (Kn Ammn)l >
7 A
1
(Iit..u) ui) > 1 7 |ztin| ||
Aln
1-
4
35

---

then the where = | span((v))
is the unit vector pointing in the direction of Zii- Note by construction u
Alia Ziin ||
0
7dd
1-
then by Lemma A.2
P (nn, unl
7
Alnn
1 1
||
|iin
2
and therefore
1 |P (tt, ui) 2 P(O > (
?
Alin
Zlin
A < O, then again by the symmetry of noise
7
P(O > WW x)) 2 TP nn, Elin) >
Alin
V 11-9
IP (( n1, 2lin) > 0)
4
This establishes the result.
Theorem 3.4. Under the setting given in Assumption
2 let 5 E (0,1) and suppose A -ADD
where 1, X E Rxo satisfy Assumption If 2211, 12 (n + log })) and O following hold.
n
The algorithm AGD terminates almost surely after finitely many updates. With W AGD(X, L(W, X, = 0.
2. With probability at least 8 over the training data (X,9) .9)
P(uf(w,))<0f
Proof. If Ajin O, then by Lemma D.4
Plyf(W, x) < 0)
So it suffices to consider the case Ana 0. Since d Ω (n + log }), by Lemma B.4 the max- margin classifier w" satisfies
n
| < C
1-7
with probability at least 5 over the randomness of the input dataset. We denote this event by w and condition on it for the rest of this proof. By Theorem 3.1
C
W
α aym m
n
m(1
7)
36

---

By Theorem 3.1 therefore
the network perfectly fits the training data, so for all i E [n2] (.f(W, (w)))) 2 1, and
1 S [f(W, æx)]
2m
1) ((w5, xii)
2m
< {w), amحه
f=1
2m
Σ
(a + 2jo Vin.0 + v1 mmn)l
Σ aa
v 7/2 nz)l
2m
2m
< vT 3=1
layl + v 1 - >
{zzj nz))
j=l
This implies that either S consider both cases separately.
/
2m j=l
|ayl or
1/2 S /1 - 7 -3mm K2,, n.)l for all [n]. We
Suppose that 1/2 s >
2m
layl- Then squaring both sides and applying Cauchy-Schware we obtain
2
1
S
7
Σ las1
4
< 2m7
lag 12
2m
< 2my
|wy ||2
j=1
2m W|
Cym
a²(1
This cannot occur if y = 0 =0(2²) and in particular it cannot occur if d = Q(n) and 7 0 (4*)
2m Now suppose that 1 S 3 Σ Cauchy-Schwarz, we obtain
1=1 nz)) for all E [n). Squaring both sides and applying
2
1 5 (1 7)
2m
Σ j=1
(2 nill
2m
5 <2m(1- - 7)
Σ [(= ni
j=1
37

---

Summing over all i E [n], we obtain
2m
n
< 2m(1 -7) Σ
[z nt
4
1=1 1=1
2m
=2m(1- - 7)
Σ
| 12 1|
5=1
2m
I <2m(1 11 Σ
||
2m(1 - 1|
Recall that d = Ω (n + log }) and that the rows of N are ii.dd with distribution Ni d (Ia
vo )) So by Lemma 4.1 with probability at least 1 over the randomness of the dataset,
|| S C. We denote this event by w2 and condition on it for the rest of this proof. So
Cn
Z F
(22)
m(1 7)
Let λ = Va By Assumption !
11
S X for all j E [2m]. So by Lemma D.I
1 - 2m Z 2m1 v [| + 2m1)3
(23)
By 22
CVπ
||
7ml1 7)
CVR
Vm
CAvnm
N 8Xv2m.
where the last line holds if n (2)). Then by 23
121
|
1
2 1
1 113
1
2
S | 22v
2ml
211F 2m22
S
(||
+ +2222²
am
[|| + 2/)a2
am
Taking the square root of both sides and recalling that a (0, a constant, we obtain
C Cl
C'
Z F
am
mm
This implies that either | S since by (22).
2C or
r
Bhall am
The case
|||| S
2C Vm
cannot happen,
C' Vn
/ r 2
Vm(1 7)
C' Vn
mm
2C
Vm
38

---

when n = =[((). So we have
||
|
Again applying (22
we obtain
Vam
Zlin|
2 C Z|
C Can
V
So
Aln
Aliu
-7
< 0
|zim|||
Van
CV1 7
van
j=1
1/2
CVT
2m Σ
2m
lay
Van
1/2
C 1m/m1-a -1
2m
Σ
|| 2 11
Van
C m( 77)
Van
2/2
Here we used that Alm 2 0 and applied Cauchy-Schwarr in the third line. Then by Lemma D.4 if
C 0
23/
7
then
Plyf(W, x) < 0) 1
8
This occurs 7 0 aa
Hence, in all cases, we have shown that with the appropriate scaling, the generalization error is at least when both and w2 occur. This happens with probability at least 1-6.
Appendix E Formalizing benign overfitting as a high dimensional phenomenon
To formalize benign overfitting as a high dimensional phenomenon we first introduce the notion of regime. Informally, regime is subset of the hyperparameters Ω N' which describes accepted combinations the input data dimension d, the number of points in the training sample n, the number of corrupt points k and the number of trainable model parameters
Definition E.1. regime is a subset
2 which satisfies the following properties.
1. For any tuple (d, n, k. p) E Ω the number of corrupt points is at most the total number of points, n.
2. There is no upper bound on the number of points,
sup n DC. (d
A non-trivial regime is regime which satisfies the following additional condition.
39

---

3. Define the set of increasing sequences of S2 as Q = {(m, di ki, Pi)tNN I s.t. lim ny 3o). For any (nt, d, kn Pt)ien S2 it holds that
C
ki 0.
inm 1-400 ni
Intuitively, a regime defines how the four hyperparameters (d, n. p) can grow in relation to one another as n goes infinity. non-trivial regime is one which the fraction of corrupt points the training sample is non-vanishing. In order to make formal definition of benign overfitting as high dimensional phenomenon we introduce the following additional concepts.
A learning algorithm A (d.. is triple indexed sequence of measurable functions Ad.n.p Raa R - Ro.
An architecture M (fap)awEN is double indexed sequence of measurable functions Ja.p R x + R.
A data model measures Da,n,k defined over Tguxd x {+1} x Rd {+1}.
(Dam,) is a triple indexed sequence of Borel probability
With these notions in place we are ready provide definition of benign overfitting in high dimensions.
Definition E.2. Let (e, E (0, A be a learning algorithm, M an architecture, D data model and Qi a regime. for every increasing sequence (dz, ny, Pt)ett St" there exists an such that for all Z L with probability at least â over (X, 9), where (X, 9, x, y) ~ Da it holds that
1. yi yi IAAaA, (X,9). xx)) Vi E [mr]
2. (Py (Ad (X,9). .)) < 0) I inf we P(y/(W, x) S 50
then the quadruplet M, D, Q2) (e, -benignyy overfits. If (A, D, (e, -bbenigly overfits for any (e, E (0, 1)2 then say (A, M, D, benignly overfits.
Analogously, we define non-benign overfitting as follows.
Definition E.3. Let (c, E 10, A be a learning algorithm, M an architecture, data model and Ω a regime. for every increasing sequence (di, ni ki, Pi)eN Q there exists L N such that for all 2 L with probability at least 5 over (X, Y), where (X, 9, x. v) ~ Da holds that
1. f (Add (X,9), xx:) ViE [nd)
2. mp (X, 1). x) < <0) 2 in Plyf(W, x) 50) +
then the quadruplet (A, (A,, D. 22) (e, -)-nnonbeniggu overfus. If (A,M, M, 22) (e, noon-bbbnnyy overfits for any (e, 5) (0, 1/2 then say (A. D. Q) non-benignly overfut..
D.
One of the key contributions this paper is proving (c, -eengn and non non-benign overfitting when the architecture is two-layer leaky ReL.U network (equation [p. the learning algorithm returns the inner layer weights of the network by minimizing the hinge loss over the training data using gradient descent (Definition 2.2). and the regime satisfies the conditions d Q2n log 1/c), 12(15)), k = (n) and 2dm for some network width 2m, m E N.
Appendix F
Experiments
To further support our theory, we train shallow neural networks on the data model described in Definition 2.1 and record the numerical results. Scripts reproduce these experiments can be found hese22/bniggg at hhtpps:: //github com/ htt.aaa///emmmoooorriiiitnnne These experiments were run on the CPU of MacBook Pro M2 with 8GB of RAM. For our first experiment, we investigate the effect of the ratio d the generalization error of the network. Recall that by Theorem 3.2 the generalization
40

---

error is bouned above by exp (n))) when d = 9(1). In other words, if d is larger than critical threshold, then the generalizatione error decays quickly to increases. We empirically confirm this prediction Figure I where train several networks while varying and n, and estimate the generalization error for each configuration by averaging over 20 trials. Within each trial, we trained the inner layer of the network with gradient descent using the hinge loss until the training loss reached O. For d greater than around 7, the generalization error rapidly decays to -
100
140 150
130
1001
120
Generalization error
110
100
10
90
80
70
10
80
50
10 10-4
3
4
7
8
d/n
Figure Generalization error two-layer leaky ReLU network trained to hinge loss varying and d. Parameter settings: 0.1, 7 5/n, 64, k 0.1n, number of trials 5, size of validation sample = 1000.
Next, we train a two-layer network varying n and y (Figure 2), holding constant the ratio Since controls the signal-to-nn -onnal-o--ooie ratio the data, the generalization error the learned network decreases as y increases. For each value of the generalization eπror falls off steeply y reaches certain threshold. This threshold decreases as n increases, indicating that the network has higher noise tolerance increases. This is in agreement with theoretical results where found that benign overfitting occurs at the threshold = Ω ( (which in this case ).). We also see that the generalization error for large values of y similar across different values of n. This effect is also predicted by Corollary 3.2. since we scale both d and k proportionally to n.
41

---

n=50
n=100
n=150
n=200
0.4
Generalization error
0.3
0.2
0.1
0.0
0.00
0.02
0.04
0.06
0.08
Gamma
Figure 2: Generalization error of two-layer leaky ReLU network trained hinge loss varying and n. Parameter settings: 0.1, d = 2n, 64, k 0.1n, number of trials 10, size of validation sample = 1000.
42

---

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

---

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

---

reproducible, they Answer: [Yes]
Justification:
We provide a link to our code to reproduce our experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/ public/guides. www.//ooeeaeiiiooonooooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https for more details.
/ //nips httpp//ccpbbbccguuuccccce wwwp:/ic/ggi////eeeeeooooeeeseee httpg/dddds//oeuubbmmmmmn seriissssonpoiiiio
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We describe our setup in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Our experiments consist of heatmap and a line chart with multiple plots.
It was not possible add error bars without crowding the plots. In our description of our experimental setup we describe the sample size, from which standard errors can be computed.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
45

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We describe the resources used in Appendix F
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics btttps://neur// http:///www.pbcceeciccceeeeeeee htt.p///eeeee/eoooooooooo/o///oo
Answer: [Yes]
Justification: The research conducted in the paper did not use data, assets, or human participants; only studied existing models; and was conducted in accordance to the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: This paper is purely theoretical study explaining behaviors seen in neural networks in practice. There are no foreseeable societal impacts of this work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
46

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No model data is presented in this paper. The paper is theoretical study of neural networks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assests.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
47

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not use new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemoodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
48

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
49


Reviews:
[{"review_id": "JacYA6kG3T", "reviewer": "Reviewer_1LbK", "summary": "This paper studies benign overfitting in a two-layer leaky ReLU network trained with hinge loss for a binary classification task. This paper proves that in a finite iteration, the leaky ReLU network can reach zero training loss through gradient descent, and the network weight matrix after convergence will approximate the max-margin. And this paper provides the conditions for benign overfitting and non-benign overfitting of the leaky ReLU network.", "questions": "The dependence of Theorem 3.2 and Theorem 3.3 on n, d, k does not cover all cases. For other cases, what are the characteristics of overfitting?", "limitations": "See Weaknesses", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper improves the previous work's requirements for almost orthogonal training data and input dimension $d= \\Omega(n² \\log n)$, and only requires $d = \\Omega(n)$.", "weaknesses": "This paper mainly studies a specific shallow leaky ReLU network. The applicability of the results is limited to deeper neural networks or other complex models such as CNN and transformer.\n\nThe results rely on a specific linearly separable data distribution assumption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and questions. It appears that the primary concern lies in the fact that our results only hold for shallow networks and linearly separable data. We emphasize that these are limitations also present in the existing literature on benign overfitting in non-linear models / networks in the rich feature learning regime (i.e., not leveraging the NTK framework). The primary contribution of our work is to relax the relationship between the input dimension and the number of points: in particular past works require a very large input dimension, $d = \\Omega(n^2 \\log(n))$ or worse. In contrast, our results are for $d = \\Omega(n)$ which is far more realistic. Furthermore to achieve this required new and highly different techniques to those used in the existing literature. As a result we would respectfully ask the reviewer to reconsider their rating. We proceed to address in more detail the specific weaknesses highlighted.\n\n> This paper mainly studies a specific shallow leaky ReLU network. The applicability of the results is limited to deeper neural networks or other complex models such as CNN and transformer.\n\n> The results rely on a specific linearly separable data distribution assumption.\n\n- Our setup involving a shallow ReLU network combined with the proposed data model is a) in-line with relevant and recent literature on the topic and b) represents perhaps the simplest and most natural setting involving a non-linear model in which one can study benign overfitting. Even in this simple setup many theoretical questions remain open: in particular, all past works require a near orthogonality condition on the data. As the emphasis of our work is to relax this technical condition we decided to work with this canonical setup. Deriving theory for more complicated settings, in particular deep networks and transformers, is clearly an important open problem. Such theory will almost certainly be built upon a solid understanding of the simple, shallow case.\n\n> The dependence of Theorem 3.2 and Theorem 3.3 on $n, d, k$ does not cover all cases. For other cases, what are the characteristics of overfitting?\n\n- In Theorems 3.2 and 3.3, the assumption $k = O(n)$ is minimal, since we always have $k \\leq n$. The relaxation $d = \\Omega(n)$ from $d = \\Omega(n^2 \\log n)$ is a main improvement of our results from prior work. We believe that the regime $d = O(n)$ will lead to different results than the ones observed in our paper, and will involve different techniques to study. In particular, if $md \\leq n$, then the network is underparameterized and it is likely impossible to perfectly fit the data. When $d = 1$ and the network is sufficiently wide, there are some partial results in the literature which suggest that the network will perfectly fit the data, but the overfitting is not benign [1]. To the best of our knowledge the case $d = O(n)$ remains open.\n\n[1] Guy Kornowski, Gilad Yehudai, and Ohad Shamir. From tempered to benign overfitting in ReLU neural networks. *Advances in Neural Information Processing Systems*, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6009Ym3kBD", "reviewer": "Reviewer_8RfS", "summary": "This paper studies the benign overfitting of two-layer leaky ReLU network for binary classification with only mild overparameterization under a simple Gaussian mixture model assumption. First, the paper proves that for sufficiently small initialization, gradient descent with hinge loss converges in a polynomial number of iterations to an approximate max-margin solution. Then, the paper establishes that any approximate margin maximizer achieves benign overfitting, or low test error, in an (essentially tight parameter) regime where $d = \\Omega(n)$. These results are matched by lower bounds in certain parameter regimes (low SNR and high label noise).", "questions": "1. What do the authors expect to change for multiclass classification with a more complicated mixture model? \n2. Line 278, there is a typo; it should be $X \\sim N(\\sqrt{\\gamma}a_v, \\frac{1-\\gamma}{d}\\| z\\|^2)$.\n3. Line 325, “of” is missing in “The proof Theorem 3.3,...”", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. This paper is well-written, clear, and technically interesting. I especially appreciated the technical overview, where the main proof ideas are explained. \n2. Previous works required $d = \\Omega(n^2 \\log n)$ to obtain benign overfitting due to using near-orthogonality of the input data, but this work only requires $d = \\Omega(n)$, which is tight (for the overparameterized regime). Hence extending benign overfitting to this setting requires using subgaussian bounds on the extreme singular values of Gaussian matrices. I do want to note that this idea has also been used to prove benign overfitting for binary and multiclass classification $d = \\omega(n)$ (see e.g. [1, 2])  \n3. Many prior works studied linear models, whereas this paper studies ReLU activation (although with only one trainable linear layer). \n4. It is of particular note that the proof techniques do not rely on exact margin maximization, as the results then apply to parameters found by GD in polynomial time (as opposed to the infinite time limit). Many (though not all) previous works have explicitly studied the limiting parameters (e.g. min $\\ell_2$-norm interpolation), which is not reached in practice. \n5. As I described in the summary, the upper bounds have matching lower bounds in some parameter regimes. Theorem 3.3 is a matching lower bound for the misclassification probability in the regime where the label noise rate $k/n = \\Omega(1)$, which is fairly realistic. \n[1] Wang, Ke, and Christos Thrampoulidis. \"Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting, and regularization.\" SIAM Journal on Mathematics of Data Science 4.1 (2022): 260-284.\n[2] Wu, David, and Anant Sahai. \"Precise asymptotic generalization for multiclass classification with overparameterized linear models.\" Advances in Neural Information Processing Systems 36 (2024).", "weaknesses": "No major weaknesses to report.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad the reviewer appreciates the contribution of our work and thank them for highlighting the two related works on linear models [1,2]. We are happy to cite these and discuss them in future revisions. We also thank the reviewer for spotting the two typos listed, we will do a further thorough proofread before uploading a revised version.\n\nIn regard to the question\n>What do the authors expect to change for multiclass classification with a more complicated mixture model?'\n\nA multiclass classification setting is an interesting future direction to look into.  It would involve looking at a different model / loss but the general form of argument, i.e., bounding the singular values of the noise matrix and comparing to the one hot class max-margin classifiers, seems possible to generalize to this new setting.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E9Z5bENfwN", "reviewer": "Reviewer_7S96", "summary": "The paper studies benign overfitting in leaky ReLU networks trained with hinge loss on a binary classification task. The paper gives the conditions on the signal-to-noise ratio under which benign or harmful overfitting occurs for leaky ReLU networks. Unlike the previous related works, this paper does not require the training data to be nearly orthogonal and reduces the input dimension required from $\\Omega(n^2\\log n)$ to $\\Omega(n)$.", "questions": "1. Since hinge loss may not be so commonly used in the analysis of neural networks, maybe you can also try on other loss functions like cross-entropy loss or logistic loss.\n2. Since the proof techniques and ideas are closely related to [1], what is the main difference between the two papers?\n\n[1] Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns over\u0002-parameterized networks that provably generalize on linearly separable data. In International Conference on Learning Representations, 2018.", "limitations": "The authors have shown the limitations as the future directions in the paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper demonstrates that leaky ReLU networks trained on hinge loss with gradient descent satisfy an approximate margin maximization property.\n2. Prior works usually supposed nearly orthogonal data setting and dimension $d=\\Omega(n^2\\log n)$. However, this paper needs linearly separable data and dimension $d=\\Omega(n)$, which weakens the requirement.", "weaknesses": "1. The paper may lack some experiments. The results are fully theoretical. If there are some empirical experiments, the conclusion will be more convincing.\n2. There are few explanations for theorems and assumptions. Some additional explanations may let readers understand the results better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for reading our paper and for raising their questions and comments. We are confident that we can clarify the issues raised and hope in light of our responses below that the reviewer will consider raising their score.\n> The paper may lack some experiments. The results are fully theoretical. If there are some empirical experiments, the conclusion will be more convincing.\n\nWe appreciate the suggestion of including experiments to better explain our results.  We will update the paper to include experiments in future revisions.  We've attached a file showcasing a couple of experiments along with explanations in the main rebuttal.\n> There are few explanations for theorems and assumptions. Some additional explanations may let readers understand the results better.\n\nWe are happy to provide more commentary in future revisions. To clarify here, in regards to the assumptions, Assumption 1 upper bounds both the step size and initialization scale. Both of these bounds are required for the proof of convergence to a global minimizer: we remark that although they are no more egregious than comparative theory works in this space, they are typically smaller than what is used in practice. Assumption 2 clarifies the model we consider and the assumptions on the data: in particular we consider data drawn from a mixture of Gaussians with a relatively small number of label corruptions. This is very standard in the literature. In terms of our results, we give an overview in Section 1.1 outlining the role of the different Theorems and Lemmas. In terms of explaining our proof techniques, we chose in Section 4 to present the key ideas using the simple case study of a linear model. In particular we highlight four key steps: first derive generalization bounds using the SNR of a classifier in terms of the size of its component in the noise versus signal subspace, second upper bound the max margin classifier, third and fourth use the bound on the max margin classifier as well as the zero loss property to to upper and lower bound the SNR.\n> Since hinge loss may not be so commonly used in the analysis of neural networks, maybe you can also try on other loss functions like cross-entropy loss or logistic loss.\n\nWe agree that different loss functions would be an interesting generalization of our results. We chose the hinge loss because it exhibits similar properties to other classification losses (such as de-emphasizing points which have already been correctly classified) while having favorable properties for theoretical analysis (such as convergence in finitely many iterations). We expect that our results could admit generalizations to the cross-entropy or logistic losses with an appropriate analogue of the convergence analysis in Theorem 3.1. Fundamentally, our generalization bounds depend on gradient descent converging to a solution which is approximately margin maximizing. For any other loss function satisfying this property, we immediately obtain a benign overfitting result by applying Theorem 3.2.\n\n> Since the proof techniques and ideas are closely related to [1], what is the main difference between the two papers?\n\nThe main result of [1] is that  a leaky ReLU neural network trained with the hinge loss on linearly separable data will converge to a global minimizer. Moreover, the weights of this solution have norm bounded above by the norm of the max-margin linear classifier of the data. While this idea and proof technique are important to our paper, our main contributions are in describing how this margin maxmimization results in benign overfitting. That is, we are interested in the generalization of leaky ReLU networks on noisy data, and we use a similar convergence analysis as an intermediate result to this goal. While [1] does establish a generalization bound in Theorem 4, the bound assumes that *population dataset* is linearly separable rather than just the training dataset. Hence, it cannot be applied when the training dataset has label-flipping noise, which is the setting that we are interested in for benign overfitting. The bound also gets worse as the learning rate $\\eta$ goes to 0, while our generalization bounds do not have any dependence on $\\eta$. In order to make these adaptations, we perform an analysis which uses properties of our specific data model. In the process, we obtain a more detailed understanding of how generalization depends on the number of data points, the dimensionality of the data, and the amount of noise in the data.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uYjhnWjoda", "reviewer": "Reviewer_xTBG", "summary": "This paper stuides the benign overiftting of two-layer neural networks (only training the first layer) with leaky ReLU for binary classification, which relaxes the dimension condition on the dimension from $d = \\Omega(n^2 log n)$ to $d = \\Omega(n)$.\n\nThe considered problem setting is\n- data generation process: the label is generated by Gaussian data corrupted by flipped noise under a linear function after sign. The parameter $\\gamma$ controls the component of signal and noise. The more $\\gamma$, the more signal.\n- the used loss is hinge loss, and the involved with optimization algorithm is sub-gradient descent.\n\nThe obtained results include that\n- implicit bias: the obtained solution (neural network parameter) will converge to a max-margin linear classifier.\n- condition of benign overfitting: $d = \\Omega(n)$, signal strength $\\gamma = \\Omega(1/k)$ \n- non-benign overfitting: $d = \\Omega(n)$, $\\gamma = O(1/d)$", "questions": "- The key idea is to bound the weight norm and its alignment with any linear separator of the data during each update by the distribution of sigular values of the noise. In this case, the obtained results heavily depend on the data-generation process. It would be possible to consider general data generation process? Besides, $d = \\Omega(n)$ is still large, what is the limit for this? Maybe constant order is sufficient?\n\n- In the proof, line 706, in the last inequality, regarding the summation $\\sum_{i,l} \\in F(t)$, there is one term missing about $\\langle w_j^{(t)}, x_j \\rangle$?\n\n- There are some typos: line 707: $\\sigma(s)$ -> $\\sigma(z)$", "limitations": "n/a", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- relax the dimension dependence from $n^2$ to $n$\n- provide the condition for benign overfitting (or not)\n- demonstrate the implicit bias: converge to a max-margin linear classifier", "weaknesses": "- this paper requires linear separable data, more strictly speaking, the optimal Bayes classifier is linearly separable, that means linear classifier is sufficient to learn this problem. I don't see the strong motivation of using two-layer neural networks, though this is a common issue in the benign overfitting community.\n\n- One major issue is, no comparison with [1]. I think this comparison should be included in terms of problem setting, proof techniques, the obtained findings. \n\n- About the main result, intuitively, classification rate is proportional to $k$, the number of corrupt points. More discussion on $\\gamma$ and $k$ is needed.\n\n- Regarding theorem 3.2, it's unclear to me in several points: \ni) the sample complexity is $\\Omega(n^2)$ in Theorem 3.1. How does this contribute to $|A|$?\niI) a larger $m$ leads to a larger missclassification probability. Intuitively, a larger size of neural network is better for performance.\n\n- In Corollary 3.2.1, I didn't see $\\delta$ in the main result.\n\n- Lemma B.1 can be directly obtained from the high dimensional probability book, Chapter 5.\n\n\n---\n[1] George etal. Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign? NeurIPS 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the overall positive feedback on our work. We are confident we have addressed each of the issues raised and hope the reviewer might consider raising their score in light of our responses.\n>Linearly separable data\n\nIndeed, a linear classifier is sufficient to learn this problem: we also demonstrate that the max-margin linear classifier benignly overfits in our data setting. However, shallow neural networks are substantially more complex models and can express a rich class of functions. Without explicit regularization, previous conventional machine learning wisdom suggests neural networks will not learn a linear classifier. Results on benign overfitting in the linearly separable setting, including ours, demonstrate that the implicit bias of neural networks trained with gradient descent is favorable to learning linear problems.\n>No comparison with [1]\n\nWe thank the reviewer for bringing this to our attention and will more thoroughly compare our work with [1] in the future revisions. Here are the comparisons with [1]:\n \n- The settings are very similar with regards to the data assumptions, network model, and training. The most significant differences is that [1] uses ReLU activations and requires $d = \\Omega(n^2\\log n)$ while we use leaky ReLU and $d = \\Omega(n)$.\n\n- The proof techniques for the two papers are very different. In [1], the authors analyze the activation patterns of the neurons during various phases of training. We do not consider the activation patterns and instead bound how much the neural network can diverge from a linear model. These different techniques are appropriate in different settings: for a ReLU network it is possible that the dynamics of different neurons are driven by different subsets of the data, but with leaky ReLU this effect is weaker and the network is closer to a linear model.\n\n- Both papers prove the existence of multiple distinct \"overfitting\" regimes. However, [1] also shows a regime where the network fails to overfit. This regime does not occur for the leaky ReLU network model we use: Theorem 3.1 shows that networks always achieves zero loss in our setting.\n\n>More discussion on $\\gamma$ and $k$ is needed\n\nWe highlight that in both Corollary 3.2.1 and Theorem 3.3 the classification error increases with $k$. The classification error bound uses the norm of the network weights, which by Theorem 3.1 is proportional to the norm of the max margin classifier. We bound this twice. In Lemma B.3 we get a dependence on $k$ by constructing an \"ideal\" linear classifier: one that uses the true signal vector for clean points and the noise only as minimally needed to fit the corrupted points. If $\\gamma$ is small, then the classifier constructed in Lemma B.4 (which uses only noise) has smaller norm. In fact, if $\\gamma$ is too small, this norm is so much smaller that the network can never learn the ``ideal'' classifier, which leads to Theorem 3.4 (non-benign overfitting).\n>Sample complexity is $\\Omega(n^2)$ in Theorem 3.1\n\nThe number of iterations $T$ does not directly contribute to $|\\mathcal{A}|$. In the proof of Theorem 3.1, we bound $|\\mathcal{A}|$ by bounding the number of non-zero data point updates. The bound for the number of updates is also a (pessimistic) bound for $T$, which we do not use but record for completeness.\n>Larger $m$ leads to a larger misclassification probability\n\nThe misclassification probability can increase if $m|\\mathcal{A}|^2$ increases. But in Theorem 3.1, $|\\mathcal{A}_{GD}| \\sim m^{-1/2}$. Thus our results specifically for neural networks (Corollary 3.2.1, Theorems 3.3 and 3.4) are independent of $m$.\n>In Corollary 3.2.1, I didn't see $\\delta$ in the main result.\n\nThe parameter $\\delta$ refers to the \"failure probability\" of the data generation process. It appears in Theorem 3.2 in lines 228--230.\n>Lemma B.1 can obtained from the high dimensional probability book\n\nWe thank the reviewer for drawing our attention to Theorem 4.6.1 in High Dimensional Probability by Vershynin. We emphasize that Lemma B.1 summarizes two results by Vershynin and co-authors that together are equivalent to 4.6.1. We have clearly cited both works and do not claim this lemma to be a novel or significant part of our contribution.\n>It would be possible to consider general data generation process?\n\nProving results for arbitrary data distributions might be intractable as benign overfitting does not always occur even experimentally. However, our results for benign overfitting (Theorem 3.2) can be proven in a slightly more general setting. If all coordinates of noise are i.i.d. sub-Gaussian, the same result will hold with an analogous proof. We chose to work with Gaussian noise to prove error lower bounds (Theorems 3.3 and 3.4). We emphasize that our data assumptions are standard for works in this space.\n>$d = \\Omega(n)$ is still large, what is the limit for this? Maybe constant order is sufficient?\n\nWe believe that the regime $d = O(n)$ will lead to different results than the ones observed in our paper, is challenging, and will involve different techniques to study. In particular, if $md \\leq n$, then the network is underparameterized and will likely not perfectly fit the data. When $d = 1$ and the network is sufficiently wide, there are partial results in the literature which suggest that the network will perfectly fit the data, but the overfitting is not benign [2]. To our knowledge, the general case $d = O(n)$ remains open.\n>In the proof, line 706...\n\nThank you for highlighting this. There was a missing factor of $\\dot{\\sigma}(\\langle w\\_j^{(t)}, x\\_l\\rangle)$. This does not affect the correctness and we will correct this in future revisions.\n>Typos\n\nThank you for drawing this to our attention. We will make another thorough proofreading to fix typos in revised versions.\n\n[2] Guy Kornowski, Gilad Yehudai, and Ohad Shamir. From tempered to benign overfitting in ReLU neural networks. *Advances in Neural Information Processing Systems*, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their time and efforts in providing feedback on our work. Two actions we can take forward in future revisions are as follows.

- **Improving the presentation**: We will better connect Section 3, where the key results are presented, with the proof sketch given in Section 4. In doing so we can provide better intuition for the reader as to the role of the number of corruptions $k$ and the signal strength $\gamma$, in particular their role in the derived bounds. We will also better elucidate the differences between our work and that by Brutzkus et al. and George et al. in the related works section.
- **Including experiments**: We will include in future revisions a new section in the appendix containing numerics supporting our theoretical results. Preliminary plots are included in the attached pdf. We offer the following explanation of the two experiments.
    - Under Assumptions 1 and 2 a key contribution of our work is to show $d = \Omega(n)$ is sufficient for benign overfitting. Note, by contrast other works require $d = \Omega(n^2\log(n))$ or higher. To test this experimentally, using gradient descent and the hinge loss we trained the inner layer weights of shallow, two layer leaky ReLU networks, varying both the size of the training sample $n$ as well as the input dimension $d$. To estimate the generalization error, for each setting of $n$ and $d$ twenty trials were conducted. Within each trial a training sample was drawn from the data model (described in Definition 2.1), a network as per Assumption 2 was initialized and trained to zero hinge loss and the validation error computed on a validation sample. The generalization error across the trials was then averaged. The results of this experiment are provided in Figure 1.

    - We remark that the number of corruptions $k$ in our experiments is fixed at $10\%$ of $n$. Considering the figure, when $d =n$ we observe that the generalization error matches the corruption rate, suggesting proportional, tempered overfitting. We note that our results do not cover or explain this setting. However, for $d >n$  we observe what seems to be a decrease in the generalization error with $d$: indeed, for $d = 10 n$ versus $d = n$ we observe a ten-fold decrease in the generalization error, dropping from the corruption rate of $10\%$ to $1\%$ error. This suggests, inline with our theory, that the generalization error is a sharply decreasing function of $d/n$.

   - In the second experiment (Figure 2), we vary the number of data points $n$ and the signal strength $\gamma$, holding constant the ratio $d/n$, the corruption rate $k/n = 0.1$, and the hidden dimension $m = 64$. We plot the generalization error as a function of $\gamma$ over different values of $n$. We find that for all values of $n$, the generalization error decreases steeply at a certain threshold, then levels off at a fixed small value. For higher values of $n$, this drop-off of generalization error occurs sooner. This is in agreement with our theoretical results where we found that benign overfitting occurs at the threshold $\gamma = \Omega(1/k)$ (which is in this case $\Omega(1/n)$). We also see that the generalization error for large values of $\gamma$ is similar across different values of $n$. This effect is also predicted by Corollary 3.2.1, since we scale both $d$ and $k$ proportionally to $n$.

Meta-review: In this paper, the authors establish conditions under which a two-layer leaky ReLU network (trained with hinge loss) provably exhibits benign or non-benign overfitting on noisy linearly separable data.  Previous works establish comparable results but require that the data to satisfy a near orthogonality property, requiring that the input dimension scales like n^2 log n, where n is the training sample size.  In the present work, the authors use an alternative proof strategy and only require that the input dimension scales like n.  The proof technique is based on an approximate margin maximization property, which is responsible for the improved results and may allow for additional results to be proved.  While the results are limited to the case of linearly separable data, these assumptions are standard in recent works in the area.  The strengths outweigh the weaknesses, and the paper is recommended for acceptance.
Decision: Accept (spotlight)