# Generalized Leverage Score Sampling for Neural Networks††thanks: The authors
would like to thank Michael Kapralov for suggestion of this topic.

Jason D. Lee<EMAIL_ADDRESS>Princeton University. Ruoqi Shen
<EMAIL_ADDRESS>University of Washington. Work done while visiting
Institute for Advanced Study. Zhao Song<EMAIL_ADDRESS>Columbia
University, Princeton University and Institute for Advanced Study. Mengdi Wang
<EMAIL_ADDRESS>Princeton University. Zheng Yu<EMAIL_ADDRESS>Princeton University.

Leverage score sampling is a powerful technique that originates from
theoretical computer science, which can be used to speed up a large number of
fundamental questions, e.g. linear regression, linear programming, semi-
definite programming, cutting plane method, graph sparsification, maximum
matching and max-flow. Recently, it has been shown that leverage score
sampling helps to accelerate kernel methods [Avron, Kapralov, Musco, Musco,
Velingker and Zandieh 17].

In this work, we generalize the results in [Avron, Kapralov, Musco, Musco,
Velingker and Zandieh 17] to a broader class of kernels. We further bring the
leverage score sampling into the field of deep learning theory.

  * •

We show the connection between the initialization for neural network training
and approximating the neural tangent kernel with random features.

  * •

We prove the equivalence between regularized neural network and neural tangent
kernel ridge regression under the initialization of both classical random
Gaussian and leverage score sampling.

###### Contents

  1. 1 Introduction
  2. 2 Related work
  3. 3 Main results
    1. 3.1 Kernel approximation with leverage score sampling
    2. 3.2 Application in training regularized neural network
      1. 3.2.1 Equivalence I, training with random Gaussian initialization
      2. 3.2.2 Equivalence II, training with leverage scores
  4. 4 Overview of techniques
  5. 5 Conclusion
  6. A Preliminaries
    1. A.1 Probability tools
    2. A.2 Neural tangent kernel and its properties
  7. B Equivalence between sufficiently wide neural net and kernel ridge regression
    1. B.1 Preliminaries
    2. B.2 Definitions
    3. B.3 Gradient, gradient flow, and linear convergence
    4. B.4 Proof sketch
    5. B.5 Equivalence between training net with regularization and kernel ridge regression for test data prediction
      1. B.5.1 Upper bounding $|u_{\operatorname{ntk},\operatorname{test}}(T)-u_{\operatorname{test}}^{*}|$
      2. B.5.2 Upper bounding $|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|$ by bounding initialization and kernel perturbation
      3. B.5.3 Upper bounding initialization perturbation
      4. B.5.4 Upper bounding kernel perturbation
      5. B.5.5 Final result for upper bounding $|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|$
      6. B.5.6 Main result for test data prediction equivalence
    6. B.6 Equivalence between training net with regularization and kernel ridge regression for training data prediction
  8. C Generalization result of leverage score sampling for approximating kernels
    1. C.1 Preliminaries
    2. C.2 Main result
  9. D Equivalence between training neural network with regularization and kernel ridge regression under leverage score sampling
    1. D.1 Preliminaries
    2. D.2 Definitions
    3. D.3 Leverage score sampling, gradient flow, and linear convergence
    4. D.4 Proof sketch
    5. D.5 Main result
      1. D.5.1 Upper bounding $\|u^{*}-\overline{u}^{*}\|_{2}$
      2. D.5.2 Upper bounding $\|\overline{u}_{\operatorname{nn}}(T)-\overline{u}^{*}\|_{2}$
      3. D.5.3 Main result for equivalence with leverage score sampling initialization
  10. E Extension to other neural network models

##  1 Introduction

Kernel method is one of the most common techniques in various machine learning
problems. One classical application is the kernel ridge regression (KRR).
Given training data $X=[x_{1},\cdots,x_{n}]^{\top}\in\mathbb{R}^{n\times d}$,
corresponding labels $Y=[y_{1},\cdots,y_{n}]\in\mathbb{R}^{n}$ and
regularization parameter $\lambda>0$, the output estimate of KRR for any given
input $z$ can be written as:

$\displaystyle f(z)=\mathsf{K}(z,X)^{\top}(K+\lambda I_{n})^{-1}Y,$ (1)

where $\mathsf{K}(\cdot,\cdot)$ denotes the kernel function and
$K\in\mathbb{R}^{n\times n}$ denotes the kernel matrix.

Despite being powerful and well-understood, the kernel ridge regression
suffers from the costly computation when dealing with large datasets, since
generally implementation of Eq. (1) requires $O(n^{3})$ running time.
Therefore, intensive research have been dedicated to the scalable methods for
KRR [Bac13, AM15, ZDW15, ACW17, MM17, ZNV+20]. One of the most popular
approach is the random Fourier features sampling originally proposed by [RR08]
for shift-invariant kernels. They construct a finite dimensional random
feature vector $\phi:\mathbb{R}^{d}\to\operatorname*{\mathbb{C}}^{s}$ through
sampling that approximates the kernel function
$\mathsf{K}(x,z)\approx\phi(x)^{*}\phi(z)$ for data $x,z\in\mathbb{R}^{d}$.
The random feature helps approximately solves KRR in $O(ns^{2}+n^{2})$ running
time, which improves the computational cost if $s\ll n$. The work [AKM+17]
advanced this result by introducing the leverage score sampling to take the
regularization term into consideration.

In this work, we follow the the approach in [AKM+17] and naturally generalize
the result to a broader class of kernels, which is of the form

$\displaystyle\mathsf{K}(x,z)=\operatorname*{{\mathbb{E}}}_{w\sim
p}[\phi(x,w)^{\top}\phi(z,w)],$

where $\phi:\mathbb{R}^{d}\times\mathbb{R}^{d_{1}}\to\mathbb{R}^{d_{2}}$ is a
finite dimensional vector and $p:\mathbb{R}^{d_{1}}\to\mathbb{R}_{\geq 0}$ is
a probability distribution. We apply the leverage score sampling technique in
this generalized case to obtain a tighter upper-bound on the dimension of
random features.

Further, We discuss the application of our theory in neural network training.
Over the last two years, there is a long line of over-parametrization theory
works on the convergence results of deep neural network [LL18, DZPS19,
AZLS19b, AZLS19a, DLL+19, ADH+19b, ADH+19a, SY19, BPSW20], all of which either
explicitly or implicitly use the property of neural tangent kernel [JGH18].
However, most of those results focus on neural network training without
regularization, while in practice regularization (which is originated from
classical machine learning) has been widely used in training deep neural
network. Therefore, in this work we rigorously build the equivalence between
training a ReLU deep neural network with $\ell_{2}$ regularization and neural
tangent kernel ridge regression. We observe that the initialization of
training neural network corresponds to approximating the neural tangent kernel
with random features, whose dimension is proportional to the width of the
network. Thus, it motivates us to bring the leverage score sampling theory
into the neural network training. We present a new equivalence between neural
net and kernel ridge regression under the initialization using leverage score
sampling, which potentially improves previous equivalence upon the upper-bound
of network width needed.

We summarize our main results and contribution as following:

  * •

Generalize the leverage score sampling theory for kernel ridge regression to a
broader class of kernels.

  * •

Connect the leverage score sampling theory with neural network training.

  * •

Theoretically prove the equivalence between training regularized neural
network and kernel ridge regression under both random Gaussian initialization
and leverage score sampling initialization.

##  2 Related work

##### Leverage scores

Given a $m\times n$ matrix $A$. Let $a_{i}^{\top}$ be the $i$-th rows of $A$
and the leverage score of the $i$-th row of $A$ is
$\sigma_{i}(A)=a_{i}^{\top}(A^{\top}A)^{\dagger}a_{i}$. A row’s leverage score
measures how important it is in composing the row space of $A$. If a row has a
component orthogonal to all other rows, its leverage score is $1$. Removing it
would decrease the rank of $A$, completely changing its row space. The
coherence of $A$ is $\|\sigma(A)\|_{\infty}$. If $A$ has low coherence, no
particular row is especially important. If $A$ has high coherence, it contains
at least one row whose removal would significantly affect the composition of
$A$’s row space.

Leverage score is a fundamental concept in graph problems and numerical linear
algebra. There are many works on how to approximate leverage scores [SS11,
DMIMW12, CW13, NN13] or more general version of leverages, e.g. Lewis weights
[Lew78, BLM89, CP15]. From graph perspective, it has been applied to maximum
matching [BLN+20, LSZ20], max-flow [DS08, Mad13, Mad16, LS20b, LS20a],
generate random spanning trees [Sch18], and sparsify graphs [SS11]. From
matrix perspective, it has been used to give matrix CUR decomposition [BW14,
SWZ17, SWZ19] and tensor CURT decomposition [SWZ19]. From optimization
perspective, it has been used to approximate the John Ellipsoid [CCLY19],
linear programming [LS14, BLSS20, JSWZ20], semi-definite programming [JKL+20],
and cutting plane methods [Vai89, LSW15, JLSW20].

##### Kernel methods

Kernel methods can be thought of as instance-based learners: rather than
learning some fixed set of parameters corresponding to the features of their
inputs, they instead “remember” the $i$-th training example $(x_{i},y_{i})$
and learn for it a corresponding weight $w_{i}$. Prediction for unlabeled
inputs, i.e., those not in the training set, is treated by the application of
similarity function $\mathsf{K}$, called a kernel, between the unlabeled input
$x^{\prime}$ and each of the training inputs $x_{i}$.

There are three lines of works that are closely related to our work. First,
our work is highly related to the recent discoveries of the connection between
deep learning and kernels [DFS16, Dan17, JGH18, CB18]. Second, our work is
closely related to development of connection between leverage score and
kernels [RR08, CW17, CMM17, MW17b, MW17a, LTOS18, AKM+17, AKM+19, ACSS20].
Third, our work is related to kernel ridge regression [Bac13, AM15, ZDW15,
ACW17, MM17, ZNV+20].

##### Convergence of neural network

There is a long line of work studying the convergence of neural network with
random input assumptions [BG17, Tia17, ZSJ+17, Sol17, LY17, ZSD17, DLT+18,
GLM18, BJW19]. For a quite while, it is not known to remove the randomness
assumption from the input data points. Recently, there is a large number of
work studying the convergence of neural network in the over-parametrization
regime [LL18, DZPS19, AZLS19b, AZLS19a, DLL+19, ADH+19b, ADH+19a, SY19,
BPSW20]. These results don’t need to assume that input data points are random,
and only require some much weaker assumption which is called “data-separable”.
Mathematically, it says for any two input data points $x_{i}$ and $x_{j}$, we
have $\|x_{i}-x_{j}\|_{2}\geq\delta$. Sufficiently wide neural network
requires the width $m$ to be at least $\operatorname{poly}(n,d,L,1/\delta)$,
where $n$ is the number of input data points, $d$ is the dimension of input
data point, $L$ is the number of layers.

##### Continuous Fourier transform

The continuous Fourier transform is defined as a problem [JLS20] where you
take samples $f(t_{1}),\cdots,f(t_{m})$ from the time domain
$f(t):=\sum_{j=1}^{n}v_{j}e^{2\pi\mathbf{i}\langle x_{j},t\rangle}$, and try
to reconstruct function
$f:\mathbb{R}^{d}\rightarrow\operatorname*{\mathbb{C}}$ or even recover
$\\{(v_{j},x_{j})\\}\in\operatorname*{\mathbb{C}}\times\mathbb{R}^{d}$. The
data separation connects to the sparse Fourier transform in the continuous
domain. We can view the $n$ input data points [LL18, AZLS19b, AZLS19a] as $n$
frequencies in the Fourier transform [Moi15, PS15]. The separation of the data
set is equivalent to the gap of the frequency set ($\min_{i\neq
j}\|x_{i}-x_{j}\|_{2}\geq\delta$). In the continuous Fourier transform, there
are two families of algorithms: one requires to know the frequency gap [Moi15,
PS15, CM20, JLS20] and the other doesn’t [CKPS16]. However, in the over-
parameterized neural network training, all the existing work requires a gap
for the data points.

##### Notations

We use $\mathbf{i}$ to denote $\sqrt{-1}$. For vector $x$, we use $\|x\|_{2}$
to denote the $\ell_{2}$ norm of $x$. For matrix $A$, we use $\|A\|$ to denote
the spectral norm of $A$ and $\|A\|_{F}$ to denote the Frobenius norm of $A$.
For matrix $A$ and $B$, we use $A\preceq B$ to denote that $B-A$ is positive
semi-definite. For a square matrix, we use $\operatorname{tr}[A]$ to denote
the trace of $A$. We use $A^{-1}$ to denote the true inverse of an invertible
matrix. We use $A^{\dagger}$ to denote the pseudo-inverse of matrix $A$. We
use $A^{\top}$ to denote the transpose of matrix $A$.

##  3 Main results

In this section, we state our results. In Section 3.1, we consider the large-
scale kernel ridge regression (KRR) problem. We generalize the Fourier
transform result [AKM+17] of accelerating the running time of solving KRR
using the tool of leverage score sampling to a broader class of kernels. In
Section 3.2, we discuss the interesting application of leverage score sampling
for training deep learning models due to the connection between regularized
neural nets and kernel ridge regression.

###  3.1 Kernel approximation with leverage score sampling

In this section, we generalize the leverage score theory in [AKM+17], which
analyzes the number of random features needed to approximate kernel matrix
under leverage score sampling regime for the kernel ridge regression task. In
the next a few paragraphs, we briefly review the settings of classical kernel
ridge regression.

Given training data given training data matrix
$X=[x_{1},\cdots,x_{n}]^{\top}\in\mathbb{R}^{n\times d}$, corresponding labels
$Y=[y_{1},\cdots,y_{n}]^{\top}\in\mathbb{R}^{n}$ and feature map
$\phi:\mathbb{R}^{d}\to\mathcal{F}$, a classical kernel ridge regression
problem can be written as111Strictly speaking, the optimization problem should
be considered in a hypothesis space defined by the reproducing kernel Hilbert
space associated with the feature/kernel. Here, we use the notation in finite
dimensional space for simplicity.

$\displaystyle\min_{\beta}\frac{1}{2}\|Y-\phi(X)^{\top}\beta\|_{2}^{2}+\frac{1}{2}\lambda\|\beta\|_{2}^{2}$

where $\lambda>0$ is the regularization parameter. By introducing the
corresponding kernel function $\mathsf{K}(x,z)=\langle\phi(x),\phi(z)\rangle$
for any data $x,z\in\mathbb{R}^{d}$, the output estimate of the kernel ridge
regression for any data $x\in\mathbb{R}^{d}$ can be denoted as
$f^{*}(x)=\mathsf{K}(x,X)^{\top}\alpha$, where $\alpha\in\mathbb{R}^{n}$ is
the solution to

$\displaystyle(K+\lambda I_{n})\alpha=Y.$

Here $K\in\mathbb{R}^{n\times n}$ is the kernel matrix with
$K_{i,j}=\mathsf{K}(x_{i},x_{j})$, $\forall i,j\in[n]\times[n]$.

Note a direct computation involves $(K+\lambda I_{n})^{-1}$, whose $O(n^{3})$
running time can be fairly large in tasks like neural network due to the large
number of training data. Therefore, we hope to construct feature map
$\phi:\mathbb{R}^{d}\to\mathbb{R}^{s}$, such that the new feature approximates
the kernel matrix well in the sense of

$\displaystyle(1-\epsilon)\cdot(K+\lambda I_{n})\preceq\Phi\Phi^{\top}+\lambda
I_{n}\preceq(1+\epsilon)\cdot(K+\lambda I_{n}),$ (2)

where $\epsilon\in(0,1)$ is small and
$\Phi=[\phi(x_{1}),\cdots,\phi(x_{n})]^{\top}\in\mathbb{R}^{n\times s}$. Then
by Woodbury matrix equality, we can approximate the solution by
$u^{*}(z)=\phi(z)^{\top}(\Phi^{\top}\Phi+\lambda I_{s})^{-1}\Phi^{\top}Y$,
which can be computed in $O(ns^{2}+n^{2})$ time. In the case $s=o(n)$,
computational cost can be saved.

In this work, we consider a generalized setting of [AKM+17] as a kernel ridge
regression problem with positive definite kernel matrix
$\mathsf{K}:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$ of the form

$\displaystyle\mathsf{K}(x,z)=\operatorname*{{\mathbb{E}}}_{w\sim
p}[\phi(x,w)^{\top}\phi(z,w)],$ (3)

where $\phi:\mathbb{R}^{d}\times\mathbb{R}^{d_{1}}\to\mathbb{R}^{d_{2}}$
denotes a finite dimensional vector and
$p:\mathbb{R}^{d_{1}}\to\mathbb{R}_{\geq 0}$ denotes a probability density
function.

Due to the regularization $\lambda>0$ in this setting, instead of constructing
the feature map directly from the distribution $q$, we consider the following
ridge leveraged distribution:

######  Definition 3.1 (Ridge leverage function).

Given data $x_{1},\cdots,x_{n}\in\mathbb{R}^{d}$ and parameter $\lambda>0$, we
define the ridge leverage function as

$\displaystyle
q_{\lambda}(w)=p(w)\cdot\operatorname{tr}[\Phi(w)^{\top}(K+\lambda
I_{n})^{-1}\Phi(w)],$

where $p(\cdot)$, $\phi$ are defined in Eq. (3), and
$\Phi(w)=[\phi(x_{1},w)^{\top},\cdots,\phi(x_{n},w)^{\top}]^{\top}\in\mathbb{R}^{n\times
d_{2}}$. Further, we define statistical dimension $s_{\lambda}(K)$ as

$\displaystyle s_{\lambda}(K)=\int
q_{\lambda}(w)\mathrm{d}w=\operatorname{tr}[(K+\lambda I_{n})^{-1}K].$ (4)

The leverage score sampling distribution $q_{\lambda}/s_{\lambda}(K)$ takes
the regularization term into consideration and achieves Eq. (2) using the
following modified random features vector:

######  Definition 3.2 (Modified random features).

Given any probability density function $q(\cdot)$ whose support includes that
of $p(\cdot)$. Given $m$ vectors $w_{1},\cdots,w_{m}\in\mathbb{R}^{d_{1}}$, we
define modified random features $\overline{\Psi}\in\mathbb{R}^{n\times
md_{2}}$ as
$\overline{\Psi}:=[\overline{\varphi}(x_{1}),\cdots,\overline{\varphi}(x_{n})]^{\top},$
where

$\displaystyle\overline{\varphi}(x)=\frac{1}{\sqrt{m}}\left[\frac{\sqrt{p(w_{1})}}{\sqrt{q(w_{1})}}\phi(x,w_{1})^{\top},\cdots,\frac{\sqrt{p(w_{m})}}{\sqrt{q(w_{m})}}\phi(x,w_{m})^{\top}\right]^{\top}.$

Now we are ready to present our result.

######  Theorem 3.3 (Kernel approximation with leverage score sampling,
generalization of Lemma 8 in [AKM+17]).

Given parameter $\lambda\in(0,\|K\|)$. Let
$q_{\lambda}:\mathbb{R}^{d_{1}}\to\mathbb{R}_{\geq 0}$ be the leverage score
defined in Definition 3.1. Let
$\widetilde{q}_{\lambda}:\mathbb{R}^{d_{1}}\rightarrow\mathbb{R}$ be any
measurable function such that $\widetilde{q}_{\lambda}(w)\geq q_{\lambda}(w)$
holds for all $w\in\mathbb{R}^{d_{1}}$. Assume
$s_{\widetilde{q}_{\lambda}}=\int_{\mathbb{R}^{d_{1}}}\widetilde{q}_{\lambda}(w)\mathrm{d}w$
is finite. Let
$\overline{q}_{\lambda}(w)=\widetilde{q}_{\lambda}(w)/s_{\widetilde{q}_{\lambda}}$.
Given any accuracy parameter $\epsilon\in(0,1/2)$ and failure probability
$\delta\in(0,1)$. Let $w_{1},\cdots,w_{m}\in\mathbb{R}^{d}$ denote $m$ samples
draw independently from the distribution associated with the density
$\overline{q}_{\lambda}(\cdot)$, and construct the modified random features
$\overline{\Psi}\in\mathbb{R}^{n\times md_{2}}$ as in Definition 3.2 with
$q=\overline{q}_{\lambda}$. Let $s_{\lambda}(K)$ be the statistical dimension
defined in (4). If $m\geq
3\epsilon^{-2}s_{\widetilde{q}_{\lambda}}\ln(16s_{\widetilde{q}_{\lambda}}\cdot
s_{\lambda}(K)/\delta)$, then we have

$\displaystyle(1-\epsilon)\cdot(K+\lambda
I_{n})\preceq\overline{\Psi}\overline{\Psi}^{\top}+\lambda
I_{n}\preceq(1+\epsilon)\cdot(K+\lambda I_{n})$ (5)

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

######  Remark 3.4.

Above results can be generalized to the complex domain
$\operatorname*{\mathbb{C}}$. Note for the random Fourier feature case
discussed in [AKM+17], we have $d_{1}=d$, $d_{2}=1$,
$\phi(x,w)=e^{-2\pi\mathbf{i}w^{\top}x}\in\operatorname*{\mathbb{C}}$ and
$p(\cdot)$ denotes the Fourier transform density distribution, which is a
special case in our setting.

###  3.2 Application in training regularized neural network

In this section, we consider the application of leverage score sampling in
training $\ell_{2}$ regularized neural networks.

Past literature such as [DZPS19],[ADH+19a] have already witnessed the
equivalence between training a neural network and solving a kernel regression
problem in a broad class of network models. In this work, we first generalize
this result to the regularization case, where we connect regularized neural
network with kernel ridge regression. Then we apply the above discussed the
leverage score sampling theory for KRR to the task of training neural nets.

####  3.2.1 Equivalence I, training with random Gaussian initialization

To illustrate the idea, we consider a simple model two layer neural network
with ReLU activation function as in [DZPS19, SY19]222Our results directly
extends to multi-layer deep neural networks with all layers trained together.

$\displaystyle
f_{\operatorname{nn}}(W,a,x)=\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\sigma(w_{r}^{\top}x)\in\mathbb{R},$

where $x\in\mathbb{R}^{d}$ is the input,
$w_{r}\in\mathbb{R}^{d},\leavevmode\nobreak\ r\in[m]$ is the weight vector of
the first layer, $W=[w_{1},\cdots,w_{m}]\in\mathbb{R}^{d\times m}$,
$a_{r}\in\mathbb{R},\leavevmode\nobreak\ r\in[m]$ is the output weight,
$a=[a_{1},\cdots,a_{m}]^{\top}$ and $\sigma(\cdot)$ is the ReLU activation
function: $\sigma(z)=\max\\{0,z\\}$.

Here we consider only training the first layer $W$ with fixed $a$, so we also
write $f_{\operatorname{nn}}(W,x)=f_{\operatorname{nn}}(W,a,x)$. Again, given
training data matrix $X=[x_{1},\cdots,x_{n}]^{\top}\in\mathbb{R}^{n\times d}$
and labels $Y=[y_{1},\cdots,y_{n}]^{\top}\in\mathbb{R}^{n}$, we denote
$f_{\operatorname{nn}}(W,X)=[f_{\operatorname{nn}}(W,x_{1}),\cdots,f_{\operatorname{nn}}(W,x_{n})]^{\top}\in\mathbb{R}^{n}$.
We formally define training neural network with $\ell_{2}$ regularization as
follows:

######  Definition 3.5 (Training neural network with regularization).

Let $\kappa\in(0,1]$ be a small multiplier333To establish the training
equivalence result, we assign $\kappa=1$ back to the normal case. For the
training equivalence result, we pick $\kappa>0$ to be a small multiplier only
to shrink the initial output of the neural network. The is the same as what is
used in [AKM+17].. Let $\lambda\in(0,1)$ be the regularization parameter. We
initialize the network as
$a_{r}\overset{i.i.d.}{\sim}\operatorname{unif}[\\{-1,1\\}]$ and
$w_{r}(0)\overset{i.i.d.}{\sim}\mathcal{N}(0,I_{d})$. Then we consider solving
the following optimization problem using gradient descent:

$\displaystyle\min_{W}\frac{1}{2}\|Y-\kappa
f_{\operatorname{nn}}(W,X)\|_{2}+\frac{1}{2}\lambda\|W\|_{F}^{2}.$ (6)

Let $w_{r}(t),r\in[m]$ be the network weight at iteration $t$. We denote the
training data predictor at iteration $t$ as $u_{\operatorname{nn}}(t)=\kappa
f_{\operatorname{nn}}(W(t),X)\in\mathbb{R}^{n}$. Further, given any test data
$x_{\operatorname{test}}\in\mathbb{R}^{d}$, we denote
$u_{\operatorname{nn},\operatorname{test}}(t)=\kappa
f_{\operatorname{nn}}(W(t),x_{\operatorname{test}})\in\mathbb{R}$ as the test
data predictor at iteration $t$.

On the other hand, we consider the following neural tangent kernel ridge
regression problem:

$\displaystyle\min_{\beta}\frac{1}{2}\|Y-\kappa
f_{\operatorname{ntk}}(\beta,X)\|_{2}^{2}+\frac{1}{2}\lambda\|\beta\|_{2}^{2},$
(7)

where $\kappa,\lambda$ are the same parameters as in Eq. (6),
$f_{\operatorname{ntk}}(\beta,x)=\Phi(x)^{\top}\beta\in\mathbb{R}$ and
$f_{\operatorname{ntk}}(\beta,X)=[f_{\operatorname{ntk}}(\beta,x_{1}),\cdots,f_{\operatorname{ntk}}(\beta,x_{n})]^{\top}\in\mathbb{R}^{n}$
are the test data predictors. Here, $\Phi$ is the feature map corresponding to
the neural tangent kernel (NTK):

$\displaystyle\mathsf{K}_{\operatorname{ntk}}(x,z)=\operatorname*{{\mathbb{E}}}\left[\left\langle\frac{\partial
f_{\operatorname{nn}}(W,x)}{\partial W},\frac{\partial
f_{\operatorname{nn}}(W,z)}{\partial W}\right\rangle\right]$ (8)

where $x,z\in\mathbb{R}^{d}$ are any input data, and the expectation is taken
over $w_{r}\overset{i.i.d.}{\sim}\mathcal{N}(0,I),\leavevmode\nobreak\
r=1,\cdots,m$.

Under the standard assumption $\mathsf{K}_{\operatorname{ntk}}$ being positive
definite, the problem Eq. (7) is a strongly convex optimization problem with
the optimal predictor
$u^{*}=\kappa^{2}H^{\operatorname{cts}}(\kappa^{2}H^{\operatorname{cts}}+\lambda
I)^{-1}Y$ for training data, and the corresponding predictor
$u_{\operatorname{test}}^{*}=\kappa^{2}\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)^{\top}(\kappa^{2}H^{\operatorname{cts}}+\lambda
I)^{-1}Y$ for the test data $x_{\operatorname{test}}$, where
$H^{\operatorname{cts}}\in\mathbb{R}^{n\times n}$ is the kernel matrix with
$[H^{\operatorname{cts}}]_{i,j}=\mathsf{K}_{\operatorname{ntk}}(x_{i},x_{j})$.

We connect the problem Eq. (6) and Eq. (7) by building the following
equivalence between their training and test predictors with polynomial widths:

######  Theorem 3.6 (Equivalence between training neural net with
regularization and kernel ridge regression for training data prediction).

Given any accuracy $\epsilon\in(0,1/10)$ and failure probability
$\delta\in(0,1/10)$. Let multiplier $\kappa=1$, number of iterations
$T=\widetilde{O}(\frac{1}{\Lambda_{0}})$, network width
$m\geq\widetilde{O}(\frac{n^{4}d}{\Lambda_{0}^{4}\epsilon})$ and the
regularization parameter $\lambda\leq\widetilde{O}(\frac{1}{\sqrt{m}})$. Then
with probability at least $1-\delta$ over the Gaussian random initialization,
we have

$\displaystyle\|u_{\operatorname{nn}}(T)-u^{*}\|_{2}\leq\epsilon.$

Here $\widetilde{O}(\cdot)$ hides
$\operatorname{poly}\log(n/(\epsilon\delta\Lambda_{0}))$.

We can further show the equivalence between the test data predictors with the
help of the multiplier $\kappa$.

######  Theorem 3.7 (Equivalence between training neural net with
regularization and kernel ridge regression for test data prediction).

Given any accuracy $\epsilon\in(0,1/10)$ and failure probability
$\delta\in(0,1/10)$. Let multiplier
$\kappa=\widetilde{O}(\frac{\epsilon\Lambda_{0}}{n})$, number of iterations
$T=\widetilde{O}(\frac{1}{\kappa^{2}\Lambda_{0}})$, network width
$m\geq\widetilde{O}(\frac{n^{10}d}{\epsilon^{6}\Lambda_{0}^{10}})$ and
regularization parameter $\lambda\leq\widetilde{O}(\frac{1}{\sqrt{m}})$. Then
with probability at least $1-\delta$ over the Gaussian random initialization,
we have

$\displaystyle\|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{test}}^{*}\|_{2}\leq\epsilon.$

Here $\widetilde{O}(\cdot)$ hides
$\operatorname{poly}\log(n/(\epsilon\delta\Lambda_{0}))$.

####  3.2.2 Equivalence II, training with leverage scores

To apply the leverage score theory discussed in Section 3.1, Note the
definition of the neural tangent kernel is exactly of the form:

$\displaystyle\mathsf{K}_{\operatorname{ntk}}(x,z)=\operatorname*{{\mathbb{E}}}\left[\left\langle\frac{\partial
f_{\operatorname{nn}}(W,x)}{\partial W},\frac{\partial
f_{\operatorname{nn}}(W,z)}{\partial
W}\right\rangle\right]=\operatorname*{{\mathbb{E}}}_{w\sim
p}[\phi(x,w)^{\top}\phi(z,w)]$

where $\phi(x,w)=x\sigma^{\prime}(w^{\top}x)\in\mathbb{R}^{d}$ and $p(\cdot)$
denotes the probability density function of standard Gaussian distribution
$\mathcal{N}(0,I_{d})$. Therefore, we try to connect the theory of training
regularized neural network with leverage score sampling. Note the width of the
network corresponds to the size of the feature vector in approximating the
kernel. Thus, the smaller feature size given by the leverage score sampling
theory helps us build a smaller upper-bound on the width of the neural nets.

Specifically, given regularization parameter $\lambda>0$, we can define the
ridge leverage function with respect to neural tangent kernel
$H^{\operatorname{cts}}$ defined in Definition 3.1 as

$\displaystyle
q_{\lambda}(w)=p(w)\operatorname{tr}[\Phi(w)^{\top}(H^{\operatorname{cts}}+\lambda
I_{n})^{-1}\Phi(w)]$

and corresponding probability density function

$\displaystyle
q(w)=\frac{q_{\lambda}(w)}{s_{\lambda}(H^{\operatorname{cts}})}$ (9)

where
$\Phi(w)=[\phi(x_{1},w)^{\top},\cdots,\phi(x_{n},w)^{\top}]^{\top}\in\mathbb{R}^{n\times
d_{2}}$.

We consider training the following reweighed neural network using leverage
score initialization:

######  Definition 3.8 (Training reweighed neural network with
regularization).

Let $\kappa\in(0,1]$ be a small multiplier. Let $\lambda\in(0,1)$ be the
regularization parameter. Let $q(\cdot):\mathbb{R}^{d}\to\mathbb{R}_{>0}$
defined in (9). Let $p(\cdot)$ denotes the probability density function of
Gaussian distribution $\mathcal{N}(0,I_{d})$. We initialize the network as
$a_{r}\overset{i.i.d.}{\sim}\operatorname{unif}[\\{-1,1\\}]$ and
$w_{r}(0)\overset{i.i.d.}{\sim}q$. Then we consider solving the following
optimization problem using gradient descent:

$\displaystyle\min_{W}\frac{1}{2}\|Y-\kappa\overline{f}_{\operatorname{nn}}(W,X)\|_{2}+\frac{1}{2}\lambda\|W\|_{F}^{2}.$
(10)

where

$\displaystyle\overline{f}_{\operatorname{nn}}(W,x)=\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\sigma(w_{r}^{\top}X)\sqrt{\frac{p(w_{r}(0))}{q(w_{r}(0))}}\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\overline{f}_{\operatorname{nn}}(W,X)=[\overline{f}_{\operatorname{nn}}(W,x_{1}),\cdots,\overline{f}_{\operatorname{nn}}(W,x_{n})]^{\top}.$

We denote $w_{r}(t),r\in[m]$ as the estimate weight at iteration $t$. We
denote
$\overline{u}_{\operatorname{nn}}(t)=\kappa\overline{f}_{\operatorname{nn}}(W(t),X)$
as the training data predictor at iteration $t$. Given any test data
$x_{\operatorname{test}}\in\mathbb{R}^{d}$, we denote
$\overline{u}_{\operatorname{nn},\operatorname{test}}(t)=\kappa\overline{f}_{\operatorname{nn}}(W(t),x_{\operatorname{test}})$
as the test data predictor at iteration $t$.

We show that training this reweighed neural net with leverage score
initialization is still equivalence to the neural tangent kernel ridge
regression problem (7) as in following theorem:

######  Theorem 3.9 (Equivalence between training reweighed neural net with
regularization and kernel ridge regression for training data prediction).

Given any accuracy $\epsilon\in(0,1)$ and failure probability
$\delta\in(0,1/10)$. Let multiplier $\kappa=1$, number of iterations
$T=O(\frac{1}{\Lambda_{0}}\log(\frac{1}{\epsilon}))$, network width
$m=\operatorname{poly}(\frac{1}{\Lambda_{0}},n,d,\frac{1}{\epsilon},\log(\frac{1}{\delta}))$
and regularization parameter $\lambda=\widetilde{O}(\frac{1}{\sqrt{m}})$. Then
with probability at least $1-\delta$ over the random leverage score
initialization, we have

$\displaystyle\|\overline{u}_{\operatorname{nn}}(T)-u^{*}\|_{2}\leq\epsilon.$

Here $\widetilde{O}(\cdot)$ hides
$\operatorname{poly}\log(n/(\epsilon\delta\Lambda_{0}))$.

##  4 Overview of techniques

##### Generalization of leverage score theory

To prove Theorem 3.3, we follow the similar proof framework as Lemma 8 in
[AKM+17].

Let $K+\lambda I_{n}=V^{\top}\Sigma^{2}V$ be an eigenvalue decomposition of
$K+\lambda I_{n}$. Then conclusion (5) is equivalent to

$\displaystyle\|\Sigma^{-1}V\overline{\Psi}\overline{\Psi}^{\top}V^{\top}\Sigma^{-1}-\Sigma^{-1}VKV^{\top}\Sigma^{-1}\|\leq\epsilon$
(11)

Let random matrix $Y_{r}\in\mathbb{R}^{n\times n}$ defined as

$\displaystyle
Y_{r}:=\frac{p(w_{r})}{\overline{q}_{\lambda}(w_{r})}\Sigma^{-1}V{\Phi}(w_{r}){\Phi}(w_{r})^{\top}V^{\top}\Sigma^{-1}.$

where
$\Phi(w)=[\phi(x_{1},w),\cdots,\phi(x_{n},w)]^{\top}\in\mathbb{R}^{n\times
d_{2}}$. Then we have

$\displaystyle\operatorname*{{\mathbb{E}}}_{\overline{q}_{\lambda}}[Y_{l}]=\operatorname*{{\mathbb{E}}}_{\overline{q}_{\lambda}}\left[\frac{p(w_{r})}{\overline{q}_{\lambda}(w_{r})}\Sigma^{-1}V{\Phi}(w_{r})\overline{\Phi}(w_{r})^{\top}V^{\top}\Sigma^{-1}\right]=\Sigma^{-1}VKV^{\top}\Sigma^{-1},$

and

$\displaystyle\frac{1}{m}\sum_{r=1}^{m}Y_{r}=\frac{1}{m}\sum_{r=1}^{m}\frac{p(w_{r})}{\overline{q}_{\lambda}(w_{r})}\Sigma^{-1}V{\Phi}(w_{r})\overline{\Phi}(w_{r})^{\top}V^{\top}\Sigma^{-1}=\Sigma^{-1}V\overline{\Psi}\overline{\Psi}^{\top}V^{\top}\Sigma^{-1}.$

Thus, it suffices to show that

$\displaystyle\left\|\frac{1}{m}\sum_{r=1}^{m}Y_{r}-\operatorname*{{\mathbb{E}}}_{\overline{q}_{\lambda}}[Y_{l}]\right\|\leq\epsilon$
(12)

holds with probability at least $1-\delta$, which can be shown by applying
matrix concentration results. Note

$\displaystyle\|Y_{l}\|\leq s_{\overline{q}_{\lambda}}\leavevmode\nobreak\
\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}_{\overline{q}_{\lambda}}[Y_{r}^{2}]\preceq
s_{\widetilde{q}_{\lambda}}\cdot\operatorname{diag}\\{\lambda_{1}/(\lambda_{1}+\lambda),\cdots,\lambda_{n}/(\lambda_{n}+\lambda)\\}.$

Applying matrix concentration Lemma 7 in [AKM+17], we complete the proof.

##### Equivalence between regularized neural network and kernel ridge
regression

To establish the equivalence between training neural network with
regularization and neural tangent kernel ridge regression, the key observation
is that the dynamic kernel during the training is always close to the neural
tangent kernel.

Specifically, given training data $x_{1},\cdots,x_{n}\in\mathbb{R}^{d}$, we
define the dynamic kernel matrix $H(t)\in\mathbb{R}^{n\times n}$ along
training process as

$\displaystyle[H(t)]_{i,j}=\left\langle\frac{\mathrm{d}f_{\operatorname{nn}}(W(t),x_{i})}{\mathrm{d}W(t)},\frac{\mathrm{d}f_{\operatorname{nn}}(W(t),x_{j})}{\mathrm{d}W(t)}\right\rangle$

Then we can show the gradient flow of training regularized neural net
satisfies

$\displaystyle\frac{\mathrm{d}\|u^{*}-u_{\operatorname{nn}}(t)\|_{2}^{2}}{\mathrm{d}t}=$
$\displaystyle-2(u^{*}-u_{\operatorname{nn}}(t))^{\top}(H(t)+\lambda
I)(u^{*}-u_{\operatorname{nn}}(t))$ (13)
$\displaystyle+2(u_{\operatorname{nn}}(t)-u^{*})^{\top}(H(t)-H^{\operatorname{cts}})(Y-u^{*})$
(14)

where term (13) is the primary term characterizing the linear convergence of
$u_{\operatorname{nn}}(t)$ to $t^{*}$, and term (14) is the additive term that
can be well controlled if $H(t)$ is sufficiently close to
$H^{\operatorname{cts}}$. We argue the closeness of $H(t)\approx
H^{\operatorname{cts}}$ as the consequence of the following two observations:

  * •

Initialization phase: At the beginning of the training, $H(0)$ can be viewed
as approximating the neural tangent kernel $H^{\operatorname{cts}}$ using
finite dimensional random features. Note the size of these random features
corresponds to the width of the neural network (scale by the data dimension
$d$). Therefore, when the neural network is sufficiently wide, it is
equivalent to approximate the neural tangent kernel using sufficient high
dimensional feature vectors, which ensures $H(0)$ is sufficiently close to
$H^{\operatorname{cts}}$.

In the case of leverage score initialization, we further take the
regularization into consideration. We use the tool of leverage score to modify
the initialization distribution and corresponding network parameter, to give a
smaller upper-bound of the width of the nets needed.

  * •

Training phase: If the net is sufficiently wide, we can observe the over-
parametrization phenomenon such that the weight estimate $W(t)$ at time $t$
will be sufficiently close to its initialization $W(0)$, which implies the
dynamic kernel $H(t)$ being sufficiently close to $H(0)$. Due to the fact
$H(0)\approx H^{\operatorname{cts}}$ argued in initialization phase, we have
$H(t)\approx H^{\operatorname{cts}}$ throughout the algorithm.

Combining both observations, we are able to iteratively show the (nearly)
linear convergence property of training the regularized neural net as in
following lemma:

######  Lemma 4.1 (Bounding kernel perturbation, informal).

For any accuracy $\Delta\in(0,1/10)$. If the network width
$m=\operatorname{poly}(1/\Delta,1/T,1/\epsilon_{\operatorname{train}},n,d,1/\kappa,1/\Lambda_{0},\log(1/\delta))$
and $\lambda=O(\frac{1}{\sqrt{m}})$, with probability $1-\delta$, there exist
$\epsilon_{W},\leavevmode\nobreak\ \epsilon_{H}^{\prime},\leavevmode\nobreak\
\epsilon_{K}^{\prime}\in(0,\Delta)$ that are independent of $t$, such that the
following hold for all $0\leq t\leq T$:

  1. 1.

$\|w_{r}(0)-w_{r}(t)\|_{2}\leq\epsilon_{W}$, $\forall r\in[m]$

  2. 2.

$\|H(0)-H(t)\|_{2}\leq\epsilon_{H}^{\prime}$

  3. 3.

$\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}^{2}\leq\max\\{\epsilon_{\operatorname{train}}^{2},e^{-(\kappa^{2}\Lambda_{0}+\lambda)t/2}\|u_{\operatorname{nn}}(0)-u^{*}\|_{2}^{2}\\}$

Given arbitrary accuracy $\epsilon\in(0,1)$, if we choose
$\epsilon_{\operatorname{train}}=\epsilon$,
$T=\widetilde{O}(\frac{1}{\kappa^{2}\Lambda_{0}})$ and $m$ sufficiently large
in Lemma D.14, then we have
$\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}\leq\epsilon$, indicating the
equivalence between training neural network with regularization and neural
tangent kernel ridge regression for the training data predictions.

To further argue the equivalence for any given test data
$x_{\operatorname{test}}$, we observe the similarity between the gradient
flows of neural tangent kernel ridge regression
$u_{\operatorname{ntk},\operatorname{test}}(t)$ and regularized neural
networks $u_{\operatorname{nn},\operatorname{test}}(t)$ as following:

$\displaystyle\frac{\mathrm{d}u_{\operatorname{ntk},\operatorname{test}}(t)}{\mathrm{d}t}=$
$\displaystyle\leavevmode\nobreak\
\kappa^{2}\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)^{\top}(Y-u_{\operatorname{ntk}}(t))-\lambda\cdot
u_{\operatorname{ntk},\operatorname{test}}(t).$ (15)
$\displaystyle\frac{\mathrm{d}u_{\operatorname{nn},\operatorname{test}}(t)}{\mathrm{d}t}=$
$\displaystyle\leavevmode\nobreak\
\kappa^{2}\mathsf{K}_{t}(x_{\operatorname{test}},X)^{\top}(Y-u_{\operatorname{nn}}(t))-\lambda\cdot
u_{\operatorname{nn},\operatorname{test}}(t).$ (16)

By choosing the multiplier $\kappa>0$ small enough, we can bound the initial
difference between these two predictors. Combining with above similarity
between gradient flows, we are able to show
$|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|\geq\epsilon/2$
for appropriate $T>0$. Finally, note the linear convergence property of the
gradient of the kernel ridge regression, we can prove
$|u_{\operatorname{nn},\operatorname{test}}(T)-u^{*}_{\operatorname{ntk},\operatorname{test}}|\geq\epsilon$.

Using the similar idea, we can also show the equivalence for test data
predictors and the case of leverage score initialization. We refer to the
Appendix for a detailed proof sketch and rigorous proof.

######  Remark 4.2.

Our results can be naturally extended to multi-layer ReLU deep neural networks
with all parameters training together. Note the core of the connection between
regularized NNs and KRR is to show the similarity between their gradient
flows, as in Eq. (15), (16). The gradient flows consist of two terms: the
first term is from normal NN training without regularizer, whose similarity
has been shown in broader settings, e.g. [DZPS19, SY19, ADH+19a, AZLS19b,
AZLS19a]; the second term is from the $\ell_{2}$ regularizer, whose similarity
is true for multi-layer ReLU DNNs if the regularization parameter is divided
by the number of layers of parameters trained, due to the piecewise linearity
of the output with respect to the training parameters.

##  5 Conclusion

In this paper, we generalize the leverage score sampling theory for kernel
approximation. We discuss the interesting application of connecting leverage
score sampling and training regularized neural networks. We present two
theoretical results: 1) the equivalence between the regularized neural nets
and kernel ridge regression problems under the classical random Gaussian
initialization for both training and test predictors; 2) the new equivalence
under the leverage score initialization. We believe this work can be the
starting point of future study on the use of leverage score sampling in neural
network training.

##### Roadmap

In the appendix, we present our complete results and rigorous proofs. Section
A presents some well-known mathematically results that will be used in our
proof. Section B discusses our first equivalence result between training
regularized neural network and kernel ridge regression. Section C discusses
our generalization result of the leverage score sampling theory. Section D
discusses our second equivalence result under leverage score initialization
and potential benefits compared to the Gaussian initialization. Section E
discusses how to extend our results to a broader class of neural network
models.

## Appendix

##  Appendix A Preliminaries

###  A.1 Probability tools

In this section we introduce the probability tools we use in the proof.

We state Chernoff, Hoeffding and Bernstein inequalities.

######  Lemma A.1 (Chernoff bound [Che52]).

Let $X=\sum_{i=1}^{n}X_{i}$, where $X_{i}=1$ with probability $p_{i}$ and
$X_{i}=0$ with probability $1-p_{i}$, and all $X_{i}$ are independent. Let
$\mu=\operatorname*{{\mathbb{E}}}[X]=\sum_{i=1}^{n}p_{i}$. Then
1\. $\Pr[X\geq(1+\delta)\mu]\leq\exp(-\delta^{2}\mu/3)$, $\forall\delta>0$ ;
2\. $\Pr[X\leq(1-\delta)\mu]\leq\exp(-\delta^{2}\mu/2)$, $\forall 0<\delta<1$.

######  Lemma A.2 (Hoeffding bound [Hoe63]).

Let $X_{1},\cdots,X_{n}$ denote $n$ independent bounded variables in
$[a_{i},b_{i}]$. Let $X=\sum_{i=1}^{n}X_{i}$, then we have

$\displaystyle\Pr[|X-\operatorname*{{\mathbb{E}}}[X]|\geq t]\leq
2\exp\left(-\frac{2t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$

######  Lemma A.3 (Bernstein inequality [Ber24]).

Let $X_{1},\cdots,X_{n}$ be independent zero-mean random variables. Suppose
that $|X_{i}|\leq M$ almost surely, for all $i$. Then, for all positive $t$,

$\displaystyle\Pr\left[\sum_{i=1}^{n}X_{i}>t\right]\leq\exp\left(-\frac{t^{2}/2}{\sum_{j=1}^{n}\operatorname*{{\mathbb{E}}}[X_{j}^{2}]+Mt/3}\right).$

We state three inequalities for Gaussian random variables.

######  Lemma A.4 (Anti-concentration of Gaussian distribution).

Let $X\sim N(0,\sigma^{2})$, that is, the probability density function of $X$
is given by
$\phi(x)=\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{x^{2}}{2\sigma^{2}}}$. Then

$\displaystyle\Pr[|X|\leq
t]\in\left(\frac{2}{3}\frac{t}{\sigma},\frac{4}{5}\frac{t}{\sigma}\right).$

######  Lemma A.5 (Gaussian tail bounds).

Let $X\sim\mathcal{N}(\mu,\sigma^{2})$ be a Gaussian random variable with mean
$\mu$ and variance $\sigma^{2}$. Then for all $t\geq 0$, we have

$\displaystyle\Pr[|X-\mu|\geq t]\leq 2e^{-\frac{-t^{2}}{2\sigma^{2}}}.$

######  Lemma A.6 (Lemma 1 on page 1325 of Laurent and Massart [LM00]).

Let $X\sim{\cal X}_{k}^{2}$ be a chi-squared distributed random variable with
$k$ degrees of freedom. Each one has zero mean and $\sigma^{2}$ variance. Then

$\displaystyle\Pr[X-k\sigma^{2}\geq(2\sqrt{kt}+2t)\sigma^{2}]\leq\exp(-t),$
$\displaystyle\Pr[k\sigma^{2}-X\geq 2\sqrt{kt}\sigma^{2}]\leq\exp(-t).$

We state two inequalities for random matrices.

######  Lemma A.7 (Matrix Bernstein, Theorem 6.1.1 in [Tro15]).

Consider a finite sequence
$\\{X_{1},\cdots,X_{m}\\}\subset\mathbb{R}^{n_{1}\times n_{2}}$ of
independent, random matrices with common dimension $n_{1}\times n_{2}$. Assume
that

$\displaystyle\operatorname*{{\mathbb{E}}}[X_{i}]=0,\forall
i\in[m]\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\mathrm{and}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\|X_{i}\|\leq M,\forall i\in[m].$

Let $Z=\sum_{i=1}^{m}X_{i}$. Let $\mathrm{Var}[Z]$ be the matrix variance
statistic of sum:

$\displaystyle\mathrm{Var}[Z]=\max\left\\{\Big{\|}\sum_{i=1}^{m}\operatorname*{{\mathbb{E}}}[X_{i}X_{i}^{\top}]\Big{\|},\Big{\|}\sum_{i=1}^{m}\operatorname*{{\mathbb{E}}}[X_{i}^{\top}X_{i}]\Big{\|}\right\\}.$

Then

$\displaystyle\operatorname*{{\mathbb{E}}}[\|Z\|]\leq(2\mathrm{Var}[Z]\cdot\log(n_{1}+n_{2}))^{1/2}+M\cdot\log(n_{1}+n_{2})/3.$

Furthermore, for all $t\geq 0$,

$\displaystyle\Pr[\|Z\|\geq
t]\leq(n_{1}+n_{2})\cdot\exp\left(-\frac{t^{2}/2}{\mathrm{Var}[Z]+Mt/3}\right).$

######  Lemma A.8 (Matrix Bernstein, Lemma 7 in [AKM+17]).

Let $B\in\mathbb{R}^{d_{1}\times d_{2}}$ be a fixed matrix. Construct a random
matrix $R\in\mathbb{R}^{d_{1}\times d_{2}}$ satisfies

$\displaystyle\operatorname*{{\mathbb{E}}}[R]=B\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ \|R\|\leq L.$

Let $M_{1}$ and $M_{2}$ be semidefinite upper bounds for the expected squares:

$\displaystyle\operatorname*{{\mathbb{E}}}[RR^{\top}]\preceq
M_{1}\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}[R^{\top}R]\preceq M_{2}.$

Define the quantities

$\displaystyle m=\max\\{\|M_{1}\|,\|M_{2}\|\\}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\
d=(\operatorname{tr}[M_{1}]+\operatorname{tr}[M_{2}])/m.$

Form the matrix sampling estimator

$\displaystyle\overline{R}_{n}=\frac{1}{n}\sum_{k=1}^{n}R_{k}$

where each $R_{k}$ is an independent copy of $R$. Then, for all
$t\geq\sqrt{m/n}+2L/3n$,

$\displaystyle\Pr[\|\overline{R}_{n}-B\|_{2}\geq t]\leq
4d\exp{\Big{(}\frac{-nt^{2}}{m+2Lt/3}\Big{)}}$

###  A.2 Neural tangent kernel and its properties

######  Lemma A.9 (Lemma 4.1 in [SY19]).

We define $H^{\operatorname{cts}}$,
$H^{\operatorname{dis}}\in\mathbb{R}^{n\times n}$ as follows

$\displaystyle H^{\operatorname{cts}}_{i,j}=$
$\displaystyle\leavevmode\nobreak\ \operatorname*{{\mathbb{E}}}_{w\sim{\cal
N}(0,I)}[x_{i}^{\top}x_{j}{\bf 1}_{w^{\top}x_{i}\geq 0,w^{\top}x_{j}\geq 0}],$
$\displaystyle H^{\operatorname{dis}}_{i,j}=$
$\displaystyle\leavevmode\nobreak\
\frac{1}{m}\sum_{r=1}^{m}[x_{i}^{\top}x_{j}{\bf 1}_{w_{r}^{\top}x_{i}\geq
0,w_{r}^{\top}x_{j}\geq 0}].$

Let $\lambda=\lambda_{\min}(H^{\operatorname{cts}})$. If
$m=\Omega(\lambda^{-2}n^{2}\log(n/\delta))$, we have

$\displaystyle\|H^{\operatorname{dis}}-H^{\operatorname{cts}}\|_{F}\leq\frac{\lambda}{4},\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\lambda_{\min}(H^{\operatorname{dis}})\geq\frac{3}{4}\lambda$

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

######  Lemma A.10 (Lemma 4.2 in [SY19]).

Let $R\in(0,1)$. If $\widetilde{w}_{1},\cdots,\widetilde{w}_{m}$ are i.i.d.
generated from ${\cal N}(0,I)$. For any set of weight vectors
$w_{1},\cdots,w_{m}\in\mathbb{R}^{d}$ that satisfy for any $r\in[m]$,
$\|\widetilde{w}_{r}-w_{r}\|_{2}\leq R$, then the $H:\mathbb{R}^{m\times
d}\rightarrow\mathbb{R}^{n\times n}$ defined

$\displaystyle H(W)=\frac{1}{m}x_{i}^{\top}x_{j}\sum_{r=1}^{m}{\bf
1}_{w_{r}^{\top}x_{i}\geq 0,w_{r}^{\top}x_{j}\geq 0}.$

Then we have

$\displaystyle\|H(w)-H(\widetilde{w})\|_{F}<2nR$

holds with probability at least $1-n^{2}\cdot\exp(-mR/10)$.

##  Appendix B Equivalence between sufficiently wide neural net and kernel
ridge regression

In this section, we extend the equivalence result in [JGH18, ADH+19a] to the
case with regularization term, where they showed the equivalence between a
fully-trained infinitely wide/sufficiently wide neural net and the kernel
regression solution using the neural tangent kernel (NTK). Specifically, we
prove Theorem 3.6 and Theorem 3.7 in this section.

Section B.1 introduces key notations and standard data assumptions. Section
B.2 restates and supplements the definitions introduced in the paper. Section
B.3 presents several key lemmas about the gradient flow and linear convergence
of neural network and kernel ridge regression predictors, which are crucial to
the final proof. Section B.4 provides a brief proof sketch. Section B.5
restates the main equivalence Theorem 3.7 and provides a complete proof
following the proof sketch. Section B.6 restates and proves Theorem 3.6 by
showing it as a by-product of previous proof.

###  B.1 Preliminaries

Let’s define the following notations:

  * •

$X\in\mathbb{R}^{n\times d}$ be the training data

  * •

$x_{\operatorname{test}}\in\mathbb{R}^{d}$ be the test data

  * •

$u_{\operatorname{ntk}}(t)=\kappa
f_{\operatorname{ntk}}(\beta(t),X)=\kappa\Phi(X)\beta(t)\in\mathbb{R}^{n}$ be
the prediction of the kernel ridge regression for the training data at time
$t$. (See Definition B.5)

  * •

$u^{*}=\lim_{t\rightarrow\infty}u_{\operatorname{ntk}}(t)$ (See Eq. (24))

  * •

$u_{\operatorname{ntk},\operatorname{test}}(t)=\kappa
f_{\operatorname{ntk}}(\beta(t),x_{\operatorname{test}})=\kappa\Phi(x_{\operatorname{test}})\beta(t)\in\mathbb{R}$
be the prediction of the kernel ridge regression for the test data at time
$t$. (See Definition B.5)

  * •

$u_{\operatorname{test}}^{*}=\lim_{t\rightarrow\infty}u_{\operatorname{ntk},\operatorname{test}}(t)$
(See Eq. (25))

  * •

$\mathsf{K}_{\operatorname{ntk}}(x,y)=\operatorname*{{\mathbb{E}}}[\left\langle\frac{\partial
f_{\operatorname{nn}}(W,x)}{\partial W},\frac{\partial
f_{\operatorname{nn}}(W,y)}{\partial W}\right\rangle]$ (See Definition B.5)

  * •

$\mathsf{K}_{t}(x_{\operatorname{test}},X)\in\mathbb{R}^{n}$ be the induced
kernel between the training data and test data at time $t$, where

$\displaystyle[\mathsf{K}_{t}(x_{\operatorname{test}},X)]_{i}=\mathsf{K}_{t}(x_{\operatorname{test}},x_{i})=\left\langle\frac{\partial
f(W(t),x_{\operatorname{test}})}{\partial W(t)},\frac{\partial
f(W(t),x_{i})}{\partial W(t)}\right\rangle$

(see Definition B.6)

  * •

$u_{\operatorname{nn}}(t)=\kappa
f_{\operatorname{nn}}(W(t),X)\in\mathbb{R}^{n}$ be the prediction of the
neural network for the training data at time $t$. (See Definition B.3)

  * •

$u_{\operatorname{nn},\operatorname{test}}(t)=\kappa
f_{\operatorname{nn}}(W(t),x_{\operatorname{test}})\in\mathbb{R}$ be the
prediction of the neural network for the test data at time $t$ (See Definition
B.3)

######  Assumption B.1 (data assumption).

We made the following assumptions:
1\. For each $i\in[n]$, we assume $|y_{i}|=O(1)$.
2\. $H^{\operatorname{cts}}$ is positive definite, i.e.,
$\Lambda_{0}:=\lambda_{\min}(H^{\operatorname{cts}})>0$.
3\. All the training data and test data have Euclidean norm equal to 1.

###  B.2 Definitions

To establish the equivalence between neural network and kernel ridge
regression, we prove the similarity of their gradient flow and initial
predictor. Note kernel ridge regression starts at 0 as initialization, so we
hope the initialization of neural network also close to zero. Therefore, using
the same technique in [ADH+19a], we apply a small multiplier $\kappa>0$ to
both predictors to bound the different of initialization.

######  Definition B.2 (Neural network function).

We define a two layer neural networks with rectified linear unit (ReLU)
activation as the following form

$\displaystyle
f_{\operatorname{nn}}(W,a,x)=\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\sigma(w_{r}^{\top}x)\in\mathbb{R},$

where $x\in\mathbb{R}^{d}$ is the input,
$w_{r}\in\mathbb{R}^{d},\leavevmode\nobreak\ r\in[m]$ is the weight vector of
the first layer, $W=[w_{1},\cdots,w_{m}]\in\mathbb{R}^{d\times m}$,
$a_{r}\in\mathbb{R},\leavevmode\nobreak\ r\in[m]$ is the output weight,
$a=[a_{1},\cdots,a_{m}]^{\top}$ and $\sigma(\cdot)$ is the ReLU activation
function: $\sigma(z)=\max\\{0,z\\}$. In this paper, we consider only training
the first layer $W$ while fix $a$. So we also write
$f_{\operatorname{nn}}(W,x)=f_{\operatorname{nn}}(W,a,x)$. We denote
$f_{\operatorname{nn}}(W,X)=[f_{\operatorname{nn}}(W,x_{1}),\cdots,f_{\operatorname{nn}}(W,x_{n})]^{\top}\in\mathbb{R}^{n}$.

######  Definition B.3 (Training neural network with regularization,
restatement of Definition 3.5).

Given training data matrix $X\in\mathbb{R}^{n\times d}$ and corresponding
label vector $Y\in\mathbb{R}^{n}$. Let $f_{\operatorname{nn}}$ be defined as
in Definition B.2. Let $\kappa\in(0,1)$ be a small multiplier. Let
$\lambda\in(0,1)$ be the regularization parameter. We initialize the network
as $a_{r}\overset{i.i.d.}{\sim}\operatorname{unif}[\\{-1,1\\}]$ and
$w_{r}(0)\overset{i.i.d.}{\sim}\mathcal{N}(0,I_{d})$. Then we consider solving
the following optimization problem using gradient descent:

$\displaystyle\min_{W}\frac{1}{2}\|Y-\kappa
f_{\operatorname{nn}}(W,X)\|_{2}+\frac{1}{2}\lambda\|W\|_{F}^{2}.$ (17)

We denote $w_{r}(t),r\in[m]$ as the variable at iteration $t$. We denote

$\displaystyle u_{\operatorname{nn}}(t)=\kappa
f_{\operatorname{nn}}(W(t),X)=\frac{\kappa}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\sigma(w_{r}(t)^{\top}X)\in\mathbb{R}^{n}$
(18)

as the training data predictor at iteration $t$. Given any test data
$x_{\operatorname{test}}\in\mathbb{R}^{d}$, we denote

$\displaystyle u_{\operatorname{nn},\operatorname{test}}(t)=\kappa
f_{\operatorname{nn}}(W(t),x_{\operatorname{test}})=\frac{\kappa}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\sigma(w_{r}(t)^{\top}x_{\operatorname{test}})\in\mathbb{R}$
(19)

as the test data predictor at iteration $t$.

######  Definition B.4 (Neural tangent kernel and feature function).

We define the neural tangent kernel(NTK) and the feature function
corresponding to the neural networks $f_{\operatorname{nn}}$ defined in
Definition B.2 as following

$\displaystyle\mathsf{K}_{\operatorname{ntk}}(x,z)=\operatorname*{{\mathbb{E}}}\left[\left\langle\frac{\partial
f_{\operatorname{nn}}(W,x)}{\partial W},\frac{\partial
f_{\operatorname{nn}}(W,z)}{\partial W}\right\rangle\right]$

where $x,z\in\mathbb{R}^{d}$ are any input data, and the expectation is taking
over $w_{r}\overset{i.i.d.}{\sim}\mathcal{N}(0,I),\leavevmode\nobreak\
r=1,\cdots,m$. Given training data matrix
$X=[x_{1},\cdots,x_{n}]^{\top}\in\mathbb{R}^{n\times d}$, we define
$H^{\operatorname{cts}}\in\mathbb{R}^{n\times n}$ as the kernel matrix between
training data as

$\displaystyle[H^{\operatorname{cts}}]_{i,j}=\mathsf{K}_{\operatorname{ntk}}(x_{i},x_{j})\in\mathbb{R}.$

We denote the smallest eigenvalue of $H^{\operatorname{cts}}$ as
$\Lambda_{0}>0$, where we assume $H^{\operatorname{cts}}$ is positive
definite. Further, given any data $z\in\mathbb{R}^{d}$, we write the kernel
between test and training data
$\mathsf{K}_{\operatorname{ntk}}(z,X)\in\mathbb{R}^{n}$ as

$\displaystyle\mathsf{K}_{\operatorname{ntk}}(z,X)=[\mathsf{K}_{\operatorname{ntk}}(z,x_{1}),\cdots,\mathsf{K}_{\operatorname{ntk}}(z,x_{n})]^{\top}\in\mathbb{R}^{n}.$

We denote the feature function corresponding to the kernel
$\mathsf{K}_{\operatorname{ntk}}$ as we defined above as
$\Phi:\mathbb{R}^{d}\rightarrow\mathcal{F}$, which satisfies

$\displaystyle\langle\Phi(x),\Phi(z)\rangle_{\mathcal{F}}=\mathsf{K}_{\operatorname{ntk}}(x,z),$

for any data $x$, $z\in\mathbb{R}^{d}$. And we write
$\Phi(X)=[\Phi(x_{1}),\cdots,\Phi(x_{n})]^{\top}$.

######  Definition B.5 (Neural tangent kernel ridge regression).

Given training data matrix $X=[x_{1},\cdots,x_{n}]^{\top}$
$\in\mathbb{R}^{n\times d}$ and corresponding label vector
$Y\in\mathbb{R}^{n}$. Let $\mathsf{K}_{\operatorname{ntk}}$,
$H^{\operatorname{cts}}\in\mathbb{R}^{n\times n}$ and $\Phi$ be the neural
tangent kernel and corresponding feature functions defined as in Definition
B.4. Let $\kappa\in(0,1)$ be a small multiplier. Let $\lambda\in(0,1)$ be the
regularization parameter. Then we consider the following neural tangent kernel
ridge regression problem:

$\displaystyle\min_{\beta}\frac{1}{2}\|Y-\kappa
f_{\operatorname{ntk}}(\beta,X)\|_{2}^{2}+\frac{1}{2}\lambda\|\beta\|_{2}^{2}.$
(20)

where $f_{\operatorname{ntk}}(\beta,x)=\Phi(x)^{\top}\beta\in\mathbb{R}$
denotes the prediction function is corresponding RKHS and
$f_{\operatorname{ntk}}(\beta,X)=[f_{\operatorname{ntk}}(\beta,x_{1}),\cdots,f_{\operatorname{ntk}}(\beta,x_{n})]^{\top}\in\mathbb{R}^{n}$.
Consider the gradient flow of solving problem (20) with initialization
$\beta(0)=0$. We denote $\beta(t)$ as the variable at iteration $t$. We denote

$\displaystyle
u_{\operatorname{ntk}}(t)=\kappa\Phi(X)\beta(t)\in\mathbb{R}^{n}$ (21)

as the training data predictor at iteration $t$. Given any test data
$x_{\operatorname{test}}\in\mathbb{R}^{d}$, we denote

$\displaystyle
u_{\operatorname{ntk},\operatorname{test}}(t)=\kappa\Phi(x_{\operatorname{test}})^{\top}\beta(t)\in\mathbb{R}$
(22)

as the test data predictor at iteration $t$. Note the gradient flow converge
the to optimal solution of problem (20) due to the strongly convexity of the
problem. We denote

$\displaystyle\beta^{*}=\lim_{t\to\infty}\beta(t)=\kappa(\kappa^{2}\Phi(X)^{\top}\Phi(X)+\lambda
I)^{-1}\Phi(X)^{\top}Y$ (23)

and the optimal training data predictor

$\displaystyle
u^{*}=\lim_{t\to\infty}u_{\operatorname{ntk}}(t)=\kappa\Phi(X)\beta^{*}=\kappa^{2}H^{\operatorname{cts}}(\kappa^{2}H^{\operatorname{cts}}+\lambda
I)^{-1}Y\in\mathbb{R}^{n}$ (24)

and the optimal test data predictor

$\displaystyle
u_{\operatorname{test}}^{*}=\lim_{t\to\infty}u_{\operatorname{ntk},\operatorname{test}}(t)=\kappa\Phi(x_{\operatorname{test}})^{\top}\beta^{*}=\kappa^{2}\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)^{\top}(\kappa^{2}H^{\operatorname{cts}}+\lambda
I)^{-1}Y\in\mathbb{R}.$ (25)

######  Definition B.6 (Dynamic kernel).

Given $W(t)\in\mathbb{R}^{d\times m}$ as the parameters of the neural network
at training time $t$ as defined in Definition B.3. For any data
$x,z\in\mathbb{R}^{d}$, we define $\mathsf{K}_{t}(x,z)\in\mathbb{R}$ as

$\displaystyle\mathsf{K}_{t}(x,z)=\left\langle\frac{\mathrm{d}f_{\operatorname{nn}}(W(t),x)}{\mathrm{d}W(t)},\frac{\mathrm{d}f_{\operatorname{nn}}(W(t),z)}{\mathrm{d}W(t)}\right\rangle$

Given training data matrix
$X=[x_{1},\cdots,x_{n}]^{\top}\in\mathbb{R}^{n\times d}$, we define
$H^{(t)}\in\mathbb{R}^{n\times n}$ as

$\displaystyle[H(t)]_{i,j}=\mathsf{K}_{t}(x_{i},x_{j})\in\mathbb{R}.$

Further, given a test data $x_{\operatorname{test}}\in\mathbb{R}^{d}$, we
define $\mathsf{K}_{t}(x_{\operatorname{test}},X)\in\mathbb{R}^{n}$ as

$\displaystyle\mathsf{K}_{t}(x_{\operatorname{test}},X)=[\mathsf{K}_{t}(x_{\operatorname{test}},x_{1}),\cdots,\mathsf{K}_{t}(x_{\operatorname{test}},x_{n})]^{\top}\in\mathbb{R}^{n}.$

###  B.3 Gradient, gradient flow, and linear convergence

######  Lemma B.7 (Gradient flow of kernel ridge regression).

Given training data matrix $X\in\mathbb{R}^{n\times d}$ and corresponding
label vector $Y\in\mathbb{R}^{n}$. Let $f_{\operatorname{ntk}}$ be defined as
in Definition B.5. Let $\beta(t)$, $\kappa\in(0,1)$ and
$u_{\operatorname{ntk}}(t)\in\mathbb{R}^{n}$ be defined as in Definition B.5.
Let $\mathsf{K}_{\operatorname{ntk}}:\mathbb{R}^{d}\times\mathbb{R}^{n\times
d}\to\mathbb{R}^{n}$ be defined as in Definition B.4. Then for any data
$z\in\mathbb{R}^{d}$, we have

$\displaystyle\frac{\mathrm{d}f_{\operatorname{ntk}}(\beta(t),z)}{\mathrm{d}t}=\kappa\cdot\mathsf{K}_{\operatorname{ntk}}(z,X)^{\top}(Y-u_{\operatorname{ntk}}(t))-\lambda\cdot
f_{\operatorname{ntk}}(\beta(t),z).$

###### Proof.

Denote
$L(t)=\frac{1}{2}\|Y-u_{\operatorname{ntk}}(t)\|_{2}^{2}+\frac{1}{2}\lambda\|\beta(t)\|_{2}^{2}$.
By the rule of gradient descent, we have

$\displaystyle\frac{\mathrm{d}\beta(t)}{\mathrm{d}t}=-\frac{\mathrm{d}L}{\mathrm{d}\beta}=\kappa\Phi(X)^{\top}(Y-u_{\operatorname{ntk}}(t))-\lambda\beta(t),$

where $\Phi$ is defined in Definition B.4. Thus we have

$\displaystyle\frac{\mathrm{d}f_{\operatorname{ntk}}(\beta(t),z)}{\mathrm{d}t}=$
$\displaystyle\leavevmode\nobreak\
\frac{\mathrm{d}f_{\operatorname{ntk}}(\beta(t),z)}{\mathrm{d}\beta(t)}\frac{\mathrm{d}\beta(t)}{\mathrm{d}t}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\Phi(z)^{\top}(\kappa\Phi(X)^{\top}(Y-u_{\operatorname{ntk}}(t))-\lambda\beta(t))$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\kappa\mathsf{K}_{\operatorname{ntk}}(z,X)^{\top}(Y-u_{\operatorname{ntk}}(t))-\lambda\Phi(z)^{\top}\beta(t)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\kappa\mathsf{K}_{\operatorname{ntk}}(z,X)^{\top}(Y-u_{\operatorname{ntk}}(t))-\lambda
f_{\operatorname{ntk}}(\beta(t),z),$

where the first step is due to chain rule, the second step follows from the
fact $\mathrm{d}f_{\operatorname{ntk}}(\beta,z)/\mathrm{d}\beta=\Phi(z)$, the
third step is due to the definition of the kernel
$\mathsf{K}_{\operatorname{ntk}}(z,X)=\Phi(X)\Phi(z)\in\mathbb{R}^{n}$, and
the last step is due to the definition of
$f_{\operatorname{ntk}}(\beta(t),z)\in\mathbb{R}$. ∎

######  Corollary B.8 (Gradient of prediction of kernel ridge regression).

Given training data matrix
$X=[x_{1},\cdots,x_{n}]^{\top}\in\mathbb{R}^{n\times d}$ and corresponding
label vector $Y\in\mathbb{R}^{n}$. Given a test data
$x_{\operatorname{test}}\in\mathbb{R}^{d}$. Let $f_{\operatorname{ntk}}$ be
defined as in Definition B.5. Let $\beta(t)$, $\kappa\in(0,1)$ and
$u_{\operatorname{ntk}}(t)\in\mathbb{R}^{n}$ be defined as in Definition B.5.
Let $\mathsf{K}_{\operatorname{ntk}}:\mathbb{R}^{d}\times\mathbb{R}^{n\times
d}\rightarrow\mathbb{R}^{n},\leavevmode\nobreak\
H^{\operatorname{cts}}\in\mathbb{R}^{n\times n}$ be defined as in Definition
B.4. Then we have

$\displaystyle\frac{\mathrm{d}u_{\operatorname{ntk}}(t)}{\mathrm{d}t}$
$\displaystyle=\kappa^{2}H^{\operatorname{cts}}(Y-u_{\operatorname{ntk}}(t))-\lambda\cdot
u_{\operatorname{ntk}}(t)$
$\displaystyle\frac{\mathrm{d}u_{\operatorname{ntk},\operatorname{test}}(t)}{\mathrm{d}t}$
$\displaystyle=\kappa^{2}\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)^{\top}(Y-u_{\operatorname{ntk}}(t))-\lambda\cdot
u_{\operatorname{ntk},\operatorname{test}}(t).$

###### Proof.

Plugging in $z=x_{i}\in\mathbb{R}^{d}$ in Lemma B.7, we have

$\displaystyle\frac{\mathrm{d}f_{\operatorname{ntk}}(\beta(t),x_{i})}{\mathrm{d}t}=\kappa\mathsf{K}_{\operatorname{ntk}}(x_{i},X)^{\top}(Y-u_{\operatorname{ntk}}(t))-\lambda\cdot
f_{\operatorname{ntk}}(\beta(t),x_{i}).$

Note $[u_{\operatorname{ntk}}(t)]_{i}=\kappa
f_{\operatorname{ntk}}(\beta(t),x_{i})$ and
$[H^{\operatorname{cts}}]_{:,i}=\mathsf{K}_{\operatorname{ntk}}(x_{i},X)$, so
writing all the data in a compact form, we have

$\displaystyle\frac{\mathrm{d}u_{\operatorname{ntk}}(t)}{\mathrm{d}t}=\kappa^{2}H^{\operatorname{cts}}(Y-u_{\operatorname{ntk}}(t))-\lambda\cdot
u_{\operatorname{ntk}}(t).$

Plugging in data $z=x_{\operatorname{test}}\in\mathbb{R}^{d}$ in Lemma B.7, we
have

$\displaystyle\frac{\mathrm{d}f_{\operatorname{ntk}}(\beta(t),x_{\operatorname{test}})}{\mathrm{d}t}=\kappa\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)^{\top}(Y-u_{\operatorname{ntk}}(t))-\lambda\cdot
f_{\operatorname{ntk}}(\beta(t),x_{\operatorname{test}}).$

Note by definition, $u_{\operatorname{ntk},\operatorname{test}}(t)=\kappa
f_{\operatorname{ntk}}(\beta(t),x_{\operatorname{test}})\in\mathbb{R}$, so we
have

$\displaystyle\frac{\mathrm{d}u_{\operatorname{ntk},\operatorname{test}}(t)}{\mathrm{d}t}=\kappa^{2}\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)^{\top}(Y-u_{\operatorname{ntk}}(t))-\lambda\cdot
u_{\operatorname{ntk},\operatorname{test}}(t).$

∎

######  Lemma B.9 (Linear convergence of kernel ridge regression).

Given training data matrix
$X=[x_{1},\cdots,x_{n}]^{\top}\in\mathbb{R}^{n\times d}$ and corresponding
label vector $Y\in\mathbb{R}^{n}$. Let $\kappa\in(0,1)$ and
$u_{\operatorname{ntk}}(t)\in\mathbb{R}^{n}$ be defined as in Definition B.5.
Let $u^{*}\in\mathbb{R}^{n}$ be defined in Definition B.5. Let $\Lambda_{0}>0$
be defined as in Definition B.4. Let $\lambda>0$ be the regularization
parameter. Then we have

$\displaystyle\frac{\mathrm{d}\|u_{\operatorname{ntk}}(t)-u^{*}\|_{2}^{2}}{\mathrm{d}t}\leq-2(\kappa^{2}\Lambda_{0}+\lambda)\|u_{\operatorname{ntk}}(t)-u^{*}\|_{2}^{2}.$

Further, we have

$\displaystyle\|u_{\operatorname{ntk}}(t)-u^{*}\|_{2}\leq
e^{-(\kappa^{2}\Lambda_{0}+\lambda)t}\|u_{\operatorname{ntk}}(0)-u^{*}\|_{2}.$

###### Proof.

Let $H^{\operatorname{cts}}\in\mathbb{R}^{n\times n}$ be defined as in
Definition B.4. Then

$\displaystyle\kappa^{2}H^{\operatorname{cts}}(Y-u^{*})=$
$\displaystyle\leavevmode\nobreak\
\kappa^{2}H^{\operatorname{cts}}(Y-\kappa^{2}H^{\operatorname{cts}}(\kappa^{2}H^{\operatorname{cts}}+\lambda
I_{n})^{-1}Y)$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}H^{\operatorname{cts}}(I_{n}-\kappa^{2}H^{\operatorname{cts}}(\kappa^{2}H^{\operatorname{cts}}+\lambda
I)^{-1})Y$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}H^{\operatorname{cts}}(\kappa^{2}H^{\operatorname{cts}}+\lambda
I_{n}-\kappa^{2}H^{\operatorname{cts}})(\kappa^{2}H^{\operatorname{cts}}+\lambda
I_{n})^{-1}Y$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}\lambda
H^{\operatorname{cts}}(\kappa^{2}H^{\operatorname{cts}}+\lambda I_{n})^{-1}Y$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ \lambda u^{*},$ (26)

where the first step follows the definition of $u^{*}\in\mathbb{R}^{n}$, the
second to fourth step simplify the formula, and the last step use the
definition of $u^{*}\in\mathbb{R}^{n}$ again. So we have

$\displaystyle\frac{\mathrm{d}\|u_{\operatorname{ntk}}(t)-u^{*}\|_{2}^{2}}{\mathrm{d}t}=$
$\displaystyle\leavevmode\nobreak\
2(u_{\operatorname{ntk}}(t)-u^{*})^{\top}\frac{\mathrm{d}u_{\operatorname{ntk}}(t)}{\mathrm{d}t}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
-2\kappa^{2}(u_{\operatorname{ntk}}(t)-u^{*})^{\top}H^{\operatorname{cts}}(u_{\operatorname{ntk}}(t)-Y)-2\lambda(u_{\operatorname{ntk}}(t)-u^{*})^{\top}u_{\operatorname{ntk}}(t)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
-2\kappa^{2}(u_{\operatorname{ntk}}(t)-u^{*})^{\top}H^{\operatorname{cts}}(u_{\operatorname{ntk}}(t)-u^{*})+2\kappa^{2}(u_{\operatorname{ntk}}(t)-u^{*})^{\top}H^{\operatorname{cts}}(Y-u^{*})$
$\displaystyle\leavevmode\nobreak\
-2\lambda(u_{\operatorname{ntk}}(t)-u^{*})^{\top}u_{\operatorname{ntk}}(t)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
-2\kappa^{2}(u_{\operatorname{ntk}}(t)-u^{*})^{\top}H^{\operatorname{cts}}(u_{\operatorname{ntk}}(t)-u^{*})+2\lambda(u_{\operatorname{ntk}}(t)-u^{*})^{\top}u^{*}$
$\displaystyle\leavevmode\nobreak\
-2\lambda(u_{\operatorname{ntk}}(t)-u^{*})^{\top}u_{\operatorname{ntk}}(t)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
-2(u_{\operatorname{ntk}}(t)-u^{*})^{\top}(\kappa^{2}H^{\operatorname{cts}}+\lambda
I)(u_{\operatorname{ntk}}(t)-u^{*})$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
-2(\kappa^{2}\Lambda_{0}+\lambda)\|u_{\operatorname{ntk}}(t)-u^{*}\|_{2}^{2},$
(27)

where the first step follows the chain rule, the second step follows Corollary
B.8, the third step uses basic linear algebra, the fourth step follows Eq.
(B.3), the fifth step simplifies the expression, and the last step follows the
definition of $\Lambda_{0}$. Further, since

$\displaystyle\leavevmode\nobreak\
\frac{\mathrm{d}(e^{2(\kappa^{2}\Lambda_{0}+\lambda)t}\|u_{\operatorname{ntk}}(t)-u^{*}\|_{2}^{2})}{\mathrm{d}t}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
2(\kappa^{2}\Lambda_{0}+\lambda)e^{2(\kappa^{2}\Lambda_{0}+\lambda)t}\|u_{\operatorname{ntk}}(t)-u^{*}\|_{2}^{2}+e^{2(\kappa^{2}\Lambda_{0}+\lambda)t}\cdot\frac{\mathrm{d}\|u_{\operatorname{ntk}}(t)-u^{*}\|_{2}^{2}}{\mathrm{d}t}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ 0,$

where the first step calculates the gradient, and the second step follows from
Eq. (B.3). Thus,
$e^{2(\kappa^{2}\Lambda_{0}+\lambda)t}\|u_{\operatorname{ntk}}(t)-u^{*}\|_{2}^{2}$
is non-increasing, which implies

$\displaystyle\|u_{\operatorname{ntk}}(t)-u^{*}\|_{2}\leq
e^{-(\kappa^{2}\Lambda_{0}+\lambda)t}\|u_{\operatorname{ntk}}(0)-u^{*}\|_{2}.$

∎

######  Lemma B.10 (Gradient flow of neural network training).

Given training data matrix $X\in\mathbb{R}^{n\times d}$ and corresponding
label vector $Y\in\mathbb{R}^{n}$. Let
$f_{\operatorname{nn}}:\mathbb{R}^{d\times
m}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as in Definition B.2.
Let $W(t)\in\mathbb{R}^{d\times m}$, $\kappa\in(0,1)$ and
$u_{\operatorname{nn}}(t)\in\mathbb{R}^{n}$ be defined as in Definition B.3.
Let $\mathsf{K}_{t}:\mathbb{R}^{d}\times\mathbb{R}^{n\times
d}\rightarrow\mathbb{R}^{n}$ be defined as in Definition B.6. Then for any
data $z\in\mathbb{R}^{d}$, we have

$\displaystyle\frac{\mathrm{d}f_{\operatorname{nn}}(W(t),z)}{\mathrm{d}t}=\kappa\mathsf{K}_{t}(z,X)^{\top}(Y-u_{\operatorname{nn}}(t))-\lambda\cdot
f_{\operatorname{nn}}(W(t),z).$

###### Proof.

Denote
$L(t)=\frac{1}{2}\|Y-u_{\operatorname{nn}}(t)\|_{2}^{2}+\frac{1}{2}\lambda\|W(t)\|_{F}^{2}$.
By the rule of gradient descent, we have

$\displaystyle\frac{\mathrm{d}w_{r}}{\mathrm{d}t}=-\frac{\partial L}{\partial
w_{r}}=(\frac{\partial u_{\operatorname{nn}}}{\partial
w_{r}})^{\top}(Y-u_{\operatorname{nn}})-\lambda w_{r}.$ (28)

Also note for ReLU activation $\sigma$, we have

$\displaystyle\Big{\langle}\frac{\mathrm{d}f_{\operatorname{nn}}(W(t),z)}{\mathrm{d}W(t)},\lambda
W(t)\Big{\rangle}=$ $\displaystyle\leavevmode\nobreak\
\sum_{r=1}^{m}\Big{(}\frac{1}{\sqrt{m}}a_{r}z\sigma^{\prime}(w_{r}(t)^{\top}z)\Big{)}^{\top}(\lambda
w_{r}(t))$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{\lambda}{\sqrt{m}}\sum_{r=1}^{m}a_{r}w_{r}(t)^{\top}z\sigma^{\prime}(w_{r}(t)^{\top}z)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{\lambda}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\sigma(w_{t}(t)^{\top}z)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ \lambda
f_{\operatorname{nn}}(W(t),z),$ (29)

where the first step calculates the derivatives, the second step follows basic
linear algebra, the third step follows the property of ReLU activation:
$\sigma(l)=l\sigma^{\prime}(l)$, and the last step follows from the definition
of $f_{\operatorname{nn}}$. Thus, we have

$\displaystyle\leavevmode\nobreak\
\frac{\mathrm{d}f_{\operatorname{nn}}(W(t),z)}{\mathrm{d}t}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\Big{\langle}\frac{\mathrm{d}f_{\operatorname{nn}}(W(t),z)}{\mathrm{d}W(t)},\frac{\mathrm{d}W(t)}{\mathrm{d}t}\Big{\rangle}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\sum_{j=1}^{n}(y_{j}-\kappa
f_{\operatorname{nn}}(W(t),x_{j}))\Big{\langle}\frac{\mathrm{d}f_{\operatorname{nn}}(W(t),z)}{\mathrm{d}W(t)},\frac{\mathrm{d}\kappa
f_{\operatorname{nn}}(W(t),x_{j})}{\mathrm{d}W(t)}\Big{\rangle}-\Big{\langle}\frac{\mathrm{d}f_{\operatorname{nn}}(W(t),z)}{\mathrm{d}W(t)},\lambda
W(t)\Big{\rangle}$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\kappa\sum_{j=1}^{n}(y_{j}-\kappa
f_{\operatorname{nn}}(W(t),x_{j}))\mathsf{K}_{t}(z,x_{j})-\lambda\cdot
f_{\operatorname{nn}}(W(t),z)$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\kappa\mathsf{K}_{t}(z,X)^{\top}(Y-u_{\operatorname{nn}}(t))-\lambda\cdot
f_{\operatorname{nn}}(W(t),z),$

where the first step follows from chain rule, the second step follows from Eq.
(28), the third step follows from the definition of $\mathsf{K}_{t}$ and Eq.
(B.3), and the last step rewrites the formula in a compact form. ∎

######  Corollary B.11 (Gradient of prediction of neural network).

Given training data matrix
$X=[x_{1},\cdots,x_{n}]^{\top}\in\mathbb{R}^{n\times d}$ and corresponding
label vector $Y\in\mathbb{R}^{n}$. Given a test data
$x_{\operatorname{test}}\in\mathbb{R}^{d}$. Let
$f_{\operatorname{nn}}:\mathbb{R}^{d\times
m}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$ be defined as in Definition B.2.
Let $W(t)\in\mathbb{R}^{d\times m}$, $\kappa\in(0,1)$ and
$u_{\operatorname{nn}}(t)\in\mathbb{R}^{n}$ be defined as in Definition B.3.
Let $\mathsf{K}_{t}:\mathbb{R}^{d}\times\mathbb{R}^{n\times
d}\rightarrow\mathbb{R}^{n},\leavevmode\nobreak\ H(t)\in\mathbb{R}^{n\times
n}$ be defined as in Definition B.6. Then we have

$\displaystyle\frac{\mathrm{d}u_{\operatorname{nn}}(t)}{\mathrm{d}t}=$
$\displaystyle\leavevmode\nobreak\
\kappa^{2}H(t)(Y-u_{\operatorname{nn}}(t))-\lambda\cdot
u_{\operatorname{nn}}(t)$
$\displaystyle\frac{\mathrm{d}u_{\operatorname{nn},\operatorname{test}}(t)}{\mathrm{d}t}=$
$\displaystyle\leavevmode\nobreak\
\kappa^{2}\mathsf{K}_{t}(x_{\operatorname{test}},X)^{\top}(Y-u_{\operatorname{nn}}(t))-\lambda\cdot
u_{\operatorname{nn},\operatorname{test}}(t).$

###### Proof.

Plugging in $z=x_{i}\in\mathbb{R}^{d}$ in Lemma B.10, we have

$\displaystyle\frac{\mathrm{d}f_{\operatorname{nn}}(W(t),x_{i})}{\mathrm{d}t}=\kappa\mathsf{K}_{t}(x_{i},X)^{\top}(Y-u_{\operatorname{nn}}(t))-\lambda\cdot
f_{\operatorname{nn}}(W(t),x_{i}).$

Note $[u_{\operatorname{nn}}(t)]_{i}=\kappa f_{\operatorname{nn}}(W(t),x_{i})$
and $[H(t))]_{:,i}=\mathsf{K}_{t}(x_{i},X)$, so writing all the data in a
compact form, we have

$\displaystyle\frac{\mathrm{d}u_{\operatorname{nn}}(t)}{\mathrm{d}t}=\kappa^{2}H(t)(Y-u_{\operatorname{nn}}(t))-\lambda\cdot
u_{\operatorname{nn}}(t).$

Plugging in data $z=x_{\operatorname{test}}\in\mathbb{R}^{d}$ in Lemma B.10,
we have

$\displaystyle\frac{\mathrm{d}f_{\operatorname{nn}}(W(t),x_{\operatorname{test}})}{\mathrm{d}t}=\kappa\mathsf{K}_{t}(x_{\operatorname{test}},X)^{\top}(Y-u_{\operatorname{nn}}(t))-\lambda\cdot
f_{\operatorname{nn}}(W(t),x_{\operatorname{test}}).$

Note by definition, $u_{\operatorname{nn},\operatorname{test}}(t)=\kappa
f_{\operatorname{nn}}(W(t),x_{\operatorname{test}})$, so we have

$\displaystyle\frac{\mathrm{d}u_{\operatorname{nn},\operatorname{test}}(t)}{\mathrm{d}t}=\kappa^{2}\mathsf{K}_{t}(x_{\operatorname{test}},X)^{\top}(Y-u_{\operatorname{nn}}(t))-\lambda\cdot
u_{\operatorname{nn},\operatorname{test}}(t).$

∎

######  Lemma B.12 (Linear convergence of neural network training).

Given training data matrix
$X=[x_{1},\cdots,x_{n}]^{\top}\in\mathbb{R}^{n\times d}$ and corresponding
label vector $Y\in\mathbb{R}^{n}$. Fix the total number of iterations $T>0$.
Let , $\kappa\in(0,1)$ and $u_{\operatorname{nn}}(t)\in\mathbb{R}^{n\times n}$
be defined as in Definition B.3. Let $u^{*}\in\mathbb{R}^{n}$ be defined in
Eq. (24). Let $H^{\operatorname{cts}}\in\mathbb{R}^{n\times n}$ and
$\Lambda_{0}>0$ be defined as in Definition B.4. Let
$H(t)\in\mathbb{R}^{n\times n}$ be defined as in Definition B.6. Let
$\lambda>0$ be the regularization parameter. Assume
$\|H(t)-H^{\operatorname{cts}}\|\leq\Lambda_{0}/2$ holds for all $t\in[0,T]$.
Then we have

$\displaystyle\frac{\mathrm{d}\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}^{2}}{\mathrm{d}t}\leq-(\kappa^{2}\Lambda_{0}+\lambda)\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}^{2}+2\kappa^{2}\|H(t)-H^{\operatorname{cts}}\|\cdot\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}\cdot\|Y-u^{*}\|_{2}.$

###### Proof.

Note same as in Lemma B.9, we have

$\displaystyle\kappa^{2}H^{\operatorname{cts}}(Y-u^{*})=$
$\displaystyle\leavevmode\nobreak\
\kappa^{2}H^{\operatorname{cts}}(Y-\kappa^{2}H^{\operatorname{cts}}(\kappa^{2}H^{\operatorname{cts}}+\lambda
I_{n})^{-1}Y)$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}H^{\operatorname{cts}}(I_{n}-\kappa^{2}H^{\operatorname{cts}}(\kappa^{2}H^{\operatorname{cts}}+\lambda
I)^{-1})Y$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}H^{\operatorname{cts}}(\kappa^{2}H^{\operatorname{cts}}+\lambda
I_{n}-\kappa^{2}H^{\operatorname{cts}})(\kappa^{2}H^{\operatorname{cts}}+\lambda
I_{n})^{-1}Y$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}\lambda
H^{\operatorname{cts}}(\kappa^{2}H^{\operatorname{cts}}+\lambda I_{n})^{-1}Y$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ \lambda u^{*},$ (30)

where the first step follows the definition of $u^{*}\in\mathbb{R}^{n}$, the
second to fourth step simplify the formula, and the last step use the
definition of $u^{*}\in\mathbb{R}^{n}$ again. Thus, we have

$\displaystyle\leavevmode\nobreak\
\frac{\mathrm{d}\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}^{2}}{\mathrm{d}t}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
2(u_{\operatorname{nn}}(t)-u^{*})^{\top}\frac{\mathrm{d}u_{\operatorname{nn}}(t)}{\mathrm{d}t}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
-2\kappa^{2}(u_{\operatorname{nn}}(t)-u^{*})^{\top}H(t)(u_{\operatorname{nn}}(t)-Y)-2\lambda(u_{\operatorname{nn}}(t)-u^{*})^{\top}u_{\operatorname{nn}}(t)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
-2\kappa^{2}(u_{\operatorname{nn}}(t)-u^{*})^{\top}H(t)(u_{\operatorname{nn}}(t)-u^{*})+2\kappa^{2}(u_{\operatorname{nn}}(t)-u^{*})^{\top}H^{\operatorname{cts}}(Y-u^{*})$
$\displaystyle\leavevmode\nobreak\
+2\kappa^{2}(u_{\operatorname{nn}}(t)-u^{*})^{\top}(H(t)-H^{\operatorname{cts}})(Y-u^{*})-2\lambda(u_{\operatorname{nn}}(t)-u^{*})^{\top}u_{\operatorname{nn}}(t)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
-2\kappa^{2}(u_{\operatorname{nn}}(t)-u^{*})^{\top}H(t)(u_{\operatorname{nn}}(t)-u^{*})+2\lambda(u_{\operatorname{nn}}(t)-u^{*})^{\top}u^{*}$
$\displaystyle\leavevmode\nobreak\
+2\kappa^{2}(u_{\operatorname{nn}}(t)-u^{*})^{\top}(H(t)-H^{\operatorname{cts}})(Y-u^{*})-2\lambda(u_{\operatorname{nn}}(t)-u^{*})^{\top}u_{\operatorname{nn}}(t)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
-2(u_{\operatorname{nn}}(t)-u^{*})^{\top}(\kappa^{2}H(t)+\lambda
I)(u_{\operatorname{nn}}(t)-u^{*})+2\kappa^{2}(u_{\operatorname{nn}}(t)-u^{*})^{\top}(H(t)-H^{\operatorname{cts}})(Y-u^{*})$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
-(\kappa^{2}\Lambda_{0}+\lambda)\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}^{2}+2\kappa^{2}\|H(t)-H^{\operatorname{cts}}\|\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}\|Y-u^{*}\|_{2}$

where the first step follows the chain rule, the second step follows Corollary
B.11, the third step uses basic linear algebra, the fourth step follows Eq.
(B.3), the fifth step simplifies the expression, and the last step follows the
assumption $\|H(t)-H^{\operatorname{cts}}\|\leq\Lambda_{0}/2$. ∎

###  B.4 Proof sketch

Our goal is to show with appropriate width of the neural network and
appropriate training iterations, the neural network predictor will be
sufficiently close to the neural tangent kernel ridge regression predictor for
any test data. We follow similar proof framework of Theorem 3.2 in [ADH+19a].
Given any accuracy $\epsilon\in(0,1)$, we divide this proof into following
steps:

  1. 1.

Firstly, according to the linear convergence property of kernel ridge
regression shown in Lemma B.9, we can choose sufficiently large training
iterations $T>0$, so that
$|u_{\operatorname{test}}^{*}-u_{\operatorname{ntk},\operatorname{test}}(T)|\leq\epsilon/2$,
as shown in Lemma B.13.

  2. 2.

Once fix training iteration $T$ as in step 1, we bound
$|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|\leq\epsilon/2$
by showing the following:

    1. (a)

Due to the similarity of the the gradient flow of neural network training and
neural tangent kernel ridge regression, we can reduce the task of bounding the
prediction perturbation at time $T$, i.e.,
$|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|$,
back to bounding

      1. i.

the initialization perturbation
$|u_{\operatorname{nn},\operatorname{test}}(0)-u_{\operatorname{ntk},\operatorname{test}}(0)|$
and

      2. ii.

kernel perturbation $\|H(t)-H^{\operatorname{cts}}\|$,
$\|\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X)\|_{2}$,
as shown in Lemma B.14.

    2. (b)

According to concentration results, we can bound the initialization
perturbation
$|u_{\operatorname{nn},\operatorname{test}}(0)-u_{\operatorname{ntk},\operatorname{test}}(0)|$
small enough by choosing sufficiently small $\kappa\in(0,1)$, as shown in
Lemma B.20.

    3. (c)

We characterize the over-parametrization property of the neural network by
inductively show that we can bound kernel perturbation
$\|H(t)-H^{\operatorname{cts}}\|$,
$\|\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X)\|_{2}$
small enough by choosing network width $m>0$ large enough, as shown in Lemma
B.21.

  3. 3.

Lastly, we combine the results of step 1 and 2 using triangle inequality, to
show the equivalence between training neural network with regularization and
neural tangent kernel ridge regression, i.e.,
$|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{test}}^{*}|\leq\epsilon$,
as shown in Theorem B.28.

###  B.5 Equivalence between training net with regularization and kernel ridge
regression for test data prediction

In this section, we prove Theorem 3.7 following the proof sketch in Section
B.4.

####  B.5.1 Upper bounding
$|u_{\operatorname{ntk},\operatorname{test}}(T)-u_{\operatorname{test}}^{*}|$

In this section, we give an upper bound for
$|u_{\operatorname{ntk},\operatorname{test}}(T)-u_{\operatorname{test}}^{*}|$.

######  Lemma B.13.

Let $u_{\operatorname{ntk},\operatorname{test}}(T)\in\mathbb{R}$ and
$u_{\operatorname{test}}^{*}\in\mathbb{R}$ be defined as Definition B.5. Given
any accuracy $\epsilon>0$, if $\kappa\in(0,1)$, then by picking
$T=\widetilde{O}(\frac{1}{\kappa^{2}\Lambda_{0}})$, we have

$\displaystyle|u_{\operatorname{ntk},\operatorname{test}}(T)-u_{\operatorname{test}}^{*}|\leq\epsilon/2.$

where $\widetilde{O}(\cdot)$ here hides
$\operatorname{poly}\log(n/(\epsilon\Lambda_{0}))$.

###### Proof.

Due to the linear convergence of kernel ridge regression, i.e.,

$\displaystyle\frac{\mathrm{d}\|\beta(t)-\beta^{*}\|_{2}^{2}}{\mathrm{d}t}\leq-2(\kappa^{2}\Lambda_{0}+\lambda)\|\beta(t)-\beta^{*}\|_{2}^{2}$

Thus,

$\displaystyle|u_{\operatorname{ntk},\operatorname{test}}(T)-u_{\operatorname{test}}^{*}|=$
$\displaystyle\leavevmode\nobreak\
|\kappa\Phi(x_{\operatorname{test}})^{\top}\beta(T)-\kappa\Phi(x_{\operatorname{test}})\beta^{*}|$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\kappa\|\Phi(x_{\operatorname{test}})\|_{2}\|\beta(T)-\beta^{*}\|_{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ \kappa
e^{-(\kappa^{2}\Lambda_{0}+\lambda)T}\|\beta(0)-\beta^{*}\|_{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
e^{-(\kappa^{2}\Lambda_{0}+\lambda)T}\cdot\operatorname{poly}(\kappa,n,1/\Lambda_{0})$

where the last step follows from $\beta(0)=0$ and
$\|\beta^{*}\|_{2}=\operatorname{poly}(\kappa,n,1/\Lambda_{0})$.

Note $\kappa\in(0,1)$. Thus, by picking
$T=\widetilde{O}(\frac{1}{\kappa^{2}\Lambda_{0}})$, we have

$\displaystyle\|u_{\operatorname{ntk},\operatorname{test}}(T)-u_{\operatorname{test}}^{*}\|_{2}\leq\epsilon/2,$

where $\widetilde{O}(\cdot)$ here hides
$\operatorname{poly}\log(n/(\epsilon\Lambda_{0}))$.∎

####  B.5.2 Upper bounding
$|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|$
by bounding initialization and kernel perturbation

The goal of this section is to prove Lemma B.14, which reduces the problem of
bounding prediction perturbation to the problem of bounding initialization
perturbation and kernel perturbation.

######  Lemma B.14 (Prediction perturbation implies kernel perturbation).

Given training data matrix $X\in\mathbb{R}^{n\times d}$ and corresponding
label vector $Y\in\mathbb{R}^{n}$. Fix the total number of iterations $T>0$.
Given arbitrary test data $x_{\operatorname{test}}\in\mathbb{R}^{d}$. Let
$u_{\operatorname{nn},\operatorname{test}}(t)\in\mathbb{R}^{n}$ and
$u_{\operatorname{ntk},\operatorname{test}}(t)\in\mathbb{R}^{n}$ be the test
data predictors defined in Definition B.3 and Definition B.5 respectively. Let
$\kappa\in(0,1)$ be the corresponding multiplier. Let
$\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)\in\mathbb{R}^{n},\leavevmode\nobreak\
\mathsf{K}_{t}(x_{\operatorname{test}},X)\in\mathbb{R}^{n},\leavevmode\nobreak\
H^{\operatorname{cts}}\in\mathbb{R}^{n\times n},\leavevmode\nobreak\
H(t)\in\mathbb{R}^{n\times n},\leavevmode\nobreak\ \Lambda_{0}>0$ be defined
in Definition B.4 and Definition B.6. Let $u^{*}\in\mathbb{R}^{n}$ be defined
as in Eq. (24). Let $\lambda>0$ be the regularization parameter. Let
$\epsilon_{K}\in(0,1)$, $\epsilon_{\operatorname{init}}\in(0,1)$ and
$\epsilon_{H}\in(0,1)$ denote parameters that are independent of $t$, and the
following conditions hold for all $t\in[0,T]$,

  * •

$\|u_{\operatorname{nn}}(0)\|_{2}\leq\sqrt{n}\epsilon_{\operatorname{init}}$
and
$|u_{\operatorname{nn},\operatorname{test}}(0)|\leq\epsilon_{\operatorname{init}}$

  * •

$\|\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X)\|_{2}\leq\epsilon_{K}$

  * •

$\|H(t)-H^{\operatorname{cts}}\|\leq\epsilon_{H}$

then we have

$\displaystyle|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|\leq$
$\displaystyle\leavevmode\nobreak\
(1+\kappa^{2}nT)\epsilon_{\operatorname{init}}+\kappa^{2}\epsilon_{K}\cdot\Big{(}\frac{\|u^{*}\|_{2}}{\kappa^{2}\Lambda_{0}+\lambda}+\|u^{*}-Y\|_{2}T\Big{)}$
$\displaystyle\leavevmode\nobreak\
+\sqrt{n}T^{2}\kappa^{4}\epsilon_{H}(\|u^{*}\|_{2}+\|u^{*}-Y\|_{2})$

###### Proof.

Combining results from Lemma B.15, Claim B.16. B.17, B.18, we complete the
proof. We have

$\displaystyle|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|\leq$
$\displaystyle\leavevmode\nobreak\
|u_{\operatorname{nn},\operatorname{test}}(0)-u_{\operatorname{ntk},\operatorname{test}}(0)|$
$\displaystyle\leavevmode\nobreak\
+\kappa^{2}\Big{|}\int_{0}^{T}(\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X))^{\top}(u_{\operatorname{ntk}}(t)-Y)\mathrm{d}t\Big{|}$
$\displaystyle\leavevmode\nobreak\
+\kappa^{2}\Big{|}\int_{0}^{T}\mathsf{K}_{t}(x_{\operatorname{test}},X)^{\top}(u_{\operatorname{ntk}}(t)-u_{\operatorname{nn}}(t))\mathrm{d}t\Big{|}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\epsilon_{\operatorname{init}}+\kappa^{2}\epsilon_{K}\cdot\Big{(}\frac{\|u^{*}\|}{\kappa^{2}\Lambda_{0}+\lambda}+\|u^{*}-Y\|_{2}T\Big{)}$
$\displaystyle\leavevmode\nobreak\
+\kappa^{2}n\epsilon_{\operatorname{init}}T+\sqrt{n}T^{2}\cdot\kappa^{4}\epsilon_{H}\cdot(\|u^{*}\|_{2}+\|u^{*}-Y\|_{2})$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
(1+\kappa^{2}nT)\epsilon_{\operatorname{init}}+\kappa^{2}\epsilon_{K}\cdot\Big{(}\frac{\|u^{*}\|_{2}}{\kappa^{2}\Lambda_{0}+\lambda}+\|u^{*}-Y\|_{2}T\Big{)}$
$\displaystyle\leavevmode\nobreak\
+\sqrt{n}T^{2}\kappa^{4}\epsilon_{H}(\|u^{*}\|_{2}+\|u^{*}-Y\|_{2})$

where the first step follows from Lemma B.15, the second step follows from
Claim B.16, B.17 and B.18, and the last step simplifies the expression. ∎

To prove Lemma B.14, we first bound
$|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|$
by three terms in Lemma B.15, then we bound each term individually in Claim
B.16, Claim B.17, and Claim B.18.

######  Lemma B.15.

Follow the same notation as Lemma B.14, we have

$\displaystyle|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|\leq
A+B+C,$

where

$\displaystyle A=$ $\displaystyle\leavevmode\nobreak\
|u_{\operatorname{nn},\operatorname{test}}(0)-u_{\operatorname{ntk},\operatorname{test}}(0)|$
$\displaystyle B=$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}\Big{|}\int_{0}^{T}(\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X))^{\top}(u_{\operatorname{ntk}}(t)-Y)\mathrm{d}t\Big{|}$
$\displaystyle C=$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}\Big{|}\int_{0}^{T}\mathsf{K}_{t}(x_{\operatorname{test}},X)^{\top}(u_{\operatorname{ntk}}(t)-u_{\operatorname{nn}}(t))\mathrm{d}t\Big{|}$

###### Proof.

$\displaystyle\leavevmode\nobreak\
|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\Big{|}u_{\operatorname{nn},\operatorname{test}}(0)-u_{\operatorname{ntk},\operatorname{test}}(0)+\int_{0}^{T}(\frac{\mathrm{d}u_{\operatorname{nn},\operatorname{test}}(t)}{\mathrm{d}t}-\frac{\mathrm{d}u_{\operatorname{ntk},\operatorname{test}}(t)}{\mathrm{d}t})\mathrm{d}t\Big{|}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
|u_{\operatorname{nn},\operatorname{test}}(0)-u_{\operatorname{ntk},\operatorname{test}}(0)|+\Big{|}\int_{0}^{T}(\frac{\mathrm{d}u_{\operatorname{nn},\operatorname{test}}(t)}{\mathrm{d}t}-\frac{\mathrm{d}u_{\operatorname{ntk},\operatorname{test}}(t)}{\mathrm{d}t})\mathrm{d}t\Big{|},$
(31)

where the first step follows from the definition of integral, the second step
follows from the triangle inequality. Note by Corollary B.8, B.11, their
gradient flow are given by

$\displaystyle\frac{\mathrm{d}u_{\operatorname{ntk},\operatorname{test}}(t)}{\mathrm{d}t}$
$\displaystyle=-\kappa^{2}\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)^{\top}(u_{\operatorname{ntk}}(t)-Y)-\lambda
u_{\operatorname{ntk},\operatorname{test}}(t)$ (32)
$\displaystyle\frac{\mathrm{d}u_{\operatorname{nn},\operatorname{test}}(t)}{\mathrm{d}t}$
$\displaystyle=-\kappa^{2}\mathsf{K}_{t}(x_{\operatorname{test}},X)^{\top}(u_{\operatorname{nn}}(t)-Y)-\lambda
u_{\operatorname{nn},\operatorname{test}}(t)$ (33)

where $u_{\operatorname{ntk}}(t)\in\mathbb{R}^{n}$ and
$u_{\operatorname{nn}}(t)\in\mathbb{R}^{n}$ are the predictors for training
data defined in Definition B.5 and Definition B.3. Thus, we have

$\displaystyle\leavevmode\nobreak\
\frac{\mathrm{d}u_{\operatorname{nn},\operatorname{test}}(t)}{\mathrm{d}t}-\frac{\mathrm{d}u_{\operatorname{ntk},\operatorname{test}}(t)}{\mathrm{d}t}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
-\kappa^{2}\mathsf{K}_{t}(x_{\operatorname{test}},X)^{\top}(u_{\operatorname{nn}}(t)-Y)+\kappa^{2}\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)^{\top}(u_{\operatorname{ntk}}(t)-Y)-\lambda(u_{\operatorname{nn},\operatorname{test}}(t)-u_{\operatorname{ntk},\operatorname{test}}(t))$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}(\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X))^{\top}(u_{\operatorname{ntk}}(t)-Y)-\kappa^{2}\mathsf{K}_{t}(x_{\operatorname{test}},X)^{\top}(u_{\operatorname{ntk}}(t)-u_{\operatorname{nn}}(t))$
$\displaystyle\leavevmode\nobreak\
-\lambda(u_{\operatorname{nn},\operatorname{test}}(t)-u_{\operatorname{ntk},\operatorname{test}}(t)),$
(34)

where the first step follows from Eq. (32) and Eq. (33), the second step
rewrites the formula. Note the term
$-\lambda(u_{\operatorname{nn},\operatorname{test}}(t)-u_{\operatorname{ntk},\operatorname{test}}(t))$
will only make

$\displaystyle\Big{|}\int_{0}^{T}(\frac{\mathrm{d}u_{\operatorname{nn},\operatorname{test}}(t)}{\mathrm{d}t}-\frac{\mathrm{d}u_{\operatorname{ntk},\operatorname{test}}(t)}{\mathrm{d}t})\mathrm{d}t\Big{|}$

smaller, so we have

$\displaystyle\leavevmode\nobreak\
\Big{|}\int_{0}^{T}(\frac{\mathrm{d}u_{\operatorname{nn},\operatorname{test}}(t)}{\mathrm{d}t}-\frac{\mathrm{d}u_{\operatorname{ntk},\operatorname{test}}(t)}{\mathrm{d}t})\mathrm{d}t\Big{|}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\Big{|}\int_{0}^{T}\kappa^{2}((\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X))^{\top}(u_{\operatorname{ntk}}(t)-Y)-\kappa^{2}\mathsf{K}_{t}(x_{\operatorname{test}},X)^{\top}(u_{\operatorname{ntk}}(t)-u_{\operatorname{nn}}(t)))\mathrm{d}t\Big{|}$
(35)

Thus,

$\displaystyle\leavevmode\nobreak\
|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
|u_{\operatorname{nn},\operatorname{test}}(0)-u_{\operatorname{ntk},\operatorname{test}}(0)|+\Big{|}\int_{0}^{T}(\frac{\mathrm{d}u_{\operatorname{nn},\operatorname{test}}(t)}{\mathrm{d}t}-\frac{\mathrm{d}u_{\operatorname{ntk},\operatorname{test}}(t)}{\mathrm{d}t})\mathrm{d}t\Big{|}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
|u_{\operatorname{nn},\operatorname{test}}(0)-u_{\operatorname{ntk},\operatorname{test}}(0)|+\Big{|}\int_{0}^{T}\kappa^{2}((\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X))^{\top}(u_{\operatorname{ntk}}(t)-Y)$
$\displaystyle\leavevmode\nobreak\
-\kappa^{2}\mathsf{K}_{t}(x_{\operatorname{test}},X)^{\top}(u_{\operatorname{ntk}}(t)-u_{\operatorname{nn}}(t)))\mathrm{d}t\Big{|}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
|u_{\operatorname{nn},\operatorname{test}}(0)-u_{\operatorname{ntk},\operatorname{test}}(0)|+\Big{|}\int_{0}^{T}\kappa^{2}(\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X))^{\top}(u_{\operatorname{ntk}}(t)-Y)\mathrm{d}t\Big{|}$
$\displaystyle\leavevmode\nobreak\
+\Big{|}\int_{0}^{T}\kappa^{2}\mathsf{K}_{t}(x_{\operatorname{test}},X)^{\top}(u_{\operatorname{ntk}}(t)-u_{\operatorname{nn}}(t))\mathrm{d}t\Big{|}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ A+B+C,$

where the first step follows from Eq. (B.5.2), the second step follows from
Eq. (B.5.2), the third step follows from triangle inequality, and the last
step follows from the definition of $A,\leavevmode\nobreak\
B,\leavevmode\nobreak\ C$. ∎

Now let us bound these three terms $A$, $B$ and $C$ one by one. We claim

######  Claim B.16 (Bounding the term $A$).

We have

$\displaystyle A\leq\epsilon_{\operatorname{init}}.$

###### Proof.

Note $u_{\operatorname{ntk},\operatorname{test}}(0)=0$, so by assumption we
have

$\displaystyle
A=|u_{\operatorname{nn},\operatorname{test}}(0)|\leq\epsilon_{\operatorname{init}}.$

∎

######  Claim B.17 (Bounding the term $B$).

We have

$\displaystyle
B\leq\kappa^{2}\epsilon_{K}\cdot\Big{(}\frac{\|u^{*}\|}{\kappa^{2}\Lambda_{0}+\lambda}+\|u^{*}-Y\|_{2}T\Big{)}.$

###### Proof.

Note

$\displaystyle B=$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}\Big{|}\int_{0}^{T}(\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X))^{\top}(u_{\operatorname{ntk}}(t)-Y)\mathrm{d}t\Big{|}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}\max_{t\in[0,T]}\|\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X)\|_{2}\int_{0}^{T}\|u_{\operatorname{ntk}}(t)-Y\|_{2}\mathrm{d}t,$

where the first step follows from definition of $B$, and the second step
follows from the Cauchy-Schwartz inequality. Note by Lemma B.9, the kernel
ridge regression predictor $u_{\operatorname{ntk}}(t)\in\mathbb{R}^{n}$
converges linearly to the optimal predictor
$u^{*}=\kappa^{2}H^{\operatorname{cts}}(\kappa^{2}H^{\operatorname{cts}}+\lambda
I)^{-1}Y\in\mathbb{R}^{n}$, i.e.,

$\displaystyle\|u_{\operatorname{ntk}}(t)-u^{*}\|_{2}\leq
e^{-(\kappa^{2}\Lambda_{0}+\lambda)t}\|u_{\operatorname{ntk}}(0)-u^{*}\|_{2}.$
(36)

Thus, we have

$\displaystyle\int_{0}^{T}\|u_{\operatorname{ntk}}(t)-Y\|_{2}\mathrm{d}t\leq$
$\displaystyle\leavevmode\nobreak\
\int_{0}^{T}\|u_{\operatorname{ntk}}(t)-u^{*}\|_{2}\mathrm{d}t+\int_{0}^{T}\|u^{*}-Y\|_{2}\mathrm{d}t$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\int_{0}^{T}e^{-(\kappa^{2}\Lambda_{0}+\lambda)}\|u_{\operatorname{ntk}}(0)-u^{*}\|_{2}\mathrm{d}t+\int_{0}^{T}\|u^{*}-Y\|_{2}\mathrm{d}t$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{\|u_{\operatorname{ntk}}(0)-u^{*}\|_{2}}{\kappa^{2}\Lambda_{0}+\lambda}+\|u^{*}-Y\|_{2}T$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{\|u^{*}\|}{\kappa^{2}\Lambda_{0}+\lambda}+\|u^{*}-Y\|_{2}T,$ (37)

where the first step follows from the triangle inequality, the second step
follows from Eq. (36), the third step calculates the integration, and the last
step follows from the fact $u_{\operatorname{ntk}}(0)=0$. Thus, we have

$\displaystyle B\leq$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}\max_{t\in[0,T]}\|\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X)\|_{2}\cdot\int_{0}^{T}\|u_{\operatorname{ntk}}(t)-Y\|_{2}\mathrm{d}t$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}\epsilon_{K}\cdot\Big{(}\frac{\|u^{*}\|}{\kappa^{2}\Lambda_{0}+\lambda}+\|u^{*}-Y\|_{2}T\Big{)}.$

where the first step follows from Eq. (36), the second step follows from Eq.
(B.5.2) and definition of $\epsilon_{K}$. ∎

######  Claim B.18 (Bounding the term $C$).

We have

$\displaystyle C\leq
n\epsilon_{\operatorname{init}}T+\sqrt{n}T^{2}\cdot\kappa^{2}\epsilon_{H}\cdot(\|u^{*}\|_{2}+\|u^{*}-Y\|_{2})$

###### Proof.

Note

$\displaystyle C=$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}\Big{|}\int_{0}^{T}\mathsf{K}_{t}(x_{\operatorname{test}},X)^{\top}(u_{\operatorname{ntk}}(t)-u_{\operatorname{nn}}(t))\mathrm{d}t\Big{|}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}\max_{t\in[0,T]}\|\mathsf{K}_{t}(x_{\operatorname{test}},X)\|_{2}\max_{t\in[0,T]}\|u_{\operatorname{ntk}}(t)-u_{\operatorname{nn}}(t)\|_{2}\cdot
T$ (38)

where the first step follows from the definition of $C$, and the second step
follows the Cauchy-Schwartz inequality.

To bound term
$\max_{t\in[0,T]}\|u_{\operatorname{ntk}}(t)-u_{\operatorname{nn}}(t)\|_{2}$,
notice that for any $t\in[0,T]$, we have

$\displaystyle\|u_{\operatorname{ntk}}(t)-u_{\operatorname{nn}}(t)\|_{2}\leq$
$\displaystyle\leavevmode\nobreak\
\|u_{\operatorname{ntk}}(0)-u_{\operatorname{nn}}(0)\|_{2}+\Big{\|}\int_{0}^{t}\frac{\mathrm{d}(u_{\operatorname{ntk}}(\tau)-u_{\operatorname{nn}}(\tau))}{\mathrm{d}\tau}\mathrm{d}\tau\Big{\|}_{2}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\sqrt{n}\epsilon_{\operatorname{init}}+\Big{\|}\int_{0}^{t}\frac{\mathrm{d}(u_{\operatorname{ntk}}(\tau)-u_{\operatorname{nn}}(\tau))}{\mathrm{d}\tau}\mathrm{d}\tau\Big{\|}_{2},$
(39)

where the first step follows the triangle inequality, and the second step
follows the assumption. Further,

$\displaystyle\frac{\mathrm{d}(u_{\operatorname{ntk}}(\tau)-u_{\operatorname{nn}}(\tau))}{\mathrm{d}\tau}$
$\displaystyle=-\kappa^{2}H^{\operatorname{cts}}(u_{\operatorname{ntk}}(\tau)-Y)-\lambda
u_{\operatorname{ntk}}(\tau)+\kappa^{2}H(\tau)(u_{\operatorname{nn}}(\tau)-Y)+\lambda
u_{\operatorname{nn}}(\tau)$ $\displaystyle=-(\kappa^{2}H(\tau)+\lambda
I)(u_{\operatorname{ntk}}(\tau)-u_{\operatorname{nn}}(\tau))+\kappa^{2}(H(\tau)-H^{\operatorname{cts}})(u_{\operatorname{ntk}}(\tau)-Y),$

where the first step follows the Corollary B.8, B.11, the second step rewrites
the formula. Since the term $-(\kappa^{2}H(\tau)+\lambda
I)(u_{\operatorname{ntk}}(\tau)-u_{\operatorname{nn}}(\tau))$ makes
$\|\int_{0}^{t}\frac{\mathrm{d}(u_{\operatorname{ntk}}(\tau)-u_{\operatorname{nn}}(\tau))}{\mathrm{d}\tau}\mathrm{d}\tau\|_{2}$
smaller.

Taking the integral and apply the $\ell_{2}$ norm, we have

$\displaystyle\Big{\|}\int_{0}^{t}\frac{\mathrm{d}(u_{\operatorname{ntk}}(\tau)-u_{\operatorname{nn}}(\tau))}{\mathrm{d}\tau}\mathrm{d}\tau\Big{\|}_{2}\leq\Big{\|}\int_{0}^{t}\kappa^{2}(H(\tau)-H^{\operatorname{cts}})(u_{\operatorname{ntk}}(\tau)-Y)\mathrm{d}\tau\Big{\|}_{2}.$
(40)

Thus,

$\displaystyle\max_{t\in[0,T]}\|u_{\operatorname{ntk}}(t)-u_{\operatorname{nn}}(t)\|_{2}\leq$
$\displaystyle\leavevmode\nobreak\
\sqrt{n}\epsilon_{\operatorname{init}}+\max_{t\in[0,T]}\Big{\|}\int_{0}^{t}\frac{\mathrm{d}(u_{\operatorname{ntk}}(\tau)-u_{\operatorname{nn}}(\tau))}{\mathrm{d}\tau}\mathrm{d}\tau\Big{\|}_{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sqrt{n}\epsilon_{\operatorname{init}}+\max_{t\in[0,T]}\Big{\|}\int_{0}^{t}\kappa^{2}(H(\tau)-H^{\operatorname{cts}})(u_{\operatorname{ntk}}(\tau)-Y)\mathrm{d}\tau\Big{\|}_{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sqrt{n}\epsilon_{\operatorname{init}}+\max_{t\in[0,T]}\int_{0}^{t}\kappa^{2}\|H(\tau)-H^{\operatorname{cts}}\|\cdot\|u_{\operatorname{ntk}}(\tau)-Y\|_{2}\mathrm{d}\tau$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sqrt{n}\epsilon_{\operatorname{init}}+\max_{t\in[0,T]}\kappa^{2}\epsilon_{H}\Big{(}\int_{0}^{t}\|u_{\operatorname{ntk}}(\tau)-u^{*}\|_{2}\mathrm{d}\tau+\int_{0}^{t}\|u^{*}-Y\|_{2}\mathrm{d}\tau\Big{)}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sqrt{n}\epsilon_{\operatorname{init}}+\max_{t\in[0,T]}\kappa^{2}\epsilon_{H}\Big{(}\int_{0}^{t}\|u_{\operatorname{ntk}}(0)-u^{*}\|_{2}\mathrm{d}\tau+\int_{0}^{t}\|u^{*}-Y\|_{2}\mathrm{d}\tau\Big{)}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sqrt{n}\epsilon_{\operatorname{init}}+\max_{t\in[0,T]}t\cdot\kappa^{2}\epsilon_{H}\cdot(\|u^{*}\|_{2}+\|u^{*}-Y\|_{2})$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sqrt{n}\epsilon_{\operatorname{init}}+T\cdot\kappa^{2}\epsilon_{H}\cdot(\|u^{*}\|_{2}+\|u^{*}-Y\|_{2})$
(41)

where the first step follows from Eq. (B.5.2), the second step follows from
Eq. (40), the third step follows from triangle inequality, the fourth step
follows from the condition
$\|H(\tau)-H^{\operatorname{cts}}\|\leq\epsilon_{H}$ for all $\tau\leq T$ and
the triangle inequality, the fifth step follows from the linear convergence of
$\|u_{\operatorname{ntk}}(\tau)-u^{*}\|_{2}$ as in Lemma B.9, the sixth step
follows the fact $u_{\operatorname{ntk}}(0)=0$, and the last step calculates
the maximum. Therefore,

$\displaystyle C\leq$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}\max_{t\in[0,T]}\|\mathsf{K}_{t}(x_{\operatorname{test}},X)\|_{2}\max_{t\in[0,T]}\|u_{\operatorname{ntk}}(t)-u_{\operatorname{nn}}(t)\|_{2}\cdot
T$ $\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}\max_{t\in[0,T]}\|\mathsf{K}_{t}(x_{\operatorname{test}},X)\|_{2}\cdot(\sqrt{n}\epsilon_{\operatorname{init}}T+T^{2}\cdot\kappa^{2}\epsilon_{H}\cdot(\|u^{*}\|_{2}+\|u^{*}-Y\|_{2}))$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\kappa^{2}n\epsilon_{\operatorname{init}}T+\sqrt{n}T^{2}\cdot\kappa^{4}\epsilon_{H}\cdot(\|u^{*}\|_{2}+\|u^{*}-Y\|_{2})$

where the first step follows from Eq. (B.5.2), and the second step follows
from Eq. (B.5.2), and the last step follows from the fact that
$\mathsf{K}_{t}(x,z)\leq 1$ holds for any $\|x\|_{2},\leavevmode\nobreak\
\|z\|_{2}\leq 1$. ∎

######  Remark B.19.

Given final accuracy $\epsilon$, to ensure
$|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|\leq\epsilon$,
we need to choose $\kappa>0$ small enough to make
$\epsilon_{\operatorname{init}}=O(\epsilon)$ and choose width $m>0$ large
enough to make $\epsilon_{H}$ and $\epsilon_{\operatorname{test}}$ both
$O(\epsilon)$. And we discuss these two tasks one by one in the following
sections.

####  B.5.3 Upper bounding initialization perturbation

In this section, we bound $\epsilon_{\operatorname{init}}$ to our wanted
accuracy $\epsilon$ by picking $\kappa$ large enough. We prove Lemma B.20.

######  Lemma B.20 (Bounding initialization perturbation).

Let $f_{\operatorname{nn}}$ be as defined in Definition B.2. Assume the
initial weight of the network work
$w_{r}(0)\in\mathbb{R}^{d},\leavevmode\nobreak\ r=1,\cdots,m$ as defined in
Definition B.3 are drawn independently from standard Gaussian distribution
$\mathcal{N}(0,I_{d})$. And $a_{r}\in\mathbb{R},\leavevmode\nobreak\
r=1,\cdots,m$ as defined in Definition B.2 are drawn independently from
$\operatorname{unif}[\\{-1,+1\\}]$. Let $\kappa\in(0,1)$,
$u_{\operatorname{nn}}(t)$ and
$u_{\operatorname{nn},\operatorname{test}}(t)\in\mathbb{R}$ be defined as in
Definition B.3. Then for any data $x\in\mathbb{R}^{d}$ with $\|x\|_{2}\leq 1$,
we have with probability $1-\delta$,

$\displaystyle|f_{\operatorname{nn}}(W(0),x)|\leq 2\log(2m/\delta).$

Further, given any accuracy $\epsilon\in(0,1)$, if
$\kappa=\widetilde{O}(\epsilon(\Lambda_{0}+\lambda)/n)$, let
$\epsilon_{\operatorname{init}}=\epsilon(\Lambda_{0}+\lambda)/n$, we have

$\displaystyle|u_{\operatorname{nn}}(0)|\leq\sqrt{n}\epsilon_{\operatorname{init}}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\
|u_{\operatorname{nn},\operatorname{test}}(0)|\leq\epsilon_{\operatorname{init}}$

hold with probability $1-\delta$, where $\widetilde{O}(\cdot)$ hides the
$\operatorname{poly}\log(n/(\epsilon\delta\Lambda_{0}))$.

###### Proof.

Note by definition,

$\displaystyle
f_{\operatorname{nn}}(W(0),x)=\frac{1}{\sqrt{m}}\sum_{r=1}^{m}a_{r}\sigma(w_{r}(0)^{\top}x).$

Since $w_{r}(0)\sim\mathcal{N}(0,I_{d})$, so
$w_{r}(0)^{\top}x_{\operatorname{test}}\sim
N(0,\|x_{\operatorname{test}}\|_{2})$. Note
$\|x_{\operatorname{test}}\|_{2}\leq 1$, by Gaussian tail bounds Lemma A.5, we
have with probability $1-\delta/(2m)$:

$\displaystyle|w_{r}(0)^{\top}x|\leq\sqrt{2\log(2m/\delta)}.$ (42)

Condition on Eq. (42) holds for all $r\in[m]$, denote
$Z_{r}=a_{r}\sigma(w_{r}(0)^{\top}x)$, then we have
$\operatorname*{{\mathbb{E}}}[Z_{r}]=0$ and
$|Z_{r}|\leq\sqrt{2\log(2m/\delta)}$. By Lemma A.2, with probability
$1-\delta/2$:

$\displaystyle\Big{|}\sum_{r=1}^{m}Z_{r}\Big{|}\leq
2\sqrt{m}\log{(2m/\delta)}.$ (43)

Since $u_{\operatorname{nn},\operatorname{test}}(0)=\frac{1}{\sqrt{n}}\sum
Z_{r}$, by combining Eq. (42), (43) and union bound over all $r\in[m]$, we
have with probability $1-\delta$:

$\displaystyle|u_{\operatorname{nn},\operatorname{test}}(0)|\leq
2\log(2m/\delta).$

Further, note $[u_{\operatorname{nn}}(0)]_{i}=\kappa
f_{\operatorname{nn}}(W(0),x_{i})$ and
$u_{\operatorname{nn},\operatorname{test}}(0)=\kappa
f_{\operatorname{nn}}(W(0),x_{\operatorname{test}})$. Thus, by choosing
$\kappa=\widetilde{O}(\epsilon(\Lambda_{0}+\lambda)/n)$, taking the union
bound over all training and test data, we have

$\displaystyle|u_{\operatorname{nn}}(0)|\leq\sqrt{n}\epsilon_{\operatorname{init}}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\
|u_{\operatorname{nn},\operatorname{test}}(0)|\leq\epsilon_{\operatorname{init}}$

hold with probability $1-\delta$, where $\widetilde{O}(\cdot)$ hides the
$\operatorname{poly}\log(n/(\epsilon\delta\Lambda_{0}))$. ∎

####  B.5.4 Upper bounding kernel perturbation

In this section, we try to bound kernel perturbation by induction. We want to
prove Lemma B.21, which also helps to show the equivalence for training data
prediction as shown in Section B.6.

######  Lemma B.21 (Bounding kernel perturbation).

Given training data $X\in\mathbb{R}^{n\times d}$, $Y\in\mathbb{R}^{n}$ and a
test data $x_{\operatorname{test}}\in\mathbb{R}^{d}$. Let $T>0$ denotes the
total number of iterations, $m>0$ denotes the width of the network,
$\epsilon_{\operatorname{train}}$ denotes a fixed training error threshold,
$\delta>0$ denotes the failure probability. Let
$u_{\operatorname{nn}}(t)\in\mathbb{R}^{n}$ and
$u_{\operatorname{ntk}}(t)\in\mathbb{R}^{n}$ be the training data predictors
defined in Definition B.3 and Definition B.5 respectively. Let
$\kappa\in(0,1)$ be the corresponding multiplier. Let
$\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)\in\mathbb{R}^{n},\leavevmode\nobreak\
\mathsf{K}_{t}(x_{\operatorname{test}},X)\in\mathbb{R}^{n},\leavevmode\nobreak\
H(t)\in\mathbb{R}^{n\times n},\leavevmode\nobreak\ \Lambda_{0}>0$ be the
kernel related quantities defined in Definition B.4 and Definition B.6. Let
$u^{*}\in\mathbb{R}^{n}$ be defined as in Eq. (24). Let $\lambda>0$ be the
regularization parameter. Let
$W(t)=[w_{1}(t),\cdots,w_{m}(t)]\in\mathbb{R}^{d\times m}$ be the parameters
of the neural network defined in Definition B.3.

For any accuracy $\epsilon\in(0,1/10)$. If
$\kappa=\widetilde{O}(\frac{\epsilon\Lambda_{0}}{n})$,
$T=\widetilde{O}(\frac{1}{\kappa^{2}(\Lambda_{0}+\lambda)})$,
$\epsilon_{\operatorname{train}}=\widetilde{O}(\|u_{\operatorname{nn}}(0)-u^{*}\|_{2})$,
$m\geq\widetilde{O}(\frac{n^{10}d}{\epsilon^{6}\Lambda_{0}^{10}})$ and
$\lambda=\widetilde{O}(\frac{1}{\sqrt{m}})$, with probability $1-\delta$,
there exist $\epsilon_{W},\leavevmode\nobreak\
\epsilon_{H}^{\prime},\leavevmode\nobreak\ \epsilon_{K}^{\prime}>0$ that are
independent of $t$, such that the following hold for all $0\leq t\leq T$:

  * •

1\. $\|w_{r}(0)-w_{r}(t)\|_{2}\leq\epsilon_{W}$, $\forall r\in[m]$

  * •

2\. $\|H(0)-H(t)\|_{2}\leq\epsilon_{H}^{\prime}$

  * •

3\.
$\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}^{2}\leq\max\\{\exp(-(\kappa^{2}\Lambda_{0}+\lambda)t/2)\cdot\|u_{\operatorname{nn}}(0)-u^{*}\|_{2}^{2},\leavevmode\nobreak\
\epsilon_{\operatorname{train}}^{2}\\}$

  * •

4\.
$\|\mathsf{K}_{0}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X)\|_{2}\leq\epsilon_{K}^{\prime}$

Further,
$\epsilon_{W}\leq\widetilde{O}(\frac{\epsilon\lambda_{0}^{2}}{n^{2}})$,
$\epsilon_{H}^{\prime}\leq\widetilde{O}(\frac{\epsilon\lambda_{0}^{2}}{n})$
and
$\epsilon_{K}^{\prime}\leq\widetilde{O}(\frac{\epsilon\lambda_{0}^{2}}{n^{1.5}})$.
Here $\widetilde{O}(\cdot)$ hides the
$\operatorname{poly}\log(n/(\epsilon\delta\Lambda_{0}))$.

We first state some concentration results for the random initialization that
can help us prove the lemma.

######  Lemma B.22 (Random initialization result).

Assume initial value $w_{r}(0)\in\mathbb{R}^{d},\leavevmode\nobreak\
r=1,\cdots,m$ are drawn independently from standard Gaussian distribution
$\mathcal{N}(0,I_{d})$, then with probability $1-3\delta$ we have

$\displaystyle\|w_{r}(0)\|_{2}\leq$ $\displaystyle\leavevmode\nobreak\
2\sqrt{d}+2\sqrt{\log{(m/\delta)}}\leavevmode\nobreak\ \text{for
all}\leavevmode\nobreak\ r\in[m]$ (44)
$\displaystyle\|H(0)-H^{\operatorname{cts}}\|\leq$
$\displaystyle\leavevmode\nobreak\ 4n(\log(n/\delta)/m)^{1/2}$ (45)
$\displaystyle\|\mathsf{K}_{0}(x_{\operatorname{test}},X)-\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)\|_{2}\leq$
$\displaystyle\leavevmode\nobreak\ (2n\log{(2n/\delta)}/m)^{1/2}$ (46)

###### Proof.

By lemma A.6, with probability at least $1-\delta$,

$\displaystyle\|w_{r}(0)\|_{2}\leq\sqrt{d}+\sqrt{\log(m/\delta)}$

holds for all $r\in[m]$.

Using Lemma A.9 in [SY19], we have

$\displaystyle\|H(0)-H^{\operatorname{cts}}\|\leq\epsilon_{H}^{\prime\prime}=4n(\log{(n/\delta)}/m)^{1/2}$

holds with probability at least $1-\delta$.
Note by definition,

$\displaystyle\operatorname*{{\mathbb{E}}}[\mathsf{K}_{0}(x_{\operatorname{test}},x_{i})]=\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},x_{i})$

holds for any training data $x_{i}$. By Hoeffding inequality, we have for any
$t>0$,

$\displaystyle\Pr[|\mathsf{K}_{0}(x_{\operatorname{test}},x_{i})-\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},x_{i})|\geq
t]\leq 2\exp{(-mt^{2}/2)}.$

Setting $t=(\frac{2}{m}\log{(2n/\delta)})^{1/2}$, we can apply union bound on
all training data $x_{i}$ to get with probability at least $1-\delta$, for all
$i\in[n]$,

$\displaystyle|\mathsf{K}_{0}(x_{\operatorname{test}},x_{i})-\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},x_{i})|\leq(2\log(2n/\delta)/m)^{1/2}.$

Thus, we have

$\displaystyle\|\mathsf{K}_{0}(x_{\operatorname{test}},X)-\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)\|_{2}\leq(2n\log(2n/\delta)/m)^{1/2}$
(47)

holds with probability at least $1-\delta$.
Using union bound over above three events, we finish the proof. ∎

Now conditioning on Eq. (44), (45), (46) holds, We show all the four
conclusions in Lemma B.21 holds using induction.

We define the following quantity:

$\displaystyle\epsilon_{W}:=$ $\displaystyle\leavevmode\nobreak\
\frac{\sqrt{n}}{\sqrt{m}}\max\\{4\|u_{\operatorname{nn}}(0)-u^{*}\|_{2}/(\kappa^{2}\Lambda_{0}+\lambda),\epsilon_{\operatorname{train}}\cdot
T\\}$ $\displaystyle\leavevmode\nobreak\
+\Big{(}\frac{\sqrt{n}}{\sqrt{m}}\|Y-u^{*}\|_{2}+\lambda(2\sqrt{d}+2\sqrt{\log(m/\delta)})\Big{)}\cdot
T$ (48) $\displaystyle\epsilon_{H}^{\prime}:=$
$\displaystyle\leavevmode\nobreak\ 2n\epsilon_{W}$
$\displaystyle\epsilon_{K}:=$ $\displaystyle\leavevmode\nobreak\
2\sqrt{n}\epsilon_{W}$

which are independent of $t$.

Note the base case when $t=0$ trivially holds. Now assuming Lemma B.21 holds
before time $t\in[0,T]$, we argue that it also holds at time $t$. To do so,
Lemmas B.23, B.24, B.25 argue these conclusions one by one.

######  Lemma B.23 (Conclusion 1).

If for any $\tau<t$, we have

$\displaystyle\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}^{2}\leq\leavevmode\nobreak\
\max\\{\exp(-(\kappa^{2}\Lambda_{0}+\lambda)\tau/2)\cdot\|u_{\operatorname{nn}}(0)-u^{*}\|_{2}^{2},\leavevmode\nobreak\
\epsilon_{\operatorname{train}}^{2}\\}$

and

$\displaystyle\|w_{r}(0)-w_{r}(\tau)\|_{2}\leq\epsilon_{W}\leq 1$

and

$\displaystyle\|w_{r}(0)\|_{2}\leq\leavevmode\nobreak\
\sqrt{d}+\sqrt{\log(m/\delta)}\leavevmode\nobreak\ \text{for
all}\leavevmode\nobreak\ r\in[m]$

hold, then

$\displaystyle\|w_{r}(0)-w_{r}(t)\|_{2}\leq\epsilon_{W}$

###### Proof.

Recall the gradient flow as Eq. (28)

$\displaystyle\frac{\mathrm{d}w_{r}(\tau)}{\mathrm{d}\tau}=\leavevmode\nobreak\
\sum_{i=1}^{n}\frac{1}{\sqrt{m}}a_{r}(y_{i}-u_{\operatorname{nn}}(\tau)_{i})x_{i}\sigma^{\prime}(w_{r}(\tau)^{\top}x_{i})-\lambda
w_{r}(\tau)$ (49)

So we have

$\displaystyle\Big{\|}\frac{\mathrm{d}w_{r}(\tau)}{\mathrm{d}\tau}\Big{\|}_{2}=$
$\displaystyle\leavevmode\nobreak\
\left\|\sum_{i=1}^{n}\frac{1}{\sqrt{m}}a_{r}(y_{i}-u_{\operatorname{nn}}(\tau)_{i})x_{i}\sigma^{\prime}(w_{r}(\tau)^{\top}x_{i})-\lambda
w_{r}(\tau)\right\|_{2}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
\frac{1}{\sqrt{m}}\sum_{i=1}^{n}|y_{i}-u_{\operatorname{nn}}(\tau)_{i}|+\lambda\|w_{r}(\tau)\|_{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{\sqrt{n}}{\sqrt{m}}\|Y-u_{\operatorname{nn}}(\tau)\|_{2}+\lambda\|w_{r}(\tau)\|_{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{\sqrt{n}}{\sqrt{m}}\|Y-u_{\operatorname{nn}}(\tau)\|_{2}+\lambda(\|w_{r}(0)\|_{2}+\|w_{r}(\tau)-w_{r}(0)\|_{2})$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{\sqrt{n}}{\sqrt{m}}\|Y-u_{\operatorname{nn}}(\tau)\|_{2}+\lambda(\sqrt{d}+\sqrt{\log(m/\delta)}+1)$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{\sqrt{n}}{\sqrt{m}}\|Y-u_{\operatorname{nn}}(\tau)\|_{2}+\lambda(2\sqrt{d}+2\sqrt{\log(m/\delta)})$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{\sqrt{n}}{\sqrt{m}}(\|Y-u^{*}\|_{2}+\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2})+\lambda(2\sqrt{d}+2\sqrt{\log(m/\delta)})$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{\sqrt{n}}{\sqrt{m}}\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}$
$\displaystyle\leavevmode\nobreak\
+\frac{\sqrt{n}}{\sqrt{m}}\|Y-u^{*}\|_{2}+\lambda(2\sqrt{d}+2\sqrt{\log(m/\delta)})$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{\sqrt{n}}{\sqrt{m}}\max\\{e^{-(\kappa^{2}\Lambda_{0}+\lambda)\tau/4}\|u_{\operatorname{nn}}(0)-u^{*}\|_{2},\epsilon_{\operatorname{train}}\\}$
$\displaystyle\leavevmode\nobreak\
+\frac{\sqrt{n}}{\sqrt{m}}\|Y-u^{*}\|_{2}+\lambda(2\sqrt{d}+2\sqrt{\log(m/\delta)}),$
(50)

where the first step follows from Eq. (49), the second step follows from
triangle inequality, the third step follows from Cauchy-schwarz inequality,
the forth step follows from triangle inequality, the fifth step follows from
condition $\|w_{r}(0)-w_{r}(\tau)\|_{2}\leq 1,\leavevmode\nobreak\
\|w_{r}(0)\|_{2}\leq\sqrt{d}+\sqrt{\log(m/\delta)}$, the seventh step follows
from triangle inequality, the last step follows from
$\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}^{2}\leq\max\\{\exp(-(\kappa^{2}\Lambda_{0}+\lambda)\tau/2)\cdot\|u_{\operatorname{nn}}(0)-u^{*}\|_{2}^{2},\leavevmode\nobreak\
\epsilon_{\operatorname{train}}^{2}\\}$.

Thus, for any $t\leq T$,

$\displaystyle\|w_{r}(0)-w_{r}(t)\|_{2}\leq$
$\displaystyle\leavevmode\nobreak\
\int_{0}^{t}\Big{\|}\frac{\mathrm{d}w_{r}(\tau)}{\mathrm{d}\tau}\Big{\|}_{2}d\tau$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{\sqrt{n}}{\sqrt{m}}\max\\{4\|u_{\operatorname{nn}}(0)-u^{*}\|_{2}/(\kappa^{2}\Lambda_{0}+\lambda),\epsilon_{\operatorname{train}}\cdot
T\\}$ $\displaystyle\leavevmode\nobreak\
+\Big{(}\frac{\sqrt{n}}{\sqrt{m}}\|Y-u^{*}\|_{2}+\lambda(2\sqrt{d}+2\sqrt{\log(m/\delta)})\Big{)}\cdot
T$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\ \epsilon_{W}$

where the first step follows triangle inequality, the second step follows Eq.
(B.5.4), and the last step follows the definition of $\epsilon_{W}$ as Eq.
(48). ∎

######  Lemma B.24 (Conclusion 2).

If $\forall r\in[m]$,

$\displaystyle\|w_{r}(0)-w_{r}(t)\|_{2}\leq\epsilon_{W}<1,$

then

$\displaystyle\|H(0)-H(t)\|_{F}\leq 2n\epsilon_{W}$

holds with probability $1-n^{2}\cdot\exp{(-m\epsilon_{W}/10)}$.

###### Proof.

Directly applying Lemma A.10, we finish the proof. ∎

######  Lemma B.25 (Conclusion 3).

Fix $\epsilon_{H}^{\prime}>0$ independent of $t$. If for all $\tau<t$

$\displaystyle\|H(0)-H^{\operatorname{cts}}\|\leq
4n(\log{(n/\delta)}/m)^{1/2}\leq\Lambda_{0}/4$

and

$\displaystyle\|H(0)-H(\tau)\|\leq\epsilon_{H}^{\prime}\leq\Lambda_{0}/4$

and

$\displaystyle
4n(\log(n/\delta)/m)^{1/2}\leq\frac{\epsilon_{\operatorname{train}}}{8\kappa^{2}\|Y-u^{*}\|_{2}}(\kappa^{2}\Lambda_{0}+\lambda)$
(51)

and

$\displaystyle\epsilon_{H}^{\prime}\leq\frac{\epsilon_{\operatorname{train}}}{8\kappa^{2}\|Y-u^{*}\|_{2}}(\kappa^{2}\Lambda_{0}+\lambda)$
(52)

then we have

$\displaystyle\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}^{2}\leq\max\\{\exp(-(\kappa^{2}\Lambda_{0}+\lambda)t/2)\cdot\|u_{\operatorname{nn}}(0)-u^{*}\|_{2}^{2},\leavevmode\nobreak\
\epsilon_{\operatorname{train}}^{2}\\}.$

###### Proof.

By triangle inequality we have

$\displaystyle\|H(\tau)-H^{\operatorname{cts}}\|\leq$
$\displaystyle\leavevmode\nobreak\
\|H(0)-H(\tau)\|+\|H(0)-H^{\operatorname{cts}}\|$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
\epsilon_{H}^{\prime}+4n(\log{(n/\delta)}/m)^{1/2}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ \Lambda_{0}/2$ (53)

holds for all $\tau<t$. Denote
$\epsilon_{H}=\epsilon_{H}^{\prime}+4n(\log{(n/\delta)}/m)^{1/2}$, we have
$\|H(\tau)-H^{\operatorname{cts}}\|\leq\epsilon_{H}\leq\Lambda_{0}/2$, which
satisfies the condition of Lemma B.12. Thus, for any $\tau<t$, we have

$\displaystyle\frac{\mathrm{d}\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}^{2}}{\mathrm{d}\tau}\leq$
$\displaystyle\leavevmode\nobreak\
-(\kappa^{2}\Lambda_{0}+\lambda)\cdot\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}^{2}+2\kappa^{2}\|H(\tau)-H^{\operatorname{cts}}\|\cdot\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}\cdot\|Y-u^{*}\|_{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
-(\kappa^{2}\Lambda_{0}+\lambda)\cdot\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}^{2}+2\kappa^{2}\epsilon_{H}\cdot\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}\cdot\|Y-u^{*}\|_{2}$
(54)

where the first step follows from Lemma B.12, the second step follows from Eq.
(B.5.4). Now let us discuss two cases:

Case 1. If for all $\tau<t$,
$\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}\geq\epsilon_{\operatorname{train}}$
always holds, we want to argue that

$\displaystyle\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}^{2}\leq\exp(-(\kappa^{2}\Lambda_{0}+\lambda)t/2)\cdot\|u_{\operatorname{nn}}(0)-u^{*}\|_{2}.$

Note by assumption (51) and (52), we have

$\displaystyle\epsilon_{H}\leq\frac{\epsilon_{\operatorname{train}}}{4\kappa^{2}\|Y-u^{*}\|_{2}}(\kappa^{2}\Lambda_{0}+\lambda)$

implies

$\displaystyle
2\kappa^{2}\epsilon_{H}\cdot\|Y-u^{*}\|_{2}\leq(\kappa^{2}\Lambda_{0}+\lambda)/2\cdot\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}$

holds for any $\tau<t$. Thus, plugging into (B.5.4),

$\displaystyle\frac{\mathrm{d}\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}^{2}}{\mathrm{d}\tau}\leq\leavevmode\nobreak\
-(\kappa^{2}\Lambda_{0}+\lambda)/2\cdot\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}^{2},$

holds for all $\tau<t$, which implies

$\displaystyle\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}^{2}\leq\exp{(-(\kappa^{2}\Lambda_{0}+\lambda)t/2)}\cdot\|u_{\operatorname{nn}}(0)-u^{*}\|_{2}^{2}.$

Case 2. If there exist $\overline{\tau}<t$, such that
$\|u_{\operatorname{nn}}(\overline{\tau})-u^{*}\|_{2}<\epsilon_{\operatorname{train}}$,
we want to argue that
$\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}<\epsilon_{\operatorname{train}}$. Note
by assumption (51) and (52), we have

$\displaystyle\epsilon_{H}\leq\frac{\epsilon_{\operatorname{train}}}{4\kappa^{2}\|Y-u^{*}\|_{2}}(\kappa^{2}\Lambda_{0}+\lambda)$

implies

$\displaystyle
2\kappa^{2}\epsilon_{H}\cdot\|u_{\operatorname{nn}}(\overline{\tau})-u^{*}\|_{2}\cdot\|Y-u^{*}\|_{2}\leq(\kappa^{2}\Lambda_{0}+\lambda)\cdot\epsilon_{\operatorname{train}}^{2}.$

Thus, plugging into (B.5.4),

$\displaystyle\frac{\mathrm{d}(\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}^{2}-\epsilon_{\operatorname{train}}^{2})}{\mathrm{d}\tau}\leq\leavevmode\nobreak\
-(\kappa^{2}\Lambda_{0}+\lambda)\cdot(\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}^{2}-\epsilon_{\operatorname{train}}^{2})$

holds for $\tau=\overline{\tau}$, which implies
$e^{(\kappa^{2}\Lambda_{0}+\lambda)\tau}(\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}^{2}-\epsilon_{\operatorname{train}}^{2})$
is non-increasing at $\tau=\overline{\tau}$. Since
$\|u_{\operatorname{nn}}(\overline{\tau})-u^{*}\|_{2}^{2}-\epsilon_{\operatorname{train}}^{2}<0$,
by induction,
$e^{(\kappa^{2}\Lambda_{0}+\lambda)\tau}(\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}^{2}-\epsilon_{\operatorname{train}}^{2})$
being non-increasing and
$\|u_{\operatorname{nn}}(\tau)-u^{*}\|_{2}^{2}-\epsilon_{\operatorname{train}}^{2}<0$
holds for all $\overline{\tau}\leq\tau\leq t$, which implies

$\displaystyle\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}<\epsilon_{\operatorname{train}}.$

Combine above two cases, we conclude

$\displaystyle\|u_{\operatorname{nn}}(t)-u^{*}\|_{2}^{2}\leq\max\\{\exp(-(\kappa^{2}\Lambda_{0}+\lambda)t/2)\cdot\|u_{\operatorname{nn}}(0)-u^{*}\|_{2}^{2},\leavevmode\nobreak\
\epsilon_{\operatorname{train}}^{2}\\}.$

∎

######  Lemma B.26 (Conclusion 4).

Fix $\epsilon_{W}\in(0,1)$ independent of $t$. If $\forall r\in[m]$, we have

$\displaystyle\|w_{r}(t)-w_{r}(0)\|_{2}\leq\epsilon_{W}$

then

$\displaystyle\|\mathsf{K}_{t}(x_{\operatorname{test}},X)-\mathsf{K}_{0}(x_{\operatorname{test}},X)\|_{2}\leq\epsilon_{K}^{\prime}=2\sqrt{n}\epsilon_{W}$

holds with probability at least $1-n\cdot\exp{(-m\epsilon_{W}/10)}$.

###### Proof.

Recall the definition of $\mathsf{K}_{0}$ and $\mathsf{K}_{t}$

$\displaystyle\mathsf{K}_{0}(x_{\operatorname{test}},x_{i})=$
$\displaystyle\leavevmode\nobreak\
\frac{1}{m}\sum_{r=1}^{m}x_{\operatorname{test}}^{\top}x_{i}\sigma^{\prime}(x_{\operatorname{test}}^{\top}w_{r}(0))\sigma^{\prime}(x_{i}^{\top}w_{r}(0))$
$\displaystyle\mathsf{K}_{t}(x_{\operatorname{test}},x_{i})=$
$\displaystyle\leavevmode\nobreak\
\frac{1}{m}\sum_{r=1}^{m}x_{\operatorname{test}}^{\top}x_{i}\sigma^{\prime}(x_{\operatorname{test}}^{\top}w_{r}(t))\sigma^{\prime}(x_{i}^{\top}w_{r}(t))$

By direct calculation we have

$\displaystyle\|\mathsf{K}_{0}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X)\|_{2}^{2}\leq\sum_{i=1}^{n}\Big{(}\frac{1}{m}\sum_{r=1}^{m}s_{r,i}\Big{)}^{2},$

where

$\displaystyle s_{r,i}={\bf 1}[w_{r}(0)^{\top}x_{\operatorname{test}}\geq
0,w_{r}(0)^{\top}x_{i}\geq 0]-{\bf
1}[w_{r}(t)^{\top}x_{\operatorname{test}}\geq 0,w_{r}(t)^{\top}x_{i}\geq
0],\forall r\in[m],i\in[n].$

Fix $i\in[n]$, by Bernstein inequality (Lemma A.3), we have for any $t>0$,

$\displaystyle\Pr\Big{[}\frac{1}{m}\sum_{r=1}^{m}s_{r,i}\geq
2\epsilon_{W}\Big{]}\leq\exp(-m\epsilon_{W}/10).$

Thus, applying union bound over all training data $x_{i},\leavevmode\nobreak\
i\in[n]$, we conclude

$\displaystyle\Pr[\|\mathsf{K}_{0}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X)\|_{2}\leq
2\sqrt{n}\epsilon_{W}]\leq 1-n\cdot\exp{(-m\epsilon_{W}/10)}.$

Note by definition $\epsilon_{K}^{\prime}=2\sqrt{n}\epsilon_{W}$, so we finish
the proof. ∎

Now we summarize all the conditions need to be satisfied so that the induction
works as in Table 1.

Table 1: Summary of conditions for induction No. | Condition | Place
---|---|---
1 | $\epsilon_{W}\leq 1$ | Lem. B.23
2 | $\epsilon_{H}^{\prime}\leq\Lambda_{0}/4$ | Lem. B.25
3 | $4n(\frac{\log{(n/\delta)}}{m})^{1/2}\leq\Lambda_{0}/4$ | Lem. B.25
4 | $4n(\frac{\log{(n/\delta)}}{m})^{1/2}\leq\frac{\epsilon_{\operatorname{train}}}{8\kappa^{2}\|Y-u^{*}\|_{2}}(\kappa^{2}\Lambda_{0}+\lambda)$ | Lem. B.25
5 | $\epsilon_{H}^{\prime}\leq\frac{\epsilon_{\operatorname{train}}}{8\kappa^{2}\|Y-u^{*}\|_{2}}(\kappa^{2}\Lambda_{0}+\lambda)$ | Lem. B.25

Note by choosing If
$\kappa=\widetilde{O}(\frac{\epsilon\Lambda_{0}}{n}),\leavevmode\nobreak\
T=\widetilde{O}(\frac{1}{\kappa^{2}(\Lambda_{0}+\lambda)})$,
$\epsilon_{\operatorname{train}}=\widetilde{O}(\|u_{\operatorname{nn}}(0)-u^{*}\|_{2})$,
$m\geq\widetilde{O}(\frac{n^{10}d}{\epsilon^{6}\Lambda_{0}^{10}})$ and
$\lambda=\widetilde{O}(\frac{1}{\sqrt{m}})$, we have

$\displaystyle\|Y-u^{*}\|_{2}=$ $\displaystyle\leavevmode\nobreak\
\|(\kappa^{2}\lambda(H^{\operatorname{cts}}+\lambda I_{n})^{-1}Y\|_{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\lambda\|(\kappa^{2}H^{\operatorname{cts}}+\lambda I_{n})^{-1}\|\|Y\|_{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\widetilde{O}(\frac{\lambda\sqrt{n}}{\kappa^{2}\Lambda_{0}})$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\widetilde{O}(\frac{1}{n^{2.5}})$ (55)

where the first step follows from the definition of $u^{*}$, the second step
follows from Cauchy-Schwartz inequality, the third step follows from
$Y=O(\sqrt{n})$, and the last step follows from the choice of the parameters.

Further, with probability $1-\delta$, we have

$\displaystyle\|u_{\operatorname{nn}}(0)-u^{*}\|_{2}\leq$
$\displaystyle\leavevmode\nobreak\
\|u_{\operatorname{nn}}(0)\|_{2}+\|Y-u^{*}\|_{2}+\|Y\|_{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\widetilde{O}(\frac{\epsilon\Lambda_{0}}{\sqrt{n}})+\widetilde{O}(\frac{1}{n^{2.5}})+\widetilde{O}(\sqrt{n})$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\widetilde{O}(\sqrt{n})$

where the first step follows from triangle inequality, the second step follows
from Lemma B.20, Eq. (B.5.4) and $Y=O(\sqrt{n})$, and the last step follows
$\epsilon,\leavevmode\nobreak\ \Lambda_{0}<1$. With same reason,

$\displaystyle\|u_{\operatorname{nn}}(0)-u^{*}\|_{2}\geq$
$\displaystyle\leavevmode\nobreak\
-\|u_{\operatorname{nn}}(0)\|_{2}-\|Y-u^{*}\|_{2}+\|Y\|_{2}$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
-\widetilde{O}(\frac{\epsilon\Lambda_{0}}{\sqrt{n}})-\widetilde{O}(\frac{1}{n^{2.5}})+\widetilde{O}(\sqrt{n})$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
\widetilde{O}(\sqrt{n}).$

Thus, we have
$\|u_{\operatorname{nn}}(0)-u^{*}\|_{2}=\widetilde{O}(\sqrt{n})$.

Now, by direct calculation, we have all the induction conditions satisfied
with high probability. Note the failure probability only comes from Lemma
B.20, B.22, B.24, B.26, which only depend on the initialization. By union
bound over these failure events, we have all four conclusions in Lemma B.21
holds with high probability, which completes the proof.

####  B.5.5 Final result for upper bounding
$|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|$

In this section, we prove Lemma B.27.

######  Lemma B.27 (Upper bounding test error).

Given training data matrix $X\in\mathbb{R}^{n\times d}$ and corresponding
label vector $Y\in\mathbb{R}^{n}$. Fix the total number of iterations $T>0$.
Given arbitrary test data $x_{\operatorname{test}}\in\mathbb{R}^{d}$. Let
$u_{\operatorname{nn},\operatorname{test}}(t)\in\mathbb{R}^{n}$ and
$u_{\operatorname{ntk},\operatorname{test}}(t)\in\mathbb{R}^{n}$ be the test
data predictors defined in Definition B.3 and Definition B.5 respectively. Let
$\kappa\in(0,1)$ be the corresponding multiplier. Given accuracy $\epsilon>0$,
if $\kappa=\widetilde{O}(\frac{\epsilon\Lambda_{0}}{n})$,
$T=\widetilde{O}(\frac{1}{\kappa^{2}\Lambda_{0}})$,
$m\geq\widetilde{O}(\frac{n^{10}d}{\epsilon^{6}\Lambda_{0}^{10}})$ and
$\lambda\leq\widetilde{O}(\frac{1}{\sqrt{m}})$. Then for any
$x_{\operatorname{test}}\in\mathbb{R}^{d}$, with probability at least
$1-\delta$ over the random initialization, we have

$\displaystyle\|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)\|_{2}\leq\epsilon/2,$

where $\widetilde{O}(\cdot)$ hides
$\operatorname{poly}\log(n/(\epsilon\delta\Lambda_{0}))$.

###### Proof.

By Lemma B.14, we have

$\displaystyle|u_{\operatorname{nn},\operatorname{test}}(T)-u_{\operatorname{ntk},\operatorname{test}}(T)|\leq$
$\displaystyle\leavevmode\nobreak\
(1+\kappa^{2}nT)\epsilon_{\operatorname{init}}+\kappa^{2}\epsilon_{K}\cdot\Big{(}\frac{\|u^{*}\|_{2}}{\kappa^{2}\Lambda_{0}+\lambda}+\|u^{*}-Y\|_{2}T\Big{)}$
$\displaystyle\leavevmode\nobreak\
+\sqrt{n}T^{2}\kappa^{4}\epsilon_{H}(\|u^{*}\|_{2}+\|u^{*}-Y\|_{2})$ (56)

By Lemma B.20, we can choose
$\epsilon_{\operatorname{init}}=\epsilon(\Lambda_{0})/n$.

Further, note

$\displaystyle\|\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X)\|_{2}\leq$
$\displaystyle\leavevmode\nobreak\
\|\mathsf{K}_{\operatorname{ntk}}(x_{\operatorname{test}},X)-\mathsf{K}_{0}(x_{\operatorname{test}},X)\|_{2}+\|\mathsf{K}_{0}(x_{\operatorname{test}},X)-\mathsf{K}_{t}(x_{\operatorname{test}},X)\|_{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\