# Generalization Ability of Wide Neural Networks on $\mathbb{R}$

Jianfa Lailabel=e1]<EMAIL_ADDRESS>[ Manyun Xulabel=e2]
<EMAIL_ADDRESS>[ Rui Chenlabel=e3]<EMAIL_ADDRESS>[ Qian Lin  Center for Statistical Science, Department of Industrial
Engineering Tsinghua University
Beijing Academy of Artificial Intelligence, Beijing, 100084, China,
<EMAIL_ADDRESS>
# Supplement to “Generalization Ability of Wide Neural Networks on
$\mathbb{R}$”

Jianfa Lailabel=e1]<EMAIL_ADDRESS>[ Manyun Xulabel=e2]
<EMAIL_ADDRESS>[ Rui Chenlabel=e3]<EMAIL_ADDRESS>[ Qian Lin  Center for Statistical Science, Department of Industrial
Engineering Tsinghua University
Beijing Academy of Artificial Intelligence, Beijing, 100084, China,
<EMAIL_ADDRESS>
###### Abstract

We perform a study on the generalization ability of the wide two-layer ReLU
neural network on $\mathbb{R}$. We first establish some spectral properties of
the neural tangent kernel (NTK): $a)$ $K_{d}$, the NTK defined on
$\mathbb{R}^{d}$, is positive definite; $b)$ $\lambda_{i}(K_{1})$, the $i$-th
largest eigenvalue of $K_{1}$, is proportional to $i^{-2}$. We then show that:
$i)$ when the width $m\rightarrow\infty$, the neural network kernel (NNK)
uniformly converges to the NTK; $ii)$ the minimax rate of regression over the
RKHS associated to $K_{1}$ is $n^{-2/3}$; $iii)$ if one adopts the early
stopping strategy in training a wide neural network, the resulting neural
network achieves the minimax rate; $iv)$ if one trains the neural network till
it overfits the data, the resulting neural network can not generalize well.
Finally, we provide an explanation to reconcile our theory and the widely
observed “benign overfitting phenomenon”.

62G08,

68T07,

46E22,

Early stopping,

linear Interpolation,

neural networks,

neural tangent kernel,

###### keywords:

[class=MSC2020]

###### keywords:

, 111Co-first author, and ††thanks: Corresponding author

##  1 Introduction

Deep neural networks have been successfully applied in various fields such as
image analysis, natural language processing, protein structure prediction,
etc.[40, 22, 35]. Since the number of parameters appeared in deep neural
networks is often ten times or hundred times larger than the sample size of
data, the successes of neural network methods have challenged the traditional
bias variances trade-off principle, one of the primary doctrines in the
classical statistical learning theories [61]. For example, many influential
experiments [9, 67, 8, 48, 7] suggested that if one trains a neural network
till it overfits the data, the resulting network can still generalize well.
This observation, often referred to as the “benign overfitting phenomenon” [4,
53, 26, 45], actually reshaped the landscape of the studies in neural
networks. For example, some researchers built giant neural networks in
practice which can easily achieve nearly zero training error and possess the
state-of-the-art performances [31, 50, 21]. Inspired by these experiments and
observations, researchers proposed various new theories to explain why
overfitted neural networks do generalize well on certain data [9, 43, 26, 47].

Several groups of statisticians tried to explain the generalization ability of
neural networks from statistical decision theory with various carefully
designed nonparametric regression frameworks. For example, assuming that the
regression function belongs to a carefully designed sub-class of the Hölder
continuous functions, [5] proved that there exists a neural network with
sigmoid activation function achieving the corresponding minimax rate; [54]
further established similar results for ReLU neural networks based on the
approximation theory from [66]; [59] then extended these results to regression
functions in Besov space and its variants. Most of these works [38, 49, 54, 5,
32, 59, 28, 60, 37] first proposed a carefully chosen candidate class of
functions/models; they then showed that the empirical risk minimizer (ERM) of
some loss function over the sets of neural networks can achieve the
corresponding minimax rate. However, besides the unrealistic assumptions on
the underlying models, these (static) ERMs approaches are hard to apply in
practice, because the corresponding optimization problems are highly non-
linear and non-convex. Therefore these static non-parametric explanations are
far from a satisfactory theory.

Since training a neural network is a highly non-convex optimization problem,
researchers put lots of effort to argue whether the gradient descent (GD) or
stochastic gradient descent (SGD) can find the global minimal points. At first
glance, it is unlikely that GD/SGD can find the global minimum on a highly
non-convex problem. Since the number of parameters of an implemented neural
network in practice is often ten times or hundred times larger than the sample
size, wide neural networks are of the top priority to investigate. After
assuming that the width of the neural network is large enough, [24] first
analyzed a wide two-layer neural network with random initialization and showed
that under some positiveness conditions on the Gram matrix, the GD can find
one of the global minimal points with high probabilities. [1] further proved
that GD/SGD can find the global minima of wide multi-layer neural networks in
polynomial time with high probabilities. These analyses focus on the so-called
“lazy training regime” where the width $m$ is sufficiently large such that the
weight parameters stay in a small neighborhood of their initialization during
the training process. Though these works showed that GD/SGD can find one of
the many global minimum points in the lazy training regime, they lack the
analyses of the generalization ability of the selected neural network.

In [33], Jacot et al. proposed a framework to understand the gradient flow
appeared in training wide neural networks through the gradient flow of a
kernel regression. To be more precise, they interpreted the gradient flow of a
loss function defined on the set of neural networks as a gradient flow
associated to a kernel regression problem where the kernel, often referred to
as the neural network kernel (NNK), is varying during the training process.
Moreover, by allowing the width $m\to\infty$, they further showed that the NNK
stays invariant during the training process. This time-independent kernel,
which they called the neural tangent kernel (NTK), plays an indispensable role
in the current research of neural networks. On the one hand, the studies of
neural networks in the “lazy training regime” can resort to the studies of
kernel regression with respect to the NTK. [3, 41] concluded that as the width
$m\to\infty$, the wide neural network trained by GD converges to the kernel
regression predictor with respect to the NTK. [29, 58] showed that with a
proper regularization parameter, the kernel ridge regression with respect to
the NTK can reach the minimax-optimal rate. On the other hand, whether the NTK
possesses some remarkable properties inspired a renaissance of the studies in
kernel regression from various aspects. For example, [51, 6, 15, 45] and [43]
considered the generalization performance of the kernel ridgeless regression
in low dimensional and high dimensional data respectively; [34, 13, 16, 56]
reinvestigated the generalization error of kernel ridge regression through the
eigenlearning framework.

Though the aforementioned inspirational works shed us some light on
understanding the superior performance of neural networks, they have not
formed a comprehensive explanation on why neural networks can generalize, even
in the “lazy training regime”. In this paper, we perform a study on the
generalization ability of the wide neural network on $\mathbb{R}$. We first
show in Section 3 that the NNK converges to the NTK uniformly as the width
$m\to\infty$, therefore the gradient flow of the wide two-layer ReLU neural
network uniformly converges to the gradient flow of the corresponding NTK
regression. With these uniform convergences, we then show in Section 4 that:
1\. the neural network produced by an early stopping strategy is minimax rate
optimal; 2. the overfitted neural network can not generalize well. It is clear
that the “benign overfitting phenomenon” violates the latter statement. To
reconcile this contradiction, we further proposed a hypothesis on the role
played by the signal strength in the “benign overfitting phenomenon” in
Section 5.

###  1.1 Contributions

In this paper, we focus on training a wide two-layer ReLU neural network in
the so-called “lazy training regime”. That is, the width $m$ of the neural
network is sufficiently large so that the parameters of the neural network
stay in a small neighbourhood of the initialization.

$\bullet$ Spectral properties of the NTK. We first show that the NTK is
positive definite on $\mathbb{R}^{d}$, filling a long-standing gap in the
literature. We then provide an optimal bound on the minimum eigenvalue of the
gram matrix $(K(\boldsymbol{x}_{i},\boldsymbol{x}_{j}))_{1\leq i,j\leq n}$ for
one-dimensional data. Finally, we determine the decay rate of the eigenvalues
of the NTK defined on $[0,1]$. To the best of our knowledge, our work is the
first result about the spectral properties of the NTK defined on a domain
other than sphere [11, 10, 17]. Though the eigenvalue decay rate of the NTK is
obtained only for a one-dimensional interval in this paper, it sheds light on
obtaining similar results for the NTK defined on $\mathbb{R}^{d}$. We believe
this problem would be of great interest to researchers.

$\bullet$ NNK converges to NTK uniformly. Though many works have claimed that
the dynamic of training the wide neural network can be well approximated by
that of the NTK regression, all of them only proved this claim pointwisely [3,
41]. In this paper, we first show that the NNK converges to the NTK uniformly
and that the dynamic of training the wide two-layer ReLU neural network
converges to that of the NTK regression uniformly. Thus, the generalization
performance of the wide neural networks can be approximated well by that of
the NTK regression.

$\bullet$ Generalization performance of neural networks on $\mathbb{R}$. With
the assumption that the regression function $f_{\star}\in\mathcal{H}_{1}$, the
RKHS associated to the NTK $K_{1}$ defined on $\mathbb{R}$, we prove that
training a wide neural network with a properly early stopping strategy can
produce a neural network achieving the minimax-optimal rate $n^{-2/3}$, i.e.,
the early stopped neural network can generalize. On the other hand, we can
show that if one trains a wide neural network till it overfits the equally-
distanced one-dimensional data, the resulting neural network is essentially a
linear interpolation and thus can not generalize. To the best of our
knowledge, it is the first time that we have a concrete understanding on what
an overfitted neural network looks like.

$\bullet$ Implicitly early stopping caused the “benign overfitting
phenomenon”.  Most reported experiments on the “benign overfitting phenomenon”
in neural networks might ignore a subtle difference between the 100% training
accuracy of labels and the (nearly) zero training loss. This difference
actually leads the training process being stopped earlier than the time needed
to overfit the data. We call the strategy stopping the training process with
near 100% training accuracy the implicit early stopping rule and find that the
occurrence of it depends on the signal strength of the data. We further
illustrate through several experiments how the signal strength affects the
implicitly early stopping rule and the generalization ability of the resulting
neural networks.

###  1.2 Related works

Whether the overfitted neural network can generalize is arguably one of the
most intriguing questions in explaining the superior performance of the neural
network methods in practice. Inspired by the experiments reported in [67],
lots of effort tried to explain that overfitted models/neural networks can
generalize well [9, 43]. For example, [9] exhibited the singular Nadaraya-
Watson estimator that interpolates the data can achieve the corresponding
minimax optimal rate; [43] illustrated that the Kernel “Ridgeless” Regression
can perfectly fit the high dimensional data and still generalize well. Though
these interpolations possess some generalization ability, we still need more
work to explain the “benign overfitting phenomenon” for neural networks. On
the other hand, there are few results claiming that kernel interpolations can
not generalize well [51, 15]. For example, [51] showed that for fixed
dimension, the Laplace kernel interpolation cannot have vanishing error for
noisy data as $n\to\infty$, even with bandwidth adaptive to the training set;
[15] further extended the result to the kernels whose associated reproducing
kernel Hilbert space (RKHS) is a Sobolev space $H^{s}$, where $d/2<s<3d/4$.
However, these results can not conclude the inconsistency of the neural
network interpolation.

Besides the aforementioned non-parametric static ERMs approaches, there are
few works studying the generalization ability of neural networks through the
dynamic of gradient descent or stochastic gradient descent [69, 68, 42]. Most
of them assumed that the data live in a sphere since the NTK is an inner
product kernel on the sphere and the spectral properties of the NTK are well
understood [11, 17, 27, 10]. For example, Hu et al. [29], one of the most
relevant works, considered the generalization performance of a two-layer ReLU
neural network defined on a sphere $\mathbb{S}^{d}$ trained by the gradient
descent with or without a $L^{2}$ penalized term. They claimed that: 1) the
overfitted neural network does not generalize well; 2) the properly early
stopped trained neural network can achieve the optimal rate. Unfortunately,
their first claim relies on an unproved result (the second statement of the
Corollary 3 in [52]) essentially; their second claim secretly utilizes another
unproved fact: the NNK convergence to the NTK uniformly, one of the major
technical contributions in our current work.

##### Notation

For every positive integer $n\in\mathbb{N}^{+}$, denote $\\{1,\dots,n\\}$ by
$[n]$. For a real number $x\in\mathbb{R}$, denote by $\lceil x\rceil$ the
smallest integer that is greater or equal to $x$ and by $\lfloor x\rfloor$ the
greatest integer that is greater or equal to $x$. For
$\boldsymbol{v}\in\mathbb{R}^{d}$, denote by $\boldsymbol{v}_{(j)}$ the $j$-th
component of $\boldsymbol{v}$ and denote the $\ell_{2}$ norm and supreme norm
of $\boldsymbol{v}$ by
$\|\boldsymbol{v}\|_{2}=(\sum_{j\in[d]}\boldsymbol{v}_{(j)}^{2})^{1/2}$ and
$\|\boldsymbol{v}\|_{\infty}=\max_{j\in[d]}|\boldsymbol{v}_{(j)}|$
respectively. For a matrix $\boldsymbol{A}\in\mathbb{R}^{m\times n}$, denote
by $a_{ij}$ the $(i,j)$-th component of $\boldsymbol{A}$ and denote the
operator norm and the Frobenius norm of $\boldsymbol{A}$ by
$\|\boldsymbol{A}\|_{2}=\sup_{\boldsymbol{v}\in\mathbb{R}^{n}}\|\boldsymbol{A}\boldsymbol{v}\|_{2}/\|\boldsymbol{v}\|_{2}$
and $\|\boldsymbol{A}\|_{\mathrm{F}}=(\sum_{i\in[m],j\in[n]}a_{ij}^{2})^{1/2}$
respectively. For a set $A$, denote by $|A|$ the number of elements $A$
contains. Let $\mu_{\mathcal{X}}$ be a positive measure on
$\mathcal{X}\subseteq\mathbb{R}^{d}$. We define the space
$L_{2}(\mathcal{X},\mu_{\mathcal{X}})=\\{f:\mathcal{X}\to\mathbb{R}:\int_{\mathcal{X}}|f(\boldsymbol{x})|^{2}\mathrm{d}\mu_{\mathcal{X}}<\infty\\}$.
We use the notation $a_{m}=o_{m}(1)$, meaning the sequence
$\\{a_{m}\\}_{m=1}^{\infty}$ converges to zero as $m\to\infty$.

Let $f_{\star}$ be a continuous function defined on a compact subset
$\mathcal{X}\subseteq[-B,B]^{d}\subseteq\mathbb{R}^{d}$ for some $B>0$ and
$\mu_{\mathcal{X}}$ be a distribution supported on $\mathcal{X}$. Suppose that
we have observed $n$ i.i.d. samples $\\{(\boldsymbol{x}_{i},y_{i}),i\in[n]\\}$
sampling form the model:

$y_{i}=f_{\star}(\boldsymbol{x}_{i})+\varepsilon_{i},\quad i=1,\dots,n,$ (1)

where $\boldsymbol{x}_{i}$’s are sampled from $\mu_{\mathcal{X}}$ and
$\varepsilon_{i}\sim\mathcal{N}(0,\sigma^{2})$ for some fixed $\sigma>0$. We
are interested in finding $\hat{f}_{n}$ based on these $n$ samples, which can
minimize the excess risk, i.e., the difference between
$\mathcal{L}(\hat{f}_{n})=\mathbf{E}_{(\boldsymbol{x},y)}\left[(\hat{f}_{n}(\boldsymbol{x})-y)^{2}\right]$
and
$\mathcal{L}(f_{\star})=\mathbf{E}_{(\boldsymbol{x},y)}\left[(f_{\star}(\boldsymbol{x})-y)^{2}\right]$.
One can easily verify the following formula about the excess risk:

$\mathcal{E}(\hat{f}_{n})=\mathcal{L}(\hat{f}_{n})-\mathcal{L}(f_{\star})=\int_{\mathcal{X}}(\hat{f}_{n}(\boldsymbol{x})-f_{\star}(\boldsymbol{x}))^{2}\mathrm{d}\mu_{\mathcal{X}}(\boldsymbol{x}).$
(2)

It is clear that the excess risk is an equivalent evaluation of the
generalization performance of $\hat{f}_{n}$. When $\boldsymbol{x}_{i}$ is
assumed to be fixed, the excess risk can be taken as measuring the
$L^{2}(\mathcal{X},\nu)$ distance between $\hat{f}$ and $f_{\star}$, where
$\nu$ is the Lebesgue measure.

##  2 Neural tangent kernel and its spectral properties

Given the data
$\\{(\boldsymbol{x}_{i},y_{i})\in\mathbb{R}^{d}\times\mathbb{R},i\in[n]\\}$,
we are interested in analyzing the gradient flow of the empirical loss
function

$\hat{\mathcal{L}}_{n}(f_{\boldsymbol{\theta}}^{m})=\frac{1}{2n}\sum_{i=1}^{n}\left(y_{i}-f_{\boldsymbol{\theta}}^{m}(\boldsymbol{x}_{i})\right)^{2}=\frac{1}{2n}\|\boldsymbol{y}-f_{\boldsymbol{\theta}}^{m}(\boldsymbol{X})\|_{2}^{2},$

where $f^{m}_{\boldsymbol{\theta}}$ is a two-layer ReLU neural network with
width $m$. More precisely,

$f_{\boldsymbol{\theta}}^{m}(\boldsymbol{x})=\sqrt{\frac{2}{m}}\sum_{r=1}^{m}\left(a_{r}\sigma\left(\langle\boldsymbol{w}_{r},\boldsymbol{x}\rangle+b_{r}\right)\right)+b,$

where $a_{r}(0),\boldsymbol{w}_{r,j}(0),b_{r}(0),b\sim\mathcal{N}(0,1)$ for
$r\in[m]$ and $j\in[d]$,
$\boldsymbol{\theta}=\operatorname{vec}(\\{a_{r},\boldsymbol{w}_{r},b_{r},b,r\in[m]\\})$
and the activation function $\sigma(z)=\max\\{z,0\\}$.

Since training neural networks is a highly non-linear problem, Jacot et al.
[33] proposed to utilize a time-invariant kernel, the neural tangent kernel
(NTK), to investigate the training process of neural networks when the width
$m\rightarrow\infty$. Let us denote the neural tangent kernel of the two-layer
neural network by $K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})$. Thanks to
the results in [20] and [33], we can get the following explicit expression:

$K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})=\frac{2}{\pi}\left(\pi-\psi(\boldsymbol{x},\boldsymbol{x}^{\prime})\right)(\langle\boldsymbol{x},\boldsymbol{x}^{\prime}\rangle+1)+\frac{1}{\pi}\sqrt{\|\boldsymbol{x}-\boldsymbol{x}^{\prime}\|_{2}^{2}+\|\boldsymbol{x}\|_{2}^{2}\|\boldsymbol{x}^{\prime}\|_{2}^{2}-\langle\boldsymbol{x},\boldsymbol{x}^{\prime}\rangle^{2}}+1$
(3)

where $\psi(\boldsymbol{x},\boldsymbol{x}^{\prime})=\arccos$
$\frac{\langle\boldsymbol{x},\boldsymbol{x}^{\prime}\rangle+1}{\sqrt{(\|\boldsymbol{x}\|_{2}^{2}+1)(\|\boldsymbol{x}^{\prime}\|_{2}^{2}+1)}}$
.

We first show that $K_{d}$ is a positive definite kernel. To avoid the
potential confusion between positive definiteness and positive semi-
definiteness of a kernel function, we explicitly adopt the following
definition of positive definiteness.

######  Definition 1.

A kernel function $K$ is positive definite (semi-definite) over domain
$\mathcal{X}\subseteq\mathbb{R}^{d}$ if for any positive integer $n$ and any
$n$ different points
$\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{n}\in\mathcal{X}$, the smallest
eigenvalue $\lambda_{\min}$ of the matrix
$K(\boldsymbol{X},\boldsymbol{X})=(K(\boldsymbol{x}_{i},\boldsymbol{x}_{j}))_{1\leq
i,j\leq n}$ is positive (non-negative).

Positive definiteness of the neural tangent kernel is widely assumed in
literature [24, 23, 2]. To the best of our knowledge, the positive
definiteness of the NTK has been only proved when it is defined on sphere
$\mathbb{S}^{d-1}\subseteq\mathbb{R}^{d}$ [33]. The following proposition
states that the NTK is positive definite on a compact set $\mathbb{R}^{d}$.

######  Proposition 2.1 (Positive definiteness of $K_{d}$).

For any $d\geq 1$, the neural tangent kernel
$K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})$ is positive definite on any
compact subset $\mathcal{X}\subseteq\mathbb{R}^{d}$.

Once we know the positive definiteness of $K_{d}$ on $\mathbb{R}^{d}$, the
spectral properties of $K_{d}$ are of our further interest. For example, the
minimum eigenvalue of $K_{d}(\boldsymbol{X},\boldsymbol{X})$ is of particular
interest in analyzing the dynamic of training a wide neural network, because
most analyses are implicitly or explicitly assumed that it is positive
(e.g.,[29, 58]). Furthermore, the celebrated Mercer’s decomposition theorem
asserts (loosely speaking) that there exist non-negative numbers
$\lambda_{1}\geq\lambda_{2}\geq\cdots$ and functions
$\phi_{1},\phi_{2},\cdots\in L_{2}(\mathcal{X},\mu_{\mathcal{X}})$ such that
$\left<\phi_{i},\phi_{j}\right>_{L_{2}(\mathcal{X},\mu_{\mathcal{X}})}=\delta_{ij}$
and

$\displaystyle
K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})=\sum_{j=1}^{\infty}\lambda_{j}\phi_{j}(\boldsymbol{x})\phi_{j}(\boldsymbol{x}^{\prime}),$
(4)

where the series on RHS converges in $L_{2}(\mathcal{X},\mu_{\mathcal{X}})$
(please see Appendix A for more rigorous statements). The numbers
$\\{\lambda_{j},j\geq 1\\}$ and the functions $\\{\phi_{j},j\geq 1\\}$ are
often referred to as the eigenvalues and the eigenfunctions associated to the
kernel $K_{d}$ respectively. The decay rate of $\\{\lambda_{j},j\geq 1\\}$ is
of great interest in determining the metric entropy of the RKHS associated to
the kernel $K_{d}$.

In this paper, we will focus on the performance of two-layer neural networks
on one-dimensional data, i.e., we are more interested in $d=1$. The following
theorem summarizes the spectral properties of $K_{1}$ needed in this paper
whose proof is deferred to Appendix B.

######  Theorem 2.2 (Spectral properties of $K_{1}$).

The following properties hold for $K_{1}$.

$i)$ Let $\boldsymbol{X}=\\{x_{1},...,x_{n}\\}\subseteq[0,\pi]$ and
$d_{\min}=\min_{i\neq j}|x_{i}-x_{j}|$. The minimum eigenvalue
$\lambda_{\min}$ of $K_{1}(\boldsymbol{X},\boldsymbol{X})$ satisfies that

$c_{1}d_{\min}\leq\lambda_{\min}\leq C_{1}d_{\min}$ (5)

for some absolute constants $c_{1}$ and $C_{1}$.

$ii)$ Let $\\{\lambda_{j},j\geq 1\\}$ be the eigenvalues associated to the NTK
$K_{1}$ defined on $[0,1]$. Then we have

$\frac{c_{2}}{j^{2}}\leq\lambda_{j}\leq\frac{C_{2}}{j^{2}},~{}~{}j\geq 1$ (6)

for some absolute constants $c_{2}$ and $C_{2}$.

Theorem 2.2 $i)$ shows that the minimum eigenvalue of the gram matrix
$K_{1}(\boldsymbol{X},\boldsymbol{X})$ depends on the minimum distance between
samples. In particular, for the equally distanced one-dimensional data with
$x_{i}=\frac{i-1}{n-1}$ for $i\in[n]$, the minimum distance
$d_{\min}=\frac{1}{n-1}$ and the minimum eigenvalue is $\propto\frac{1}{n}$.
Theorem 2.2 $ii)$ states that the eigenvalue decay rate (EDR) is 2, an
important quantity in performing the kernel regression. This theorem not only
provides us with necessary results for this paper, but it also provides us
some guidance to make reasonable conjectures for the spectral properties of
$K_{d,L}$, the NTK associated to the $L$-layer neural network defined on
$\mathbb{R}^{d}$.

##  3 Neural network kernel converges to neural tangent kernel uniformly

When the loss function $\hat{\mathcal{L}}_{n}$ is viewed as a function defined
on the parameter space $\Theta$, it induces a gradient flow in $\Theta$ given
by

$\displaystyle\dot{\boldsymbol{\theta}}(t)$
$\displaystyle=\frac{\mathrm{d}}{\mathrm{d}t}\boldsymbol{\theta}(t)=-\nabla_{\boldsymbol{\theta}}\hat{\mathcal{L}}_{n}(f_{\boldsymbol{\theta}(t)}^{m})=-\frac{1}{n}\nabla_{\boldsymbol{\theta}}f_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{X})^{\mathsf{T}}(f_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{X})-\boldsymbol{y})$
(7)

where we emphasize that
$\nabla_{\boldsymbol{\theta}}f_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{X})$
is an $n\times((d+2)m+1)$ matrix. When the loss function
$\hat{\mathcal{L}}_{n}$ is viewed as a function defined on $\mathcal{F}^{m}$,
the space consisting of all two-layer neural networks
$f_{\boldsymbol{\theta}}^{m}$, it induces a gradient flow in $\mathcal{F}^{m}$
given by

$\displaystyle\dot{f}_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x})$
$\displaystyle=\frac{\mathrm{d}}{\mathrm{d}t}f_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x})=\nabla_{\boldsymbol{\theta}}f_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x})\dot{\boldsymbol{\theta}}(t)=-\frac{1}{n}K_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x},\boldsymbol{X})(f_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{X})-\boldsymbol{y}),$
(8)

where we emphasize that
$K_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x},\boldsymbol{X})=\nabla_{\boldsymbol{\theta}}f_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x})\nabla_{\boldsymbol{\theta}}f_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{X})^{\mathsf{T}}$
is a $1\times n$ vector. We further introduce a time-varying kernel function

$\displaystyle
K_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})=\langle\nabla_{\boldsymbol{\theta}}f_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x}),\nabla_{\boldsymbol{\theta}}f_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x}^{\prime})\rangle.$

To avoid potential confusion with the NTK, we refer to this time-varying
kernel $K_{\boldsymbol{\theta}(t)}^{m}$ as the NNK.

It is clear from the gradient flow equations (7) and (8) that the training
process of neural networks is determined by the random initialization of
$\boldsymbol{\theta}(0)$. To avoid unnecessary digression, we adopt a special
initialization widely used in literature so that
$f_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x})=0$ [30, 19]. More precisely,
for a two-layer neural network with width $2m$, we assume that
$a_{r}(0)=-a_{r+m}(0),\boldsymbol{w}_{r,(j)}(0)=\boldsymbol{w}_{r+m,(j)}(0),b_{r}(0)=b_{r+m}(0)\sim\mathcal{N}(0,1)$
for $r\in[m]$, $j\in[d]$ and $b=0$.

Since it is hard to find an explicit solution of the highly non-linear
equations (7) and (8) , researchers looked for approximated solutions
characterizing the asymptotic behavior of the exact solution of these
equations (see e.g.,[46, 36, 57, 25]). When the width $m\rightarrow\infty$,
Jacot et al. [33] observed that the NTK is the limit of NNK. The time-
independent kernel NTK offered us a simplified version of the equations (7)
and (8):

$\displaystyle\dot{f}^{\mathtt{NTK}}_{t}(\boldsymbol{x})=\frac{\mathrm{d}}{\mathrm{d}t}f^{\mathtt{NTK}}_{t}(\boldsymbol{x})=-\frac{1}{n}K_{d}(\boldsymbol{x},\boldsymbol{X})(f^{\mathtt{NTK}}_{t}(\boldsymbol{X})-\boldsymbol{y})$
(9)

where
$K_{d}(\boldsymbol{x},\boldsymbol{X})=(K_{d}(\boldsymbol{x},\boldsymbol{x}_{1}),\dots,K_{d}(\boldsymbol{x},\boldsymbol{x}_{n}))\in\mathbb{R}^{1\times
n}$. This equation is defined on the space $\mathcal{H}_{d}$, the RKHS
associated to the kernel $K_{d}$. The equation (9) is called the gradient flow
associated to the kernel regression with respect to the kernel $K_{d}$.
Similar to the special initialization of the neural network function, we
assume that the initial function $f^{\mathtt{NTK}}_{0}(\boldsymbol{x})=0$.

Though it is hard to solve the equations (7) and (8), the equation (9) can be
solved explicitly:

$f_{t}^{\mathtt{NTK}}(\boldsymbol{x})=K_{d}(\boldsymbol{x},\boldsymbol{X})K_{d}(\boldsymbol{X},\boldsymbol{X})^{-1}(\boldsymbol{I}-e^{-\frac{1}{n}K_{d}(\boldsymbol{X},\boldsymbol{X})t})\boldsymbol{y},$
(10)

which we refer to as NTK regression function at time $t$ in this paper.
Researchers proved that for any given $\delta\in(0,1)$, for every
$\boldsymbol{x}\in\mathcal{X}$, the neural network
$f_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x})$ can be well approximated by
the NTK regression function $f_{t}^{\mathtt{NTK}}(\boldsymbol{x})$ when $m$ is
sufficiently large, i.e., one has the pointwise convergence (see e.g., [41,
3]):

$\sup_{t\geq
0}|f^{m}_{\boldsymbol{\theta}(t)}(\boldsymbol{x})-f_{t}^{\mathtt{NTK}}(\boldsymbol{x})|=o_{m}(1)$
(11)

holds with probability at least $1-\delta$.

One of our main technical contributions is that the above convergence is
uniform with respect to all $t\geq 0$ and all $\boldsymbol{x}\in\mathcal{X}$.
Thus, the excess risk $\mathcal{E}(f_{\boldsymbol{\theta}(t)}^{m})$ of the
wide two-layer ReLU neural network $f_{\boldsymbol{\theta}(t)}^{m}$ could be
well approximated by the excess risk $\mathcal{E}(f_{t}^{\mathtt{NTK}})$ of
the NTK regression function $f_{t}^{\mathtt{NTK}}$.

######  Theorem 3.1.

Given the training data $\\{(\boldsymbol{x}_{i},y_{i}),i\in[n]\\}$, for any
$\epsilon>0$, when the width $m$ of the two-layer ReLU neural network is
sufficiently large, we have

$\sup_{t\geq
0}|\mathcal{E}(f_{\boldsymbol{\theta}(t)}^{m})-\mathcal{E}(f_{t}^{\mathtt{NTK}})|\leq\epsilon$

holds with probability at least $1-o_{m}(1)$ where the randomness comes from
the initialization of the parameters.

###### Proof.

According to the formula of $f_{t}^{\mathtt{NTK}}(\boldsymbol{x})$ in (9), we
have

$\displaystyle|f_{t}^{\mathtt{NTK}}(\boldsymbol{x})|\leq$
$\displaystyle\|K_{d}(\boldsymbol{x},\boldsymbol{X})^{\mathsf{T}}\|_{2}\|K_{d}(\boldsymbol{X},\boldsymbol{X})^{-1}\|_{2}\|\boldsymbol{I}-e^{-\frac{1}{n}K_{d}(\boldsymbol{X},\boldsymbol{X})t}\|_{2}\|\boldsymbol{y}\|_{2}$
$\displaystyle\leq$ $\displaystyle
C\sqrt{n}(\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X})))^{-1}\|\boldsymbol{y}\|_{2}$

for some constant $C$ depending only on $B$. Since $f_{\star}$ is continuous
on $\mathcal{X}$, it is bounded. Thus, we know that

$\Delta_{\star}:=\sup_{t\geq
0}\sup_{\boldsymbol{x}\in\mathcal{X}}|f_{t}^{\mathtt{NTK}}(\boldsymbol{x})-f_{\star}(\boldsymbol{x})|\leq
C\max\\{1,\sqrt{n}(\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X})))^{-1}\|\boldsymbol{y}\|_{2}\\}$

for some constant $C$ depending only on $B$ and $f_{\star}$. Let
$\Delta(t,\boldsymbol{x})=f_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x})-f_{t}^{\mathtt{NTK}}(\boldsymbol{x})$.
For any $\epsilon>0$, we know that for sufficiently large $m$,

$\displaystyle\left|\mathcal{E}(f_{\boldsymbol{\theta}(t)}^{m})-\mathcal{E}(f_{t}^{\mathtt{NTK}})\right|=$
$\displaystyle\left|\int_{\mathcal{X}}\Delta(t,\boldsymbol{x})^{2}\mathrm{d}\mu_{\mathcal{X}}(\boldsymbol{x})+\int_{\mathcal{X}}\Delta(t,\boldsymbol{x})(f_{t}^{\mathtt{NTK}}(\boldsymbol{x})-f_{\star}(\boldsymbol{x}))\mathrm{d}\mu_{\mathcal{X}}(\boldsymbol{x})\right|$
$\displaystyle\leq$
$\displaystyle\int_{\mathcal{X}}|\Delta(t,\boldsymbol{x})\left(\Delta(t,\boldsymbol{x})+(f_{t}^{\mathtt{NTK}}(\boldsymbol{x})-f_{\star}(\boldsymbol{x}))\right|\mathrm{d}\mu_{\mathcal{X}}(\boldsymbol{x})\leq\epsilon$

where the last line follows from Proposition 3.2 that for sufficiently large
$m$, we have

$\sup_{t\geq
0}\sup_{\boldsymbol{x}\in\mathcal{X}}|\Delta(t,\boldsymbol{x})|\leq\min\left\\{\Delta_{\star},\epsilon/\Delta_{\star}\right\\}$

with probability at least $1-o_{m}(1)$. ∎

Though many works tried to study the generalization performance of the neural
network through that of the NTK regression [33, 63, 3, 2, 29, 58, 47], to the
best of our knowledge, most of them took the convergence
$\mathcal{E}(f_{\boldsymbol{\theta}(t)}^{m})\xrightarrow{m\rightarrow\infty}\mathcal{E}(f_{t}^{\mathtt{NTK}})$
for granted. Theorem 3.1 fills this long-standing gap in the literature and
ensures the validity of focusing on the generalization properties of NTK
regression. The following two propositions are not only of technical interests
but also serve as a cornerstone in the future studies of the “lazy training
regime”.

######  Proposition 3.2.

Given the training data $\\{(\boldsymbol{x}_{i},y_{i}),i\in[n]\\}$, for any
$\epsilon>0$, if the width $m$ of the two-layer ReLU neural network is
sufficiently large, then

$\sup_{t\geq
0}\sup_{\boldsymbol{x}\in\mathcal{X}}|f^{m}_{\boldsymbol{\theta}(t)}(\boldsymbol{x})-f_{t}^{\mathtt{NTK}}(\boldsymbol{x})|\leq\epsilon$

holds with probability at least $1-o_{m}(1)$ where the randomness comes from
the initialization of the parameters.

######  Proposition 3.3.

Given the training data $\\{(\boldsymbol{x}_{i},y_{i}),i\in[n]\\}$, for any
$\epsilon>0$, if the width $m$ of the two-layer ReLU neural network is
sufficiently large, then

$\sup_{t\geq
0}\sup_{\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathcal{X}}|K_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})|\leq\epsilon$

holds with probability at least $1-o_{m}(1)$ where the randomness comes from
the initialization of the parameters.

The proofs of Proposition 3.2 and Proposition 3.3 are deferred to
Supplementary Material. The existing results only showed that as $m\to\infty$,
the time-varying NNK $K_{\boldsymbol{\theta}(t)}^{m}$ and the neural network
$f_{\boldsymbol{\theta}(t)}^{m}$ converge pointwise to the time-invariant NTK
$K_{d}$ and the NTK regression function $f_{t}^{\mathtt{NTK}}$ ([33, 24, 41,
3]). The Proposition 3.2 and 3.3 proved a much stronger uniformly convergence
statement.

##  4 The generalization performance of wide neural networks on $\mathbb{R}$

In order to get a meaningful discussion about the generalization performance
of a neural network, we have to specify a class of functions to which
$f_{\star}$ belongs. In this paper, we make the following assumption:

######  Assumption 1.

The regression function $f_{\star}\in\mathcal{H}_{1}$ and
$\|f_{\star}\|_{\mathcal{H}_{1}}\leq R$ for some constant $R$, where
$\mathcal{H}_{1}$ is the RKHS associated to the kernel $K_{1}$.

Proposition 3.2 and Theorem 3.1 shows that $f^{m}_{\boldsymbol{\theta}(t)}$
uniformly converges to $f^{\mathtt{NTK}}_{t}$ and
$\mathcal{E}(f_{\boldsymbol{\theta}(t)}^{m})$ is well approximate by
$\mathcal{E}(f_{t}^{\mathtt{NTK}})$, thus we can focus on studying the
generalization ability of the NTK regression function $f^{\mathtt{NTK}}_{t}$.
It would be easier to stick with the usual assumptions appeared in the kernel
regression literature (see e.g., [18, 65, 52, 12, 44]). This is exactly the
Assumption 1.

###  4.1 Wide neural networks with early stopping achieve the minimax rate

Early stopping, an implicit regularization strategy, is widely applied in
training various models such as kernel ridgeless regression, neural networks,
etc. Lots of solid research has provided theoretical guarantees for early
stopping (see e.g. [65, 52, 12, 44]), where the optimal stopping time is
depending on the decay rate of eigenvalue associated to the kernel. Note that
Theorem 2.2 gives us the eigenvalue decay rate of $K_{1}$ and Theorem 3.1
guarantees the excess risk of the NTK regression function
$f_{t}^{\mathtt{NTK}}$ is an accurate alternative of the excess risk of the
neural network $f^{m}_{\boldsymbol{\theta}(t)}$, thus we have the following
Theorem 4.1.

######  Theorem 4.1.

Suppose Assumption 1 holds and we observed $n$ i.i.d. samples
$\\{(\boldsymbol{x}_{i},y_{i}),i\in[n]\\}$ from the model (1). For any given
$\delta\in(0,1)$, if one trains a two-layer neural network with width $m$ that
is sufficiently large and stops the gradient flow at time $t_{\star}\propto
n^{2/3}$, then for sufficiently large $n$, there exists a constant $C$
independent of $\delta$ and $n$, such that

$\mathcal{E}(f_{\boldsymbol{\theta}(t_{\star})}^{m})\leq
Cn^{-\frac{2}{3}}\log^{2}\frac{6}{\delta}$ (12)

holds with probability at least $(1-\delta)(1-o_{m}(1))$ where the randomness
comes from the joint distribution of the random samples and the random
initialization of parameters in the neural network
$f_{\boldsymbol{\theta}(0)}^{m}$.

Researchers have established ([12]) the following minimax rate of regression
over the RKHS $\mathcal{H}_{1}$ associated to $K_{1}$:

$\inf_{\hat{f}_{n}}\sup_{f_{\star}\in\mathcal{H}_{1},\|f_{\star}\|_{\mathcal{H}_{1}}\leq
R}\mathbf{E}\mathcal{E}(\hat{f}_{n})=\Omega(n^{-\frac{2}{3}}).$ (13)

Thus, we have proved that training a wide neural two-layer neural network with
the early stopping strategy achieves the optimal rate.

The proof of Theorem 4.1 can be found in Supplementary Material. Theorem 4.1
rigorously shows the fully trained wide two-layer ReLU neural network with
early stopping is minimax rate optimal.

###  4.2 Overfitted Neural Networks generalize poorly

In this subsection, we are more interested in the generalization performance
of $f_{\boldsymbol{\theta}(t)}^{m}(x)$ for sufficiently large $t$ such that
$f_{\boldsymbol{\theta}(t)}^{m}(x)$ can (nearly) fit the given data.

To be more concrete, suppose that we observed $n$ equally-distanced one-
dimensional data $\\{(x_{i},y_{i})\mid x_{i}=\frac{i-1}{n-1},i\in[n]\\}$. The
following theorem shows that $f_{\boldsymbol{\theta}(t)}^{m}(x)$ almost
linearly interpolates these data points when $t$ is sufficiently large,
therefore it can not generalize well. We remind that a linear interpolation of
the equally-distanced data is given by:

$\displaystyle
f_{\mathtt{LI}}(x)=y_{i}+\frac{y_{i+1}-y_{i}}{x_{i+1}-x_{i}}(x-x_{i}),\mbox{
when }x\in[x_{i},x_{i+1}].$ (14)

######  Theorem 4.2 (Overfitted networks generalize poorly).

Suppose that we have observed $n$ data $\\{(x_{i},y_{i}),i\in[n]\\}$ from the
model (1) where $x_{i}=\frac{i-1}{n-1}$, $i\in[n]$. When the width $m$ is
sufficiently large, the following statements hold.

$i)$ There exist some absolute constants $C_{1}$, $C_{2}$ and $C_{3}$ such
that for any $t>C_{1}n^{2}\log n$, we have

$\displaystyle\sup_{x\in[0,1]}|f_{\boldsymbol{\theta}(t)}^{m}(x)-f_{\mathtt{LI}}(x)|\leq
C_{3}\sqrt{\log n}/(n-1)^{2}$ (15)

holds with probability at least $1-\frac{C_{2}}{n}$.

$ii)$ There exist some positive constant $C_{4}$ depending only on $\sigma$
and absolute constant $C_{5}$ such that for any $t>C_{1}n^{2}\log n$, we have
$\mathcal{E}(f_{\boldsymbol{\theta}(t)}^{m})\geq C_{4}$ holds with probability
at least $1-\frac{C_{5}}{n}$.

Theorem 4.2 $i)$ shows that the overfitted neural network is nearly a linear
interpolation (e.g., shown in Figure 1(a)). To the best of our knowledge, this
is the first result explicitly showing how the overfitted neural network
interpolates the data. We have to emphasize that not every kernel
interpolation (kernel ridgeless regression) is nearly linear interpolation.
For example, it is clear that the radial basis function(RBF) kernel
interpolation interpolates the data nonlinearly, shown in Figure 1(b). Figure
1(c) shows that the maximum gap between the overfitted neural network and
linear interpolation is exactly $O(\frac{1}{n^{2}})$, which is in line with
the Theorem 4.2 $i)$.

Theorem 4.2 $ii)$ shows that the generalization error of overfitted neural
networks has a constant lower bound at least for the equally-distanced data.
It strongly suggests that overfitted neural networks can not generalize well,
which contradicts the “benign overfitting phenomenon”. So in the next section,
we will provide an explanation to reconcile our theoretical result and the
“benign overfitting phenomenon”.

(a)

(b)

(c)

Figure 1: (a): The interpolation ways of two-layer neural networks with
different widths; (b): The interpolation ways of linear interpolation,
$f^{\mathtt{NTK}}_{\infty}(x)$ and RBF kernel regression with the bandwidth
$\gamma=1$; (c): The maximum gap between $f^{\mathtt{NTK}}_{\infty}$ and
linear interpolation. The input of the training data is the equally-distanced
one-dimensional data $\\{x_{i}=\frac{i-1}{n-1},i\in[n]\\}$ with randomly
selected labels. The sample size $n=100,200,\dots,1000$

##  5 Why overfitted neural networks generalize

In Section 3, we have shown that the generalization ability of a wide neural
network depends on when the training process is stopped. $i)$ If the training
process stops at a properly chosen time, the generalization ability of the
resulting neural network can achieve the minimax rate; $ii)$ If the training
process stops when the loss is near zero (or overfitting the data), the
resulting neural network can not generalize well. The latter statement,
however, contradicts to the reported “benign overfitting phenomenon” where
overfitted neural networks do generalize well in certain situations. To
resolve this annoying contradiction, we scrutinize the reported observations
again and propose a hypothesis on the role of signal strength played in these
observations. We believe this explanation reconciles the conflict between our
theory and the widely observed “benign overfitting phenomenon”.

###  5.1 Three stopping rules

We first emphasize that a subtle difference between the classification problem
and the regression problem might be ignored in the reported experiments. To be
more concrete, we have three choices of stopping times in the classification
problem: $i)$ the stopping time $t_{\text{opt}}$ where the training process
stopped at the time suggested by our theory ; $ii)$ the stopping time
$t_{\text{loss}}$ where the training process stopped till the value of the
loss function nears zero; $iii)$ the stopping time $t_{\text{label}}$ where
the training process stopped till the label error rate nears zero. Most of the
reported experiments in “benign overfitting phenomenon” utilize the stopping
time $t_{\text{label}}$ and claim that the resulting neural network can
overfit the data and generalize well [67].

Our theoretical results suggested that the neural network at the stopping time
$t_{\text{opt}}$ has the best generalization ability and the neural network at
the stopping time $t_{\text{loss}}$ can not generalize. Thus, there might be a
significant difference between the stopping time $t_{\text{label}}$ and
$t_{\text{loss}}$. This difference can clearly be seen from a toy example
consisting of 4 data points
$\\{(0,0),(\frac{1}{3},1),(\frac{2}{3},0),(1,1)\\}$. We fit the data with a
two-layer neural network with width $m=1000$ with respect to the square loss (
regression ) and cross-entropy loss (classification ) separately. The results
are reported in figure 2. It is clear that for both loss functions, the
stopping time $t_{\text{label}}$ is much earlier than $t_{\text{loss}}$. The
fact that the stopping time $t_{\text{label}}$ may be far earlier than
$t_{\text{loss}}$ partially explained why the training stopped at time
$t_{\text{label}}$ produces a neural network with some generalization ability;
if the stopping time $t_{\text{label}}$ is close to $t_{\text{opt}}$, then the
training process stopped at time $t_{\text{label}}$ produces a neural network
with the optimal generalization ability.

Figure 2: Overfitting vs. 100 % label accuracy for regression and
classification problems: The upper figures are from the regression setup and
the lower ones are from the classification setup. The left figures present the
loss and the accuracy of 4 training data points. The right figures show the
function in the epoch with 100 % label accuracy and in the interpolation
regime.

###  5.2 The effects of signal strength

We have seen the three different stopping rules and the subtle difference
between $t_{\mathrm{label}}$ and $t_{\mathrm{loss}}$. What makes the stopping
time $t_{\mathrm{label}}$ far from $t_{\mathrm{loss}}$ or not? We hypothesize
that: $i)$ if the signal strength is strong, then $t_{\mathrm{label}}$ nears
$t_{\mathrm{opt}}$; $ii)$ if the signal strength is weak, then
$t_{\mathrm{label}}$ nears $t_{\mathrm{loss}}$. We justified this hypothesis
through various experiments.

$\bullet$ Synthetic Data: Suppose that $\boldsymbol{x}_{i},1\leq i\leq 100$
are i.i.d. sampled from $\operatorname{unif}((0,1)^{3})$ and

$y_{i}=f_{\star}(x_{i})=\lfloor 2\boldsymbol{x}_{i,(1)}\rfloor+2\lfloor
2\boldsymbol{x}_{i,(2)}\rfloor+4\lfloor
2\boldsymbol{x}_{i,(3)}\rfloor\in\\{0,1,\cdots,7\\},1\leq i\leq 100.$

For a given $p\in[0,1]$, we corrupt every label $y_{i}$ of the data with
probability $p$ by a uniform random integer from $\\{0,1,\cdots,7\\}$.

For corrupted data with $p\in\\{0,0.3,0.6\\}$, we train a two-layer neural
network (width $m=10000$) with the squared loss and collect the testing
accuracy and loss based on 1000 testing data points. The results are reported
in Figure 3(a). We also execute the same experiment with the cross-entropy
loss and report the results in Figure 3(b).

(a) the results of the squared loss

(b) the results of the cross-entropy loss

Figure 3: Synthetic Data: the gap between $t_{\mathrm{label}}$ and
$t_{\mathrm{opt}}$ is increasing when the label corruption ratio $p$ is
increasing. When $p=0$, the gap between $t_{\mathrm{label}}$ and
$t_{\mathrm{opt}}$ and the gap between the corresponding testing accuracies
are extremely small, i.e., we observed the “benign overfitting”.

$\bullet$ Real Data: Inspired by the numerical studies (the classification
setup) in [67], we perform the experiments on CIFAR-10 with AlexNet. Again, we
corrupt the data with $p=\\{0,0.3,0.6\\}$ and apply the SGD to training Alex
with the momentum parameter of 0.9, the initial learning rate of 0.01 and the
decay factor 0.95 per training epoch. The results are reported in Figure 4.

(b) Generalization gap with different label corruption ratios $p$

Figure 4: AlexNet on CIFAR-10 (cross-entropy loss): the time gap between
$t_{label}$ and $t_{opt}$ is increasing when the label corruption ratio is
increasing.

The above experiments support our hypothesis and reconcile the conflict
between the “benign overfitting phenomenon” and our theory: if the signal
strength is strong, “benign overfitting” holds and our theoretical results
still work; if the signal strength is weak, “benign overfitting” can not hold
anymore and our theoretical results explain the reason for the failure of
“benign overfitting”.

##  6 Discussion and conclusion

In this paper, we first showed the positive definiteness of the NTK $K_{d}$
defined on $\mathbb{R}^{d}$, filling a long-standing gap in the literature. We
then proved that the NNK uniformly converges to the NTK, which implies that
the excess risk of wide neural networks is well approximated by that of the
NTK regression function. Thus, for two-layer neural networks and one-
dimensional data, we could prove that: $i)$ if one stops the training process
of wide neural networks at a proper time, the excess risk of the resulting
neural network achieves the minimax optimality; $ii)$ an overfitted neural
network can not generalize well. Finally, we proposed an explanation to
reconcile the contradiction between our theoretical result and the widely
observed “benign overfitting phenomenon”.

Though the current work only dealt with the two-layer neural network and one-
dimensional data, it is clear that the strategy works for more general neural
networks and more complicated data. To be more precise, one may try to first
show that neural network kernels of CNN, ResNet, etc. uniformly converge to
the corresponding neural tangent kernels, then study the spectral properties
of NTK such as positive definiteness and eigenvalue decay rate. Thus, we can
expect that training a wide deep neural network with the early stopping
strategy can produce a neural network with optimal generalization ability.

[Acknowledgments] The authors would like to thank the anonymous referees, the
Associate Editor and the Editor for their constructive comments that improved
the quality of this paper. The corresponding author was supported in part by
the National Natural Science Foundation of China (Grant 11971257), Beijing
Natural Science Foundation (Grant Z190001), National Key R&D Program of China
(2020AAA0105200), and Beijing Academy of Artificial Intelligence.

##  Appendix A Reproducing Kernel Hilbert Space

In this section, we recollect some essential concepts and theorems in the
reproducing kernel Hilbert space (RKHS). For simplicity, we assume that
$\mathcal{H}$ is a separable Hilbert space.

######  Definition 2 (RKHS and reproducing kernel).

Let $\mathcal{H}$ be a Hilbert space of functions defined on a non-empty
$\mathcal{X}$. It is an RKHS if for all $x\in\mathcal{X}$, there exists a
positive constant $M_{x}$, such that

$\displaystyle|f(x)|\leq M_{x}\|f\|_{\mathcal{H}},\quad\forall
f\in\mathcal{H}.$ (16)

By Riesz representation theory, for any $x$, there is an element
$K(\cdot,x)\in\mathcal{H}$ such that

$\displaystyle f(x)=\langle f,K(\cdot,x)\rangle_{\mathcal{H}}.$ (17)

The function $K:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ such that

$\displaystyle K(x,y)=\langle K(\cdot,x),K(\cdot,y)\rangle_{\mathcal{H}},$
(18)

is referred to as the reproducing kernel associated with $\mathcal{H}$. It is
clear that $K$ is a positive semi-definite kernel on $\mathcal{X}$.

######  Lemma A.1.

Suppose that $\\{e_{j},j\geq 1\\}$ is an orthonormal basis of $\mathcal{H}$.
Then

$\displaystyle K(x,y)=\sum_{j=1}^{\infty}e_{j}(x)e_{j}(y)$ (19)

where the sum on RHS converges in $\mathcal{H}$.

###### Proof.

Since $\mathcal{H}$ is an RKHS, the Plancherel theorem shows that

$\displaystyle K(x,y)=\sum_{j=1}^{\infty}\langle K(\cdot,x),e_{j}\rangle
e_{j}(y)$ (20)

where the sum on the RHS converges in $\mathcal{H}$. ∎

Suppose that there is a topological structure and a Borel measure (or its
completion) $\mu_{\mathcal{X}}$ on $\mathcal{X}$ with
$\operatorname{supp}(\mu_{\mathcal{X}})=\mathcal{X}$ such that $\mathcal{X}$
is compact and $K$ is continuous. One then can easily verify that the natural
embedding inclusion operator $I_{K}:\mathcal{H}\to
L^{2}(\mathcal{X},\mu_{\mathcal{X}})$ is a compact operator and the adjoint
operator $I_{K}^{*}:L^{2}(\mathcal{X},\mu_{\mathcal{X}})\to\mathcal{H}$ of
$I_{K}$ is given by:

$\displaystyle
I_{K}^{*}f(x)=\int_{\mathcal{X}}K(x,x^{\prime})f(x^{\prime})\mathrm{d}\mu_{\mathcal{X}}(x^{\prime}).$

Thus we can define an integral operator

$\displaystyle T_{K}=I_{K}\circ
I_{K}^{*}:L^{2}(\mathcal{X},\mu_{\mathcal{X}})\to
L^{2}(\mathcal{X},\mu_{\mathcal{X}})$ (21)

which is a positive semi-definite, self-adjoint, compact operator. The
spectral theorem of the positive semi-definite, self-adjoint, compact operator
shows that there exists a set of non-negative numbers
$\lambda_{1}\geq\lambda_{2}\geq\cdots$ and an orthonormal basis
$\\{\phi_{j},j\geq 1\\}$ of $L^{2}(\mathcal{X},\mu_{\mathcal{X}})$ such that

$\displaystyle
T_{K}f=\sum_{j=1}^{\infty}\lambda_{j}\left<f,\phi_{j}\right>_{L^{2}}\phi_{j},\quad\forall
f\in L^{2}(\mathcal{X},\mu_{\mathcal{X}}).$ (22)

where the sum on the RHS converges in $L^{2}(\mathcal{X},\mu_{\mathcal{X}})$.
In addition, if the operator $I_{K}$ is injective, then
$\\{\sqrt{\lambda_{j}}I_{K}^{*}\phi_{j},j\geq 1\\}$ is an orthonormal basis of
$\mathcal{H}$. Thus, we have

$\displaystyle
K(x,x^{\prime})=\sum_{j=1}^{\infty}\lambda_{j}I_{K}^{*}\phi_{j}(x)I_{K}^{*}\phi_{j}(x^{\prime})$
(23)

where the sum on the RHS converges in $\mathcal{H}$. Note that for any
$f,g\in\mathcal{H}$ and for any $x\in\mathcal{X}$, we have

$\displaystyle|f(x)-g(x)|=|\left<f-g,K_{x}\right>|\leq
M_{x}\|f-g\|_{\mathcal{H}}.$ (24)

Thus the equation (23) holds pointwise. This is the celebrated Mercer’s
decomposition theorem.

The numbers $\\{\lambda_{j},j\geq 1\\}$ and the functions
$\\{I_{K}^{*}\phi_{j},j\geq 1\\}\subseteq\mathcal{H}$ are often referred to as
the eigenvalues and the eigenfunctions associated to the kernel $K$
respectively. With these eigenvalues and the eigenfunctions, $\mathcal{H}$ can
be formulated as

$\mathcal{H}=\left\\{\sum_{j=1}^{\infty}c_{j}I_{K}^{*}\phi_{j}~{}\middle|~{}\sum_{j=1}^{\infty}c_{j}^{2}/\lambda_{j}<\infty\right\\}.$
(25)

##  Appendix B Proof of Section 2

######  Lemma B.1.

Let $K$ be an inner product kernel on $\mathbb{S}^{d}$, i.e.,
$K(\boldsymbol{x},\boldsymbol{x}^{\prime})=f(\langle\boldsymbol{x},\boldsymbol{x}^{\prime}\rangle)$
for some function $f(t):[-1,1]\to\mathbb{R}$ such that
$f(t)=\sum^{\infty}_{k=0}a_{k}t^{k}$ where $a_{k}\geq 0$ for any $k\geq 0$. If
there are infinity number $k$ such that $a_{k}>0$, then $K$ is positive
definite on
$\mathbb{S}^{d}_{+}:=\\{\boldsymbol{x}=(x_{1},\ldots,x_{d+1})\in\mathbb{S}^{d}\mid
x_{d+1}>0\\}$.

###### Proof.

For any different $n$ points $\boldsymbol{x}_{1}$, $\ldots$,
$\boldsymbol{x}_{n}\in\mathbb{S}^{d}_{+}$, the Gram matrix
$(K(\boldsymbol{x}_{i},\boldsymbol{x}_{j}))_{1\leq i,j\leq n}$ has an explicit
formula:

$(K(\boldsymbol{x}_{i},\boldsymbol{x}_{j}))_{1\leq i,j\leq n}=\sum_{k\geq
0}a_{k}M_{k},$

where
$M_{k}=\left(\langle\boldsymbol{x}_{i},\boldsymbol{x}_{j}\rangle^{k}\right)_{1\leq
i,j\leq n}$. It is obvious that each $M_{k}$ is positive semi-definite. Since
the diagonal elements of $M_{k}$ equal to 1 and
$\langle\boldsymbol{x}_{i},\boldsymbol{x}_{j}\rangle<1$ for
$\boldsymbol{x}_{i}\neq\boldsymbol{x}_{j}\in\mathbb{S}^{d}_{+}$. By Gershgorin
circle theorem, we know that for sufficiently large $k$, $M_{k}$ is positive
definite. Since there are infinitely many positive $a_{k}$’s, we know that
$(K(\boldsymbol{x}_{i},\boldsymbol{x}_{j}))_{1\leq i,j\leq n}$ is positive
definite. ∎

###### Proof of Proposition 2.1.

Let $\boldsymbol{z}^{\mathsf{T}}=(\boldsymbol{x}^{\mathsf{T}},1)$. By the
definition of the NTK, we have

$\displaystyle K(\boldsymbol{x},\boldsymbol{x}^{\prime})$
$\displaystyle=(1+\left<\boldsymbol{x},\boldsymbol{x}^{\prime}\right>)\kappa_{0}(\boldsymbol{z},\boldsymbol{z}^{\prime})+\|\boldsymbol{z}\|_{2}\|\boldsymbol{z}^{\prime}\|_{2}\kappa_{1}(\boldsymbol{z},\boldsymbol{z}^{\prime})+1$
$\displaystyle=\kappa_{0}(\boldsymbol{z},\boldsymbol{z}^{\prime})+\left<\boldsymbol{x},\boldsymbol{x}^{\prime}\right>\kappa_{0}(\boldsymbol{z},\boldsymbol{z}^{\prime})+\|\boldsymbol{z}\|_{2}\|\boldsymbol{z}^{\prime}\|_{2}\kappa_{1}(\boldsymbol{z},\boldsymbol{z}^{\prime})+1$

where
$\kappa_{n}(\boldsymbol{z},\boldsymbol{z}^{\prime}):=2\mathbf{E}_{\omega\sim\mathcal{N}(0,\boldsymbol{I})}[\sigma^{\prime}(\langle\omega,\boldsymbol{z}\rangle)\sigma^{\prime}(\langle\omega,\boldsymbol{z}^{\prime}\rangle)(\langle\omega,\boldsymbol{z}\rangle)^{n}(\langle\omega,\boldsymbol{z}^{\prime}\rangle)^{n}]$
is the arc-cosine kernels of degree $n$ [20] and $\sigma(x):=\max\\{x,0\\}$.

The arc-cosine kernels $\kappa_{0}$ and $\kappa_{1}$ of degree $0$ and $1$,
have the explicitly form (see e.g., [20]):

$\displaystyle\kappa_{0}(\boldsymbol{z},\boldsymbol{z}^{\prime})$
$\displaystyle=\frac{1}{\pi}(\pi-\psi(\boldsymbol{z},\boldsymbol{z}^{\prime}))$
$\displaystyle\kappa_{1}(\boldsymbol{z},\boldsymbol{z}^{\prime})$
$\displaystyle=\frac{1}{\pi}\left(\langle\frac{\boldsymbol{z}}{\lVert\boldsymbol{z}\rVert_{2}},\frac{\boldsymbol{z}^{\prime}}{\lVert\boldsymbol{z}^{\prime}\rVert_{2}}\rangle(\pi-\psi(\boldsymbol{z},\boldsymbol{z}^{\prime}))+\sin(\psi(\boldsymbol{z},\boldsymbol{z}^{\prime}))\right),$

where
$\psi(\boldsymbol{z},\boldsymbol{z}^{\prime})=\arccos\left(\langle\frac{\boldsymbol{z}}{\lVert\boldsymbol{z}\rVert_{2}},\frac{\boldsymbol{z}^{\prime}}{\lVert\boldsymbol{z}^{\prime}\rVert_{2}}\rangle\right)$.
We can see that $\kappa_{0}(\boldsymbol{z},\boldsymbol{z}^{\prime})$ and
$\kappa_{1}(\boldsymbol{z},\boldsymbol{z}^{\prime})$ can be considered inner
product kernels on $\mathbb{S}^{d}_{+}$, i.e.,
$\kappa_{0}(\boldsymbol{z},\boldsymbol{z}^{\prime})=f_{0}(\langle\hat{\boldsymbol{z}},\hat{\boldsymbol{z}}^{\prime}\rangle)$
and
$\kappa_{1}(\boldsymbol{z},\boldsymbol{z}^{\prime})=f_{1}(\langle\hat{\boldsymbol{z}},\hat{\boldsymbol{z}}^{\prime}\rangle)$
for some functions $f_{0}$ and $f_{1}$ satisfying the conditions of Lemma B.1
and
$\hat{\boldsymbol{z}}=\frac{\boldsymbol{z}}{\lVert\boldsymbol{z}\rVert_{2}}$
and
$\hat{\boldsymbol{z}^{\prime}}=\frac{\boldsymbol{z}^{\prime}}{\lVert\boldsymbol{z}^{\prime}\rVert_{2}}$
defined on $\mathbb{S}^{d}_{+}$. By Lemma B.1,
$\kappa_{0}(\boldsymbol{z},\boldsymbol{z}^{\prime})$ and
$\kappa_{1}(\boldsymbol{z},\boldsymbol{z}^{\prime})$ are positive definite,
meaning that $K(\boldsymbol{x},\boldsymbol{x}^{\prime})$ is also positive
definite. ∎

In the following section, we consider the spectral properties of the NTK over
data of dimensional one assuming that $\mu_{\mathcal{X}}$ is the uniform
distribution on $[0,1]$. Through Equation (3) with $d=1$, the NTK
$K(x,x^{\prime})$ can be presented as followed:

$\displaystyle
K(x,x^{\prime})=\frac{2}{\pi}(\pi-\psi(x,x^{\prime}))(1+xx^{\prime})+\frac{1}{\pi}|x-x^{\prime}|+1.$
(26)

where
$\psi(x,x^{\prime})=\arccos\frac{1+xx^{\prime}}{\sqrt{(1+x^{2})(1+(x^{\prime})^{2})}}$.
Define $\Pi_{0}$ and $\Pi_{1}$ as

$\displaystyle\Pi_{0}(x,x^{\prime})$
$\displaystyle=\frac{1}{\pi}(\pi-\psi(x,x^{\prime}))$ (27)
$\displaystyle\Pi_{1}(x,x^{\prime})$
$\displaystyle=\frac{1}{\pi}\left((1+xx^{\prime})(\pi-\psi(x,x^{\prime}))+|x-x^{\prime}|\right).$
(28)

The following lemma shows the positive definiteness of $\Pi_{0}$ and
$\Pi_{1}$:

######  Lemma B.2.

$\Pi_{0}(x,x^{\prime})$ and $\Pi_{1}(x,x^{\prime})$ are positive definite on
$[0,1]$.

###### Proof of Lemma B.2.

Suppose that $\boldsymbol{X}=\\{x_{1},\dots,x_{n}\\}\subseteq[0,1]$ and
$\boldsymbol{Z}=\\{\boldsymbol{z}_{1},\cdots,\boldsymbol{z}_{n}\\}$ where
$\boldsymbol{z}_{i}=(x_{i},1)$. Denote
$D_{z}=\operatorname{diag}\\{\|\boldsymbol{z}_{i}\|_{2}\\}_{i\in[n]}$ where
$\|\boldsymbol{z}_{i}\|_{2}\geq 1$.
$\Pi_{0}(\boldsymbol{X},\boldsymbol{X})=\kappa_{0}(\boldsymbol{Z},\boldsymbol{Z})$
and
$\Pi_{1}(\boldsymbol{X},\boldsymbol{X})=D_{z}\kappa_{1}(\boldsymbol{Z},\boldsymbol{Z})D_{z}$.
Since $\kappa_{0}(\boldsymbol{Z},\boldsymbol{Z})$,
$\kappa_{1}(\boldsymbol{Z},\boldsymbol{Z})$ are positive definite and $D_{z}$
is invertible, $\Pi_{0}(\boldsymbol{X},\boldsymbol{X})$ and
$\Pi_{1}(\boldsymbol{X},\boldsymbol{X})$ are positive definite. ∎

###### Proof of Theorem 2.2 $i)$.

Suppose that $\boldsymbol{X}=\\{x_{1},...,x_{n}\\}\subseteq[0,\pi]$. Let
$G_{\alpha}(x,x^{\prime})=\alpha-\frac{|x-x^{\prime}|}{\pi}$ where $\alpha\geq
1$. Since $\boldsymbol{X}$ is one-dimensional data, we have the following
lemmas.

######  Lemma B.3.

Let $d_{\min}=\min\\{|x_{i}-x_{j}|\\}$. We then have

$\displaystyle\frac{d_{\min}}{2\pi}\leq\lambda_{\min}(G_{\alpha}(\boldsymbol{X},\boldsymbol{X}))\leq\frac{2d_{\min}}{\pi}$
(29)

######  Lemma B.4.

Suppose that $A$ and $B$ are two symmetric matrices. We use that notation
$A\geq B$ if $A-B$ is a positive semi-definite matrix. Then we have

$G_{1}(\boldsymbol{X},\boldsymbol{X})\leq K(\boldsymbol{X},\boldsymbol{X})\leq
7G_{9/7}(\boldsymbol{X},\boldsymbol{X}).$ (30)

Its clear that Lemma B.4 implies that

$\displaystyle\lambda_{\min}(G_{1}(\boldsymbol{X},\boldsymbol{X}))\leq\lambda_{\min}(K(\boldsymbol{X},\boldsymbol{X}))\leq
7\lambda_{\min}(G_{9/7}(\boldsymbol{X},\boldsymbol{X}))$ (31)

and Lemma B.3 implies Theorem 2.2 $i)$.

∎

###### Proof of Lemma B.3.

Note that $G_{\alpha}^{-1}(\boldsymbol{X},\boldsymbol{X})=$

$\frac{\pi}{2}\begin{pmatrix}\frac{1}{x_{2}-x_{1}}+\frac{1}{2\alpha\pi-
x_{n}+x_{1}}&-\frac{1}{x_{2}-x_{1}}&0&\dots&0&\frac{1}{2\alpha\pi-
x_{n}+x_{1}}\\\
-\frac{1}{x_{2}-x_{1}}&\frac{1}{x_{2}-x_{1}}+\frac{1}{x_{3}-x_{2}}&-\frac{1}{x_{3}-x_{2}}&\dots&0&0\\\
0&\ddots&\ddots&\ddots&&\vdots\\\ \vdots&&&&&\\\
0&&&&\frac{1}{x_{n-1}-x_{n-2}}+\frac{1}{x_{n}-x_{n-1}}&-\frac{1}{x_{n}-x_{n-1}}\\\
\frac{1}{2\alpha\pi-
x_{n}+x_{1}}&0&\dots&0&-\frac{1}{x_{n}-x_{n-1}}&\frac{1}{x_{n}-x_{n-1}}+\frac{1}{2\alpha\pi-
x_{n}+x_{1}}\end{pmatrix}.$

(32)

By Gershgorin circle theorem, every eigenvalue of
$G_{\alpha}^{-1}=G_{\alpha}^{-1}(\boldsymbol{X},\boldsymbol{X})$ lies in one
of the Gershgorin discs
$D_{i}=\left\\{\lambda~{}\big{|}~{}|\lambda-(G_{\alpha}^{-1})_{i,i}|\leq\sum_{j\neq
i}|(G_{\alpha}^{-1})_{i,j}|\right\\}$. In particular, we have

$\lambda_{\max}(G_{\alpha}^{-1})\leq\max_{i\in[n]}\max_{\lambda}D_{i}\leq\max_{i\in[n]}\left\\{\sum_{j\in[n]}|G^{-1}_{i,j}|\right\\}\leq\frac{2\pi}{d_{\min}},$
(33)

which means $\lambda_{\min}(G_{\alpha})\geq\frac{d_{\min}}{2\pi}$.

One the other hand, assume that $x_{k+1}-x_{k}=d_{\min}$ for some $k$. Since
$\lambda_{\max}(G_{\alpha}^{-1})\geq u^{\mathsf{T}}G_{\alpha}^{-1}u$ for
$\forall u$ with $\|u\|_{2}=1$, let $u$ be the vector that only has 1 in the
$k$-th entry and the rest are zero. Thus, we have
$\lambda_{\max}(G_{\alpha}^{-1})\geq\frac{\pi}{2d_{\min}}$, which means
$\lambda_{\min}(G_{\alpha})\leq\frac{2d_{\min}}{\pi}$. To sum up, we have

$\frac{d_{\min}}{2\pi}\leq\lambda_{\min}(G_{\alpha})\leq\frac{2d_{\min}}{\pi}.$
(34)

∎

######  Corollary B.5.

The kernel function $G_{\alpha}$ is positive definite on $[0,\pi]$.

###### Proof of lemma B.4.

We can easily verify the following equation from the equation (26) and the
definition of $G_{\alpha}$:

$\displaystyle K(x,x^{\prime})$
$\displaystyle=G_{1}(x,x^{\prime})+2\Pi_{1}(x,x^{\prime})$ (35)
$\displaystyle=2\Pi_{0}(x,x^{\prime})(1+xx^{\prime})-G_{1}(x,x^{\prime})+2.$

It is clear that $K(\boldsymbol{X},\boldsymbol{X})\geq
G_{1}(\boldsymbol{X},\boldsymbol{X})$ from the first line in (35).

On the other hand, let $z(x)=2x-\psi(0,x)$. We can easily verify that

$\displaystyle z(0)=0;\quad z^{\prime}(x)=2-\frac{\psi(0,x)}{\partial
x}=2-\frac{1}{1+x^{2}}>0,\forall x\in[0,1];\quad z(1)=2-\frac{\pi}{4}\leq\pi.$

Thus $z(x)\in[0,\pi]$. Let $\boldsymbol{Z}=\\{z_{1},...,z_{n}\\}$, where
$z_{i}=2x_{i}-\psi(0,x_{i})$. Each entry of $G(\boldsymbol{Z},\boldsymbol{Z})$
is given by

$G(z_{i},z_{j})=1-\frac{|2x_{i}-2x_{j}-\psi(0,x_{i})+\psi(0,x_{j})|}{\pi}\\\
=2(1-\frac{|x_{i}-x_{j}|}{\pi})-(1-\frac{\psi(x_{i},x_{j})}{\pi}).$

Thus
$G_{1}(\boldsymbol{Z},\boldsymbol{Z})=2G_{1}(\boldsymbol{X},\boldsymbol{X})-\Pi_{0}(\boldsymbol{X},\boldsymbol{X})$.
Since $G_{1}(\boldsymbol{Z},\boldsymbol{Z})$ is positive definite by Corollary
B.5, we know
$\Pi_{0}(\boldsymbol{X},\boldsymbol{X})<2G_{1}(\boldsymbol{X},\boldsymbol{X})$.

Let $D_{X}=\operatorname{diag}\\{(x_{i})_{i\in[n]}\\}$ and
$1_{n}=[1,\dots,1]^{\mathsf{T}}$. Note that
$D_{X}\Pi_{0}(\boldsymbol{X},\boldsymbol{X})D_{X}\leq\Pi_{0}(\boldsymbol{X},\boldsymbol{X})$
since $x_{i}\in[0,1]$. Thus, from the second line in (35) we have

$\displaystyle K(\boldsymbol{X},\boldsymbol{X})$
$\displaystyle=2\Pi_{0}(\boldsymbol{X},\boldsymbol{X})+2D_{X}\Pi_{0}(\boldsymbol{X},\boldsymbol{X})D_{X}-G_{1}(\boldsymbol{X},\boldsymbol{X})+21_{n}1_{n}^{\mathsf{T}}$
$\displaystyle\leq
4\Pi_{0}(\boldsymbol{X},\boldsymbol{X})-G_{1}(\boldsymbol{X},\boldsymbol{X})+21_{n}1_{n}^{\mathsf{T}}\leq
7G_{1}(\boldsymbol{X},\boldsymbol{X})+21_{n}1_{n}^{\mathsf{T}}=7G_{\frac{9}{7}}(\boldsymbol{X},\boldsymbol{X}).$

∎

###### Proof of Theorem 2.2 $ii)$.

Theorem 2.2 $ii)$ is a direct corollary of the following lemmas.

######  Lemma B.6.

Let $\\{\lambda^{(\alpha)}_{j},j\geq 1\\}$ and $\\{\lambda^{K}_{j},j\geq 1\\}$
be the eigenvalues associated to the kernel $G_{\alpha}$ and $K$ on $[0,1]$,
respectively. Then we have

$\lambda^{(1)}_{j}\leq\lambda^{K}_{j}\leq 7\lambda^{(9/7)}_{j},\quad j\geq 1.$
(36)

######  Lemma B.7.

Suppose that $\alpha=\\{1,\frac{9}{7}\\}$. There exist constants $c$ and $C$
such that

$\frac{c}{j^{2}}\leq\lambda^{(\alpha)}_{j}\leq\frac{C}{j^{2}},j\geq 1.$ (37)

∎

###### Proof of lemma B.6.

It is a direct corollary of the following lemma.

######  Lemma B.8 (Corollary of Theorem 3.1 of [39]).

Let $A$ be a kernel function on $\mathcal{X}\times\mathcal{X}$ with
$\int_{\mathcal{X}}\int_{\mathcal{X}}A(x,x^{\prime})^{2}\mathrm{d}x\mathrm{d}x^{\prime}<\infty$.
For $\boldsymbol{X}=\\{x_{1},\dots,x_{n}\\}\subseteq\mathcal{X}$, let
$\hat{\lambda}_{j}$ be the eigenvalue of $A(\boldsymbol{X},\boldsymbol{X})$
and $\lambda_{j}$ be the eigenvalue of the kernel $A$. Then, for any fixed
$j$, we have

$|\hat{\lambda}_{j}-\lambda_{j}|\to 0,\mbox{as $n\to\infty$}.$ (38)

In fact, by Lemma B.4, we have $G_{1}(\boldsymbol{X},\boldsymbol{X})\leq
K(\boldsymbol{X},\boldsymbol{X})\leq
7G_{\frac{9}{7}}(\boldsymbol{X},\boldsymbol{X}).$ Thus, we have
$\hat{\lambda}^{(1)}_{j}\leq\hat{\lambda}^{K}_{j}\leq
7\hat{\lambda}^{(9/7)}_{j},j=1,2,...,n.$ Then Lemma B.8 provides us that for
any fixed $j\geq 1$,

$\lambda^{(1)}_{j}\leq\lambda^{K}_{j}\leq 7\lambda^{(9/7)}_{j}.$ (39)

∎

###### Proof of lemma B.7.

Since the $G_{\alpha}$ ($\alpha=1,9/7$) is a positive definite kernel on
$[0,1]$, we know that $\lambda_{j}\geq 0$ for any $j=1,2,\cdots$. Let
$\lambda\neq 0$ be an eigenvalue of $G_{\alpha}$, i.e., there is an
eigenfunction $f(x)$ such that

$\begin{split}\lambda
f(x)&=\left(T_{G_{\alpha}}f\right)(x)=\int_{0}^{1}\left(\alpha-\frac{|x-x^{\prime}|}{\pi}\right)f(x^{\prime})\mathrm{d}x^{\prime}\\\
&=\int_{0}^{1}\alpha
f(x^{\prime})\mathrm{d}x^{\prime}-\frac{1}{\pi}\left(\int_{0}^{x}(x-x^{\prime})f(x^{\prime})\mathrm{d}x^{\prime}+\int_{x}^{1}(x^{\prime}-x)f(x^{\prime})\mathrm{d}x^{\prime}\right).\end{split}$
(40)

After taking the first and second derivatives on both sides with respect to
$x$, we get

$\lambda
f^{\prime}(x)=-\frac{1}{\pi}\left(\int_{0}^{x}f(x^{\prime})\mathrm{d}x^{\prime}-\int_{x}^{1}f(x^{\prime})\mathrm{d}x^{\prime}\right),$
(41)

and

$\lambda f^{\prime\prime}(x)=-\frac{2}{\pi}f(x).$ (42)

It is well known that the solutions of (42) are of the following forms:

$f(x)=A\cos(\omega x)+B\sin(\omega x).$ (43)

Inserting equation (43) back to equation (42), we know that

$\omega^{2}=\frac{2}{\pi\lambda}>0.$ (44)

Inserting Equation (43) and (44) in Equation (40), we have

$\begin{split}\frac{2}{\pi\omega^{2}}f(x)&=-\frac{1}{\pi}x\omega(B+B\cos(\omega)-A\sin(\omega))+\frac{2}{\pi\omega^{2}}f(x)\\\
&+\frac{1}{\pi}A(\alpha\pi\omega\sin(\omega)-1-\omega\sin(\omega)-\cos(\omega))\\\
&+\frac{1}{\pi}B(\alpha\pi\omega(1-\cos(\omega))+\omega\cos(\omega)-\sin(\omega)),\end{split}$
(45)

which holds for all $x$ if and only if

$\begin{cases}-A\sin(\omega)+B(1+\cos(\omega))=0,\\\
A(\alpha\pi\omega\sin(\omega)-1-\omega\sin(\omega)-\cos(\omega))+B(\alpha\pi\omega(1-\cos(\omega))+\omega\cos(\omega)-\sin(\omega))=0.\\\
\end{cases}$

A necessary and sufficient condition for this system to be degenerate (i.e.,
it has a nontrivial solution $A$ and $B$) is

$\det\begin{pmatrix}-\sin(\omega)&1+\cos(\omega)\\\
\alpha\pi\omega\sin(\omega)-1-\omega\sin(\omega)-\cos(\omega)&\alpha\pi\omega(1-\cos(\omega))+\omega\cos(\omega)-\sin(\omega)\end{pmatrix}=0,$
(46)

i.e.,

$2+2\cos(\omega)+\omega\sin(\omega)(1-2\alpha\pi)=0.$ (47)

In fact, denote the left-hand side of the equation (47) by $h(\omega)$, i.e.,
$h(\omega)=2+2\cos(\omega)+\omega\sin(\omega)(1-2\alpha\pi)$. Since
$h(\omega)=h(-\omega)$, we only need to prove the assertion (55) for
$\omega>0$. By Lemma B.9 and Equation (44), we have

$\begin{cases}\lambda_{j}\in[\frac{8}{\pi^{3}},\frac{72}{\pi^{3}}],&\mbox{$j=1$};\\\
\lambda_{j}=\frac{2}{\pi^{3}}(j-1)^{-2},&\mbox{$j$ is even};\\\
\lambda_{j}\in[\frac{2}{\pi^{3}}(j-\frac{1}{2})^{-2},\frac{2}{\pi^{3}}(j-1)^{-2}],&\mbox{$j>1$
and $j$ is odd}.\end{cases}$ (48)

To sum up,

$\frac{c}{j^{2}}\leq\lambda_{j}\leq\frac{C}{j^{2}},j\geq 1$ (49)

for some absolute constants $c$ and $C$. ∎

###### Proof of lemma B.8.

By Theorem 3.1 of [39], we have

$\sqrt{\sum_{j=1}^{\infty}(\hat{\lambda}_{j}-\lambda_{j})^{2}}\to 0,\mbox{as
$n\to\infty$},$ (50)

where $\hat{\lambda}_{j}=0$ for $j\geq n$. This implies that for any fixed
$j\geq 1$,

$|\hat{\lambda}_{j}-\lambda_{j}|\leq\sqrt{\sum_{l=1}^{\infty}(\hat{\lambda}_{l}-\lambda_{l})^{2}}\to
0,\mbox{as $n\to\infty$}.$ (51)

∎

######  Lemma B.9.

Let $h(\omega)=2+2\cos(\omega)+\omega\sin(\omega)(1-2\alpha\pi)$, where
$\alpha\in\\{1,\frac{9}{7}\\}$ Then the solutions of

$h(\omega)=0,\quad\omega>0$ (52)

are given by

$\begin{cases}\omega_{j}\in[\frac{1}{6}\pi,\frac{1}{2}\pi],&\mbox{$j=1$};\\\
\omega_{j}=(j-1)\pi,&\mbox{$j$ is even};\\\
\omega_{j}\in((j-1)\pi,(j-\frac{1}{2})\pi),&\mbox{$j>1$ and $j$ is
odd}.\end{cases}$ (53)

###### Proof.

When $\omega\in(0,\pi)$, we can easily verify the following facts

  * (1).

$h(\frac{\pi}{6})=2+\sqrt{3}-(2\alpha\pi-1)\frac{\pi}{12}>0$;

  * (2).

If $\omega\in(0,\frac{1}{2}\pi]$, we have

$h^{\prime}(\omega)=-2\sin(\omega)+(1-2\alpha\pi)\sin(\omega)+(1-2\alpha\pi)\omega\cos(\omega)<0.$
(54)

  * (3).

If $\omega\in[\frac{1}{2}\pi,\pi)$, then

$h(\omega)<2+2\cos(\omega)-2\sin(\omega)=2+2\sqrt{2}\cos(\omega+\frac{\pi}{4})\leq
0.$

Since $h(\omega)$ is a continuous function on $(0,\pi)$, the above facts imply
that $h(\omega)=0$ has a unique solution $[\frac{1}{6}\pi,\frac{1}{2}\pi]$
which is denoted by $\omega_{1}$.

When $\omega\geq\pi$, it is clear that for any even number $j$, $j\pi$ is a
solution of the equation (52) with multiplicity one. We will show that there
is another unique solution of the equation (52) in the interval
$(j\pi,(j+2)\pi)$ where $j$ is an even integer. Thus, the solutions of the
equation can be indexed by $\mathbb{N}_{+}$ in the following way

$\displaystyle\omega_{2k}=(2k-1)\pi\mbox{ and
}\omega_{2k+1}\in((2k-1)\pi,(2k+1)\pi),\quad k=1,2,\cdots.$ (55)

When $\omega\in((2k-1)\pi,(2k+1)\pi),k\in\mathbb{N}_{+}$, we can easily verify
the following facts.

  * (1).

If $\omega\in((2k-1)\pi,2k\pi))$, then
$h(\omega)>\omega\sin(\omega)(1-2\alpha\pi)>0$;

  * (2).

If $\omega\in[2k\pi,(2k+\frac{1}{2})\pi]$, we have

$h^{\prime}(\omega)=-2\sin(\omega)+(1-2\alpha\pi)\sin(\omega)+(1-2\alpha\pi)\omega\cos(\omega)<0.$
(56)

  * (3).

If $\omega\in((2k+\frac{1}{2})\pi,(2k+1)\pi)$, then

$h(\omega)<2+2\cos(\omega)-2\sin(\omega)=2+2\sqrt{2}\cos(\omega+\frac{\pi}{4})<0.$

Since $h(\omega)$ is a continuous function on $((2k-1)\pi,(2k+1)\pi)$, the
above facts imply that $h(\omega)=0$ has a unique solution
$\in[2k\pi,(2k+\frac{1}{2})\pi]$, which is denoted by $\omega_{2k+1}$. Thus,
we have

$\begin{cases}\omega_{j}\in[\frac{1}{6}\pi,\frac{1}{2}\pi],&\mbox{$j=1$};\\\
\omega_{j}=(j-1)\pi,&\mbox{$j$ is even};\\\
\omega_{j}\in((j-1)\pi,(j-\frac{1}{2})\pi),&\mbox{$j>1$ and $j$ is
odd}.\end{cases}$ (57)

∎

Supplement to “Generalization Ability of Wide Neural Networks on $\mathbb{R}$”
This supplementary file contains the proofs of Theorem 3.1, 4.1 and 4.2.

## References

  * [1] [author] Allen-Zhu, ZeyuanZ., Li, YuanzhiY. and Song, ZhaoZ. (2019). A convergence theory for deep learning via over-parameterization. In International Conference on Machine Learning 242–252. PMLR.
  * [2] [author] Arora, SanjeevS., Du, SimonS., Hu, WeiW., Li, ZhiyuanZ. and Wang, RuosongR. (2019). Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning 322–332. PMLR.
  * [3] [author] Arora, SanjeevS., Du, Simon SS. S., Hu, WeiW., Li, ZhiyuanZ., Salakhutdinov, Russ RR. R. and Wang, RuosongR. (2019). On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems 32\.
  * [4] [author] Bartlett, Peter LP. L., Long, Philip MP. M., Lugosi, GáborG. and Tsigler, AlexanderA. (2020). Benign overfitting in linear regression. Proceedings of the National Academy of Sciences 117 30063–30070.
  * [5] [author] Bauer, BenediktB. and Kohler, MichaelM. (2019). On Deep Learning as a Remedy for the Curse of Dimensionality in Nonparametric Regression. The Annals of Statistics 47 2261–2285. 10.1214/18-AOS1747
  * [6] [author] Beaglehole, DanielD., Belkin, MikhailM. and Pandit, PartheP. (2022). Kernel Ridgeless Regression Is Inconsistent in Low Dimensions. 10.48550/arXiv.2205.13525
  * [7] [author] Belkin, MikhailM. (2021). Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. Acta Numerica 30 203–248.
  * [8] [author] Belkin, MikhailM., Ma, SiyuanS. and Mandal, SoumikS. (2018). To Understand Deep Learning We Need to Understand Kernel Learning. In Proceedings of the 35th International Conference on Machine Learning 541–549. PMLR.
  * [9] [author] Belkin, MikhailM., Rakhlin, AlexanderA. and Tsybakov, Alexandre BA. B. (2019). Does data interpolation contradict statistical optimality? In The 22nd International Conference on Artificial Intelligence and Statistics 1611–1619. PMLR.
  * [10] [author] Bietti, AlbertoA. and Bach, FrancisF. (2020). Deep equals shallow for relu networks in kernel regimes. arXiv preprint arXiv:2009.14397.
  * [11] [author] Bietti, AlbertoA. and Mairal, JulienJ. (2019). On the inductive bias of neural tangent kernels. Advances in Neural Information Processing Systems 32\.
  * [12] [author] Blanchard, GillesG. and Mücke, NicoleN. (2018). Optimal Rates for Regularization of Statistical Inverse Learning Problems. Foundations of Computational Mathematics 18 971–1013. 10.1007/s10208-017-9359-7
  * [13] [author] Bordelon, BlakeB., Canatar, AbdulkadirA. and Pehlevan, CengizC. (2020). Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning 1024–1034. PMLR.
  * [14] [author] Boucheron, StéphaneS., Lugosi, GáborG. and Massart, PascalP. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, Oxford. 10.1093/acprof:oso/9780199535255.001.0001
  * [15] [author] Buchholz, SimonS. (2022). Kernel Interpolation in Sobolev Spaces Is Not Consistent in Low Dimensions. In Proceedings of Thirty Fifth Conference on Learning Theory 3410–3440. PMLR.
  * [16] [author] Canatar, AbdulkadirA., Bordelon, BlakeB. and Pehlevan, CengizC. (2021). Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature communications 12 1–12.
  * [17] [author] Cao, YuanY., Fang, ZhiyingZ., Wu, YueY., Zhou, Ding-XuanD.-X. and Gu, QuanquanQ. (2019). Towards understanding the spectral bias of deep learning. arXiv preprint arXiv:1912.01198.
  * [18] [author] Caponnetto, AndreaA. and De Vito, ErnestoE. (2007). Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics 7 331–368.
  * [19] [author] Chizat, LénaïcL., Oyallon, EdouardE. and Bach, FrancisF. (2019). On Lazy Training in Differentiable Programming. In Advances in Neural Information Processing Systems 32\. Curran Associates, Inc.
  * [20] [author] Cho, YoungminY. and Saul, LawrenceL. (2009). Kernel methods for deep learning. Advances in neural information processing systems 22\.
  * [21] [author] Devlin, JacobJ., Chang, Ming-WeiM.-W., Lee, KentonK. and Toutanova, KristinaK. (2018). Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805.
  * [22] [author] Devlin, JacobJ., Chang, Ming-WeiM.-W., Lee, KentonK. and Toutanova, KristinaK. (2019). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In NAACL-HLT (1).
  * [23] [author] Du, SimonS., Lee, JasonJ., Li, HaochuanH., Wang, LiweiL. and Zhai, XiyuX. (2019). Gradient descent finds global minima of deep neural networks. In International conference on machine learning 1675–1685. PMLR.
  * [24] [author] Du, Simon SS. S., Zhai, XiyuX., Poczos, BarnabasB. and Singh, AartiA. (2018). Gradient Descent Provably Optimizes Over-parameterized Neural Networks. In International Conference on Learning Representations.
  * [25] [author] Eldan, RonenR., Mikulincer, DanD. and Schramm, TselilT. (2021). Non-asymptotic approximations of neural networks by Gaussian processes. In Conference on Learning Theory 1754–1775. PMLR.
  * [26] [author] Frei, SpencerS., Chatterji, Niladri SN. S. and Bartlett, PeterP. (2022). Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory 2668–2703. PMLR.
  * [27] [author] Geifman, AmnonA., Yadav, AbhayA., Kasten, YoniY., Galun, MeiravM., Jacobs, DavidD. and Ronen, BasriB. (2020). On the similarity between the laplace and neural tangent kernels. Advances in Neural Information Processing Systems 33 1451–1461.
  * [28] [author] Hayakawa, SatoshiS. and Suzuki, TaijiT. (2020). On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces. Neural Networks 123 343–361.
  * [29] [author] Hu, TianyangT., Wang, WenjiaW., Lin, CongC. and Cheng, GuangG. (2021). Regularization matters: A nonparametric perspective on overparametrized neural network. In International Conference on Artificial Intelligence and Statistics 829–837. PMLR.
  * [30] [author] Hu, WeiW., Li, ZhiyuanZ. and Yu, DingliD. (2019). Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. arXiv preprint arXiv:1905.11368.
  * [31] [author] Huang, YanpingY., Cheng, YoulongY., Bapna, AnkurA., Firat, OrhanO., Chen, DehaoD., Chen, MiaM., Lee, HyoukJoongH., Ngiam, JiquanJ., Le, Quoc VQ. V., Wu, YonghuiY. et al. (2019). Gpipe: Efficient training of giant neural networks using pipeline parallelism. Advances in neural information processing systems 32\.
  * [32] [author] Imaizumi, MasaakiM. and Fukumizu, KenjiK. (2019). Deep neural networks learn non-smooth functions effectively. In The 22nd international conference on artificial intelligence and statistics 869–878. PMLR.
  * [33] [author] Jacot, ArthurA., Gabriel, FranckF. and Hongler, ClémentC. (2018). Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv:1806.07572.
  * [34] [author] Jacot, ArthurA., Simsek, BerfinB., Spadaro, FrancescoF., Hongler, ClémentC. and Gabriel, FranckF. (2020). Kernel alignment risk estimator: Risk prediction from training data. Advances in Neural Information Processing Systems 33 15568–15578.
  * [35] [author] Jumper, JohnJ., Evans, RichardR., Pritzel, AlexanderA., Green, TimT., Figurnov, MichaelM., Ronneberger, OlafO., Tunyasuvunakool, KathrynK., Bates, RussR., Žídek, AugustinA., Potapenko, AnnaA. et al. (2021). Highly accurate protein structure prediction with AlphaFold. Nature 596 583–589.
  * [36] [author] Karakida, RyoR., Akaho, ShotaroS. and Amari, Shun-ichiS.-i. (2019). Universal statistics of fisher information in deep neural networks: Mean field approach. In The 22nd International Conference on Artificial Intelligence and Statistics 1032–1041. PMLR.
  * [37] [author] Kim, YongdaiY., Ohn, IlsangI. and Kim, DonghaD. (2021). Fast Convergence Rates of Deep Neural Networks for Classification. Neural Networks 138 179–197. 10.1016/j.neunet.2021.02.012
  * [38] [author] Kohler, MichaelM. and Krzyżak, AdamA. (2005). Adaptive regression estimation with multilayer feedforward neural networks. Nonparametric Statistics 17 891–913.
  * [39] [author] Koltchinskii, VladimirV. and Giné, EvaristE. (2000). Random matrix approximation of spectra of integral operators. Bernoulli 113–167.
  * [40] [author] Krizhevsky, AlexA., Sutskever, IlyaI. and Hinton, Geoffrey EG. E. (2012). Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems 25\.
  * [41] [author] Lee, JaehoonJ., Xiao, LechaoL., Schoenholz, SamuelS., Bahri, YasamanY., Novak, RomanR., Sohl-Dickstein, JaschaJ. and Pennington, JeffreyJ. (2019). Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems 32 8572–8583.
  * [42] [author] Lei, YunwenY., Jin, RongR. and Ying, YimingY. (2022). Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks. In Advances in Neural Information Processing Systems.
  * [43] [author] Liang, TengyuanT. and Rakhlin, AlexanderA. (2020). Just interpolate: Kernel “ridgeless” regression can generalize. The Annals of Statistics 48 1329–1347.
  * [44] [author] Lin, JunhongJ., Rudi, AlessandroA., Rosasco, LorenzoL. and Cevher, VolkanV. (2020). Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces. Applied and Computational Harmonic Analysis 48 868–890. 10.1016/j.acha.2018.09.009
  * [45] [author] Mallinar, NeilN., Simon, James BJ. B., Abedsoltan, AmirhesamA., Pandit, PartheP., Belkin, MikhailM. and Nakkiran, PreetumP. (2022). Benign, tempered, or catastrophic: A taxonomy of overfitting. arXiv preprint arXiv:2207.06569.
  * [46] [author] Mei, SongS., Misiakiewicz, TheodorT. and Montanari, AndreaA. (2019). Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. In Conference on Learning Theory 2388–2464. PMLR.
  * [47] [author] Montanari, AndreaA. and Zhong, YiqiaoY. (2022). The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Training. The Annals of Statistics 50 2816–2847. 10.1214/22-AOS2211
  * [48] [author] Nakkiran, PreetumP., Kaplun, GalG., Bansal, YaminiY., Yang, TristanT., Barak, BoazB. and Sutskever, IlyaI. (2021). Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment 2021 124003\.
  * [49] [author] Petersen, PhilippP. and Voigtlaender, FelixF. (2018). Optimal Approximation of Piecewise Smooth Functions Using Deep ReLU Neural Networks. Neural Networks 108 296–330. 10.1016/j.neunet.2018.08.019
  * [50] [author] Radford, AlecA., Wu, JeffreyJ., Child, RewonR., Luan, DavidD., Amodei, DarioD., Sutskever, IlyaI. et al. (2019). Language models are unsupervised multitask learners. OpenAI blog 1 9\.
  * [51] [author] Rakhlin, AlexanderA. and Zhai, XiyuX. (2019). Consistency of Interpolation with Laplace Kernels Is a High-Dimensional Phenomenon. In Proceedings of the Thirty-Second Conference on Learning Theory 2595–2623. PMLR.
  * [52] [author] Raskutti, GarveshG., Wainwright, Martin JM. J. and Yu, BinB. (2014). Early stopping and non-parametric regression: an optimal data-dependent stopping rule. The Journal of Machine Learning Research 15 335–366.
  * [53] [author] Sanyal, AmartyaA., Dokania, Puneet KP. K., Kanade, VarunV. and Torr, Philip HSP. H. (2020). How benign is benign overfitting? arXiv preprint arXiv:2007.04028.
  * [54] [author] Schmidt-Hieber, JohannesJ. (2020). Nonparametric Regression Using Deep Neural Networks with ReLU Activation Function. The Annals of Statistics 48 1875–1897. 10.1214/19-AOS1875
  * [55] [author] Simon, BarryB. (2015). Operator Theory. American Mathematical Society, Providence, Rhode Island. 10.1090/simon/004
  * [56] [author] Simon, James BJ. B., Dickens, MadelineM. and DeWeese, Michael RM. R. (2021). Neural tangent kernel eigenvalues accurately predict generalization. arXiv preprint arXiv:2110.03922.
  * [57] [author] Sirignano, JustinJ. and Spiliopoulos, KonstantinosK. (2022). Mean field analysis of deep neural networks. Mathematics of Operations Research 47 120–152.
  * [58] [author] Suh, NamjoonN., Ko, HyunoukH. and Huo, XiaomingX. (2022). A Non-parametric Regression Viewpoint: Generalization of Overparametrized Deep ReLU Network under Noisy Observations. In International Conference on Learning Representations.
  * [59] [author] Suzuki, TaijiT. (2019). Adaptivity of Deep ReLU Network for Learning in Besov and Mixed Smooth Besov Spaces: Optimal Rate and Curse of Dimensionality. In International Conference on Learning Representations.
  * [60] [author] Suzuki, TaijiT. and Nitanda, AtsushiA. (2021). Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. Advances in Neural Information Processing Systems 34\.
  * [61] [author] Vapnik, Vladimir N.V. N. (1995). The Nature of Statistical Learning Theory. Springer, New York, NY. 10.1007/978-1-4757-2440-0
  * [62] [author] Vershynin, RomanR. (2018). High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press.
  * [63] [author] Vyas, NikhilN., Bansal, YaminiY. and Nakkiran, PreetumP. (2022). Limitations of the NTK for Understanding Generalization in Deep Learning. arXiv:2206.10012. 10.48550/arXiv.2206.10012
  * [64] [author] Walter, WolfgangW. (1970). Differential and Integral Inequalities. Springer, Berlin, Heidelberg. 10.1007/978-3-642-86405-6
  * [65] [author] Yao, YuanY., Rosasco, LorenzoL. and Caponnetto, AndreaA. (2007). On early stopping in gradient descent learning. Constructive Approximation 26 289–315.
  * [66] [author] Yarotsky, DmitryD. (2017). Error Bounds for Approximations with Deep ReLU Networks. Neural Networks 94 103–114. 10.1016/j.neunet.2017.07.002
  * [67] [author] Zhang, ChiyuanC., Bengio, SamyS., Hardt, MoritzM., Recht, BenjaminB. and Vinyals, OriolO. (2016). Understanding Deep Learning Requires Rethinking Generalization. In International Conference on Learning Representations. 10.48550/arxiv.1611.03530
  * [68] [author] Zhang, XiaoX., Yu, YaodongY., Wang, LingxiaoL. and Gu, QuanquanQ. (2019). Learning one-hidden-layer relu networks via gradient descent. In The 22nd international conference on artificial intelligence and statistics 1524–1534. PMLR.
  * [69] [author] Zhong, KaiK., Song, ZhaoZ., Jain, PrateekP., Bartlett, Peter LP. L. and Dhillon, Inderjit SI. S. (2017). Recovery guarantees for one-hidden-layer neural networks. In International conference on machine learning 4140–4149. PMLR.

##  Appendix C Proof of Section 3

We first prove Proposition 3.3 and then prove Proposition 3.2. For brevity,
denote the pre-activation value and the activation pattern for the $r$-th
neuron of the hidden layer of the neural network with parameters
$\boldsymbol{\theta}$ by
$h_{\boldsymbol{\theta},r}(\boldsymbol{x})=\langle\boldsymbol{w}_{r},\boldsymbol{x}\rangle+b_{r}$
and
$\boldsymbol{1}_{\boldsymbol{\theta},r}(\boldsymbol{x})=\boldsymbol{1}_{\\{h_{\boldsymbol{\theta},r}(\boldsymbol{x})\geq
0\\}}$ respectively. For simplicity, we consider the neural network to have
$2m$ neurons.

###  C.1 Proof of Proposition 3.3

We defer the proof to the end of Section C.1. To start with, Lemma C.1, Lemma
C.2 and Lemma C.3 are the building blocks to prove Proposition 3.3, since in
these lemmas we will show the events we need to condition on hold with
probability converging to one as $m\to\infty$.

Lemma C.1 controls the scale of the parameters of the neural network at
initialization.

######  Lemma C.1.

Define the event

$\mathcal{B}=\left\\{\omega\mid|a_{r}(0)|,|\boldsymbol{w}_{r,(j)}(0)|,|b_{r}(0)|\leq
R_{B},r\in[2m],j\in[d]\right\\},\text{~{}where~{}}R_{B}=\sqrt{3\log m}.$

Conditioning on the event $\mathcal{B}$, we have
$|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})|\leq(dB+1)R_{B}$ for all
$r\in[2m]$ and $\boldsymbol{x}\in\mathcal{X}$. The event $\mathcal{B}$ holds
with high probability, i.e.,
$\mathbf{P}_{\boldsymbol{\theta}(0)}(\mathcal{B})\geq 1-P_{\mathcal{B}}(m)$,
where $P_{\mathcal{B}}(m)=\frac{2(d+2)}{\sqrt{2\pi}}m^{-1/2}$.

###### Proof.

Under our special initialization setting where $a_{r}(0)=-a_{r+m}(0)$,
$\boldsymbol{w}_{r,(j)}(0)=\boldsymbol{w}_{r+m,(j)}(0)$,
$b_{r}(0)=b_{r+m}(0)\sim\mathcal{N}(0,1)$ for $r\in[m]$, the total number of
the elements in $\mathcal{B}$ that need to be controlled is $(d+2)m$. For
$Z\sim\mathcal{N}(0,1)$, classical Gaussian tail bound gives

$\mathbf{P}(|Z|\geq
R_{B})\leq\frac{2e^{-R_{B}^{2}/2}}{\sqrt{2\pi}R_{B}}\leq\frac{2e^{-R_{B}^{2}/2}}{\sqrt{2\pi}}=\frac{2}{\sqrt{2\pi}}m^{-3/2}.$

Then $\mathbf{P}_{\boldsymbol{\theta}(0)}(\mathcal{B})\geq
1-\frac{2(d+2)}{\sqrt{2\pi}}m^{-1/2}$ by the union bound. Conditioning on
$\mathcal{B}$, we have

$|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})|=|\langle\boldsymbol{w}_{r}(0),\boldsymbol{x}\rangle+b_{r}(0)|\leq\|\boldsymbol{w}_{r}(0)\|_{2}\|\boldsymbol{x}\|_{2}+|b_{r}(0)|\leq(dB+1)R_{B}.$

∎

Our main contribution is the uniform convergence of kernel which relies on the
analysis of the continuity of $K_{\boldsymbol{\theta}(0)}^{m}$ and $K_{d}$ and
a method that is similar to the epsilon-net argument. On each dimension, we
place $\lfloor m^{\beta}\rfloor$ points with distance

$\epsilon=2B/\lfloor m^{\beta}\rfloor$

in $[-B,B]$ for some $\beta\in(0,1]$. Denote the collection
$\mathcal{N}_{\epsilon}$ so that $|\mathcal{N}_{\epsilon}|=\lfloor
m^{\beta}\rfloor^{d}$. The idea is to use $\mathcal{N}_{\epsilon}$ to
discretize the domain $\mathcal{X}$ and then use classical concentration
inequality on points in $\mathcal{N}_{\epsilon}$, which makes the probability
of the complement of the events decaying exponentially fast with $m$. Then
with the continuity of $K_{\boldsymbol{\theta}(0)}^{m}$ and $K_{d}$, the
events hold over $\mathcal{X}$ with high probability.

Lemma C.2 shows the pre-activation values of most neurons are large, which
hints that the activation pattern for these neurons is likely to stay
unchanged during training since a large pre-activation value requires the
parameters to travel a long way from the initialization to change the sign.
This is crucial to prove that the training wide neural networks fall into the
lazy regime where the parameters stay close to the initialization during
training.

######  Lemma C.2.

Define the events

$\mathcal{R}(\mathcal{N}_{\epsilon})=\left\\{\omega~{}\middle|~{}|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{z})|\leq
2(dB+1)R\mbox{~{}holds for at most~{}}2\lfloor
m^{\gamma}\rfloor\mbox{~{}of~{}}r\in[2m],\forall\boldsymbol{z}\in\mathcal{N}_{\epsilon}\right\\}$

and

$\mathcal{R}=\left\\{\omega~{}\middle|~{}|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})|\leq(dB+1)R\mbox{~{}holds
for at most~{}}2\lfloor
m^{\gamma}\rfloor\mbox{~{}of~{}}r\in[2m],\forall\boldsymbol{x}\in[-B,B]^{d}\right\\},$

where $R=\frac{\sqrt{2\pi}}{4(dB+1)}m^{-\alpha}$ for some $\alpha\in(0,\beta)$
and $\gamma>\max\\{1-\alpha,\delta\\}$ with $\delta>1/2$. If $m$ is
sufficiently large, then
$\mathcal{R}\supseteq\mathcal{R}(\mathcal{N}_{\epsilon})$ and the event
$\mathcal{R}$ holds with high probability, i.e.,
$\mathbf{P}_{\boldsymbol{\theta}(0)}\left(\mathcal{R}\right)\geq\mathbf{P}_{\boldsymbol{\theta}(0)}\left(\mathcal{R}(\mathcal{N}_{\epsilon})\right)\geq
1-P_{\mathcal{R}}(m)$, where
$P_{\mathcal{R}}(m)=m^{d\beta}e^{-2m^{2\delta-1}}$.

###### Proof.

Due to our special initialization setting, we only need to consider $r\in[m]$
since
$|h_{\boldsymbol{\theta}(0),r+m}(\boldsymbol{z})|=|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{z})|$
for $r\in[m]$. For every $\boldsymbol{z}\in\mathcal{N}_{\epsilon}$, let
$T_{r}=\boldsymbol{1}_{\\{|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{z})|\leq
2(dB+1)R\\}}$ with mean

$p=\mathbf{E}_{\boldsymbol{\theta}(0)}T_{r}=\mathbf{P}_{\boldsymbol{\theta}(0)}(|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{z})|\leq
2(dB+1)R)\leq\frac{2}{\sqrt{2\pi}}\frac{2(dB+1)R}{\sqrt{\|\boldsymbol{z}\|_{2}^{2}+1}}\leq
m^{-\alpha},$

where the second inequality holds due to
$h_{\boldsymbol{\theta}(0),r}(\boldsymbol{z})\sim\mathcal{N}(0,\lVert\boldsymbol{z}\rVert_{2}^{2}+1)$
and the density function of a standard Gaussian is upper bounded by
$1/\sqrt{2\pi}$. By Hoeffeding’s inequality (see Theorem 2.8 in [14]), for all
$\delta>0$, we have
$\mathbf{P}_{\boldsymbol{\theta}(0)}\left(\sum_{r\in[m]}T_{r}\geq
mp+m^{\delta}\right)\leq e^{-2m^{2\delta-1}}$. Now we have

$\displaystyle\mathbf{P}_{\boldsymbol{\theta}(0)}\left(|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{z})\leq
2(dB+1)R\mbox{~{}holds for at most~{}}\lfloor
m^{\gamma}\rfloor\mbox{~{}of~{}}r\in[m]\right)$ $\displaystyle=$
$\displaystyle\mathbf{P}_{\boldsymbol{\theta}(0)}\left(\sum_{r\in[m]}T_{r}\leq\lfloor
m^{\gamma}\rfloor\right)=1-\mathbf{P}_{\boldsymbol{\theta}(0)}\left(\sum_{r\in[m]}T_{r}>\lfloor
m^{\gamma}\rfloor\right)$ $\displaystyle\geq$ $\displaystyle
1-\mathbf{P}_{\boldsymbol{\theta}(0)}\left(\sum_{r\in[m]}T_{r}\geq
mp+m^{\delta}\right)\geq 1-e^{-2m^{2\delta-1}},$

where the first inequality holds when $m$ is large enough such that
$mp+m^{\delta}\leq m^{1-\alpha}+m^{\delta}\leq\lfloor m^{\gamma}\rfloor$.
Hence we have
$\mathbf{P}_{\boldsymbol{\theta}(0)}(\mathcal{R}(\mathcal{N}_{\epsilon}))\geq
1-\lvert\mathcal{N}_{\epsilon}\rvert e^{-2m^{2\delta-1}}$ simply by the union
bound. For every $\boldsymbol{x}$, we choose
$\boldsymbol{z}\in\mathcal{N}_{\epsilon}$ such that
$\|\boldsymbol{x}-\boldsymbol{z}\|_{2}\leq\sqrt{d}\epsilon$, so

$\displaystyle\lvert h_{\boldsymbol{\theta}(0),r}(\boldsymbol{z})\rvert$
$\displaystyle=\lvert
h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})+\langle\boldsymbol{w}_{r}(0),\boldsymbol{z}-\boldsymbol{x}\rangle\rvert$
$\displaystyle\leq\lvert
h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})\rvert+\|\boldsymbol{w}_{r}(0)\|_{2}\|\boldsymbol{z}-\boldsymbol{x}\|_{2}\leq\lvert
h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})\rvert+dR_{B}\epsilon.$

Thus
$|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})|\geq|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{z})|-dR_{B}\epsilon>(dB+1)R$,
where the last inequality holds when $m$ is large enough such that
$dR_{B}\epsilon<(dB+1)R$. ∎

It is intuitive that the point-wise convergence of
$K_{\boldsymbol{\theta}(0)}^{m}-K_{d}$ holds simply by the law of large
numbers. The result from Lemma C.3 shows this convergence is uniform for
points in the collection $\mathcal{N}_{\epsilon}$.

######  Lemma C.3.

Define the event

$\mathcal{C}=\left\\{\omega~{}\middle|~{}\sup_{\boldsymbol{z},\boldsymbol{z}^{\prime}\in\mathcal{N}_{\epsilon}}|K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{z},\boldsymbol{z}^{\prime})-K_{d}(\boldsymbol{z},\boldsymbol{z}^{\prime})|\leq
C_{1}\sqrt{\frac{\log m}{m}}\right\\},$

where $C_{1}>0$ is a constant depending on $d,B,\beta$. If $m$ is sufficiently
large, then the event $\mathcal{C}$ holds with high probability, i.e.,
$\mathbf{P}_{\boldsymbol{\theta}(0)}\left(\mathcal{C}\right)\geq
1-P_{\mathcal{C}}(m)$, where $P_{\mathcal{C}}(m)=4m^{-d\beta}$.

Before we give the proof of Lemma C.3, we need to dive into details of the
kernel of the neural network from here to analyze further, so we introduce
more notations. Given the parameters $\boldsymbol{\theta}$ of the neural
network, let
$H_{\boldsymbol{\theta},r}(\boldsymbol{x},\boldsymbol{x}^{\prime})=\left(\langle\boldsymbol{x},\boldsymbol{x}^{\prime}\rangle+1\right)a_{r}^{2}\boldsymbol{1}_{\boldsymbol{\theta},r}(\boldsymbol{x})\boldsymbol{1}_{\boldsymbol{\theta},r}(\boldsymbol{x}^{\prime})$,
$G_{\boldsymbol{\theta},r}(\boldsymbol{x},\boldsymbol{x}^{\prime})=\sigma(h_{\boldsymbol{\theta},r}(\boldsymbol{x}))\sigma(h_{\boldsymbol{\theta},r}(\boldsymbol{x}^{\prime}))$
be the contribution to the kernel from the $r$-th neuron at the first and
second layer respectively. Then we decompose

$K_{\boldsymbol{\theta}}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})=\langle\nabla_{\boldsymbol{\theta}}f_{\boldsymbol{\theta}}^{m}(\boldsymbol{x}),\nabla_{\boldsymbol{\theta}}f_{\boldsymbol{\theta}}^{m}(\boldsymbol{x}^{\prime})\rangle=1+H_{\boldsymbol{\theta}}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})+G_{\boldsymbol{\theta}}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime}),$

where

$H_{\boldsymbol{\theta}}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})=\frac{1}{m}\sum_{r\in[2m]}H_{\boldsymbol{\theta},r}(\boldsymbol{x},\boldsymbol{x}^{\prime}),G_{\boldsymbol{\theta}}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})=\frac{1}{m}\sum_{r\in[2m]}G_{\boldsymbol{\theta},r}(\boldsymbol{x},\boldsymbol{x}^{\prime}).$

A similar decomposition for the NTK is

$K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})=1+H(\boldsymbol{x},\boldsymbol{x}^{\prime})+G(\boldsymbol{x},\boldsymbol{x}^{\prime}),$

where
$H(\boldsymbol{x},\boldsymbol{x}^{\prime})=\mathbf{E}_{\boldsymbol{\theta}(0)}H_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})$
and
$G(\boldsymbol{x},\boldsymbol{x}^{\prime})=\mathbf{E}_{\boldsymbol{\theta}(0)}G_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})$.
Thanks to the decomposition, we can simply analyze each part of the kernel and
then use the triangle inequality to apply to the whole kernel.

###### Proof of Lemma C.3.

Notice that
$H_{\boldsymbol{\theta}(0),r}(\boldsymbol{z},\boldsymbol{z}^{\prime})$ and
$G_{\boldsymbol{\theta}(0),r}(\boldsymbol{z},\boldsymbol{z}^{\prime})$ are
both sub-exponential and their sub-exponential norm is bounded by a constant
$c^{\prime}$ depending on $d,B$. Then by Bernstein’s inequality(see Theorem
2.8.1 in [62]), for every $c>0$,

$\displaystyle\mathbf{P}_{\boldsymbol{\theta}(0)}\left(|H_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{z},\boldsymbol{z}^{\prime})-H(\boldsymbol{z},\boldsymbol{z}^{\prime})|\geq
c\sqrt{\frac{\log m}{m}}\right)\leq$ $\displaystyle
2e^{-c_{0}\min\\{\frac{c^{2}}{c^{\prime 2}}\log
m,\frac{c}{c^{\prime}}\sqrt{m\log m}\\}}$ $\displaystyle=$ $\displaystyle
2m^{-c_{0}c^{2}/c^{\prime 2}},$

where $c_{0}$ is an absolute constant and the equality holds when $m$ is large
enough such that $\frac{c^{2}}{c^{\prime 2}}\log
m\leq\frac{c}{c^{\prime}}\sqrt{m\log m}$. Likewise, we have the same
inequality for $G_{\boldsymbol{\theta}(0)}^{m}$, so that

$\displaystyle\mathbf{P}_{\boldsymbol{\theta}(0)}\left(\sup_{\boldsymbol{z},\boldsymbol{z}^{\prime}\in\mathcal{N}_{\epsilon}}\lvert
K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{z},\boldsymbol{z}^{\prime})-K_{d}(\boldsymbol{z},\boldsymbol{z}^{\prime})\rvert\leq
2c\sqrt{\frac{\log m}{m}}\right)\geq$ $\displaystyle
1-4\binom{|\mathcal{N}_{\epsilon}|}{2}m^{-c_{0}c^{2}/c^{\prime 2}}$
$\displaystyle\geq$ $\displaystyle 1-4m^{-(c_{0}c^{2}/c^{\prime 2}-2d\beta)}$
$\displaystyle=$ $\displaystyle 1-4m^{-d\beta}$

simply by the triangle inequality and the union bound, where we set
$c=\sqrt{3c^{\prime 2}d\beta/c_{0}}$ in the last equality. ∎

For initialization that lies in the intersection of the events, i.e.,
$\mathcal{B}\cap\mathcal{R}\cap{\mathcal{C}}$, Lemma C.4 and Lemma C.5 shows
how the width $m$ control the convergence of kernel at the initialization and
during training. The proof of Lemma C.4 and Lemma C.5 could be found in
Section C.1.1 and Section C.1.2 respectively.

######  Lemma C.4.

Conditioning on the event $\mathcal{B}\cap\mathcal{R}\cap\mathcal{C}$, if we
set $\gamma>1-\beta/4$ and $m$ is sufficiently large, then

$\sup_{\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathcal{X}}|K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})|\leq
C_{2}m^{-(1-\gamma)}\log m,$

where $C_{2}>0$ is a constant depending on $d,B$.

######  Lemma C.5.

Conditioning on the event $\mathcal{B}\cap\mathcal{R}\cap\mathcal{C}$, if we
set $\alpha<1/2$ and $m$ is sufficiently large, then

$\sup_{t\geq
0}\sup_{\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathcal{X}}|K_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})|\leq
C_{3}m^{-(1-\gamma)}\log m,$

where $C_{3}>0$ is constant depending on $d,B$.

###### Proof of Proposition 3.3.

Consider the initialization
$\omega\in\mathcal{B}\cap\mathcal{R}\cap\mathcal{C}$. Then for all
$\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathcal{X}$, we have

$\displaystyle|K_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})|$
$\displaystyle\leq|K_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})|+|K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})|$
$\displaystyle\leq(C_{2}+C_{3})m^{-(1-\gamma)}\log m,$

where the last inequality follows from Lemma C.4 and Lemma C.5. With Lemma
C.1, Lemma C.2 and Lemma C.3, we show that

$\displaystyle\mathbf{P}_{\boldsymbol{\theta}(0)}\left(\sup_{\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathcal{X}}|K_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})|\leq(C_{2}+C_{3})m^{-(1-\gamma)}\log
m\right)$ $\displaystyle\geq$ $\displaystyle
1-P_{\mathcal{B}}(m)-P_{\mathcal{R}}(m)-P_{\mathcal{C}}(m).$

∎

####  C.1.1 Proof of Lemma C.4

Conditioning on $\mathcal{B}\cap\mathcal{R}\cap\mathcal{C}$, for all
$\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathcal{X}$, decomposition of
$\lvert
K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})\rvert$
by the triangle inequality gives

$\displaystyle|K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})|\leq$
$\displaystyle|K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{z},\boldsymbol{z}^{\prime})|+|K_{d}(\boldsymbol{z},\boldsymbol{z}^{\prime})-K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})|$
$\displaystyle+|K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{z},\boldsymbol{z}^{\prime})-K_{d}(\boldsymbol{z},\boldsymbol{z}^{\prime})|$
$\displaystyle\leq$ $\displaystyle 2C_{4}m^{-(1-\gamma)}\log
m+2C_{5}(\sqrt{d}\epsilon)^{1/4}+C_{1}\sqrt{\frac{\log m}{m}}$

by Lemma C.7, Lemma C.8 and Lemma C.3 when $m$ is sufficiently large.

##### The continuity of $K_{\boldsymbol{\theta}(0)}^{m}$

Using the triangle inequality again yields

$|K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{z},\boldsymbol{z}^{\prime})|\leq|K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{z}^{\prime})|+|K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{z}^{\prime})-K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{z},\boldsymbol{z}^{\prime})|.$

We here illustrate how to control the first term, as the control of the second
term follows from the symmetry of
$K_{\boldsymbol{\theta}(0)}^{m}(\cdot,\cdot)$.

######  Lemma C.6.

For all $\boldsymbol{x}\in[-B,B]^{d}$ and
$\boldsymbol{z}\in\mathcal{N}_{\epsilon}$ such that
$\|\boldsymbol{x}-\boldsymbol{z}\|_{2}\leq\sqrt{d}\epsilon$, conditioning on
$\mathcal{B}\cap\mathcal{R}$, if $m$ is sufficiently large, then
$|I(\boldsymbol{x},\boldsymbol{z})|\geq 2(m-\lfloor m^{\gamma}\rfloor)$, where
$I(\boldsymbol{x},\boldsymbol{z})=\\{r\mid\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})=\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{z})\\}$
is the index set of neurons on which the activation pattern for
$\boldsymbol{x}$ and $\boldsymbol{z}$ is the same at $\boldsymbol{\theta}(0)$.

###### Proof.

Notice that

$|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})-h_{\boldsymbol{\theta}(0),r}(\boldsymbol{z})|=|\langle\boldsymbol{w}_{r}(0),\boldsymbol{x}-\boldsymbol{z}\rangle|\leq\|\boldsymbol{w}_{r}(0)\|_{2}\|\boldsymbol{x}-\boldsymbol{z}\|_{2}\leq
dR_{B}\epsilon.$

For $r\in
I_{\text{in}}(\boldsymbol{x})=\\{r\mid|h_{\boldsymbol{\theta}(0)}(\boldsymbol{x})|>(dB+1)R\\}$,
if $m$ is large enough such that $dR_{B}\epsilon\leq(dB+1)R$, we have

$|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})-h_{\boldsymbol{\theta}(0),r}(\boldsymbol{z})|<|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})|,$

which implies
$\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})=\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{z})$,
thus
$|I(\boldsymbol{x},\boldsymbol{z})|\geq|I_{\text{in}}(\boldsymbol{x})|\geq
2(m-\lfloor m^{\gamma}\rfloor)$. ∎

######  Lemma C.7.

For all $\boldsymbol{x},\boldsymbol{x}^{\prime}\in[-B,B]^{d}$ and
$\boldsymbol{z}^{\prime}\in\mathcal{N}_{\epsilon}$ such that
$\|\boldsymbol{x}^{\prime}-\boldsymbol{z}^{\prime}\|_{2}\leq\sqrt{d}\epsilon$,
conditioning on the event $\mathcal{B}\cap\mathcal{R}$, if we set
$\gamma>1-\beta$ and $m$ is sufficiently large,

$|K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{z}^{\prime})|\leq
C_{4}m^{-(1-\gamma)}\log m,$

where $C_{4}$ is a constant depending on $d,B$.

###### Proof.

For simplicity, let $I=I(\boldsymbol{x}^{\prime},\boldsymbol{z}^{\prime})$.
Then

$\displaystyle|H_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-H_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{z}^{\prime})|$
$\displaystyle\leq$
$\displaystyle\left|\langle\boldsymbol{x},\boldsymbol{x}^{\prime}-\boldsymbol{z}^{\prime}\rangle\frac{1}{m}\sum_{r\in[2m]}a_{r}^{2}(0)\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime})\right|$
$\displaystyle+\left|(\langle\boldsymbol{x},\boldsymbol{z}^{\prime}\rangle+1)\frac{1}{m}\sum_{r\in[2m]}a_{r}^{2}(0)\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})(\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime})-\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{z}^{\prime}))\right|$
$\displaystyle\leq$ $\displaystyle dB\epsilon\cdot
2R_{B}^{2}+\frac{(dB^{2}+1)R_{B}^{2}}{m}\sum_{r\in I}\sum_{r\in
I^{\mathsf{c}}}\lvert\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime})-\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{z}^{\prime})\rvert$
$\displaystyle\leq$ $\displaystyle
2dBR_{B}^{2}\epsilon+(dB^{2}+1)R_{B}^{2}\frac{2\lfloor m^{\gamma}\rfloor}{m}$
$\displaystyle\leq$ $\displaystyle 4(dB^{2}+1)R_{B}^{2}m^{-(1-\gamma)},$

where the first inequality holds by plugging in
$\langle\boldsymbol{x},\boldsymbol{z}^{\prime}\rangle\frac{1}{m}\sum_{r\in[2m]}a_{r}^{2}(0)\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime})$
and using the triangle inequality, the third inequality follows from Lemma
C.6, and the last inequality holds if $m$ is large enough such that
$2dBR_{B}^{2}\epsilon\leq 2(dB^{2}+1)R_{B}^{2}\frac{\lfloor
m^{\gamma}\rfloor}{m}$. Similarly,

$\displaystyle|G_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-G_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{z}^{\prime})|$
$\displaystyle\leq$
$\displaystyle\left|\langle\boldsymbol{x},\boldsymbol{x}^{\prime}-\boldsymbol{z}^{\prime}\rangle\frac{1}{m}\sum_{r\in[2m]}\sigma(h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}))\sigma(h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime}))\right|$
$\displaystyle+\left|\langle\boldsymbol{x},\boldsymbol{z}^{\prime}\rangle\frac{1}{m}\sum_{r\in[2m]}\sigma(h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}))(\sigma(h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime}))-\sigma(h_{\boldsymbol{\theta}(0),r}(\boldsymbol{z}^{\prime})))\right|$
$\displaystyle\leq$ $\displaystyle dB\epsilon\cdot 2(dB+1)^{2}R_{B}^{2}$
$\displaystyle+\frac{1}{m}\sum_{r\in I}\sum_{r\in
I^{\mathsf{c}}}|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})||\sigma(h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime}))-\sigma(h_{\boldsymbol{\theta}(0),r}(\boldsymbol{z}^{\prime}))|$
$\displaystyle\leq$ $\displaystyle 2dB(dB+1)^{2}R_{B}^{2}\epsilon$
$\displaystyle+\frac{1}{m}\sum_{r\in
I}|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})||h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime})-h_{\boldsymbol{\theta}(0),r}(\boldsymbol{z}^{\prime})|$
$\displaystyle+\frac{1}{m}\sum_{r\in
I^{\mathsf{c}}}|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})|\max\\{|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime})|,|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{z}^{\prime})|\\}$
$\displaystyle\leq$ $\displaystyle
2dB(dB+1)^{2}R_{B}^{2}\epsilon+2(dB+1)R_{B}\cdot
dR_{B}\epsilon+(dB+1)^{2}R_{B}^{2}\frac{2\lfloor m^{\gamma}\rfloor}{m}$
$\displaystyle\leq$ $\displaystyle 6(dB+1)^{2}R_{B}^{2}m^{-(1-\gamma)},$

where the first inequality holds by plugging in
$\langle\boldsymbol{x},\boldsymbol{z}^{\prime}\rangle\frac{1}{m}\sum_{r\in[2m]}\sigma(h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}))\sigma(h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime}))$
and using the triangle inequality, the third and the last but second
inequality follows from Lemma C.6, the last inequality holds if $m$ is large
enough such that

$\max\\{2dB(dB+1)^{2}R_{B}^{2}\epsilon,2d(dB+1)R_{B}^{2}\epsilon\\}\leq
2(dB+1)^{2}R_{B}^{2}\frac{\lfloor m^{\gamma}\rfloor}{m}.$

∎

##### The continuity of $K_{d}$

The triangle inequality shows

$\lvert
K_{d}(\boldsymbol{z},\boldsymbol{z}^{\prime})-K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})\rvert\leq\lvert
K_{d}(\boldsymbol{z},\boldsymbol{z}^{\prime})-K_{d}(\boldsymbol{z},\boldsymbol{x}^{\prime})\rvert+\lvert
K_{d}(\boldsymbol{z},\boldsymbol{x}^{\prime})-K_{d}(\boldsymbol{x},\boldsymbol{x}^{\prime})\rvert.$

Similarly, we only need to show the control of the first term, since it is the
same for the second term by the symmetry of $K_{d}(\cdot,\cdot)$.

######  Lemma C.8.

For every
$\boldsymbol{x}^{\prime},\boldsymbol{z},\boldsymbol{z}^{\prime}\in[-B,B]^{d}$
and $\epsilon_{0}>0$, if
$\|\boldsymbol{x}^{\prime}-\boldsymbol{z}^{\prime}\|_{2}\leq\epsilon_{0}$,
then

$|K_{d}(\boldsymbol{z},\boldsymbol{z}^{\prime})-K_{d}(\boldsymbol{z},\boldsymbol{x}^{\prime})|\leq
C_{5}\max\\{\epsilon_{0},\epsilon_{0}^{1/4}\\},$

where $C_{5}$ is a constant depending on $d,B$.

###### Proof.

Recall the expression of NTK $K_{d}$, we have

$\displaystyle|K_{d}(\boldsymbol{z},\boldsymbol{z}^{\prime})-K_{d}(\boldsymbol{z},\boldsymbol{x}^{\prime})|$
$\displaystyle\leq$
$\displaystyle\underbrace{\frac{2}{\pi}|(\pi-\psi(\boldsymbol{z},\boldsymbol{z}^{\prime}))(\langle\boldsymbol{z},\boldsymbol{z}^{\prime}\rangle+1)-(\pi-\psi(\boldsymbol{z},\boldsymbol{x}^{\prime}))(\langle\boldsymbol{z},\boldsymbol{x}^{\prime}\rangle+1)|}_{\text{I}}$
$\displaystyle+\underbrace{\frac{1}{\pi}\left|\sqrt{\|\boldsymbol{z}-\boldsymbol{z}^{\prime}\|_{2}^{2}-\|\boldsymbol{z}\|_{2}^{2}\|\boldsymbol{z}^{\prime}\|_{2}^{2}-\langle\boldsymbol{z},\boldsymbol{z}^{\prime}\rangle^{2}}-\sqrt{\|\boldsymbol{z}-\boldsymbol{x}^{\prime}\|_{2}^{2}-\|\boldsymbol{z}\|_{2}^{2}\|\boldsymbol{x}^{\prime}\|_{2}^{2}-\langle\boldsymbol{z},\boldsymbol{x}^{\prime}\rangle^{2}}\right|}_{\text{II}}.$

For the first term I, plugging in
$(\pi-\psi(\boldsymbol{z},\boldsymbol{z}^{\prime}))(\langle\boldsymbol{z},\boldsymbol{x}^{\prime}\rangle+1)$
and using the triangle inequality yields

$\displaystyle\text{I}\leq$
$\displaystyle\frac{2}{\pi}\left((\pi-\psi(\boldsymbol{z},\boldsymbol{z}^{\prime}))|\langle\boldsymbol{z},\boldsymbol{z}^{\prime}-\boldsymbol{x}^{\prime}\rangle|+|\langle\boldsymbol{z},\boldsymbol{x}^{\prime}\rangle+1||\psi(\boldsymbol{z},\boldsymbol{z}^{\prime})-\psi(\boldsymbol{z},\boldsymbol{x}^{\prime})|\right)$
$\displaystyle\leq$
$\displaystyle\frac{2}{\pi}\left(2\pi\cdot\sqrt{d}B\epsilon_{0}+(dB^{2}+1)|\psi(\boldsymbol{z},\boldsymbol{z}^{\prime})-\psi(\boldsymbol{z},\boldsymbol{x}^{\prime})|\right)$
$\displaystyle\leq$
$\displaystyle\frac{2}{\pi}\left(2\pi\sqrt{d}B\epsilon_{0}+(dB^{2}+1)C_{6}\max\\{\sqrt{\epsilon_{0}},\epsilon_{0}^{1/4}\\}\right),$

where the last inequality holds due to Lemma C.9 where $C_{6}$ is a constant
depending on $d,B$. For the second term II,

II
$\displaystyle\leq\sqrt{|(\|\boldsymbol{z}-\boldsymbol{z}^{\prime}\|_{2}^{2}-\|\boldsymbol{z}-\boldsymbol{x}^{\prime}\|_{2}^{2})+(\|\boldsymbol{z}\|_{2}^{2}\|\boldsymbol{z}^{\prime}\|_{2}^{2}-\|\boldsymbol{z}\|_{2}^{2}\|\boldsymbol{x}^{\prime}\|_{2}^{2})-(\langle\boldsymbol{z},\boldsymbol{z}^{\prime}\rangle^{2}-\langle\boldsymbol{z},\boldsymbol{x}^{\prime}\rangle^{2})|}$
$\displaystyle=\sqrt{|(2\langle\boldsymbol{z},\boldsymbol{x}^{\prime}-\boldsymbol{z}^{\prime}\rangle+\|\boldsymbol{z}^{\prime}\|_{2}^{2}-\|\boldsymbol{x}^{\prime}\|_{2}^{2})+\|\boldsymbol{z}\|_{2}^{2}(\|\boldsymbol{z}^{\prime}\|_{2}^{2}-\|\boldsymbol{x}^{\prime}\|_{2}^{2})-\langle\boldsymbol{z},\boldsymbol{z}^{\prime}+\boldsymbol{x}^{\prime}\rangle\langle\boldsymbol{z},\boldsymbol{z}^{\prime}-\boldsymbol{x}^{\prime}\rangle|}$
$\displaystyle\leq\sqrt{4\sqrt{d}B\epsilon_{0}+2(\sqrt{d}B)^{3}\epsilon_{0}+2(\sqrt{d}B)^{3}\epsilon_{0}}=2\sqrt{(\sqrt{d}B+d^{3/2}B^{3})}\sqrt{\epsilon_{0}},$

where the first inequality holds since
$|\sqrt{x}-\sqrt{x^{\prime}}|\leq\sqrt{|x-x^{\prime}|}$ for all
$x,x^{\prime}>0$ and the last inequality holds by the Cauchy-Schwartz
inequality and the fact that
$\boldsymbol{x}^{\prime},\boldsymbol{z},\boldsymbol{z}^{\prime}\in[-B,B]^{d}$
and $\|\boldsymbol{x}^{\prime}-\boldsymbol{z}^{\prime}\|_{2}\leq\epsilon_{0}$.
∎

######  Lemma C.9.

For every
$\boldsymbol{x}^{\prime},\boldsymbol{z},\boldsymbol{z}^{\prime}\in[-B,B]^{d}$
and $\epsilon_{0}>0$, if
$\|\boldsymbol{x}^{\prime}-\boldsymbol{z}^{\prime}\|_{2}\leq\epsilon_{0}$,
then

$|\psi(\boldsymbol{z},\boldsymbol{z}^{\prime})-\psi(\boldsymbol{z},\boldsymbol{x}^{\prime})|\leq
C_{6}\max\\{\sqrt{\epsilon_{0}},\epsilon_{0}^{1/4}\\},$ (58)

where $C_{6}$ is a constant depending on $d,B$.

###### Proof.

Let
$\Delta=|\cos(\psi(\boldsymbol{z},\boldsymbol{z}^{\prime}))-\cos(\psi(\boldsymbol{z},\boldsymbol{x}^{\prime}))|$.
Then plug in
$\frac{\langle\boldsymbol{z},\boldsymbol{x}^{\prime}\rangle+1}{\sqrt{(\|\boldsymbol{z}\|_{2}^{2}+1)(\|\boldsymbol{z}^{\prime}\|_{2}^{2}+1)}}$
and the triangle inequality concludes

$\displaystyle\Delta\leq$
$\displaystyle\left|\frac{\langle\boldsymbol{z},\boldsymbol{z}^{\prime}\rangle+1}{\sqrt{(\|\boldsymbol{z}\|_{2}^{2}+1)(\|\boldsymbol{z}^{\prime}\|_{2}^{2}+1)}}-\frac{\langle\boldsymbol{z},\boldsymbol{x}^{\prime}\rangle+1}{\sqrt{(\|\boldsymbol{z}\|_{2}^{2}+1)(\|\boldsymbol{z}^{\prime}\|_{2}^{2}+1)}}\right|$
$\displaystyle+\left|\frac{\langle\boldsymbol{z},\boldsymbol{x}^{\prime}\rangle+1}{\sqrt{(\|\boldsymbol{z}\|_{2}^{2}+1)(\|\boldsymbol{z}^{\prime}\|_{2}^{2}+1)}}-\frac{\langle\boldsymbol{z},\boldsymbol{x}^{\prime}\rangle+1}{\sqrt{(\|\boldsymbol{z}\|_{2}^{2}+1)(\|\boldsymbol{x}^{\prime}\|_{2}^{2}+1)}}\right|$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{(\|\boldsymbol{z}\|_{2}^{2}+1)(\|\boldsymbol{z}^{\prime}\|_{2}^{2}+1)}}|\langle\boldsymbol{z},\boldsymbol{z}^{\prime}-\boldsymbol{x}^{\prime}\rangle|$
$\displaystyle+\frac{1}{\sqrt{(\|\boldsymbol{z}\|_{2}^{2}+1)(\|\boldsymbol{z}^{\prime}\|_{2}^{2}+1)(\|\boldsymbol{x}^{\prime}\|_{2}^{2}+1)}}|\langle\boldsymbol{z},\boldsymbol{x}^{\prime}\rangle+1|\left|\sqrt{\|\boldsymbol{x}^{\prime}\|_{2}^{2}+1}-\sqrt{\|\boldsymbol{z}^{\prime}\|_{2}^{2}+1}\right|$
$\displaystyle\leq$
$\displaystyle\sqrt{d}B\epsilon_{0}+(dB^{2}+1)\sqrt{2\sqrt{d}B}\sqrt{\epsilon_{0}}$

where the last line follows from the fact that
$|\sqrt{x^{2}+1}-\sqrt{x^{\prime
2}+1}|\leq\sqrt{|x+x^{\prime}|}\sqrt{|x-x^{\prime}|}$ for all
$x,x^{\prime}\in\mathbb{R}$. Then we have

$\displaystyle\lvert\psi(\boldsymbol{z},\boldsymbol{z}^{\prime})-\psi(\boldsymbol{z},\boldsymbol{x}^{\prime})\rvert\leq$
$\displaystyle|\arccos
1-\arccos(1-\Delta)|=\int_{1-\Delta}^{1}\frac{1}{\sqrt{1-x^{2}}}\mathrm{d}x$
$\displaystyle\leq$
$\displaystyle\int_{1-\Delta}^{1}\frac{1}{\sqrt{1-x}}\mathrm{d}x=2\sqrt{\Delta}$
$\displaystyle\leq$ $\displaystyle
2\sqrt{\sqrt{d}B\epsilon_{0}+(dB^{2}+1)\sqrt{2\sqrt{d}B}\sqrt{\epsilon_{0}}}.$

∎

####  C.1.2 Proof of Lemma C.5

It is hard to analyze $K_{\boldsymbol{\theta}(t)}^{m}$ directly, so we show
$K_{\boldsymbol{\theta}}^{m}$ is close to $K_{\boldsymbol{\theta}(0)}^{m}$ if
$\boldsymbol{\theta}$ is close to $\boldsymbol{\theta}(0)$ in Lemma C.11 first
and then prove $\boldsymbol{\theta}(t)$ is indeed near
$\boldsymbol{\theta}(0)$ in Proposition C.12.

##### Approximation for $K_{\boldsymbol{\theta}}^{m}$ to
$K_{\boldsymbol{\theta}(0)}^{m}$

Denote by

$\boldsymbol{\Theta}(\boldsymbol{\theta}(0),R_{0})=\left\\{\boldsymbol{\theta}~{}\middle|~{}|a_{r}-a_{r}(0)|,|\boldsymbol{w}_{r,(j)}-\boldsymbol{w}_{r,(j)}(0)|,|b_{r}-b_{r}(0)|\leq
R_{0},r\in[2m],j\in[d]\right\\}$

the neighborhood of $\boldsymbol{\theta}(0)$.

######  Lemma C.10.

For all $\boldsymbol{x}\in\mathcal{X}$, for all
$\boldsymbol{\theta}\in\boldsymbol{\Theta}(\boldsymbol{\theta}(0),R)$,
conditioning on the event $\mathcal{R}$, then $|I(\boldsymbol{x})|\geq
2(m-\lfloor m^{\gamma}\rfloor)$ where
$I(\boldsymbol{x})=\\{r\mid\boldsymbol{1}_{\boldsymbol{\theta},r}(\boldsymbol{x})=\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})\\}$
is the index set of neurons on which the activation pattern for
$\boldsymbol{x}$ is the same at $\boldsymbol{\theta}$ and
$\boldsymbol{\theta}(0)$.

###### Proof.

Since $\boldsymbol{\theta}\in\boldsymbol{\Theta}(\boldsymbol{\theta}(0),R)$,
we have

$|h_{\boldsymbol{\theta},r}(\boldsymbol{x})-h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})|=|\langle\boldsymbol{w}_{r}-\boldsymbol{w}_{r}(0),\boldsymbol{x}\rangle+(b_{r}-b_{r}(0))|\leq(dB+1)R.$

For $r\in
I_{\mathrm{in}}(\boldsymbol{x})=\left\\{r~{}\middle|~{}|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})|>(dB+1)R~{}\right\\}$,
we have

$|h_{\boldsymbol{\theta},r}(\boldsymbol{x})-h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})|<|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})|,$

which implies
$\boldsymbol{1}_{\boldsymbol{\theta},r}(\boldsymbol{x})=\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})$,
thus $|I(\boldsymbol{x})|\geq|I_{\text{in}}(\boldsymbol{x})|\geq 2(m-\lfloor
m^{\gamma}\rfloor)$. ∎

######  Lemma C.11.

Conditioning on the event $\mathcal{B}\cap\mathcal{R}$, if $m$ is sufficiently
large, then

$\sup_{\boldsymbol{\theta}\in\boldsymbol{\Theta}(\boldsymbol{\theta}(0),R)}\sup_{\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathcal{X}}|K_{\boldsymbol{\theta}}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})|\leq
C_{7}m^{-(1-\gamma)}\log m,$

where $C_{7}>0$ is a constant depending on $d,B$.

###### Proof.

For all $\boldsymbol{x},\boldsymbol{x}^{\prime}\in\mathcal{X}$, let
$I=I(\boldsymbol{x})\cap I(\boldsymbol{x}^{\prime})$, then
$|I|=|I(\boldsymbol{x})|+|I(\boldsymbol{x}^{\prime})|-|I(\boldsymbol{x})\cup
I(\boldsymbol{x}^{\prime})|\geq 2m-4\lfloor m^{\gamma}\rfloor$ by Lemma C.10.
Hence for all
$\boldsymbol{\theta}\in\boldsymbol{\Theta}(\boldsymbol{\theta}(0),R)$,

$\displaystyle\quad|H_{\boldsymbol{\theta}}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-H_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})|$
$\displaystyle\leq\frac{(dB^{2}+1)}{m}\sum_{r\in[2m]}|a_{r}^{2}\boldsymbol{1}_{\boldsymbol{\theta},r}(\boldsymbol{x})\boldsymbol{1}_{\boldsymbol{\theta},r}(\boldsymbol{x}^{\prime})-a_{r}^{2}(0)\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})\boldsymbol{1}_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime})|$
$\displaystyle\leq\frac{(dB^{2}+1)}{m}\left(\sum_{r\in I}\lvert
a_{r}^{2}-a_{r}^{2}(0)\rvert+\sum_{r\in
I^{\mathsf{c}}}\max\\{a_{r}^{2},a_{r}^{2}(0)\\}\right)$
$\displaystyle\leq(dB^{2}+1)\left(\frac{|I|}{m}3RR_{B}+\frac{|I^{\mathsf{c}}|}{m}4R_{B}^{2}\right)$
$\displaystyle\leq(dB^{2}+1)\left(3RR_{B}+16R_{B}^{2}\frac{\lfloor
m^{\gamma}\rfloor}{m}\right).$

Similarly, we have

$\displaystyle\quad|G_{\boldsymbol{\theta}}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-G_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})|$
$\displaystyle\leq\frac{1}{m}\sum_{r\in[2m]}|\sigma(h_{\boldsymbol{\theta},r}(\boldsymbol{x}))\sigma(h_{\boldsymbol{\theta},r}(\boldsymbol{x}^{\prime}))-\sigma(h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}))\sigma(h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime}))|$
$\displaystyle\leq\frac{1}{m}\bigg{(}\sum_{r\in
I}\left(|h_{\boldsymbol{\theta},r}(\boldsymbol{x})||h_{\boldsymbol{\theta},r}(\boldsymbol{x}^{\prime})-h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime})|+|h_{\boldsymbol{\theta},r}(\boldsymbol{x})-h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})||h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime})|\right)$
$\displaystyle\quad+\sum_{r\in
I^{\mathsf{c}}}\max\\{|h_{\boldsymbol{\theta},r}(\boldsymbol{x})||h_{\boldsymbol{\theta},r}(\boldsymbol{x}^{\prime})|,|h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x})||h_{\boldsymbol{\theta}(0),r}(\boldsymbol{x}^{\prime})|\\}\bigg{)}$
$\displaystyle\leq\frac{|I|}{m}4(dB+1)^{2}R_{B}R+\frac{|I^{\mathsf{c}}|}{m}8(dB+1)^{2}R_{B}^{2}$
$\displaystyle\leq 4(dB+1)^{2}R_{B}R+8(dB+1)^{2}R_{B}^{2}\frac{\lfloor
m^{\gamma}\rfloor}{m}.$

Simply by the triangle inequality, we have

$\displaystyle\quad|K_{\boldsymbol{\theta}}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})|$
$\displaystyle\leq|H_{\boldsymbol{\theta}}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-H_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})|+|G_{\boldsymbol{\theta}}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})-G_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{x},\boldsymbol{x}^{\prime})|$
$\displaystyle\leq(dB^{2}+1)\left(3R_{B}R+16R_{B}^{2}\frac{\lfloor
m^{\gamma}\rfloor}{m}\right)+4(dB+1)^{2}R_{B}R+8(dB+1)^{2}R_{B}^{2}\frac{\lfloor
m^{\gamma}\rfloor}{m}$ $\displaystyle\leq C_{7}m^{-(1-\gamma)}\log m,$

where the last inequality holds when $m$ is sufficiently large. ∎

##### Lazy regime

######  Proposition C.12.

Let
$R^{\prime}=\frac{4\sqrt{3}(dB+1)\|\boldsymbol{y}\|_{2}}{\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X}))\sqrt{n}}\sqrt{\frac{\log
m}{m}}$. Denote the “lazy regime” event by

$\mathcal{A}=\mathcal{A}_{\lambda}\cap\mathcal{A}_{\boldsymbol{\theta}}\cap\mathcal{A}_{\boldsymbol{u}},$

where

$\displaystyle\mathcal{A}_{\lambda}=\left\\{\omega~{}\middle|~{}\lambda_{\min}(K_{\boldsymbol{\theta}(t)}^{m}(\boldsymbol{X},\boldsymbol{X}))\geq\frac{\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X}))}{2},~{}\forall
t\geq 0\right\\},$
$\displaystyle\mathcal{A}_{\boldsymbol{\theta}}=\left\\{\omega~{}\middle|~{}\boldsymbol{\theta}(t)\in\boldsymbol{\Theta}(\boldsymbol{\theta}(0),R^{\prime}),~{}\forall
t\geq 0\right\\},$
$\displaystyle\mathcal{A}_{\boldsymbol{u}}=\left\\{\omega~{}\middle|~{}\|\boldsymbol{u}^{m}(t)\|_{2}^{2}\leq
e^{-\frac{\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X}))}{n}t}\|\boldsymbol{u}(0)\|_{2}^{2},~{}\forall
t\geq 0\right\\}.$

If we further set $\alpha<1/2$ and $\gamma>1-\beta/4$, when $m$ is
sufficiently large, such that $R^{\prime}<R$, then we have

$\mathcal{A}\supseteq\mathcal{B}\cap\mathcal{R}\cap\mathcal{C}.$

The proof of Proposition C.12 is deferred to the end of Appendix C.1.2. To
prove it, we need the following three lemmas.

######  Lemma C.13.

For some $t\geq 0$, if there exists some $\lambda_{\min}>0$ such that for all
$0\leq s\leq t$,

$\lambda_{\min}(K_{\boldsymbol{\theta}(s)}^{m}(\boldsymbol{X},\boldsymbol{X}))\geq\lambda_{\min}/2,$

then

$\|\boldsymbol{u}^{m}(t)\|_{2}^{2}\leq
e^{-\frac{\lambda_{\min}}{n}t}\|\boldsymbol{u}^{m}(0)\|_{2}^{2}.$

###### Proof.

Notice that

$\displaystyle\frac{\partial\|\boldsymbol{u}^{m}(s)\|_{2}^{2}}{\partial
s}=\frac{\partial\|\boldsymbol{u}^{m}(s)\|_{2}^{2}}{\partial\boldsymbol{u}^{m}(s)}\frac{\partial\boldsymbol{u}^{m}(s)}{\partial
s}=-\frac{2}{n}\boldsymbol{u}^{m}(s)^{\top}K_{\boldsymbol{\theta}(s)}^{m}(\boldsymbol{X},\boldsymbol{X})\boldsymbol{u}^{m}(s)\leq-\frac{\lambda_{\min}}{n}\|\boldsymbol{u}^{m}(s)\|_{2}^{2}$

leads to

$\frac{\partial
e^{\frac{\lambda_{\min}}{n}s}\|\boldsymbol{u}^{m}(s)\|_{2}^{2}}{\partial
s}=e^{\frac{\lambda_{\min}}{n}s}\left(\frac{\lambda_{\min}}{n}\|\boldsymbol{u}^{m}(s)\|_{2}^{2}+\frac{\partial\|\boldsymbol{u}^{m}(s)\|_{2}^{2}}{\partial
s}\right)\leq 0.$

Thus $e^{\frac{\lambda_{\min}}{n}s}\|\boldsymbol{u}^{m}(s)\|_{2}^{2}$ is non-
increasing, which implies
$e^{\frac{\lambda_{\min}}{n}s}\|\boldsymbol{u}^{m}(t)\|_{2}^{2}\leq\|\boldsymbol{u}^{m}(0)\|_{2}^{2}$.
∎

######  Lemma C.14.

Conditioning on $\mathcal{B}\cap\mathcal{R}\cap\mathcal{C}$, if we set
$\gamma>1-\beta/4$ and $m$ is sufficiently large, then for all
$\boldsymbol{\theta}\in\boldsymbol{\Theta}(\boldsymbol{\theta}(0),R)$,

$\lambda_{\min}(K_{\boldsymbol{\theta}}^{m}(\boldsymbol{X},\boldsymbol{X}))\geq\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X}))/2.$

###### Proof.

Notice that

$\displaystyle\quad\|K_{\boldsymbol{\theta}}^{m}(\boldsymbol{X},\boldsymbol{X})-K_{d}(\boldsymbol{X},\boldsymbol{X})\|_{2}$
$\displaystyle\leq\lVert
K_{\boldsymbol{\theta}}^{m}(\boldsymbol{X},\boldsymbol{X})-K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{X},\boldsymbol{X})\rVert_{2}+\lVert
K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{X},\boldsymbol{X})-K_{d}(\boldsymbol{X},\boldsymbol{X})\rVert_{2}$
$\displaystyle\leq\|K_{\boldsymbol{\theta}}^{m}(\boldsymbol{X},\boldsymbol{X})-K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{X},\boldsymbol{X})\|_{\mathrm{F}}+\|K_{\boldsymbol{\theta}(0)}^{m}(\boldsymbol{X},\boldsymbol{X})-K_{d}(\boldsymbol{X},\boldsymbol{X})\|_{\mathrm{F}}$
$\displaystyle\leq(C_{2}+C_{7})nm^{-(1-\gamma)}\log m,$

where the last inequality follows from Lemma C.11 and Lemma C.4. If $m$ large
enough such that
$\|K_{\boldsymbol{\theta}}^{m}(\boldsymbol{X},\boldsymbol{X})-K_{d}(\boldsymbol{X},\boldsymbol{X})\|_{2}\leq\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X}))/2$,
then

$\displaystyle\lambda_{\min}(K_{\boldsymbol{\theta}}^{m}(\boldsymbol{X},\boldsymbol{X}))$
$\displaystyle\geq\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X}))-\|K_{\boldsymbol{\theta}}^{m}(\boldsymbol{X},\boldsymbol{X})-K_{d}(\boldsymbol{X},\boldsymbol{X})\|_{2}$
$\displaystyle\geq\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X}))/2.$

∎

######  Lemma C.15.

For some $t\geq 0$, suppose that
$\lambda_{\min}(K_{\boldsymbol{\theta}(s)}^{m}(\boldsymbol{X},\boldsymbol{X}))\geq\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X}))/2$
holds for all $s\in[0,t]$ and we set $\alpha<1/2$, so that $R^{\prime}<R$ when
$m$ is sufficiently large. Then conditioning on the event
$\mathcal{B}\cap\mathcal{R}\cap\mathcal{C}$, we have
$\boldsymbol{\boldsymbol{\theta}}(s)\in\boldsymbol{\Theta}(\boldsymbol{\theta}(0),R^{\prime})$
for all $s\in[0,t]$ when $m$ is sufficiently large.

###### Proof.

We prove the following two statements instead.

  1. 1.

If $|\boldsymbol{w}_{r,(j)}(s)-\boldsymbol{w}_{r,(j)}(0)|\leq R$ and
$|b_{r}(s)-b_{r}(0)|\leq R$ hold for all $r\in[2m],j\in[d]$ and all
$s\in[0,t]$, then $|a_{r}(t)-a_{r}(0)|\leq R^{\prime}$ holds for all
$r\in[2m]$;

  2. 2.

If $|a_{r}(s)-a_{r}(0)|\leq R$ holds for all $r\in[2m]$ and for all
$s\in[0,t]$, then $|\boldsymbol{w}_{r,(j)}(t)-\boldsymbol{w}_{r,(j)}(0)|\leq
R^{\prime},|b_{r}(t)-b_{r}(0)|\leq R^{\prime}$ hold for all
$r\in[2m],j\in[d]$.

We can bound the distance from initializations by integrating the norm of
gradient since
$\|\boldsymbol{v}(t)-\boldsymbol{v}(0)\|_{2}\leq\int_{0}^{t}\|\dot{\boldsymbol{v}}(s)\|_{2}\mathrm{d}s$
for any vector-valued function $\boldsymbol{v}(t)$. The gradient flow of
parameters is as follows:

$\displaystyle\dot{a}_{r}(s)=-\nabla_{a_{r}}\hat{\mathcal{L}}_{n}(f_{\boldsymbol{\theta}(s)}^{m})=-\frac{1}{n}m^{-1/2}\sum_{i\in[n]}\sigma(h_{\boldsymbol{\theta}(s),r}(\boldsymbol{x}_{i}))\boldsymbol{u}_{i}^{m}(s),$
$\displaystyle\dot{\boldsymbol{w}}_{r,(j)}(s)=-\nabla_{\boldsymbol{w}_{r,(j)}}\hat{\mathcal{L}}_{n}(f_{\boldsymbol{\theta}(s)}^{m})=-\frac{1}{n}m^{-1/2}\sum_{i\in[n]}a_{r}(s)\boldsymbol{x}_{i,(j)}\boldsymbol{1}_{\boldsymbol{\theta}(s),r}(\boldsymbol{x}_{i})\boldsymbol{u}_{i}^{m}(s),$
$\displaystyle\dot{b}_{r}(s)=-\nabla_{b_{r}}\hat{\mathcal{L}}_{n}(f_{\boldsymbol{\theta}(s)}^{m})=-\frac{1}{n}m^{-1/2}\sum_{i\in[n]}a_{r}(s)\boldsymbol{1}_{\boldsymbol{\theta}(s),r}(\boldsymbol{x}_{i})\boldsymbol{u}_{i}^{m}(s).$

By the Cauchy-Schwartz inequality and Lemma C.13,

$\sum_{i\in[n]}|\boldsymbol{u}_{i}^{m}(s)|\leq\sqrt{n}\|\boldsymbol{u}^{m}(s)\|_{2}\leq\sqrt{n}e^{-\frac{\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X}))}{2n}s}\|\boldsymbol{y}\|_{2}.$

In the following, we suppose $m$ is sufficiently large such that $R\leq
R_{B}$.

1\. Since $|\boldsymbol{w}_{r,(j)}(s)-\boldsymbol{w}_{r,(j)}(0)|\leq R$ and
$|b_{r}(s)-b_{r}(0)|\leq R$ hold for all $r\in[2m],j\in[d]$, we have
$\sigma(h_{\boldsymbol{\theta}(s),r}(\boldsymbol{x}_{i}))\leq 2(dB+1)R_{B}$.
Thus, according to the gradient flow, we have

$\displaystyle|\dot{a}_{r}(s)|\leq$
$\displaystyle\frac{1}{n}m^{-1/2}\max_{i\in[n]}\sigma(h_{\boldsymbol{\theta}(s),r}(\boldsymbol{x}_{i}))\sum_{i\in[n]}|\boldsymbol{u}_{i}^{m}(s)|$
$\displaystyle\leq$
$\displaystyle\frac{1}{n}m^{-1/2}2(dB+1)R_{B}\sqrt{n}e^{-\frac{\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X}))}{2n}s}\|\boldsymbol{y}\|_{2}$

and

$|a_{r}(t)-a_{r}(0)|\leq\int_{0}^{t}|\dot{a}_{r}(s)|\mathrm{d}s\leq\frac{4\sqrt{3}(dB+1)\|\boldsymbol{y}\|_{2}}{\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X}))\sqrt{n}}\sqrt{\frac{\log
m}{m}}\leq R^{\prime}.$

hold for every $r\in[2m]$.

2\. Since $|a_{r}(s)-a_{r}(0)|\leq R$ holds for all $r\in[2m]$, we have
$|a_{r}(s)|\leq 2R_{B}$. Thus, we have that

$\displaystyle|\dot{\boldsymbol{w}}_{r,(j)}(s)|\leq\frac{1}{n}m^{-1/2}B2R_{B}\sqrt{n}e^{-\frac{\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X}))}{2n}s}\|\boldsymbol{y}\|_{2},$
$\displaystyle|\dot{b}_{r}(s)|\leq\frac{1}{n}m^{-1/2}2R_{B}\sqrt{n}e^{-\frac{\lambda_{\min}(K_{d}(\boldsymbol{X},\boldsymbol{X}))}{2n}s}\|\boldsymbol{y}\|_{2},$

and