Benign Overfitting in Deep Neural Networks under Lazy Training
This paper focuses on over-parameterized deep neural networks (DNNs) with
ReLU activation functions and proves that when the data distribution is
well-separated, DNNs can achieve Bayes-optimal test error for classification
while obtaining (nearly) zero-training error under the lazy training regime.
For this purpose, we unify three interrelated concepts of overparameterization,
benign overfitting, and the Lipschitz constant of DNNs. Our results indicate
that interpolating with smoother functions leads to better generalization.
Furthermore, we investigate the special case where interpolating smooth
ground-truth functions is performed by DNNs under the Neural Tangent Kernel
(NTK) regime for generalization. Our result demonstrates that the
generalization error converges to a constant order that only depends on label
noise and initialization noise, which theoretically verifies benign
overfitting. Our analysis provides a tight lower bound on the normalized margin
under non-smooth activation functions, as well as the minimum eigenvalue of NTK
under high-dimensional settings, which has its own interest in learning theory.
Zhenyu Zhu, Fanghui Liu, Grigorios G Chrysos, Francesco Locatello, Volkan Cevher
# Benign Overfitting in Deep Neural Networks under Lazy Training

###### Abstract

This paper focuses on over-parameterized deep neural networks (DNNs) with ReLU activation functions and proves that when the data distribution is well-separated, DNNs can achieve _Bayes-optimal_ test error for classification while obtaining (nearly) zero-training error under the lazy training regime. For this purpose, we unify three interrelated concepts of overparameterization, benign overfitting, and the Lipschitz constant of DNNs. Our results indicate that interpolating with smoother functions leads to better generalization. Furthermore, we investigate the special case where interpolating smooth ground-truth functions is performed by DNNs under the Neural Tangent Kernel (NTK) regime for generalization. Our result demonstrates that the generalization error converges to a constant order that only depends on label noise and initialization noise, which theoretically verifies benign overfitting. Our analysis provides a tight lower bound on the normalized margin under non-smooth activation functions, as well as the minimum eigenvalue of NTK under high-dimensional settings, which has its own interest in learning theory.

Machine Learning, Deep Neural Networks, Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Learning, Deep Neural Networks, Neural Networks, Learning,
summarized below:

* We adhere to the standard data setting with label noise that has been previously explored in two-layer networks (Frei et al., 2022), along with the model setting for multi-layer fully connected neural networks (Cao and Gu, 2019; Allen-Zhu et al., 2019). Building upon the proof concept of (Frei et al., 2022), we extend our results to deep ReLU neural networks, which presents a considerable challenge in connecting the Bayes-optimal test error to the training dynamics of deep neural networks. Theorem 1 for binary classification shows that, under the lazy training regime, even though training on noisy data, DNNs can still obtain the _Bayes-optimal_ test error, i.e., the error rate is less than the proportion of incorrect labels in the training set plus a generalization term that converges to zero. We also demonstrate that this term is positively correlated with the Lipschitz constants of DNNs, which implies that interpolating more smooth functions leads to a faster convergence rate.
* Theorem 2 provides the first lower bound on the minimum eigenvalues of the NTK matrix of DNNs in the high-dimensional setting and demonstrates its phase transition under different tendencies of the number of training data and input dimension. We believe that it has its own interest in learning theory.
* Theorem 3 builds the generalization guarantees of over-parameterized neural networks under the NTK regime in the high-dimensional setting to learn a ground-truth function in RKHS. Our result exhibits a phase transition on the excess risk (related to generalization performance) between the \(n<d\) and \(n>d\) case. It implies that the excess risk finally converges to a constant order only relying on the label noise and initialization noise, which theoretically verifies the benign overfitting.

**Technical challenges.** The main technical challenge of this paper is how to derive the lower bound of the non-smooth function in deep ReLU neural networks for the normalized margin on test points. In the context of lazy training (Chizat et al., 2019), the function of a neural network is nearly linear during the initial stages of training. By analyzing the accumulation of weights for each training step, we can establish a lower bound for the normalized margin on test points. By doing so, we transform the _Bayes-optimal_ test error to the expected risk and Lipschitz constant of DNNs.

When compared with Frei et al. (2022) on shallow neural networks with smooth activation functions for binary classification, we extend their results to our deep ReLU neural networks, not limited to high-dimensional settings, and obtain a faster convergence rate with the number of data. The key difficulty lies in how to build the relationship between the _Bayes-optimal_ test error and the training dynamics of DNNs. When compared to the generalization results of deep neural networks (DNNs) in the over-parameterized regime (Cao and Gu, 2019), our results focus on overfitted models that are trained by noisy data and achieve a faster convergence rate. Besides, Ju et al. (2022) present generalization guarantees on three-layer neural networks (only the last layer is training) for regression, which has the closed-form min \(L^{2}\)-norm solution. However, this nice property is invalid in our DNN setting. In this case, we build the connection between DNNs and kernel methods (e.g., NTK) in high dimensional settings for benign overfitting.

### Related work

**Benign overfitting:** There has been a significant amount of research devoted to understanding the phenomenon of benign overfitting, with a particular emphasis on linear models, e.g., linear regression (Bartlett et al., 2020; Chatterji et al., 2021; Zou et al., 2021), sparse linear regression (Chatterji and Long, 2022; Koehler et al., 2021; Wang et al., 2022), logistic regression (Montanari et al., 2019; Wang et al., 2021), ridge regression (Tsigler and Bartlett, 2020) and kernel-based estimators (Mei and Montanari, 2022; Liang et al., 2019). Furthermore, the concept of benign overfitting can be extended to tempered or catastrophic based on various spectra of the kernel (ridge) regression (Mallinar et al., 2022).

For nonlinear models, Li et al. (2021) study the benign overfitting phenomenon of random feature models. Frei et al. (2022) prove that a two-layer fully connected neural network exhibits benign overfitting under certain conditions, e.g., well-separated log-concave distribution and smooth activation function. Then Xu and Gu (2023) extends the previous results to the non-smooth case. Similarly, Cao et al. (2022) focus on the benign overfitting of two-layer convolutional neural networks (CNN).

Mallinar et al. (2022) argue that many true interpolation methods (such as neural networks) for noisy data are not benign but tempered overfitting, and even catastrophic under various model capacities.

**Generalization of NNs and Neural Tangent Kernel (NTK):** The generalization ability of neural networks has been a core problem in machine learning theory. Brutzkus et al. (2017) show that SGD can learn an over-parameterized two-layer neural network with good generalization ability. Allen-Zhu et al. (2019) study the generalization performance of SGD for \(2\)- and \(3\)-layer networks. Cao and Gu (2019) study the training and generalization of deep neural networks (DNNs) in the over-parameterized regime. Besides, Arora et al. (2019); Cao and Gu (2020); E et al. (2020) provide the algorithm-dependent generalization bounds for different settings.
The NTK (Jacot et al., 2018) is a powerful tool for deep neural network analysis. Specifically, NTKs establish equivalence between the training dynamics of gradient-based algorithms for DNNs and kernel regression under specific initialization, so it can be considered as an intermediate step between simple linear models and DNNs (Allen-Zhu et al., 2019; Du et al., 2019; Chen et al., 2020). Besides, the convergence rate (Arora et al., 2019) and generalization bound (Cao and Gu, 2019; Zhu et al., 2022; Nguyen et al., 2021; Bombari et al., 2022) can be linked to the minimum eigenvalue of the NTK matrix.

One can see that studying benign overfitting for DNNs is missing and it appears possible to borrow some ideas from deep learning theory, e.g., NTK. Nevertheless, we need to tackle the noisy training as well as the high-dimensional setting for benign overfitting, which is our main interest.

## 2 Problem Settings

In this section, we detail the problem setting for a deep ReLU neural network trained by SGD from the perspective of notations, neural network architecture, initialization schemes, and optimization algorithms.

### Notation

In this paper, we use the shorthand \([n]:=\{1,2,\ldots,n\}\) for a positive integer \(n\). We denote by \(a(n)\gtrsim b(n)\): the inequality \(a(n)\geq cb(n)\) that hides a positive constant \(c\) that is independent of \(n\). Vectors (matrices) are denoted by boldface, lower-case (upper-case) letters. The standard Gaussian distribution is \(\mathcal{N}(0,1)\) with the zero-mean and the identity variance. We use the \(\text{Lip}_{f}\) to represent the Lipschitz constant of the function \(f\). We follow the standard Bachmann-Landau notation in complexity theory e.g., \(\mathcal{O}\), \(o\), \(\Omega\), and \(\Theta\) for order notation.

### Network

Here we introduce the formulation of DNNs. We focus on the typical depth-\(L\) fully-connected ReLU neural networks with scalar output, width \(m\) on the hidden layers and \(n\) training data, \(\forall i\in[n]\):

\[\mathbf{h}_{i,0}=\mathbf{x}_{i}; \tag{1}\] \[\mathbf{h}_{i,l}=\phi(\mathbf{W}_{l}\mathbf{h}_{i,l-1});\quad\forall l\in[L- 1];\] \[f(\mathbf{x}_{i};\mathbf{W})=\mathbf{W}_{L}\mathbf{h}_{i,L-1};\]

where \(\mathbf{x}_{i}\in\mathbb{R}^{d}\) is the input, \(f(\mathbf{x}_{i};\mathbf{W})\in\mathbb{R}\) is the neural network output, and \(\phi=\max(0,x)\) is the ReLU activation function. The neural network parameters formulate the tuple of weight matrices \(\mathbf{W}:=\{\mathbf{W}_{l}\}_{l=1}^{L}\in\{\mathbb{R}^{m\times d}\times(\mathbb{R}^ {m\times m})^{L-2}\times\mathbb{R}^{1\times m}\}\).

**Initialization:** We follow the standard Neural Tangent Kernel (NTK) initialization (Allen-Zhu et al., 2019):

\[[\mathbf{W}_{1}]_{i,j}\sim\mathcal{N}(0,\tfrac{2}{m});\quad\forall i,j\in[m]\times [d]; \tag{2}\] \[\mathbf{W}_{l}]_{i,j}\sim\mathcal{N}(0,\tfrac{2}{m});\quad\forall i,j \in[m]\quad\text{and}\quad l\in[L-2]+1;\] \[\mathbf{W}_{L}]_{i,j}\sim\mathcal{N}(0,1);\quad\forall i,j\in[1] \times[m].\]

The related Neural Tangent Kernel (NTK) (Jacot et al., 2018) matrix of neural network \(f\) can be expressed as:

\[K_{\texttt{NTK}}(\mathbf{x},\widetilde{\mathbf{x}}):=\mathbb{E}_{\mathbf{W}}\left\langle \frac{\partial f(\mathbf{x};\mathbf{W})}{\partial\mathbf{W}},\frac{\partial f(\widetilde {\mathbf{x}};\mathbf{W})}{\partial\mathbf{W}}\right\rangle\,. \tag{3}\]

By virtue of \(\phi(x)=x\phi^{\prime}(x)\) of ReLU, we have \(\mathbf{h}_{i,l}=\mathbf{D}_{i,l}\mathbf{W}_{l}\mathbf{h}_{i,l-1}\), where \(\mathbf{D}_{i,l}\) is a diagonal matrix under the ReLU activation function defined as below.

**Definition 1** (Diagonal sign matrix).: For each \(i\in[n]\), \(l\in[L-1]\) and \(k\in[m]\), the diagonal sign matrix \(\mathbf{D}_{i,l}\) is defined as: \((\mathbf{D}_{i,l})_{k,k}=1\left\{(\mathbf{W}_{l}\mathbf{h}_{i,l-1})_{k}\geq 0\right\}\).

In addition, we define \(\omega\)-neighborhood to describe the difference between two matrices.

For any \(\mathbf{W}\in\mathcal{W}\), we define its \(\omega\)-neighborhood as follows:

**Definition 2** (\(\omega\)-neighborhood).: \[\mathcal{B}(\mathbf{W},\omega):=\left\{\mathbf{W}^{\prime}\in\mathcal{W}:\left\|\mathbf{ W}_{l}^{\prime}-\mathbf{W}_{l}\right\|_{\text{F}}\leq\omega,l\in[L]\right\}\,.\]

### Optimization algorithm

In our work, a deep ReLU neural network is trained by SGD on the training data \(\{(\mathbf{x}_{i},y_{i})\}_{i=1}^{n}\) sampled from a joint distribution \(P\). The data generation process is deferred to Section 3.1 for binary classification and Section 4 for regression. We employ the logistic loss for classification, which is defined as \(\ell(z)=\log(1+\exp(-z))\), and denote \(g(z):=-\ell^{\prime}(z)=\frac{1}{1+e^{z}}\) for notational simplicity.

The expected risk is defined as \(\mathbb{E}_{(\mathbf{x},y)\sim P}\ \ell\left(yf(\mathbf{x};\mathbf{W})\right)\). Denote the empirical risks under \(\ell\) by: \(\hat{L}(\mathbf{W}):=\frac{1}{n}\sum_{i=1}^{n}\ell\left(y_{i}f(\mathbf{x}_{i};\mathbf{W})\right)\), we employ SGD to minimize \(\hat{L}(\mathbf{W})\) initialized at \(\mathbf{W}^{(0)}\) with fixed step-size \(\alpha>0\), as shown in Algorithm 1.

For notational simplicity, at step \(t\), the neural network output is denoted as \(f_{i}^{(t)}=f(\mathbf{x}_{i};\mathbf{W}^{(t)})\) and the derivative of the loss function is realized to \(g_{i}^{(t)}:=g(y_{i}f_{i}^{(t)})=g(y_{i}f(\mathbf{x}_{i};\mathbf{W}^{(t)}))\).
## 3 Main Results on Binary Classification

In this section, we present our main result on benign overfitting of a ReLU DNN for binary classification under the lazy training regime. The data generation process is introduced in Section 3.1, and the related assumptions that are given in Section 3.2. Our main theory and proof sketch are presented in Section 3.3 and Section 3.4, respectively. We use NTK initialization (Allen-Zhu et al., 2019) in this section, but the main result can be easily extended to more initializations, such as He (He et al., 2015) and LeCun (LeCun et al., 2012).

### Data generation process

We consider a standard mixture model setting (Chatterji and Long, 2021; Frei et al., 2022) in benign overfitting for binary classification, where a joint distribution \(P\) is defined over \((\mathbf{x},y)\in\mathbb{R}^{d}\times\{\pm 1\}\) and samples from this distribution can have noisy labels. Following Frei et al. (2022), we first define the clean distribution \(\widetilde{P}\) and then define the true distribution \(P\) based on \(\widetilde{P}\):

1. Sample a clean label \(\widetilde{y}\) uniformly at random, \(\widetilde{y}\sim\text{Uniform}(\{+1,-1\})\).
2. Sample \(\mathbf{z}\sim P_{\text{clust}}\) that satisfy: * \(P_{\text{clust}}=P_{\text{clust}}^{(1)}\times\cdots\times P_{\text{clust}}^{(d)}\) is a product distribution whose marginals are all mean-zero with the sub-Gaussian norm at most one; * \(P_{\text{clust}}\) is a \(\lambda\)-strongly log-concave distribution over \(\mathbb{R}^{d}\) for some \(\lambda>0\); * For some \(\kappa\), it holds that \(\mathbb{E}_{\mathbf{z}\sim P_{\text{clust}}}(\|\mathbf{z}\|^{2})>\kappa d\).
3. Generate \(\widetilde{\mathbf{x}}=\mathbf{z}+\widetilde{y}\mathbf{\mu}\).
4. Then, given a noise rate \(\eta\in[0,\frac{1}{2})\), \(P\) is any distribution over \(\mathbb{R}^{d}\times\{\pm 1\}\) such that the marginal distribution of the features for \(P\) and \(\widetilde{P}\) coincide, and the total variation distance between the two distributions satisfies \(d_{\text{TV}}(\widetilde{P},P)\leq\eta\). Specifically, \(P\) has the same marginal distribution over \(\mathbf{x}\) as \(\widetilde{P}\), but a sample \((\mathbf{x},y)\sim P\) has a label equal to \(\widetilde{y}\) with probability \(1-\eta\) and has a label equal to \(-\widetilde{y}\) with probability \(\eta\). That is, the labels are flipped with \(\eta\) ratio.

We denote by \(\mathcal{C}\subset[n]\) the set of indices corresponding to samples with clean labels, and \(\mathcal{C}^{\prime}\) as the set of indices corresponding to noisy labels so that \(i\in\mathcal{C}^{\prime}\) implies \((\mathbf{x}_{i},y_{i})\sim P\) is such that \(y_{i}=-\widetilde{y}_{i}\) using the notation above.

### Assumptions

We make two assumptions about the data distribution.

**Assumption 1**(Du et al. (2019); Allen-Zhu et al. (2019)).: We assume that the data is bounded, i.e. there is a constant \(C_{\text{norm}}\) that satisfies \(\|\mathbf{x}\|_{2}\leq C_{\text{norm}}\).

**Assumption 2**.: For two different data sample \((\mathbf{x}_{1},\widetilde{y}_{1}),(\mathbf{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}\), The NTK kernel defined in Eq. (3) satisfies that:

\[\mathbb{E}_{(\mathbf{x}_{1},\widetilde{y}_{1}),(\mathbf{x}_{2},\widetilde {y}_{2})\sim\widetilde{P}}\big{[}K_{\text{NTK}}(\mathbf{x}_{1},\mathbf{x}_{2})| \widetilde{y}_{1}=\widetilde{y}_{2}\big{]}\] \[-\mathbb{E}_{(\mathbf{x}_{1},\widetilde{y}_{1}),(\mathbf{x}_{2},\widetilde {y}_{2})\sim\widetilde{P}}\big{[}K_{\text{NTK}}(\mathbf{x}_{1},\mathbf{x}_{2})| \widetilde{y}_{1}\neq\widetilde{y}_{2}\big{]}\] \[\geq C_{N}>0\,.\]

**Remark:** This assumption states that the NTK value for data points belonging to the same class is larger than that for a different class, in expectation. This makes sense in practice, since, as a kernel, the NTK is able to evaluate the similarity of two data points (Scholkopf et al., 2002): if they are from the same class, the similarity value is large and vice versa. To verify this assumption, we give an example of the two-layer NTK over a uniform distribution inside a multidimensional sphere such that \(C_{N}=\Theta(1/\sqrt{d})\), refer to Appendix B.

Besides, we also empirically verify our assumption on MNIST (Lecun et al., 1998) with ten digits from 0 to 9. We randomly sample \(1,000\) data for each digit and calculate the empirical mean (to approximate the expectation) of the two-layer NTK kernel value over these digit pairs. The experimental result is shown in Figure 1. We can see that the confusion matrix usually has a larger diagonal element than its non-diagonal element, which implies that the kernel value on the same class is often larger than that of different classes. This verifies the justification of our assumption.

### Theoretical guarantees

Based on our assumption, we are ready to present our theoretical result that the test error of a ReLU DNN is close to the Bayes-optimal (noise rate).

**Theorem 1**.: _Given a DNN defined by Eq. (1) and trained by Algorithm 1 with a step size \(\alpha\gtrsim L^{-2}(\log m)^{-5/2}\). Then under Assumption 1 and 2, for \(\omega\leq\mathcal{O}(L^{-9/2}(\log m)^{-3})\) and \(\lambda>0\), with probability at
least \(1-\mathcal{O}(nL^{2})\exp(-\Omega(m\omega^{2/3}L))\), we have:_

\[\mathbb{P}_{(\mathbf{x},y)\sim P}(y\neq\operatorname{sgn}(f(\mathbf{x}; \mathbf{W}^{(n)})))\] \[\leq \eta+\exp\bigg{(}-\lambda\Theta\bigg{(}\frac{n\alpha(1-2\eta)C_{N} }{\text{Lip}_{f(\mathbf{x};\mathbf{W}^{(n)})}}\bigg{)}^{2}\bigg{)}\,,\]

_where the \(\eta\) is the noise rate defined in Section 3.1 and \(C_{N}\) is defined in Assumption 2._

**Remark:** Theorem 1 provides the upper bound on the test error rate, including two parts. The first part is the proportion of the wrong labels in the training data. The second part exponentially decreases with the square of the number of training samples \(n\). Also, this term is positively correlated with the Lipschitz constants of DNNs after training, which implies that interpolating more smooth functions leads to a faster convergence rate. We take a closer look at this phenomenon in Section 4, analyzing how neural networks interpolate target functions in a regression setting. Overall, this bound shows that the models overfit the wrong or noisy data on the training set, but still achieve good generalization error on the testing set. This is consistent with previous work on broader settings of benign overfitting that are not limited to classification problems with label noise. For example, various regression problems Bartlett et al. (2020); Zou et al. (2021); Chatterji and Long (2022); Koehler et al. (2021); Tsigler and Bartlett (2020), classification problems of 2-layer networks Frei et al. (2022); Cao et al. (2022), 2-layer and 3-layer NTK networks Ju et al. (2021); Hu et al. (2021).

Here we discuss the (nearly) zero-training loss and how the Lipschitz constant affects our error bounds.

**SGD can obtain arbitrarily (nearly) zero-training errors on the training set:** A lot of work has shown that deep neural networks trained with SGD can obtain zero training error on the training set and perfectly fit any training label in both classification and regression problems with mean squared loss or logistic loss Du et al. (2019); Ba et al. (2019); Zou et al. (2020). These results for empirical loss need to be over-parameterized by the condition that \(m=\text{poly}(n,L)\). In Appendix D, we provide proof that the loss can be arbitrarily small on the training set under the setting of Section 2. This indicates that when the training data has label noise, the neural network will learn all the noise, that is, overfitting. Combined with the bound of the test error rate in Theorem 1, we can say that the deep neural network has a benign overfitting phenomenon.

**Lipschitz constant of the deep neural network:** Theorem 1 shows that the convergence rate of the test error rate with the amount of data and is closely related to the Lipschitz constant of the neural network. The Lipschitz constant of DNNs has been widely studied in Bubeck et al. (2021); Wu et al. (2021); Huang et al. (2021); Nguyen et al. (2021). For example, for ReLU DNNs, if we employ the result of Nguyen et al. (2021, Theorem 6.2): \(\text{Lip}_{f}\lesssim\mathcal{O}\big{(}(2\log m)^{L-1}\big{)}\), then our bound is

\[\mathbb{P}_{(\mathbf{x},y)\sim P}(y\neq\operatorname{sgn}(f(\mathbf{x}; \mathbf{W}^{(n)})))\] \[\qquad\lesssim\eta+\exp\left(-\lambda\Theta\Big{(}\frac{n}{(2 \log m)^{L-1}}\Big{)}^{2}\right)\,,\]

which leads to a better convergence rate on generalization than the two-layer result Frei et al. (2022).

### Proof sketch of Theorem 1

Let us first introduce a few relevant lemmas.

The first Lemma will follow by establishing a lower bound for the expected normalized margin on clean points, \(\mathbb{E}_{(\mathbf{x},\widetilde{y})\sim\widetilde{P}}[\widetilde{y}f(\mathbf{x}; \mathbf{W})]/\text{Lip}_{f(\mathbf{x};\mathbf{W}^{(t)})}\).

**Lemma 1**.: _Given a DNN defined by Eq. (1) and trained by Algorithm 1. For any \(t\geq 0\), assuming \(\mathbb{E}_{(\mathbf{x},\widetilde{y})\sim\widetilde{P}}[\widetilde{y}f(\mathbf{x}; \mathbf{W}^{(t)})]\geq 0\), then we have:_

\[\mathbb{P}_{(\mathbf{x},y)\sim P}(y\neq\operatorname{sgn}(f(\mathbf{x}; \mathbf{W}^{(t)})))\] \[\leq \eta+\exp\bigg{(}-\frac{\lambda}{4}\bigg{(}\frac{\mathbb{E}_{(\bm {x},\widetilde{y})\sim\widetilde{P}}[\widetilde{y}f(\mathbf{x};\mathbf{W}^{(t)})]}{ \text{Lip}_{f(\mathbf{x};\mathbf{W}^{(t)})}}\bigg{)}^{2}\bigg{)}\,.\]

We next introduce some structural results concerning the neural network optimization objective. The following lemma states that near initialization, the neural network function is almost linear in terms of its weights.

**Lemma 2**.: _Let \(\mathbf{W},\mathbf{W}^{\prime}\in\mathcal{B}(\mathbf{W}^{(0)},\omega)\) with \(\omega=\mathcal{O}(L^{-9/2}(\log m)^{-3})\), for any \(\mathbf{x}\in\mathbb{R}^{d}\) that satisfy Assump

Figure 1: Averaged kernel values among 10 classes in MNIST, where a larger kernel value indicates a higher similarity between two data pairs.
tion 1, with probability at least \(1-\exp(-\Omega(m\omega^{2}\log m))-\mathcal{O}(nL^{2})\exp(-\Omega(m\omega^{2/3}L))\), we have:_

\[|f(\mathbf{x};\mathbf{W})-f(\mathbf{x};\mathbf{W}^{\prime})-\left\langle\nabla f( \mathbf{x};\mathbf{W}^{\prime}),\mathbf{W}-\mathbf{W}^{\prime}\right\rangle|\] \[\leq \mathcal{O}(\sqrt{\omega^{2}L^{3}m\log m})\sum_{l=1}^{L-1}\|\mathbf{ W}_{l}-\mathbf{W}_{l}^{\prime}\|_{2}\.\]

The following lemma describes the change of \(yf(\mathbf{x};\mathbf{W}^{(t+1)})\) from time \(t\) to \(t+1\).

**Lemma 3**.: _Given a DNN defined by Eq. (1) and trained by Algorithm 1. For any \(t\geq 0\) and \((\mathbf{x},\widetilde{y})\sim\widetilde{P}\) that satisfy Assumption 1, with \(\omega=\mathcal{O}(L^{-9/2}(\log m)^{-3})\), with probability at least \(1-\exp(-\Omega(m\omega^{2}\log m))-\mathcal{O}(nL^{2})\exp(-\Omega(m\omega^{ 2/3}L))\), we have:_

\[\widetilde{y}[f(\mathbf{x};\mathbf{W}^{(t+1)})-f(\mathbf{x};\mathbf{W}^{(t)})]\] \[\geq \alpha g_{t}^{(t)}\left\langle\widetilde{y}\nabla f(\mathbf{x};\mathbf{ W}^{(t)}),y_{i}\nabla f(\mathbf{x}_{i};\mathbf{W}^{(t)})\right\rangle\] \[-\mathcal{O}(\sqrt{\omega^{2}L^{3}m\log m})\sum_{l=1}^{L-1}\left\| \mathbf{W}_{l}^{(t+1)}-\mathbf{W}_{l}^{(t)}\right\|_{2}\,\]

_where \((\mathbf{x}_{i},y_{i})\) is the random selected training sample at step \(t+1\)._

Based on the previous lemmas, we can now derive a lower bound on the normalized margin. Note that this lower bound on the normalized margin in conjunction with Lemma 1 results in the test error bound for the main theorem.

**Lemma 4**.: _Let us define a DNN using Eq. (1) and trained by Algorithm 1 with a step size \(\alpha\gtrsim L^{-2}(\log m)^{-5/2}\). Then under Assumption 1 and 2, for any \(t\geq 0\), \(\omega\leq\mathcal{O}(L^{-9/2}(\log m)^{-3})\), with probability at least \(1-\exp(-\Omega(m\omega^{2}\log m))-\mathcal{O}(nL^{2})\exp(-\Omega(m\omega^{2/ 3}L))\), we have:_

\[\mathbb{E}_{(\mathbf{x},\widetilde{y})\sim\widetilde{P}}[\widetilde{y}f(\mathbf{x};\bm {W}^{(t)})]\geq\Theta\big{(}t\alpha(1-2\eta)C_{N}\big{)}\,.\]

Now, we can prove Theorem 1.

Proof.: According to Lemma 1, choosing \(t:=n\), we have:

\[\mathbb{P}_{(\mathbf{x},y)\sim P}(y\neq\mathrm{sgn}(f(\mathbf{x};\mathbf{W}^{(n)})))\] \[\leq \eta+\exp\bigg{(}-\frac{\lambda}{4}\bigg{(}\frac{\mathbb{E}_{(\bm {x},\widetilde{y})\sim\widetilde{P}}[\widetilde{y}f(\mathbf{x};\mathbf{W}^{(n)})]}{ \text{\rm Lip}_{f(\mathbf{x};\mathbf{W}^{(n)})}}\bigg{)}^{2}\bigg{)}\,.\]

Then, by Lemma 4, choosing \(t:=n\) and \(\alpha\gtrsim L^{-2}(\log m)^{-5/2}\), for \(\omega\leq\mathcal{O}(L^{-9/2}(\log m)^{-3})\), with probability at least \(1-\mathcal{O}(nL^{2})\exp(-\Omega(m\omega^{2/3}L))\), we have:

\[\mathbb{E}_{(\mathbf{x},\widetilde{y})\sim P}[\widetilde{y}f(\mathbf{x};\mathbf{W}^{(n)})] \geq\Theta\big{(}n\alpha(1-2\eta)C_{N}\big{)}\,.\]

Combine the results, we have:

\[\mathbb{P}_{(\mathbf{x},y)\sim P}(y\neq\mathrm{sgn}(f(\mathbf{x};\mathbf{W}^{ (n)})))\] \[\leq \eta+\exp\bigg{(}-\lambda\Theta\bigg{(}\frac{n\alpha(1-2\eta)C_{ N}}{\text{\rm Lip}_{f(\mathbf{x};\mathbf{W}^{(n)})}}\bigg{)}^{2}\bigg{)}\,.\]

## 4 Interpolating Smooth Function by NTK

In this section, we take a closer look at the phenomenon of the relationship between Lipschitz constants of DNNs and convergence rate in Theorem 1, and accordingly analyze how neural networks interpolate smooth ground-truth functions in a regression setting from an approximation theory view (Cucker and Zhou, 2007). In this section, we will also follow the NTK initialization (Allen-Zhu et al., 2019). For other different initialization (Cao and Gu, 2019; Arora et al., 2019), similar conclusions will apply.

To be specific, let \(X\subseteq\mathbb{R}^{d}\) be an input space, and \(Y\subseteq\mathbb{R}\) be the output space, \(f_{\rho}:X\to Y\) be the ground-truth function, that is smooth in RKHS, described by the source condition in Section 4.1. We assume that the data \((\mathbf{x},y)\) is sampled from an unknown distribution \(\rho\), and \(\rho_{X}\) is the marginal distribution of \(\rho\) over \(X\). The label is generated through \(y=f_{\rho}(\mathbf{x})+\epsilon\), where \(\epsilon\) is the noise. Accordingly, denote \(L^{2}_{\rho_{X}}\) as the \(\rho_{X}\) weighted \(L^{2}\)-space and its norm \(\|f\|_{L^{2}_{\rho_{X}}}^{2}=\int_{X}|f(\mathbf{x})|^{2}\,d\rho_{X}(\mathbf{x})\), we are interested in the excess risk \(\|f(\mathbf{x};\mathbf{W}^{(t)})-f_{\rho}\|_{L^{2}_{\rho_{X}}}^{2}\), which describes how neural networks interpolate/approximate a smooth ground-truth function in a certain space (Cucker and Zhou, 2007; Bach, 2017). In this section, we use the standard NTK network and initialization, which is equivalent to Arora et al. (2019) using the initialization with standard normal distribution together with the scale factor after each layer for the training dynamics.

### Assumptions

We make the following assumptions:

**Assumption 3** (High dimensionality (Liang and Rakhlin, 2020; Liu et al., 2021)).: There exists universal constants \(c_{1},c_{2}\in(0,\infty)\) such that \(c_{1}\leq\frac{d}{n}\leq c_{2}\).

**Assumption 4** (Noise condition (Liang and Rakhlin, 2020; Liu et al., 2021)).: There exists a \(\sigma_{\epsilon}>0\) such that \(\mathbb{E}[(f_{\rho}(\mathbf{x})-y)^{2}|\mathbf{x}]\leq\sigma_{\epsilon}^{2}\), almost surely.

**Assumption 5** (Geifman et al. (2020); Chen and Xu (2021)).: We assume that \(\mathbf{x}_{i},\forall i\in[n]\) are i.i.d. sampled from a uniform distribution on the \(d\)-dimensional unit sphere. i.e. \(\mathbf{x}\sim\text{Unif}(\mathbb{S}^{d-1}(1)),\;\mathbb{S}^{d-1}(1):=\big{\{}\mathbf{x} \in\mathbb{R}^{d}|\,\|\mathbf{x}\|_{2}=1\big{\}}\).
**Remark:** The i.i.d unit sphere data assumption implies that the data \(\mathbf{x}\) is isotropic _asymptotically_ under our high-dimensional setting (Wainwright, 2019), i.e., \(\mathbb{E}[\mathbf{x}\mathbf{x}^{\top}]=\mathbb{I}_{d}/d\). In fact, there is an alternative way in our proof by directly assuming \(\mathbf{x}\) is sub-Gaussian and \(\mathbb{E}[\mathbf{x}\mathbf{x}^{\top}]=\mathbb{I}_{d}/d\).

**Assumption 6** (Existence of \(f_{\rho}\)).: We assume the ground-truth function \(f_{\rho}\in\mathcal{H}_{\text{NTK}}\), where \(\mathcal{H}_{\text{NTK}}\) is the RKHS associated with the limiting NTK kernel.

**Remark:** This is a standard assumption in learning theory by assuming that the ground-truth function \(f_{\rho}\) is indeed realizable (Cucker and Zhou, 2007; Rudi and Rosasco, 2017; Liu et al., 2021). This assumption is a special case of the source condition (Cucker and Zhou, 2007) by taking certain values and can be easily extended to non-RKHS spaces or teacher-student settings (Hinton et al., 2015). For ease of analysis, we directly assume the ground-truth function in an RKHS.

### Kernel regression estimator

Let \(\mathbf{X}\in\mathbb{R}^{n\times d}\) be a matrix, each column of which is the input of one training sample, \(\mathbf{\epsilon}\in\mathbb{R}^{n\times 1}\) be the noise in the output of training data. The empirical risk minimization (ERM) is defined with the squared loss:

\[\hat{f}_{\mathbf{z}}=\arg\min_{f\in\mathcal{F}}\left\{\frac{1}{2n}\sum_{i=1}^{n}(f (\mathbf{x}_{i})-y_{i})^{2}\right\}\,, \tag{4}\]

where the hypothesis space \(\mathcal{F}\) can be defined properly. For example, if \(\mathcal{F}\) is a RKHS \(\mathcal{H}_{\mathbf{K}}\), Eq. (4) is formulated as a kernel regression. Denoting that \(\mathbf{K}_{\texttt{ker}}(\mathbf{x},\mathbf{X})=[\mathbf{K}_{\texttt{ker}}(\mathbf{x},\mathbf{x}_{1 }),\mathbf{K}_{\texttt{ker}}(\mathbf{x},\mathbf{x}_{1}),\ldots,\mathbf{K}_{\texttt{ker}}(\mathbf{ x},\mathbf{x}_{n})]^{\top}\in\mathbb{R}^{n}\), the closed form of the kernel regression estimator to Eq. (4) is given by:

\[f_{\texttt{ker}}=\mathbf{K}_{\texttt{ker}}(\mathbf{x},\mathbf{X})^{\top}\mathbf{K}_{\texttt{ ker}}^{-1}\mathbf{y}\,.\]

If we use a neural network as in Eq. (1) to solve Eq. (4), the corresponding hypothesis space \(\mathcal{F}_{\texttt{nn}}\) is:

\[\mathcal{F}_{\texttt{nn}}:=\left\{f(\mathbf{x};\mathbf{W})\text{ admits Eq. \eqref{eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq: eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq: eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq: eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq:eq: eq:eq
eigenvalue of \(\mathbf{K}_{\text{\tiny{RTK}}}\). Then, under Assumption 3 and 5, with probability at least \(1-2e^{-n}\), we obtain that:_

\[\lambda_{0}\geq\left\{\begin{array}{ll}2\mu_{1}^{2}\frac{n}{d} \Big{(}\frac{3}{4}-\frac{c}{4}\sqrt{\frac{d}{n}}\Big{)}^{2},&\text{if}\quad n \geq d,\\ 2\mu_{1}^{2}\frac{n}{d}\Big{(}\sqrt{\frac{d}{n}}-\frac{c+6}{4}\Big{)}^{2},& \text{if}\quad n<d\,,\end{array}\right.\]

_where we have an absolute constant \(c=2^{3.5}\sqrt{\log(9)}\approx 16.77\) and \(\mu_{1}\) is the \(1\)-st Hermite coefficient of the ReLU activation function._

**Remark:** This theorem provides the upper bound of the minimum eigenvalue of the NTK matrix of the infinite-width neural network under the high-dimensional setting and can be easily extended to the finite-width setting. Note that our result under the high dimensional setting is different from previous work under the fixed \(d\) setting in Zhu et al. (2022). If we fix \(d\) and vary \(n\) from small to large, there exists a phase transition when \(n\) increases, see Table 1. If \(n\ll d\), the lower bound of the minimum eigenvalue of NTK \(\lambda_{0}\geqslant\Omega(1)\), then when \(n\) increases, we can see that \(\lambda_{0}\) decreases to a bottom and then increases until \(n:=d\). In the \(n\geq d\) regime, there exists a similar trend to that of the \(n\leq d\) regime: firstly decreasing and then increasing. When \(n\gg d\), we have \(\lambda_{0}\geqslant\Omega(n)\).

### Generalization error bound

Based on the aforementioned upper and lower bounds of the minimum eigenvalue of NTK under the high dimensional setting, we establish the relationship between the minimum eigenvalue of NTK and the generalization error of DNNs. We provide a bound on the norm of the difference between the network output and ground truth function under the weighted \(L^{2}_{\rho_{X}}\) space.

**Theorem 3** (An upper bound on the generalization error for deep over-parameterized NTK network).: _Let \(\theta\in(0,1/2]\), \(\delta\) and \(c\) are some non-negative constants, the ground-truth function \(f_{\rho}\) lies in a RKHS by Assumption 6 and \(d\) large enough, under Assumption 3, 4 and 5, suppose that, \(\omega\leq poly(1/n,\lambda_{0},1/L,1/\log(m),\epsilon,1/\log(1/\delta^{\prime }),\kappa),\ m\geq poly(1/\omega)\) and \(\kappa=\mathcal{O}(\frac{\epsilon}{\log(n/\delta^{\prime})})\). then for any given \(\varepsilon>0\), with high probability, we have:_

\[\mathbb{E}\left\|f_{\text{nn}}-f_{\rho}\right\|_{L^{2}_{\rho_{X}} }^{2}\lesssim\mathcal{O}\bigg{(}n^{-\theta}\log^{4}(\frac{2}{\delta})+\frac{ \sigma_{\epsilon}^{2}}{d}\mathcal{N}_{\widetilde{\mathbf{X}}}\] \[+\frac{\sigma_{\epsilon}^{2}\log^{2+4\epsilon}d}{d^{4\theta-1}} +\epsilon^{2}+\frac{n}{\lambda_{0}^{2}}\omega^{2/3}L^{5}m\log m+\frac{n^{3}} {\lambda_{0}^{6}\kappa^{2}}\bigg{)}\,,\]

_where the \(\lambda_{0}\) satisfies Theorem 2 and the effective dimension \(\mathcal{N}_{\widetilde{\mathbf{X}}}\) is defined as:_

\[\mathcal{N}_{\widetilde{\mathbf{X}}}:=\sum_{i=0}^{n-1}\frac{\lambda_{i}( \widetilde{\mathbf{X}})}{(\lambda_{i}(\widetilde{\mathbf{X}}+\gamma))^{2}}\,,\]

_with \(\widetilde{\mathbf{X}}:=\beta\mathbf{X}\mathbf{X}^{\top}/d+\alpha\mathbf{1} \mathbf{1}^{\top}\) for some non-negative constants \(\alpha\), \(\beta\), \(\gamma\)._

**Remark:**

This theorem builds a connection between DNNs and kernel methods in benign overfitting and gives the upper bound of the generalization error of the NTK network in the high-dimensional setting. To be specific,the first term is the upper bound of the bias of NTK regression, which decreases as the number of data increases. The second and the third terms jointly form the upper bound of variance of NTK regression, which is mainly affected by the effective dimension (eigenvalue decay) of the data. The fourth term is the error introduced by the initialization of the NTK neural network. The fifth and the sixth term reflect the difference between the finite-width NTK network and the infinite-width NTK network (neural tangent kernel regression), which decreases with the increase of the minimum eigenvalue of the NTK network we provide in Theorem 2.

Under refined assumptions, e.g., source condition, capacity condition (Cucker and Zhou, 2007), we can achieve \(\theta=1\) for a better convergence rate. Regarding the convergence properties, we need to make the following discussion.

The three non-negative constants \(\alpha\), \(\beta\), and \(\gamma\) are related to the linearization of the kernel matrix in the high dimension setting, refer to Liu et al. (2021) for details. Here we give the following discussion on \(\mathcal{N}_{\widetilde{\mathbf{X}}}\) under three typical eigenvalue decay of \(\mathbf{X}\mathbf{X}^{\top}\) cases, and then discuss our generalization bound. Note that when \(n>d\), the sample matrix \(\mathbf{X}\mathbf{X}^{\top}\) has at most \(d\) eigenvalues, so we can directly have \(\mathcal{N}_{\widetilde{\mathbf{X}}}\leq\mathcal{O}(d)\). Accordingly, here we present the results on the \(n<d\) case.

* **Harmonic decay:**\(\lambda_{i}(\widetilde{\mathbf{X}})\propto n/i,\forall i\in\{1,2,\ldots,r_{\star}\}\) and \(\lambda_{i}(\widetilde{\mathbf{X}})=0,\forall i\in\{r_{\star}+1,\ldots,n\}\).

\begin{table}
\begin{tabular}{l c c} \hline Range of \(n\) & Trend w.r.t. \(n\) & Limit bound \\ \hline \(n\ll d\) & - & \(2\mu_{1}^{2}\) \\ \hline \(0\leq n\leq(\frac{4}{c+6})^{2}d\) & \(\searrow\) & - \\ \hline \((\frac{4}{c+6})^{2}\leq n\leq d\) & \(\nearrow\) & - \\ \hline \(d\leq n\leq\frac{c^{2}}{9}d\) & \(\searrow\) & - \\ \hline \(\frac{c^{2}}{9}d\leq n\) & \(\nearrow\) & - \\ \hline \(n\gg d\) & - & \(\frac{9}{8}\mu_{1}^{2}\frac{n}{d}\) \\ \hline \end{tabular}
\end{table}
Table 1: The trend of the bound with respect to \(n\) under different range of \(n\) values and a fixed \(d\).
We have: \(\mathcal{N}_{\tilde{\mathbf{X}}}=\mathcal{O}(n)\), then the term \(\frac{\sigma_{\epsilon}^{2}}{d}\mathcal{N}_{\tilde{\mathbf{X}}}\leq\mathcal{O}( \frac{\sigma_{\epsilon}^{2}}{d}n)\).
* **Polynomial decay:**\(\lambda_{i}(\widetilde{\mathbf{X}})\propto n{i^{-2a}}\) with \(a>1/2,\forall i\in\{1,2,\dots,r_{\star}\}\) and \(\lambda_{i}(\widetilde{\mathbf{X}})=0,\forall i\in\{r_{\star}+1,\dots,n\}\). We have: \(\mathcal{N}_{\tilde{\mathbf{X}}}=\mathcal{O}(n^{1/2a})\), then the term \(\frac{\sigma_{\epsilon}^{2}}{d}\mathcal{N}_{\tilde{\mathbf{X}}}\leq\mathcal{O}( \frac{\sigma_{\epsilon}^{2}}{d}n^{1/2a})\leq\mathcal{O}(\frac{\sigma_{\epsilon }^{2}}{d}n)\).
* **Exponential decay:**\(\lambda_{i}(\widetilde{\mathbf{X}})\propto ne^{-ai}\) with \(a>0,\forall i\in\{1,2,\dots,r_{\star}\}\) and \(\lambda_{i}(\widetilde{\mathbf{X}})=0,\forall i\in\{r_{\star}+1,\dots,n\}\). We have: \(\mathcal{N}_{\tilde{\mathbf{X}}}=\frac{1}{a}\big{(}\frac{1}{\gamma+n\exp(-a(r_{ \star}+1))}-\frac{1}{\gamma+n\exp(-a)}\big{)}\), then the term \(\frac{\sigma_{\epsilon}^{2}}{d}\mathcal{N}_{\tilde{\mathbf{X}}}\leq\mathcal{O}( \frac{\sigma_{\epsilon}^{2}}{d}\frac{\sigma^{\star_{\epsilon}}}{n})\).

Based on our discussion on the eigenvalue decay, we are ready to discuss our generalization bound in Theorem 3. When \(n,d\) are comparably large enough, e.g., \(n\geq\frac{e^{2}}{9}d\), in this case, we have \(\mathcal{N}_{\tilde{\mathbf{X}}}\leq\mathcal{O}(d)\), according to Theorem 2 for \(\lambda_{0}\), three terms \(n^{-\theta}\log^{4}(\frac{a}{2})\), \(\frac{n}{\lambda_{0}^{2}}\omega^{2/3}L^{5}m\log m\) and \(\frac{n^{3}}{\lambda_{0}^{6}\kappa^{2}}\) convergence to \(0\). The term \(\frac{\sigma_{\epsilon}^{2}\log^{2+4}d}{d^{6}-1}\) also converges to \(0\) for a large enough \(d\). Accordingly, for large enough \(n\) and \(d\), we have

\[\mathbb{E}\left\|f_{\text{nn}}-f_{\rho}\right\|_{L^{2}_{\mathcal{ \tilde{\mathbf{X}}}}}^{2}\lesssim\mathcal{O}\big{(}\sigma_{\epsilon}^{2}+\epsilon ^{2}\big{)}\,,w.h.p\,,\]

which show that the bound only depends on the noise and random initialization term, and thus coincide with previous work on benign overfitting (Frei et al., 2022; Cao et al., 2022; Ju et al., 2022; Arora et al., 2019b).

Besides, we can also find that the phase transition exists in the minimum eigenvalue \(\lambda_{0}\) and the effective dimension \(\mathcal{N}_{\tilde{\mathbf{X}}}\) from \(n<d\) and \(n>d\). This also leads to a phase transition on the excess risk. Roughly speaking, the excess risk firstly increases with \(n\) until \(n:=d\) and then decreases with \(n\) when \(n>d\).

## 5 Conclusion and limitations

In this work, we present a theoretical analysis of benign overfitting for deep ReLU NNs. For binary classification, our results demonstrate that DNNs under the lazy training regime obtain the _Bayes-optimal_ test error with a better convergence rate than Frei et al. (2022). For regression, our results exhibit a phase transition on the excess risk from \(n<d\) to \(n>d\), of which the excess risk converges to a constant order \(\mathcal{O}(1)\) that only depends on label noise and initialization noise. The above two results theoretically validate the benign overfitting of DNNs.

We need to mention that, our results are only applicable to lazy training regimes and appear difficult to be extended to the non-lazy training regime, commonly used in practice. This is because DNN cannot be linearly approximated well under the non-lazy training regime. We leave this as a future work. Besides, an interesting direction is, extending our data-generating distribution assumption from log-concave distribution to a general one, as we require it to ensure the output of neural networks is sub-Gaussian.

## Acknowledgements

We are thankful to the reviewers for providing constructive feedback. This work was supported by Hasler Foundation Program: Hasler Responsible AI (project number 21043). This work was supported by SNF project - Deep Optimisation of the Swiss National Science Foundation (SNSF) under grant number 200021_205011. This work was supported by Zeiss. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement nd 725594 - time-data).
