Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign?
Authors: Erin George
Michael Murray
William Joseph Swartworth
Deanna Needell
Venue: NeurIPS 2023 spotlight (2023)
Keywords: benign overfitting
neural networks
relu
hinge loss

Abstract: We study benign overfitting in two-layer ReLU networks trained using gradient descent and hinge loss on noisy data for binary classification. In particular, we consider linearly separable data for which a relatively small proportion of labels are corrupted or flipped. We identify conditions on the margin of the clean data that give rise to three distinct training outcomes: benign overfitting, in which zero loss is achieved and with high probability test data is classified correctly; overfitting, in which zero loss is achieved but test data is misclassified with probability lower bounded by a constant; and non-overfitting, in which clean points, but not corrupt points, achieve zero loss and again with high probability test data is classified correctly. Our analysis provides a fine-grained description of the dynamics of neurons throughout training and reveals two distinct phases: in the first phase clean points achieve close to zero loss, in the second phase clean points oscillate on the boundary of zero loss while corrupt points either converge towards zero loss or are eventually zeroed by the network. We prove these results using a combinatorial approach that involves bounding the number of clean versus corrupt updates during these phases of training.

Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign?
*Erin George, 'Michael Murray, William Swartworth, Deanna Needell
Department of Mathematics, UCLA, CA, USA
[egeo, mmurrry, ws wswart wawaattworthe h,, deanna] @math. ucla. edu
"qqual contribution
Abstract
We study benign overfitting in two-layer ReLU networks trained using gradient descent and hinge loss on noisy data for binary classification. In particular, we consider linearly separable data for which relatively small proportion of labels are corrupted or flipped. We identify conditions on the margin of the clean data that give rise to three distinct training outcomes: benign overfitting, in which zero loss is achieved and with high probability test data is classified correctly; non-benign overfitting, in which zero loss is achieved but test data is misclassified with probability lower bounded by a constant: and non-overfitting. in which clean points, but not corrupt points, achieve zero loss and again with high probability test data is classified correctly. Our analysis provides fine-grained description of the dynamics of neurons throughout training and reveals two distinct phases: in the first phase clean points achieve close to zero loss, in the second phase clean points oscillate on the boundary of zero loss while corrupt points either converge towards zero loss or are eventually zeroed by the network. We prove these results using a combinatorial approach that involves bounding the number of clean versus corrupt updates across these phases of training.
1 Introduction
Conventional machine learning wisdom suggests that the generalization error of complex model will typically be worse versus a simpler model when both are trained interpolate data. Indeed, the bias-variance trade-off implies that although choosing complex model is advantageous in terms of approximation error, comes the price of an increased risk of overfitting. The traditional solution to managing this trade-off is to use some form of regularization, allowing the optimizer to select predictor from rich class of functions while at the same time encouraging to choose one that is in some sense simple. However, in recent years this perspective has been challenged by the observation that deep learning models, trained with minimal if any form of regularization, can almost perfectly interpolate noisy data with nominal cost to their generalization performance (Zhang et al. 2017 Belkin et al. 2018b 2019). This phenomenon is referred to as benign overfitting.
Following these empirical observations, a line of research has emerged aiming to theoretically characterize the conditions under which various machine learning models, trained zero loss on noisy data, obtain, at least asymptotically, optimal generalization error. To date, the majority of analyses in this regard have focused primarily on linear models, including linear regression (Bartlett
et aa.|22220) Muthukumar et al., 20200 Wu & Xu| 2020 Chatterji & Long] 2021: Zou et al.) 2021 Hastie et al. [2022] Koehler et al. 2021 Wang et al., 2021a] CChtterrji Long 2022 Cao al. Shamir 2022), , logistic regression Chatterji & Long 2021; Muthukumar et al.) |02 Wang
2021
ct al.
2021b) and kernel regression (Belkin et al. 221 Saj Mei & Montanari] 2019 Liang & Rakhlin
2020
Liang et al. 2019). With regards to understanding benign overfitting in neural networks, in the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Neural Tangent Kernel (NTK) regime (Jacot et al. 2018) the prediction of a neural network is well approximated via kernel regression (Adlam & Pennington 2020). However, this regime typically requires unrealistically large network width and fails to capture feature learning. Indeed, and despite being the initial source of inspiration, an understanding of when and how neural networks benignly overfit in the rich, feature learning regime is not well understood.
1.1 Contributions and related work
In this work we study benign overfitting in the context of binary classification for two-layer ReLU networks, trained using gradient descent and hinge loss, on label corrupted, linearly separable data. There are a number of recent and or concurrent works which prove benign overfitting results in a similar setting Frei et al. (2022 2023): Xu & Gul (2023); Cao et al. (2022); Kou al. (2023); Kornowski ct al. (2023). however, we emphasize that these exclusively study exponentially tailed losses, notably the popular logistic loss. Benign overfitting intimately related to the notion of implicit bias, the preference of an algorithm for selecting minimizers with certain properties over others. The implicit bias of homogeneous networks trained with gradient descent on an exponentially tailed loss from a low initial loss is known to converge in direction to TarrushKKhn-TTe point of the associated max-margin problem Lyu & Li (2020); Ji & Telgarsky (2020). This implies at least intuitively a certain bias towards margin maximization. In recent work Frei et al. (2023) it is
(KKT)
shown that if the input data is sufficiently orthogonal then a shallow, leaky ReLU network evaluated on such a KKT point is equivalent to particular linear classifier. Moreover, and under additional data assumptions, the authors show such networks benignly overfit. Another recent paper Kornowski ctt al. (023) uses a similar approach to derive benign overfitting results for ReLU networks and also provides a description of the transition between benign and tempered overfitting in the univariate input case. To the best of our knowledge, equivalent results the implicit bias of homogeneous networks trained with non-exponentially tailed losses are not characterized. Furthermore, training a linear classifier with an exponential versus non-exponential tailed loss is known result in a different implicit bias, with the non-exponential tailed loss potentially inducing convergence in direction to a classifier with a poor margin Di et al. (2020). As result, a priori it is not clear if and how the choice of hinge loss impacts the propensity for a shallow ReLU network to overfit.
There are two main existing lines of work which study benign overfitting in neural networks outside of the kernel regime. Concerning perhaps the most relevant line of prior work to our own, [Frei et al. (2022) consider smooth, leaky ReLU activation function, train the network using the logistic instead of the hinge loss and assume the data is drawn from a mixture of well-separated distributions. The key result of this work is that given a sufficient number of iterations of GD, then the network will interpolate the noisy training data while also achieving minimax optimal generalization error up constants in the exponents. A concurrent work Xu & Gu (2023) extends this result to more general activation functions including ReLUU, relaxes the assumptions on the noise distribution to being centered with bounded logarithmic Sobolev constant, and also improves the convergence rate. As highlighted in Xu & Gu (2023), the fact that ReLU is non-smooth and non-leaky significantly complicates the analysis of both the convergence and generalization. A second line of work (Cao) ct al. 2022. Kou et al. (023) studies benign overfitting in two-layer convolutional as opposed to feedforward neural networks. Whereas here and in Frei et al. 2022); ;; Xu & Gu 20033 each data point is modeled as the sum of a signal and noise component, in Cao et al. (2022); Kou et al. (2023)
Sab-Gaussian
the signal and noise components lie in disjoint patches. The weight vector of each neuron is applied to both patches separately and 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 vs non-benignly overfits. We emphasize that the data model studied in this work is very different to the setting we study here, and as a result we primarily restrict our comparison to that with Frei et al. (2022) and the concurrent work Xu & Gu (2023). Finally, in regard to optimizing shallow ReLU networks using hinge loss, a line of work (Brutzkus et al. 2018 Wang et al.] 2019: Yang et al. 202I) studies the convergence of gradient descent on generic, linearly separable data without label corruptions. These works also require additional assumptions, notably leaky ReLU instead of ReLU, insertion of noise into the optimization algorithm or changes to the loss function.
Before we discuss our contributions we remark that a previous work Mallinar et al. 2022) describes and experimentally explores a taxonomy of overfitting: benign overfitting, where the generalization error is optimal; catastrophic overfitting, where the generalization error is close to random chance;
2

---

and tempered overfitting, which lies in between. In this work, we do not consider the full breadth of this taxonomy, and use the terms "non-benign overfitting" or equivalently "harmful overfitting" to refer to overfitting that may be either tempered or catastrophic. We now summarize our contributions: in particular, under certain assumptions on the model hyperparameters, we prove conditions on the clean margin resulting in the three distinct training outcomes highlighted below. We remark also that the prior works discussed primarily focus on deriving positive benign overfitting results.
1. Benign overfitting:
Theorem 3.1 provides conditions under which the training loss con- verges to zero and bounds the generalization error, showing that it is asymptotically optimal. This result is analogous to those of Frei al. (2022 and Xu & Gu (2023) but for the hinge instead of logistic loss.
2. Non-benign overfitting: Theorem 3.6 provides conditions under which the network achieves zero training loss while generalization error is bounded below by a constant. Unlike Frei et al. (2022) and Xu & Gu (2023). this is not due to the son-separability of the data model but is instead a result of the neural network failing to learn the optimal classifier.
3. No overfitting: Theorem 3.8 provides conditions under which the network achieves zero training loss on points with uncorrupted label signs but nonzero loss on points with corrupted signs. Again the generalization error is bounded and shown to be asymptotically optimal.
To conclude this section we further remark that our proof techniques are quite different from those used in (Fre et al. (2022); Xu & Gu (2023) and indeed the other works highlighted in this section. Again we emphasize this is due to the fact we study the hinge loss instead of the logistic loss and discuss the differences arising from this in detail in Section 3 In particular,
set up the problem in such a way that the convergence analysis reduces to counting the number of activations of clean versus corrupt points during various stages of training. Our analysis further provides detailed description of the dynamics of the network's ' neurons, thereby allowing us to understand how the network fits both the clean and corrupted data.
2 Preliminaries
2.1 Data model
We consider training sample of 2n pairs of points and their labels (Xi, y:) where (xi, ys) Rd x [11 for all E [2n]. Furthermore, we identify two disjoint subsets ST C [2n] = {1, .....,2n) 2n} and Sp [2m], Sr Sp = [2n]. which correspond to the clean and corrupt points in the sample respectively. The categorization of point as clean or corrupted is determined by its label: for all i E [2n] we assume y {i) (-)" where B(i) - iff Sp and 3(1) = otherwise. In addition, we assume [Sp 7 [2m] e| = |Sp n [2m]al = k and |S, n [2n]el = Sr n [2m]a]= = n k. where [2m]e C [2m] and [2n]. C [2n] are the even and odd indices, respectively. We remark that this assumption simplifies the exposition of our results but is not integral to our analysis. Each data point assumed have the form
x = (-1) (())n)
(I)
Here IRd satisfies ||||| and furthermore refer to the signal vector the alignment of a clean point with v determines its sign. Indeed, sign((x, v)) = (-1)' = y/: for E ST whereas sign((x; ((x, v)) = - y for i Sp. Thus we may view the labels of a corrupt point as flipped from their clean state. The vectors (m:) are mutually independent and identically distributed (i.i.d)) random vectors drawn from the uniform distribution over gd-1 n span(v}', which we denote ( svpn Clearly this distribution is symmetric, mean zero and for any n ~ (ssann
holds that n and |||| = 1. We refer to these vectors as noise components due to the fact that they are independent of the labels of their respective points. The real, scalar quantity y E [0, 1] controls the strength of the signal versus the noise and also defines the clean margin. Finally, at test time a clean label U({ (1-11,11 1,) is sampled and the corresponding test data point is constructed,
x x= + / 11-11 1n)
(2)
where again (span-v))))
3

---

The key idea we use to characterize the training dynamics is to reduce the analysis of the trajectory of each neuron to that of counting the number of clean versus corrupt updates it. This combinatorial approach relies on each point having similar sized signal and noise components. In order to make our analysis as clear as possible, we select a data model which ensures the signal and noise components are consistent in size across all points. We emphasize that these assumptions are not strictly necessary and we believe analogous analyses could be conducted when the signal and noise components are instead appropriately bounded. In addition, and discussed in more detail in Section 3.2, the orthogonality the signal and noise components allow us to demonstrate non-benign overfitting when perfect classifier exists.
2.2 Network architecture, optimization and initialization
We consider a densely connected, single layer ferd-forward neural network f : R2mxd R with the following forward pass map,
2m
S(W, x) = Σ
(-1))((w;,
==1
Here @ == 20, denotes the ReLU activation function and w, the j-th row of the weight matrix W E 122x The network weights are optimized using full batch gradient descent (GD) with step size > O in order to minimize the hinge loss over a training sample ((x, ) C (R& x (11,1}) sampled as described in Section 2.1 After 1' iterations this optimization process generates a sequence of weight matrices (W('); n- For convenience, we overload our notation for the forward pass map of the network and let ftt x) == f(W('), x). Furthermore, we denote the hinge loss the i-th point iteration /. e(t, i) == max (0, 1 yr x;)). The hinge loss over the entire training sample at iteration is therefore L(t) E.n (tt, i). Let F()) == fi [2m] : ((t, (t,,;) > 0}
and A, (t) := {i [2n] (w, (t) xx) 0} denote the sets of point indices that have nonzero loss and which activate the jith neuron at iteration respectively. With
il(t, Owir
0,
x.) S 0, x,, > 0
1-1-1) yeater
then the GD update ruld for the neuron weights iteration 2 may be written as
(++1) = w/ (-11'n Σ 1 A )
(3)
In regard to the initialization of the network parameters, for convenience we assume each neuron's 's weight vector is drawn mutually i.i.d. uniform from the centered sphere with radius A > We remark that results analogous to the ones presented hold if the weights are instead initialized mutually i..dd
w (0) NO, o for sufficiently small o
2.3 Notation
For indices i,j E Z,21 we say ~ j iff (-1)= (-1). We often refer to data point or neuron by its index alone, e.g. "point i" refers to the i-th training point (x;, y:). For two iterations fo 41 with > to we define the following.
1. (to,tt)) == Eies, E 1(i A47) (n(()) the number of clean updates applied to the j-th neuron between iterations to and f1.
2. By (fo, (1) : Eies, Σh 1(i E ((t) ((F) the number of corrupt updates applied to the j-th neuron between iterations to and f1
3. G(lo, 41) := EjE(am) Gy 41) and B(o, 41) == Ej (1a, f1) are the total number of clean and corrupt updates applied to the entire network between iterations to and tj.
Although the derivative of ReLU clearly does not exist at zero, we follow the routine procedure of defining update rule that extends the gradient update this event.

---

4. t1) : := (tt B(t,, f1) is the total number of updates from all points applied to the entire network between iterations ig and ty.
We extend all these definitions to the case to by letting the empty sum be 0. Finally, use C 2 1 and c S to denote generic, positive constants.
3 Results
The main contributions of this work are Theorem 3.1 ize how the margin of the clean data drives three different training regimes: namely benign overfitting. non-benign (or harmful) overfitting and no-overfiting respectively. We primarily distinguish between the three aforementioned training outcomes based on conditions on the signal strength y E [o. 1] which controls the clean margin. Assuming the corrupt points are the minority in the training sample, then heuristically we might expect the following behavior as y varies: if ny >> 1, then the signal dominates the noise during training, corrupted points are never fitted and the network generalizes well. If ry < 1, then all points are eventually fitted based on their noise component and the network generalizes poorly. As such, we expect to observe benign overfitting when y is small but not too small: in this regime the network learns the signal, thus ensuring generalizes well, but corrupted points can still be fitted based on their noise component, thereby allowing training to zero loss.
Theorem and Theorem 3.8 which character-
With each theorem we provide here we give a sketch of its proof: full proofs are contained in the Supplementary Materials, which also contain supporting numerical simulations in Appendix Throughout this section, and in order to establish a common setting in which to observe variety of different behaviors, we make the following assumptions on the network and data hyperparameters.
Assumption 1. For sufficiently large constant C > 1, failure probability 5 E 1/2) and noise inner product bound p E (0, 1). let d 2 Cp Cp-22og((n/6 k S en, An S [z) and n S &, where depends on ni m, k and d.
log(n/8),
We remark that the condition d 2 Cp-2 log(n/8) ensures the noise components are nearly- orthogonal: in particular, maxiştt (n., ne)l S cp with high probability for some positive constant This near orthogonality condition on the noise terms is restrictive, but is a common assumption in the related works Frei al. (2022); Xu & Gu (2023). We note that the value of p required for each of our results to hold varies. Likewise, the optimal constants c and C' required in each case also vary and we will not concern ourselves with finding the tightest possible constants.
While there are differences the proofs of Theorem 3.1 3.6 and 3.8 generally fit the following outline.
1. Use concentration to show with high probability the training data nearly orthogonal and certain initialization pattern is satisfied.
2. Characterize the activation pattern early in training before any point achieves zero loss.
3. Bound the activations at iteration just before any training point achieves zero loss.
4. Based bounds the activations given iteration, derive iteration-independenn upper bound on the number of subsequent updates that can occur before convergence. At convergence all points either have zero loss or activate no neurons.
We emphasize that our proof techniques are significantly different from those used in Frei al. (002)); Xu & Gu (2023) due to the differences between the hinge and logistic loss. In particular, letting or (=)) denote the logistic loss, a key step in the proof of these prior works is showing at any iteration 2 0 that the ratio (yre xx)) /3/))// (n x1) is upper bounded by a constant for all pairs of points i, in the training sample. For the hinge loss this approach is not feasible: indeed, if at an iteration some points achieve zero loss while others have not then this ratio is unbounded.
3.1 Benign overfitting
The following theorem states conditions in particular on y under which the network simultaneously achieves asymptotically optimal test error and achieves zero loss on both the clean and corrupted data after a finite number of iterations. A detailed proof of this Theorem along with the associated lemmas is provided in Appendix C
5

---

Theorem 3.1. Let Assumption hhaiipttioooooddo and further assume 2 C'log(1/6), m C'oog(n66), p cy and C /lognn/))dddd S. en Then there exists sufficiently small step-size lt such that with probability at least 1 over the randomness of the dataset and network initialization the following hold.
1. The training process terminates at an iteration Tens S Cn.
2. For all i E [2n)] then {(Tend, x.) O.
3. The generalization error satisfies
P(sgu(J x)) + v) S exp (-cdh²).
Proof sketch. Recall the parameter bounds the inner products of the noise components of the training data. Specifically, the conditions on d given in Assumption [ with high probability. We also identify the following sets of neurons for E {-1,1}.
ensure max;41 (n,, nz) S -
Tp = { j [2m] (-1)² p. G,(0, p) (0,
-0, 1) + p) 2 2Aw
9₂ = LEr,, G, 1)(1 + B, () p) -1
These sets are useful in that neurons in p have predictable activation patterns during the early phase of training. Furthermore, if i is the index of a corrupted point which activates a neuron in Og at initialization, then this point will continue activating this neuron throughout the early phase of training. Concentration argument shows that r and θ are sufficiently significant subsets of [2m]]]] with bigh probability. In summary, for benign overfitting we say we have good initialization if i) maxezi (n,, ni)l S T-y. ii) for some small constant a E (0, 1) then [T 2 (1 aa)m for
p
p E (-1,1), and iii) for each i E Sy there exists j E [2m] such that (-1) = ys and E A
Lemma 3.2. Under the assumptions of Theorem 3.1 and assuming we have a good initialization, suppose at some iteration to the loss of every clean point is bounded above by E IR20, while the loss of every corrupted point is bounded above by E R2z. Then for all 2 to the total number of clean and corrupt updates which occur after to are upper bounded as follows.
bky
b anyy
G(lo, 1) S Cn
B(la, 1) S Cl
27
17
Because these upper bounds are independent of then we may conclude that training reaches a steady state after a finite number of iterations. particular, this means every point either has zero loss or activates no neurons. To prove the network achieves zero loss we need only show that every training point activates least one neuron after the last training update. This property is simple to prove for clean points: indeed, if i E ST then i activates every neuron in r after the first iteration. An inductive argument then shows i activates a neuron in every subsequent iteration. Showing that every corrupt point activates neuron at the end of training is not as simple, and requires more careful consideration of the training dynamics. To this end we say a neuron a carrier a training point
between iterations lg and t if E A for all E [fo, 4). In order to prove the network fits the corrupt data we need to show each corrupt point (x:, MR) has carrier neuron in O throughout training. If too many clean points activate such neuron, then it is possible it will eventually cease to carry any corrupt points and if corrupt point loses all of its carrier neurons then it cannot be fitted. We show this event cannot occur by studying the activation patterns of neurons in I == T1 U--
Lemma 3.3. Let the assumptions of Theorem 3.7 hold and suppose we have good initialization. Let j I and t >> 0 be an iteration such that no point achieves zero loss at or before this iteration.
For point i Sr, then i A!) iff i j. For point i Sp with i + j, E A iff A
The next lemma bounds the activations just before any points achieve zero loss.
Here we use [2m]+1 to refer to the even indices, or those neurons with positive output weights, while [2m] -1 the odd indices, those neurons with negative output weights.

---

Lemma 3.4. Under the assumptions of Theorem 3.1 and assuming we have good initialization, before any point achieves zero loss where the following
there is an iteration Ti I (mo[1-[1+pinnE]]] hold for a constant that varies from line to line.
C
1. For all E (-1,1), E ETp. in and E Sr, then (w) (1) xi) 2 cm
2. For all E (-1,1}, E Pp. it 3. and E ST, then (w) xi) -crym
(Th)
3. For all i E ST, then x.), Sc
Due to the fact that clean points are the majority and all of them push the network in the same signal direction, then immediately after Ti the loss of clean points small and clean points activate all neurons in the relevant r strongly. Furthermore, once the loss of a clean point is small it stays small. In subsequent iterations, the number of corrupt updates since Ti is also small, approximately Ceny/(n( + p). then each clean point will activate on all but an proportion of neurons in the relevant pp As the hinge loss switches off the updates from a point once it reaches zero loss, eventually clean points do not participate in every iteration. Furthermore, when they do participate their updates are spread over large proportion of the neurons. This ensures that most neurons in Op cannot receive too many clean updates in isolation, thereby ensuring carrier neurons continue to carry corrupted points throughout training.
Lastly, the generalization result follows from the near orthogonality of the noise components of both the training and test data. Indeed, using the same concentration bound, test point satisfies the same inner product noise condition as the training data with high probability.
Lemma 3.5. Consider a test label y E {-1,1} and point x yVTV -1- where
Uniform( Sd11 n spantv] ") is mutually i..dd from the training sample. Assume the conditions of Theorem 3.1 hold and that we have good initialization. In addition. suppose that (n, n:)l < +
for all 2m]. then yf (Tend, x) O.
3.2 Non-benign overfitting
The next theorem states a harmful overfitting result: for sufficiently small y the network achieves again zero loss on both the clean and corrupt data after a finite number of iterations, but the probability of misclassification is bounded from below by a constant. A detailed proof of this Theorem along with the associated lemmas is provided in Appendix D
Theorem 3.6. Let Assumption
I hold and further assume m 2 Clog(n/6),, S cn- < 1/m2m) and 7 S Vig. Then with probability at least ô over the randomness of the dataset and network initialization the following hold.
1. The training process terminates at iteration Tond S Cn.
2. For all e [2n] then {(Tend x.) = O.
3. The generalization error satisfies
1 (fsgn(((Tama) x)) # +V) 8
We remark that the above result holds for n > and any k. Indeed, in this regime the noise components dominate the training dynamics and we therefore expect the performance of the network on test points to be close to random. We re-emphasize that, unlike in the data model used by |Frii et al. (2022) and Xu & Gu (2023), there does exist a classifier with perfect generalization error for arbitrarily small 7. The significance of Theorem 3.6 is that under the data model considered GD results in suboptimal classifier.
Proof sketch. Similar to the proof of Theorem 3.1 the context of non-benign overfitting we say the initialization is "good" if max (n,, ni)
and if each point in the training sample

---

activates a neuron of the same sign. Under the conditions of Theorem 3.6 can be shown that good initialization in this context happens with high probability.
Lemma 3.7. In addition to the conditions of Theorem 3.6 suppose we have a good initialization and that for some iteration to then E(la, x.) S a a.for all i [2n). Then T(lo: 1) S Coa
As for the benign overfitting case, we need to show that each training point activates a neuron after the last training iteration. Under the assumptions on ? it can be shown that the loss of point decreases during every iteration it participates in, regardless of the status and activations of other points in the training sample. All that remains is to lower bound the generalization error. To this end observe for test point (x, y) that
2m
([[(Tend: x) f(Tend, -x)) Σ y Ey(-)((w) (w) (Tas) x).
the right-hand-side this equality is negative we can conclude that either x or -x is misclassified. That this event is true with probability lower bounded by constant in turn follows by appropriately upper bounding the norm of the network weights in the signal subspace, as well as lower bounding the norm of the network weights in the noise subspace.
3.3 No-overfitting
The following theorem illustrates that for y larger than the upper bound required for benign overfitting. then after convergence, which occurs in finite number of iterations, only the clean points achieve zero loss. By contrast, the corrupt points cease to activate any neurons and thus zeroed by the network. The network also achieves asymptotically optimal test error. A detailed proof of this theorem along with the associated lemmas is provided in Appendix
Theorem 3.8. Let Assumption I hold and further assume m 2 2 Clog (%)) P S ey and en-1 5 S ck- Then there exists a sufficiently small step-size nj such that with probability at least 1 - 8 over the randomness of the dataset and network initialization we have the following.
1. The training process terminates at an iteration Tens S Cn.
2. For all E Sr then E(Tends x.) while ((Tend: x;) = 1 for all i E Sp.
3. The generalization error satisfies
Pfsgn(f x)) + S exp (-cd?2).
We remark that the upper bound on allows us to re-deploy the same proof technique used to prove convergence in the benign overfitting case, thereby ensuring the training process converges within finite number of iterations. We conjecture this upper bound can be relaxed but leave such an analysis future work.
Proof sketch. In the context of no-overfitting we identify "good" initialization for which maxi41 (n; ni)l S f and I' = 1- UT = [2m]. Under the conditions of Theorem 3.8 it can be shown a good initialization in this context occurs with high probability, furthermore the resulting activation pattern early during training is simple characterize.
Lemma 3.9. Suppose that the conditions of Theorem holl and that we have a good initialization. Consider an arbitrary j [2m] and iteration < S occurring before a point has achieved zero loss. Then i E A iff i~ j.
Next we bound the activations of the training points just before To, the iteration at which any training points first achieve zero loss. In the following we use Fi, F2 and F3 as placeholders for expressions depending on the data and model parameters. Here, for the sake of conveying the ideas the proof we do not write them in full and refer the reader to Supplementary Material.

---

Lemma 3.10. Suppose that the conditions of Theorem 3.8 hold and that we have good initialization. then there is an iteration Ti before any point achieves zero loss such that
(w) (T.) xx) v Fi
if Sp,in ~
m
(w) (Ti)
xx)) z
F2
if Sp, rj.
m
(w) (T) x,) - m
F3 j.
Next we seek to ensure the activation patterns remain mostly fixed: in particular, we show E A if i ST and ~ j. while i & A if i
Lemma 3.11. Suppose that the conditions of Theorem 3.8 hold and that we have good initialization. In addition, for a. b E R assume there is a time to such that E(to, x,) S a for all E Sr and (w (ta) xx)) S b for all E Sp and i ~ j. If vic E Sr, i implies i E A and of j implies i A for all t satisfying to S < 1, then
a (y,, S 7) m
Ck
(
ΣG jrus
C(a + mb) 7
As before, this update bound is finite and iteration- independent, therefore GD converges provided the assumptions on the activation patterns are not violated. Furthermore, these activation patterns do hold, then every clean point activates neuron and no corrupt point activates a neuron of the same label sign. Therefore, under the assumption on the activation pattern, at convergence clean points achieve zero loss while corrupt points have non-zero loss, i.e., they activate no neurons. It therefore suffices to prove the condition on the activation pattern, which we show holds long as
Fs 772
F2 m
Fi F1+1-
F2 F2) 2 n ()
min
2 Ckly + p)n
m
As C' sufficiently small. With p S cn en- we show suffices that 7 < ck Finally, the generalization result follows in a fashion almost identical to that used for Lemma 3.5
does not depend on the parameters, we can ensure this condition holds by letting Ck(y + p) be
3.4 Comparison of results
We compare the differing regimes of our results side-by-side with those of Frei et (2022)
) Xu &
Gu (2023) in Table We note that comparisons are not like-for-like as Frei et al. (2022) consider smooth, leaky ReLU and logistic loss,XXu & Gu (2023) a generalized family of activation functions, which includes ReLU, and logistic loss, and this paper ReLU and hinge loss. Furthermore, in addition to differences in the noise distribution discussed in Section 2.1 Frei et al.) (2022); Xu & Gu (2023) assume data model where the norm of each data point is approximately proportional to vd. We therefore re-scale their results in order to make comparison with this work in which all data points have unit norm.
Taken together these results suggest, at least under the type of data model considered, that benign overfitting occurs for signal strengths proportional to between roughly 1/Vdn dn and 1/n. Furthermore, results also suggest that above approximately 1/n one might expect to transition to overfitting, while below approximately 1/Vnd transition to harmful overfitting. We provide preliminary supporting experiments in the Supplementary Material. We again remark that the latter non-trivial our setting as for all 7 0 the classifier (xx) sign((v, ((v,)) always has perfect accuracy.
Frei et al. (202 show overfitting results smaller 7, but assume a data model where benign overfitting possible only when /(v//dd) is asymptotically zero, implicitly showing non- non-benign overfitting.

---

Table I: across all results & S en while C'2² log(n/6) for (Frei al. 2022 and Theorem 3.1
Xu & Gu
2023
Frei et al. (2022)
Xu & Gu (023))
Theorem 3.1
Theorem 3.6
Theorem 3.8
n 2 C.
log 8
log
log
log
70
2 C.
log
log
log
1
7Sc
Y
Vnd
k:
log ma) nd
log("))
1
726 C.
0
Vnd
n
Result
Benign
Benign
Benign
Non-benign
No-overfit
4 Conclusion
Developing theoretical description of benign overfitting in neural networks is highly nascent area, with mathematical results available only for very limited data models. Furthermore, the conditions describing the transitions between overfitting versus non-overfitting and benign versus non-benign even in these simplified settings are yet to fully characterized. The goal of this work was to address this issue well explore the impact of using the hinge loss. In particular, and admittedly for simple data model, we prove three different training outcomes, corresponding to non-benign overfitting, benign overfitting and no-overfitting, based on conditions the clean data. Our analysis also differs significantly from prior works due to the fact the ratio loss between different training points can be unbounded and the implicit bias of using hinge loss versus exponentially tailed loss is poorly understood.
the margin of
Limitations and future work: the key limitation of this work is the restrictiveness of the data model. particular, as in prior and related works we use a cecaroorthoonal noise model and assume rank one signal, also place additional conditions generalizing the signal and noise model as well as improving the bounds required for our results to hold, believe the following themes are important orthogonal noise condition, second exploring data models beyond those which are linearly separable, third investigating the role and impact of depth.
the noise distribution. In addition to
for future research: first relaxing the near
Acknowledgments
EG, WS and DN were partially supported by NSF DMS 2011140 140 and NSF DMS 2108479. EG was also partially supported by NSF DGE 2034835.
10

---

References
Ben Adlam and Jeffrey Pennington. The neural tangent kernel in high dimensions: Triple descent and multi-scale theory of generalization. In International Conference Machine Learning, 2020.
Hilal Asi and John C. Duchi. Stochastic (approximate) proximal point methods: Convergence, optimality, and adaptivity. SIAM Journal on Optimization, 29(3):257--2990, 2019. doi: 10.1137/ 18M1230323. URL https: htop:s://doia wtt.:oooorr//oo 1 2217//10M2233333
Keith Ball. An elementary introduction to modern convex geometry. 1997.
Rémi Bardenet and Odalric-Ambrym Maillard, Concentration inequalities for sampling without replacement. 2015.
Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 1 1177448)300633-0077, 2020. doi: 10. (9007///a...907338887
URL https:/ htwp:/wwpaett....
1907378117
Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting perfect fitting? Risk bounds for classification and regression rules that interpolate. In S. Bengio, H. Wal- lach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018a. URL https::/ wttp://ssss.nuurs.cccccoaaoa (111:222322777777277777777722222
Files/papee:/2018/
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need understand kernel learning. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning. volume 80 of Proceedings of Machine Learning Research,
pp. 541- PMLR, 10-15 Jul 2018b. URL https:tts: //proce ings ings wwa.angmm........... be lilkin188 1a.88.htttt html
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learnigg practice and the classical varinnar trade-off. Proceedings of the National Academy of Sciences, 116632):15849-1558 2019.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. SGD learns over- parameterized networks that provably generalize linearly separable data. In International Conference on Learning Representations, 2018. URL hwt.::ttt:///t httt::::/openreviii ew net./ feree/ooruie forum?
Id=rJ33wwxRb
Yuan Cao, Quanquan Gu, and Mikhail Belkin. Risk bounds for paramettaeeerrized max- imum margin classification on sub-gaussian mixtures. In M. Ranzato, A. Beygelz- imer, 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
crtp sacpeer_fiiesppppreee witees/ppppe/e221/// File/ File://eeaaaer2227cc///eeffeoo22 Pawp:eeppeecc--app.ppppp
Yuan Cao, Zixiang Chen, Misha Belkin, and Quanquan Gu. Benign overfitting in two-layer convo- lutional neural networks. Advances in neural information processing systems, 35:25237-25250, 2022.
Niladri Chatterji and Philip M. Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. Journal of Machine Learning Research, 22(129): 2021. URL
http::/ http://w....ggpppppeeeeeeeeeeeee vv22/20 974.html
Niladri S. Chatterji and Philip M. Long. Foolish crowds support benign overfitting. Journal of wtt.ttt::/ http:/tttp/..mm.. http:p///hhil...rgg/aaarrsrs///s
Machine Learning Research, 23 2022. URL
21 htm
Spencer Frei, Niladri S Chatterji, and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. Conference on Learning Theory, pp. 2668-2703. PMLR, 2022.

---

Spencer Frei, Gal Vardi, Peter 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.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 1173-32283 PMLR, 12-15 Jul 2023, URL.
.gg.mms....... r www.m.....rrrsr.ee prwss / v1 95/ f rei 23a .html
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. doi: 10.1214/21-0022133 URL/ttpss: //doi. org/ 10. 1214/21-A0020
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and general- ization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018. URL
www.. cttpcc//ppppp/ee..c _ilee__ie//__e Paperra-appprppp..
Ziwei and Matus Telgarsky. Directional convergence and alignment in deep learning. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN
Ziwei Ji, Miroslav Dudík, Robert E. Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 2109 2136. PMLR. 09-12 Jul 2020. URL ltttps: https://proceddng. mlr
press/v125 110//1120002 20a. htmm]
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 J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. LRL
n wow.mmidomiiiieee ForoummiidyyyoTaaDea.
Guy Kornowski, Gilad Yehudai, and Ohad Shamir. From tempered benign overfitting in relu neural networks, 2023.
Yiwen Kou, Zixiang Chen, Yuanzhou Chen, and Quanquan Gu. Benign overfitting for two-layer relu networks, 2023.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "Ridgeless" regression can gen- eralize. The Annals of Statistics, 48(3):1329 1347, 2020. doi: 10.1214/19-A0S1844) URL
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the multiple descent of minimum-nonn norm interpolants and restricted lower isometry of kernels. In Annual Conference Computational Learning Theory, 2019.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia. April 26-30, 2020. OpenReview.net, 2020. htth:tt::/// peattps://openreviie net forum?in SJeLIgBKPS
Neil Rohit Mallinar, James B Simon, Amirhesam Abedsoltan, Parthe Pandit, Misha Belkin, and Preetum Nakkiran. Benign, tempered, catastrophic: Toward refined taxonomy of overfitting. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL httpsttt:: /opneevieeeeeeeee net forum?
1d=5oS20NUC.EN
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, 2019.
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. doi: 10. 10.1109/SAATT22222294441
12

---

Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparameterized regimes: Does the loss function matter? J. Mach. Learn. Res., 22(1), Jan 2021. ISSN 1532-4435.
S. Concise formulas for the area and volume of a hyperspherical cap. Asian Journal of Mathematics and Statistics, 4, 01 2011. doi: 10.3923/ajms.20) 1.66.70..
Ohad Shamir.
The implicit bias of benign overfitting. In Po-Ling Loh and Maxim Raginsky (eds.). Proceedings of Thirty Fifth Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 448-478 PMLR, 02-05 Jul 2022. URL/https://prooeeete
mlr
press/v178 shami wwthaamii2222. r22a html
Gang Wang, Georgios Giannakis, and Jie Chen. Learning ReLU networks on linearly separable data: Algorithm, optimality, and generalization. IEEE Transactions on Signal Processing, 67(9): 2357-2370, 2019. doi: 10.1109/TSP.2119299000 2904921..
Guillaume Wang, Konstantin Donhauser, and Fanny Yang. Tight bounds for minimum norm interpolation of noisy data. In International Conference on Artificial Intelligence and Statistics, 2021a.
Ke Wang. Vidya Muthukumar, and Christos Thrampoulidis. Benign overfitting in mul- ticlass classification: All roads lead interpolation. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural In- formation Processing Systems, volume 34, pp- 24164 24179. Curran Associates, Inc., 2021b. URL ht http:: http::::s///pprreeeeneesee www.sps..r.appppppppepepes 2tle:/aaaeee//2222200aafffffffee wtwpee/eeepppeeeeeeeeeeeeeeeeeee ft..ss/ppppee//21111
Denny Wu and Ji Xu. On the optimal weighted l regularization in overparameterized linear regression. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.). Ad- vances in Neural Information Processing Systems, volume 33, pp. 10112-10122 Curran Asso- ciates, Inc., 2020. URL UtL.tttpss//prrreeenss...rrrrrre cappper fi
2200F111226622233312222222422222 Paperr.
Xingyu Xu and Yuantao Gu. Benign overfitting of non-smooth neural networks beyond lazy training. In Francisco Ruiz, Jennifer Dy, and Jan- Willel van de Meent (eds.). Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 1 11094 11117. PMLR, 25-27 Apr 2023. URL https //proceedings.. mir pttpp/v206
/ xu23k. html
Qiuling Yang. Alireza Sadeghi, Gang Wang, and Jian Sun. Learning two-layer ReLU networks is nearly easy as learning linear classifiers on separable data. IEEE Transactions on Signal Processing, 69:4416-4427, 2021. doi: 10.1 109/TSPP2021.3399999
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.
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Benign overfit- ting of constant-stepp stepsize SGD for linear regression. Mikhail Belkin and Samory Kpotufe (eds.), Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Pro- ceedings of Machine Learning Research, pp. 4633 4635. PMLR, 15-19 Aug 2021. URL
htttps:/pproceediee mlr. pwwss/vvssi 34/ 2ou21a.......o html
13

---

Appendix A Properties of the data and network at initialization
For each of our results to hold we require certain properties on both the network weights and training sample to hold at initialization. Here we bound the probabilities of these events in turn. Later, for each specific setting we combine the relevant conditions using the union bound.
First, and in order to prove convergence, we require the noise components of the training sample to be approximately orthogonal one another.
Lemma A.1. Let p, (0, 1). Civen sequence (n.)²= mutually i.i.d. random vectors with
n. U(S n span +) for all i [2n], then assuming d 2 max {3,3) In 2n
0
P
{l ne)l 03 2 21-8. 8.
Proof. Consider two pairs of mutually i..d. random vectors n, ~ U(Sá-1 n span(v) !)
and
u, u' ~ U(Sd-2), observe
nn. d (u, u').
Due to the fact that u and u' are independent as well as the rotational invariance U (Sd-2) follows that
(u, u') d uu, e1):
where e1 == [1, 0..00... Let Cap(e1. p) = z E gd-2 (e1, 2) 2 p} denote the spherical cap of gd-2 centered on 0₁. As d 2 then from Ball [197)]] Lemma 2.2] it follows that
Puu E Cap(er, S exp (-d4)
(d 1)p² S exp
dp²
P([(,, n'>l 2 p)
3
Applying the union bound
(1 ne)l S p}
(Kne ne), 2 p}
i.E (ME(2n]iiph
2n 2P (KKD,,
2 p)
dp2
2n exp
3
Setting 8 2 2n exp
dd"
and rearranging we arrive at the result claimed.
In addition to requiring the approximate orthogonality property on the training data, our approach also requires large proportion of the neurons initialization satisfy particular conditions in regard to the number of clean versus corrupt activations. To this end, we introduce the following terms where p E 1).
Let I = (j (-1y=p, -) ()(,
2xxz) denote the set of neurons with output weight (-1)² which have more clean points activating them than corrupt ones initialization. We will show that these sets of neurons have a predictable behavior early during training before any clean points achieve zero loss. We further let
r T=r,rr_.
Oe : (j G,(0,1) + p) B, 1) <1- p) C Tp- For our benign overfitting result we will show that neurons in this subset are able to carry corrupt points throughout training, eventually, at least in the overfitting setting, enabling them to achieve zero loss. We further let @ = θ U
First we show D accounts for significant proportion of neurons. To this end we first provide the following result.
14

---

Lemma A.2. Define μ y== 2k and assume &. (0,1) satisfies & > P.. Given an arbitrary neuron Wj U( we say that collection of training points (eoo) iff both (0,0 Z 1 and (0, < (0, 1) with probability at least 1 - over the randomness of the neuron. There exist positive constants C, e such that i := exp( exp(-cn(K - 1²)) and n 2 C then with probability at least
n+k
1- 6 the training sample is (e, -))oood.
Proof. First we establish certain pieces of notation specific to what follows: we say a point x is positive iff (x, v) > O and is negative iff (x. v) < O. We use S* and S to denote these sets of points respectively. Note by construction, mutually i.i.d. As here we only ever consider one neuron and the activations of the training sample on this neuron initialization, we also drop both the subscript the counting functions. We also use + superseripts to denote the subsets corresponding to activations from positive and negative points respectively: as examples T is used as shorthand for the total number of activations, B is the number corrupt positive activations and G- is the number of clean negative activations.
[ clean and corrupt points of the same sign are
well as the argument parentheses on
First by the symmetry of the distribution of w, P((w, v) > 0) = -(( v) < 0) = 1.2 As a result
P((B < kT) (T)n
2 P( < R7 () (w, v) > 0)
+ + < kT) n (T 0) (w, v) < 0).
As the analysis and results derived under either condition will prove identical under reversal of the signs involved, without loss of generality we let (w, v) > 0. Using the union bound
P((B < KT) n (T > 0) I (w, v) > 0) 2 1 P(T = 0 | (w, v) > 0) P(B 2 KT | (w, > 0), therefore it suffices to upper bound the two probabilities on the right- right-hand-sidd hand-side.
Observe if (w, v) > 0 then for x E St we have P((x, w)) > 1/2 and for x E S we have P((x w) < 1/2. By the mutual independence of the preactivations ((x, wy)) then P(T 0 (w, v) > 0) S (1/2)". Consider now a slightly different data model, in which a training sample consists of - k clean positive points and 2k corrupt positive points. Abusing notation, we let C denote the event that we are instead drawing our training sample in this manner and also that (w, v) > 0. In this setting T+ T and furthermore the event B kT' is equivalent to B+ < kT* Again, as the preactivations are mutually independent the number of positive activations can be lower bounded using a binomial distribution with probability 1/2. Applying a Chernoff bound it follows that
P
r
n + k
()
< exp
72 + k.
4
16
Furthermore, observe sampling positive points which activate w, is equivalent to uniformly sampling without replacement T points from St. Let Ze- = 1 iff the ε-th element sampled from S is coruupt and is 0 otherwise. Using variant of Hoeffding's 's bound for sampling without replacement (see for example Proposition 1.2 of Bardenct & Maillard (2015)
T
P P(B 2 x (c) = IP
Σ
Ze 4 22 1
S Sexp (-2I+ - 11)2)
T+
Therefore
P(B KT vw > 0) (B+ xT (c)
(B+
n k .5) + P
n + k
<P B+ 2 KT
T 2
T <
5)
4
4
(n ))( - -1)²
2exp
Combining these results it follows that
P(B < kT) (T' 0) (w, v) > 0) 2 1 1 PP =0 | (w. v) > 0) - P(B 2 KT
(w.v) > 0)
(n + k)( - -1)2
2 1 1- 1-3exp
16
15

---

Therefore, there exist constants C, c > 0 such that if n 2 C' then
IP((B < kT) n (T > 0) (w, v) > 0) -
Note if instead we condition on the event (x, w) < then swapping the roles of the negative and positive points in the argument above gives the same outcome. As a result
P(B < (T) 0)) 2
Pw((B 2 kT) U (T' = 0)) > }} the set of training samples which are not (c, k)-good. Note here that the subscript wo indicates randomness
For convenience let X == (x))²= denote the training sample and X == =X
the neuron alone, furthermore by construction
P ( 2 UT) 0) X E X 26
Furthermore, as
8 (T 0)) 2 P ( then it follows that P (X E X < - As result conclude that the probability of drawing (e, -good training sample is at least
Xx,w:
Based Lemma A.2 the following lemma bounds the probability that the cardinality of Te is large. We note that the result presented here on non-overfitting requires [T = m while the result on benign overfitting that [T, pl (1 a)) for some small constant a: E (0, 1).
Lemma A.3. Suppose n 2 15k, Au S n " and 7j 2 4p. Then there exist positive constants C, > 0 such that if n 2 C the following are true.
1. IP (IT m)
m expe(-cnn)
2. With a E (0, 1) then
P (Ir 2 (1 - a)m) 2 1 exp(-cn). 21-exp(-or).
Proof. Again as here we only ever consider the activations at initialization, we write 7, 1) as T,, (0, 1) as G2 and (0, 1) By. Let p E 1-1, and consider arbitrary neuron j such that (-1) p. by definition if
2
G₃(7 - p) - [3 +
we may conclude j e rp- Rearranging this expression, equivalently j r
B, + A 7 PT. 7 27
As Au S I-6 then membership to r2 is guaranteed as long as T, 2 1 and B, S T= Note
4y
by the assumptions of the lemma μ ntk S
8 and T-P 3 Conditioning on the event we 4n 2
draw (c, 3 ]good training sample then the probability that тр is at most by Lemma A.2 Furthermore, with the training sample fixed the activations of each neuron are mutually independent. Let X = (x denote the draw of the training sample and X [X Pw > <T) U (T 0)) S } the set of (e, k)ooo training samples. In what follows we assume K 3/16 and let
16
= exp(-cn) where e < 16-2 is a sufficiently small positive constant, then by Lemma A.2 there
exist constants C, c such that n 2
8 21 1211-21- exp (-cn).
P P(X Xen) 21
The first result follows by applying the union bound,
P ((T = m) 2 P ([r, m X Xxx) P(x e Xcx)
2 (1 - m mexp(-en)) (1 exp (-cn))
2 1 - exp(-cn).
16

---

For the second result, let a' E (0, 1) denote the smallest scalar satisfying both < a' and a'm [m]. Observe
P (( pl < (1 - (1)mm X E Xe,n) = (33 c
& VjEJ X Xx,x)
calm
a/m
ce
As a is a constant, there exists positive constants C, c such that if n 2 C then
a = exp(-cm + + lo)g///))++)) exp(-on).
Therefore
P(T 21 (1-))m())mmm 2 P( (1 a.m X Xe,x) P(X E Xc,k)
P
2 (1 exp (-cmna')) (1 exp (-mn)
2 1 - exp(-cn)
as claimed.
We now turn our attention to establishing the conditions required at initialization on the corrupt points for the result on benign overfitting. To this end, in the following two lemmas we introduce the notion of e-fine training sample and lower bound the probability of drawing one. Then, by conditioning on drawing such a training sample, we lower bound the cardinality of a set of neurons, which we denote A, which satisfy a property related θ.
5m and y 2 5p. We say training sample is e-fine if for random neuron Wj the inequality G₃ < 10 To nn holds with probability at least There exist constants C,e> 0 such that in C then with probability at least c exp (-cn) the training sample is e-fine.
Lemma A.4. Assume 7 S 4.
Proof. This lemma is analogous to Lemma A.2 and to this end we reuse much of the same notation. In particular, recall point x is positive iff (x, v) > O and is negative iff (x, v) < 0. Note all points with the same sign are mutually i.i.d. by construction. We use S and S denote these sets of positive and negative points respectively. As here we only consider single random neuron w, and the activations at intiillization of the training sample on it, we also drop both the subscript j as well as the argument parentheses on the counting functions. We also use + superscripts to denote the subsets corresponding to activations from clean and corrupt points. As indicative examples of our notation going forward, we denote w, w, T is used as shorthand for the total number of activations while B and G are the number of corrupt positive and clean negative activations respectively.
By the symmetry of the distribution of w, IP((W v) > 0) P((w, v) 0) 1.4. As result
G
4
5
5 (, v) > 0
IP
T
+
= P
G
<
T
+
10
10
8
1 P G
4
+ 2
T
n (w, v) <0
10
g
As the analysis and results derived under either condition will prove identical under reversal of the signs involved, without loss of generality let (w, v) > 0. Consider this problem for a slightly different data model, in which a training sample consists of 2(n - k) clean, positive points and negative points. Abusing notation, we let ( denote the event that we are instead drawing training sample in this manner and also that (w, v) > O. Clearly
PP
4 T+ GG
5 (w. v) > 20 SP G
SP(G
G+
4 T 10
10
In this setting, only positive points activate w, therefore all points which activate are identically distributed. As result, sampling positive points which activate w is equivalent to uniformly sampling without replacement + points from S+. Let Ze 1 if the f-th element sampled from S+ is clean
17

---

and is O otherwise. Define 2(n-k) 2n F then again using variant of Hoeffding's 's bound for sampling
without replacement (Bardenet Maillard 2015 (rroposiiin 1.2] and as long as To + ST p., we have
P
G
2
4 T
+ 8
1 5 = P
1 2
G+
+
5n
15)
10
T
10
8T
T
4
5n
= P
7 1=1
Z1
2
10
+
87
1 15
(4)
[ 10
5n
2
S exp
-27
87
We proceed lower and upper bound T*, to this end we first lower and upper bound the probability
that positive point activates w conditioned on the event (w, v) >> O. Let x = /TV + v1 yn be a fixed positive point, then by the symmetry of the distribution of w
P x(w,x) > (w. v) > 0) = P (V7(w, v) + VI- n) > 0|(w, v) <0)
2 P ((W,, n) > 0)
2
For convenience, let E1 denote the event (w, x) 0, E2 the event (w. v) > 0 and E3 the event
(ww, v)1 S ip for some arbitrary ip E (0, 1). For the upper bound observe
P x(w.x) x)) > 0 vw > 0) P (Ei Eg)
E2, P PE E3 Ba) S PP (E) Es, + - ( 12)).
(E)
Let Cap(n, vp= = (z E gd-1; (n.z) > ( denote the spherical cap of gd-1 centered on n. As d 2 3 and w ~ U then from Ball 1997) |997)| Lemma 2.2] it follows that
dp²
P(K(w, u\| 2 vp) IP(w E Cap(u, v)) < exp
Furthermore
P ((E Eg, Es) (W + V (w, n) > (w, 0, (w, S
< P
(w.n) n)
7 4
1 1
+ p
(ww,n\/
<
7 1p
2
d=/p2
< exp
3(1 7)
Therefore, and noting under the assumptions of the lemma that
I-7 I 1
dp²
dryp?
P x(w, > (W,,, v) > 0) < 1 exp
exp
3
2
3(1 7)
dp²
4dy²
< 1 exp
exp
3n
Set x² 3/n then
4
P ((W,x) > 0/[w, v) > 0) < 1+ exp (-Vn)
exp
vn
Letting E (0, 1/2) be an arbitrary constant, then as long n 2 max (In? (2) 16
(1-))
1 + 2
P P(wwx) x) > (/ v) 0) < 2
18

---

In order to take advantage of concentration the upper bound on T must be greater than E[T*). On the other hand, if the upper bound is too large then the condition +
p will be compromised.
10
As <
100
Σ
1(i E ( -
96 n
REST
then this condition is not compromised. Setting w = 18
if n 2 16In -2 (17) =: C' then
= (2n k)P(i E A S n2
96
and therefore, applying a Chernoff bound,
T
99
71
(6) 2 -1eppp
exp 19900
96
Under the same conditions, to lower bound T we again apply a Chernoff, which gives
T 2(n
k)
5) 2 exp (- 2(n 2(n - k)
(- 16
Therefore, there exists a small positive constant c and a large constant positive constant such that C' then
2
T
99
<)
exp (-cn).
96
In combination with the bound in from this result it follows that there also exists sufficiently small constant >> O such that
4
2nn k)
99
G
n 6,
S exp(-on).
96
As result, there exist positive constants C, e such that if n C' then
4
5
P
G
T
+
(w, v) 0)
10
8
5
5)
P
G+
T
+
10
8
4 T
5
2(n - k)
99
2(n
k)
99
P
G
5,
T
P
T
|
10
8"
4
96
96
4
5
2(n
k)
99
2(n k))
99
+P
G+
T
T
or
T
P
T or T
5
10
8
4
96
4
96
5
2(n -
k)
99
2
k)
99
<P
G+
T
5,
<
<
P
T
5
10
8
4
96
96
2(n - k)
99
+P
T
T
1 15)
96
< exp(_cnn.
Note if instead (x, v) < 0, then swapping the roles of the negative and positive points in the argument outlined above gives the same result. Therefore, under the assumptions of the lemma,
TP p
4
5
T
2 exp (-en).
Let X (x,)²n denote the training sample and X = (X : P.. (G 2 TO + > }} the set of training samples which are not e-fine. Note the subscript above indicates randomness over the neuron w alone. Clearly by construction
P
G
T
T+
n
x E 2E.
10
8
19

---

Furthermore,
exp(-on) 2 P
G
4
T
n
2
P
Gz
10 T+ s" x xelxxxx)) P(XEXX)
10
8
S c- exp (-en). As a result we conclude that there exist positive constants C, e such that if n 2 then the probability of drawing an e-fine training sample least
then it follows that P (X E x.)
1 e exp (-cn).
Lemma A.5. Assume 7 S 5n 7 2 5p and ler A = {j [2m] : G3 TT + 2, There exists
positive constants such that for any d (0, 1) if n2 2 C Colg(11/)) (166 then
P(A > 1.75m) 2 6.
Proof. To bound the size of A with high probability follow similar approach used bound the size of T with high probability. As 7 S 5n
4
and p I 3. then observe
7 7-
27 10 T
2y
Therefore, J < + nn. Conditioned on the event that the training sample is e-fine for exp(-cn) for some sufficiently small constant c, then with the data fixed the preactivations of the data on each neuron are mutually independent and identically distributed by construction. As such, in this setting the events (G, _107 T3 + ) are also mutually independent. Let (x:) 2n denote the training sample and X the set of 6-fine training samples, then
IP (IAI < 1.75m
X X.) = P C [2mlps | = 0.25m
m
0.25m
0.25m
(4ce)0.25m
(4ce) 0.25m
It follows that there exists sufficiently small positive constant such that
4ce = exp(-cn + + log(4)) S exp(-en).
Therefore, using Lemma A.4 there exists a sufficiently small positive constant e such that
P(A > 1.75m)
2 PP[A| 1.75m 2 exp( cc0mmmmm))) - exp(-cn))
E e XX) e X.)
2 exp(-cn))
from which the result claimed follows.
Lemma A.6. Assume 7 7 2 5p and || > 0.99m for p E {-1, 13. There exists positive constant such that for any d E (0, 1), if n 2 Cllo(()) { and m 2 C log (.), then with probability
least - 8 for all i Sp there exists a j Gg for which E e
Proof. For convenience here we use Ty. Gj and B, for (0, 1), G, 1) and By 1) respectively. For neuron to be in O it must satisfy the following condition,
G,(7 + p) By p) <
p.
Adding and subtracting Ty(7 - pp) to the left-hand-side gives
G,2y T, (- - p) < 1 - 1
Rearranging this inequality it follows that the conditions jE TT, and Gj < 2 उ are sufficient to conclude j E Op. Let A := {j E [2m] G; < the desired result it suffices to lower bound the probability that for each corrupt point (x;, ys the intersection between the set of neurons which x, activates, the set of neurons Ty, and the set of neurons A is nonempty.
2- T- + 27 Therefore, in order to prove
20

---

By a Chernoff bound there exists small constant > 0 such that with probability at least 1 exp(-cm) a fixed training point activated by at least 1/3 of the neurons of each sign. Therefore, using the union bound, every corrupt training point is activated by at least m/3 of the neurons with matching sign with probability at least 2k exp(-cm)) Conditioning on this event, then under the assumption IT, p > 0.99m for p E {-1,1}, each corrupt point (x, Vs) activates at least 97 300 300 neurons in n. Therefore, if for instance, |A| > 1.75m, we can conclude for each (x,, y4) with
i SF that there cxists j E Gy such that E A0 Therefore, under the conditions of the lemma, using the union bound and Lemmas A.5 and A.3 we can upper bound the failure probability of this as
2k expl (-cm) + exp(-cn).
Therefore, for 8 E (0, 1) there exists a positive constant C' such that if n 2 C'log(3) and m 2 C'log (#) then the probability that for E SF there exists a j E Oy such that E A (0) least 1 1-
The final lemma we provide here states, under mild conditions on the network width, that with high probability every point the training sample activates a neuron whose output weight matches its label in sign. We use this to prove the result on non- non-benign overfitting, detailed in Section D
Lemma A.7. Let E (0, 1), if m logz( (2) then the probability that for all i E [2n] there exists j E [2m] such that (-1)² y/ and A (0) is at least
Proof. Observe by the rotational symmetry of the weight distribution that for any j [2m]
P((w,,x.) x.) < 0) = P((w), e1) < <) = 1/2.
By construction, for each element in the training sample (x,, W1 ) there are neurons whose output weight has the same sign. As the preactivations of x; with each neuron are mutually independent from one another, then using the union bound it follows that
2n
2n = P (U E [2m] (-1)² = ys, i !
n (3j E [2m]: : (-1) = yr, i A
2 1 - 2n (P((W,, x,) < 0))
= 1 - 2n²2
Setting 8 2 2n2 and rearranging we arrive the stated result.
Appendix B Supporting Lemmas
B.1 Bounds on activations and preactivations
For any pair of iterations I, to satisfying / lo. unrolling the GD update rule (3) gives
2n Tey(lo, Oyexe-
(A) w (1o) + (-1)"n
1=1
Using T and the fact that n, 1 for any i E [2n]. then
2n
(w/" (1)
x1) x.,) = (w/"0) (1) xx) + (-1)'n
Te (Lo, (xx
E=1
2n Tey ()-1)=+( xx)
=(w//)) xx) (-1)3+in
(5)
2n
= (w (1)) xx) (-13' - 3(1m
Σ
Tey 1)
where we define Age == (1)))(((()))(()()))))) (x,, x,) Towards the goal of bounding the activation of neuron with data point provide the following results.
21

---

Lemma B.1. Assume [n, no)l I-y for all i E [2n] such that i + t.
1. Ifi = l then Xa= = 1.
2. Ifi + E Sr, and f Sp, then (7 S de S -(7 p)-
3. Ifi f, E Sp, and & E Sr, then - (7 p) Ae I -1 p)-
4. If * f and i,6 Sv, then Y Ae 5
5. ifi + l and i E Sp, then 7 Are 4p
Proof. Observe by the data model that
(x,, (-1) e1 (7 (1 (7-))))))))))) m.).
Therefore
Aut = =1)) (1-7),,;))
from which the results claimed follow.
Lemma B.2. Assume (n;, ne)) S E-y for all i, [2m] such that i + E. Then for any j [2m] the following are true.
1. ifi E Sr, i ~~ then
(w]) xx) 2 (w) (ta)
x:) + (iy(la, + G, (lo, - p) - B3" (lo: ()(7 +p)
(w))
xxi= ,, S (w) (ta) x,) + t) C) (to t) + - 13 (to, t) - ()(--))) p))
2. if E Sr, i it then
(w)",x xx) 2 (w/ x.) - C, + p) (tu, - p))
(w/", xz) S (w/ft) (ta) xz) - (Ti(la, (lo,
1) - p) - B¹x) (1: ()(7 + t))
3. lf E Sp, i ~ j then
(w])) x²) 2 (w) (ta) xx) - (Ti)(t, (t. - p)
p) Db t) + p) (w/",x/, xx) S (w/f (ta) xx) - 17 (Ti(tonnt) - G (t) + +) (to t) - -p):
4. Ifi E Sr, i + then
t) + (w)) x,) 2 (w) (ta) x.) + (To)(o, (to
B) t) - -p)) (w]) (1) xx) - (w/ (ta) xx) + (T)( - G (fo, t)r - -p) p)+ B) 1) + p)):
(t.,
Proof. Considering
5 we can further separate the summation term as follows,
(w xi) = (w (1o) x²) + (-1)+t+3ii
Tey(to.t+ Σ Tey(to, ()ta + Σ
Tey t)dee
REST
RES
E
Note, with i E Sr and i j. or i E Sp and i 26 j. then (-1))+i On the other hand, with
i Sy and & j. or Sp and ~ j. then (-1)3++ -1. Substituting the relevant bounds
(f. on Air provided in Lemma B.1 and observing by definition that (lo. 1) = EEES, Ezt Tex Tey(to, t)
and ( (to.t) Eresr Te (to, t), arrives at the results claimed.
22

---

We will often make use of the following similar but more pessimistic bounds on the activations. Recall that @ is the ReLU function: o(a) = max(a,0) 0}.
Lemma B.3. For any j E [2ml] and iterations tu, t with to S t the following hold:
1. If E ST ~~ j then
o((w)) xx)) 2 (((w) (16) xxx) + ( -1 ") (lo, ()
- (fo.t)
+ o((W)) (1) xx)) S <δ( (w (10) xx1) + 1(( pl +
- - B) t).
2. If E ST, i i j then
-oblo (((w)) (1) xx)) 2 (((w) (t)) x1)) - -100::)---tt0000000000000--00000 (t. (tn t)
(((w)) (0) xx)) S (((,) (t)) xi))
+ +) 10l - 7) (tu, t) + n
3. Ifi E Sp, j j then
d((w)) 10 xx1) 2 ((w, (ta) x1)) (to,)(to, - +) (to, (o - (to,t) t)
d(w))) (0 xx))= S ((w,)
(to) xx)) (lo,) + 7 + D)G () + no(p 7) 7) (lo, 1) + 1).
4. Ifi E Sp, i + j then
o((w)) (1) x))) 2 @b (ta) xx)) + T7 (to, 1) - -77 + PGG - nolp - 73) (Lo, 1) (( (t) x))) S ((w)) (ta) x.)) + 11T (lo, 1) +1++))+++)))) +)(++ (lo, 1) + nnlp - G) 1).
The yj term in the upper bound for cases 2 and 3 is only necessary Tf (to, t) > 0.
We remark that we will often use this result in setting where p S 7. In these cases, the terms that involve p(p 77) are zero and will be dropped.
Proof. For each of these results, we make use of Lemma B.2 S d(a) for all a E R, and
0 s Gj
(1) (to. t2) S (1)
0 < BJ (to. (1) S (2)
for all i.j, t0 42. We will only prove the inequalities for i E Sy here, as the inequalities for i E Sp are analogous.
For the first inequality in Statement I we claim it suffices to show
(7+1) (((w(T+1) 3
xx)) 2 o((w)" xx)) + t (T, T + -1+++11-=+++p)))
(T, (T, +1)
Indeed, if (6) is true then the result claimed follows as
Φ( (((w?) (1) xx)) - o((m xz))
(x,) =
j (T+1) xx)) - (((w)))) (x²) <((w
n(> + (T, +1B
#=0
-nglo - 1 (T.
nTT (((())t)))((()))))))))
By t) nolp - -nooolt---o(-(ooo-) 7 (to, t).
In order to prove 66) we bound
Φ0 (w (1+1)
x;)) 2 (w/ (1+1), ,x+z))x))
2 (w)") xi) + 1/Tiis
- He -
(7,7+1). (1,71),
23

---

This follows from Statement in Lemma B.2 From here, we consider two cases: first, if (w)7), x.) > O then (w) (T) x.) ((w (T)
xx) and 4 clearly holds. Alternatively, if (w) , < 0 then
(Ty 0, (w))) (r) xx)) 0 and as a result the right-hand-side of (6 is non non-positive while
the left is non-negative. As such 6 holds trivially.
For the second equality in Statement 1 we bound
(w)) x() S (w, (ta) x.) + (to, 1) + Gj (to ((+
(to, + -) B5Sh (to, t) -P)
{ (16) xx)) + nfTiy (fo, t) + 7 + p).. (to, t) no(p - B) t).
Since the right-hand side is non-negative, this inequality is true even if we replace the left-hand side by (((w)) (+) x.)). (x))).
We now proceed to Statement 2. For the first inequality, notice that if (( (to)
x.)) = 0 then the right-hand side is non-positive and therefore the inequality trivially holds. Otherwise, it must be the case that <( ((w (to)
(ta)
x,)) = (ww"")
(f)), xx) Using Statement 2 from Lemma B.2 we obtain the bound
(((W) j xx)) 2 (w])) xx)
(w) x,) (Ta)(o: +) (lo 0(7 + p) -)B (la, ()(( - p))
(to)
((w))) (1) xx)) - 1/Tii(lus 1) - . + ,) (4,, - nolp B,,,
We now turn the second inequality in Statement 2. The corresponding statement from Lemma B.2 yields
(w) (w))
(w//xx/) xx) S (w,) (to) xx.) - (to, + no(p nolo- - (to.
S ((w,) (to) xx)) 7/Ti + + p) (to, nolp G) (1) (to,
E)
(7)
S (ww)
(1a) xx))
(to,, 7 + P) (to, t) + nolp 7) (to, t) +
we remark that the reason for the addition of to the right- right-hand-side will soon become apparent. The desired inequality holds as long as the higt-hand-side non-negative, we therefore proceed by induction to prove
((w)) (() x;)) (to, + + ()o, r) no(p-~)G))) -)f (to. 2
for t 2 to- The base case T = to is trivial assume then that the induction hypothesis holds for some + 2 to. For iteration + 1 there are two cases to consider: first, if (w,
(r) xx)) < 0 then
(to ++1 = (io(to,7) In addition, as (3 T) S By 1+ and cf (to. T) c (to, T+1) then
0 < ((ww) (fo) x;)) nTTi;(o,, (3 + - 7) (lo, r) + + S <(((w) (fo) x;)) - + + (to,
(i) n0(p 7) (to, T + 1) +1
by the induction hypothesis. Alternatively, if instead (wf?), xx) 2 0 one may use the second inequality from to conclude that
0 S (w)) (T) xx) & ((w)) (fo) } xx)) (To, + n(7 + p) B, t) + no(p - -)G ()..)((o.)) (to.
In addition, as Tiy (1o, 7 + 1) < Tū (lo: 7) + 1 it follows that
0 ((ww) (10), xx)) - 1/ (1, 7) + 17 + By + 7/0 (lo,
S (((w)) (to) xx)) -
1 TTTi + + 77 (to + G) (lo, T + 11 +n
which completes the induction.
I Lastly, we consider the final remark in the statement of the lemma: if Tip (4,, 1) = 0 then the right hand side of the second line in (7) is non-negative trivially, so we do not need the additional n term.
D
24

---

B.2 Convergence of training
We say that GD terminates if it reaches finite iteration in which a zero update is applied to the network parameters. The following lemmas are used to show that GD terminates by in turn upper bounding the number of clean and corrupt updates. The first lemma facilitates the bounding of the hinge loss of clean and corrupt points.
Lemma B.4, For any iterations t, to satisfying 2 to.
1. if E Sr then
(t,, 2 v.J x,) + (TT((ta:)) (7 + ())((t) - -6( -0) 1) -m),
2. i E SF then
y: x,) 2 Va Voo, x:) + (TT(((a, () (7 p)G((o, () h(p 7) (to; 1) m)-
Proof. Both statements follow from the bounds provided in Lemma
B.3 For Statement
Σ (((w)) xx)) - Σ ((w! (x)))
2 Σ (o((w)))) (to) xx1) + (to, - -n(( + p) 1) - - (40 (40:t)
j-i
Σ (o((w]")) (1o) .xx)) n/Ti 1) + + By 1) + npbe ,) ) (lo: 1) + Spl
(1,((o, x;) + (T((Ttto.) (7 + B)b, t) s0p 70000 (to. m)-
For Statement 2 Ne I1 x,)
Σ ((( (1) xxi) - E (((wgg) xx²)
j
grs
2 Σ (o((m))") (10) xxi) + nTTi (to: t) - -n(7 + P)G;(to. -nol::::t--n-------- -) - (tu: t))
joh
Σ (ol(m/ (ta) xx,) 1/12, 1) + + + D) (to, + molp 1) (to: t) + 1)
2 wi xx) + (Ti(oo, 1) - (7 -(0-))))))) (1o, m).
The following lemma bounds the number of updates of corrupt and clean points an interval of iterations in terms of their hinge loss at the beginning of the interval as well as the number of clean and corrupt updates.
Lemma B.S. Let 1. 2 la- For E ST.
Tt(to,t) 5 x(to.x))
+ (7 + t(to + H(p - 7)0 f) 3m.
For i E Sp,
Te(lo: 1) < E(lo. xi) (7 + ()G((o, H(p ()) (to: f) + 3m.
Proof. We will show this for i E ST; the E Sp case is analogous but with the roles of corrupt and
clean points reversed. We proceed by induction on I and assume E(lo, x;) S a. If = to this holds trivially because the left-hand side is zero and the right-hand side is positive. Otherwise, assume the inequality holds at iteration t. By Lemma B.4 and our assumption on ((t,,))),
yr. (t. x;) 2 (to. xx) (T, t) (r + p) t) p(p y) ( (ta, t) m)
こ (1 - a) + (Ti - () B(to, - o(p - (0) (to, t) - m).
We consider two cases:
25

---

1. If (t) t) - -mm) 2 then we see that (tt,x,) 0. Therefore,
Ti(to, t + +) tt)
Q
+ (7 + Bt t) + 3m
11
0
< - + (7+ B(to, + 3m.
"1
2. Otherwise, Ti 1) S 2m neurons, we bound
(40, 6) m. Since there are only
Ti(to, & + 1) Ti(to, t) + 2m
a + (7 + p) olp -) t) - m + 2m
(t) + p) + olp 7) (to, t) 3m.
Appendix C Benign overfitting
Assumption 2. With 6, p E (0, 1) and C' generic, positive constant, then we assume the following conditions on the data and model hyperparameters.
1. 2 C' Coo((3) 3
2. m 2 C'log( 8))
3. d2 max 3, 22 2In Onn }
4. k 100
In(9n2 /81
5. 51
5m
6. A
In addition to the assumptions detailed in Assumption 2 in our analysis we use three further conditions.
Assumption 3. Let p E (0,1) satisfy 2 5p. In addition to the assumptions detailed in Assumption assume that the following conditions hold.
1. rpl 0.99m for p E {-1,1].
2. For all i SF there is E y, such that E A
3. For all i, [2n], & then (n;, nz)l S -
We remark that under these conditions then for sufficiently large n the inequalities S min 1=3k
n+t 7, 6(n-1) } and 7 min {v/ 4(n 4oj n 99% 100 are satisfied. As shown in the following lemma, these three additional conditions hold with high probability over the randomness of the initialization and training sample.
1
Lemma C.1. There exists positive constant such that for any E (0, if 2 Clog()) then the extra conditions of Assumption 3 hold with probability at least 1 - 8.
under the Assumption 3 for sufficiently large n there exists positive constant such that the probability the first condition does not hold is at most exp(-en). Alternatively,
Proof. Using Lemma A.3
26

---

setting 8 2 3exp(-en) and rearranging, as long as n 2 C loog (3) then the probability the first condition does not hold is at most 3" Conditioned the first event, using Lemma A.6 then if n 2 C Cloog()) (3) and m 2 Clog (%) then the probability condition two does not hold is also at most
3. not hold is also at most 3' Therefore, we conclude that all three properties hold with probability at least 1 8.
Therefore the probability that the first two events hold is at least (1 - $)2 2 1 26 For the third
3.
condition, noting - p and p - 7/5, then by Lemma A.] the probability the third condition does
C.1 Proof of Lemma 3.2
The following lemma characterizes an iteration independent upper bound on the number of clean and corrupt updates. This result will prove significant for proving the termination of GD.
Lemma C.2 (Lemma 3.2.. Assume Assumption holds. Suppose further that at some epoch to the loss of every clean point bounded above by a E R20, while the loss of every corrupted point is bounded above by b E Rgo Then the total number of updates which occurs after this epoch is upper bounded as follows.
2(n k:)
+mm+ +2k(( + p) (b) (3((+
G(to, 1) S - 4k(n k7 + x))
(1
2k:
+ p) ( +3m)
B(lo,t) 4k(n - (7 + p)
3m + 2(n - 2(m-))(7++)
3m
17
for all t 2 to-
Proof. From Lemma B.5
S 7, and the assumption on and b,
Ti(to, t) 2(n k) ( + (7 p)B(to: t) + +3m)
G(to,t) Σ
iEST
B(oo, Ti(lo, 1) s 2k ( ( t) + +3mm
iESr
Substituting these bounds into each other, and as y + p < (4(n k)) under Assumption we arrive at the iteration independent bound on the number of updates as claimed in the statement of the theorem.
C.2 Early training and proof of Lemma 3.3
Lemma C.3. Under Assumption for i E ST and j E I' follows that (w (1) ,x) > 0 iff ~
For i E Sp, j E Op. and o j it follows that (w(), xx) > ifi E A
Proof. Suppose j P, ~ j. i E Sr. Recall from definition of T that (0, - p)
Blsl (0, + p) z 2du, Using Lemma B.2
(w)", x,) 2 (w])) (0) xx) + 17 (Ti (f p) (B (o. + p))
(w)) (0) xx) 17
B,
(w) (0)
xx) 2\
> \w
On the other hand, i + j then again from Lemma B.2
(w j xx) < (w) (0)
(0,1(( p) - (0.1 +p)
x;)
$ (w)) (0)
xx) (G, -))
< ->w
27

---

Now consider i E Sp, o4 j. and E AA By Lemma B.2 and the definition of O
(w) (1) x, 2 (w) (0)
x:) + 1j (0, 1) + (0, - p) - -o. 1). + +1) 7 - 7 p) + (0, -)(-))))))))) - p) -C,(0.1((T+ P))
(0,
N 0.
Lemma C.4 (Lemma
3.3
Suppose Assumption 3
holds. Let j E p. Let 0 To. point
i A if one of the following conditions hold:
1. E ST and i ~
2. E Sp, + j. and E A!!.
Furthermore, if one of the following conditions hold, then i $ A/):
1. E ST and i +
2. i E Sp, i of j. and & A
Proof. We proceed by induction. For t = 1, the E ST case was shown in Lemma C.3 and the i SF. + j case is clear. Now, suppose the lemma holds for iteration t and consider iteration + 1. First i E Sp, i +f lf E A!) then
(w) ((+1) xx) 2 (w) x:) + (t, Gf
P))
(1 (n- - k)(7 + p))
2 0.
Here the first line is Lemma B the second line comes from the inductive hypothesis, and the third
line comes from (7 + p)
(Assumption 30. If & A. then
(w 3 (1+1) xx, $ (w) j xx) + 17 [t, Gf (t, 1)(7- - p) (t, 1)(7 p))
< (- (n - k) - p) + 22(7 p)) -n 3k) (n + k)p)
< 0.
Again, the first line is Lemma B.2 the second line uses the inductive hypothesis, and the fourth line uses S 4-3k, (Assumption 3).
n+*
n-38 Now, let Sr. We again use, in order, Lemma B.2 the inductive hypothesis, and p S i~ then
n 7- If
(w (1+1)
x
2 (w j x1) (x) + (+
- p) - p))
1 + p - ((n-))) p))
> 0.
If i ل then
(w] (++1)
xz) < (w)) (1) xi) -1 (1,(,,++1]] ( p) (0((,+++)(7+)))
< (n k)(r p) 12k(222 +))
((nn 3k)7 - (n k)p)
< 0.
Lemma C.5. Suppose Assumption 3 holds. For all to S t1 < To
Gz(to, < (n (n() to + 2) +
28

---

Proof. First we claim that for all i E Sr. j of i, and t < To.
(w)), x.) - Au + 21k((7 + p)-
We prove the claim by induction. The base case (t)
follows because (w, (0)
xx) S Aw. Now
suppose is true at iteration If (w) x;) then by Lemma B.2
(1+1)
x v (w) 3 X.) TiT (t, + n(7 p)B
(w xi) 77(1 - 2k + p))
(w) x,)
using 7 + + 26
1.
From this, the claim follows. Otherwise,
(w] (111) xx) S (w)
2nk(7 + p).
We now turn to the statement of the lemma, again proceeding by induction. The base case t to is clear. Otherwise, we consider two cases:
1. If tt) > 1+2k(t1 +1++))))) then for all i E Sr and + i, by Lemma B.2 7-p
(w/t), x.) S (w, (1)) xx) - 17 (T))(t,, G. (to. p) 1y) (to,
I (w,) (to) xx) - 17 (G, ti ti)(7 p) (1) p))
< (Aw + 2nk(1 + p)) + 2nk(t; - to) p) - ()) (1)(x-p)
0
by the claim and Aw < (Assumption B
Therefore, Gy(to: t +1) - Gy(to, 12) + (n k).
2. If Gy(to.t)) S 1+2k(t, 11++))
then
7-p
1 2k(11 - to + 1)(r pp) + +2(n kk)
G,(to. l + 1)
P
1
2k(11
to 1)(n 1ikn-)) + +2(n k)
+
7 7-1 p
2k
1
+ (t) - to + +3 k).
P-P
Lemma C.6. Suppose Assumption 3 holds. For all < To, i E Sp, and ~ j.
xx) S (A + 2mk(7 - p)) + 2n(7 + p) - k) + 7(7 + p)
(w))
P
Proof. Consider t < To- We consider three cases
1. If = then
(w: x.) S Au
2. If (w] (t-1) xx) S O then by Lemma B.2
(w)²) xx) - (w) (t-1) x,,
n TTy(t 1,t)
G/0 - 1,t)(--1) p))
< 27k((7 -p).
29

---

3. If (w, (t-1) xx.) > 0 then let 1' < ( be the smallest iteration such that (w)"), ,x,) > 0 for all
x,)
t' S t. By Lemma
B.2 Lemma
C.5 and the previous two cases above,
(w) 9 x - (wj²) (t) xx) - (T,(,,))-c.' (1, (t, - m))
-
1 (Aw + 27y((7 p))
2(7 + 1 (11 (1 - (7 + p)(n k)](L- (0:1)))(+++)))) p) - k) 7 p)
p
By p < n--E (Assumption 3 we conclude
xx)) s (Aw + 2nk(n - p)) + 2n(r + p) -k)+ 1777 + p) (w) (t) x,)
--P P
C.3 Proof of Lemma
Lemma C.7 (Lemma 3.4
Suppose Assumption 3 holds. There is an iteration Ti < To during
training and expressions C₁ Cz. and C3 where the following hold:
1. For all E (-1,1} j E Pp in J. and i E ST,
(w) (1) xx, 2
3
4m
2. For all p E (-1,1), T i J. and E ST,
(w) (T)
xxi= ( -
3ny
4m
3. For all i ST,
((Ti,x;) S $g
Furthermore,
Ti 1.03mmm(1 + (7 + p) - k))
+ 0(1)
Proof. Fix i E ST. At every iteration 1 < To. we bound
(11,x,) - f(l + 1, xx) = + 1,,,) - [1,,
2m
[6) (Ww) (1+1) xx)) - "((w)"",, xx,)
Σ
(-1) (o( (1+1) x:)) o((w)") x:))]
J&T 11t11
Σ 1,(6++1)+((++0c)))) (1, 11)
SpT (-1i1
Σ
+,( (t,++1)
=
(ET
+
(1,
jET
S 170.99m[1 + (r + ()(n k)] + 0.02 + 2(r + p) - [k)]
where we use order: 1 < To. the definition of [(1, x), Lemma C.4 Lemma B.3 -_ = 0.
and Lemma C.4 again. We also use |T, 2 0.99m (Assumption) 3 We further simplify this bound to conclude
l(t + 1,x,) x(t) < 1.03mm[1 + (7 p) -A)]
30

---

Additionally, we bound
8(1x;)) = (1,
2m
1 (-1)(tb((()))) (1) (x1)
j=1
2 1 Σ d((w) (1) .xx))
2 [K((W) (0) xx)) + (T, + + p)G (0. 1)
inj
2 1 m Aw + + + 27(r + p) Rt).
Therefore as long as
1 m AM + + 2
+ p) -]]]
1
+ 1.03pm[1 + (7 + p) k) +011,
1. 1.33mm [1 + (7 + () k:]
then
x(t, = ((,, + Σ l(t' + x - x()
1=1
2 1 - ml>e + + 2n(r + p) - k)] - 1.03(t' - 1))mm[1 + (x+ + p) k)]
0.
Notice that this does not depend on i p. Therefore can let Ti be the largest integer satisfying this bound for l and bound ((TI,x)) > 0 for all I E Sr. To verify that Ti < To, consider i E Sp:
2m
v.f(t,x,)=
Σ 1+1 (((W, xx:)
(1-1)*+3
1=1
El(o((w))) xx)) [x)))) (((m,))) (0), xx))) + d((w, (0) x:))
(Tij(O,t) + (r p) (0. + km)
S mmm[1 2(7 + p)k] + mmw
This is less than for all Ti since k 3 (Assumption
Now, fix i E ST again. For ~ j. we then can use Lemma B.2 and Lemma C.4
(w 5
(T) xx) Z x.) + (1- - (7 ())
(1,
2 0 (TT - -1-
2k(7
1 + (n- 1 - 2 p) +
1.03m + (7 + () k)]
1 2p(n- - 22(7 + (7 + p) - 2k(7 + p) ((n)
m
m( (7 + p) k))
1
1/6 4/99 + 1/100
+ +(
m
m
3
4m
31

---

using p S R(n is sufficiently small, and y < min
1 99k 100 / (Assumption 3
Now assume
i of j. Using Lemma B.2 and Lemma C.4 we can bound
(w) (T)
x S (w))) (1 x.) (1 ())))) (1, - (L
+
(1
S 0 (Ti - () ( - p) 2k(7 + p))
(n 17 - p) 10--2k 102(222+))) P) +0(1)
1.03m(1 (1 + (7 + p) k)]
(n -3k)y - (n + k) + (n)
1.03m
0.97ny
5" n
Lol
+ (n)
1.03m
3ny
4m
using 1) is sufficiently small and k S
and p S 2 (Assumption 3. Likewise, for 1 5t TT, n T0o
E(t, xx) - E(
vils( + 1,):) x:)]
2m
()) (++1) xx)) - ((( (t) xx))]
E
xx1)) (-1)+t) ((+1)
JED (-1)++1
Kw j ((( xx) - (w//) x,i]
=1
JET
Σ
(-1) (1)) (c+1) xxi)) - o((ws) .x:)]]
+
jer
Σ
Tiy(to, + G (lo - p) - -BJ0 (1o. (6
11
+ 17
-
jer
2 0.99mmm [1 + (7 - p)(n
+ 0.04ymm(7 + p)h
0.99 + (7 p)(n k- --11]] 2.000=.02mm7---- + p)k
In the first six lines we use: t < To. the definition of f(t, x). Lemma C.4 Lemma B.2 and Lemma B.3
Lemma C.4 again, and [ p > 0.99m (Assumption respectively.
We also bound
(11,,)) = 1 - (1,
2m
(1) (xi)) -1)t500((0)) ((((
1
j=1
< 1 Σ
(((w (1)
,x,))
Ktjj
5 1
[d((w)) (0) xx)) -
+),, + +
< 1 + m An + + + 21y(7 + p)k}
32

---

Combining these two bounds we see that
x(), - (1,, (T< ()(0099m(1++ (7 p)(n - 1)) 2.02m(7 + p)k)
0.99m (7 - 0)
1)] 2.02m(7 p)k O(1)
1.03m + (7 + p) k))
0.99((7 + p) + 2p(n k - 1)) + 0.08 4.04
99
+ +0()
1.03m + (7 p) k))
0.99( 1 0.08 + 4.04
100
99
+ 0
1.03
3
this iteration, as desired. Here we use (7 +)+ S min { oos 10o n }. n sufficiently small, and
S
6(n-R) (Assumption 3
C.4 Late training
Lemma C.8. Suppose Assumption holds. Fix > O. We will say a neuron aligned (at iteration t)
if
(-1)² sgm (w xx) y
for all ST- 1. 2 Tı, if
5en
B(T, 1) I
81)
than at least - 8)m neurons each T will be aligned.
Proof. Let E {-1,1} and be such that em different neurons in Пр are unaligned at iteration L.
For any neuron index j E pр and E Sr, we can use Lemma B.2 to bound
(-1)tt3 (w.) (1) x 2 (-1) (w) (1) xx) + (TI.t)
+ 17(7 GG (Ti,t) ne + p)B
{
3ny n(7 + (T.
min
4m
4m
3ney
77 B) (Ti,)).
4m
If the lower bound above is positive then (-1)² sgn(w" (w" x.) ys. Therefore, if a neuron j is unaligned then B, (Ti,t) 2 3ny
Since ny < (Assumption 3 we see that min
3 3ny 3ny
Im Tm
Im
5n 81mm
(using from Assumption 3
If there
unaligned neurons, then
4mp((+p)
2m
5En 8n
B(T,,))= Σ B,((T,1)2
Denote the first iteration after Ti where more than sm neurons in one of the I,, are unaligned as T no such iteration exists, let T = oo. will eventually show that indeed T = oc, by showing that the training process reaches zero loss before such an iteration can happen.
Lemma C.9. Assume Assumption holds and also y + < so that for all iterations satisfying To t < T. and all ST,
0.99(1-5) There an iteration T2 2 Ti dk
E(1, x:) < 471( + p)km.
Furthermore, we can choose To so that
Ta - Ti S
31mm(0.991 - 5) 4k(7 + p))
33

---

Proof. Fix i E Sp and & < Te - 1. Suppose xtt,x,) > O. Using Lemma B.3 and t < Te.
2m
ytf(t,x;)
(0(+) (++1) xx)) o((w)) x;)))
j=1
2m
(x -
Σ
j=1
n0.99(1 =)m 17 p).
Therefore,
(,x,),x,) S min, x.) pmm - c) -k),
By Lemma
C.7 the loss of each clean point at Ti at most 5. so each clean point reaches zero loss
in at most
37pm(0.99(1 - E) 4k(7 + p))
iterations.
Now suppose x() = O. We similarly argue
2m
ytf(t + 1,x,) - xf(
11)+t (1+1) ,x)) - NlWw, xx)))
j=1
Σ
44ymk.
This implies Ell + 1, x;)= S 4ymkk. By induction, we see that if Te and E(t, x,) S 4nmnk, then ((t + 1,x,) 4rmk..
Lemma C.10. Assume Assumption 3 holds and + < 0.99(1-s) S Te and i E Sr,
For all t1, 12 satisfying To S
4k
t,( A(t2 ti)(y + p)k + 4k +
0.99 6)
Proof. Recall Lemma B.5 (restated in this setting, using Lemma C.9
Ti(1,,t2) 5 4nmkk + + + B) 12) + 3m.
Using Te we bound
0.99(1 - =)mS, S t2)
4mmk
+ (1 + ((1( 3m
< 4mk + 4(t2 - 11)(T + p)mk + 3m.
From this, the desired inequality follows.
Lemma C.11. Assume Assumption 3 holds and 7 + min 0.99(1-s)
0.99( --
Let E Sp.
4k
8[n RIR
Suppose there is j o such that
2(n k)( + p)k -
(w (T))
0.99(1 -6)
Then for all t satisfying Ta St Te. (w x.) 0 for some neuron j' depending t.
34

---

Proof. Let 2 To be the first iteration after Tz where ((t,x,) = O. We will show by induction that for all & satisfying T2 S t S To that (w) x 0. The case T2 follows immediately by the assumption of the lemma. Otherwise, assume (w) (w( xx)) > for all T2 S < t. By Lemma B.2 and Lemma C.10
(w) (1+1) xx) 2 (w)
(T5)
x.)
+ 17 Tip 2, 1 + + - 1)(1 p) BB) (T2,t ( 1)(7 p))
(w/ T2) xx)) + (t 11 T2) 77 + p) Σ +.
IEST
(w) (1)) x.) + +n(t - -1-13 T2)
72 k7 - p) ( (A(t+1 1 (7) + p)l: 4 +
0.99(1 -6)
(tt 1 1-11-)) ( 8(n - k)k(7 -1)--) + p)²
+ (w/ xi)
0.99(1 - 8)
2(n k) + () +)
11
0.99(1 =)
> 0.
We now continue the induction past To- If (t, 0, then point i clearly activates some neuron. Let Ti be the first iteration after To where E(t, x,) > 0. By Lemma B.3
2m
x))( vaf(n 1,x,)
Σ (-11) (0l)))))0((())) (n) xx)) (x,)) (((w(m-1),x)))) xx)))
2m
> ((T - G 1))
j=1
2 4mmmm k).
This means
Σ E(-1)o((W)) (1) xi)) 2 UI((I, 2 1 4mmm(n k)
s'
and there is some j' satisfying
1 4n(n - k) > 17 0.99(1 s)
2(n k) + p) + 3)
o((w /' xx))
2 m
assuming is sufficiently small (Assumption 3). We can run the original induction argument with Ti replacing T2 and T2 min(t T2 ((t,x; 0} replacing To to verify the conclusion for Ti Sts 72. By switching back and forth between these two arguments, we can show that point i activates some neuron for all T2 < Te-
Lemma C.12. If Assumption 3 holds, the training process reaches loss.
Proof. In this proof, let E
= 5- The conditions of Lemma C.9 Lemma C.10 and Lemma C.11 hold
because + p S min 0.99/5
0.99/5
2k[n-A]
By Lemma C.2 there finite bound on the number of updates, independent of the number of iterations spent training. If we carry out the training procedure for infinitely many iterations, there must be some iteration where we make no updates. Since the training procedure deterministic, we will not make any updates after this point, and we will have converged. It remains to show that this convergence results in zero training loss. The only way for a point to not update any neurons is for that point's 's loss to be zero for that point to activate neurons.
35

---

Lemma C.8 and Lemma C.I1 say, under certain conditions, that every clean point and every corrupted point activates some neuron for each iteration < Tr. We need only to verify that these conditions hold and that B(Ti.)) 1) remains below the limitation set in Lemma C.8
We apply Lemma C.2 starting to Tí. By Lemma Lemma C.6 for i E Sp,
C.7
( x.)
for all i E Sr. Using S
2
{(T1,xx) $ V
11)0((w) TT)) (T), ,xx))
j=1
2m
< 1 +
(((w)
(T1)
xx)))
1 O(n).
With these bounds, Lemma C.2 shows that for all 2 Ti,
2k:
- + 2(n - k)(7 + +0) 1
((T1,)) <
+ +0
- 4k(n - k) + p)²
21:(1 + (2/3)(n k)(( + p))
1/(1 44:(n - k)(7+ 1) 0(1
2k(5/33 + O(1)
711 4/99)
n
S 10n
using 7 + P min
1 k- 9ok }. 7 sufficiently small, and le S 100 (Assumption 3). By Lemma C.8 Sen
Te = 00 if
n
which is clearly true for s = } 8ry
10n
We now show that every training point i activates least one neuron each iteration. By Lemma C.9 this is true if i E Sr. By Lemma C.II this is true for i E Sp if there is a neuron j + i such that (w) (T2)
x 17 2(n (pn-k)(
0,99(1-s)
First, assume that E(1, x;) > 0 for all 1 < Tz. By Assumption and Lemma C.3
we know there is
j E T y, such that i E A Using Lemma B.2 and Lemma C.4 we can bound
(w (T) x.) 2 (w) (1) x.) + (1, - -17 + p) (1, T1) + 1 p)BB (1,
2 n
+ p) (T)
and
(Ti, (w) x 2 (w) (T)) xx) + TTi T2) - + (T, T2) + n ( (Ti, T2).
j
By induction on we see that
(m (m- (7+ (T,,))(TTT,)))
(T( S maax TiSt'<1
7-P
for t > Ti. The base case = Ti + 1 is clear. Suppose the inequality holds for t. Either GT(Ti, t)
increases by at most n - l or there is some i' E ST n Altt1) with i' z j. By Lemma B.2 and Lemma
0 xx) < (w) (T))
x²) () () (T)
S 5-1(7 p) (T.,) n(7 + p) (TT,1)
from which the inequality follows. Since (T < 3k(1'' -Ti) < (n k) - Ti) (using
7-P
p and k < 100 from Assumption 3. this maximum occurs at 7 = Tí. This yields
(T2)
xx) 2 171 (7 + (m k))( +1 1))(r~))
- ,)BB (Ti Tz)
2 n/1 - (7 + pm (0 k))T2
36

---

We want to show this bound is larger than a quantity that is On)). This happens when both of the following hold:
0(1) s (x + (n))))aa
which holds when 17 is sufficiently small.
Now suppose {(T, = 0 for some iteration 7 S T2. By Lemma C.7 Ti <T. In this case, we see that
M. x.) y. x:) +
(-11) [6((W))
(Ti) xx))) ,x))
((wr)()x)))))
2 1 777 + +p)G(T, T2)
2(n 1:)
[
++2k(7 + p) + +0(n)
2 1 (x +p)
1- 4k(n k) + 0)²
[
2
3 + 2
2 1 1 4/99
= O(n) 2
99
where in the third line we use Lemma C.2 and the fourth line we use 7 + p S min| ---x sote and sufficiently small (Assumption 3) Sine this is positive, there is some neuron j with / j such that xx)) is at least this bound. This is an 2211) lower bound. Since the required condition is (w) x O()), this can be achieved by taking 7) sufficiently small.
<((w) (Ta)
C.5 Proof of Lemma
Lemma C.13 (Lemma 3.5 Assume Assumption 3 holds. Let y E {-1,1} chosen uniformly and x = TV + vI- nn, where n ~ Uniform( (sspa(v) Suppose that (n, ne)) < T for all I E [2m], then (Tens, x) O.
Proof. Following the same steps as in 5 for any j E [2m]
(w) (Tau) x) = (w)
x + (- 1)'n n
Tep (1, Tend) (x)e,
2n
= =(w (to x1} + (-1)² yn
(to t) ((=)),,))())))))((((())))))))
2n Tey t)
= =(wf" xx, + (-1)' ym
Σ
t=1
where (==((1)y3(0)/xxx> = -(07 +(1 (1-7) (1 n). Then as in Lemma B.1
7 p SX 5 ST.
- -7 + p) SX S 5-(7- (---p) -), S
Recall, from Lemma C.4 for any j E T then (1, Tena) 2 G2(1,Ti = Ti(n - -k). As
consequence, for j we have
(w) (Tes) x) 2 (w (1) , x;) + G1 Ten) p) nB (1, Tem))( + p)
2 O(n) + Tn - k)(7 p) 11 Tend) (7 p).
For j such that (-1)3 then
o((w) (Ta))
(1) (Ta)) xx) - (((w,( j x,) - - Tend (em p) + - On) + (1, (7 + p).
(1, (7 + p))
37

---

As result
yf (Ten, x)
Σ (((w) (Tad) xx))
56/2ml
2 Σ (w) (Tru) x)
Σ
o( ((w) ((w)
(Ta)) x))
,ET,
1:1-1)+
2 " Ti k)(7 -D) -1 jE|2n]
By(1, Tena) O
JEL
2 0.99mmm - k) - B1, Tema) (7 + p)) O(n)
using [pp 2 0.99 (Assumption Bd. From Lemma C.7
T
1.03pm [1 + (r + p)(n - k:] +0(1,
furthermore, combining the assumptions 100k n, 1) sufficiently small, and y p - with Lemma
C.2 see
2k
1 ) + O())
B(1, Tema)
-
+ 2(n -
4k(n ky + p)
1
n
$
10n
Here we also use that ((0, x,) & 1 + mdw = 1 + O()) for all i.
Combining these incqualities it follows that
V x) 2
0.99
n
k
(1 P) 10 (7 + 0(n)
n
1.03
2
n
3n
+ O(n) > 0,
25
again using 100k < n, sufficiently small, and
n-
C.6 Proof of Theorem 3.1
Theorem C.14 (Theorem 3.1 Let Assumption 2 hold with p = 7/5. There exists sufficiently small
step-size yi such that with probability at least 8 over the randomness of the dataset and network initialization the following hold.
1. There exists a positive constant such that the training process terminates at an iteration Tend < On
2. For all [2n] then ((Tend, xx)
3. There exists a positive constant such that the generalization error satisfies Pf x)) + y) S cxp (-ody2).
Proof. Under Assumption 3 Statement and 2 follow from Lemma C.12 Note the bound in Statement
1 comes from Lemma C.2 applied from iteration 0 iteration Tend. using 4k(n k)( + p)² < 4 4/99
and ((0,x0 xx) = 1 O()) for all i E [2n]. With regards to Statement 3, from Lemma C.13 if
(n, nz)l < I-y
__ for all E [2m] it follows that sgn(f(Tens: x)) = y. Therefore, as _ p and
analogous Lemma A.I under Assumption 3 there exists positive constant such that
U 1=1
(nn (Kn, --
P(sgn( x)) # y) <
2nP(n E Cap(e1,7/5))
dy2
2n exp
15
exp (-od-²).
Finally, under Assumption
then Assumption holds with probability least by Lemma
C.I
D
38

---

Appendix D Non-benign overfitting
Assumption With p E (0,1) we assume the following conditions on the data and model hyperparameters.
1. n 2 1,
2. m 2 log2( ())
3. d max f3,3p- 33p-211 In An |
4. 120 O.
5. Y 6ydn'
6. 1) 2mon'
7. Aw 17.
In our analysis we require two additional assumptions on the training sample and activations at initialization.
Assumption 5. Let p E (0, 1) satisfy p S min 2 2 > and in addition the conditions detailed in Assumption assume the following two conditions hold.
For all i [2n] there exists j E [2m] such that (-13² = and E A
2. For all i, E [2m]. [(n, mi)l (mn, S R
1 Note under these assumptions that y 24 this implies 2n-1 > y and p S min 1-7 1
4n. 2n-1 ?
p < 5m As demonstrated in the following Lemma, these additional conditions hold with high probability over the randomness of the initialization and training set.
Lemma D.1. The additional conditions of Assumption hold with probability at least 1 - 8.
Proof. Using Lemma A.7 then as long as m 2 loge the probability the first condition does not
hold is at most 8/2. Using Lemma A. and observing T_ > p, then as long as
4n
d 2 max 3,3p
2 In
the probability that the second condition does not hold is also at most 8/2. Using the union bound we conclude that both properties hold with probability at least
D.1 Proof of Lemma
Lemma D.2 (Lemma 3.7 In addition to Assumption
S assume also that x(to S a for all
i [2m]. Then
2n
(++
T(to,t) 5 1- (2n 1)(7 + p)
+ ++33m
Proof.
From Lemma B.5
6(p 7) p 7, and the assumption on a,
Ti(to, f) 1
+ 3m (v p)T (t.
If we sum over we get
2na
T(to, t) <
+ 6mn (2n 1)(7 + (to,to
r7
from which the result follows.
39

---

D.2 Supporting lemmas
Lemma D.3. If Assumption 5 holds, then the training process converges to zero loss.
Proof. By Lemma D.2 there is an upper bound on the number of updates independent of iteration. This can only happen if there is some iteration after which we make no updates. In turn, this can only happen if every point is either at zero loss or activates no neurons. We prove by induction that every point activates a neuron each iteration t = 0. Consider an arbitrary point i [2n], at the induction hypothesis is true by Statement 1 of Assumption [ Suppose the induction hypothesis true iteration t, we consider the following two cases separately order show the induction
hypothesis also holds at iteration /. + 1.
1.
If ((t,x:) > O, then by assumption we can choose j [2m] such that o((w) (1) x.)) > O.
We bound
6 (((W[ (++1)
x1)) 2 00 (((W] ()) xx)) + 7 - 777 + () (t,t+1)
2 Φ0 (w) xx)) + 7 (7 + p) (2n 1)]
0,
which follows as y + p <
(Assumption
2n
2. If E(t, x.) = O, then
n: - yi
(-Ip ()xx)) xxi)
S Σ p((wg) (0) xi))
=-1-->=
is bounded below by 1. This means that there is some such that p0 ((w})) x:)) 2 1 We bound
d((w)) (1+1) (11)) xx)) 2 <( (1) xx)) 7(5 + +)T, (t,t+1)
11 + (2
m
2mn (Assumption 5)
Lemma D.4. Suppose that at epoch T every point is at zero loss. Then
(0, r) 2 n + O(n).
Proof. If ((T,,;) = 0 for all i [2m], then y:f f
(Ø((w))) ((((w))),x,))) xx)) ((w (0) x.))) O(n) x,) (T)
for all E [2n]. We bound
vif(T,x;) z
Σ
S Σ (TTT(
+ (7+ (0. 0(n)
=:(-1'==
< (0, r) + 7/(7 + p)) () (0,7)
Summing over i E [2n] we see that
2n S r/[1 + (2n 1)(x + p)T < (0, 0(1).
from which the result claimed follows.
Lemma D.5. Let y U)- and consider a clean test point x 7( + 7n), where n USd sppanv))+). If Assumptiin 5 holds, then
Plyf x) <
40

---

Proof. Observe by symmetry of the distributions of both and n that -x is identically distributed to and furthermore that the labels of x and -x are opposite. As result, if yf (Ten:: - -x) < O then at least one of ((Teme x) < or (TTend, -x) < O, in turn implying at least one of them misclassified. By construction, (w) x) > 0 iff (w)) (t) x)
0, therefore
(TToTo x) f(Teud, -x)) y
Σe (-1) ( Frad), x)) c((w)T -xi))
j=1
Σ
v(
1111)
(Tou) x).
j=1
Unwinding the GD update to a neuron we have
2n Tiy (0, Tand) (-1)ttix
w) (ina)
w (0)
+
Furthermore,
(x,, x) = 2(-1)((7 + (1 7)3(1)
then
2mm
2m
2m 2n
y( 1) (w,
(Tan)
x)
Σ
y y(-1) (W))
(0)
x
17
y(-1)) (0, Teaa) (x,, x)
==1
j=1
2n
$ 2md +
T:(0, Teni (7 + (1-m))((i(m;,n))
i=1
2md +
T(0, Tead)
(1 7) Σ
To Tena) ((()),, m,
im1
d 2md + 17 (0, Tend)? - ||z|| (1 (1-7) (n, u))
where the final equality follows from symmetry of the noise distribution, and u
EE 2n T: Tena n.
Observe
2n T,(0, (e,, Tems) (n; ne)
2 = Σ
i,1=1
2n
2 Σ
T (0, Temi)
P Σ
T: Te Te Tena)
1 y ip!t
2n
1- 1-7+ 7 +
Σ T,:(0, Tend)
P T0, Tena)
1 1-7
1-7
1 P T (0, (0, Tent).
2 2n
1-7)
where the final inequality follows from Jensen's inequality. By assumption 4np < 7, and v
10mAw S ny < which holds with probability 1/2, these inequalities in combination with Lemma D.4 give
6vd" furthermore trivially (1 () > 0.8. Conditioning on the event (n, u) > 0,
2m
V (1 - 7) (n. u)
Σ y( - (1-1)(w(7m)) (Tae)) x) < 2m2 +ny
2
4 Vilnn u).
5V
10
Therefore, if (n, u) > then the condition
Vnn u) 2 2
(8)
41

---

implies at least one of x or -x is misclassified. Suppose ~ U n span(v) is such that (8) holds. Then as y ~ U(f-1,13) follows given that either x or -x are sampled each with equal probability and thus the chance of misclassifying is at least 1/2. As a result, the probability of misclassification is at least
1 1 (Vdn, u)
claimed. We note the final inequality above follows by showing that the two spherical caps corresponding to the set of unit vectors satisfying (n, u) 2 1/(2vd) account for less than half the area of gd-1, which can be derived from formulas provided in (S (011).) This inequality has also appeared for instance in (Asi Duchi 2019).
D.3 Proof of Theorem 3.6
Theorem D.6 (Theorem 3.6
Assume Assumption 4 holds with p 5n. With probability at least 1 over the randomness of the dataset and network initialization the following hold.
1. There exists a positive constant C such that the training process terminates at an iteration Tend S
2. For all i E [2n]] e(Tends X;) O.
3. The generalizution error satisfies
1
P(sgu(((Tentt x)) # 4) 2
Proof. Under Assumption Statement I and 2 come from Lemma D.3 The bound on Tend comes
from Lemma D.2 applied between iterations 0 and Tend using &,, x;) = 1 O(r) for all E [2n]
and (7 + ( 2n 1) Statement 3 follows from Lemma D.5 We conclude by observing under
Assumption that 3 holds with probability at least 8.
Appendix E No-overfitting
Assumption 6. With 5. (0.1) and C generie, positive constant, assume the following conditions on the data and model hyperparameters.
1. n 2 Cooog
2. 2
3. d
3p 22 In
Gn
4. k < TO0
5. 2 <
min(k
-1 1,1).
36
6. Au <.
For our analysis we make two additional assumptions.
Assumption 7. Let p E (0, satisfy 2 5p. In addition to the assumptions detailed in Assumption 6 suppose the following conditions hold.
1. T= [2m].
2. For all i, ale. E [2n] such that + then (m,, n/)l S 1-y-
We remark under these assumptions that for sufficiently large n then satisfies the inequality p min (nn-36)-2 3. 11 ] As shown in the following lemma, these two additional conditions n+*
hold with high probability over the randomness of the initialization and training set.
42

---

Lemma E.1. There exists positive constant C such that if 2 C' log of Assumption hoold with probability at least 1- 6.
(2m 5
then the extra conditions
there exists a positive constant C such that for n 2 C there in turn exists constant e such that the probability the first condition does not hold most m exp(-cn). Setting d 2 2m exp(-cn)) and rearranging, as long as n 2 C log (2m then the probability the first condition does not hold is at most 6/2. Using Lemma A.1 and observing - > p. then under the condition on d stated in Assumption 7 the probability that the second condition does not hold is also at most 2' Using the union bound, we therefore conclude that both properties hold with probability at least 8.
Proof. Using Lemma A.3
E.1 Proof of Lemma 3.9
7 holds. Consider an arbitrary j E [2m] and iteration t satisfying 2 s t To. Then i E A/" iff j.
Lemma E.2 (Lemma 3.9 Suppose Assumption
Proof. First we establish at iteration t = 1 that for all E ST, i E A, iff i ~ j. The argument here is similar to that of Lemma C.3 Suppose ~ j and i E Sr. By Assumption 7 neurons are in I,
therefore from the definition of p for all j [2m] we have G (0, 1)(7 p) BB (0. 1)(7))++))))
2Am. Using Lemma
B.2
x,)
(0)
xx) + 17 (T
p) B) +)) p))
x + 1 (0, -) Bo, 10
2 (w) xx) + 2\
(0)
> Aw.
On the other hand, if of j then again from Lemma B.2
(w) j xx) - (w) (0)
x;)
(0, (),1)
(0. ( p) - -f
S (w) (0)
xx) - 17 (G, -
5 -
Now we consider 1 = 2. If i E ST and ~jj j then
(w) x 2 (w]) (1) x + 17 ( (1, (L,2((77
2)
> 17 (1 + (n - k - 1)(7 p) - -2k(y + p))
whereas if E ST and + j then
(w) (2) x₂) < (w)) (1) xx) 17 (1,) + t (1,2)(r p) -
-B// (1, + p))
S s-n((n - k)(7 - -)) + ())-
By assumption y >
2+ (ntk)p and therefore for i E Sr then i E At8) iff j. Again
n-3k
n-36
using Lemma B.2 for i Sp and ~
(w) x.) 2 (w)) xx) 17
(0)
---0 - (0, p) + B/ +B (0, (0. + p))
( 1 1- 2>10
> ~ -
17
> -77
and for i E SF and j
(w)) x,) 1 (w,) (0)
xx) + 17 - p) +)+B/0 (0. + +P)
< Aur + 17 (1 2>w
17
<
43

---

Therefore, as asy> 2+(ntkle then for i E Sp and i ~j n-3k
(w) j xx) 2 (w ( x:) 11 (f.
- (1, -
() +)+ BB) + +0)
> - 1y ((1 - k) 2k(7 + p) 11)
00
and for i E SF and اf j
(w xi) < (w, (1) x:) + (Ti) (1.2((1)) + (1.2))++++)
< 7 -
- ( p) - p)
0.
With the base case established we proceed by induction to prove if E A iff ~ j. then E A! iff i j. By the assumptions 7. the induction hypothesis and again using Lemma B.2 for
(w)) (9) xx) (w) (t-1) xx) -1 (Tup(t- 1, - -.0)),,(( 1, p)+ + BB8d (t 1, p)
((n k) -))-1(7 () 1)
>0
and for i A
(w/) x,) S (w, (111) xz) +1 Tip(t 1,0) - G1 (1- - p)+ + BB - 1, 1,0 + +1)
< <nn((n k) p) 1)
0.
Therefore, for an epoch / satisfying 2 Ti then i E A iffi
E.2 Proof of Lemma 3.10
Lemma E.3 (Lemma
3.10
Suppose Assumption 7 holds, then there is an iteration Ti < To such
that
(w," (T))
x,) S
>(n 2k) pm pm + (7 p) m(1 + n - 2k) + pm - (7 - p))
+ + ifi Sp
(w/ (Ti) xx))=
1 1+ 2k) pm (7 p)
01)) ifi ST,i
m(1 + i(n (k) + pm - (7 - p))
(w/T)), x))x)))) m(1 + 7(1 - 2k) + pm (7 p)) +0( fi
7(1 - 2k) pm
Furthermore for i E ST
2pm
(Ti, S
1 + 1 - 2k) + pm - (7 (p) +0())
Finally,
Ti 7m + ((n - 2k) pn (x- p)) O(1)
Proof. Lett To. By Lemma E.2 and Lemma B.2 we can bound for E SF and j as follows,
(w/)) xx) )x,) S (w/? xx)) - (2, ()) p)
nnt(( + p) -))
= n7((1(n- - + pm 1 - (1-))
Similarly, for E Sp, + j.
(w)) xx) ), S (w/²) + + (2,)))
= =-11((7 - pp(nn k) (1=
= =nnt(y(n 2k) pm) 0(n).
44

---

For E Sr, i ~ 3.
(0
S
= =n -m
and
(2) (2) - [ 2,
x1) 2 .x)
- (1) + 0
O(n).
Lastly, for i Sr.i j.
(w))) xx) S (w) (2) x1) + + 7 -) (2,1) +
-ny((1 pm - k) - (++ p)k) 0(n)
= -n 2k) pm) O())
Therefore, for ST.
2m
(-1) (1)))((w!),xx)
f(t, = ys
j=1
Σ (w))) xi) jui
from which conclude (1 +-(n pm))-m--a
- f(1,x,) < +7/((1+((n--- 2k) pm (p
Therefore, as long as
1pml(1 + + - 22k) + pm (7 - p)) + 0 <1,
(9)
then {(,,,,) > 0. Let Ti the largest value of satisfying ( and t < Tu- We see that
Ti mm + 7(n - 2k) pn - (7 - p)) OL)).
From this, the bounds claimed follow.
E.3 Proof of Lemma 3.11
Lemma E.4 (Lemma 3.11). Let Assumption hold. Suppose at iteration ty the following conditions satisfied.
a k(to,x,) S for all Sr.
b. (((w)))
(b) xi)) S for all E Sp and i ~ j.
c. For all iterations satisfying to S T S t holds that i AlT) only if j.
d. For all iterations satisfying to S Slii A if and e ST.
Then for j E [2m] and p E {-1,1) we have
3b 2a
By 7)
1)
m
3a
Σ tt((oott <
mb
?17
45

---

Proof. Consider an arbitrary neuron j E [2m], using Lemma B.3 and assumption (b) we bound for t T Ettttii Sp, and j
o x,)) S (Ti -) - (7 + P)G, 1).
As ((()) (,, .x,)) in general may conclude that
(1y 7) - + (r + ()G, r) + 1.
Summing over all i E Sp such that i then by assumption (c)
Σ [io 7) (t,
RESP
Combining these expressions it follows that
kb
By(lo, r)
k(> + p)G;(lo, r) + k.
"
As the number of clean updates on pair of neurons and j with l e~ is the same by assumptions (c) and (d), then we may rewrite this bound as
kb k(y p)
(tu T)
Σ Gelto, + k.
(10)
m
Let E [2m] be arbitrary, we proceed to bound i iNj
Σj G2 (lo, t). Using Lemma B.2 for i E Sr and
(w)
(1-1) x,) (w)) (1) xx) (Ti () T- 1) (r
|) (to,
1)).
By assumptions (c) and (d)
1,,, Σ
Φ (w (,,))
Σ jui
(w (fo) xxi + +
+ 1 - /) (to, - 1) n7(7 + p) (),,(to,
2 a) + 11 (7 -)))[(to,TT11
+
(t.) Σ ((7 (). 1) () 1))
Note either T,(,o, 7) = T: 7 - 1)or or ((T, x;) > 0. Consider the case where the latter holds, then
n((1- (111-7-p))Tl (t) Σ ((7 P) ( j-i
1))) <
Furthermore, suppose 7' S t is the first iteration before such that G,(T', = 0 and let E Sr, i be point that makes an update iteration 1. Using the above bound follows that
n((1 - (7 - -t))))((((of r' - 1) + Σ ((r (t,, T' 1) - (r + p) By - 1))) a.
This implies
Σ 11-- 1)) < a
1
Jm
and
Σ -06--pGao (ttt-)) () (to r')) < a 2(nn k)(7 p)-
1
j-8
46

---

By the construction of r' it follows that
(6-- + B,) < a
2(n k)(7 - p)-
jive
From this get the bound
E,,(to,t) - p 7
(r p) Σ By(lo,t) + +0(1).
(11)
grus
Combining 110) summed over j ~ with
then
(G)to::) + + xx)) +
kmb
EG - P
(r + p)
+ +(( +
71
1
a +
kmblr + +P)
5 - k(y + p)2
+ +1(1)
and
By(to r) 1 kb +
k(7 + p)
a kmb(( + p)
+ O(1.
m(7 k(y + p)2)
Using p S F. sufficiently small and S 36k
(Assumption
these bounds simplify to
3b
2a
B,(,,,
m
3a
E Gy(to:
mb
717
E.4 Late training
Lemma E.S. Under Assumption the training process terminates at iteration Tend satisfying
(TTend, xi) 0
for all i E Sr and
8 (((w)Tau) x;i)= =0
for all SF and j E [2m].
Proof. By Lemma E.3
iteration Ti with
2pn
1 + + 2k) + pn (4 + +0()).
((n 22: pm 1-11- (7
+ +
m(1 + 7 22k) + pm - (7 - p))
then the first two conditions of Lemma E.4 are satisfied. Next, using Lemma B.2
we see by induction
on t 2 Ti that if
7(n 7(n-26 22k) pm
B,(T,,t) <
mmm(y + p) + +(1 - 2k) + pm - (7 - p)) +0(1)
then for i + j and T S St.
(w xx,) (w (1) xx) + m(n + (TB,(
x,)
(w]
x m(r + (T,(TT.)
<0
47

---

and for i E Sp, i J. and TI STSt,
(w) (w)", x;) 2 (w) (Ti) xx) - 77 + (Ti,)
(w) (Ti) x,) - 11( + p) BTTi,)
1 1- p)
m (( 2k) + pm (7 p)) +0())
for 1) sufficiently small. Thus we have shown under an additional assumption on (T, 6) that with to 'I and and b as defined above, then all four conditions of Lemma H.4 are satisfied. As result GD converges or terminates as long as
A
3b
2a
nm(r p)(1 + + 2k) pm (7- +1()
7(n-2k)
- pm
2m
1pm
which is equivalent to
3 (r(n 2k) - 1 (7 p))
11 pm)
k(y p)
< <n(n (2k) pm + 0
This is true by Assumption 7
3 (7(n ((kl--2k--a 2k)
11
1
3
3
k(7 + p)
- 1 (7 p)) +
2 pm
S
30
2
7(n
2k)
2
+
36
+
< 1
1
7n1 2k)
20
2
< 7 2k) pr,
where above we used S min 36x 36 and p S min {E) }.
Lemma E.6. Assume Assumption 7 holds. Let y E f-1,1} 1 be drawn uniformly at random and
x = y TV + vI-in for all I E [2n], then (T x) > O.
in where m Uniform(S S n span(v} ). Suppose that ne)) <
Proof. We proceed as in the proof of Lemma C.13
Following the same steps as in (5) for any
j E [2
2n
(w) (Tai) x) = -w, (2)
xx) + (-1y'n
Tei (1, Tend) x²)
2n Teş (1)
= -(w,² x,) + (-1)' yn
8=1
2n
= -w x,) + (-1)" yn
(2,
8=1
where (-1))_]))( x) = 3(0 + (1 n). Then as in Lemma B.1
- p SX 54+ if Sr,
-7 SX < 5-77 p), if i
Recall, from Lemma E.2 for any j E [2m] then (2 2 G2) = =T1 2)(n - -k). As
consequence, for j p have
(w) (w (Tes)
x) > (w) (2)
xx) + G2 Tand (7 p) B2, Tend) + p)
> O(n) + T k)(7 p) (1, Tema) (7 p).
For j such that (-1)3 then
d((w) (Ta))
(Ta)) x))
;a)) - (6(w,))))) ; xx:) - 7, Tend) p) + (2, Tema))))))))) + p))
(2)
- On) + Tena) (7 + p).
48

---

As result
(Tend, x)
Σ
(W( Tou) x))
jc 2m
(w) (Ta))
Σ (((w) (Toe) ,x))
2
x)
j:(-1)mm
1:(-1)'/y
2 1) Σ ( k)(7 - p) -1 Σ
B2 Tend) (1 (m)
y: ;
jE(2x)
2 nm (n - k) p) - B1 (r + p)) + O(n)
Decompose B2; Tend)
B[2, T1) B(Ti, Tena) and observe from Lemma E.2 that
(2, T1) = (Ti 2) 2km + O(1).
From Lemma E.3 and Lemma
E.4
using the assumptions S
11 sufficiently small and s
2
min
A then
36
3b
2a
B(T,, Tena)
s 2mk
2n
17m
3(7(n 2k) + pn
1 + (7 pp))
< 2mkTi
+ +pp + O(1)
2
"1
2k
S 2mTh
+
+011)
24
22
2
72
11
mTi(n k:)
12
Using the assumption that S 100
and 1) is sufficiently small we see that
mTTin k)
Tena) S
As
(f x) 2 mm k)(() P) - p)) O()),
then (Tena x) is positive provided (y- p) (7 + p)/9 positive and rj is sufficiently small. Both these conditions are guaranteed by Assumption 7 and thus the test point correctly elassified. O
E.5
Proof of Theorem
3.8
Theorem E.7 (Theorem 3.8 Let Assumption 6 hold with p p== 7/5 There exists a sufficiently small step-size yi such that with probability at least 1 6 over the randommess of the dataset and network initialization we have the following.
1. There exists a positive constant C. such that the training process terminates at an iteration Tend S Cn
2. For all i ST then e(Tend, xi) O while l(Tend: xi) for all i SF.
3. There exists positive constant e. such that the generalization error satisfies
PJ x)) + < exp (-cd72).
Proof. Under Assumption 7, Statements and 2 follow from Lemma E.5
The bound on Tend follows
from Lemma E.4 applied to 2, indeed the number of iterations cannot exceed the number of updates which, as 3. is bounded as
2
B(2, Tema) + Teml) S le
+
+ O())
mm
2n
Again under Assumption 7 Jsing Lemma E.6 then Statement 3 follows in exactly the same manner as
the proof of Statement for Theorem C.14 Finally, Lemma E. liplies that under Assumption then Assumption 7 holds with probability at least 8.
49

---

Appendix F Numerical simulations
Reproducibility statement: the code used to generate the following figures can be found at https //gi tig.thhu.com http:hhhw....cm////w.ttttot///// ott.rrrtrrreoeoonnoeeeeeiittttt.
To investigate our theory we train two-layer neural networks with ReLU activations using full-batch gradient descent and a fixed step size. We train on a synthetic binary classification dataset generated Finally, we train using both the hinge and logistic loss.
as per Section 2.1
Lit
Iecce
33'4
301
377
1400
220
Correclly
Oceeily Carret
Coceddy
33
0.9
00
0.
0.4
06
Figure I: from left to right, the first row shows the clean, corrupt, and test losses as a function of epoch (or iteration). The second row shows the fraction of clean, corrupt, and test points that are classified correctly. These plots were generated with n 100, = 800, k/n = 0.1, m = 100, 7 0.015, and step size of 17 0.01.
In Figure T we call attention to the difference in the training dynamics of hinge loss versus logistic loss. Perhaps the key difference between the hinge loss and logistic loss is that the contributions from any given point do not get smaller as the point approaches 0 loss. Furthermore, unlike with the logistic loss, points can actually attain zero hinge loss after finite number of epochs. While point has zero loss ceases to contribute to the update the network parameters. As a result, points close to zero hinge loss periodically activate and deactivate giving rise to the chaotic behavior observed as the training loss approaches zero. We emphasize that managing this behavior required a careful analysis distinct from that of prior works analysing the logistic loss.
In Figure 2 we call particular attention to the bottom right plot. Our theory predicts a phase transition between benign overfitting and non- benbeenign overfitting when y R c/n: the phase transition we observe empirically in the bottom-right heatmap suggests this estimate is reasonable. With regard to the hinge loss over the corrupt points, displayed in the top-right heatmap, we observe another phase transition, this time between overfitting and non-overfittin. The top and bottom heatmaps of the left-hand column display the hinge loss over the clean training set and total training set respectively, these appear very similar due to the fact that clean points make up 95% of the training set. The clean points fail to achieve zero, or close to zero, hinge loss only when y is small and is large. As stated in the caption, in these experiments d is fixed and thus as n increases the near -rthoonnttyy condition we require the noise components in order to prove convergence to zero clean loss is compromised. As a result, when y is small and the correlations between noise vectors is potentially large it is possible for pairs of points with opposite labels to be significantly correlated.
50

---

Clean Loss
Cernupt Loss
2
4
4
0.4
9
0.1
30
10
0.2
-0.
-35
0.0
0.0
20
99 110125 380 355 370 200
35
50
310 140 17011325200
Total Loss
Test Loss
0.5
0.6
0.5
0.4
0.4
40
-1
12
12
-02
0.9
Figure from left right in the top we show the loss on clean training and corrupt training points after training. In the bottom row and again from left to right we show the total loss after training and the test loss 10000 randomly generated points. For each plot set 1000, m 30, y) 0.005 and train for 5000 iterations of gradient descent using hinge loss. In each plot we vary and n and hold the fraction of corrupt points constant 0.05. In the bottom right plot we also graph the curve c/ for x 0.6
51


Reviews:
[{"review_id": "dbHXXDcVUi", "reviewer": "Reviewer_dAPs", "summary": "This paper studies the benign overfitting (or not) of two-layer ReLU neural networks under the hinge loss. Under a new noisy (almost orthogonal) data setting without separable data setting, \n- Theorem 3.1 shows that benign overfitting exists occurs the signal-level parameter $\\gamma$ is small in $\\Theta(1/n)$;  \n- catastrophic overfitting (the generalization error is bounded below by a constant) occurs when $\\gamma$ is small enough at the order of $n^{-2/3}$. \n- Instead, if $\\gamma$ is large, no overfitting occurs, i.e., training error cannot be zero but generalizes well.\n", "questions": "- I understand the data setting with $d \\geq n^2$ for the orthogonal condition, which is widely used in the benign overfitting literature for two-layer neural networks. But currently there exists some work that has fixed this issue:\n\nFrei et al. Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization. COLT2023.\n\nSo I kindly ask the authors to think about whether their assumption can be relaxed or not.\n\n- Since I’m an emergency reviewer, I don’t have enough time to check the proof. I high level read the proof framework, and find that line 236-237 is they key proof idea:”every training point activates one neuron after the last training update”. Could you please detail this?\nThe generalization performance (whether benign overfitting occurs) only depends on the signal-level parameter $\\gamma$ in the data generation process. However, intuitively, the difference on generalization guarantees is based on the changes of model complexity. So how to understand this issue?\n\n- Continuing the above question, we can find that, if $\\gamma$ is small (enough) at the $O(1/n)$ order, we have the benign overfitting. However, it means that the signal level $v$ is quite small and the noise level $n_i$ is quite large. That means, the model can fit such large random noise? If $\\gamma$ is large in Theorem 3.8, the model cannot fix the noise to achieve zero training loss if the noise level decreases. When checking these two results, I find that there exists some contradictions here? Maybe I’m missing something.\n\n- The width $m$ is not required to be over-parameterization?  More discussions are needed.\n", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- provide solid analysis of generalization guarantees of two-layer ReLU neural networks under a new data setting\n- The results on benign overfitting, catastrophic overfitting, and no overfitting heavily depend on the choice of the signal-level parameter $\\gamma$ \n", "weaknesses": "- The motivation of this paper is to fix the benign overfitting problem under the hinge loss. Since the analysis of previous work on the logistic loss is invalid, the authors focus on a new data generation setting and new proof framework. However, the motivation and significance of this research appear somewhat limited, particularly when considering the hinge loss. It would be beneficial to emphasize the differentiation between the results obtained with the logistic loss and the hinge loss, highlighting the theoretical advantages of employing the hinge loss. Additionally, exploring potential implicit biases related to benign overfitting and engaging in further discussions, particularly in comparison to the work conducted by Shamir (COLT2022) on the squared hinge loss, would strengthen the paper's arguments.\n\n- The problem setting and data assumption are a bit unrealistic (also as suggested by the authors). It’s ok for me but there are some assumptions missing, e.g., in the benign overfitting part, $n - k > 2*10^6$ in Lemma B.4 is needed. I think this should be clearly mentioned in the main text.\n\nMinior: \n- The early phase in line 224 is undefined.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their time and comments and hope we can address each of them below. We hope that if you are satisfied with our responses you might consider increasing your score.\n\n- *\"...emphasize the differentiation between ... the logistic loss and the hinge loss\"* A comparison of the hyperparameter regimes required for our results versus those of related works is provided in Table 1. We also display preliminary experimental results in Figure 1, Section G of the supplementary: as discussed in the text of Section G the network trained with hinge loss appears to fit the data faster and exhibits an oscillatory behavior in the loss dynamics not present in the loss dynamics of the network trained with logistic loss. We remark that the primary goal of our work was to investigate benign overfitting away from the exponentially tailed losses setting, thereby diversifying our understanding of the phenomenon.  In revisions, we will call further attention to the results in Section G in the main text.\n\n- *\"Additionally, exploring potential implicit biases related to benign overfitting and engaging in further discussions, particularly in comparison to the work conducted by Shamir (COLT2022) on the squared hinge loss, would strengthen the paper's arguments.\"* We remark that we do cite this interesting work but did not include a detailed discussion due to space constraints: in particular, while our work and those we use for detailed comparison in Section 1.1 consider non-linear models, the work highlighted considers linear models.  We will give more attention to this paper on future revisions.\n\n- *\"...there are some assumptions missing, e.g., in the benign overfitting part...\"* Thank you for highlighting this.  While that assumption is in Table 1, it was mistakenly left out of Assumption 1. This will be corrected in future versions.\n\n- *\"I understand the data setting with $d \\geq n^2$ for the orthogonal condition, which is widely used in the benign overfitting literature for two-layer neural networks. There exists some work that has fixed this issue: Frei et al. ...\"*. To clarify, we emphasize that, like the paper highlighted and indeed all other works in this space we are aware of, we do not require strict orthogonality. Instead an approximate notion of orthogonality suffices: we require that pairwise all inner products between the noise components of data points are small. Likewise, in the paper highlighted by the reviewer, the authors also require a condition of approximate orthogonality, controlled by a parameter $p$. In Lemma B.1 of our paper, one may observe this is analogous to our variable $\\rho$. Depending on the distribution from which points are drawn then as long as $d$ is sufficiently large whp an approximate orthogonality condition on the dataset will be satisfied. The $O(n^2)$ scaling of $d$ required across the broader literature (in the highlighted work see condition CL2 on page 10 for instance) arises from a union bound over all possible pairings of inputs.  We will clarify this in the revision.\n\n- *\"... every training point activates one neuron after the last training update, could you please detail this?\"* Lemma 3.2 and its analogues in other settings state an iteration-independent bound on the total number of updates. This implies that there must be an iteration after which no further updates are made and therefore the network must reach a steady state. This is only possible if the gradient with respect to each training point is zero. For a given training point $i$, a zero gradient is possible only in two situations with a ReLU network and hinge loss: 1) that point achieves zero hinge loss (i.e., is fully and correctly classified) or 2) that point activates no neurons (i.e., $\\langle x_i, w_j \\rangle \\leq 0$ for all $j$).  We wish to rule out the second of these cases, so our goal is to show for each training point $i$ there exists a neuron $j$ such that $\\langle x_i, w_j \\rangle > 0$.\n\n- *\"the difference on generalization guarantees is based on the changes of model complexity. So how to understand this issue?... The width $m$ is not required to be over-parameterization? More discussions are needed.\"* Large dimensionality of the input data ($d > n^2$) implies that the number of learnable parameters of the neural network is large relative to the size of the training sample. This in turn yields a relatively high model complexity even when $m$ is relatively small. Indeed, as shown in Table 1, our dependence on the number of neurons is very similar to that in prior work.\n\n- *\"... if $\\gamma$ is small (enough) at the $O(1/n)$ order, we have the benign overfitting. However, it means that the signal level $v$ is quite small and the noise level $n_i$ is quite large... If $\\gamma$ is large in Theorem 3.8, the model cannot fix the noise to achieve zero training loss if the noise level decreases. When checking these two results, I find that there exists some contradictions here?''* In the small signal, high noise setting the network is able to fit the noise because the noise components are pairwise close to being orthogonal to one another. Therefore the projections of the network weights onto each noise component evolve approximately independently of each other during training. Indeed, with a large noise level the updates from the noise components dominate and each point is fitted by the network learning its noise component (harmful overfitting). In the large signal setting the signal dominates the training dynamics and points are fitted based on their signal component. Furthermore, fitting the clean points decreases the pre-activation of each corrupted point on neurons of the same label sign. Eventually this leads to corrupted points not activating neurons of the same label sign, the corrupted point then zeroed by the network, and an equilibrium position then reached.  This results in a nonzero loss at the end of training."}, {"review_id": "ipJOwJ8eUN", "reviewer": "Reviewer_ZHgu", "summary": "In this work a simple model of linear classification is analyzed to study the phenomenon of benign overfitting and generalization of neural networks with noisy data. A theoretical analysis of the trajectory of GD shows that it can be in three regimes (1) benign overfitting (2) non-benign overfitting and (3) no overfitting.  The analysis relies on a novel proof of the nonlinear dynamics which shows a bound on the number of non-trivial updates of GD until convergence.\n", "questions": "In Eq. (1) why is $\\beta(i)$ needed in the definition of $\\boldsymbol{x}_i$. Isn’t the distribution of $\\beta(i)\\boldsymbol{n}_i$ the same as the distribution of $\\boldsymbol{n}_i$?", "limitations": "Limitations are discussed.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. Strong theoretical results in a very challenging setup of learning with nonlinear NNs.\n2. Novel proof. Most works consider the logistic loss without a thorough analysis of the trajectory. Here the hinge loss is considered and a detailed analysis of the trajectory is provided. The key result is a bound on the number of non-trivial updates which is independent of the total number of iterations. This is highly non-trivial: a “worst-case” dynamics can result in oscillating behavior or non-convergence. However, a clever argument is presented which derives inequalities of clean and corrupt updates that together imply convergence.  Hopefully such reasoning can be helpful in more complex settings.\n3. Full understanding of the dynamics. While the proof is lengthy, it provides a unique understanding of NN dynamics, their inner workings and the impact on generalization.\n4. The paper is mostly clearly written.\n\n", "weaknesses": "1. The theoretical result holds for a bounded number of samples (i.e., $n$ cannot go to infinity).\n2. Simple experiments which show the theoretical predictions could strengthen the paper.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and for appreciating the novel contributions of our work. We are happy to answer the questions raised.\n\n- *\"The theoretical result holds for a bounded number of samples (i.e.,  cannot go to infinity).\"* As long as $d$ scales appropriately we do not require an upper bound on $n$ for our results to hold. The assumption on $d$ is used to ensure the noise components of the data points are approximately orthogonal and is standard in the literature.\n\n- *\"Simple experiments which show the theoretical predictions could strengthen the paper.\"* We remark that preliminary experimental results are included in the supplementary materials, in particular we direct the reviewer's attention to Section G, Figures 1 and 2 and the discussion around them. For space reasons we were unable to include these in the main section of the paper.\n\n- *\"In Eq. (1) why is $\\beta(i)$ needed in the definition of $x_i$. Isn’t the distribution of $n_i$ the same as the distribution of $\\beta(i) n_i$?\"* Correct, we emphasize that this choice is for notational convenience only. Recall that we define $y_i = \\beta(i)(-1)^i$, therefore defining $x_i$ in this way means that the update to each weight, which involves terms of the form $y_ix_i$, has a neater expression as $\\beta(i)^2= 1$."}, {"review_id": "dppbQ4t9cK", "reviewer": "Reviewer_8QyX", "summary": "The paper studies training a noisy dataset with label noise using GD on a 2-layer network, without biases, and where the second layer is fixed. The main results are, that under the data distribution defined in the paper (namely, linearly separable with orthogonal noise), different types of overfitting (or no fitting) occur when changing the margin. ", "questions": "- How the results would change if the network had bias terms? or the second layer would also be trained?\n- Will the result still hold if the noise n_i are drawn from a Gaussian distribution? (or other symmetric distribution such as uniform over a sphere)\n- What should the upper bound on the loss in Theorem 3.6 be? \n", "limitations": "I think the authors adequately addressed the limitations of their work.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I think the main three results are very interesting, and shed light on the role of the margin for determining the types of overfitting which occurs. \n- AFAIK the main three results are novel, as they study benign overfitting for neural networks under hinge loss, whereas previous works either studied classification losses (e.g. log loss) or kernel methods.\n- The proof techniques also seem interesting and employ combinatorial arguments about how the iterations change the activation pattern of the network.\n- The proof intuitions are very helpful and elaborative.\n", "weaknesses": "I think overall this is a nice paper that should be accepted, however, there are some weaknesses/questions which I would be happy to see the author’s response about.\n\n- I think the main weakness of the paper is the limited and very specific setting to which it is applied. This is acknowledged by the authors, however, I still think it should be further addressed.\n- The network doesn’t contain biases and only the weights of the first layer are trained. Regarding the bias terms, I am not sure how adding them would change the results and would be happy to see the author’s comment about this.\n- Regarding the data distribution, would it be possible to achieve a similar result where the noise n_i are sampled from a Gaussian distribution? If so, I think this is a much more standard setting to study (signal plus Gaussian noise). I guess also here, the noise would be almost orthogonal to the signal v. If something breaks here (rather than just make the computations more tedious), then I think the result is very brittle since it requires the noise to be exactly orthogonal to the signal.\n- I think the paper “Benign, Tempered, or Catastrophic: A Taxonomy of Overfitting” by Mallinar et al. should also be cited, as it gives a taxonomy of the different possible types of overfitting (which is studied also here).\n- It would be nice to see an upper bound for Theorem 3.6. Currently when the margin is very small then the overfitting is either catastrophic (i.e random guess) or tempered (something between benign and catastrophic). Can the authors provide such an upper bound, or at least remark on what they think it should be? I think that it could depend on k, which depicts the noise level in the labels.\n- Small note: Assumption 1, should it be k <= n/C ?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and insightful questions which we address below.\n\n- *\"How the results would change if the network had bias terms? or the second layer would also be trained?\"* We believe our arguments can readily be extended to cover the case of bias terms and sketch some ideas as follows: a bias term is equivalent to modifying the data so that each training and test point contains an extra dimension with a fixed value of 1. One can think of the associated one hot vector as defining a common or bias component.  The effect of this change is increased correlation in the noise components, which has an effect of increasing $\\rho$.  It is possible some way to control this effect may need to be introduced, e.g. varying the norms of the noise components or the individual learning rate of the bias terms.  We note that the argument in this paper does not immediately apply when the second layer weights are trained, and we see this as a direction to be explored in future work. We remark however that fixed outer weights is also a limitation in the two benign overfitting papers we directly compare our results to, as well as the third reference Frei, Vardi, Bartlett, and Srebo suggested by the other reviewers.\n\n- *\"Will the result still hold if the noise $n_i$ are drawn from a Gaussian distribution? (or other symmetric distribution such as uniform over a sphere)\"* In short yes primarily as long as the noise distribution entails that w.h.p. the noise components of the training sample are approximately orthogonal. In Lemma C.1 in the supplementary, we derive bounds on the inner product between two training points.  These bounds, along with the conditions on $\\gamma$ and $\\rho$, are what we use to prove our key results. This lemma would hold under e.g., Gaussian or isotropic noise distribution using a sufficient concentration result. We remark in our work that we also use the norm of each data point being exactly 1, this makes the analysis easier as each point provides an exactly equivalent push to the weights of a neuron at each iteration. However, again this is an assumption we make only to simplify the argument: some variation in the norm of the data points is certainly tolerable and furthermore a concentration result will yield this in the case of a sub-gaussian noise model for instance.\n\n- *\"I think the paper “Benign, Tempered, or Catastrophic: A Taxonomy of Overfitting” by Mallinar et al. should also be cited, as it gives a taxonomy of the different possible types of overfitting\"* We thank the reviewer for highlighting this interesting and important work, we will cite it in future versions of our work. \n\n- *\"I guess also here, the noise would be almost orthogonal to the signal v. If something breaks here (rather than just make the computations more tedious), then I think the result is very brittle since it requires the noise to be exactly orthogonal to the signal.\"* As we stated in another response, the primary requirement we need is that the bounds in Lemma C.1 of the supplementary hold. These bounds can hold even in the case where the noise is not orthogonal to the signal, provided the component of the noise in the direction of the signal is not too strong.  We do note, however, that if the noise is allowed to be not orthogonal to the signal then the generalization bound in the non-benign overfitting result for small $\\gamma$ may be a consequence of the data model and not the training dynamics.\n\n- *\"It would be nice to see an upper bound for Theorem 3.6. Currently when the margin is very small then the overfitting is either catastrophic (i.e random guess) or tempered (something between benign and catastrophic). Can the authors provide such an upper bound, or at least remark on what they think it should be? I think that it could depend on k, which depicts the noise level in the labels.\"* Thanks for raising this important and challenging question. In the small $\\gamma$ regime each point is primarily fitted with respect to its noise component, the activation patterns are therefore hard to track and as a result deriving a lower bound on the projection of the weights onto the signal is challenging. We believe the reviewer is correct in their conjecture as a larger $k$ means the contributions from clean and corrupt points, which are equally likely to activate a neuron at initialization, are more likely to cancel one another out, thus resulting in a small if negligible signal component being learned by the network. We leave a more in-depth study of this issue to future work.\n\n- *\"Assumption 1, should it be $k \\leq n/C$?\"* Yes, this is a typo in the main text, thank you for highlighting!"}, {"review_id": "jXx3fnO5rE", "reviewer": "Reviewer_NX3e", "summary": "The paper studies overfitting when training shallow ReLU networks with the hinge loss using noisy data (i.e., with label flipping noise). They consider a setting where the data points consist of a direction $\\mathbf{v}$ that determines the (clean) labels, and noise from a sphere orthogonal to $\\mathbf{v}$. This distribution is similar to the two-clusters setting that has been studied in previous works [Frei et al. 2022, Xu and Gu 2023, Chatterji and Long 2021], except that the assumptions on the noise in the current work is stronger. The authors identify conditions on the signal strength that result in benign overfitting, harmful overfitting, and “non overfitting” (where only the clean training examples are classified correctly, and the test error on clean data is small). The results follow by analyzing the trajectory of gradient descent.", "questions": "See the “weaknesses” section.", "limitations": "The authors discussed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Understanding the conditions where benign overfitting occurs is an intriguing question that has be studied extensively in recent years. While the primary motivation for studying benign overfitting is to better understand interpolation learning in neural networks, most of the known results consider linear models (or kernel regression). The current paper helps understanding benign/harmful overfitting in shallow fully-connected ReLU networks trained with the hinge loss. Given our limited understanding of benign overfitting in nonlinear networks, I believe that the contribution of the current paper is significant.\n\nI did not verify the correctness of the proofs, which are in the appendix.", "weaknesses": "- Assumption 1 in the main text is different from Assumption 1 in the appendix. Specifically, condition 5 of Assumption 1 in the appendix includes a parameter $\\rho$ that does not appear in the assumption in the main text. I think that the authors should discuss the relationship between these two versions of Assumption 1. \n- Related to the above: Note that in lines 221-222 in the main text, the authors claim that the condition on the correlations between $\\mathbf{n}_i,\\mathbf{n}_l$ follows from Assumption 1 by letting $\\rho \\leq \\frac{\\gamma}{C}$. This is true if we use Assumption 1 from the appendix, but it does not follow from Assumption 1 in the main text. Please explain how/whether the proof holds using the assumption from the main text. This issue appears also in the other proof sketches.\n- The authors claim that there are only two papers about benign overfitting in nonlinear fully-connected neural networks: Frei et al. 2022, and Xu \\& Gu 2023. The authors provide a nice comparison between the current results and these prior results. It is worth noting that there is an additional prior work on benign overfitting in nonlinear fully-connected networks: “Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization” by Spencer Frei, Gal Vardi, Peter Bartlett and Nati Srebro. This paper appeared in arxiv only 2.5 months before the NeurIPS deadline, so it is reasonable that the authors were not aware of it when writing the current paper, but I think that a comparison to this paper would be helpful.\n- The writing is quite sloppy. Below I specify some typos and minor comments:\n    - Line 130, in the definition of $\\mathcal{F}^{(t)}$: should be $>0$ instead of $<1$.\n    - Line 132: “j=th”\n    - Line 155 — “constant that depends on $n,m,k,\\gamma,d$”: if we think about all of these parameters as constants, then what isn’t a constant?\n    - Line 156: (5) should be (4)\n    - Line 227: is the notation $[m]_p$ defined? Also, you probably meant $[2m]_p$.\n    - Line 385 in the appendix: “delta”\n    - The word “overfitting” sometimes means “interpolating also the noisy examples” and sometimes means “harmful overfitting”. I would write explicitly “harmful overfitting” when talking about the latter.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and thoughtful questions which we address below.\n\n- *\"Assumption 1 in the main text is different from Assumption 1 in the appendix. Specifically, condition 5 of Assumption 1 in the appendix includes a parameter that does not appear in the assumption in the main text.\"* The two assumptions labeled Assumption 1 were not supposed to be directly related, and we apologize for the confusion. Assumption 1 in the main text sketches the common setting for the three main results in the paper, while Assumption 1 in the supplementary details specific relationships between the parameters of the neural network and data model that result in our benign overfitting result. We will clarify this better in future versions.\n\n- *\"in lines 221-222 in the main text, the authors claim that the condition on the correlations between $n_i, n_l$ follows from Assumption 1 by letting $\\rho \\leq \\frac{\\gamma}{C}$. This is true if we use Assumption 1 from the appendix, but it does not follow from Assumption 1 in the main text. Please explain how/whether the proof holds using the assumption from the main text. This issue appears also in the other proof sketches.\"* We apologize for this confusion and will clarify it in future versions. In the lines in question, as well as the corresponding parts in the other proof sketches, we only mean that there exists a $\\rho$ that simultaneously satisfies $\\rho \\leq \\frac{\\gamma}{C}$ and $|\\langle n_i, n_l \\rangle | \\leq \\frac{\\rho}{1-\\gamma}$ for all $i$ and $l$.  This follows from Assumption 1 in the main text by taking $\\rho = \\frac{\\gamma}{C}$ and applying inequality (4) in Assumption 1 to Lemma B.1 in the supplementary materials.\n\n- *\"It is worth noting that there is an additional prior work on benign overfitting in nonlinear fully-connected networks: 'Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization'... it is reasonable that the authors were not aware of it when writing the current paper, but I think that a comparison to this paper would be helpful.\"* Thank you for bringing this very interesting, recent and highly relevant paper to our attention. This work studies a setting similar to that considered in the papers we make a direct comparison against. In the context of Leaky ReLU networks, this work shows that gradient flow exhibits an implicit bias towards solutions that satisfy KKT conditions. Under certain assumptions on the data, similar to those in our work and the existing literature, they are able to show that parameters satisfying the KKT points result in networks which exhibit benign overfitting. With regard to differences we remark that while we consider hinge loss the work highlighted considers an exponentially tailed loss. Furthermore while they study gradient flow we consider gradient descent.\n\n- *\"Line 155 — 'constant that depends on $n, m, k, \\gamma, d$': if we think about all of these parameters as constants, then what isn't a constant?\"* Apologies this was not well put, we mean only that $\\eta$ depends on these parameters in an as of yet unspecified way. We will clarify this in future versions.\n\n- *\"The word 'overfitting' sometimes means 'interpolating also the noisy examples' and sometimes means 'harmful overfitting'. I would write explicitly 'harmful overfitting' when talking about the latter.\"* We agree with the reviewer that this vocabulary is probably preferable to the one we used. As it currently stands we use non-benign (harmful does seem a better choice) overfitting and benign overfitting to distinguish bad interpolation from benign interpolation.  While regrettably in some instances we have used ``overfitting'' to refer to harmful overfitting, we have corrected this in our current draft.\n\n- *\"Line 155 — 'constant that depends on $n, m, k, \\gamma, d$': if we think about all of these parameters as constants, then what isn't a constant?\"* None of the listed parameters should be thought of as constant and we apologize for the confusion.  We only mean that the upper bound for $\\eta$ depends on these parameters in an unspecified way.\n\n- In regard to typos, the comments with regards to lines 130, 132, 156 and 385 are correct, we apologize for these and will fix them. In regard to line 227 it should be $[2m]$."}]

Author rebuttal:

Meta-review: In this work, a simple model of linear classification is analyzed to study the phenomenon of benign overfitting and the generalization of neural networks with noisy data. A theoretical analysis of the trajectory of GD shows that it can be in three regimes (1) benign overfitting (2) non-benign overfitting and (3) no overfitting. The analysis relies on a novel proof of the nonlinear dynamics which shows a bound on the number of non-trivial updates of GD until convergence. 

The reviewers all agree this paper makes solid contributions toward understanding benign overfitting in challenging settings, i.e., non-linear networks. This is a clear acceptance.
Decision: Accept (spotlight)