From Tempered to Benign Overfitting in ReLU Neural Networks
Authors: Guy Kornowski
Gilad Yehudai
Ohad Shamir
Venue: NeurIPS 2023 spotlight (2023)
Keywords: benign overfitting
implicit bias
interpolating predictors
neural networks
theory
TL;DR: We prove tempered and benign overfitting for ReLU NNs in various settings

Abstract: Overparameterized neural networks (NNs) are observed to generalize well even when trained to perfectly fit noisy data. This phenomenon motivated a large body of work on "benign overfitting", where interpolating predictors achieve near-optimal performance. Recently, it was conjectured and empirically observed that the behavior of NNs is often better described as "tempered overfitting", where the performance is non-optimal yet also non-trivial, and degrades as a function of the noise level. However, a theoretical justification of this claim for non-linear NNs has been lacking so far. In this work, we provide several results that aim at bridging these complementing views. We study a simple classification setting with 2-layer ReLU NNs, and prove that under various assumptions, the type of overfitting transitions from tempered in the extreme case of one-dimensional data, to benign in high dimensions. Thus, we show that the input dimension has a crucial role on the overfitting profile in this setting, which we also validate empirically for intermediate dimensions. Overall, our results shed light on the intricate connections between the dimension, sample size, architecture and training algorithm on the one hand, and the type of resulting overfitting on the other hand.

From Tempered to Benign Overfitting in ReLU Neural Networks
Guy Kornowski Weizmann Institute of Science guy, www.kkoowwiiioio.ooo wwtsskkwwwwwimmmmmmn. ac.
Gilad Yehudai
Weizmann Institute of Science
gilad yehudaihheeeeeeeeeee eeeiiieeeeiiiimme ac
Ohad Shamir
Weizmann Institute of Science ohad, shami r &eei zmann. ac
Abstract
Overparameterized neural networks (NNs) are observed to generalize well even when trained to perfectly fit noisy data. This phenomenon motivated a large body of work "benign overfitting" where interpolating predictors achieve near- optimal performance. Recently, it was conjectured and empirically observed that the behavior of NNs is often better described "tempered overfitting", where the performance non-optimal yet also non-trivial, and degrades as a function of the noise level. However, theoretical justification of this claim for non-linear NNs has been lacking so far. In this work, we provide several results that aim bridging these complementing views. We study a simple classification setting with 2-layer ReLU NNs, and prove that under various assumptions, the type of overfitting transitions from tempered in the extreme case of one-dimensional data, to benign in high dimensions. Thus, we show that the input dimension has crucial role on the overfitting profile in this setting, which we also validate empirically for intermediate dimensions. Overall, our results shed light on the intricate connections between the dimension, sample size, architecture and training algorithm on the one hand, and the type of resulting overfitting on the other hand.
Introduction
Overparameterized neural networks (NNs) are observed to generalize well even when trained to perfectly fit noisy data. Although quite standard in deep learning, the so-called interpolation learning regime challenges classical statistical wisdom regarding overfitting, and has attracted much attention in recent years.
In particular, the phenomenon commonly referred to as "benign overfitting" [Bartlett et al., 2020] describes a situation in which learning method overfits, in the sense that it achieves zero training error over inherently noisy samples, yet it is able to achieve near-optimal accuracy with respect to the underlying distribution. So far, much of the theoretical work studying this phenomenon focused on linear (or kernel) regression problems using the squared loss, with some works extending this to classification problems. However, there is naturally much interest in gradually pushing this research towards neural networks. For example, Frei et al. [2023] recently showed that the implicit bias of rradient-based training algorithms towards margin maximization, established in series of works throughout the past few years, leads to benign overfitting of leaky ReLU networks high dimensions (see discussion of related work below).
Recently, Mallinar et [2022] suggested a more nuanced view, coining the notion of "tempered" overfitting. An interpolating learning method is said to overfit in tempered manner if its error (with
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

respect to the underlying distribution, and as the training sample size increases) is bounded away from the optimal possible error yet also not "catastrophic", e.g,, better than a random guess. To be more concrete, consider a binary classification setting (with labels in [+1)), and data distribution D, where the output labels correspond to some ground truth function f belonging to the predictor class of interest, corrupted with independent label noise at level p E (0, } (i.e., given sampled point x, its associated label y equals sign(f (f (x)) with probability 1 1- p. and sign(f((x) with probability p). Suppose furthermore that the training method is such that the learned predictor achieves zero error on the (inherently noisy) training data. Finally, let Let denote the "clean" test error, namely La(N)= Pix~D((NXx) (x) I 0) for some predictor N (omitting the contribution of the label noise). In this setting, benign, catastrophic or tempered overfitting corresponds to a situation where the clean test error Lei of the learned predictor approaches 0. 2. or some value in (0, 2) respectively. In the latter case, the clean test error typically scales with the amount of noise p. For example, for the one-nearest-niighhor algorithm, it is well-known that the test error asymptotically converges to 2p(1 p) in our setting [Cover and Hart, 1967], which translates to a clean test error of p. Mallinar et al. [2022] show how a similar behavior (with the error scaling linearly with the noise level) occurs for kernel regression, and provided empirical evidence that the same holds for neural networks.
The starting point of our paper is intriguing experiment from that paper (Figure 6b), where they considered the following extremely simple data distributioin: The inputs are drawn uniformly at random from the unit sphere, and f* is the constant +1 function. This is perhaps the simplest possible setting where benign or tempered overfitting in binary classification may be studied. In this setting, the authors show empirically that a three-layer vanilla neural network exhibits tempered overfitting, with the clean test error almost linear in the label noise level p. Notably, the experiment used an input dimension of 10, which is rather small. This naturally leads to the question of whether can rigorously understand the overfitting behavior of neural networks in this simple setup, and how problem parameters such as the input dimension, number of samples and the architecture affect the type of overfitting.
Our contributions: In this work we take a step towards rigorously understating the regimes under which simple, 2-layer ReLU neural networks exhibit different types of overfitting (i.e. benign, catastrophic or tempered), depending on the problem parameters, for the simple and natural data distribution described in the previous paragraph. We foeus on interpolating neural networks trained with ssponentially-talees losses, which are well-known to converge to KKT points of a max-margin problem (see Section for more details). At a high level, our main conclusion is that for such networks, the input dimension plays crucial role, with the type of overfitting gradually transforming from tempered to benign as the dimension increases. In contrast, most of our results are not sensitive to the network's 's width, as long as it is sufficient to interpolate the training data. In a bit more detail, our contributions can be summarized as follows:
Tempered overfitting in one dimension (Theorem 3.1 and Theorem 3.2). We prove that in one dimension (when the imputs are uniform over the unit interval), the resulting overfitting is provably tempered, with a clean test error scaling as (poly(p)). Moreover, under the stronger assumption that the algorithm converges to local minimum of the max-margin problem, we show that the clean test error provably scales linearly with p. As far as we know, this is the first result provably establishing tempered overfitting for non-linear neural networks.
Benign overfitting in high dimensions (Theorem 4.1 and Theorem 4.3). We prove that when the inputs are sampled uniformly from the unit sphere (and with the dimension scaling polynomially with the sample size), the resulting overfitting will generally be benign. In particular, we show that convergence to a max-margin predictor (up to some constant factor) implies that the clean test error decays exponentially fast to O with respect to the dimension. Furthermore, under an assumption on the scaling of the noise level and the network width, we obtain the same result for any KKT point of the max-margin problem.
The role of bias terms and catastrophic overfitting (Section 4.2). The proof of the results mentioned earlier crucially relied on the existence of bias parameters in the network architecture. Thus, we further study the case of bias-less network, and prove that without such biases, neural networks may exhibit catastrophic overfitting, and that in general they do not overfit benignly without further assumptions. We consider this an interesting illustration of how catastrophic overfitting is possible in neural networks, even in our simple setup.
2

---

Empirical study for intermediate dimensions (Section 5). Following our theoretical results, we attempt at empirically bridging the gap between the one-dimensional and high dimensional settings. In particular, it appears that the tempered and overfitting behavior extends to wider regime than what our theoretical results formally cover, and that the overfitting profile gradually shifts from tempered to benign as the dimension increases. This substantially extends the prior empirical observation due to Mallinar et al. [2022, Figure 6b], which exhibited tempered overlitting in input dimension 10.
We note that in independent and concurrent work, Joshi al. [2023] studied ReLU neural networks with one- mee-immensional inputs, similar to the setting we study in Section 3, and proved that tempered and catastrophic overfitting can occur for possibly non-constant target functions, depending on the loss function. However, they focus on a regression setting, and on min-norm predictors, whereas our results cover classification and any KKT point of the max-magin problem. Moreover, the architecture considered differs somewhat from our work, with Joshi et al. including an untrained skip connection and untrained bias term.
1.1 Related work
Following the empirical observation that modern deep learning methods can perfectly fit the training data while still performing well on test data [Zhang et al., 2017], many works have tried to provide theoretical explanations of this phenomenon. By now the literature on this topic is quite large, and we will only address here the works most relevant to this paper (for a broader overview, see for example the surveys Belkin 2021, Bartlett et al. 2021, Vardi 2022).
There are many works studying regression settings in which interpolating methods, especially linear and kernel methods, succeed at obtaining optimal or near-optimal performance [Belkin et al., 2018a,b, 2019, 2020, Mei and Montanari, 2022, Hastie et al., 2022]. In particular, it is interesting to compare our results to those of Rakhlin and Zhai [2019], Beaglehole et al. [2023], who proved that minimal norm interpolating (i.e. "ridgeless") kernel methods are not consistent in any fixed dimension, while they can be whenever the dimension scales with the sample size (under suitable assumptions) [Liang and Rakhlin, 2020]. Our results highlight that the same phenomenon occurs for ReLU networks.
There is by now also a large body of work on settings under which benign overfitting (and analogous definitions thereof) occurs [Nagarajan and Kolter, 2019, Bartlett al., 2020, Negrea et al., 2020, Nakkiran and Bansal, 2020, Yang et al., 2021, Koehler et al., 2021, Bartlett and Long, 2021, Muthuku- mar al., 2021, Bachmann et al., 2021, Zhou et al., 2023, Shamir, 2023]. In classification settings, as argued by Muthukumar et al. [2021], many existing works on benign overfitting analyze settings in which max-margin predictors can be computed (or approximated), and suffice to ensure benign behavior [Poggio and Liao, 2019, Montanari et al., 2019, Thrampoulidis et al., 2020, Wang and Thrampoulidis, 2021, Wang et al., 2021, Cao et al., 2021, Hu et al., 2022, McRae et al., 2022, Liang and Recht, 2023]. It is insightful to compare this to main proof strategy, in which max- max--margin problem in the case of NNs (which no longer admits a closed form). Frci et al. [2022] showed that NNs with smoothed leaky ReLU activations overfit benignly when the data comes from well-seperated mixture distribution, a result which was recently generalized to ReLU activations [Xu and Gu, 2023]. Similarly, Cao et al. [2022] proved that convolutional NNs with smoothed activations overfit benignly when the data is distributed according to a high dimensional Guassian with noisy labels, which was subsequently generalized to ReLU CNNs [Kou et al., 2023]. We note that these distributions are reminiscent of the setting we study in Section 4 for (non convolutional) ReLU NNs. Chatterji and Long [2023] studied benign overfitting for deep linear networks.
analyze the
As mentioned in the introduction, Mallinar et al. [2022] formally introduced the notion of tempered overfitting and suggested the study of it in the context of NNs. Subsequently, Manoj and Srebro [2023] proved that the minimum description length learning rule exhibits tempered overfitting, though noticeably this learning rule does not explicitly relate to NNs. As previously mentioned, we not aware of existing works that prove tempered overfitting in the context of NNs.
In parallel line of work, the implicit bias of gradient- based training algorithms has received much attention [Soudry et al., 2018 Lyu and Li, 2020, Ji and Telgarsky, 2020j. Roughly speaking, these results drew the connection between NN training to margin maximization see Section 2 for formal reminder. For our first result (Theorem 3. we build upon the analysis of Safran et al. [2022] who studied this implicit bias for univariate inputs, though for the sake of bounding the number of linear
3

---

regions. In our context, Frei et al. [2023] utilized this bias to prove benign overfitting for leaky ReLU NNs in a high dimensional regime.
2 Preliminaries
Notation. We use bold-faced font to denote vectors, e.g. x E IR and denote by ||x]] the Euclidean norm. We use e, C, C > etc. to denote absolute constants whose exact value can change throughout the proofs. We denote by [n] == {I....,, n). by 1 } the indicator function, and by gd-1 C Rd the unit sphere. Given sets A C B, we denote by Uni((A) the uniform measure over a set A, by A the complementary set, and given a function f B - we denote its restriction fla - R. We let be the identity matrix whenever the dimension is clear from context, and for a matrix A we denote by ||A]] its spectral norm. We use stadard big-O notation, with O(+), Q(()) and (-) hiding absolute constants, write f S g if f O(g), and denote by poly(-) polynomial factors.
Setting. We consider a classification task based on noisy training data S (x;; y1 C R x {+1} drawn i.idd. from underlying distribution D = Dx x Dy, Throughout, we assume that the output values y are constant +1, corrupted with independent label noise at level p (namely, each ys is
independent of and satisfies Pr(y = =] = p, Pr[m = -1] p)) Note that the Bayes-optimal predictor in this setting is f = 1. Given a dataset S, we denote by 1 == {i E [m] y = 1} and
I_ = {i E [m] y -13. We study 2-layer ReLU networks:
n
Nx(x)= Σ eojo(w x x bz),
where n the number of neurons or network width, (2) == max 2} is the ReLU function, vy.b, by R. W, E Ed and 0 (uy, w,, by); ( [d++))n is a vectorized form of all the parameters. Throughout this work we assume that the trained network classifies the entire dataset correctly, namely y: (x;) > 0 for all i [m]. Following Mallinar et al. [2022, Section 2.3] we consider the clean test error
(N) Pr (N) < 0]. x>Dxx
correspouding to the misclassification error with respect to the clean underlying distribution. It is said that No exhibits benign overfitting if Let -> O with respect large enough problem parameters (e.g. m. d + oo), while the overfitting is said to be catastrophic if La + 2. Formally, Mallinar et al. [2022] have coined tempered overfitting to describe any case in which Lej converges
value in (0, }). though special attention has been given in the literature to cases where Lat scales monotonically or even linearly with the noise level p [Belkin et al., 20181 Rb, Chatterji and Long, 2021, Manoj and Srebro, 2023].
Implicit bias. We will now briefly describe the results of Lyu and Li [2020]. Ji and Telgarsky [2020] which shows that under our setting, training the network with respect the logistic or exponential loss converges towards a KKT point of the margiin-aaiiizatiion problem. To that end, suppose {(z) =
log(1 + e or {(=) e== and consider the empirical loss L(()- > No Suppose
that (t) evolves according to the gradient flow the empirical loss, namely de
de(() = ((((
Note that this corresponds to performing gradient descent over the data with an infinitesimally small
step size.
Theorem 2.1 (Rephrased from Lyu and Li, 2020, Ji and Telgarsky, 2020). Under the setting above,
there exists some to such that (tt) satisfies min [mn] (:) (x4) > then o(t) [0(A]]
0 for
which is a KKT point of the margin maximization problem
min
0
s.t.
Ye No,o 21
Vi E [m]
Note that the ReLU function is not differentiable at This can addressed either by setting o0()) E [o, 1] as done in practical implementations, or by considering the Clarke subdifferential [Clarke, 1990] (see Lyu and Li, 2020, Dutta et al., 2013 for discussion on on our results.
optimization). We note that this issue has no effect

---

The result above shows that although there are many possible parameters O that result in network correctly classifying the training data, the training method has an implicit bias in the sense that yields a network whose parameters are KKT point of Problem (1). Recall that 0 is called a KKT point of Problem (1) if there exist A1, ...,,..,,... Am E R such that the following conditions hold:
Σ Ary VoNo(())
(stationarity)
(2)
Vi E [m]: )x,Vo(x;)) 2
(primal feasibility)
(3)
A Am 2 0
(dual feasibility)
(4)
Vi E [m]: (xx,) 1)
(complementary slackness)
It is well-known that global or local optima of Problem (1) are KKT points, but in general, the reverse direction may not be true, even our context of 2-layer ReLU networks (see Vardi et al., 2022). In this work, our results rely either on convergence to a KKT point (Theorem 3.1 and Theorem 4.3), or on stronger assumptions such as convergence to local optimum (Theorem 3.2) or near-global optimum (Theorem 4.1) of Problem (1) in order to obtain stronger results.
3 Tempered overfitting in one dimension
Throughout this section we study the one dimensional case d = 1 under the uniform distribution D₂ = [ni 1)), so that Let (No) = Prg--Cni(((o11) [No S 0]. We note that although we focus here the uniform distribution for simplicity, our proof techniques are applicable in principle to other distributions with bounded density. Further note that both results to follow are independent of the number of neurons, so that in setting, tempered overfitting occurs soon as the network is wide enough to interpolate the data. We first show that any KKT point of the margin maximization problem (and thus any network
may converge to) gives rise to tempered overfitting.
Theorem 3.1. Let d = I, p E [0, })) Then with probability at least - 8 over the sample S ~ D for any KKT point = (Ug, wy, b of Problem (I), holds that
(
log(m/6) m
S Lei (No) SC (N
(v++//
log(m/
m
where c, C are absolute constants.
The theorem above shows that for a large enough sample size La((N) (poly(p)), proving that the clean test error must scale roughly monotonically with the noise level p, leading to tempered overfitting.
We will now provide intuition for the proof of Theorem 3.1, which appears in Appendix A.1. The proofs of both the lower and the upper bounds rely on the analysis of Safran et al. [2022] for univariate networks that satisfy the KKT conditions. For the lower bound, we note that with high probability over the sample (r:)m² ~ D approximately p'm m of the sampled points will be part of a sequence of 5 consecutive points I; < ... < Fi+4 all labeled 1I Based on a lemma due Safran al. [2022], we show any such sequence must contain segment [ı. 11+ i S j S i 3 for which No Noltzy.2511] < O, contributing to the clean test error proportionally to the length of 21 Under the probable event that most samples are not too close to one another, namely of distance (211m) we get that the total length of all such segments (and hence the error) is at least of order 2( (mm"" R(p²).
As to the upper bound, we observe that the number of neighboring samples with opposing labels is likely to be on order of pm, which implies that the data can be interpolated using a network of width of order n² (pm). We then invoke a result of Safran et al. [2022] that states that the class of interpolating networks that satisfy the KKT conditions has VC dimension dyc = O(n") O(pm). Thus, standard uniform convergence result for VC classes asserts that the test error would be of order m Σie(m) 1 (sig # yi + O ((/v///m) = 0 O ((vpm(/mm pm pm/m)= ((PP).
We remark that the additional summands are merely matter of concentration in order to get high probability bounds. As for the expected clean test error, our proof readily shows that cp² < Es-Dm [Na()o) C.p.
5

---

While the result above establishes the overfitting being tempered with an error scaling as poly(p), we note that the range [cp², Cypl is rather large. Moreover, previous works suggest that in many cases we should expect the clean test error to scale linearly with p [Belkin et al., 201 8b, Chatterji and Long, 2021, Manoj and Srebro, 2023). Therefore it is natural to conjecture that this also true here, at least for trained NNs that we are likely to converge to. We now turn to show such result under a stronger assumption, where instead of any KKT point of the margin maximization problem, we consider specifically local minima. We note that several prior works have studied networks corresponding to global minima of the max-margin problem. which is of course an even stronger assumption than local minimality (e.g. Savarese et al., 2019, Boursier and Flammarion, 2023). We say that @ is a local minimum of Problem (1) whenever there exists r > 0 such that if ||0' - 0|| <r and Vi E [m]] No (z:) 2 1 then ||012 S 1|0"
Theorem 3.2. Let d = 1. p E [0, 5) Then with probability at least 1 - 8 over the sample S ~ D for any local minimum 0 (ug, Wj, ba)3=1 of Problem (1), it holds that
log mm/)) p
c(p+
log(m/0)
S Tad (No) S SC p+1
m
m
where c, C > O are absolute constants.
The theorem above indeed shows that whenever the sample size is large enough, the clean test error indeed scales linearly with p. The proof of Theorem 3.2, which appears in Appendix A.2, is based on different analysis than that of Theorem 3.1. Broadly speaking, the proof relies on analyzing the structure of the learned prediction function, assuming it a local minimum of the max-man max-margin problem. More specifically, in order to obtain the lower bound we consider segments in between
samples z;-1 < Z2 < Ti+1 that are labeled y = 3/; = -1, Vi-1 = 1. Note that with high probability over the sample, approximately p(1 p)² = (2()) of the probability mass lies in such segments. Our key proposition is that for a KKT point which is local minimum, No(-) must be linear on the segment [xr,, 1.] and furthermore that No(x;,) -1, (1(41)1)
1. Thus, assuming the points are not too unevenly spaced, it follows that a constant fraction of any such segment contributes to the clean test error, resulting in overall error of 32()). In order to prove this proposition, provide an exhaustive list of cases in which the network does not satisfy the assertion, and show that in each case the norm can be locally reduced see Figure 3 in the appendix for an illustration.
For the upper bound, a similar analysis is provided for segments [z., 2++1] for which yi = Vi+1 = 1. Noting that with high probability over the sample an order of (1 - p)² = 1 - O(p) of the probability mass lies in such segments, it suffices to show that along any such segment the network is positive implying upper bound of Opp) the possible clean test error. Indeed, we show that along such segments, by locally minimizing parameter norm the network is incentivized to stay positive.
[
Benign overfitting in high dimensions
In this section we focus on the high dimensional setting. Throughout this section we assume that the dataset is sampled according to Dx = (n and d > m, where m is the number of samples, S 0j. We note that our results hold for other commonly
so that Lai (No) P studied distributions (see Remark 4.2). We begin by showing that if the network converges to the maximum margin solution up some multiplicative factor, then benign overfitting occurs:
Theorem 4.1. Let e, > O. Assume that p S C1. m 2 C2 log(1/6) and d Z cam? log ( (m) log (7)
for some universal constants 61, C2 C3 > O. Given a sample (x,, D:) m ~ D suppose 0 = (Wy, Uy, b,)3-1 a KKT point of Problem (1) such that ||012 S S
vF 11 where 0* is max-margin solution of Eg. (1) and C4 > 0 is some universal constant. Then, with probability at least 1 - 8 over S ~ Dm we have that Les (Na) S.
The theorem above shows that under the specified assumptions, benign overfitting occurs for any noise level p which is smaller than some universal constant. Note that this result is independent of
NNote that this is merely the standard definition of local minimality of the Euclidean norm function, under the constraints imposed by interpolating the dataset. 'Similarly to footnote 2, our proof also characterizes the expected clean test error for any sample size as Es-pm [La(No)] ((p).

---

the number of neurons and requires d = =m The mild lower bound on m is merely to ensure that the negative samples concentrate around a (pp) fraction of the entire dataset. Also note that the dependence on is only logarithmic, which means that in the setting we study, the clean test error decays exponentially fast with d.
We now turn to provide a short proof intuition, while the full proof can be found in Appendix B.I. The main crux of the proof is showing that Σj- (b,) = Q2(1, i.e. the bias terms are the dominant factor in the output of the network, and they tend towards being positive. In order to see why this suffices to show benign overfitting, first note that (x) = 2ド=1 (W x + by) equals
ugo(w] xb)) Σ ryolby))
Σ (b)o(b,)) 2
Σ (o)l
Σ [ujo(w]
All the samples (including the test sample x) are drawn independently from Unif(8 thus with high probability |x x = (1(1) for all i E [mm]. Using our assumption regarding convergence to the max-margin solution (up to some multiplicative constant), we show that the norms |/w are bounded by some term independent of d. Thus, we can bound |x w, or for every j E [n]] Additionally, by the same assumption we show that both Σك=1 ||y and ΣØ=1 e2yl are bounded by the value of
the max- max-margin solution (up multiplicative factor), which we bound by O(ym). Plugging this into the displayed equation above, and using the assumption that d is sufficiently larger than m, we get that the Σラ= [w) J x)] term is negligible, and hence the bias terms Σラ= (bg(bb) the predominant factor in determining the output of No.
Showing that Σn (b,) (1) is done in two phases. Recall the definitions of / == {i E [m] 5 -1 [m]] : y; = 11, and that by our label distribution and assumption on p we have p)m > pm x [__]. We first show that if the bias terms are too small, and the predictor 4+
correctly classifies the training data, then its parameter vector O satisfies ||0||2 = (2((+)). Intuitively, this is because the data is nearly mutually orthogonal, so if the biases are small, the vectors w, must have a large enough correlation with each different point in 7 to classify it correctly. On the other hand, explicitly construct a solution that has large bias terms, which satisfies |00| O(I--))
By setting p small enough, we conclude that the biases cannot be too small.
Remark 4.2 (Data distribution). Theorem 4.1 is phrased for data sampled uniformly from unit sphere, but can be easily extended to other isotropic distributions such as standard Gaussian and uniform over the unit ball. In fact, the only properties of the distribution we use are that |x] X5 o1(1) for every i # [m], and that |XXX || = O(1) (independent of m) where X is m x d matrix whose rows are X5.
4.1 Benign overfitting under KKT assumptions
In Theorem 4.1 we showed that benign overfitting occurs in high dimensional data, but under the strong assumption of convergence to the max- max-margin solution up to a multiplicative factor (whose value is allowed to be larger for smaller values of p). On the other hand, Theorem 2.1 only guarantees convergence to a KKT point of the max-margin problem (1). We note that Vardi al. [2022] provided
several examples of ReLU neural networks where there are in fact KKT points which are not a global or even local optinum of the max-margin problem.
Consequently, in this section we aim at showing a benign overfitting result by only assuming convergence to a KKT point of the max- max-margin problem. For such a result we use two additional assumptions, namely: (1) The output weights vj are all fixed to be =1, while only (w,, by) b)) are trained;' and (2) Both the noise level and the input dimension d depend on n, the number of neurons. Our main result the following:
Theorem 4.3. Let c,6 >
O. Assume that p S n m 2 cnn log (?) and d >
m² for some universal constants C1 C2,02,00 C3 O. Assume that the output weights are fixed so that [ij U3 11H- [i 0; = -11 while (wj. by)je(n) are trained, and that No converges to a KKT point of Problem (1). Then, with probability least 1 over S ~ Dmm we have Le (No) <
cym log log
'This assumption appears in prior works such as Cao et al. [2022], Frei et al. [2023], Xu and Gu [2023], and is primarily used to simplify the analysis.
7

---

Note that contrary to Theorem 4.1 and to the results from Section 3, here there is a dependence on n. the number of neurons. For n (11) we get benign overfitting for any p smaller than a universal constant. This dependence is due to technical limitation of the proof (which we will soon explain), and it would be interesting to remove in future work. The full proof can be found in Appendix B.2, and here we provide a short proof intuition.
The proof strategy is similar to that of Theorem 4.1, by showing that (50(b)))))))) Q(1), i.e the bias terms are dominant and tend towards being positive. The reason that this suffices is proven using similar arguments to that of Theorem 4.1. The main difficulty of the proof is showing that دド= Uj0 (by) = R(1). We write each bias term as bj Uy Σie[m] A where diy 1 x, + bj > 1) is the derivative of the j-th ReLU neuron at the point x, We first show that all the bias terms by are positive (Lemma B.5) and that for each E 4+, there is j E (......n//2) This means that it suffices show that X is not too small for all E 4+, while for every i E T_, X; is bounded from above.
with of
We assume towards contradiction that the sum of the biases is small, and show it implies that I, and 0 = O(1) for i E I_ Using the stationarity condition we can write for X; (+) for i
j E (L.....n/2) that w = =i== A Taking some r E L4, we have that w w/ x, = X since x, is almost orthogonal all other samples in the dataset. By the primal feasibility condition (Eq. (3)) No(x)) 2 1, hence there must be some j E (1..... n/2} with o 1 and with A that is larger than some constant. The other option that the bias terms are large, which we assumed does not happen. Note that we don't know how many neurons w, there are with dj,,- = 1, which means that we can only lower bound X by a term that depends on n2.
To show that A, are not too big for E 7_, we use the complementary slackness condition (Eq. (5)) which states that if X * then Nx(),) 1. Since the sum of the biases is not large, then if there exists some s E I_ with A, that is too large we would get that (x,).) < -1 which contradicts the complementary slackness. Combining those bounds and picking p to be small enough shows that Zj=1 (b;) cannot be too small.
4.2
The role of the bias and catastrophic overfitting in neural networks
In both our benign overfitting results (Theorem 4.1 and Theorem 4.3), our main proof strategy was showing that if p is small enough, then the bias terms tend to be positive and dominate over the other components of the network. In this section we further study the importance of the bias terms for obtaining benign overfitting, by examining bias-less ReLU networks of the form (x = Ej=1 " x) where = (vj, wj)je(nj We note that if the input dimension is sufficiently large and n > 2, such bias-less networks can still fit any training data. The proofs for this section can be found in Appendix C.
We begin by showing that without bias term and with no further assumption on the network width, any solution can exhibit catastrophic behaviour:
Proposition 4.4 (Catastrophic overfitting without bias). Consider bias-less network with 2 which classifies a dataset correctly. If the dataset contains at least one sample with a negative label, then Let (No) 2 z.
While the result above is restricted to any network of width two (in particular, it holds under any assumption such as convergence to a KKT point), this already precludes the possibility of achieving either benign or tempered overfitting without further assumptions on the width of the network in contrast to our previous results. Furthermore, we next show that in the bias-less case, the clean test error is lower bounded by some term which depends only on n (which again, holds for any network so in particular under further assumptions such as convergence to a KKT point).
1 Proposition 4.5 (Not benign without bias). For any bias-less network of width n, Le (No) 2 2n
Note that the result above does not depend on m nor on d, thus we cannot hope to prove benign overfitting for the bias-less case unless n is large, or depends somehow on both mn and d. We emphasize that Proposition 4.5 does no subsume Proposition 4.4 although they appear to be similar. Indeed, for the case of 2, Proposition 4.5 provides bound of which does not fall under the definition of catastrophic overfitting, as opposed to Proposition 4.4. Next. we show that even for
8

---

arbitrarily large n (possibly scaling with other problem parameters such as m, d), there are KKT points which do not exhibit benign overfitting:
Proposition 4.6 (Benign overfitting does not follow from KKT without bias). Consider bias-less network, and suppose that x] x; for every + j. Denote 1_ == Ki [m] yi = -11. Then
there exists KKT point of Problem (1) with Lel (Ne) 2 2 21'-1"
The result above shows that even if we're willing to consider arbitrarily large networks, there still exist KKT points which do not exhibit benign overfitting (at least without further assumptions on the data). This implies that positive benign overfitting result in the bias-less case, all possible, cannot possibly apply to all KKT points so one must make further assumptions on which KKT points consider or resort an alternative analysis. The assumption that x, x; for every i # is made to simplify the construction of the KKT point, while we hypothesize that the proposition can be extended to the case where X; Unif(S (or other isotropic distributions) for large enough
Between tempered and benign overfitting for intermediate dimensions
In Section 3, we showed that tempered overfitting occurs for mee-imensioonll data, while in Section we showed that benign overfitting occurs for high-dimensionall data. In this section we complement these results by empirically studying intermediate dimensions and their relation to the number of samples. Our experiments extend an experiment from [Mallinar et al., 2022, Figure 6b] which considered the same distribution as we do, for d 10 and varying from 300 3.6 10 Here we study larger values of d, and how the ratio between d and m affects the overfitting profile. We also focus on 2-layer networks (although we do show our results may extend depth 3).
In our experiments, we trained fully connected neural network with will be specified later) and ReLU activations. We sampled dataset (x;, y ~ Unif(gd-1) D, for noise level p E {0.05, 0.1, 0.5]. We trained the network using SGD with a constant learning rate of 0.1, and with the logistic (cross-entropy) loss. Each experiment ran for total of 20k epochs, times with different random seeds, the plots are averaged over the runs. In all of our experiments, the trained network overfitted in the sense that it correctly classified all of the (inherently noisy) training data. Furthermore, we remark that longer training times (100k epochs) were also examined, and the results remained unaffected, thus omit such plots.
layers, width (which
and was repeated
500 samples
2000 samples
Input dimension
0.5
Inp ámersion
10000
10000
5000
2000
Clean taxt eiror
0.4
2000
1000
Clean text
xmy
0.3
xmy
0.2
0.2
0.2
0.2
0.3
Noise level ('p")
Noise level ("p")
Figure 1: Training a 2-layer network with 1000 neurons on m samples drawn uniformly from Sd-1 for varying input dimensions d. Each label is equal to -1 with probability p and +1 with probability (1 - p). Left: m 500, Right: m 2000. The line corresponding to the identity function y = x was added for reference. Best viewed in color.
In Figure we trained 2-layer network with 1000 neurons over different input dimensions, with m 500 samples (left) and m 2000 samples (right). There appears be a gradual transition from tempered overfitting (with clean test error linear in p) to benign overfitting (clean test eπrr close to 0 for any p), as d increases compared m. Our results indicate that the overfitting behavior is close to tempered/benign in wider parameter regimes than what our theoretical results formally cover (d = 1 vs. > m²). Additionally, benign overfitting seems to occur for lower values of p. whereas for closer to 0.5 the clean test error is significantly above 0 even for the highest dimensions examined.

---

Varying Width
Depth 3
Input amersion
10000
Clean test arror
0.4
Clean test error
0.4
2000
nw3300
0.3
xey
0.3
x-y
0.2
0.3
0.2
0.3
0.4
0.1
Nolse level ("p")
Noise level ("p")
Figure 2: Left: 2-layer network with n and 3000 neurons and varying input dimension. Right: 3-layer network with n = 1000 neurons and varying input dimension. Both plots correspond m 500 samples.
We further experimented on the effects of the width and depth on the overfitting profile. In Figure 2 (left) we trained a 2-layer network on = 500 samples with input dimension d E {250, 2000, 10000} and n neurons for E {50, 3000]. It can be seen that even when the number of neurons vary significantly, the plots remain almost the same. It may indicate that the network width has little effect on the overfitting profile (similar most of our theoretical results), and that the dependence on in Theorem 4.3 is an artifact of the proof technique (in accordance with our other results). In Figure 2 (right) we trained a 3-layer neural networks on m 500 samples, as opposed to a 2-layer networks in all our other experiments. Noticeably, this plot looks very similar to Figure (left) which may indicate that our observations generalize deeper networks.
Discussion
In this paper, focused classification setting with 2-layer ReLU neural networks that interpolate noisy training data. We showed that the implicit bias of gradient based training towards margin maximization yields tempered overfitting in low dimensional regime, while causes benign overfitting in high dimensions. Furthermore, we provide empirical evidence that there is a gradual transition from tempered benign overfitting the input dimension increases.
Our work leaves open several questions. A natural follow-up is to study data distributions for which results do not apply. While analysis in dimension is readily applicable for other distributions, it is currently not clear how to extend the high dimensional analysis to other data distributions (in partieular, to settings in which the Bayes-optimal predictor is not constant). Moreover, establishing formal results in any constant dimension larger than 1, or whenever the dimension scales sub-quadratically (e.g., linearly) with the number of training samples, is interesting open problem which would likely require different proof techniques.
At technical level, there is the question of whether assumptions be relaxed. In particular, Theorem 3.2 provides a tight bound under the assumption of convergence to a local minimum of the margin maximization problem, whereas Theorem 3.1 only requires convergence to a KKT point, yet leaves a polynomial gap. Similarly, Theorem 4.1 and Theorem 4.3 require the noise level and width, respectively.
assumptions the predictor norm
Our work also leaves open a more thorough study different architectures and their possible effect on the type of overfitting, In particular, we note that our results suggest that as long as the network large enough to interpolate, the width plays minor role our studied setting - which we also empirically observe. On the other hand, whether this also holds for other architectures, well the role depth altogether, remains unclear. Finally, it would be interesting to further study the bias-less case and assess its corresponding overfitting behavior under suitable assumptions.
Acknowledgments and Disclosure of Funding
We thank Gal Vardi for insightful discussions regarding the implicit bias of neural networks. This research is supported in part by European Research Council (ERC) grant 754705.
10

---

References
Gregor Bachmann, Seyed-Mohsen Moosavi-Dezfooli; and Thomas Hofmann. Uniform convergence, adversarial spheres and simple remedy. In International Conference on Machine Learning, pages 490-499. PMLR, 2021.
Keith Ball. An elementary introduction to modern convex geometry. Flavors of geometry, (1-588)): 26, 1997.
Peter L Bartlett and Philip M Long. Failures of model-dependent generalization bounds for least-norm interpolation. The Journal of Machine Learning Research, (2(()))977991111 2021.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):00033-30070 2020.
Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: statistical viewpoint.
Acta numerica, 30:87-201, 2021.
Daniel Beaglehole, Mikhail Belkin, and Parthe Pandit. On the inconsistency of kernel ridgeless regression in fixed dimensions. SIAM Journal on Mathematics of Data Science, 5(4):854-872, 2023.
Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. Acta Numerica, 30:203-248, 2021.
Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. Advances in neural information processing systems, 31, 2018a.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In International Conference on Machine Learning, pages 541-549, PMLR, 2018b.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias variance trade-off. Proceedings of the National Academy of Sciences, 116(32)115849-15533 15854, 2019.
158544
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4):1167-1180) 2020.
Etienne Boursier and Nicolas Flammarion. Penalising the biases in norm regularisation enforces sparsity, arXiv preprint arXiv:2303. 013333 2023.
Yuan Cao, Quanquan Gu, and Mikhail Belkin. Risk bounds for over-parameterized maximum margin classification on sub-gaussian mixtures. Advances in Neural Information Processing Systems, 34: 8407-8418, 2021.
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 S Chatterji and Philip M Long. Finite-sample analysis of interpolating linear classifiers in the overparameterizeed regime. The Journal of Machine Learning Research, 22(1):521-55700, 2021.
Niladri S Chatterji and Philip M Long. Deep linear networks benignly overfit when shallow do. Journal of Machine Learning Research, 24(117):1-33 2023.
F. H. Clarke. Optimization and Nonsmooth Analysis. SIAM, 1990.
Thomas Cover and Peter Hart. Nearest neighbor pattern classification. IEEE transactions on information theory, 13(1):21-27, 1967.
Joydeep Dutta, Kalyanmoy Deb, Rupesh Tulshyan, and Ramnik Arora. Approximate kkt points and proximity measure for termination. Journal of Global Optimization, 1664):1463-1499, 2013.
11

---

Spencer Frei, Niladri S Chatterji, and Peter Bartlett. Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory, pages
PMLR, 2022.
Spencer Frei, Gal Vardi, Peter L Bartlett, and Nathan Srebro. Benign overfitting in linear clas- sifiers and leaky relu networks from kkt conditions for margin maximization. arXiv preprint arXiv:2303.01462 2023.
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.
Lars Holst. On the lengths of the pieces stick broken at random. Journal of Applied Probability, (733)623-6344 1980.
Tianyang Hu, Jun Wang, Wenjia Wang, and Zhenguo Li. Understanding square loss in training overparametrized neural network classifiers. Advances Neural Information Processing Systems, 35:16495-16508, 2022.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. Advances in Neural Information Processing Systems, 33:17176-17186, 2020.
Nirmit Joshi, Gal Vardi, and Nathan Srebro. Noisy interpolation learning with shallow univariate relu networks. arXiv preprint arXiv: 15396, 2023.
Frederic Koehler, Lijia Zhou, Danica J Sutherland, and Nathan Srebro. Uniform convergence of interpolators: Gaussian width, norm bounds and benign overfitting. Advances in Neural Information Processing Systems, 34:20657-20668, 2021.
Yiwen Kou, Zixiang Chen, Yuanzhou Chen, and Quanquan Gu. Benign overfitting for two-layer relu networks. arXiv preprini urXiv:2303.04145, 2023.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 48(3):1329-13 112299--37,,11 2020.
Tengyuan Liang and Benjamin Recht. Interpolating classifiers make few mistakes Journal of Machine Learning Research, 24(20):1-21 2023.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In 8th International Conference on Learning Reprexentations (ICLR), 2020.
Neil Mallinar, James Simon, Amirhesam Abedsoltan, Parthe Pandit, Misha Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: Toward a refined taxonomy of overfitting. Advances in Neural Information Processing Systems, 35:1::::11111 11:1182-1195, 2022.
Naren Sarayu Manoj and Nathan Srebro. Interpolation learning with minimum description length. arXiv preprint arXiv:230..07263, 2023.
Andrew D McRae, Santhosh Karnik, Mark Davenport, and Vidya K Muthukumar. Harmless inter- polation in regression and classification with structured features. In International Conference on Artificial Intelligence and Statistics, pages 5853-5875. PMLR, 2022.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75 (4):667-766, 2022.
Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max- mar-mn linear classifiers: tigh-dimensional asymptotics in the overparametrized regime. arXiv preprint 1rX15:1111.01144, 2019.
Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparameterized regimes: Does the loss function matter? The Journal of Machine Learning Research, 22(1):00144-0072 2021.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
12

---

Preetum Nakkiran and Yamini Bansal. Distributional generalization: A new kind of generalization. arXiv preprint XXiv:2009.08092 2020.
Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy. In defense of uniform convergence:
Generalization via derandomization with an application to interpolating predictors. In International Conference on Machine Learning, pages 7263-7272. PMLR, 2020.
Tomaso Poggio and Qianli Liao. Generalization in deep network classifiers trained with the square loss. Center for Brains, Minds and Machines (CBMM) Memo, 112, 2019.
Ronald Pyke. Spacings, Journal of the Royal Statistical Society: Series B (Methodological) 27(3): 395 436, 1965.
Alexander Rakhlin and Xiyu Zhai. Consistency of interpolation with laplace kernels is a high- dimensional phenomenon. In Conference Learning Theory, pages 2595-2623, PMLR, 2019.
Itay Safran, Gal Vardi, and Jason D Lee. On the effective number of linear regions in shallow univariate relu networks: Convergence guarantees and implicit bias. Advances in Neural Information Processing Systems, 35, 2022.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pages 2667-2690. PMLR, 2019.
Ohad Shamir. The implicit bias of benign overfitting. Journal of Machine Learning Research, 24 (113):1-40, 2023.
Daniel Soudry. Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018.
Christos Thrampoulidis, Samet Oymak, and Mahdi Soltanolkotabi. Theoretical insights into mul- ticlass classification: A high-dimensional asymptotic view. Advances in Neural Information Processing Systems, 33:8907-8999 8920, 2020.
Gal Vardi. On the implicit bias in deep-learning algorithms. arXiv preprint arXiv:2208. 12591, 2022.
Gal Vardi, Ohad Shamir, and Nati Srebro. On margin maximization in linear and relu networks. Advances in Neural Information Processing Systems, 35:37024-37036, 2022.
Roman Vershynin. diggeddimessonal probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
Ke Wang and Christos Thrampoulidis. Benign overfitting in binary classification of gaussian mixtures. In ICASSP 2021-2021 IEEE International Conference on Acousties, Speech and Signal Processing (ICASSP), pages 4030-4034 IEEE, 2021.
Ke Wang, Vidya Muthukumar, and Christos Thrampoulidis. Benign overfitting in multiclass classifi- cation: All roads lead to interpolation. Advances in Neural Information Processing Systems, 34:
24164-24179, 2021.
Xingyu Xu and Yuantao Gu. Benign overfitting of non-shooth neural networks beyond lazy training. In International Conference on Artificial Intelligence and Statistics, pages 1099-11117. PMLR, 2023.
Zitong Yang, Yu Bai, and Song Mei. Exact gap between generalization error and uniform convergence in random feature models. In International Conference on Machine Learning, pages 1 11704-11715 PMLR, 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. 5th International Conference on Learning Representations, ICLR, 2017.
Lijia Zhou, Frederic Koehler, Danica J Sutherland, and Nathan Srebro. Optimistic rates: A unifying theory for interpolation learning and regularization in linear regression. ACM/IMS Journal of Data Science, 1, 2023.
13

---

A Proofs of tempered overfitting
A.1 Proof of Theorem 3.1
Throughout the proof, given a sample S = (Iz, M)) ~ D we denote S = (xt) Sy =
(y6 ) and assume without loss of generality that æ1 S x2 S ... S Tm-
Lemma A.I. Denote by F.g the event in which the samples (x:) Der satisfy
(maximal gap isn't I too large) dmax == maxxe/mm (1i41 Ii) log(8(m-1114)
m++1
(most gaps aren't 't too small) K E [m-1] - 1] 2141 I2 < 10(m+1) H < m+1
(no collisions) Vi + j E [m] 2; # # Z---
Then there exists absolute mo E N such that Vm 2 mo Pro Ex
8
Proof. Deferred Appendix D.
Following the lemma above, we continue by conditioning on the probable event Eg, after which we will conclude the proof by the union bound. We now state lemma due to Safran al. [2022] which is crucial for our analysis.
Lemma A.2 (Lemma E.6. Safran et al., 2022). Suppose that < j are such that yi, 1i+1...... -1. Then in the interval (2,,7)) there are at most two points which N₂ increases.
We derive the following corollary:
Corollary A.3. Suppose that Vi+1. Vi+4 = -. Then there exists S é iit 3 for which No Nol( < O.
Proof. Assume towards contradiction that y....., U1++ = -1- yet for any i < < i i there cxists Ze E (Iyg xf+1) such that (2e) 2 O. Recall that No(z,),....... (2(24433) < - by Eq. (3). Thus for each i < L < + 2, looking at the segment (ze, ze+1) 9 Øe+1 we that No (= 0, No (No+1)))) < -1, (2t) > O. particular, by the mean value theorem, any such segment must contain a point at which N2 increases. Obtaining three such points which are distinct contradicts Lemma A.2.
We assume without loss of generality that m is divisible by 5 and split the index set [m] into groups consecutive five indices: we let /1 .I...., 5), Le {6...., 10) and so on up to Lm/s. Denoting by the (one dimensional) Lebesgue measure we get that under the event E,, it holds that
E.S
Pr [No(x) <0] -Es, [u(x: No(x) < <0) InD,
> Es, Din
Σ
p(0+41 1 xz)) { [x < <0}
iE/m-1]
By
[2 - -xz) (1
[10 < <0]]
[m
Dsy [(01+1 - x1) [N [[)1)1]] < <0]]
kE tE(m/55 (E(1.
[Corollary A.3 2
Σ
Σ
Es, Dm
min(#e+1 - zz) (YL I, Ve = -1]
EEl,
fe(m/5) (E(T.)
Σ
Σ
min(#e+1 - 2z)) Prrpu. Bit1.....,, 1144 -1]
REr.
(Elm/G) [e(1.)
2 "p²;
14

---

where the last inequality follows from our conditioning on Eg. To see why, note that the sum Eielm/B] Eie(s minggr, (Ze+1 - 2z) is lower bounded by the sum of the m/5 smallest gaps, yet under Eg this sum contains at least (m)) summands larger than (2(1/m)= - hence is at least some constant. We conclude that as long as E, occurs we have Es [Pra~D, (No(2) +]] 2 cp". Moreover, we see by the analysis above that if a single label yt for some / 4 C [m]] is changed.
this can affect (a) only in the segment [Aminy, &. E. r) which is of length at most 7dmax =
O log (1n/
Thus we can apply McDiarmid's inequality to obtain that under Lgg, with probability
m
at least 1 - 6/4:
log (m/6)
Pr (No(x) <0] 2 p² Do
Overall, by union bounding over Ex the inequality above holds with probability least 8/2. which proves the desired lower bound.
We now turn prove the upper bound. Let (*).) be 2-layer ReLU network of minimal width n E N that classifies the data correctly, namely (x,) > for all i E [m]] Note that n is uniquely defined by the sample while N* is not. Furthermore, n² is upper bounded by the number of neighboring samples with different labels. 6 Hence,
Esy~Dy [n' S Esy~Dy l1fi E [m 1]: : y: # 94t2ll
(6)
= (m 1) DD [1 {uz + U22l
(m 1) Pr [y) + y2!
SynDy
2(m 1)p(1 p) Opm)).
We conclude that the expected width of N (as a function of the sample) is at most n² (pm).
By Safran et al. [2022, Theorem 4.2], this implies No belongs to a class of VC dimension O(n")=
(pm)). Thus by denoting the 0-1 loss - _ (No) Pi(ea))-//sig(NNeee (z)) # y) and invoking standard VC generalization bound we get
1 (sign(No(r)) + vi v0 (
Byy (No) In]] S
n
= =0
n
m
By Jensen's inequality E[vn*] I /Bnn*] S ppm expectation
ElVn* n* /m] z vp. by the law of total
D 1 [No)l = En- ES ( (No) |n*]]
S En-
V n
SVD.
(7)
In order to relate the bound above to the clean test error, note that
07 (No) Pr [sign(NNo (z)) * vl
(z,g)~
(1 - p)
Pr (No(x) s Oly 1] pp. Pr (N((x) > 0ly = 1] (a.a)
(E.0)~
p) Pr [No(x) 0
IND,
1
>
Pr (No(x) S 50
2 DnDs
hence
Eq. (7)
Es Dm
Dm
Pr [No(x) s0] < BS,-Dm znD=
[2r 210-1(No)
vD.
'This can be seen by considering network representing the linear spline of the data, for which it suffices to set a neuron for adjacent samples with alternating signs.
15

---

As in our argument for the lower bound, we now note by Eq. (6) that flipping single label for some E [m] changes n' by at most 1, hence changing the test enror by at most (11/m). Therefore we can apply McDiarmid's inequality and see that under the event Exz, with probability at least 6/4:
log (1/))
Pr [No(x) - 0 5 D>
Vp
Overall, by union bounding over E, the inequality above holds with probability at least 1 - 8/2. which proves the upper bound and finishes the proof.
A.2 Proof of Theorem 3.2
+1
Xt-1
X
X1+1
Xt-1
X1+1
Xt-1
X
Xc-1
Xi
Xt-1
Figure Illustration of the proof of Theorem 3.2 in case there is a single non-linearity along [2,, xi+1] If the network is not linear along [x,, 2i+1], one of the cases illustrated in the top row (in blue) must occur. In each case, the dashed green perturbation classifies correctly by altering exactly two neurons while reducing the parameter norm. Moreover, if the network is linear along [2,, Z++1), yet (1,);) < -1 or No (2)++1) either case, the dashed green perturbation classifies correctly by altering exactly two neurons while reducing the parameter norm.
one of the cases illustrated in the bottom row must occur In
Throughout the proof, given sample S = (Ii, y)) Dm we denote S. (x:) Sy (y:) and assume without loss generality that 21 S x2 S ... S Im Denote by E., the event in which the samples (x:) Dm satisfy
log(8(m + 1)/5)
dmax == max (I++1 xz) S m +
sE(m-1
and recall that by Lemma A. we have Prs [Eg] 2 1 for m larger than an absolute constant. conclude using
Therefore from here throughout the proof condition Ez, after which the union bound.
For any point denote the event in which yi, 1, Di. and t1 1. Note that for any x we have
(0. 1). denote by iz the maximal index i E [m]] such that 2; < Let AS
Dm [Av] p(1 2)2 2 1p, so get
16

---

Eg
Pr (No(x) <0] g Di ,ND D.ND [1 (No(x) <0] xnDe
2 Dyy D. [11 (No(z) < <0) [Am] Dy DenD:
Pr
[Ap]
2 P. B Dr
Pr (No(x) 0 A END,
(8)
We aim to show that Pra-D, (2) < 0|4 (1)). In order to do so, note that conditioning the uniform measure D = Unif 1]) on the event A₂ results in a uniform measure over the (union of) segments between -1 labeled samples to +1 labeled samples that also satisfy the additional property that the neighboring sample on their left is labeled +1. We will show that if 0 is a local minimum of Problem (1), then along any such segment No(x) is linear from -1 to +1:
Proposition A.4. Let [m 1] be such that I;-1 I, 24+1 with yı-1 y1 -1 and 3i+1 1. I is a local minimum of Problem (1), it holds that No(r,) = -1, No((141) = 1 and (-(-) is linear over (æi, ((+)).
In particular, the proposition above shows that
Pr [No(x) <0)A)) D>D,
which plugged into Eq. (8) gives
Pr [No(r) < <0] DwD;
2 P
Bs, - Dr
Moreover, noting that any local minimum is in particular a KKT point, we saw in the proof of Theorem 3.1 that under the event E,, changing a single label yı, E [m]] can change the test error by at most (ddmax) = OOlog(m//)) ([llo(m//)/m) /m) By McDiarmid's 's inequality this finishes the proof of the desired lower bound.
As for the upper bound, for x E (0, 1) we denote by BN the event in which ye = = +i = namely, x is between two positively labeled samples. Note that for any x we have Prs,~D.- [Ba]
(1 p) 2 1 - 2p = PIs [B]] I 2p. We will show that is a local minimum of the margin maximization problem, then BR implies that No(x) 2 O.
Proposition A.5. Let E [m - 1] be such that = yi+1 = 1, and let x E [2t, (14)). IfO is a local minimum of Problem (I), it holds that No(x) O.
In particular, the proposition above shows that
Es DDD [1 (No(x) < [&] = =0
so we get
Es
Pr [No(2)== < <0] Es .DD [1 (Z)()) < 0]] DDDDe
Es, zD (No < 0) [Bx]
Pr
[Bx]
S. Do
Es w> D. [1 (N) 0) [b]
Pr
[B2]
S 0 2p = 2p
As in the lower bound proof, recalling that any local minimum is in particular KKT point, we saw in the proof of Theorem 3.1 that under the event Ez, changing single label yr, 1 E [m] can change the test error by at most (ddmax) Ologgmm m/))/m). Hence applying McDiarmid's inequality proves the upper bound thus finishing the proof.
Proof of Proposition A.4. Throughout the proof we fix i [mi] for which the conditions described in the proposition hold, and we assume without loss of generality that the neurons are ordered
17

---

with respect to their activation point: b1 < bz < ... < bn. Moreover, we may assume without loss of generality that W1, wi..... Wn 2 0. Indeed, note that Eq. (1) is invariant under the transformation 8/ f -; W/ + - wj, bj 6 bb, which does affect neither the parameter norm nor the parameterized network in function space. Hence, any local minimum of Eq. (1) corresponds local minimum with wi,.... wn 0. Lastly, we will make frequent use of the following simple observation. For differentiable we have
wa
No(1) = Ev, Ug j=1
Uv.wung Wy {wzz + b, 2 0}
(9)
20
so (2(1) (z2) for some 21 22, then there must exist,j E [na] with vj 0 21
01
mi
22. Similarly,
(21) N6 > (22)2) implies that there exists j E [n]] with v < 0, 21 < b1 22
We split the proof Proposition A.4 into two lemmas.
Lemma A.6. (- linear over (mis 1.+1).
Proof. Recall that No(x,) -1 and No(1:+1) 2 so No increases along the segment x++1) 1)- Thus, (-) is not linear over (z,, xx+1) only (at least) one of the following occur: (1) There exist 21, 22 (2g; 1141) such that 21 < 22 and 0 < N² (21) such that 21 < 22, (11) > O and N% > (22) or (3) there exists a single E (I), 2441) at which No is non-differentiable, such that No (x,,,,))) 0 and N² (x. > O. We will show either of these contradict the assumption that is a local optimum of the margin maximization problem.
Ng (=2): (2) there exist 21, 22 (2s, 2141)
Case (1). The assumption 21, 22 implies that there exists j1 [ni] such that B3
(21, 22)
way
and Uy > 0. Let j2 jı be the minimal index j {úr + .....,n] for which vy 0. For some
small å > 0, consider the perturbed network
(o,
Σ JElm]
Bjo (wy I b1)
(10)
bi bjs )))
+ (1 - 8705,
Wij x + bjj 1 1 8
W/jz
+ (1 8 Uii Wiis
Uj2 (wjz
x + biz)
Uig Wij
It is clear that ||0 0s| satisfies the margin condition, yet has smaller parameter norm. To see why the margin condition is not violated for small enough 8, notice that Ne, (I) Ne (x) for all of (æ,,
8-ي0 and we will show that for small enough 5 the network above still
di2 in particular wij
No, (ar) = No(2r) for all E [1]. as well as for all æ0 2 bj2_
Furthermore, by minimality of ja wis
we note that there cannot exist yı 1 for such that 24 E (- (-ا, Aoz A direct computation gives that No. 2 No along this segment, so overall the margin condition is indeed satisfied for the
wyy 15i3
We can assume that such ja exists, by otherwise discarding ja in the rest of the proof which would work verbatim. Notably, the only case in which there does not exist such ja is when z; is the last sample to be labeled -1.
18

---

entire sample. As to the parameter norm, we have
8
(
و3 ))
||0=11==
E
(o}+
0) b3) (1
+ w + +(1))
b/
-
w/p
2
2
+ # + 11
32
1/ jz
E
(0) + w/ + 69) + (1- - 25)0 + w + +bg
1 8/
25
jeIm|tisn.aat
1 + 26 U/j Wi
12
2/2
+
2
+ 12 + +
U/2 W/
= Σ (ug + u + +b)
20
1/1
+
b/1
W b/2
bbs
Uy 11
+ 0007))
1- 8
W'j2
Ui Wijz
jE(m]
Thus,
|1011 - |10s|| 2- = 26
2
Uj Wij 4/2
bjj
bjj
Wp bja
+ +0((2)
1
Wiz
|101/ = ||0s|| + 26
Uj Why U/2
bjr
bi
Wj.
+ 0(6")
(11)
W'ja
1
Wija
By construction, fj > and 8/2 < hence
2i ",,, 122
> 0. Moreover,
0 and w/
1/2
b/ 50 - for d < 1. Lastly, recall that j2 Overall, plugging these into Eq. (11) shows that 1012> ||ss|" for small enough 6, contradicting the assumption the a local minimum.
bj2
by
My b > 0.
>j
bj.
W22
Mai
Case (2). Since No(z1-1) 2 1 and No(x;) S -1, N2 must be negative somewhere along the segment (2)) Yet, (2) O so there must exist ji E [n] such that by (x;-1,2) wa and U/ > 0. Moreover, the assumption 21, 22 implies that there exists E [r] such that bi2 E 22) and V/ja <. For some small 5 > 0, consider the perturbed network win
(z) =
Σ Us (wy - x +b)b))
(12)
je(m|Minnd))
+ (1- 8)0-) (wj, x x bj,) + 1zz ((1z)
8U W/1
)
oug, òusybii by
x biz
+
Ui2
U/a
clear that ||0 0sl و= and we will show that for small enough the network above still satisfies the margin condition, yet has smaller parameter norm. To see why the margin condition is
not violated for small enough 6, notice that No, (x) = (2 for all x & (2,-1, so particular No, (æ1) (o)r for all 7 o i. Furthermore, direct computation yields No, (xx) < No(x;) s 1. As to the parameter norm, by similar computation to that leading up to Eq. (11) we get that
| ||0g| 2 28
Ui "in Wia
Uý bj biz
O(59).
(13)
Uja
By construction, U/ Wjj O and Ujz Wij
0 hence
My wyy
1832
O. Moreover, wy.
0 and
Vis
bi so we also have Vy, b, Dy enough 8, contradicting the assumption the 0 is a local minimum.
0. Hence, Eq. (13) shows that |012 > ||0s 2| for small
1032
Vig
Case (3). The assumption implies that there exists ji [ri] such that wai
by E (204 Uj
0 and
h1 2 Z++1. Let j2 > ji be the minimal index j E {ii + I,..., n such that uy < 0 (see W1++1 Footnote 7). Consider the perturbed netowrk as in Eq. (10) and continue the proof as in Case (1) verbatim.
19

---

Lemma A.7. No(x;) -1 and (o(++)1) 1.
Proof of Lemma A.7. Recall that (x,) I -1, so assume towards contradiction that No ) < -1.
Note that since No (x))) 2 1, (-)()) must decrease along (I;-1, Zz), so there must exist E [n] with
V/ and by
< z₁- Denote by Ji E [n] the maximal such index. Similarly, since Ng (2:+1) 2 1
w
there must exist f2 E [n] with U/2 > and 2;-1 <
622 < 21+1. Consider the perturbed network
w52
No, (z) =
Σ
Uyo (wy x + bU)
(14)
(e
+ (1 - 8)0; a (w/, x x+ +b,)) + U120 ((w)) W/i + 80j, Wij
8uz Dog
x +
4/2
Ujz
for some small 8 > It is clear that 100 0, = 0, and we will show that for small enough ò the network above still satisfies the margin condition, yet has smaller parameter norm. To see why the margin condition is not violated for small enough 6, first notice that No, (1)(2) & (I:-1, L(+1). Furthermore, Ne, (z:) is continuous with respect to ô so Ne; < -1 implies that Ne, (xx)) < --1 for small enough 8. As to the parameter norm, by a similar computation that leading up to Eq. (11) we get that
No(x:) for all
| |00,
+ 28
2
U/ Whi W/j
U/ by bi2
O(a²)
(15)
Uja
Ujz
By construction, Uy < 0 and U/2 hence "y, 1012
> 0. Moreover,
byg and wij
1/22
so we also have My by Doz
> 0. Hence, Eq. (15) shows that ||01|2 > |0,1|2 for small enough 8,
Mig
contradicting the assumption the O is local minimum.
Having proved that (z;) = 1. we turn to prove that No( = 1. Knowing that No (x 2 1, assume towards contradiction that (o(x141) > 1. Recalling that No(2;-1) 1, No I and that (-)-) is linear along (Z;, 1- due to Lemma A.6, we conclude that there must exist [m) such that Un 0 and T;-1 that fy; < O. Consider once again the perturbed network in Eq. (14) (only now J1: are different, we just described). The same argument in the previous part of the proof shows that for small enough the network above still satisfies the margin condition, while Eq. (15) once again implics that ||]| 2 ||0g| 1 for small enough d contradicting the assumption the f is local minimum.
by Jz. Denote by f2 > ý1 the minimal index such
Overall, combining Lemma A.6 and Lemma A.7 finishes the proof of Proposition A.4.
Proof of Proposition A.5. The proof is essentially the same as Case (1) in the proof of Proposi- tion A.4.
Throughout the proof we fix i [m 1 for which the conditions described in the proposition hold, and we assume without loss of generality that the neurons are ordered with respect to their
bb < ... S ba. As in the proof of Proposition A.4, we may assume activation point: b1 S - wi without loss of generality that W1. Wn 2 O. Moreover, as explained there as consequence of Eq. (9), we observe that (21) < 22(22) for some 21 < 22 implies the existence of E [m] with < z2. Similarly, N2(21) > (22) implies that there exists j2 E [n]] with by
Ui > 0 and 21 < Was
bi2 22. With this choice of j1.j2. the proof continues in Case (1) in the proof 2/22 0, 21 wiy
of Proposition A.4 verbatim.
20

---

B Proofs of benign overfitting
B.1 Proof of Theorem 4.1
We sample dataset X1,...a Xm Unif(S and labels yı,- y...... Um Dy. for p S c for some universal constant 61. We first prove that the following properties holds with probability >
log
For every i,j E [m]] (x,, x,)l
2. |XX to X₁.
$ C where C' is some universal constant, and X is matrix whose rows are equal
3. |-| I
3pm 2
Lemma B.1. Let 8 > 0, assume that we sample X1,...Xm Xm Unif(Sd-1), and yı..... Ym Dy
for p S C₁, and that m > los(3) for some universal constant cı, C2 > 0. Then, with probability properties I, 2, 3 holds.
2 Iog
Proof. By Lemma D.1 we have that Pr
|x]
x
2
87
S 8. Take 8' 3m and use union
bound over all i,j E [m]] with + j. This shows that for every
+ j we have:
2 log
3m
Pr
x Xj
2
8
d
This proves Property 1. Next, set X to be the matrix whose rows are equal to x;. By Lemma D.2 there constant
>
such that:
c' ( d+ log (3) dd+
+ log (3)
)
8
Pr |XX 1 d
+
(16)
m
m
We can also bound |XX S |||| XXX -1 -||- Combining both bounds and using the assumption that m 2 log !) we get that there is universal constant C such that
Pr [|]XXT]] || > c] S 5. This proves Property 2.
Finally, using Bernstein's 's inequality over the choice of the labels yi have that:
3pm
< exp (- (-mp(1- - p) + mp/6
p²m²//4
pm
Pr 1-12 2
exp
mpp1
5
where we used that p < Hence, if 2 02 log(3) for some universal constant C2 0, then | <
3pm 2 Applying union those three arguments proves the lemma.
From now on we condition on the event that properties 1, 2, 3 hold, and our bounds will depend on the probability of this event.
the following lemma we show that 0 converges to a solution of the max margin problem and bias terms are relatively small, then the norm of 0 is relatively large:
Lemma B.2. Assume that m 02 log (?) and that 0 (w,, by is a solution to the max
margin problem Eq. (1) with E Ujo(b,) < 1. Then. Σ₁= 11 + 2 CV/LL where C. is some universal constant.
21

---

Proof. Take E [mm] then we have that No(x,) 2 1. By our assumption, this implies that:
1
- No(x:))
Σ Nz0(b;)
2
5=1
(w x + xb,) - Σ "
mj((b,)
j=1
loyl |o(w x + by) (bb))
|w] x
j=1
W x,)x
j=1
where the last inequality we used Cauchy-Schwards Denote by S = ード= /w5112 + -0g + 17. Combining the above and that
Σ n
uz
S
V
we get:
Σ
w xz) 1
45
j=1
We sum the above inequality for every E 1+ to get:
1+
<
)2
48
j=1==1
(x:x,]
Jw
f=1
m
||5
Σ
x
/=1
$
Σ |w CSSC j=1
where in the second last to last inequality we used the Property for some constant C and in the last inequality we used that ΣØ= ||w,| < S. Rearranging the above terms yields:
S $20
I2C
We now prove a lemma which constructs a specific solution that achieves a norm bound that depends on [.
Lemma B.3. Assume d 2 50m2 log
and S t. There exists weights 0 = (wj, Uj b,) that allain margin of least every sample and have Σ ||w + oz 13 < /
3mm² (
Proof. Assume without loss of generality that is even (otherwise fix the last neuron to be 0). We consider the following weight assignment: For every j < n. consider wj V "viL Σier Xi.
0i 2V and by
> consider w, V Vnyiu_ Σiel_ X;. For every
0y 2 and bj 0.
22

---

We first show that this solution attains a margin of at least 1. For every i E 4 we have:
No(x)) =
Σ
2 x; + bz)
==1
Σ
21
a
nIVIL1
4
4
Σ
x,xx
n
jSn/2
rEI-
VIL
Σ
21
Σ x,xx;
T1
nVIL
j>n/2
reL-
4
|11 V
log
[im?
0
4
[1-1
2 log (mn²)
Σ
1
Σ
Vd
Vd
iSn/2
12n/2
2 71 4
n
4 21,
2
10
2 n 10
where we Property 1, that S hence by Property 3 |--1 i E 1_ we have:
S
m 2
and our assumption on m and d. For
Nx(),)
(w x3 b,)
=
Σ
2
[-1
V
nn
4
Σ
X
12n/2
MET
Σ 21
VI_
4
Σ X
VV [VLLL
n
32n/2
rEL-
Σ
-0
Σ x,xx/
Σ
o
1+ Σ
x, X3
/2n/2 n
n
jzn/2
rEL 1687
(( ( 1)
log
3mm2 6
( (1T-1-1) 1)
log
(3m²
Σ 4
1 1-
vd
vd
35n/2
S2n/2
11
4
1
n
4
1
1
S
-1,
2 11
10
2
n
10
where again we used properties 1 and 3, that p < hence |--| m
2 and our assumption on m and d.
This shows that this is indeed feasible solution. We turn calculate the norm of this solution. First we bound the following:
Σ iel_
x;
=
| 12 +
Σ
x X,
iel_
jg.. fJjE!_
3mm2 /2log 5
11
<
|1|++14 12
<
|
dd
10
23

---

where we used Property 1 and the assumption on m and d. We now use the above calculation to bound the norm of our solution:
2
n
2n
w, 11 + oj
+ b3 =n-
Σ
n2.
x
TV L
n1
2
1-
iE1
44v
2
+
-2/1L-1+
19V1-
10
VIL1
We are now ready prove the main theorem of this subsection:
Proof of Theorem 4.1. Denote by := ΣE= -| uz + +1, and assume that K < a.
10
vp
where will be chosen later and 0 is solution the max margin solution from Eq. (1). Assume on the way of contradiction that Σド=1 (b)( 2.2 then by Lemma B.2 we know that: K 2 CVI 2
cV(1- - ? m. On the other hand, by Lemma B.3 we know that ||0'|| S 9 S 9 3p m. Combining this with the assumption we have on K we get that:
c v(1
(
3p)
9a 3pm 2 m S
2
Picking a to be some constant with a Cv2 contradicts the above inequality. Thus, there exists 18v3
constant C₁ := _ such that if K S vP
S then )zo(b 1.2
Suppose we sample x ~ N (0, I), then we have:
No(x) = Σ U5 (wr x + bb))
n
n2 Σ
n
Σ (ba(
[jo((b))
Σ uo x b1)
j=1
j=1
j=1
1
Σ (bo(),)) Σ [wo( bj)
2
1
luyl [w] x
2
J=1
1
N
[w] [w]xx x)2
(17)
2
We will now bound the terms of the above equation. Note that Σラ 2g < K S 9/m. For the second term, we denote by w,
w; Tw T and write:
x)2
1|, (I
< max w, x jEIn]
Again, we have that Σn ||w,12 < K < 9/m. By using the stationarity KKT condition from
Eq. (2), we get that w, E span(x1, ..., Xm thus write w, Em aizx, Xa, where
24

---

X is a matrix with rows equal to x,, and (ay): = at,.
We will bound == arg max; |4
1 = |w,ll
Σ 0s X
|Xa 11
X Xaj
a. la, + a (X X - a)
2 |ayll - ||,|| - -1l
| 1| || x| - T|I
where the last equality is true by using the SVD decomposition of X. Namely, write X = USVT, then || X - /| = VV - = | - / | 5 - /|| = ||X - /||- Note that in Lemma B.I, Eq. (16) we have shown that ||X T I S d for some constant d' Note that we can choose large enough such that d' I In total, this shows that ||ay|| < e" for some constant c".
We now use Lemma D.1 and the union bound to get that with probability > we have for every
i that xxx,, [4|
V
log( m
We condition this event from now Applying both bounds
get:
m Σ ii=
max W x) S max jE(n)
Oli
x
3E(m) [p]
2 log
$ V
max jE(n]
|ayll
d
log
m
S d"y
d Plugging in the bounds above Eq. (17) we get:
No(x)= 2
w x)2
2 2og m
2
9/m 9/m d"
8lme"
2 (m)
2 2
vd
cym2 /og (m) then then
By choosing constant C3
large enough such that if
81me" /2 log m)
< 1 we get that No(x) > 0.
Vd
B.2 Proof of Theorem 4.3
We sample a dataset XI.... Xm ~ (n and labels y...... Um ~ Dy, for p I Ci for some universal constant C1. We first prove that the following properties holds with probability 8:
2 log
1. For every i,j E [m]] (xx, xy)l $
V
d
2. |1- < 73"
Lemma B.4. Let ė > O, assume that we sample XI.... Xm Unif(Sd-1), and yr. yo ~ Dry
for p 5., and that m > d' log ( for some universal constant e, d' 0. Then, with probability properties and holds.
25

---

The proof is the same as in Lemma B.1 so we will not repeat it for conciseness. The only different is that here we only need | be smaller than fim which is independent of p. Hence, for p n.5 we get this concentration where m depends only on the probability. From now on we condition on Nx(x)= Σ
the event that properties and 2 hold, and our bounds will depend on the probability that this event happens.
In this section we consider networks of the form:
n/2
T2 - Σ o(w) x + bb)
==1
j=n/2+1
That is, the output weights are all fixed to be +1, equally divided between the neurons. We will use the stationarity condition (Eq. (2)) freely throughout the proof. For our network it means that we can write for every j [n]:
w Uj
Σ xEfm]
Aoo
by Dj
X
iE|m
where o/1 = 1w] x; bb u3 = for j E (1...., n/2} and 1U = -1 for j E
The next lemma shows that all the biases are positive. Note that this lemma relies only on that the dimension large enough, and that Property of the data holds:
Lemma B.5, Assume that d 2 8m log
Then for every j [m] we have by 2 O.
Proof. Assume on the way of contradiction that bj < 0 for some j E [n]. We assume without loss of generality that j E .1.....11 n1/2), the proof for {n/2 + +1,++1.. I,...,n is done similarly. Denote by 14 = fi E 4 == oi. = 1} and l' = (i = oij = 1]. We can write:
by =
Σ A
Σ
mmmm]
iEL
iE
Note that A, 2 0 for every i, hence 1'_ is non empty, otherwise by 2 Take X, arg max A
we have:
w Xx + bb = by +
Σ
X
iEr UP
-x
A X
iEt, UZ Mr)
where we used that by < and ||x||| 1. Rearranging the terms and using Property 1:
A1axex x
VEL, UU Mr3
2 2 (2m²)
Σ
A
d
SER;Ur 1r3
2 log
2m2
Σ A
d
2 log 2m3
Denote Aa = arg max or A; then from above we have shown that X, S A.m since 144 JUL 1 < m. In particular, Lt otherwise, X, A which means that X, 0 since
d
26

---

log
2m
m
which is contradiction. We can now write:
bj
Σ A
Σ
X
ie!
Σ
X Σ A
ie!"
log
2m2
2 A Xam²
d
2log
22m²
As
1 m
d
2log
2m
By our assumption d, we have that m²? by which contradiction since X,
hence bj 2 2/. But, by our assumption,
2
The following lemma is general property the KKT conditions:
Lemma B.6. Let i E 14 (resp. E I_) with X; > 0. Then, there is a neuron k with positive output weight (resp. negative oulput weight) d/P.
Proof. We prove it for E L+, the other case is similar. Assume otherwise, that is for every neurons with positive output
have dij 0, that is w) x; by S by the definition of o(.-- This means that No (x;),) S 0, since all the positive neurons are inactive x,, which is contradiction to Nx(x,) 2 1.
The next lemma shows that if the bias terms are smaller than t. then the Aj's for i E L cannot be small.
Lemma B.7. Assume that d 2 32m 'n log for every I we have X
2mm 5
and that End by Ez=n/241 bg S 7. Then,
Proof. Take T4, have:
n/2
1 <No(x,) = Σ
σ (w) x, + +by) - Σ
alw] + bz)
j=1
j=n/2+1
Apo'T + Σ
X181o(y& X, by
0
j=l
tErifr)
Σ
Xeyiol bbj
i jmn/2+1
sEri(r)
n/2
X
Σ iElii)
x + bb
Σ
Ar
Σ sEr\fr)
Noo
x,
+ bj
j=1
j=n/2+1
(18)
We will bound the two terms above. For the first term, note that the terms inside the ReL.U are positive, since by Lemma B.5 we have b, O, and X, by Eq. (4) hence we can remove the ReLU
27

---

function, Using Property 1 we can bound:
Σ j=1
n2/2
Ap +
Σ
x,1
n
2 A,
2 log
2m²
5
Σ
n,2
Σ
+ Σ bj
a/2
iEliir)
j=1 (e
j=1
2 log 2m3
n/2
Σ
X
2
bj
(19)
2
2
d
AET
where used that of I 1. For the second term in Eq. (18) we the fact that the ReLU function 1-Lipschitz to get that:
Σ
-
E (E((())
x x
bb
j=n/2+1
a
n
Σ
A 1x_ bb
Σ
o(b,)
Σ
o(b,)
j=n/2+1
iET())
i j=n/2+1
j=n/2+1
n
S
by
Σ iElifr
> X.
j=n/2+1
j=n/2+1
2 log 22m2
71
S
by
+
Ar
+
A (E((()
(20)
2
d
j=n/2+1
where again used Lemma B.5 get that by 2 and Property 1. Combining Eq. (19) and Eq. (20) with Eq. (18) we get that:
a/2
2 log
b
Σ
by nd, + m
Σ A
d
1=1
j=n/2+1
iET(()
Rearranging the terms above, and using our assumption on the biases we get that:
2log
2mm 5
Σ A
< nd, +n
iETVE)
2 2m
If X, 2 in then we are done. Assume otherwise, then n
Eiergo A 2 and
X < Denote A arg max4e[m] di then have that Σ
[E(m)](r) d S md., which by the
above inequality means that X 2mm log 2m12
Va
We split into cases:
Case L. Assume I.. By Lemma B.6 there is l E fl....,,/""" n/23 with 0'.4 = 1. For the k-th neuron we have:
o( ow x, + bk)
Σ rE(mi
yidio X bv.
2 A Σ
Ax|x, x.1 bb
(E(\fs)
2log
12m² 5
+ bb
(21)
28

---

2 2m
and note that since A 2 O, my
and bj 2 0 this neuron is active. For every other
neuron j with positive output weight we have:
[w, Xx (1) - -o(b))
Σ
Vidio x, + tbs -0(b))
sm|ml
Σ sm[m]
\x x,l + -b(bg)
2 2log 22m
mx V
+ +bg -o(b))
d
2log
22m²
-
(22)
where we used that a is 1-Lipschitz and that X is the largest among the X,'s For a neuron with negative output weight, we can write:
a(w] x5 + bÿ)
Σ vE(m)
o xTxxx x, bs
2log (2m²
Sa o
Σ (ET((e)
>x/x X +by
s Sb + md
In total, combining the above bound with Eq. (21) and Eq. (22) have that:
n/2
1 Nx(x.) = Σ
(w
X.
bb,)
Σ
o(w, X. + b,)
1=1
j=n/2-1
n/2
n/2
n/2
Σ
[(w] x, + bb))
Σ
a(w]
X, + bbb
Σ
a o(by)
Σ
a (by)
1=1
j=n/2+1
j=1
1=1
2og 2m?
n/2
Aammn
Σ bj
bj
j jmn/2+1
log
2m3
By our assumption on d we have that mn get that:
V
Hence, rearranging the terms above, we
2.
n/2
X 2
by
by
1=1
j=n/2+1
29

---

But then, looking at the output of the network on X, (recall that by our assumption A,- S in. we get:
n/2
1 5 Nx(x,)
= Σ
a(w Xr + +b,)
Σ
a(w, x, + bb)
==1
j=n/2+1
n/2
Σ 0
Σ
yidio X, + bb
Σ
-
I x, tb, +
jml
kE(m)
j=n/2+1
sE/mJ
Σ
o(b;)
Σ o(bs) jmm/2+1
j n/2+1
a/2
Ar +
Σ
Xx|x,
x
+ bb
Σ
Σ
dxxx x,, +b2)
+
j=1
iETi(r)
j=n/2+1
ieT(r))
n Σ
o(b,))
a(bú)
j=n/2+1
j=n/2+1
n2
2 2oo 22m²
n/2
+ Aammy
bj
by
2
d
1=1
j=n/2+t
2+1
2mm² 2 2log
X
+ Ammm
8
2
9
2m² 2log
+ d
(23)
8
d
2
2m²2 log x
By our assumption mn
hence rearranging the terms above we get that X S
which is a contradiction to A 2
fd
1.
2mn log
2x12
30

---

10 Case II. Assume E I_. By Lemma B.6 there is k E fn/2+ +//2+1,... 1,...,,,, n) with d'2A 1. Note that
since X # O we have that (x(x.) = -1 (i.e this sample is on the margin). We have that:
n/2
-1 No(x) =
Σ
o(w X8 bb)
Σ
o(W) Xx + bb)
/=1
J=n/2+1
n/2
n
Σ
Σ
S Xs + bj
Σ
E iE/ml
2i Xs + +bs
j=1
iE(m]
j=n/241
Σ
a(b;)
Σ o(bj) j=n/2+1
j=n/2+1
n/2
$
0
Σ
>1|2; X,1 + +bg
Σ
As E
x
x51
j=1
iE/((})
j=n/2+1
a
Σ
a(bj)
Σ o(bs)
j=n/2+1
j=n/2+1
n/2
2 log 2mm²
bj
Σ
bj Agmma
Xs
d
1=1
j=n/2-1
1
2 log
2m3
+
mmn
(24)
4
2og
2m
where we used that mn)
and by 2 O by Lemma B.5, hence in the second to last inequality the term inside the ReLU is positive. In addition, we used that the ReLU function is
2 2np
1-Lipschitz, and that X, is the largest amont the X/s. Since mn
2. rearranging the
terms above give us that Dg I 10, which a contradiction to that X 2
Vd
2 3.
2mn
2 2og
2m
To conclude, both cases are not possible, hence X .n which true for every E E..
Lemma B.8. Assume that d 2 16m nn log (2m² and that Eg Ejen/241 by S Then, for every E I_ we have \; T
Proof. Take X = arg maxie[m] A We split into two cases:
Case I. Assume I_. Note that X O, otherwise X; 0 for every i, which means that Nx(x) is the zero function. Hence, x, lies on the margin, and also by Lemma B.6 there is neuron j with negative output weight such that o's,
By the same calculation in Eq. (24) have::
n/2
-1 ==ooxxx)
Σ
<((w
+b))
aWW]x, by)
jmn/2+1
1
2 log
2m? x
mn
d
2log
2m?
Using our assumption that mn which finishes the proof.
2 and rearranging the above terms we get: X, 5
10
4
31

---

Case II. Assume E 4. Denote by X, := S arr maxier_ A,. By Lemma 6.6 there is at least one neuron & with a positive output weight such that d' 1, for this neuron we can bound:
by Σ iE|m)
vidiol A mm
Every neuron j with a negative output weight can be bounded similarly by:
by
Σ
yidoo' S md,.
re(ml
Combining the above bounds, and using that by 2 by Lemma B.5 we can bound:
n/2
2 by
bj
4
==1
j=n/2+1
12+1
2 X mX
mx
j=n/2+1
2 A mmy
Rearranging the terms we get that: X & mnd
1 If Xr I we are finished, otherwise
1.
X < 2mmAd and also x, lies on the margin since X, > hence. By doing similar calculation to
Case I we can write:
n/2
-1 = N=(x)) = Σ
o(w x, + +b))
Σ
o(w]x x, b,)
j=n/2+1
n/2
Σ o
Σ
Vidio' xxx X, + tbs
Σ
Σ iE|m]
y:dio' x,, + by +
j=1
m
j=n/2+1
n
n
Σ
a(b,))
Σ a(b)))
j=n/2+1
j=n/2+1
n/2
n Σ
Σ
Σ
>g|27 x, +bbb)
dr
Σ
>x|x]xx, x +
j=1
(En(F)
j=n/2+1
iE(((r)
Σ
a(b,)
Σ o(b))
j=n/2+1
j=n/2+1
n/2
(2m² 2oog
- +
bi
by + Aamoa
8
j=1
j=n/2+1
2 log (2m²2)
< -,, + 4
+ 22mmm
d
2 log
2012
By the assumption on d we have 2m²n2 using these bounds we get that A <
Thus, rearranging the terms above and
2.
10
7
Lemma B.9. Assume that p S Ct, 2 can log (+) and d 2 32m log
22m") (2n²). Then, Σn/2 by
Ej=m/2+1 by > 1.
Proof. Assume on the way of contradiction that E by
E/ by S 1. By Lemma B.7 we
have that X₂ 2 an for every i 44, and by Lemma B.8 we have that A 10 for every i e I_, By 4
32

---

Lemma B.6, for every E 1+ there is some E f1....,n/22 with di = 1. This means that:
n/2
n/2
Σ
bj
=
yid:o's
2=1
j= 1
KE mm]
n/2
|7
1+
10n
Σ
Σ
A
4n
8
j=1 iEl-
In similar manner, we can bound:
bj
Σ
Σ
vidoo's
j=n/2+1
j=n/2+1 ic(ml
10n 10n 1
Σ
8
j=n/2+1iel_
Combining the two bounds above get that:
7+|
10m[T_]
Σ
b
Σ
by
4n
j=n/241
But, by our assumptions we have that m 2 2n (for large enough constant), and by Lemma B.4 am
we have |T- S n. and |/+ 2 (1 -tt m for some universal constant >> 0 which we will later choose. Plugging these bounds the displayed equation above, we get that:
n/2
b
Σ j=n/2+1
12
(1-
c - n
10c
11c
2
2 2
2=1
where in the last inequality we used that n 2 Taking c to be small enough constant (i.e. 22) get that Σj= bj
E)=m/241 by 4 which is contradiction.
We now ready prove the main theorem of this section:
Proof of Theorem 4.3. By Lemma B.9 we have that ΣØ by - -E by 1.2 Denote by
A = arg maxic [m] A; we would first like to show that X S 3mn. We split into two cases:
Case I. Assume E I4. Note that x, lies on the margin, otherwise A for every E I, which means that No the zero predictor, this contradicts the assumption that Ng classifies the data correctly. Using similar analysis to Case I in Lemma B.7 we have:
n/2
1 No(x,)
Σ [w.], x, bb)
Σ
x,,x,+1)
1=1
j=n/2+1
n/2
n//
n/2 o(b,)
Σ
yodio' Xx +b,)
Σ
a(- Σ
3 +b,) L obb,)
Σ
1=1
sE/m]
j=n/2+1
rE[m]
j=1
1=1
n/2
12/2
n/2
A
+
a
Σ
x/x]x,l+b]
Σ of Σ xxxxx+++b,) +
(bb)) Σ o(bi)
j=//2+1 iE/(ss
n/2
2m3 o 2 log
Σ 6j
by م -m
d
j=n/2+1
1
2log (2m²
+ >
1- mn
33

---

where we used Lemma B.6 to show that there is at least one & E [l....,n//)) with d², = 1. Using
2m12 for a large enough constant C3 and rearranging the terms above we have that A S I 3mn since m, n 2 1.
2og
that mn V
Case II. Assume E I. Take A == arg max A.. By Lemma B.5 there is at least one neuron k (n/2 + ,.,,,, with d' We have that:
n/2
1
bj
bj
4
j=1
1+1
n/2
7 Σ
X.yio'
Awoo S mnd, Ag
j=1iE|m]
j=n/2+1 iE[m]
Rearranging the terms we get X S mnd, - mnnr Note that x, lies on the margin, otherwise A₂- O, which similarly to Case I a contradiction. Again, using similar analysis to Case we get:
n/2
1 = No(x,)
Σ σ (w, bb))
Σ
[Ww]x, x bb))
5=1
j=n/241
n/2
n/2
n/2
yo xx bz) -
Σ
a-- Σ
x,
+ 3=1
Σ (b,y)
Σ a(b))
/=1
sE[m]
j=n/2+1
tE(m]
==1
n/2
Σ x(xxxx|+b))
Σ o Σ Xxxxx.++b)))
o(by)
Σ o (bb))
j=1
j mm/12+1
(ET(())
==1
n/2
2 log 2m?
Σ
bj
bj Ap Ammmy
d
1=1
j j=n/2+1
1
(2m² m 2log
8
4
By our assumption, nn log(d)2/2 < 1/2 for a large enough constant Cg. Hence, rearranging the terms
we get A 1 This means that A S 2mnd, I 3mn.
We now turn to calculate the output of No on the sample x. Suppose we sample x ~ Unif(Sa-1).
log for every i E [m]. We
by Lemma D.1 we have with probability > 1 - that |x x| S
condition on this event for the rest of the proof. Note that for every positive neuron we have that:
dW3 + b;) - obb,) a
Σ iE(m)
Vidio' xbx xidcohsx/(+bbb
- (bbb)
2 2log m
2
Sam
+ by o(b,)
log
2 -Xamy.
d
Similarly, for every negative neuron j we have:
2og m
a(b;) xww
x
-Aamp
d
34

---

In both bounds above we used that X2 is the largest among the X ss Combining both bounds, we have that:
n/2
No(x)= =
Σ
o (w) x, + bb,)
Σ a(w,x, x, + bb)
1=1
j=n/2+1
n/2
Σ (W, x, +bg)
Σ
a(w, x, b,)t
j=1
j=/22+1
n/2
n/2
+
Σ (b,))
Σ
obbb)
+
Σ
a(by)
Σ o(b,)
j=1
j=1
j=n/2+1
j=n/2+1
n/2
2 2oog m1
Σ
bj
Σ
bj Ammm
d
j=1
j jmn/2+1
2lgg
2
3m 2n² 2
d
3m 3m?nn v2 vd
We use that finishes the proof.
< for a large enough constant c3. hence No(x) 2 -5 > 0, this
C Proofs from Section 4.2
C.1 Proof of Proposition 4.4.
We first note that there exists j E {1,2) with by 0, since otherwise the network wouldn't be able to classify samples with a negative label (which exist by assumption). Assuming without loss of generality that U2 0, for any WT we also have that Pix--uminedd 1)) 1)(w]] x S = 3/2 If this even occurs, then (x) S (2 Tx) < O.
C.2 Proof of Proposition 4.5
Suppose [n] = J+ U J___ are such that
No(x) = Σ [ujow]xx)
x)+
Σ uyj((]]x) x),
JEJ+
jEJ_
where Uy 2 0 for j E J and U/ < for E J_. Then, for any choice of (wy)jeJ4
1 1
Pr
(No(x) < <0 2
Pr Pr J4, w < 0
2
x~Unif((d-1)
x-
2
2n
C.3 Proof of Proposition 4.6
Assume without loss of generality that I_ = [k]. Consider the weights w; = x,, 0 -1 for every i E I_, and Wk+1 = Eier, W., Uk+1 all points lie on the margin. In addition, it is not difficult to that this network satisfies the other
For this network we have yx:No((;) 1, thus
KKT conditions with X = 1 for every E [m.. Note that Prą- 2y[w < 0] and
Pix--Uni((3--1)) Vi I_ w. x 0] 2 since all the x; orthogonal. Thus, we get that
1
Pr X-Unif(Bd 1)
[oo(x) S0
Pr
W < 0J
Pr. MELL, w. x 0 2 Un 1)
Unifff 1)
2
35

---

D Additional probabilistic lemmas
D.1 Proof of Lemma A.1
Clearly, the third (no collisions) condition holds almost surely, so it suffices to analyze the gaps between samples. The distribution of distances between uniformly random points a segment is well studied [Pyke, 1965, Holst, 1980] and the lemma can be derived by known results. Nonetheless we provide proof for completeness.
Denote by A S A2 S .... I Am+1 the ordered spacings T1, (I2 z1),.... (Im -m- (1-Fm) With this notation, note that Eg occurs if Am+1 S log(S( m 1)/6) and Am/s 2 Iüm
1. We will show
m+1 that each of these conditions holds with probability least 1 á. under which we would conclude by the union bound. Let Zi,.... ., Zm+1 rid Exp(1) be unit mean exponential random variables, and denote their ordering by (1) ... S (m++))- The main well known observation which we use is 2(z) (see Holst, 1980). Hence for any >> 0:
that for any j [m + 1]: A Σmst Z
Pr[(m + 1) -log(m m +1) S]
mm+ Zi
= Pr (10 log(m + 1) S (t + log(m 1))
m + 1
Note that
8m++1 Z m++1
-
P, 0 as E
Z Σ m++1
= 1 and Var
mm+ Zi
m+11 1 (m++1²
m- 0.
m++
Furthermore,
Pr [Z)) - log(m + 1) S 1) = Pr [2 S + log(m + 1)] = Pr) ..) 200 S 1. log(m +
(1- - e 1o)
e +
By introducing the change of variables r ++log(m+1) 1) we conclude that m+1
( j
lim Pr[A, sr]
m 100
17 + 1
It remains to plug in our parameters of interest. For j = m++ we get
(1
(m +lgg(m+++
m+11
lim Pr|Am#+1 S rl m=-20
lim
lim exp (-e (m+)))++og(mmm))) m=+00
m ==000
m +
Noting that for r (log(8(m+11/88) it holds that e (mm+ Do+gog(m+)) + 0 so we can use the Taylor approximation exp(2) ~ + and conclude that
m+1
5
lim Pr[Am+1 S - 1r)++++r++oom-+) m-000
g
where the last equality holds for log(8(m 1))4a) Overall for larger than some numerical constant, the left hand side is larger than 1 - 5/4 required.
m+1
The second condition follows similar computation for m+11 the fact Pr
log(m/88 log(8/5))
while using
8(m+1)
A m/8 10[m=1] 1 Pr
A m/s S 10(m+1]
D.2 Concentration bounds for vectors on the unit sphere
Here we present some some standard concentration bounds for uniformly sampled points the unit sphere in high dimension.
Lemma D.1 (Lemma 2.2 from Ball, 1997). Pru.v-unir(gs-)) [I T v 2 1] < 2 exp
-di²
Lemma D.2 (Exercise 4.7.3 from Vershynin, 2018). Let x Unil(Sd-1), and denote by X the matrix whose i'th row is X;. Then, there is a universal constant & > such that:
Pr
XX T - -11l
C.
d dt
d+t < 2e
d
36


Reviews:
[{"review_id": "DhNKxsXpLh", "reviewer": "Reviewer_M9si", "summary": "This paper explores the spectrum of benign to catastrophic overfitting in a specific instance of a 2-layered neural network with ReLU activation when the training data has noisy labels with proportion $p$. The authors when the input dimension is , the test error is lower bounded proportionally to $poly(p)$ under different assumptions. When the input dimension is high, i.e. $d=poly(n)$, a NN overfitting (i.e. achieving perfect training accuracy) is benign and good generalization performance is exhibited. The authors also consider the intermediate  regime for the input dimension and show a gradual behavior for the error rate as a function of the noise factor.\n", "questions": "1. Is the assumption that the ground truth labels are 1 and all the noise is labeled -1 necessary for the analysis or just a simplifying assumption for presentation?\n2. The authors mention that the width of the network probably doesn't play an important role in the benign overfitting phenomena - is this also the case for more realistic empirical setups? it seems to contradict common practice of deep learning where the number of parameters scales and benign overfitting is exhibited.", "limitations": "The assumptions made in the theoretical setup are not very realistic, that being said, the reviewer appreciates the difficulty in obtaining such theoretical results. I would recommend that the authors discuss the assumptions and limitations in a dedicated section.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper is very well written with a great exposition and tradeoff between results and intuition.\n2. Results presented seem comprehensive and I like the fast the authors do not neglect the intermediate regime and provide empirical evidence where theoretical analysis is not attainable.\n3. The authors make their theoretical results accessible and explain the importance of the bias for the analysis.", "weaknesses": "1. The paper is missing a discussion/conclusion section to tie the results to real scenarios. Consider shortening one of the sections/proof sketches in favor or the above.\n2. The assumptions of the theoretical results are not very realistic, specifically in theorem 4.3, the input dimension is big with respect to both m and n, this does not follow common practice of deep learning where the number of parameters exceeds the number of examples but usually the input dimension is not very big.\n3. The considered architecture is rather limited, it would be interesting to explore empirically with much greater depth and not only 2 and 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thorough review, helpful comments and positive feedback.\n\nWeaknesses:\n\n- 1. If space permits, we will consider adding a short discussion on practical implications of our results. We note that such discussions also appear in several previous papers on benign and tempered overfitting (e.g. Bartlett et al. 2019, Mallinar et al. 2022).\n- 2. We emphasize that in most papers regarding benign overfitting the input dimension is much larger than the number of training samples, e.g. Bartlett et al. 2019, Shamir 2022. This is arguably a valid drawback shared by this whole line of work.\n- 3. We indeed agree that it would be interesting to study empirically more architectures and different settings under which benign/tempered overfitting holds. However, in this paper we focused more on the theoretical aspects, and we leave a thorough empirical investigation for future work.\n\nQuestions:\n- 1. This is an interesting question. We used this data distribution as it was already studied in previous works (e.g. Mallinar et al. 2022), while making the analysis tractable. Our results for one-dimensional data can be readily extended for other distributions using the same proof technique. On the other hand, it seems that the results for high-dimensional data may require a more intricate analysis for such extensions, which we leave for future research.\n\n- 2. We believe that also in practical settings, the width doesn't play a role in the type of overfitting that appears, as long as the network is large enough to interpolate the data. Note that for our high-dimensional setting, the number of trainable parameters increases with the input dimension, which we assume is larger than the number of samples. Hence, this ensures the network can interpolate the data, with no restrictions on the width. Notably, a parallel line of work establishes advantages in terms of *optimization* for wider networks (e.g. NTK analyses), which is not the focus of this paper in which perfect interpolation is assumed throughout."}, {"review_id": "HEb3vw1Ar3", "reviewer": "Reviewer_2xri", "summary": "This work studies the phenomenon of overparameterized neural networks (NNs) generalizing well even when trained on noisy data. Previous research focused on \"benign overfitting,\" where interpolating predictors achieve near-optimal performance. However, recent empirical observations suggest that NN behavior is better described as \"tempered overfitting,\" with non-optimal yet non-trivial performance that degrades with increasing noise levels. In this study, the authors provide theoretical justification and empirical validation, showing that the type of overfitting transitions from tempered to benign as the dimensionality increases in a simple classification setting with 2-layer ReLU NNs. Their findings highlight the intricate connections between input dimension, sample size, architecture, training algorithm, and resulting overfitting.", "questions": "It would be particularly intriguing to investigate whether these findings remain consistent when applied to other commonly studied data distributions, such as mixture distributions. Additionally, it would be valuable to explore the possibility of extending the analysis techniques utilized in the proof to encompass a broader range of distributions.", "limitations": "Same as weaknesses.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper establishes the connection between data dimensionality and the occurrence of benign or tempered overfitting. It presents three theorems that address benign, tempered, and catastrophic overfitting, respectively, corresponding to one-dimensional data, high-dimensional data, and intermediate-dimensional data.\n\nThe study focuses on a two-layer ReLU neural network that includes a bias term, which is a more comprehensive approach compared to recent works that examined the two-layer ReLU neural network without a bias term. Additionally, a specific data distribution is considered in this paper. Furthermore, the paper explores the relationship between the bias term and the occurrence of benign/tempered overfitting.", "weaknesses": "The findings presented in this paper are built upon the outcomes (specifically, the convergence to the KKT point of the max-margin problem) obtained in previous studies by Lyu and Li (2020) and Ji and Telgarsky (2020). To be more precise, the results in this paper depend on either achieving convergence to a KKT point or making stronger assumptions, such as converging to a local optimum. Nonetheless, these assumptions are reasonable considering that numerous other papers also derive their results based on the convergence to the KKT point, such as the work by Frei et al. (2023).\n\nIt is important to note that this paper exclusively focuses on a simplistic data model, where the samples originate from a unit sphere and the labels are fixed constants, specifically +1. The discussion does not extend to other more prevalent data distributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive review and insightful comments.\n\nWe used this data distribution as it was already studied in previous works (e.g. Mallinar et al. 2022), while making the analysis tractable. Our results for one-dimensional data can be readily extended for other distributions using the same proof technique. On the other hand, it seems that the results for high-dimensional data may require a more intricate analysis for such extensions, which we leave for future research. We agree that it would be interesting to further use our techniques to study a broader range of distributions. Moreover, we also believe that our techniques can be used to further study other phenomena, beyond benign and tempered overfitting, by utilizing the implications of the implicit bias of gradient methods towards margin maximization."}, {"review_id": "sUt0Pt6EoK", "reviewer": "Reviewer_dEM1", "summary": "This paper considers the various settings of overfitting, including benign overfitting where an interpolating estimator is optimal in spite of perfectly fitting noisy labels, tempered overfitting where an interpolating estimator is inconsistent but error is a function of the label noise, and catastrophic overfitting where an interpolating estimator has no ability to generalize (random guessing in classification or infinite risk in regression). The authors follow-up prior works in benign overfitting by showing that a two layer neural network can benignly overfit so long as the input dimension of the data grows faster than the number of training samples, irrespective of the width of the network itself (assuming convergence to a max-margin solution, and additionally show another benign overfitting result that only requires convergence to a KKT point of a max-margin problem). \n\nThey also provide a theoretical justification for tempered overfitting in two-layer ReLU networks, a phenomena that was empirically studied in prior work. The authors precisely characterize the excess risk of an interpolating network trained to fit uniform data with labels samples as +1 and flipped to -1 with probability p. The authors show that for one-dimensional data, the excess risk of such a network interpolating this problem is tightly bounded by functions of the noise level (e.g. theta(poly(p)) and theta(p) in a more restrictive setting).\n\nThe authors then observe that catastrophic overfitting can occur when forcing networks, of width at least 2, without a bias to interpolate the training data (drawn as specified before) when there is at least one sample with -1 label. They also show that you cannot obtain benign overfitting from convergence to a KKT point of the max-margin problem unless the network has a bias term.\n\nFinally, the authors provide an extended version of an experiment from prior work on tempered overfitting in which fully-connected ReLU networks are trained to interpolate data on the unit sphere with +1/-1 labels sampled with probability p, as defined before. They observe that there are regions between benign and tempered that are a function of the ratio of input data dimension to number of training samples, namely: as the input data dimension grows higher than the number of training samples, the excess risk of the model approaches 0. They additionally show experimental results on 3-layer networks to empirically assert that, while their theory holds for 2 layer networks practically the same behavior is seen for 3. Finally, they experimentally show in their setting that the width of the network is not as important as the input dimension when evaluating consistency of the estimator.\n\nEDIT: Thank you for the rebuttal and engaging response, this is indeed a very thoughtful work. I opt to keep my positive score.", "questions": "In the setting where all layers are trained the width does not seem to be so important. This definitely speaks to the intuition I have that the ambient dimension of the data is what matters. When studying a random feature model the ambient dimension is indicated by the width of the first layer, but when you train that layer too the ambient dimension would be the input dimension. These results make me want to understand more the interplay between intrinsic and ambient dimension, as well as bottleneck vs. non-bottleneck networks in overfitting. Do you have any further intuitions about these comparisons? Is this width-independence something you would expect to hold for deeper networks, or other architectures?\n\nDoes Proposition 4.5 subsume Proposition 4.4? Could you explain a bit more about the difference here.  n=2 in Prop 4.5 would lead to a lower bound of ¼ but in Prop 4.4 the lower bound is ½. I haven’t read deeply the proofs on this section but it might help to give a little more exposition on what assumptions are made about width that differ between 4.4 and 4.5.\n\nYou prove tempered overfitting for one-dimensional data only, but practically it seems that it is more about certain settings where the ratio of input dimension to number of samples satisfies some criteria (at least, experimentally and based on prior works). Can you speak to the difference between the theorem you propose and practice? It appears that tempered overfitting could occur at any input dimension, depending on how much training data is used. Can your proof techniques be extended to explain this?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper provides a clear theoretical analysis for tempered overfitting for two-layer ReLU networks that has not appeared in prior literature. There is some earlier theoretical work on tempered overfitting in kernel regression and for minimum description length settings, but as far as I know nothing for a standard finite-width neural network. The prior cited work (Mallinar et al. 2022) shows experimental evidence with neural networks that suggests tempered overfitting, and following their formalisms the authors of this work go a step further to give proofs of excess risk of one of the experiments in that paper (more on this in later section). \n\nI really appreciate the authors providing proof outlines and intuitions in the main text, as well as citing references where they are using techniques and following proof styles introduced in prior works. The style of explanation is accessible and gives me, at a high level, the right amount of information to contextualize the theorem statement while deferring details to the appendix should I want to review them.\n\nThere are many intriguing results from this paper. For one, I am initially surprised by the one-dimensional tempered results and Theorem 4.1 on benign overfitting feature bounds that don’t depend on the width of the network. I’ve written more about this in the questions section, but I would have expected a more subtle interplay between width of the network and input dimension of the data. Notably, though, the width of the network has to be sufficiently large to interpolate the data (e.g. overparameterized) and since the authors study 2-layer networks this might imply a large width, though their experimental results show roughly similar behavior for width 3000 and width 50 networks) across varying input dimensionality.\n\nI find the role of bias section illuminating as well. To the best of my knowledge, I haven’t seen a generic negative result like this, that any bias-less network will have a risk lower bounded by a function of the network width or the support of the negative training samples.", "weaknesses": "The authors do acknowledge it and give a tighter bound subsequently under stronger assumptions, but Theorem 3.1 has an upper and lower bound gap that is growing with p. It’s not really a weakness of the paper, but it would be nice if the authors wrote a bit about when this bound can be very tight (as a function of p, m?).\n\nTheorem 4.3 seems to indicate a dependence on p being smaller than some constant divided by the width of the network squared, which seems to indicate for very wide networks that this result holds for p shrinking -> 0. While interesting, I’m not sure if this is the most general result and the authors don’t discuss in too much detail the implications of this, and what settings of network width lead to various results apart from n=O(1). For instance, it could be useful to assert if p is meaningful for n >> m or n ~ m, etc. There are common settings of network width with relation to number of samples or input dimensionality and at first glance I don’t know whether this theorem will give me a useful result in many of those settings. \n\nAdditionally, this theorem trades off one assumption (convergence to a max-margin solution vs. KKT point of max-margin problem) for another (output weights are fixed as +- 1 and only the input weights are trained). They mention this theorem stems from attempting to drop the strong assumptions of the prior theorem (Theorem 4.1), but to me it seems perhaps to still include a new, strong assumption. Granted, I’m unfamiliar with the works cited in the footnote that study this setting in particular. Maybe the authors can provide a little exposition about why this setting is of particular interest and what motivates it in the grander study of neural networks?\n\nMissing concluding thoughts, would like to see some final discussion on everything and where the authors see next steps going.\n\nOther notes / fixes:\n\n- Page 5, 3rd paragraph: double “we we” in the line “we we get that the total length of all…”\n- Figures could use grid-lines as well as separate line-styles to differentiate the settings for accommodation to colorblind people and for printing in black and white", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very thorough review, constructive comments and positive feedback.\n\n- Bound for Theorem 3.1: We acknowledge that this bound is not tight (even for very large values of $m$), while the bound in Theorem 3.2 is tight yet requires stronger assumptions. We believe that the non-tightness of the bound is an artifact of the proof technique, and may be improved using a different analysis.\n\n- Theorem 4.3 and dependence of $p$ on $n$: We believe that this is also an artifact of the proof technique, since we only used the relatively-weak assumption of convergence to a KKT point, instead of convergence to a local or global minimum of the max-margin problem. Removing this dependence may require a more intricate analysis, or an assumption on \"which\" KKT point the network converge to. We note that in our experiments there is indeed no dependence of $p$ on $n$, which indicates that this assumption might be removed via a different analysis.\n\n- Assumption on fixed output weights: This setting is mostly used to make the analysis more tractable, hence it is used in many different works even beyond the topic of benign overfitting (e.g. for analyzing optimization in neural networks). We will elaborate the exposition on this assumption, and include some citations of related works.\n\n- Concluding thoughts: Thank you for these suggestions. We will add a conclusion section to the camera ready version if space permits, and make the figures more accessible to colorblind people by adding grid-lines and different line styles.\n\n- \"Is this width-independence something you would expect to hold for deeper networks, or other architectures?\": \nWe do expect that width independence will hold for other architectures, under the assumption of convergence to a solution of the max-margin problem. In fact, such convergence indicates that the norm of all the weights is bounded, and adding more neurons shouldn't affect this bound. This may imply that the norm of the weights has a larger effect on the analysis, than the width, or number of neurons -- as indicated by many works on the sample complexity of NNs. We will elaborate on this issue in the final version.\n\n- \"Does Proposition 4.5 subsume Proposition 4.4?\" Although they are similar, Proposition 4.5 does not subsume Proposition 4.4. Note that the bound from Proposition 4.5 would only show a lower bound of $\\frac{1}{4}$, while the lower bound in Proposition 4.4 is $\\frac{1}{2}$, which falls under the definition of catastrophic overfitting. We will clarify and emphasize this issue in the revision.\n\n- \"You prove tempered overfitting for one-dimensional data only...\": We do believe there is a more intricate connection between the input dimension and number of training samples for intermediate dimensions. We also think that our proof techniques (analyzing solutions or KKT points of the max-margin problem) can be extended to higher dimensions, although the analysis is much more intricate. We can currently prove these results only for 1-dimensional or very high dimensional data, and extending our techniques to intermediate dimensions is a very interesting (and possibly challenging) future direction."}, {"review_id": "DUHlBtzeoR", "reviewer": "Reviewer_s2UC", "summary": "This work examines asymptotic overfitting behavior on a simple class of toy classification problem for two-hidden-layer ReLU nets, finding that increasing input dimension tends to push the model from tempered towards benign overfitting.", "questions": "Could the authors explain the definition of \"local minimum\" before Theorem 3.2? I'm confused as to how points satisfying this condition are local minima.\n\nNote A: as an aside, just to flag it, a potentially interesting Q here seems like studying the difference between classification and regression. I suspect that Figure 1 would look different in these two cases. (In particular, for regression, the results of Mallinar et al. for KR suggest that you'd see a linear fit whose *slope* depends on input dim, whereas for classification you see this quite complicated nonlinear shape that intersections with the line $y=x$ at the endpoints. I wonder what the shape of that curve is.) This Q is AFAIK totally unstudied, even for KR, for which is seems probably tractable.", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Originality: this is, to my knowledge, the first analysis of tempered overfitting for nets outside the kernel regime. The broader problem's admittedly decently well-studied, and the conclusions here are more or less in line with intuitions from other works, but the authors are doing something new here.\n\nQuality: while I haven't checked the proofs, the theoretical results seem conceptually solid. While they rely on certain assumptions (e.g., assuming you've reached a KKT point or local minimum), the authors are upfront about these. I have some Qs about the experiments below.\n\nClarity: the paper's very well organized and written. Most things were clear on a single linear readthrough.\n\nSignificance: to my mind, the nice takeaways here are (a) the identification of a very simple toy problem for the study of these regimes and (b) theoretical results for classification that complement those of Mallinar et al. (which only study (kernel) *regression*). It's nice that the authors recover the $\\Theta(p)$ scaling in their Theorem 3.2. I hadn't seen the cited results about margin maximization used in a setting like this; it's nice that they let one avoid consideration of the network dynamics entirely.", "weaknesses": "One omission here seems to be comparison to the experiment of Figure 9 of Mallinar et al, which shows that Laplace kernels basically exhibit the core phenomenon found by the paper: i.e., larger input dim pushing fitting from tempered to benign (with no need to scale dim w.r.t. dataset size).\n\nI suppose the biggest weakness here is that this paper's results seem like exactly what you'd intuitively expect from (the much simpler model of) kernel regression, and so it's sort of unclear what new thing we've gained from this long set of calculations. (For the purposes of review, I wouldn't count this *against* the work -- and I do appreciate that establishing facts for neural nets is hard, and improving techniques there is useful.) It's also sort of unclear to me that the proof techniques used here will scale to other problems -- they seem clever but ad-hoc, and the tempered results rely crucially on the input space being 1D -- and so it's not obvious that, e.g., the specialized + expected results here will enable extension to other more general + powerful conclusions later.\n\nThe empirics seem generally good, but a bit odd in certain ways. For example, the input dimensions are very large! The aforementioned Figure 9 of Mallinar et al. suggests that much smaller input dims should be needed to see the correct behavior here. (Could be due to the difference between classifcation + regression; see note A below). A bigger oddity's that the difference in training set size between the two plots of Figure 1 is only 4x, which is quite small. It seems like the authors are trying to say that maybe \"when [input dim] >> [dataset size], fitting is benign, and vice versa,\" but if that's the message, there are much more compelling ways of showing that, including having much greater variation in both parameters or making a 2D heatmap at some fixed and intermediate $p$.\n\nAnother concern with the empirics is that converging can presumably take a very long time when you're relying on the exponential tail of the loss fn to push you. Seems worth confirming that these experiments won't change after a much longer training time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thorough review and constructive comments.\n\n- \"Comparison to the experiment of Figure 9 of Mallinar et al.\": This is indeed an interesting comparison, although we point out that we analyze a classification setting, while the aforementioned experiment deals with regression. We agree it would be very interesting to examine the relations between these two settings, though this is beyond the scope of our paper.\n\n- \"This paper's results seem like exactly what you'd intuitively expect from... kernel regression\": As far as we know, our work gives the first theoretical result for tempered overfitting in neural networks - which even if \"confirming prior beliefs\", is interesting by its own right in our opinion. Moreover,  we note that our work is on classification, while most previous works (for kernels) examined regression settings.\n\n- \"The empirics seem generally good, but a bit odd in certain ways\": We agree that it is possible to do a more thorough empirical study, as was done by Mallinar et al., although this is not the main focus of our paper.\n\n\n- \" ...converging can presumably take a very long time when you're relying on the exponential tail... \": In our experiments we trained for $20k$ epochs (line 375), which is much longer than it takes to reach an accuracy of $100$%.  We also tested for longer training times ($100k$ epochs) and the results were not affected.\n\n- \"Definition of local minimum before Theorem 3.2\": This is the standard definition of a local minimum under constraints, as opposed to a local minimum in the general unconstrained sense. In other words, $\\theta$ is a local minimum of a function $f$ under some constraints, if there exists a neighborhood containing it, such that every $\\theta'$ in this neighborhood which also satisfies the constraints satisfies $f(\\theta')\\geq f(\\theta)$. Note that in our case, $f$ is just the $L_2$ norm function, while the constraints are interpolating the dataset. We will make further attempts to clarify this issue in the final version."}]

Author rebuttal:

Meta-review: This paper theoretically studies the phenomenon of "benign overfitting", in a certain simplified setting. They find that for two-layer ReLU networks, increasing the input dimension can shift the model from the tempered to the benign regime.
Reviewers were enthusiastic about the strength of the work, and the clarity of the writing. Extending the theoretical study of benign overfitting beyond kernels is a valuable contribution. Thus, I recommend acceptance.
Decision: Accept (spotlight)