# Benign Overfitting in Deep Neural Networks under Lazy Training

Zhenyu Zhu  Fanghui Liu  Grigorios G Chrysos  Francesco Locatello  Volkan
Cevher

###### 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, ICML

.tocmtchapter mtchaptersubsection mtappendixnone

##  1 Introduction

Benign overfitting has attracted significant research interest recently in an
effort to understand why predictors with zero training loss can still achieve
counter-intuitively good generalization performance even in the presence of
noise (Koehler et al., 2021; Zou et al., 2021; Chatterji and Long, 2022; Wang
et al., 2022; Mei and Montanari, 2022). Current efforts on benign overfitting
mainly focus on the finite sample behavior under linear regression (Bartlett
et al., 2020; Chatterji et al., 2021; Zou et al., 2021), kernel-based
estimators (Mei and Montanari, 2022; Liang et al., 2019), and logistic
regression (Montanari et al., 2019; Wang et al., 2021).

To our knowledge, results on neural networks (NNs) are restricted to two-layer
neural networks (Tsigler and Bartlett, 2020; Ju et al., 2021; Frei et al.,
2022; Cao et al., 2022) and three-layer neural networks but only the last
layer is trained (Ju et al., 2022). The extension from shallow NNs to deep
neural networks (DNNs) is non-trivial: _under what conditions does benign
overfitting occur in deep neural networks?_ and _what makes them special?_ are
still open problems in both statistical learning theory and deep learning
theory.

In this work, we address this open question in benign overfitting of deep ReLU
NNs for binary classification under the lazy training regime. We assume the
network is trained by stochastic gradient descent (SGD) on well-separated data
under adversarially corrupted labels, following the standard problem setting
of Frei et al. (2022). We prove that the ReLU DNN exhibits benign overfitting,
i.e., obtaining Bayes-optimal test error while obtaining zero training error
under the lazy training regime.

Our results establish a rigorous connection between the Lipschitz constants of
DNNs and benign overfitting. We demonstrate that interpolating with
(Lipschitz) smoother functions leads to a faster convergence rate on the
generalization guarantees. Accordingly, for a better understanding of how the
estimator by DNNs interpolates the ground-truth function, we also consider a
regression task for DNNs from an approximation theory view (Cucker and Zhou,
2007), interpolating the smooth ground-truth function by DNNs under the neural
tangent kernel (NTK) regime (Bach, 2017; Jacot et al., 2018).

Overall, we expect our results to foster a refined analysis of the
generalization guarantees for large dimensional machine learning models,
especially on DNNs.

###  1.1 Contributions and technical challenges

In this paper, we consider a finite sample behavior, in which the input
dimension $d$ can be large but fixed, or comparably large with the number of
training data $n$ and model parameters to obtain a dimension-free bound
(Bartlett et al., 2020; Ju et al., 2022; Li et al., 2021). Our main
contributions are 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., 2019b). 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.

###  1.2 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. (2019a)
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.
(2019a); 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., 2019b; Du et al.,
2019a; Chen et al., 2020). Besides, the convergence rate (Arora et al., 2019b)
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.

###  2.1 Notation

In this paper, we use the shorthand $[n]:=\\{1,2,\dots,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.

###  2.2 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]$:

$\begin{matrix}\bm{h}_{i,0}=\bm{x}_{i};\\\ \\\
\bm{h}_{i,l}=\phi(\bm{W}_{l}\bm{h}_{i,l-1});\quad\forall l\in[L-1];\\\ \\\
f(\bm{x}_{i};\bm{W})=\bm{W}_{L}\bm{h}_{i,L-1};\\\ \\\ \end{matrix}$ (1)

where $\bm{x}_{i}\in\mathbb{R}^{d}$ is the input,
$f(\bm{x}_{i};\bm{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
$\bm{W}:=\\{\bm{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., 2019b):

$\begin{matrix}[\bm{W}_{1}]_{i,j}\sim\mathcal{N}(0,\frac{2}{m});\quad\forall
i,j\in[m]\times[d];\\\ \\\
[\bm{W}_{l}]_{i,j}\sim\mathcal{N}(0,\frac{2}{m});\quad\forall
i,j\in[m]\quad\text{and}\quad l\in[L-2]+1;\\\ \\\
[\bm{W}_{L}]_{i,j}\sim\mathcal{N}(0,1);\quad\forall i,j\in[1]\times[m].\\\
\end{matrix}$ (2)

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

$K_{\tt
NTK}(\bm{x},\widetilde{\bm{x}}):=\mathbb{E}_{\bm{W}}\left\langle\frac{\partial
f(\bm{x};\bm{W})}{\partial\bm{W}},\frac{\partial
f(\widetilde{\bm{x}};\bm{W})}{\partial\bm{W}}\right\rangle\,.$ (3)

By virtue of $\phi(x)=x\phi^{\prime}(x)$ of ReLU, we have
$\bm{h}_{i,l}=\bm{D}_{i,l}\bm{W}_{l}\bm{h}_{i,l-1}$, where $\bm{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
$\bm{D}_{i,l}$ is defined as:
$(\bm{D}_{i,l})_{k,k}=1\left\\{(\bm{W}_{l}\bm{h}_{i,l-1})_{k}\geq 0\right\\}$.

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

For any $\bm{W}\in\mathcal{W}$, we define its $\omega$-neighborhood as
follows:

######  Definition 2 ($\omega$-neighborhood).

$\mathcal{B}(\bm{W},\omega):=\left\\{\bm{W}^{\prime}\in\mathcal{W}:\left\|\bm{W}^{\prime}_{l}-\bm{W}_{l}\right\|_{\mathrm{F}}\leq\omega,l\in[L]\right\\}\,.$

###  2.3 Optimization algorithm

In our work, a deep ReLU neural network is trained by SGD on the training data
$\\{(\bm{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}_{(\bm{x},y)\sim
P}~{}\ell\left(yf(\bm{x};\bm{W})\right)$. Denote the empirical risks under
$\ell$ by:
$\hat{L}(\bm{W}):=\frac{1}{n}\sum_{i=1}^{n}\ell\left(y_{i}f(\bm{x}_{i};\bm{W})\right)$,
we employ SGD to minimize $\hat{L}(\bm{W})$ initialized at $\bm{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(\bm{x}_{i};\bm{W}^{(t)})$ and the derivative of the loss
function is realted to
$g_{i}^{(t)}:=g(y_{i}f_{i}^{(t)})=g(y_{i}f(\bm{x}_{i};\bm{W}^{(t)}))$.

Algorithm 1 SGD for training DNNs

Input: training data $\\{(\bm{x}_{i},y_{i})\sim P\\}_{i=1}^{n}$ and step size
$\alpha$.

Gaussian initialization: $\bm{W}_{l}^{(0)}\sim\mathcal{N}(0,2/m)$,
$l\in[L-1]$.

Gaussian initialization: $\bm{W}_{L}^{(0)}\sim\mathcal{N}(0,1)$.

for $i=1$ to $n$ do

Draw $(\bm{x}_{i},y_{i})$ from
$\\{(\bm{x}_{i},y_{i})_{i=1}^{n}\\}$.$\bm{W}^{(i)}=\bm{W}^{(i-1)}-\alpha\cdot\nabla_{\bm{W}}\ell\big{(}y_{i}f(\bm{x}_{i};\bm{W}^{(i-1)})\big{)}\,.$

end forOutput $\bm{W}^{(n)}$ for the final network $f(\bm{x};\bm{W}^{(n)})$.

##  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., 2019b) 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).

###  3.1 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 $(\bm{x},y)\in\mathbb{R}^{d}\times\left\\{\pm
1\right\\}$ 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. 1.

Sample a clean label $\widetilde{y}$ uniformly at random,
$\widetilde{y}\sim\text{Uniform}(\left\\{+1,-1\right\\})$.

  2. 2.

Sample $\bm{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}_{\bm{z}\sim
P_{\text{clust}}}(\left\|\bm{z}\right\|^{2})>\kappa d$.

  3. 3.

Generate $\widetilde{\bm{x}}=\bm{z}+\widetilde{y}\bm{\mu}$.

  4. 4.

Then, given a noise rate $\eta\in[0,\frac{1}{2})$, $P$ is any distribution
over $\mathbb{R}^{d}\times\left\\{\pm 1\right\\}$ 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 $\bm{x}$ as $\widetilde{P}$, but a sample
$(\bm{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
$(\bm{x}_{i},y_{i})\sim P$ is such that $y_{i}=-\widetilde{y}_{i}$ using the
notation above.

###  3.2 Assumptions

We make two assumptions about the data distribution.

######  Assumption 1 (Du et al. (2019a); Allen-Zhu et al. (2019b)).

We assume that the data is bounded, i.e. there is a constant $C_{\text{norm}}$
that satisfies $\|\bm{x}\|_{2}\leq C_{\text{norm}}$.

######  Assumption 2.

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

$\begin{split}&\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\big{[}K_{\tt
NTK}(\bm{x}_{1},\bm{x}_{2})|\widetilde{y}_{1}=\widetilde{y}_{2}\big{]}\\\
-&\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\big{[}K_{\tt
NTK}(\bm{x}_{1},\bm{x}_{2})|\widetilde{y}_{1}\neq\widetilde{y}_{2}\big{]}\\\
\geq&C_{N}>0\,.\end{split}$

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 (Schölkopf 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.

Figure 1: Averaged kernel values among 10 classes in MNIST, where a larger
kernel value indicates a higher similarity between two data pairs.

###  3.3 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 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:

$\begin{split}&\mathbb{P}_{(\bm{x},y)\sim
P}(y\neq\mathrm{sgn}(f(\bm{x};\bm{W}^{(n)})))\\\
\leq&\eta+\exp\bigg{(}-\lambda\Theta\bigg{(}\frac{n\alpha(1-2\eta)C_{N}}{\text{Lip}_{f(\bm{x};\bm{W}^{(n)})}}\bigg{)}^{2}\bigg{)}\,,\end{split}$

where the $\eta$ is the noise rate defined in Section 3.1 and $C_{N}$ is
defined in 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, 2022).

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., 2019b, a; Chizat 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

$\begin{split}&\mathbb{P}_{(\bm{x},y)\sim
P}(y\neq\mathrm{sgn}(f(\bm{x};\bm{W}^{(n)})))\\\
&\qquad\lesssim\eta+\exp\left(-\lambda\Theta\Big{(}\frac{n}{(2\log
m)^{L-1}}\Big{)}^{2}\right)\,,\end{split}$

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

###  3.4 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}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}[\widetilde{y}f(\bm{x};\bm{W})]/\text{Lip}_{f(\bm{x};\bm{W}^{(t)})}$.

######  Lemma 1.

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

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

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 $\bm{W},\bm{W}^{\prime}\in\mathcal{B}(\bm{W}^{(0)},\omega)$ with
$\omega=\mathcal{O}(L^{-9/2}(\log m)^{-3})$, for any $\bm{x}\in\mathbb{R}^{d}$
that satisfy 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:

$\begin{split}&|f(\bm{x};\bm{W})-f(\bm{x};\bm{W}^{\prime})-\left\langle\nabla
f(\bm{x};\bm{W}^{\prime}),\bm{W}-\bm{W}^{\prime}\right\rangle|\\\
\leq&\mathcal{O}(\sqrt{\omega^{2}L^{3}m\log
m})\sum_{l=1}^{L-1}\left\|\bm{W}_{l}-\bm{W}_{l}^{\prime}\right\|_{2}\,.\end{split}$

The following lemma describes the change of $yf(\bm{x};\bm{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
$(\bm{x},\widetilde{y})\sim\widetilde{P}$ that satisfy 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:

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

where $(\bm{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 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}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}[\widetilde{y}f(\bm{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:

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

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}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}[\widetilde{y}f(\bm{x};\bm{W}^{(n)})]\geq\Theta\big{(}n\alpha(1-2\eta)C_{N}\big{)}\,.$

Combine the results, we have:

$\begin{split}&\mathbb{P}_{(\bm{x},y)\sim
P}(y\neq\mathrm{sgn}(f(\bm{x};\bm{W}^{(n)})))\\\
\leq&\eta+\exp\bigg{(}-\lambda\Theta\bigg{(}\frac{n\alpha(1-2\eta)C_{N}}{\text{Lip}_{f(\bm{x};\bm{W}^{(n)})}}\bigg{)}^{2}\bigg{)}\,.\end{split}$

∎

##  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., 2019b). For other different initialization (Cao and Gu,
2019; Arora et al., 2019b), 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 $(\bm{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}(\bm{x})+\epsilon$, where
$\epsilon$ is the noise. Accordingly, denote $L_{\rho_{X}}^{2}$ as the
$\rho_{X}$ weighted $L^{2}$-space and its norm
$\left\|f\right\|_{L_{\rho_{X}}^{2}}^{2}=\int_{X}\left|f(\bm{x})\right|^{2}d\rho_{X}(\bm{x})$,
we are interested in the excess risk
$\|f(\bm{x};\bm{W}^{(t)})-f_{\rho}\|_{L_{\rho_{X}}^{2}}^{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. (2019b) using the initialization with standard normal distribution
together with the scale factor after each layer for the training dynamics.

###  4.1 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}(\bm{x})-y)^{2}|\bm{x}]\leq\sigma_{\epsilon}^{2}$, almost
surely.

######  Assumption 5 (Geifman et al. (2020); Chen and Xu (2021)).

We assume that $\bm{x}_{i},\forall i\in[n]$ are i.i.d. sampled from a uniform
distribution on the $d$-dimensional unit sphere. i.e.
$\bm{x}\sim\text{Unif}(\mathbb{S}^{d-1}(1)),\
\mathbb{S}^{d-1}(1):=\left\\{\bm{x}\in\mathbb{R}^{d}|\left\|\bm{x}\right\|_{2}=1\right\\}$.

Remark: The i.i.d unit sphere data assumption implies that the data $\bm{x}$
is isotropic _asymptotically_ under our high-dimensional setting (Wainwright,
2019), i.e., $\mathbb{E}[\bm{xx}^{\\!\top}]=\mathbb{I}_{d}/d$. In fact, there
is an alternative way in our proof by directly assuming $\bm{x}$ is sub-
Gaussian and $\mathbb{E}[\bm{xx}^{\\!\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.

###  4.2 Kernel regression estimator

Let $\bm{X}\in\mathbb{R}^{n\times d}$ be a matrix, each column of which is the
input of one training sample, $\bm{\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}_{\bm{z}}=\arg\min_{f\in\mathcal{F}}\left\\{\frac{1}{2n}\sum_{i=1}^{n}(f(\bm{x}_{i})-y_{i})^{2}\right\\}\,,$
(4)

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

$f_{\tt ker}=\bm{K}_{\tt ker}(\bm{x},\bm{X})^{\top}\bm{K}_{\tt
ker}^{-1}\bm{y}\,.$

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

$\begin{split}\mathcal{F}_{\tt nn}&:=\bigg{\\{}f(\bm{x};\bm{W})~{}\mbox{admits
Eq.~{}\eqref{eq:deep_network}}:\bm{x}\sim\text{Unif}(\mathbb{S}^{d-1}(1)),\\\
&\bm{W}\in\mathbb{R}^{m\times d}\times(\mathbb{R}^{m\times
m})^{L-2}\times\mathbb{R}^{1\times m}\bigg{\\}}\,,\end{split}$

which implies:

$f_{\tt nn}=\arg\min_{f\in\mathcal{F}_{\tt
nn}}\left\\{\frac{1}{2n}\sum_{i=1}^{n}(f(\bm{x}_{i};\bm{W})-y_{i})^{2}\right\\}\,.$

In addition to the neural tangent kernel mentioned earlier Eq. 3, we will
present some examples of the positive definite kernels to be studied in this
paper.

Dot product kernel (Ghosh et al., 2022): The dot product kernels have the
following forms:

$K_{\tt
dot}(\bm{x},\widetilde{\bm{x}})=k(\left\langle\bm{x},\widetilde{\bm{x}}\right\rangle),\quad\forall\bm{x},\widetilde{\bm{x}}\in\mathbb{S}^{d-1}(1)\,,$

for some function $k:[-1,1]\to\mathbb{R}$.

Laplace kernel (Geifman et al., 2020): The Laplace kernel is defined as:

$K_{\tt
Laplace}(\bm{x},\widetilde{\bm{x}})=e^{-c\left\|\bm{x}-\widetilde{\bm{x}}\right\|_{2}},\quad
c>0\,.$

According to 5, we have:

$K_{\tt
Laplace}(\bm{x},\widetilde{\bm{x}})=e^{-c\sqrt{2(1-\bm{x}^{\top}\widetilde{\bm{x}})}}=e^{-\widetilde{c}\sqrt{1-u}}\triangleq
K_{\tt dot}(u)\,,$ (5)

where $u=\left\langle\bm{x},\widetilde{\bm{x}}\right\rangle$.

###  4.3 The minimum eigenvalue of NTK matrix under the high dimensional
setting

We are now ready to state the main result of a deep over-parameterized NTK
network. We first provide the lower bounds of the minimum eigenvalue of NTK
under the high dimensional setting.

Recall that the Neural Tangent Kernel (NTK) (Jacot et al., 2018) matrix of
neural network $f$ is defined in Eq. 3. When we focus on the infinite-width
setting ($m\to\infty$), the NTK matrix for a neural network Eq. 1 is derived
by the following regular chain rule.

######  Lemma 5 (Adapted from Lemma 3.1 in Nguyen et al. (2021)).

For any $l\in[3,L]$ and $s\in[2,L]$, denote

$\small\begin{split}&\bm{G}^{(1)}=\bm{XX}^{\top}\,,\\\
&\bm{G}^{(2)}=2\mathbb{E}_{\bm{w}\sim\mathcal{N}(\bm{0},\mathbb{I}_{d})}[\sigma_{1}(\bm{Xw})\sigma_{1}(\bm{Xw})^{\top}]\,,\\\
&\bm{G}^{(l)}=2\mathbb{E}_{\bm{w}\sim\mathcal{N}(\bm{0},\mathbb{I}_{N})}[\sigma_{l-1}(\sqrt{\bm{G}^{(l-1)}}\bm{w})\sigma_{l-1}(\sqrt{\bm{G}^{(l-1)}}\bm{w})^{\top}]\,,\\\
&\dot{\bm{G}}^{(s)}=2\mathbb{E}_{\bm{w}\sim\mathcal{N}(\bm{0},\mathbb{I}_{N})}[{\sigma}^{\prime}_{s-1}(\sqrt{\bm{G}^{(s-1)}}\bm{w}){\sigma}^{\prime}_{s-1}(\sqrt{\bm{G}^{(s-1)}}\bm{w})^{\top}]\,.\end{split}$

Then, the NTK for a $L$-layer neural network defined in Eq. 1 can be written
as

$\bm{K}_{\tt
NTK}=\bm{G}^{(L)}+\sum_{l=1}^{L-1}\bm{G}^{(l)}\circ\dot{\bm{G}}^{(l+1)}\circ\dot{\bm{G}}^{(l+2)}\circ\cdots\circ\dot{\bm{G}}^{(L)}\,,$

where $\circ$ represents the element-wise Hadamard product.

Based on the formulation of NTK, we are ready to present the estimation of the
minimum eigenvalue of NTK.

######  Theorem 2 (Minimum eigenvalue of NTK matrix).

For a DNN defined by Eq. 1, let $\bm{K}_{\tt NTK}$ be the limiting NTK
recursively defined in Lemma 5 and let $\lambda_{0}$ be the minimum eigenvalue
of $\bm{K}_{\tt NTK}$. Then, under 3 and 5, with probability at least
$1-2e^{-n}$, we obtain that:

$\lambda_{0}\geq\begin{cases}&2\mu_{1}^{2}\frac{n}{d}\bigg{(}\frac{3}{4}-\frac{c}{4}\sqrt{\frac{d}{n}}\bigg{)}^{2},\quad\text{if}\quad
n\geq d,\\\
&2\mu_{1}^{2}\frac{n}{d}\bigg{(}\sqrt{\frac{d}{n}}-\frac{c+6}{4}\bigg{)}^{2},\quad\text{if}\quad
n<d\,,\end{cases}$

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

Table 1: The trend of the bound with respect to $n$ under different range of $n$ values and a fixed $d$. Range of $n$ | Trend w.r.t. $n$ | Limit bound
---|---|---
$n\ll d$ | - | $2\mu_{1}^{2}$
$0\leq n\leq(\frac{4}{c+6})^{2}d$ | $\searrow$ | -
$(\frac{4}{c+6})^{2}\leq n\leq d$ | $\nearrow$ | -
$d\leq n\leq\frac{c^{2}}{9}d$ | $\searrow$ | -
$\frac{c^{2}}{9}d\leq n$ | $\nearrow$ | -
$n\gg d$ | - | $\frac{9}{8}\mu_{1}^{2}\frac{n}{d}$

###  4.4 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 6 and $d$ large enough,
under 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:

$\begin{split}\mathbb{E}&\left\|f_{\tt
nn}-f_{\rho}\right\|_{L_{\rho_{X}}^{2}}^{2}\lesssim\mathcal{O}\bigg{(}n^{-\theta}\log^{4}(\frac{2}{\delta})+\frac{\sigma_{\epsilon}^{2}}{d}\mathcal{N}_{\widetilde{\bm{X}}}\\\
+&\frac{\sigma_{\epsilon}^{2}\log^{2+4\varepsilon}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{)}\,,\end{split}$

where the $\lambda_{0}$ satisfies Theorem 2 and the effective dimension
$\mathcal{N}_{\widetilde{\bm{X}}}$ is defined as:

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

with
$\widetilde{\bm{X}}:=\beta\bm{X}\bm{X}^{\top}/d+\alpha\bm{1}\bm{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{\bm{X}}}$ under three typical eigenvalue decay of
$\bm{X}\bm{X}^{\\!\top}$ cases, and then discuss our generalization bound.
Note that when $n>d$, the sample matrix $\bm{X}\bm{X}^{\\!\top}$ has at most
$d$ eigenvalues, so we can directly have
$\mathcal{N}_{\widetilde{\bm{X}}}\leq\mathcal{O}(d)$. Accordingly, here we
present the results on the $n<d$ case.

  * •

Harmonic decay: $\lambda_{i}(\widetilde{\bm{X}})\propto n/i,\forall
i\in\left\\{1,2,\dots,r_{\star}\right\\}$ and
$\lambda_{i}(\widetilde{\bm{X}})=0,\forall
i\in\left\\{r_{\star}+1,\dots,n\right\\}$.

We have: $\mathcal{N}_{\bm{X}}=\mathcal{O}(n)$, then the term
$\frac{\sigma_{\epsilon}^{2}}{d}\mathcal{N}_{\widetilde{\bm{X}}}\leq\mathcal{O}(\frac{\sigma_{\epsilon}^{2}}{d}n)$.

  * •

Polynomial decay: $\lambda_{i}(\widetilde{\bm{X}})\propto ni^{-2a}$ with
$a>1/2,\forall i\in\left\\{1,2,\dots,r_{\star}\right\\}$ and
$\lambda_{i}(\widetilde{\bm{X}})=0,\forall
i\in\left\\{r_{\star}+1,\dots,n\right\\}$.

We have: $\mathcal{N}_{\bm{X}}=\mathcal{O}(n^{1/2a})$, then the term
$\frac{\sigma_{\epsilon}^{2}}{d}\mathcal{N}_{\widetilde{\bm{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{\bm{X}})\propto ne^{-ai}$ with
$a>0,\forall i\in\left\\{1,2,\dots,r_{\star}\right\\}$ and
$\lambda_{i}(\widetilde{\bm{X}})=0,\forall
i\in\left\\{r_{\star}+1,\dots,n\right\\}$.

We have:
$\mathcal{N}_{\widetilde{\bm{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}_{\widetilde{\bm{X}}}\leq\mathcal{O}(\frac{\sigma_{\epsilon}^{2}}{d}\frac{e^{ar_{\star}}}{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{c^{2}}{9}d$, in this case, we have
$\mathcal{N}_{\widetilde{\bm{X}}}\leq\mathcal{O}(d)$, according to Theorem 2
for $\lambda_{0}$, three terms $n^{-\theta}\log^{4}(\frac{2}{\delta})$,
$\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\varepsilon}d}{d^{4\theta-1}}$ also
converges to $0$ for a large enough $d$. Accordingly, for large enough $n$ and
$d$, we have

$\mathbb{E}\left\|f_{\tt
nn}-f_{\rho}\right\|_{L_{\rho_{X}}^{2}}^{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}_{\widetilde{\bm{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 n°
725594 - time-data).

## References

  * Allen-Zhu et al. (2019a) Z. Allen-Zhu, Y. Li, and Y. Liang.  Learning and generalization in overparameterized neural networks, going beyond two layers.  In _Advances in neural information processing systems (NeurIPS)_ , 2019a.
  * Allen-Zhu et al. (2019b) Z. Allen-Zhu, Y. Li, and Z. Song.  A convergence theory for deep learning via over-parameterization.  In _International Conference on Machine Learning (ICML)_ , 2019b.
  * Arora et al. (2019a) S. Arora, S. Du, W. Hu, Z. Li, and R. Wang.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In _International Conference on Machine Learning (ICML)_ , 2019a.
  * Arora et al. (2019b) S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang.  On exact computation with an infinitely wide neural net.  In _Advances in neural information processing systems (NeurIPS)_ , 2019b.
  * Bach (2017) F. Bach.  Breaking the curse of dimensionality with convex neural networks.  _Journal of Machine Learning Research_ , 2017.
  * Bartlett et al. (2020) P. L. Bartlett, P. M. Long, G. Lugosi, and A. Tsigler.  Benign overfitting in linear regression.  _Proceedings of the National Academy of Sciences_ , 2020.
  * Bietti and Mairal (2019) A. Bietti and J. Mairal.  On the inductive bias of neural tangent kernels.  In _Advances in neural information processing systems (NeurIPS)_ , 2019.
  * Bombari et al. (2022) S. Bombari, M. H. Amani, and M. Mondelli.  Memorization and optimization in deep neural networks with minimum over-parameterization.  In _Advances in neural information processing systems (NeurIPS)_ , 2022.
  * Brutzkus et al. (2017) A. Brutzkus, A. Globerson, E. Malach, and S. Shalev-Shwartz.  Sgd learns over-parameterized networks that provably generalize on linearly separable data.  In _International Conference on Learning Representations (ICLR)_ , 2017.
  * Bubeck et al. (2021) S. Bubeck, Y. Li, and D. M. Nagaraj.  A law of robustness for two-layers neural networks.  In _Conference on Learning Theory_ , 2021.
  * Cai et al. (2013) T. Cai, J. Fan, and T. Jiang.  Distributions of angles in random packing on spheres.  _Journal of Machine Learning Research_ , 2013.
  * Cao and Gu (2019) Y. Cao and Q. Gu.  Generalization bounds of stochastic gradient descent for wide and deep neural networks.  In _Advances in neural information processing systems (NeurIPS)_ , 2019.
  * Cao and Gu (2020) Y. Cao and Q. Gu.  Generalization error bounds of gradient descent for learning over-parameterized deep relu networks.  In _AAAI Conference on Artificial Intelligence_ , 2020.
  * Cao et al. (2022) Y. Cao, Z. Chen, M. Belkin, and Q. Gu.  Benign overfitting in two-layer convolutional neural networks, 2022.
  * Chatterji and Long (2021) N. S. Chatterji and P. M. Long.  Finite-sample analysis of interpolating linear classifiers in the overparameterized regime.  _Journal of Machine Learning Research_ , 2021.
  * Chatterji and Long (2022) N. S. Chatterji and P. M. Long.  Foolish crowds support benign overfitting.  _Journal of Machine Learning Research_ , 2022.
  * Chatterji et al. (2021) N. S. Chatterji, P. M. Long, and P. L. Bartlett.  The interplay between implicit bias and benign overfitting in two-layer linear networks, 2021.
  * Chen and Xu (2021) L. Chen and S. Xu.  Deep neural tangent kernel and laplace kernel have the same {rkhs}.  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Chen et al. (2020) Z. Chen, Y. Cao, D. Zou, and Q. Gu.  How much over-parameterization is sufficient to learn deep ReLU networks?  In _International Conference on Learning Representations (ICLR)_ , 2020.
  * Chizat et al. (2019) L. Chizat, E. Oyallon, and F. Bach.  On lazy training in differentiable programming.  In _Advances in neural information processing systems (NeurIPS)_ , 2019.
  * Cucker and Zhou (2007) F. Cucker and D. X. Zhou.  _Learning theory: an approximation theory viewpoint_.  Cambridge University Press, 2007.
  * Du et al. (2019a) S. Du, J. Lee, H. Li, L. Wang, and X. Zhai.  Gradient descent finds global minima of deep neural networks.  In _International Conference on Machine Learning (ICML)_ , 2019a.
  * Du et al. (2019b) S. S. Du, X. Zhai, B. Poczos, and A. Singh.  Gradient descent provably optimizes over-parameterized neural networks.  In _International Conference on Learning Representations (ICLR)_ , 2019b.
  * E et al. (2020) W. E, C. Ma, and L. Wu.  A comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics.  _Science China Mathematics_ , 2020.
  * Frei et al. (2022) S. Frei, N. S. Chatterji, and P. Bartlett.  Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data.  In _Conference on Learning Theory_ , 2022.
  * Geifman et al. (2020) A. Geifman, A. Yadav, Y. Kasten, M. Galun, D. Jacobs, and B. Ronen.  On the similarity between the laplace and neural tangent kernels.  In _Advances in neural information processing systems (NeurIPS)_ , 2020.
  * Ghosh et al. (2022) N. Ghosh, S. Mei, and B. Yu.  The three stages of learning dynamics in high-dimensional kernel methods.  In _International Conference on Learning Representations (ICLR)_ , 2022.
  * He et al. (2015) K. He, X. Zhang, S. Ren, and J. Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In _International Conference on Computer Vision (ICCV)_ , pages 1026–1034, 2015.
  * Hinton et al. (2015) G. Hinton, O. Vinyals, and J. Dean.  Distilling the knowledge in a neural network, 2015.
  * Huang et al. (2021) H. Huang, Y. Wang, S. M. Erfani, Q. Gu, J. Bailey, and X. Ma.  Exploring architectural ingredients of adversarially robust deep neural networks.  In _Advances in neural information processing systems (NeurIPS)_ , 2021.
  * Jacot et al. (2018) A. Jacot, F. Gabriel, and C. Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  In _Advances in neural information processing systems (NeurIPS)_ , 2018.
  * Ju et al. (2021) P. Ju, X. Lin, and N. Shroff.  On the generalization power of overfitted two-layer neural tangent kernel models.  In _International Conference on Machine Learning (ICML)_ , 2021.
  * Ju et al. (2022) P. Ju, X. Lin, and N. Shroff.  On the generalization power of the overfitted three-layer neural tangent kernel model.  In _Advances in neural information processing systems (NeurIPS)_ , 2022.
  * Koehler et al. (2021) F. Koehler, L. Zhou, D. J. Sutherland, and N. Srebro.  Uniform convergence of interpolators: Gaussian width, norm bounds and benign overfitting.  In _Advances in neural information processing systems (NeurIPS)_ , 2021.
  * Kuzborskij et al. (2021) I. Kuzborskij, C. Szepesvari, O. Rivasplata, A. Rannen-Triki, and R. Pascanu.  On the role of optimization in double descent: A least squares study.  In _Advances in neural information processing systems (NeurIPS)_ , 2021.
  * Lecun et al. (1998) Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 1998.
  * LeCun et al. (2012) Y. A. LeCun, L. Bottou, G. B. Orr, and K.-R. Müller.  Efficient backprop.  In _Neural networks: Tricks of the trade_ , pages 9–48. Springer, 2012.
  * Li et al. (2021) Z. Li, Z.-H. Zhou, and A. Gretton.  Towards an understanding of benign overfitting in neural networks, 2021\.
  * Liang and Rakhlin (2020) T. Liang and A. Rakhlin.  Just interpolate: Kernel “ridgeless” regression can generalize.  _The Annals of Statistics_ , 2020.
  * Liang et al. (2019) T. Liang, A. Rakhlin, and X. Zhai.  On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels, 2019.
  * Liu et al. (2021) F. Liu, Z. Liao, and J. Suykens.  Kernel regression in high dimensions: Refined analysis beyond double descent.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2021.
  * Mallinar et al. (2022) N. R. Mallinar, J. B. Simon, A. Abedsoltan, P. Pandit, M. Belkin, and P. Nakkiran.  Benign, tempered, or catastrophic: Toward a refined taxonomy of overfitting.  In _Advances in neural information processing systems (NeurIPS)_ , 2022.
  * Mei and Montanari (2022) S. Mei and A. Montanari.  The generalization error of random features regression: Precise asymptotics and the double descent curve.  _Communications on Pure and Applied Mathematics_ , 2022.
  * Montanari et al. (2019) A. Montanari, F. Ruan, Y. Sohn, and J. Yan.  The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime, 2019.
  * Nguyen et al. (2021) Q. Nguyen, M. Mondelli, and G. F. Montufar.  Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks.  In _International Conference on Machine Learning (ICML)_ , 2021.
  * Rudi and Rosasco (2017) A. Rudi and L. Rosasco.  Generalization properties of learning with random features.  In _Advances in neural information processing systems (NeurIPS)_ , 2017.
  * Schölkopf et al. (2002) B. Schölkopf, A. J. Smola, F. Bach, et al.  _Learning with kernels: support vector machines, regularization, optimization, and beyond_.  MIT press, 2002.
  * Tsigler and Bartlett (2020) A. Tsigler and P. L. Bartlett.  Benign overfitting in ridge regression, 2020.
  * Wainwright (2019) M. J. Wainwright.  _High-dimensional statistics: A non-asymptotic viewpoint_.  Cambridge University Press, 2019.
  * Wang et al. (2022) G. Wang, K. Donhauser, and F. Yang.  Tight bounds for minimum $ell\\_1$-norm interpolation of noisy data.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2022.
  * Wang et al. (2021) K. Wang, V. Muthukumar, and C. Thrampoulidis.  Benign overfitting in multiclass classification: All roads lead to interpolation.  In _Advances in neural information processing systems (NeurIPS)_ , 2021.
  * Wu et al. (2021) B. Wu, J. Chen, D. Cai, X. He, and Q. Gu.  Do wider neural networks really help adversarial robustness?  In _Advances in neural information processing systems (NeurIPS)_ , 2021.
  * Xu and Gu (2023) X. Xu and Y. Gu.  Benign overfitting of non-smooth neural networks beyond lazy training.  In _International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2023.
  * Zhu et al. (2022) Z. Zhu, F. Liu, G. Chrysos, and V. Cevher.  Generalization properties of NAS under activation and skip connection search.  In _Advances in neural information processing systems (NeurIPS)_ , 2022.
  * Zou et al. (2020) D. Zou, Y. Cao, D. Zhou, and Q. Gu.  Gradient descent optimizes over-parameterized deep relu networks.  _Machine learning_ , 2020.
  * Zou et al. (2021) D. Zou, J. Wu, V. Braverman, Q. Gu, and S. Kakade.  Benign overfitting of constant-stepsize sgd for linear regression.  In _Conference on Learning Theory_ , 2021.

## Appendix introduction

The Appendix is organized as follows:

  * •

In Appendix A, we state the symbols and notation used in this paper.

  * •

In Appendix B, we provide a example to verify the 2.

  * •

In Appendix C, we provide the proof for the lemmas in Section 3.4.

  * •

In Appendix D, we provide the theorem and its proof of the optimization result
for the classification problem.

  * •

In Appendix E, we provide the proof for the Theorem 2.

  * •

In Appendix F, we provide the proof for the Theorem 3.

##  Appendix A Symbols and Notation

In the paper, vectors are indicated with bold small letters and matrices with
bold capital letters. To facilitate the understanding of our work, we include
some core symbols and notation in Table 2.

Table 2: Core symbols and notations used in this project. Symbol | Dimension(s) | Definition
---|---|---
$\mathcal{N}(\mu,\sigma)$ | - |  Gaussian distribution of mean $\mu$ and variance $\sigma$
$\mathcal{B}(\bm{W},\cdot)$ | - |  Neighborhood of matrix $\bm{W}$
$\lambda(\bm{M})$ | - |  Eigenvalues of matrices $\bm{M}$
$\lambda_{\min}(\bm{M})$ | - |  Minimum eigenvalue of matrices $\bm{M}$
$\lambda_{0}$ | - | Minimum eigenvalue NTK matrix
$\phi(x)=\max(0,x)$ | - | ReLU activation function for scalar
$\phi(\bm{v})=(\phi(v_{1}),\dots,\phi(v_{m}))$ | - | ReLU activation function for vectors
$1\left\\{A\right\\}$ | - |  Indicator function for event $A$
$\mathrm{sgn}(\cdot)$ | - | Sign function
$\text{Lip}_{(\cdot)}$ | - | Lipschitz constant of a function
$n$ | - | Size of the dataset
$d$ | - | Input size of the network
$L$ | - | Depth of the network
$m$ | - | Width of intermediate layer
$\bm{x}_{i}$ | $\mathbb{R}^{d}$ |  The $i$-th data point
$y_{i}$ | $\\{\pm 1\\}$ |  The $i$-th clean label
$\widetilde{y}_{i}$ | $\\{\pm 1\\}$ |  The $i$-th training label
$P$ | - |  Clean data distribution that $(\bm{x}_{i},y_{i})\sim P$
$\widetilde{P}$ | - |  Training data distribution that $(\bm{x}_{i},\widetilde{y}_{i})\sim\widetilde{P}$
$P_{\text{clust}}$ | - | Cluster distribution for generate data
$\mathcal{C}$ | - | A subset of training data for clean labels
$\mathcal{C}^{\prime}$ | - | A subset of training data for noisy labels
$\alpha$ | - | Step size of SGD
$\eta$ | - | Noise rate
$\omega$ | - | Lazy training rate
$\lambda$ | - |  Strongly log-concave rate of distribution $P_{\text{clust}}$
$\ell$ | - | Logistic loss function
$\hat{L}$ | - | Empirical risks
$g_{i}^{(t)}$ | - |  Value of $g$ for input $\bm{x}_{i}$ at time $t$, where $g(z):=-\ell^{\prime}(z)$
$f_{i}^{(t)}$ | - |  Output of neural network for input $\bm{x}_{i}$ at time $t$
$f_{\rho}$ | - | Ground-truth function
$\bm{K}_{\tt NTK}$, $\bm{K}_{\tt Laplace}$, $\bm{K}_{\tt dot}$ | $\mathbb{R}^{n\times n}$ | Three different kernel matrices
$\mathcal{H}_{\tt NTK}$, $\mathcal{H}_{\tt Laplace}$, $\mathcal{H}_{\tt dot}$ | - | RKHS of the kernel
$\bm{W}_{1}$ | $\mathbb{R}^{m\times d}$ | Weight matrix for the input layer
$\bm{W}_{l}$ | $\mathbb{R}^{m\times m}$ |  Weight matrix for the $l$-th hidden layer
$\bm{W}_{L}$ | $\mathbb{R}^{1\times m}$ | Weight matrix for the output layer
$\bm{h}_{i,l}$ | $\mathbb{R}^{m}$ |  The $l$-th layer activation for input $\bm{x}_{i}$
$\bm{D}_{i,l}$ | $\mathbb{R}^{m\times m}$ |  Diagonal sign matrix of $l$-th layer input $\bm{x}_{i}$

##  Appendix B A example of 2

######  Proposition 1.

For two different data samples
$\bm{x}_{1},\bm{x}_{2}\in\mathbb{R}^{d}\sim\widetilde{P}:=\text{Unif}(\mathbb{S}^{d-1}(C_{\text{norm}}))$,
$y=\begin{cases}1&\text{ if }x_{i}>0,\forall i\in[d],\\\ -1&\text{ if
}x_{i}\leq 0,\forall i\in[d],\end{cases}$ the $2$-layer NTK kernel defined in
Eq. 3 with $L=2$ satisfy that:

$\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\big{[}K_{\tt
NTK}(\bm{x}_{1},\bm{x}_{2})|\widetilde{y}_{1}=\widetilde{y}_{2}\big{]}-\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\big{[}K_{\tt
NTK}(\bm{x}_{1},\bm{x}_{2})|\widetilde{y}_{1}\neq\widetilde{y}_{2}\big{]}\geq
C_{N}=\Theta(1)\,.$

###### Proof.

According to Bietti and Mairal [2019], we have for $2$-layer neural network:

$K_{\tt
NTK}(\bm{x}_{1},\bm{x}_{2})=\left\|\bm{x}_{1}\right\|_{2}\left\|\bm{x}_{2}\right\|_{2}\kappa\left(\frac{\left\langle\bm{x}_{1},\bm{x}_{2}\right\rangle}{\left\|\bm{x}_{1}\right\|_{2}\left\|\bm{x}_{2}\right\|_{2}}\right)\,,$

where $\kappa(u):=u\kappa_{0}(u)+\kappa_{1}(u)$ with
$\kappa_{0}(u):=\frac{1}{\pi}(\pi-\arccos(u))$ and
$\kappa_{1}(u):=\frac{1}{\pi}(u(\pi-\arccos(u))+\sqrt{1-u^{2}})$. Denote
$\cos(\theta):=\frac{\left\langle\bm{x}_{1},\bm{x}_{2}\right\rangle}{\left\|\bm{x}_{1}\right\|_{2}\left\|\bm{x}_{2}\right\|_{2}}$,
we have:

$\begin{split}K_{\tt
NTK}(\bm{x}_{1},\bm{x}_{2})&=\left\|\bm{x}_{1}\right\|_{2}\left\|\bm{x}_{2}\right\|_{2}\kappa\big{(}\frac{\left\langle\bm{x}_{1},\bm{x}_{2}\right\rangle}{\left\|\bm{x}_{1}\right\|_{1}\left\|\bm{x}_{2}\right\|_{2}}\big{)}\\\
&=\left\|\bm{x}_{1}\right\|_{2}\left\|\bm{x}_{2}\right\|_{2}\kappa\big{(}\cos(\theta)\big{)}\\\
&=\left\|\bm{x}_{1}\right\|_{2}\left\|\bm{x}_{2}\right\|_{2}\big{(}\cos(\theta)\kappa_{0}(\cos(\theta))+\kappa_{1}(\cos(\theta))\big{)}\\\
&=\left\|\bm{x}_{1}\right\|_{2}\left\|\bm{x}_{2}\right\|_{2}\big{(}\cos(\theta)\frac{1}{\pi}(\pi-\theta)+\frac{1}{\pi}(\cos(\theta)(\pi-\theta)+\left|\sin(\theta)\right|)\big{)}\\\
&=\left\|\bm{x}_{1}\right\|_{2}\left\|\bm{x}_{2}\right\|_{2}\big{(}\cos(\theta)\frac{2}{\pi}(\pi-\theta)+\frac{\left|\sin(\theta)\right|}{\pi}\big{)}\,.\end{split}$

According to $y=\begin{cases}1&\text{ if }x_{1}>0\\\ -1&\text{ if }x_{1}\leq
0\end{cases}$, we have if $\bm{x}_{3}=-\bm{x}_{2}$ then $y_{3}=-y_{2}$ and
$\cos(\theta^{\prime}):=\frac{\left\langle\bm{x}_{1},\bm{x}_{3}\right\rangle}{\left\|\bm{x}_{1}\right\|_{2}\left\|\bm{x}_{3}\right\|_{2}}=-\cos(\theta)$,
so $\theta^{\prime}=\pi-\theta$
and$\left|\sin(\theta^{\prime})\right|=\left|\sin(\theta)\right|$.

According to the symmetry of $\widetilde{P}$, we can compute that:

$\begin{split}&\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\big{[}\cos(\theta)\frac{2}{\pi}(\pi-\theta)+\frac{\left|\sin(\theta)\right|}{\pi}|\widetilde{y}_{1}=\widetilde{y}_{2}\big{]}\\\
=&\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{3},\widetilde{y}_{3})\sim\widetilde{P}}\big{[}\cos(\theta)\frac{2}{\pi}(\pi-\theta)+\frac{\left|\sin(\theta)\right|}{\pi}|\widetilde{y}_{1}=\widetilde{y}_{3}\big{]}\\\
=&\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{3},\widetilde{y}_{3})\sim\widetilde{P}}\big{[}-\cos(\theta^{\prime})\frac{2}{\pi}\theta^{\prime}+\frac{\left|\sin(\theta^{\prime})\right|}{\pi}|\widetilde{y}_{1}=\widetilde{y}_{3}\big{]}\\\
\end{split}$

According to the isotropy of $\widetilde{P}$, we have:

$\begin{split}&\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\big{[}K_{\tt
NTK}(\bm{x}_{1},\bm{x}_{2})|\widetilde{y}_{1}=\widetilde{y}_{2}\big{]}-\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\big{[}K_{\tt
NTK}(\bm{x}_{1},\bm{x}_{2})|\widetilde{y}_{1}\neq\widetilde{y}_{2}\big{]}\\\
=&\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1})\sim\widetilde{P}}\left\|\bm{x}_{1}\right\|_{2}\mathbb{E}_{(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\left\|\bm{x}_{2}\right\|_{2}\\\
\times&\bigg{(}\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\big{[}\cos(\theta)\frac{2}{\pi}(\pi-\theta)+\frac{\left|\sin(\theta)\right|}{\pi}|\widetilde{y}_{1}=\widetilde{y}_{2}\big{]}-\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\big{[}\cos(\theta)\frac{2}{\pi}(\pi-\theta)+\frac{\left|\sin(\theta)\right|}{\pi}|\widetilde{y}_{1}\neq\widetilde{y}_{2}\big{]}\bigg{)}\\\
=&\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1})\sim\widetilde{P}}\left\|\bm{x}_{1}\right\|_{2}\mathbb{E}_{(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\left\|\bm{x}_{2}\right\|_{2}\\\
\times&\bigg{(}\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\big{[}\cos(\theta)\frac{2}{\pi}(\pi-\theta)+\frac{\left|\sin(\theta)\right|}{\pi}|\widetilde{y}_{1}=\widetilde{y}_{2}\big{]}-\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{3},\widetilde{y}_{3})\sim\widetilde{P}}\big{[}-\cos(\theta^{\prime})\frac{2}{\pi}\theta^{\prime}+\frac{\left|\sin(\theta^{\prime})\right|}{\pi}|\widetilde{y}_{1}=\widetilde{y}_{3}\big{]}\bigg{)}\\\
=&2\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1})\sim\widetilde{P}}\left\|\bm{x}_{1}\right\|_{2}\mathbb{E}_{(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\left\|\bm{x}_{2}\right\|_{2}\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\big{[}\cos(\theta)|\widetilde{y}_{1}=\widetilde{y}_{2}\big{]}\\\
=&2C_{\text{norm}}^{2}\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\big{[}\cos(\theta)|\widetilde{y}_{1}=\widetilde{y}_{2}\big{]}\\\
\geq&2C_{\text{norm}}^{2}\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\left|\cos(\theta)\right|\,,\end{split}$

where the last inequality holds by the fact that the inner product of two data
points from the same class is always non-negative in our problem setting. We
know that the distribution of the angle between the vectors uniformly
distributed on a $d$-dimensional sphere is [Cai et al., 2013]:

$p(\theta)=\frac{\Gamma(\frac{d}{2})}{\Gamma(\frac{d-1}{2})\sqrt{\pi}}\sin^{d-2}\theta,\quad\theta\in[0,\pi]\,.$

Then we use substitution that $x=\cos\theta$, then we have the distribution of
the cosine of the angle between the vectors uniformly distributed on a
$d$-dimensional sphere is:

$p(x)=\frac{\Gamma(\frac{d}{2})}{\Gamma(\frac{d-1}{2})\sqrt{\pi}}(1-x^{2})^{(d-3)/2},\quad
x\in[-1,1]\,.$

Then we have:

$\begin{split}\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\left|\cos(\theta)\right|&=\int_{-1}^{1}\left|x\right|p(x)\mathrm{d}x\\\
&=2\frac{\Gamma(\frac{d}{2})}{\Gamma(\frac{d-1}{2})\sqrt{\pi}}\int_{0}^{1}x(1-x^{2})^{(d-3)/2}\mathrm{d}x\\\
&=\frac{2\Gamma(\frac{d}{2})}{\Gamma(\frac{d-1}{2})\sqrt{\pi}(d-1)}\\\
&=\frac{\Gamma(\frac{d}{2})}{\Gamma(\frac{d+1}{2})\sqrt{\pi}}\,.\end{split}$

Then, we have:

$\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\big{[}K_{\tt
NTK}(\bm{x}_{1},\bm{x}_{2})|\widetilde{y}_{1}=\widetilde{y}_{2}\big{]}-\mathbb{E}_{(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}}\big{[}K_{\tt
NTK}(\bm{x}_{1},\bm{x}_{2})|\widetilde{y}_{1}\neq\widetilde{y}_{2}\big{]}\geq\frac{2C_{\text{norm}}^{2}\Gamma(\frac{d}{2})}{\Gamma(\frac{d+1}{2})\sqrt{\pi}}=\Theta\left(\frac{1}{\sqrt{d}}\right)\,.$

When we fix the data dimension $d$, it is a constant order. ∎

##  Appendix C Proof for Lemmas in Section 3.4

###  C.1 Proof of Lemma 1

Let us restate Lemma 1 as below:

See 1

###### Proof.

According to the proof of Chatterji and Long [2021, Lemma 9] and Frei et al.
[2022, Lemma 3], we have:

$\begin{split}\mathbb{P}_{(\bm{x},y)\sim
P}(y\neq\mathrm{sgn}(f(\bm{x};\bm{W}^{(t)})))&=\mathbb{P}_{(\bm{x},y)\sim
P}(y\mathrm{sgn}(f(\bm{x};\bm{W}^{(t)}))<0)\\\
&\leq\eta+\mathbb{P}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}(\widetilde{y}f(\bm{x};\bm{W}^{(t)})<0)\,.\end{split}$
(6)

Denoting the Lipschitz constant of the neural network as
$\text{Lip}_{f(\bm{x};\bm{W}^{(t)})}$, since $P_{\text{clust}}$ is
$\lambda$-strongly log-concave, then according to Wainwright [2019, Theorem
3.16], for any $t>0$, we have:

$\mathbb{P}(|\widetilde{y}f(\bm{x};\bm{W}^{(t)})-\mathbb{E}[\widetilde{y}f(\bm{x};\bm{W}^{(t)})]|\geq
t)\leq
2\exp\bigg{(}-\frac{\lambda}{4}\bigg{(}\frac{t}{\text{Lip}_{f(\bm{x};\bm{W}^{(t)})}}\bigg{)}^{2}\bigg{)}\,.$

Choosing $t:=\mathbb{E}[\widetilde{y}f(\bm{x};\bm{W}^{(t)})]$, we have:

$\mathbb{P}(|\widetilde{y}f(\bm{x};\bm{W}^{(t)})-\mathbb{E}[\widetilde{y}f(\bm{x};\bm{W}^{(t)})]|\geq\mathbb{E}[\widetilde{y}f(\bm{x};\bm{W}^{(t)})])\leq
2\exp\bigg{(}-\frac{\lambda}{4}\bigg{(}\frac{\mathbb{E}[\widetilde{y}f(\bm{x};\bm{W}^{(t)})]}{\text{Lip}_{f(\bm{x};\bm{W}^{(t)})}}\bigg{)}^{2}\bigg{)}\,,$

which implies:

$\begin{split}\mathbb{P}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}(\widetilde{y}f(\bm{x};\bm{W}^{(t)})<0)&=\mathbb{P}(\widetilde{y}f(\bm{x};\bm{W}^{(t)})-\mathbb{E}[\widetilde{y}f(\bm{x};\bm{W}^{(t)})]<-\mathbb{E}[\widetilde{y}f(\bm{x};\bm{W}^{(t)})])\\\
&\leq\exp\bigg{(}-\frac{\lambda}{4}\bigg{(}\frac{\mathbb{E}[\widetilde{y}f(\bm{x};\bm{W}^{(t)})]}{\text{Lip}_{f(\bm{x};\bm{W}^{(t)})}}\bigg{)}^{2}\bigg{)}\,.\end{split}$

Incorporating it into Eq. 6, we conclude the proof.

∎

###  C.2 Proof of Lemma 2

Let us restate Lemma 2 as below:

See 2

###### Proof.

We can directly calculate that:

$\begin{split}&f(\bm{x};\bm{W})-f(\bm{x};\bm{W}^{\prime})-\left\langle\nabla
f(\bm{x};\bm{W}^{\prime}),\bm{W}-\bm{W}^{\prime}\right\rangle\\\
=&\bm{W}_{L}(\bm{h}_{i,L-1}-\bm{h}_{i,L-1}^{\prime})-\sum_{l=1}^{L-1}\bm{W}_{L}^{\prime}\bigg{(}\prod_{r=l+1}^{L-1}(\bm{D}_{i,r}^{\prime}\bm{W}_{r}^{\prime})\bigg{)}\bm{D}_{i,l}^{\prime}(\bm{W}_{l}-\bm{W}_{l}^{\prime})\bm{h}_{i,l-1}^{\prime}\,.\end{split}$

By Allen-Zhu et al. [2019b, Claim 11.2], when
$\bm{W},\bm{W}^{\prime}\in\mathcal{B}(\bm{W}^{(0)},\omega)$, there exist
diagonal matrices $\bm{D}_{i,l}^{\prime\prime}\in\mathbb{R}^{m\times m}$ with
entries in $\\{+1,-1\\}$ such that
$\left\|\bm{D}_{i,l}^{\prime\prime}\right\|_{0}\leq\mathcal{O}(m\omega^{2/3}L)$
and:

$\bm{h}_{i,L-1}-\bm{h}_{i,L-1}^{\prime}=\sum_{l=1}^{L-1}\bigg{(}\prod_{r=l+1}^{L-1}(\bm{D}_{i,r}+\bm{D}_{i,r}^{\prime\prime})\bm{W}_{r}\bigg{)}(\bm{D}_{i,l}+\bm{D}_{i,l}^{\prime\prime})(\bm{W}_{l}-\bm{W}_{l}^{\prime})\bm{h}_{i,l-1}^{\prime},\quad\forall
i\in[n]\,.$

Therefore, we have:

$\begin{split}&f(\bm{x};\bm{W})-f(\bm{x};\bm{W}^{\prime})-\left\langle\nabla
f(\bm{x};\bm{W}^{\prime}),\bm{W}-\bm{W}^{\prime}\right\rangle\\\
=&\sum_{l=1}^{L-1}\bm{W}_{L}\bigg{(}\prod_{r=l+1}^{L-1}(\bm{D}_{i,r}+\bm{D}_{i,r}^{\prime\prime})\bm{W}_{r}\bigg{)}(\bm{D}_{i,l}+\bm{D}_{i,l}^{\prime\prime})(\bm{W}_{l}-\bm{W}_{l}^{\prime})\bm{h}_{i,l-1}^{\prime}\\\
&-\sum_{l=1}^{L-1}\bm{W}_{L}^{\prime}\bigg{(}\prod_{r=l+1}^{L-1}(\bm{D}_{i,r}^{\prime}\bm{W}_{r}^{\prime})\bigg{)}\bm{D}_{i,l}^{\prime}(\bm{W}_{l}-\bm{W}_{l}^{\prime})\bm{h}_{i,l-1}^{\prime}\,.\end{split}$
(7)

According to Cao and Gu [2019, Lemma B.1], for
$\omega\leq\mathcal{O}(L^{-9/2}(\log m)^{-3})$, then with probability at least
$1-\mathcal{O}(nL^{2})\exp(-\Omega(m\omega^{2/3}L))$, we have:

$\frac{1}{2}\left\|\bm{x}_{i}\right\|_{2}\leq\left\|\bm{h}_{i,l-1}^{\prime}\right\|_{2}\leq\frac{3}{2}\left\|\bm{x}_{i}\right\|_{2}\leq\frac{3}{2}C_{\text{norm}}=\Theta(1),\forall
i\in[n],l\in[L-1]\,.$ (8)

According to Allen-Zhu et al. [2019b, Lemma 8.7], for
$s\in\big{[}\Omega\big{(}\frac{1}{\log
m}\big{)},\mathcal{O}\big{(}\frac{m}{L^{3}\log m}\big{)}\big{]}$,
$\omega=\mathcal{O}(L^{-3/2})$, with probability at least
$1-\exp(-\Omega(s\log m))$, we have:

$\left\|\bm{W}_{L}\bigg{(}\prod_{r=l+1}^{L-1}(\bm{D}_{i,r}+\bm{D}_{i,r}^{\prime\prime})\bm{W}_{r}\bigg{)}(\bm{D}_{i,l}+\bm{D}_{i,l}^{\prime\prime})-\bm{W}_{L}^{\prime}\bigg{(}\prod_{r=l+1}^{L-1}(\bm{D}_{i,r}^{\prime}\bm{W}_{r}^{\prime})\bigg{)}\bm{D}_{i,l}^{\prime}\right\|_{2}\leq\mathcal{O}(\sqrt{L^{3}s\log
m+\omega^{2}L^{3}m})\,.$

Then, taking $s:=\Theta(m\omega^{2})$, we have
$m\omega^{2}\leq\mathcal{O}\big{(}\frac{m}{L^{3}\log m}\big{)}$, that is
$\omega\leq\mathcal{O}(L^{-3/2}(\log m)^{-1/2})$, with probability at least
$1-\exp(-\Omega(m\omega^{2}\log m))$, we have:

$\left\|\bm{W}_{L}\bigg{(}\prod_{r=l+1}^{L-1}(\bm{D}_{i,r}+\bm{D}_{i,r}^{\prime\prime})\bm{W}_{r}\bigg{)}(\bm{D}_{i,l}+\bm{D}_{i,l}^{\prime\prime})-\bm{W}_{L}^{\prime}\bigg{(}\prod_{r=l+1}^{L-1}(\bm{D}_{i,r}^{\prime}\bm{W}_{r}^{\prime})\bigg{)}\bm{D}_{i,l}^{\prime}\right\|_{2}\leq\mathcal{O}(\sqrt{\omega^{2}L^{3}m\log
m})\,.$ (9)

Take Eq. 8 and Eq. 9 into Eq. 7, for $\omega\leq\mathcal{O}(L^{-9/2}(\log
m)^{-3})$, then 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:

$\begin{split}|f(\bm{x};\bm{W})-f(\bm{x};\bm{W}^{\prime})-\left\langle\nabla
f(\bm{x};\bm{W}^{\prime}),\bm{W}-\bm{W}^{\prime}\right\rangle|\leq\mathcal{O}(\sqrt{\omega^{2}L^{3}m\log
m})\sum_{l=1}^{L-1}\left\|\bm{W}_{l}-\bm{W}_{l}^{\prime}\right\|_{2}\,,\end{split}$

which concludes the proof. ∎

###  C.3 Proof of Lemma 3

Let us restate Lemma 3:

See 3

###### Proof.

By Lemma 2, for $\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:

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

Since $\widetilde{y}\in\left\\{\pm 1\right\\}$, we can calculate that:

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

where $(\bm{x}_{i},y_{i})$ is the random selected training sample at step
$t+1$, and $(a)$ uses Algorithm 1 and definition of $g_{i}^{(t)}$ that:

$\begin{split}\bm{W}^{(t+1)}-\bm{W}^{(t)}&=-\alpha\cdot\nabla\ell\big{(}y_{i}f(\bm{x}_{i};\bm{W}^{(t)})\big{)}\\\
&=-\alpha\ell^{\prime}\big{(}y_{i}f(\bm{x}_{i};\bm{W}^{(t)})\big{)}\cdot\nabla\big{(}y_{i}f(\bm{x}_{i};\bm{W}^{(t)})\big{)}\\\
&=\alpha g_{i}^{(t)}y_{i}\nabla f(\bm{x}_{i};\bm{W}^{(t)})\,.\end{split}$

Finally we conclude the proof. ∎

###  C.4 Proof of Lemma 4

Let us restate Lemma 4 as below:

See 4

###### Proof.

According to the Lemma 3, $\forall t\geq 0$, for
$\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:

$\begin{split}&\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}[\widetilde{y}(f(\bm{x};\bm{W}^{(t+1)})-f(\bm{x};\bm{W}^{(t)}))]\\\
\geq&\alpha
g_{i}^{(t)}\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}\left\langle\widetilde{y}\nabla
f(\bm{x};\bm{W}^{(t)}),y_{i}\nabla
f(\bm{x}_{i};\bm{W}^{(t)})\right\rangle-\mathcal{O}(\sqrt{\omega^{2}L^{3}m\log
m})\sum_{l=1}^{L-1}\left\|\bm{W}^{(t+1)}_{l}-\bm{W}^{(t)}_{l}\right\|_{2}\\\
\geq&\alpha
g_{i}^{(t)}\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}\left\langle\widetilde{y}\nabla
f(\bm{x};\bm{W}^{(t)}),y_{i}\nabla
f(\bm{x}_{i};\bm{W}^{(t)})\right\rangle-\mathcal{O}(\sqrt{\omega^{2}L^{5}\log
m})\\\ :=&\alpha
g_{i}^{(t)}\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}\left\langle\widetilde{y}\nabla
f(\bm{x};\bm{W}^{(t)}),y_{i}\nabla
f(\bm{x}_{i};\bm{W}^{(t)})\right\rangle-\varepsilon\,,\end{split}$ (10)

where the second inequality use the result of lazy-training that
$\bm{W}^{(t+1)}\in\mathcal{B}(\bm{W}^{(t)},\frac{1}{\sqrt{m}})$ and
$(\bm{x}_{i},y_{i})$ is the random selected training sample at step $t+1$.

By the definition of $\varepsilon$ we have:

$\varepsilon=\mathcal{O}(\sqrt{\omega^{2}L^{3}\log m})=\mathcal{O}(L^{-2}(\log
m)^{-5/2})\,.$

According to 2, we have:

$\begin{split}&\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}\left\langle\widetilde{y}\nabla
f(\bm{x};\bm{W}^{(t)}),y_{i}\nabla f(\bm{x}_{i};\bm{W}^{(t)})\right\rangle\\\
=&\mathbb{P}(i\in\mathcal{C})\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}\bigg{[}\left\langle\widetilde{y}\nabla
f(\bm{x};\bm{W}^{(t)}),y_{i}\nabla
f(\bm{x}_{i};\bm{W}^{(t)})\right\rangle|i\in\mathcal{C}\bigg{]}\\\
&+\mathbb{P}(i\in\mathcal{C}^{\prime})\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}\bigg{[}\left\langle\widetilde{y}\nabla
f(\bm{x};\bm{W}^{(t)}),y_{i}\nabla
f(\bm{x}_{i};\bm{W}^{(t)})\right\rangle|i\in\mathcal{C}^{\prime}\bigg{]}\\\
=&\mathbb{P}(i\in\mathcal{C})\mathbb{P}(\widetilde{y}=y_{i})\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}\bigg{[}\left\langle\nabla
f(\bm{x};\bm{W}^{(t)}),\nabla
f(\bm{x}_{i};\bm{W}^{(t)})\right\rangle|i\in\mathcal{C},\widetilde{y}=y_{i}\bigg{]}\\\
&-\mathbb{P}(i\in\mathcal{C})\mathbb{P}(\widetilde{y}\neq
y_{i})\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}\bigg{[}\left\langle\nabla
f(\bm{x};\bm{W}^{(t)}),\nabla
f(\bm{x}_{i};\bm{W}^{(t)})\right\rangle|i\in\mathcal{C},\widetilde{y}\neq
y_{i}\bigg{]}\\\
&+\mathbb{P}(i\in\mathcal{C}^{\prime})\mathbb{P}(\widetilde{y}=y_{i})\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}\bigg{[}\left\langle\nabla
f(\bm{x};\bm{W}^{(t)}),\nabla
f(\bm{x}_{i};\bm{W}^{(t)})\right\rangle|i\in\mathcal{C}^{\prime},\widetilde{y}=y_{i}\bigg{]}\\\
&-\mathbb{P}(i\in\mathcal{C}^{\prime})\mathbb{P}(\widetilde{y}\neq
y_{i})\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}\bigg{[}\left\langle\nabla
f(\bm{x};\bm{W}^{(t)}),\nabla
f(\bm{x}_{i};\bm{W}^{(t)})\right\rangle|i\in\mathcal{C}^{\prime},\widetilde{y}\neq
y_{i}\bigg{]}\\\ \geq&(1-\eta)\times\frac{1}{2}\times
C_{N}+[\eta\times\frac{1}{2}\times(-C_{N})]\\\
=&\frac{1-2\eta}{2}C_{N}\,,\end{split}$ (11)

where the $\mathcal{C}$ and $\mathcal{C}^{\prime}$ represent the subset of
training data for clean labels and noisy labels respectively. And
$(\bm{x}_{i},y_{i})$ is the random selected training sample at step $t+1$.

According to Cao and Gu [2019, Lemma B.1]. For
$\omega\leq\mathcal{O}(L^{-9/2}(\log m)^{-3})$, then with probability at least
$1-\mathcal{O}(nL^{2})\exp(-\Omega(m\omega^{2/3}L))$,
$\frac{1}{2}\leq\left|f(\bm{x}_{i};\bm{W}^{(t)}))\right|\leq\frac{3}{2}\left\|\bm{x}_{i}\right\|_{2}\leq\frac{3}{2}C_{\text{norm}},\forall
i\in[n]$.

That means:

$g_{i}^{(t)}=-\ell^{\prime}(y_{i}f(\bm{x}_{i};\bm{W}^{(t)}))=\frac{1}{1+\exp\big{(}y_{i}f(\bm{x}_{i};\bm{W}^{(t)}\big{)}}\geq\frac{1}{1+\exp(\frac{3}{2}C_{\text{norm}})}\,,\quad\forall
i\in[n]\,.$ (12)

Take Eq. 11 and Eq. 12 into Eq. 10, we have for
$\omega\leq\mathcal{O}(L^{-9/2}(\log m)^{-3})$, then with probability at least
$1-\exp(-\Omega(m\omega^{2}\log
m))-\mathcal{O}(nL^{2})\exp(-\Omega(m\omega^{2/3}L))$:

$\begin{split}&\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}[\widetilde{y}(f(\bm{x};\bm{W}^{(t+1)})-f(\bm{x};\bm{W}^{(t)}))]\\\
\geq&\alpha
g_{i}^{(t)}\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}\left\langle\widetilde{y}\nabla
f(\bm{x};\bm{W}^{(t)}),y_{i}\nabla
f(\bm{x}_{i};\bm{W}^{(t)})\right\rangle-\varepsilon\\\ \geq&\alpha
g_{i}^{(t)}\frac{1-2\eta}{2}C_{N}-\varepsilon\\\
\geq&\frac{\alpha}{1+\exp(\frac{3}{2}C_{\text{norm}})}\frac{1-2\eta}{2}C_{N}-\varepsilon\\\
=&\Theta\big{(}\alpha(1-2\eta)C_{N}\big{)}\,,\end{split}$

where the last inequality hold for
$\alpha\gtrsim\varepsilon=\mathcal{O}(L^{-2}(\log m)^{-5/2})$.

Since the symmetry of the random Gaussian initialization and zero-mean of
$\tilde{y}$, we have
$\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}[\widetilde{y}f(\bm{x};\bm{W}^{(0)})]=0$,
then we have:

$\begin{split}&\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}[\widetilde{y}f(\bm{x};\bm{W}^{(t)})]\\\
=&\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}[\widetilde{y}f(\bm{x};\bm{W}^{(0)})]+\sum_{s=0}^{n-1}\mathbb{E}_{(\bm{x},\widetilde{y})\sim\widetilde{P}}[\widetilde{y}(f(\bm{x};\bm{W}^{(s+1)})-f(\bm{x};\bm{W}^{(s)}))]\\\
\geq&0+\sum_{t=0}^{t-1}\Theta\big{(}\alpha(1-2\eta)C_{N}\big{)}\\\
=&\Theta\big{(}t\alpha(1-2\eta)C_{N}\big{)}\,.\end{split}$

∎

##  Appendix D Optimization result for the classification problem

Before presenting the optimization result, we first introduce the following
assumption:

######  Assumption 7.

For
$(\bm{x}_{1},\widetilde{y}_{1}),(\bm{x}_{2},\widetilde{y}_{2})\sim\widetilde{P}$,
if $y_{1}\neq y_{2}$, then $\left\|\bm{x}_{1}-\bm{x}_{2}\right\|_{2}\geq\phi$
for some $\phi>0$.

Then we present the theorem and its proof.

######  Theorem 4.

Given a DNN defined by Eq. 1 and trained by Algorithm 1 with the training data
satisfy 1 and 7, then for the step size
$\alpha=\mathcal{O}(n^{-3}L^{-9}m^{-1})$, the width
$m=\widetilde{\Omega}(\text{poly}(n,\phi^{-1},L))\Omega(1/\delta)$ and the
maximum number of iteration
$t=\mathcal{O}\big{(}\text{poly}(n,\phi^{-1},L)\big{)}\mathcal{O}(1/\delta)$
then with high probability, Algorithm 1 can find a point $\bm{W}^{(t)}$ such
that $\hat{L}(\bm{W}^{(t)})\leq\delta$.

###### Proof.

Recall our loss function is:

$\ell(z)=\log(1+\exp(-z))\,.$

And we can derive that:

$\ell^{\prime}(z)=-\frac{1}{1+e^{z}},\quad\ell^{\prime\prime}(z)=\frac{e^{z}}{(1+e^{z})^{2}}\,.$

It is easy to verify that:

$\ell^{\prime}(z)<0,\quad\lim_{z\to\infty}\ell(z)=0,\quad\lim_{z\to\infty}\ell^{\prime}(z)=0,\quad-\ell^{\prime}(z)\geq\min\left\\{\frac{1}{2},\frac{1}{2}\ell(z)\right\\},\quad\left|\ell^{\prime\prime}(z)\right|\leq\frac{1}{4}\,.$

Then according to Zou et al. [2020, Theorem 4.1], we conclude the proof. ∎

##  Appendix E Proof of Theorem 2

Before proving Theorem 2, we first introduce the following lemmas.

######  Lemma 6 (Minimum eigenvalue of sample covariance matrix. Adapted from
Lemma 1 in Kuzborskij et al. [2021]).

Let $\bm{X}=[\bm{x}_{1},\cdots,\bm{x}_{n}]^{\top}\in\mathbb{R}^{n\times d}$ be
a matrix with i.i.d. columns that satisfy Assumptions 5, and let
$\hat{\bm{\Sigma}}=\bm{X}^{\top}\bm{X}/n$, and
$\bm{\Sigma}=\mathbb{E}[\bm{x}\bm{x}^{\top}]$. Then, for every $s\geq 0$, with
probability at least $1-2e^{-n}$, we have:

$\lambda_{\min}(\hat{\bm{\Sigma}})\geq\lambda_{\min}(\bm{\Sigma})\bigg{(}\frac{3}{4}-\frac{c}{4}\sqrt{\frac{d}{n}}\bigg{)}^{2},\quad\text{if}\quad
n\geq d\,,$

and

$\lambda_{\min}(\hat{\bm{\Sigma}})\geq\lambda_{\min}(\bm{\Sigma})\bigg{(}\sqrt{\frac{d}{n}}-\frac{c+6}{4}\bigg{)}^{2},\quad\text{if}\quad
n<d\,,$

where we have an absolute constant $c=2^{3.5}\sqrt{\log(9)}$.

###### Proof.

According to 5, we have $\max_{i}\left\|\bm{x}_{i}\right\|_{\psi_{2}}$ is
bounded and $\left\|\bm{x}_{i}\right\|_{\bm{\Sigma}^{\dagger}}=\sqrt{d}$
almost sure for all $i\in[n]$. Without loss of generality, take
$\max_{i}\left\|\bm{x}_{i}\right\|_{\psi_{2}}\leq\frac{1}{2}$ into Kuzborskij
et al. [2021, Lemma 1], then choosing $s:=n$,which conclude the proof. ∎

Then we are ready to prove Theorem 2.

###### Proof of Theorem 2.

According to Lemma 5 and Zhu et al. [2022, Theorem 1], we have:

$\lambda_{0}\geq 2\mu_{1}^{2}\lambda_{\min}(\bm{XX}^{\top})\,,$

where $\mu_{1}$ is the $1$-st Hermite coefficient of the ReLU activation
function.

We know that, $\bm{XX}^{\top}$ and $\bm{X}^{\top}\bm{X}$ have the same non-
zero eigenvalues. Then according to Lemma 6 and 5, with probability at least
$1-2e^{-n}$, we have:

Case 1: $n\geq d$

$\begin{split}\lambda_{0}&\geq 2\mu_{1}^{2}\lambda_{\min}(\bm{XX}^{\top})\\\
&=2\mu_{1}^{2}n\lambda_{\min}(\hat{\bm{\Sigma}})\\\ &\geq
2\mu_{1}^{2}\frac{n}{d}\bigg{(}\frac{3}{4}-\frac{c}{4}\sqrt{\frac{d}{n}}\bigg{)}^{2},\quad\text{if}\quad
n\geq d\,.\end{split}$

Case 2: $n<d$

$\begin{split}\lambda_{0}&\geq 2\mu_{1}^{2}\lambda_{\min}(\bm{XX}^{\top})\\\
&=2\mu_{1}^{2}n\lambda_{\min}(\hat{\bm{\Sigma}})\\\ &\geq
2\mu_{1}^{2}\frac{n}{d}\bigg{(}\sqrt{\frac{d}{n}}-\frac{c+6}{4}\bigg{)}^{2},\quad\text{if}\quad
n<d\,.\end{split}$

where we have an absolute constant $c=2^{3.5}\sqrt{\log(9)}\approx 16.77$. ∎

##  Appendix F Supplementary proofs for Theorem 3

In this section, we present the proofs of Theorem 3 in Section 4.

###  F.1 A Precise Form of the Theorem 3

######  Theorem 5 (Precise form of Theorem 3).

Let $\alpha$, $\beta$ and $\gamma$ be three non-negative parameters depends on
the Laplace kernel, under 3, 4 and 5, let $0<\delta<\frac{1}{2}$,
$0<\theta\leq 1/2$, the ground-truth function $f_{\rho}$ lies in a RKHS by 6
and $d$ large enough, 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$, it holds with probability at least
$1-2\delta-\delta^{\prime}-d^{-2}-2e^{-n}$.

$\begin{split}\mathbb{E}\left\|f_{\tt
nn}-f_{\rho}\right\|_{L_{\rho_{X}}^{2}}^{2}\leq&n^{-\theta}\log^{4}(\frac{2}{\delta})+\frac{\sigma_{\epsilon}^{2}\beta}{d}\mathcal{N}_{\widetilde{\bm{X}}}^{\gamma}+\frac{\sigma_{\epsilon}^{2}\log^{2+4\varepsilon}d}{\gamma^{2}d^{4\theta-1}}+\mathcal{O}\bigg{(}\big{(}\epsilon+\frac{\sqrt{n}}{\lambda_{0}}\omega^{1/3}L^{5/2}\sqrt{m\log
m}+\frac{n^{3/2}}{\lambda_{0}^{3}\kappa}\big{)}^{2}\bigg{)}\,,\end{split}$

where:

$\lambda_{0}\geq\begin{cases}&2\mu_{1}^{2}\frac{n}{d}\bigg{(}\frac{3}{4}-\frac{c}{4}\sqrt{\frac{d}{n}}\bigg{)}^{2},\quad\text{if}\quad
n\geq d,\\\
&2\mu_{1}^{2}\frac{n}{d}\bigg{(}\sqrt{\frac{d}{n}}-\frac{c+6}{4}\bigg{)}^{2},\quad\text{if}\quad
n<d\,.\end{cases}$

where we have an absolute constant $c=2^{3.5}\sqrt{\log(9)}$,
$\widetilde{\bm{X}}:=\beta\bm{X}\bm{X}^{\top}/d+\alpha\bm{1}\bm{1}^{\top},\mathcal{N}_{\widetilde{\bm{X}}}^{\gamma}=\sum_{i=0}^{n-1}\frac{\lambda_{i}(\widetilde{\bm{X}})}{(\lambda_{i}(\widetilde{\bm{X}}+\gamma))^{2}},\left\|f\right\|_{L_{\rho_{X}}^{2}}^{2}=\int_{X}\left|f(\bm{x})\right|^{2}d\rho_{X}(\bm{x})$,
and $\mu_{1}$ is the $1$-st Hermite coefficient of the ReLU activation
function.

Remark: The three non-negative parameters $\alpha$, $\beta$, and $\gamma$
depend on the linearization of the Laplace kernel in the high dimension
setting, refer to [Liu et al., 2021] for details.

###  F.2 Propositions

We present several propositions that are needed for our Theorem 3 as below.

######  Proposition 2 (Convergence to the NTK at initialization. Adapted from
Theorem 3.1 in Arora et al. [2019b]).

Fix $\epsilon>0$ and $\delta\in(0,1)$. Suppose that
$m\geq\Omega(\frac{L^{6}}{\epsilon^{4}}\log(L/\delta))$. Then for any inputs
$\left\|\bm{x}_{1}\right\|\leq 1$, $\left\|\bm{x}_{2}\right\|\leq 1$, with
probability at least $1-\delta$ we have:

$\left|\left\langle\frac{\partial
f(\bm{x}_{1};\bm{W})}{\partial\bm{W}},\frac{\partial
f(\bm{x}_{2};\bm{W})}{\partial\bm{W}}\right\rangle-K_{\tt
NTK}(\bm{x}_{1},\bm{x}_{2})\right|=\mathcal{O}(\epsilon L)\,.$

######  Proposition 3 (Equivalence between trained neural network and kernel
regression).

Suppose that, $\omega\leq
poly(1/n,\lambda_{0},1/L,1/\log(m),\epsilon,1/\log(1/\delta),\kappa)$, $m\geq
poly(1/\omega)$, $\bm{x}_{te}$ satisfy 5 and
$\kappa=\mathcal{O}(\frac{\epsilon}{\log(n/\delta)})$. Then w.p. at least
$1-\delta$ over random initialization, we have:

$\left|f_{\tt nn}(\bm{x}_{te})-f_{\tt
NTK}(\bm{x}_{te})\right|\leq\mathcal{O}\big{(}\epsilon+\frac{\sqrt{n}}{\lambda_{0}}\omega^{1/3}L^{5/2}\sqrt{m\log
m}+\frac{n^{3/2}}{\lambda_{0}^{3}\kappa}\big{)}\,.$

######  Proposition 4 (Adapted from Theorem 2 in Liu et al. [2021]).

Let $\alpha$, $\beta$ and $\gamma$ be three non-negative parameters depends on
the laplace kernel, under 3, 4 and 5 let $0<\delta<\frac{1}{2}$,
$\theta=\frac{1}{2}-\frac{2}{8+m}$, ground-truth function $f_{\rho}$ lies in a
RKHS and $d$ large enough, then for any given $\varepsilon>0$, it holds with
probability at least $1-2\delta-d^{-2}$.

$\mathbb{E}\left\|f_{\tt NTK}-f_{\rho}\right\|_{L_{\rho_{X}}^{2}}^{2}\leq
n^{-2\theta
r}\log^{4}(\frac{2}{\delta})+\frac{\sigma_{\epsilon}^{2}\beta}{d}\mathcal{N}_{\widetilde{\bm{X}}}^{\gamma}+\frac{\sigma_{\epsilon}^{2}\log^{2+4\varepsilon}d}{\gamma^{2}d^{4\theta-1}}\,,$

where
$\widetilde{\bm{X}}:=\beta\bm{X}\bm{X}^{\top}/d+\alpha\bm{1}\bm{1}^{\top},\mathcal{N}_{\widetilde{\bm{X}}}^{\gamma}=\sum_{i=0}^{n-1}\frac{\lambda_{i}(\widetilde{\bm{X}})}{(\lambda_{i}(\widetilde{\bm{X}}+\gamma))^{2}},\left\|f\right\|_{L_{\rho_{X}}^{2}}^{2}=\int_{X}\left|f(\bm{x})\right|^{2}d\rho_{X}(\bm{x})$.

###  F.3 Proof of 3

Before proving 3, we need the following lemmas:

######  Lemma 7 (Gradient Perturbation $\to$ Kernel Perturbation).

For any two data point $\bm{x}_{1}$, $\bm{x}_{2}$ that satisfy 5 and the
neural network defined in Eq. 1, if $\left\|\frac{\partial
f(\bm{x}_{1};\bm{W}^{(t)})}{\partial\bm{W}}-\frac{\partial
f(\bm{x}_{1};\bm{W}^{(0)})}{\partial\bm{W}}\right\|\leq\epsilon$ and
$\left\|\frac{\partial
f(\bm{x}_{2};\bm{W}^{(t)})}{\partial\bm{W}}-\frac{\partial
f(\bm{x}_{2};\bm{W}^{(0)})}{\partial\bm{W}}\right\|\leq\epsilon$, we have

$\left|K_{\tt NTK}^{(t)}(\bm{x}_{1},\bm{x}_{2})-K_{\tt
NTK}^{(0)}(\bm{x}_{1},\bm{x}_{2})\right|=\mathcal{O}(\epsilon)\,,$

where the $\bm{K}_{\tt NTK}^{(t)}$ means the NTK kernel defined in Eq. 3 for
neural networks Eq. 1 at training time $t$.

###### Proof.

According to Lemma 5 in Zhu et al. [2022] and our network Eq. 1, we have:

$\frac{\partial f(\bm{x};\bm{W}^{(0)})}{\partial\bm{W}}=\Theta(1)\,.$

Then we use triangle inequality, which concludes the proof. ∎

######  Lemma 8 (Adapted from Lemma 8.2 in Allen-Zhu et al. [2019b]).

Suppose that $\omega=\mathcal{O}(\frac{1}{L^{9/2}(\log m)^{3}})$, then w.p. at
least $1-\exp(-\Omega(m\omega^{2/3}L))$ over random initialization, if
$\left\|\bm{W}_{l}-\bm{W}_{l}^{\prime}\right\|_{2}\leq\omega,\forall l\in[L]$,
we have
$\left\|\bm{W}_{l}\bm{h}_{i,l-1}-\bm{W}_{l}^{\prime}\bm{h}_{i,l-1}^{\prime}\right\|_{2}=\mathcal{O}(\omega
L^{5/2}\sqrt{\log m}),\forall l\in[L]$.

For notational simplicity, we define the notation $\bm{b}_{l}$:

$\bm{b}_{l}=\begin{cases}&1\quad\text{ if }l=L+1,\\\
&\bm{D}_{l}(\bm{W}_{l+1})^{\top}\bm{b}_{l+1}\quad\text{otherwise}.\end{cases}$

######  Lemma 9 (Adapted from Lemma 8.7 in Allen-Zhu et al. [2019b]).

Suppose that $\omega=\mathcal{O}(\frac{1}{L^{6}(\log m)^{3/2}})$, then with
probability at least $1-\exp(-\Omega(\omega^{2/3}mL\log m))$ over random
initialization, if
$\left\|\bm{W}_{l}-\bm{W}_{l}^{\prime}\right\|_{2}\leq\omega,\forall l\in[L]$,
we have
$\left\|\bm{b}_{l}-\bm{b}_{l}^{\prime}\right\|_{2}=\mathcal{O}(\omega^{1/3}L^{2}\sqrt{m\log
m}),\forall l\in[L]$.

###### Proof.

According to Allen-Zhu et al. [2019b, Lemma 8.7], choose $s:=m\omega^{2/3}L$,
which concludes the proof. ∎

######  Lemma 10.

Suppose that $\omega=\mathcal{O}(\frac{1}{L^{6}(\log m)^{3}})$, then with
probability at least $1-\exp(-\Omega(\omega^{2/3}mL))$ over random
initialization, if
$\left\|\bm{W}_{l}-\bm{W}_{l}^{\prime}\right\|_{2}\leq\omega,\forall l\in[L]$,
we have:

$\left\|\bm{b}_{l}^{\prime}(\bm{W}_{l-1}^{\prime}\bm{h}_{i,l-2}^{\prime})^{\top}-\bm{b}_{l}(\bm{W}_{l-1}\bm{h}_{i,l-2})^{\top}\right\|_{\mathrm{F}}=\mathcal{O}(\omega^{1/3}L^{5/2}\sqrt{m\log
m})\,,\quad\forall l\in[L]\,.$

###### Proof.

We use Lemmas 8 and 9 and the triangle inequality:

$\begin{split}&\left\|\bm{b}_{l}^{\prime}(\bm{W}_{l-1}^{\prime}\bm{h}_{i,l-2}^{\prime})^{\top}-\bm{b}_{l}(\bm{W}_{l-1}\bm{h}_{i,l-2})^{\top}\right\|_{\mathrm{F}}\\\
\leq&\left\|\bm{b}_{l}^{\prime}(\bm{W}_{l-1}^{\prime}\bm{h}_{i,l-2}^{\prime})^{\top}-\bm{b}_{l}(\bm{W}_{l-1}^{\prime}\bm{h}_{i,l-2}^{\prime})^{\top}\right\|_{\mathrm{F}}+\left\|\bm{b}_{l}(\bm{W}_{l-1}^{\prime}\bm{h}_{i,l-2}^{\prime})^{\top}-\bm{b}_{l}(\bm{W}_{l-1}\bm{h}_{i,l-2})^{\top}\right\|_{\mathrm{F}}\\\
\leq&\mathcal{O}(\omega^{1/3}L^{5/2}\sqrt{m\log m})\,.\end{split}$

∎

######  Lemma 11 (Adapted from Lemma F.9 in Arora et al. [2019b]).

Let
$\omega\leq\text{poly}(\epsilon,L,\lambda_{0},\frac{1}{\log(m)},\frac{1}{\log(1/\delta)},\kappa,\frac{1}{n}).$
If $m\geq\text{poly}(1/\omega)$, then with probability at least $1-\delta$
over random initialization, we have:

$\left\|\bm{W}_{l}^{(t)}-\bm{W}_{l}^{(0)}\right\|_{\mathrm{F}}\leq\omega\,,\quad\forall
t\geq 0,\forall l\in[L]\,,$

and

$f_{\tt nn}^{(t)}(\bm{x})-y\leq\exp(-\frac{1}{2}\kappa^{2}\lambda_{0}t)(f_{\tt
nn}^{(0)}(\bm{x})-y)\,.$

######  Lemma 12 (Kernel Perturbation During Training).

Suppose that, $\omega\leq
poly(1/n,\lambda_{0},1/L,1/\log(m),\epsilon,1/\log(1/\delta))$, $m\geq
poly(1/\omega)$ and $\kappa\leq 1$. Then with probability at least $1-\delta$
over random initialization, we have for all $t\leq 0$,
$\forall(\bm{x}_{1},\bm{x}_{2})$:

$\left|K_{\tt NTK}^{(t)}(\bm{x}_{1},\bm{x}_{2})-K_{\tt
NTK}^{(0)}(\bm{x}_{1},\bm{x}_{2})\right|\leq\mathcal{O}(\omega^{1/3}L^{5/2}\sqrt{m\log
m})\,.$

###### Proof.

By Lemma 11, we know that for $t\to\infty$,
$\left\|\bm{W}_{l}^{(t)}-\bm{W}_{l}^{(0)}\right\|_{\mathrm{F}}\leq\omega$, by
Lemma 10, we know that on the gradient, there is only a small perturbation,
then the perturbation of kernel value is small by Lemma 7. ∎

######  Lemma 13 (Kernel Perturbation $\to$ Output Perturbation. Adapted from
Lemma F.1 in Arora et al. [2019b]).

Fix $\epsilon_{\bm{H}}\leq\frac{1}{2}\lambda_{0}$. Suppose
$\left|f(\bm{x}_{i};\bm{W}^{(0)})\right|\leq\epsilon_{0},\forall i\in[n]$,
$\left|f(\bm{x}_{\text{te}};\bm{W}^{(0)})\right|\leq\epsilon_{0}$ and $f_{\tt
nn}^{(0)}(\bm{x})-y=\mathcal{O}(\sqrt{n})$. Furthermore, if $\forall t\geq 0$,
$\left\|\bm{K}_{\tt NTK}^{(t)}(\bm{x}_{\text{te}},\bm{X})-\bm{K}_{\tt
NTK}^{(0)}(\bm{x}_{\text{te}},\bm{X})\right\|_{2}\leq\epsilon_{te}$ and
$\left\|\bm{K}_{\tt NTK}^{(0)}-\bm{K}_{\tt
NTK}^{(t)}\right\|_{2}\leq\epsilon_{\bm{H}}$, then we have:

$\left|f_{\tt nn}(\bm{x}_{te})-f_{\tt
NTK}(\bm{x}_{te})\right|\leq\mathcal{O}\left(\epsilon_{0}+\frac{\sqrt{n}}{\lambda_{0}}\epsilon_{te}+\frac{\sqrt{n}}{\lambda_{0}^{2}}\log\left(\frac{n}{\epsilon_{\bm{H}}\lambda_{0}\kappa}\right)\epsilon_{\bm{H}}\right)\,.$

Then we are ready to prove 3.

###### Proof of 3.

According to Lemma 13, we have:

$\left|f_{\tt nn}(\bm{x}_{te})-f_{\tt
NTK}(\bm{x}_{te})\right|\leq\mathcal{O}\left(\epsilon+\frac{\sqrt{n}}{\lambda_{0}}\epsilon_{te}+\frac{\sqrt{n}}{\lambda_{0}^{2}}\log\left(\frac{n}{\epsilon_{\bm{H}}\lambda_{0}\kappa}\right)\epsilon_{\bm{H}}\right)\,.$

Note that the function $g(x):=x\log(\frac{n}{x\lambda_{0}\kappa})$ achieves
its maximum $g(x)_{\max}=\frac{n}{e\lambda_{0}\kappa}$.

Combine this and Lemma 12, we have:

$\left|f_{\tt nn}(\bm{x}_{te})-f_{\tt
NTK}(\bm{x}_{te})\right|\leq\mathcal{O}\left(\epsilon+\frac{\sqrt{n}}{\lambda_{0}}\omega^{1/3}L^{5/2}\sqrt{m\log
m}+\frac{n^{3/2}}{\lambda_{0}^{3}\kappa}\right)\,.$

∎

###  F.4 Proof of 4

Before proving 4, we first introduce the following lemmas:

######  Lemma 14 (Adapted from Theorem 1 in Chen and Xu [2021]).

Let $\mathcal{H}_{\tt Lap}$ and $\mathcal{H}_{\tt NTK}$ be the RKHS associated
with the Laplace kernel and the neural tangent kernel of a $L$-layer fully
connected ReLU network. Both kernels are restricted to the sphere
$\mathbb{S}^{d-1}$. Then the two spaces include the same set of functions:

$\mathcal{H}_{\tt Lap}=\mathcal{H}_{\tt NTK}\,.$

Then we are ready to prove 4.

###### Proof of 4.

According to Lemma 14, we have $\mathcal{H}_{\tt Lap}=\mathcal{H}_{\tt NTK}$,
that means, the estimators of Eq. 4 under two RKHS corresponding to the NTK
kernel and Laplace kernel are the same:

$f_{\tt NTK}(\bm{x}_{te})=f_{\tt Laplace}(\bm{x}_{te})\,,$ (13)

where $f_{\tt NTK}$, $f_{\tt Laplace}$ are the estimators of Eq. 4 in
$\mathcal{H}_{\tt NTK}$ and $\mathcal{H}_{\tt Laplace}$, respectively.

According to Eq. 5, when the Laplace kernel is restricted to the sphere
$\mathbb{S}^{d-1}$, it is a dot product kernel.

Combine Eq. 13 and Liu et al. [2021, Theorem 2], we get the result.

∎

###  F.5 Proof of Theorem 5

###### Proof.

Using triangle inequality, we have:

$\begin{split}\mathbb{E}\left\|f_{\tt
nn}-f_{\rho}\right\|_{L_{\rho_{X}}^{2}}^{2}\leq&\mathbb{E}\left\|f_{\tt
nn}-f_{\tt ntk}\right\|_{L_{\rho_{X}}^{2}}^{2}+\mathbb{E}\left\|f_{\tt
ntk}-f_{\rho}\right\|_{L_{\rho_{X}}^{2}}^{2}\\\
\leq&n^{-2\theta}\log^{4}(\frac{2}{\delta})+\frac{\sigma_{\epsilon}^{2}\beta}{d}\mathcal{N}_{\widetilde{\bm{X}}}^{\gamma}+\frac{\sigma_{\epsilon}^{2}\log^{2+4\varepsilon}d}{\gamma^{2}d^{4\theta-1}}\\\
+&\mathbb{E}\int_{X}\left|f_{\tt
ntk}(\bm{x})-f_{\rho}(\bm{x})\right|^{2}d\rho_{X}(\bm{x})\\\
\leq&n^{-2\theta}\log^{4}(\frac{2}{\delta})+\frac{\sigma_{\epsilon}^{2}\beta}{d}\mathcal{N}_{\widetilde{\bm{X}}}^{\gamma}+\frac{\sigma_{\epsilon}^{2}\log^{2+4\varepsilon}d}{\gamma^{2}d^{4\theta-1}}\\\
+&\mathcal{O}\bigg{(}\big{(}\epsilon+\frac{\sqrt{n}}{\lambda_{0}}\omega^{1/3}L^{5/2}\sqrt{m\log
m}+\frac{n^{3/2}}{\lambda_{0}^{3}\kappa}\big{)}^{2}\bigg{)}\,,\end{split}$
(14)

with probability at least $1-2\delta-\delta^{\prime}-d^{-2}$, where the first
inequality use 4 and second inequality use 3.

Then According to Theorem 2, we have:

$\lambda_{0}\geq\begin{cases}&2\mu_{1}^{2}\frac{n}{d}\bigg{(}\frac{3}{4}-\frac{c}{4}\sqrt{\frac{d}{n}}\bigg{)}^{2},\quad\text{if}\quad
n\geq d,\\\
&2\mu_{1}^{2}\frac{n}{d}\bigg{(}\sqrt{\frac{d}{n}}-\frac{c+6}{4}\bigg{)}^{2},\quad\text{if}\quad
n<d\,.\end{cases}$ (15)

with probability at least $1-2e^{-n}$.

Combine Eq. 14 and Eq. 15, we conclude the proof. ∎