From Tempered to Benign Overfitting in ReLU Neural Networks
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 type of overfitting 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.
Guy Kornowski, Gilad Yehudai, Ohad Shamir
# From Tempered to Benign Overfitting

###### 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 type of overfitting 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.

## 1 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 a 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 gradient-based training algorithms towards margin maximization, as established in a series of works throughout the past few years, leads to benign overfitting of leaky ReLU networks in high dimensions (see discussion of related work below).
Recently, Mallinar et al. (2022) suggested a more nuanced view, coining the notion of "tempered" overfitting. An interpolating learning method is said to overfit in a tempered manner if its error (with respect to the underlying distribution, and as the training sample size increases) is bounded away from the optimal possible error yet is also not "catastrophic", e.g., better than a random guess. To be more concrete, consider a binary classification setting (with labels in \(\{\pm 1\}\)), and a data distribution \(\mathcal{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\in(0,\frac{1}{2})\) (i.e., given a sampled point \(\mathbf{x}\), its associated label \(y\) equals \(\text{sign}(f^{*}(\mathbf{x}))\) with probability \(1-p\), and \(-\text{sign}(f^{*}(\mathbf{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 \(L_{\mathrm{cl}}\) denote the "clean" test error, namely \(L_{\mathrm{cl}}(N)=\Pr_{\mathbf{x}\sim\mathcal{D}}(N(\mathbf{x})\cdot f^{*}( \mathbf{x})\leq 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 \(L_{\mathrm{cl}}\) of the learned predictor approaches \(0\), \(\frac{1}{2}\), or some value in \((0,\frac{1}{2})\) respectively. In the latter case, the clean test error typically scales with the amount of noise \(p\). For example, for the one-nearest-neighbor 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 an intriguing experiment from that paper (Figure 5(b)), 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 we 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 focus on interpolating neural networks trained with exponentially-tailed losses, which are well-known to converge to KKT points of a max-margin problem (see Section 2 for more details). At a high level, our main conclusion is that for such networks, the input dimension plays a 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 width, as long as it is sufficient to interpolate the training data. In a bit more detail, our contributions can be summarized as follows:

* [leftmargin=*,noitemsep,topsep=0pt,parsep=0pt,topsep=0pt]
* **Tempered overfitting in one dimension (Theorem 3.1 and Theorem 3.2).** We prove that in one dimension (when the inputs are uniform over the unit interval), the resulting overfitting is provably tempered, with a clean test error scaling as \(\Theta(\mathrm{poly}(p))\). Moreover, under the stronger assumption that the algorithm converges to a 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 0 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 a 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.
* **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 a 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 overfitting in input dimension \(10\).

The full proofs of our results are provided in appendices A and B.

### 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., 2018, 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), who proved that the minimal norm interpolating (i.e. "ridgeless") Laplace kernel method is not consistent in any fixed dimension, while it is 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 et al., 2020, Negrea et al., 2020, Nakkiran and Bansal, 2020, Yang et al., 2021, Kochler et al., 2021, Bartlett and Long, 2021, Muthukumar et 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 our main proof strategy, in which we analyze the max-margin problem in the case of NNs (which no longer admits a closed form). Frei et al. (2022) showed that NNs with smoothed leaky ReLU activations overfit benignly when the data comes from a 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.

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 are not aware of existing works that prove tempered overfitting in the context of NNs.

In a 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, 2020). Roughly speaking, these results drew the connection between NN training to margin maximization - see Section 2 for a formal reminder. For our first result (Theorem 3.1) 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 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. \(\mathbf{x}\in\mathbb{R}^{d}\), and denote by \(\|\mathbf{x}\|\) the Euclidean norm. We use \(c,c^{\prime},\widetilde{c},C>0\) etc. to denote absolute constants whose exact value can change throughout the proofs. We denote by \([n]:=\{1,\ldots,n\}\), by \(\mathbbm{1}\left\{\cdot\right\}\) the indicator function, and by \(\mathbb{S}^{d-1}\subset\mathbb{R}^{d}\) the unit sphere. Given sets \(A\subset B\), we denote by \(\mathrm{Unif}(A)\) the uniform measure over a set \(A\), by \(A^{c}\) the complementary set, and given a function \(f:B\to\mathbb{R}\) we denote its restriction \(f|_{A}:A\to\mathbb{R}\). We let \(I\) 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(\cdot),\Omega(\cdot)\) and \(\Theta(\cdot)\) hiding absolute constants, write \(f\lesssim g\) if \(f=O(g)\), and denote by \(\mathrm{poly}(\cdot)\) polynomial factors.

Setting.We consider a classification task based on _noisy_ training data \(S=(\mathbf{x}_{i},y_{i})_{i=1}^{m}\subset\mathbb{R}^{d}\times\{\pm 1\}\) drawn i.i.d. from an underlying distribution \(\mathcal{D}:=\mathcal{D}_{\mathbf{x}}\times\mathcal{D}_{y}\). Throughout, we assume that the output values \(y\) are constant \(+1\), corrupted with independent label noise at level \(p\) (namely, each \(y_{i}\) is independent of \(\mathbf{x}_{i}\) and satisfies \(\Pr[y_{i}=1]=1-p,\ \Pr[y_{i}=-1]=p\)). Note that the Bayes-optimal predictor in this setting is \(f^{*}\equiv 1\). Given a dataset \(S\), we denote by \(I_{+}:=\{i\in[m]:y_{i}=1\}\) and \(I_{-}=\{i\in[m]:y_{i}=-1\}\). We study 2-layer ReLU networks:

\[N_{\boldsymbol{\theta}}(\mathbf{x})=\sum_{j=1}^{n}v_{j}\sigma(\mathbf{w}_{j} \cdot\mathbf{x}+b_{j})\;,\]

where \(n\) is the number of neurons or network width, \(\sigma(z):=\max\{0,z\}\) is the ReLU function, \(v_{j},b_{j}\in\mathbb{R},\ \mathbf{w}_{j}\in\mathbb{R}^{d}\) and \(\boldsymbol{\theta}=(v_{j},\mathbf{w}_{j},b_{j})_{j=1}^{n}\in\mathbb{R}^{(d+2)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_{i}N_{\boldsymbol{\theta}}(\mathbf{x}_{i})>0\) for all \(i\in[m]\). Following Mallinar et al. (2022, Section 2.3) we consider the _clean_ test error \(L_{\mathrm{cl}}(N_{\boldsymbol{\theta}}):=\Pr_{\mathbf{x}\sim\mathcal{D}_{ \mathbf{x}}}[N_{\boldsymbol{\theta}}(\mathbf{x})\leq 0]\), corresponding to the misclassification error with respect to the clean underlying distribution. It is said that \(N_{\boldsymbol{\theta}}\) exhibits benign overfitting if \(L_{\mathrm{cl}}\to 0\) with respect to large enough problem parameters (e.g. \(m,d\to\infty\)), while the overfitting is said to be _catastrophic_ if \(L_{\mathrm{cl}}\to\frac{1}{2}\). Formally, Mallinar et al. (2022) have coined tempered overfitting to describe any case in which \(L_{\mathrm{cl}}\) converges to a value in \((0,\frac{1}{2})\), though a special attention has been given in the literature to cases where \(L_{\mathrm{cl}}\) scales monotonically
or even linearly with the noise level \(p\)(Belkin et al., 2018; 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 to the logistic or exponential loss converges towards a KKT point of the _margin-maximization problem_. To that end, suppose \(\ell(z)=\log(1+e^{-z})\) or \(\ell(z)=e^{-z}\), and consider the empirical loss \(\hat{\mathcal{L}}(\mathbf{\theta})=\sum_{i=1}^{n}\ell(y_{i}N_{\mathbf{\theta}}(\mathbf{ x}_{i}))\). Suppose that \(\mathbf{\theta}(t)\) evolves according to the gradient flow of the empirical loss, namely \(\frac{d\mathbf{\theta}(t)}{dt}=-\nabla\hat{\mathcal{L}}(\mathbf{\theta}(t))\).1 Note that this corresponds to performing gradient descent over the data with an infinitesimally small step size.

Footnote 1: Note that the ReLU function is not differentiable at \(0\). This can be addressed either by setting \(\sigma^{\prime}(0)\in[0,1]\) as done in practical implementations, or by considering the Clarke subdifferential (Clarke, 1990)(see Lyu and Li, 2020; Dutta et al., 2013 for a discussion on non-smooth optimization). We note that this issue has no effect on our results.

**Theorem 2.1** (Rephrased from Lyu and Li, 2020; Ji and Telgarsky, 2020).: _Under the setting above, if there exists some \(t_{0}\) such that \(\mathbf{\theta}(t_{0})\) satisfies \(\min_{i\in[m]}y_{i}N_{\mathbf{\theta}(t_{0})}(\mathbf{x}_{i})>0\), then \(\frac{\mathbf{\theta}(t)}{\|\mathbf{\theta}(t)\|}\stackrel{{ t\to\infty}}{{\longrightarrow}} \frac{\mathbf{\theta}}{\|\mathbf{\theta}\|}\) for \(\mathbf{\theta}\) which is a KKT point of the margin maximization problem_

\[\min\quad\|\mathbf{\theta}\|^{2}\quad\mathrm{s.t.}\qquad y_{i}N_{\mathbf{\theta}}( \mathbf{x}_{i})\geq 1\quad\forall i\in[m]\enspace. \tag{1}\]

The result above shows that although there are many possible parameters \(\mathbf{\theta}\) that result in a network correctly classifying the training data, the training method has an _implicit bias_ in the sense that it yields a network whose parameters are a KKT point of Problem (1). Recall that \(\mathbf{\theta}\) is called a KKT point of Problem (1) if there exist \(\lambda_{1},\ldots,\lambda_{m}\in\mathbb{R}\) such that the following conditions hold:

\[\mathbf{\theta}=\sum_{i=1}^{m}\lambda_{i}y_{i}\nabla_{\mathbf{\theta}}N_ {\mathbf{\theta}}(\mathbf{x}_{i}) \text{(stationarity)} \tag{2}\] \[\forall i\in[m]:\enspace y_{i}N_{\mathbf{\theta}}(\mathbf{x}_{i})\geq 1 \text{(primal feasibility)}\] (3) \[\lambda_{1},\ldots,\lambda_{m}\geq 0 \text{(dual feasibility)}\] (4) \[\forall i\in[m]:\enspace\lambda_{i}(y_{i}N_{\mathbf{\theta}}(\mathbf{ x}_{i})-1)=0 \text{(complementary slackness)} \tag{5}\]

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 in 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 a 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 \(\mathcal{D}_{x}=\mathrm{Unif}([0,1])\), so that \(L_{\mathrm{cl}}\left(N_{\mathbf{\theta}}\right)=\mathrm{Pr}_{x\sim\mathrm{Unif}([ 0,1])}[N_{\mathbf{\theta}}(x)\leq 0]\). We note that although we focus here on 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 our setting, tempered overfitting occurs as 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 we may converge to) gives rise to tempered overfitting.
**Theorem 3.1**.: _Let \(d=1\), \(p\in[0,\frac{1}{2})\). Then with probability at least \(1-\delta\) over the sample \(S\sim\mathcal{D}^{m}\), for any KKT point \(\boldsymbol{\theta}=\left(v_{j},w_{j},b_{j}\right)_{j=1}^{n}\) of Problem (1), it holds that_

\[c\left(p^{7}-\sqrt{\frac{\log(m/\delta)}{m}}\right)\leq L_{\rm cl}\left(N_{ \boldsymbol{\theta}}\right)\leq C\left(\sqrt{p}+\sqrt{\frac{\log(m/\delta)}{m }}\right)\,\]

_where \(c,C>0\) are absolute constants._

The theorem above shows that for a large enough sample size \(L_{\rm cl}(N_{\boldsymbol{\theta}})=\Theta({\rm poly}(p))\), proving that the clean test error must scale roughly monotonically with the noise level \(p\), leading to tempered overfitting.2

Footnote 2: We remark that the additional summands are merely a matter of concentration in order to get high probability bounds. As for the expected clean test error, our proof readily shows that \(cp^{7}\leq\mathbb{E}_{S\sim\mathcal{D}^{m}}\left[L_{\rm cl}(N_{\boldsymbol{ \theta}})\right]\leq C\sqrt{p}\).

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 \((x_{i})_{i=1}^{m}\sim\mathcal{D}_{x}^{m}\), approximately \(p^{7}m\) of the sampled points will be part of a sequence of 7 consecutive points \(x_{i}<\cdots<x_{i+6}\) all labeled \(-1\). A lemma due to Safran et al. (2022) implies that any such sequence must contain a segment \([x_{j},x_{j+1}],\ i\leq j\leq i+5\) for which \(N_{\boldsymbol{\theta}}|_{[x_{j},x_{j+1}]}<0\), contributing to the clean test error proportionally to the length of \([x_{j},x_{j+1}]\). Under the probable event that most samples are not too close to one another, namely of distance \(\Omega(1/m)\), we we get that the total length of all such segments (and hence the error) is at least of order \(\Omega(\frac{mp^{7}}{m})=\Omega(p^{7})\).

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^{*}=O(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 \(d_{\rm VC}=O(n^{*})=O(pm)\). Thus, a standard uniform convergence result for VC classes asserts that the test error would be of order \(\frac{1}{m}\sum_{i\in[m]}\mathbbm{1}\left\{\operatorname{sign}(N_{\boldsymbol {\theta}})(x_{i})\neq y_{i}\right\}+O(\sqrt{d_{\rm VC}/m})=0+O(\sqrt{pm/m})=O (\sqrt{p})\).

While the result above establishes the overfitting being tempered with an error scaling as \({\rm poly}(p)\), we note that the range \([cp^{7},C\sqrt{p}]\) 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., 2018, Chatterji and Long, 2021, Manoj and Srebro, 2023). Therefore it is natural to conjecture that this is also true here, at least for trained NNs that we are likely to converge to. We now turn to show such a 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, Glasgow et al., 2022, Boursier and Flammarion, 2023). We say that \(\boldsymbol{\theta}\) is a local minimum of Problem (1) whenever there exists \(r>0\) such that if \(\|\boldsymbol{\theta}^{\prime}-\boldsymbol{\theta}\|<r\) and \(\forall i\in[m]:y_{i}N_{\boldsymbol{\theta}^{\prime}}(x_{i})\geq 1\) then \(\|\boldsymbol{\theta}\|^{2}\leq\|\boldsymbol{\theta}^{\prime}\|^{2}\).

**Theorem 3.2**.: _Let \(d=1\), \(p\in[0,\frac{1}{2})\). Then with probability at least \(1-\delta\) over the sample \(S\sim\mathcal{D}^{m}\), for any local minimum \(\boldsymbol{\theta}=(v_{j},w_{j},b_{j})_{j=1}^{n}\) of Problem (1), it holds that_

\[c\left(p-\sqrt{\frac{\log(m/\delta)}{m}}\right)\leq L_{\rm cl}\left(N_{ \boldsymbol{\theta}}\right)\leq C\left(p+\sqrt{\frac{\log(m/\delta)}{m}} \right)\,\]

_where \(c,C>0\) 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\).3 The proof of Theorem 3.2, which appears in Appendix A.2, is based on a different analysis than that of Theorem 3.1. Broadly speaking, the proof relies on analyzing the structure of the learned prediction function, assuming it is a local minimum of the max-margin problem. More specifically, in order to obtain the lower bound we consider segments in between samples \(x_{i-1}<x_{i}<x_{i+1}\) that are labeled \(y_{i-1}=1,y_{i}=-1,y_{i+1}=1\). Note that with high probability over the sample, approximately \(p(1-p)^{2}=\Omega(p)\) of the probability mass lies in such segments. Our key proposition is that for a KKT point which is a local minimum, \(N_{\boldsymbol{\theta}}(\cdot)\) must be linear on the segment \([x_{i},x_{i+1}]\), and furthermore that \(N_{\boldsymbol{\theta}}(x_{i})=-1,N_{\boldsymbol{\theta}}(x_{i+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 an overall error of \(\Omega(p)\). In order to prove this proposition, we 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 1 for an illustration of such a case.

Footnote 3: Similarly to footnote 2, our proof also characterizes the expected clean test error for any sample size as \(\mathbb{E}_{S\sim\mathcal{D}^{m}}\left[L_{\mathrm{cl}}(N_{\boldsymbol{\theta} })\right]=\Theta(p)\).

For the upper bound, a similar analysis is provided for segments \([x_{i},x_{i+1}]\) for which \(y_{i}=y_{i+1}=1\). Noting that with high probability over the sample an order of \((1-p)^{2}=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 an upper bound of \(O(p)\) on the possible clean test error. Indeed, we show that along such segments, by locally minimizing parameter norm the network is incentivized to stay positive.

## 4 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 \(\mathcal{D}_{\mathbf{x}}=\mathrm{Unif}(\mathbb{S}^{d-1})\) and \(d\gg m\), where \(m\) is the number of samples, so that \(L_{\mathrm{cl}}\left(N_{\boldsymbol{\theta}}\right)=\Pr_{\mathbf{x}\sim \mathrm{Unif}(\mathbb{S}^{d-1})}[N_{\boldsymbol{\theta}}(\mathbf{x})\leq 0]\). We note that our results hold for other commonly studied distributions (see Remark 4.2). We begin by showing that if the network converges to the maximum margin solution up to some multiplicative factor, then benign overfitting occurs:

**Theorem 4.1**.: _Let \(\epsilon,\delta>0\). Assume that \(p\leq c_{1}\), \(m\geq c_{2}\frac{\log(1/\delta)}{p}\) and \(d\geq c_{3}m^{2}\log\left(\frac{m}{\epsilon}\right)\log\left(\frac{m}{\delta}\right)\) for some universal constants \(c_{1},c_{2},c_{3}>0\). Given a sample \((\mathbf{x}_{i},y_{i})_{i=1}^{m}\sim\mathcal{D}^{m}\), suppose \(\boldsymbol{\theta}=(\mathbf{w}_{j},v_{j},b_{j})_{j=1}^{n}\) is a KKT

Figure 1: Illustration of the proof idea of Theorem 3.2. The dashed green perturbation reduces the parameter norm while still classifying correctly, by slightly altering exactly two neurons.
point of Problem (1) such that \(\|\mathbf{\theta}\|^{2}\leq\frac{c_{4}}{\sqrt{p}}\|\mathbf{\theta}^{*}\|^{2}\), where \(\mathbf{\theta}^{*}\) is a max-margin solution of Eq. (1) and \(c_{4}>0\) is some universal constant. Then, with probability at least \(1-\delta\) over \(S\sim\mathcal{D}^{m}\) we have that \(L_{\mathrm{cl}}\left(N_{\mathbf{\theta}}\right)\leq\epsilon\)._

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 the number of neurons \(n\), and requires \(d=\tilde{\Omega}(m^{2})\). The mild lower bound on \(m\) is merely to ensure that the negative samples concentrate around a \(\Theta(p)\) fraction of the entire dataset. Also note that the dependence on \(\epsilon\) 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.1. The main crux of the proof is showing that \(\sum_{j=1}^{n}v_{j}\sigma(b_{j})=\Omega(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 \(N_{\mathbf{\theta}}(\mathbf{x})=\sum_{j=1}^{n}v_{j}\sigma(\mathbf{w}_{j}^{\top} \mathbf{x}+b_{j})\) equals

\[\sum_{j=1}^{n}v_{j}\sigma(\mathbf{w}_{j}^{\top}\mathbf{x}+b_{j})+\sum_{j=1}^{n }v_{j}\sigma(b_{j})-\sum_{j=1}^{n}v_{j}\sigma(b_{j})\geq\sum_{j=1}^{n}v_{j} \sigma(b_{j})-\sum_{j=1}^{n}\left|v_{j}\sigma(\mathbf{w}_{j}^{\top}\mathbf{x} )\right|\;.\]

All the samples (including the test sample \(\mathbf{x}\)) are drawn independently from \(\mathrm{Unif}(\mathbb{S}^{d-1})\), thus with high probability \(|\mathbf{x}^{\top}\mathbf{x}_{i}|=o_{d}(1)\) for all \(i\in[m]\). Using our assumption regarding convergence to the max-margin solution (up to some multiplicative constant), we show that the norms \(\|\mathbf{w}_{j}\|\) are bounded by some term independent of \(d\). Thus, we can bound \(|\mathbf{x}^{\top}\mathbf{w}_{j}|=o_{d}(1)\) for every \(j\in[n]\). Additionally, by the same assumption we show that both \(\sum_{j=1}^{n}\|\mathbf{w}_{j}\|\) and \(\sum_{j=1}^{n}|v_{j}|\) are bounded by the value of the max-margin solution (up to a multiplicative factor), which we bound by \(O(\sqrt{m})\). Plugging this into the displayed equation above, and using the assumption that \(d\) is sufficiently larger than \(m\), we get that the \(\sum_{j=1}^{n}|v_{j}\sigma(\mathbf{w}_{j}^{\top}\mathbf{x})|\) term is negligible, and hence the bias terms \(\sum_{j=1}^{n}v_{j}\sigma(b_{j})\) are the predominant factor in determining the output of \(N_{\mathbf{\theta}}\).

Showing that \(\sum_{j=1}^{n}v_{j}\sigma(b_{j})=\Omega(1)\) is done in two phases. Recall the definitions of \(I_{+}:=\{i\in[m]:y_{i}=1\}\), \(I_{-}=\{i\in[m]:y_{i}=-1\}\), and that by our label distribution and assumption on \(p\) we have \(|I_{+}|\approx(1-p)m\gg pm\approx|I_{-}|\). We first show that if the bias terms are too small, and the predictor correctly classifies the training data, then its parameter vector \(\mathbf{\theta}\) satisfies \(\|\mathbf{\theta}\|^{2}=\Omega(|I_{+}|)\). Intuitively, this is because the data is nearly mutually orthogonal, so if the biases are small, the vectors \(\mathbf{w}_{j}\) must have a large enough correlation with each different point in \(I_{+}\) to classify it correctly. On the other hand, we explicitly construct a solution that has large bias terms, which satisfies \(\|\mathbf{\theta}\|^{2}=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 a 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 \(|\mathbf{x}_{i}^{\top}\mathbf{x}_{j}|=o_{d}(1)\) for every \(i\neq j\in[m]\), and that \(\|XX^{\top}\|=O(1)\) (independent of \(m\)) where \(X\) is an \(m\times d\) matrix whose rows are \(\mathbf{x}_{i}\)._

### 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-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 et al. (2022) provided several examples of ReLU neural networks where there are in fact KKT points which are not a global or even local optimum 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-margin problem. For such a result we use two additional assumptions, namely: (1) The output weights \(v_{j}\) are all fixed to be \(\pm 1\), while only \((\mathbf{w}_{j},b_{j})_{j\in[n]}\) are trained;4 and (2) Both the noise level \(p\) and the input dimension \(d\) depend on \(n\), the number of neurons. Our main result is the following:

Footnote 4: This assumption appears in prior works such as Cao et al. (2022); Frei et al. (2023); Xu and Gu (2023).

**Theorem 4.3**.: _Let \(\epsilon,\delta>0\). Assume that \(p\leq\frac{c_{1}}{n^{2}}\), \(m\geq c_{2}n\log\left(\frac{1}{\delta}\right)\) and \(d\geq c_{3}m^{4}n^{4}\log\left(\frac{m}{\epsilon}\right)\log\left(\frac{m^{2}} {\delta}\right)\) for some universal constants \(c_{1},c_{2},c_{3}>0\). Assume that the output weights are fixed so that \(|\{j:v_{j}=1\}|=|\{j:v_{j}=-1\}|\) while \((\mathbf{w}_{j},b_{j})_{j\in[n]}\) are trained, and that \(N_{\boldsymbol{\theta}}\) converges to a KKT point of Problem (1). Then, with probability at least \(1-\delta\) over \(S\sim\mathcal{D}^{m}\) we have \(L_{\mathrm{cl}}\left(N_{\boldsymbol{\theta}}\right)\leq\epsilon\)._

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=O(1)\) we get benign overfitting for any \(p\) smaller than a universal constant. This dependence is due to a technical limitation of the proof (which we will soon explain), and it would be interesting to remove it 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 \(\sum_{j=1}^{n}v_{j}\sigma(b_{j})=\Omega(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 \(\sum_{j=1}^{n}v_{j}\sigma(b_{j})=\Omega(1)\). We can write each bias term as \(b_{j}=v_{j}\sum_{i\in[m]}\lambda_{i}y_{i}\sigma^{\prime}_{i,j}\), where \(\sigma^{\prime}_{i,j}=\mathbbm{1}\left(\mathbf{w}_{j}^{\top}\mathbf{x}_{i}+b_ {j}>1\right)\) is the derivative of the \(j\)-th ReLU neuron at the point \(\mathbf{x}_{i}\). We first show that all the bias terms \(b_{j}\) are positive (Lemma B.5) and that for each \(i\in I_{+}\), there is \(j\in\{1,\ldots,n/2\}\) with \(\sigma^{\prime}_{i,j}=1\). This means that it suffices to show that \(\lambda_{i}\) is not too small for all \(i\in I_{+}\), while for every \(i\in I_{-}\), \(\lambda_{i}\) is bounded from above.

We assume towards contradiction that the sum of the biases is small, and show it implies that \(\lambda_{i}=\Omega\left(\frac{1}{n}\right)\) for \(i\in I_{+}\) and \(\lambda_{i}=O(1)\) for \(i\in I_{-}\). Using the stationarity condition we can write for \(j\in\{1,\ldots,n/2\}\) that \(\mathbf{w}_{j}=\sum_{i=1}^{m}\lambda_{i}y_{i}\sigma^{\prime}_{i,j}\mathbf{x}_ {i}\). Taking some \(r\in I_{+}\), we have that \(\mathbf{w}_{j}^{\top}\mathbf{x}_{r}\approx\lambda_{r}\sigma^{\prime}_{r,j}\) since \(\mathbf{x}_{r}\) is almost orthogonal to all other samples in the dataset. By the primal feasibility condition (Eq. (3)) \(N_{\boldsymbol{\theta}}(\mathbf{x}_{r})\geq 1\), hence there must be some \(j\in\{1,\ldots,n/2\}\) with \(\sigma^{\prime}_{r,j}=1\) and with \(\lambda_{r}\) that is larger than some constant. The other option is that the bias terms are large, which we assumed does not happen. Note that we don't know how many neurons \(\mathbf{w}_{j}\) there are with \(\sigma^{\prime}_{j,r}=1\), which means that we can only lower bound \(\lambda_{r}\) by a term that depends on \(n\).

To show that \(\lambda_{s}\) are not too big for \(s\in I_{-}\), we use the complementary slackness condition (Eq. (5)) which states that if \(\lambda_{s}\neq 0\) then \(N_{\boldsymbol{\theta}}(\mathbf{x}_{s})=-1\). Since the sum of the biases is not large, then if there exists some \(s\in I_{-}\) with \(\lambda_{s}\) that is too large we would get that \(N_{\boldsymbol{\theta}}(\mathbf{x}_{s})<-1\) which contradicts the complementary slackness. Combining those bounds and picking \(p\) to be small enough shows that \(\sum_{j=1}^{n}v_{j}\sigma(b_{j})\) cannot be too small.

### 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 \(N_{\boldsymbol{\theta}}(\mathbf{x})=\sum_{j=1}^{n}v_{j}\sigma(\mathbf{w}_{j}^ {\top}\mathbf{x})\) where \(\boldsymbol{\theta}=(v_{j},\mathbf{w}_{j})_{j\in[n]}\). We note that if the input dimension is sufficiently large and \(n\geq 2\), such bias-less networks can still fit any training data. The proofs for this section can be found in Appendix B.3.
We begin by showing that without a 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 a bias-less network with \(n=2\) which classifies a dataset correctly. If the dataset contains at least one sample with a negative label, then \(L_{\mathrm{cl}}\left(N_{\boldsymbol{\theta}}\right)\geq\frac{1}{2}\)._

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).

**Proposition 4.5** (Not benign without bias).: _For any bias-less network of width \(n\), \(L_{\mathrm{cl}}\left(N_{\boldsymbol{\theta}}\right)\geq\frac{1}{2^{n}}\)._

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 \(m\) and \(d\). Furthermore, next we show that even for 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 a bias-less network, and suppose that \(\mathbf{x}_{j}^{\top}\mathbf{x}_{i}=0\) for every \(i\neq j\). Denote \(I_{-}:=|\{i\in[m]:y_{i}=-1\}|\). Then there exists a KKT point \(\boldsymbol{\theta}\) of Problem (1) with \(L_{\mathrm{cl}}\left(N_{\boldsymbol{\theta}}\right)\geq\frac{1}{2}-\frac{1}{2 ^{|I_{-}|}}\)._

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 a positive benign overfitting result in the bias-less case, if at all possible, cannot possibly apply to all KKT points - so one must make further assumptions on which KKT points to consider or resort to an alternative analysis. The assumption that \(\mathbf{x}_{j}^{\top}\mathbf{x}_{i}=0\) for every \(i\neq j\) is made to simplify the construction of the KKT point, while we hypothesize that the proposition can be extended to the case where \(\mathbf{x}_{i}\sim\mathrm{Unif}(\mathbb{S}^{d-1})\) (or other isotropic distributions) for large enough \(d\).

## 5 Between tempered and benign overfitting for intermediate dimensions

In Section 3, we showed that tempered overfitting occurs for one-dimensional data, while in Section 4 we showed that benign overfitting occurs for high-dimensional 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 [15, Figure 6b] which considered the same distribution as we do, for \(d=10\) and \(m\) varying from \(300\) to \(3.6\times 10^{5}\). Here we study larger values of \(d\), and how the ratio between \(d\) and \(m\) affects the type of overfitting. We also focus on \(2\)-layer networks (although we do show our results may extend to depth \(3\)).

In our experiments, we trained a fully connected neural network with \(2\) or \(3\) layers, width \(n\) (which will be specified later) and ReLU activations. We sampled a dataset \((\mathbf{x}_{i},y_{i})_{i=1}^{m}\sim\mathrm{Unif}(\mathbb{S}^{d-1})\times \mathcal{D}_{y}\) for noise level \(p\in\{0.05,0.1,\ldots,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 a total of \(20k\) epochs, and was repeated \(10\) 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.
In Figure 2 we trained a \(2\)-layer network with \(1000\) neurons over different input dimensions, with \(m=500\) samples (left) and \(m=2000\) samples (right). There appears to be a gradual transition from tempered overfitting (with clean test error linear in \(p\)) to benign overfitting (clean test error close to \(0\) for any \(p\)), as \(d\) increases compared to \(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. \(d>m^{2}\)). Additionally, benign overfitting seems to occur for lower values of \(p\), whereas for \(p\) closer to \(0.5\) the clean test error is significantly above \(0\) even for the highest dimensions we examined.

We further experimented on the effects of the width and depth on the type of overfitting. In Figure 3 (left) we trained a \(2\)-layer network on \(m=500\) samples with input dimension \(d\in\{250,2000,10000\}\) and \(n\) neurons for \(n\in\{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 \(n\) has little effect on the type of overfitting (similar to most of our theoretical results), and that the dependence on \(n\) in Theorem 4.3 is an artifact of the proof technique (in accordance with our other results). In Figure 3 (right) we trained a

Figure 3: Left: \(2\)-layer network with \(n=50\) and \(n=3000\) neurons and varying input dimension. Right: \(3\)-layer network with \(n=1000\) neurons and varying input dimension. Both plots correspond to \(m=500\) samples.

Figure 2: Training a \(2\)-layer network with \(1000\) neurons on \(m\) samples drawn uniformly from \(\mathbb{S}^{d-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.
\(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 2 (left) which may indicate that our observations generalize to deeper networks.

## 6 Discussion

In this work, we studied different types of overfitting that emerge when training 2-layer ReLU neural networks to interpolate a noisy dataset in a simple classification setting. We proved that univariate data gives rise to tempered overfitting, with a clean (noiseless) test error scaling with the amount of label noise of the training data. For high dimensional data, the type of overfitting is provably benign, and the clean test error decays exponentially fast to \(0\) with respect to the input dimension. While both results depend on the network having bias terms, we showed that without bias terms, networks can exhibit catastrophic overfitting, and that in general they will not overfit benignly without further assumptions. Finally, we conducted an empirical study for intermediate dimensions and observe a gradual shift from tempered to benign overfitting as the input dimension grows.

There are several intereseting future directions which are left open by this work. First, on a more technical level, it would be interesting to bridge some of the limitations of our proof techniques. For example, proving either benign overfitting or tempered overfitting scaling linearly with the label noise, merely under the assumption of convergence to a KKT point (instead of the stronger assumptions we impose for those results), or by establishing the impossibility of such results. Our work also leaves open the theoretical understanding of other regimes of the input dimension, such as any constant dimension larger than \(1\), or high-dimensional data where the dimension scales sub-quadratically (e.g., linearly) with the number of training samples. Moreover, a compelling direction would be to extend the studied setting for other ground truth functions \(f^{*}\) which are more complex, and to more complex network architectures. Finally, it would be interesting to further study the bias-less case and assess its corresponding overfitting behavior under suitable assumptions.

### Acknowledgements

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.
