# Characterizing the spectrum of the NTK via a power series expansion

$\dagger$ Michael Murray, $\dagger$ Hui Jin, $\dagger$ Benjamin Bowman,
$\dagger{\ddagger}\mathsection$ Guido Montufar
$\dagger$ Department of Mathematics, UCLA, CA, USA
${\ddagger}$ Department of Statistics, UCLA, CA, USA
$\mathsection$ Max Planck Institute for Mathematics in the Sciences, Leipzig,
Germany
<EMAIL_ADDRESS>

###### Abstract

Under mild conditions on the network initialization we derive a power series
expansion for the Neural Tangent Kernel (NTK) of arbitrarily deep feedforward
networks in the infinite width limit. We provide expressions for the
coefficients of this power series which depend on both the Hermite
coefficients of the activation function as well as the depth of the network.
We observe faster decay of the Hermite coefficients leads to faster decay in
the NTK coefficients. Using this series, first we relate the effective rank of
the NTK to the effective rank of the input-data Gram. Second, for data drawn
uniformly on the sphere we derive an explicit formula for the eigenvalues of
the NTK, which shows faster decay in the NTK coefficients implies a faster
decay in its spectrum. From this we recover existing results on eigenvalue
asymptotics for ReLU networks and comment on how the activation function
influences the RKHS. Finally, for generic data and activation functions with
sufficiently fast Hermite coefficient decay, we derive an asymptotic upper
bound on the spectrum of the NTK.

##  1 Introduction

Neural networks currently dominate modern artificial intelligence, however,
despite their empirical success establishing a principled theoretical
foundation for them remains an active challenge. The key difficulties are that
neural networks induce nonconvex optimization objectives (Sontag & Sussmann,
1989) and typically operate in an overparameterized regime which precludes
classical statistical learning theory (Anthony & Bartlett, 2002). The
persistent success of overparameterized models tuned via non-convex
optimization suggests that the relationship between the parameterization,
optimization, and generalization is more sophisticated than that which can be
addressed using classical theory.

A recent breakthrough on understanding the success of overparameterized
networks was established through the Neural Tangent Kernel (NTK) (Jacot et
al., 2018). In the infinite width limit the optimization dynamics are
described entirely by the NTK and the parameterization behaves like a linear
model (Lee et al., 2019). In this regime explicit guarantees for the
optimization and generalization can be obtained (Du et al., 2019a, b; Arora et
al., 2019a; Allen-Zhu et al., 2019). While one must be judicious when
extrapolating insights from the NTK to finite width networks (Lee et al.,
2020), the NTK remains one of the most promising avenues for understanding
deep learning on a principled basis.

The spectrum of the NTK is fundamental to both the optimization and
generalization of wide networks. In particular, bounding the smallest
eigenvalue of the NTK Gram matrix is a staple technique for establishing
convergence guarantees for the optimization (Du et al., 2019a, b; Oymak &
Soltanolkotabi, 2020). Furthermore, the full spectrum of the NTK Gram matrix
governs the dynamics of the empirical risk (Arora et al., 2019b), and the
eigenvalues of the associated integral operator characterize the dynamics of
the generalization error outside the training set (Bowman & Montúfar, 2022a,
b). Moreover, the decay rate of the generalization error for Gaussian process
regression using the NTK can be characterized by the decay rate of the
spectrum (Caponnetto & De Vito, 2007; Cui et al., 2021; Jin et al., 2022).

The importance of the spectrum of the NTK has led to a variety of efforts to
characterize its structure via random matrix theory and other tools (Yang &
Salman, 2019; Fan & Wang, 2020). There is a broader body of work studying the
closely related Conjugate Kernel, Fisher Information Matrix, and Hessian
(Poole et al., 2016a; Pennington & Worah, 2017, 2018; Louart et al., 2018;
Karakida et al., 2020). These results often require complex random matrix
theory or operate in a regime where the input dimension is sent to infinity.
By contrast, using a just a power series expansion we are able to characterize
a variety of attributes of the spectrum for fixed input dimension and recover
key results from prior work.

###  1.1 Contributions

In Theorem 3.1 we derive coefficients for the power series expansion of the
NTK under unit variance initialization, see Assumption 2. Consequently we are
able to derive insights into the NTK spectrum, notably concerning the outlier
eigenvalues as well as the asymptotic decay.

  * •

In Theorem 4.1 and Observation 4.2 we demonstrate that the largest eigenvalue
$\lambda_{1}(\mathbf{K})$ of the NTK takes up an $\Omega(1)$ proportion of the
trace and that there are $O(1)$ outlier eigenvalues of the same order as
$\lambda_{1}(\mathbf{K})$.

  * •

In Theorem 4.3 and Theorem 4.5 we show that the effective rank
$Tr(\mathbf{K})/\lambda_{1}(\mathbf{K})$ of the NTK is upper bounded by a
constant multiple of the effective rank
$Tr(\mathbf{X}\mathbf{X}^{T})/\lambda_{1}(\mathbf{X}\mathbf{X}^{T})$ of the
input data Gram matrix for both infinite and finite width networks.

  * •

In Theorem 4.6 and Theorem 4.8 we characterize the asymptotic behavior of the
NTK spectrum for both uniform and nonuniform data distributions on the sphere.

###  1.2 Related work

Neural Tangent Kernel (NTK): the NTK was introduced by Jacot et al. (2018),
who demonstrated that in the infinite width limit neural network optimization
is described via a kernel gradient descent. As a consequence, when the network
is polynomially wide in the number of samples, global convergence guarantees
for gradient descent can be obtained (Du et al., 2019a, b; Allen-Zhu et al.,
2019; Zou & Gu, 2019; Lee et al., 2019; Zou et al., 2020; Oymak &
Soltanolkotabi, 2020; Nguyen & Mondelli, 2020; Nguyen, 2021). Furthermore, the
connection between infinite width networks and Gaussian processes, which
traces back to Neal (1996), has been reinvigorated in light of the NTK. Recent
investigations include those of Lee et al. (2018); de G. Matthews et al.
(2018); Novak et al. (2019).

Analysis of NTK Spectrum: theoretical analysis of the NTK spectrum via random
matrix theory was investigated by Yang & Salman (2019); Fan & Wang (2020) in
the high dimensional limit. Velikanov & Yarotsky (2021) demonstrated that for
ReLU networks the spectrum of the NTK integral operator asymptotically follows
a power law, which is consistent with our results for the uniform data
distribution. Basri et al. (2019) calculated the NTK spectrum for shallow ReLU
networks under the uniform distribution, which was then expanded to the
nonuniform case by Basri et al. (2020). Geifman et al. (2020) and Bietti &
Bach (2021) analyzed the reproducing kernel Hilbert spaces of the NTK for ReLU
networks and the Laplace kernel via the decay rate of the spectrum of the
kernel. In contrast to previous works, we are able to address the spectrum in
the finite dimensional setting and characterize the impact of different
activation functions on it.

Hermite Expansion: Daniely et al. (2016) used Hermite expansion to the study
the expressivity of the Conjugate Kernel. Simon et al. (2022) used this
technique to demonstrate that any dot product kernel can be realized by the
NTK or Conjugate Kernel of a shallow, zero bias network. Oymak &
Soltanolkotabi (2020) use Hermite expansion to study the NTK and establish a
quantitative bound on the smallest eigenvalue for shallow networks. This
approach was incorporated by Nguyen & Mondelli (2020) to handle convergence
for deep networks, with sharp bounds on the smallest NTK eigenvalue for deep
ReLU networks provided by Nguyen et al. (2021). The Hermite approach was
utilized by Panigrahi et al. (2020) to analyze the smallest NTK eigenvalue of
shallow networks under various activations. Finally, in a concurrent work Han
et al. (2022) use Hermite expansions to develop a principled and efficient
polynomial based approximation algorithm for the NTK and CNTK. In contrast to
the aforementioned works, here we employ the Hermite expansion to characterize
both the outlier and asymptotic portions of the spectrum for both shallow and
deep networks under general activations.

##  2 Preliminaries

For our notation, lower case letters, e.g., $x,y$, denote scalars, lower case
bold characters, e.g., $\mathbf{x},\mathbf{y}$ are for vectors, and upper case
bold characters, e.g., $\mathbf{X},\mathbf{Y}$, are for matrices. For natural
numbers $k_{1},k_{2}\in\mathbb{N}$ we let $[k_{1}]=\\{1,\ldots,k_{1}\\}$ and
$[k_{2},k_{1}]=\\{k_{2},\ldots,k_{1}\\}$. If $k_{2}>k_{1}$ then
$[k_{2},k_{1}]$ is the empty set. We use $\left\lVert\cdot\right\rVert_{p}$ to
denote the $p$-norm of the matrix or vector in question and as default use
$\left\lVert\cdot\right\rVert$ as the operator or 2-norm respectively. We use
$\mathbf{1}_{m\times n}\in\mathbb{R}^{m\times n}$ to denote the matrix with
all entries equal to one. We define $\delta_{p=c}$ to take the value $1$ if
$p=c$ and be zero otherwise. We will frequently overload scalar functions
$\phi:\mathbb{R}\rightarrow\mathbb{R}$ by applying them elementwise to vectors
and matrices. The entry in the $i$th row and $j$th column of a matrix we
access using the notation $[\mathbf{X}]_{ij}$. The Hadamard or entrywise
product of two matrices $\mathbf{X},\mathbf{Y}\in\mathbb{R}^{m\times n}$ we
denote $\mathbf{X}\odot\mathbf{Y}$ as is standard. The $p$th Hadamard power we
denote $\mathbf{X}^{\odot p}$ and define it as the Hadamard product of
$\mathbf{X}$ with itself $p$ times,

$\mathbf{X}^{\odot
p}\vcentcolon=\mathbf{X}\odot\mathbf{X}\odot\cdots\odot\mathbf{X}.$

Given a Hermitian or symmetric matrix $\mathbf{X}\in\mathbb{R}^{n\times n}$,
we adopt the convention that $\lambda_{i}(\mathbf{X})$ denotes the $i$th
largest eigenvalue,

$\lambda_{1}(\mathbf{X})\geq\lambda_{2}(\mathbf{X})\geq\cdots\geq\lambda_{n}(\mathbf{X}).$

Finally, for a square matrix $\mathbf{X}\in\mathbb{R}^{n\times n}$ we let
$Tr(\mathbf{X})=\sum_{i=1}^{n}[\mathbf{X}]_{ii}$ denote the trace.

###  2.1 Hermite Expansion

We say that a function $f\colon\mathbb{R}\rightarrow\mathbb{R}$ is square
integrable with respect to the standard Gaussian measure
$\gamma(z)=\frac{1}{\sqrt{2\pi}}e^{-z^{2}/2}$ if
$\mathbb{E}_{X\sim\mathcal{N}(0,1)}[f(X)^{2}]<\infty$. We denote by
$L^{2}(\mathbb{R},\gamma)$ the space of all such functions. The normalized
probabilist’s Hermite polynomials are defined as

$\displaystyle
h_{k}(x)=\frac{{(-1)}^{k}e^{x^{2}/2}}{\sqrt{k!}}\frac{d^{k}}{dx^{k}}e^{-x^{2}/2},\quad
k=0,1,\ldots$

and form a complete orthonormal basis in $L^{2}(\mathbb{R},\gamma)$
(O’Donnell, 2014, §11). The Hermite expansion of a function $\phi\in
L^{2}(\mathbb{R},\gamma)$ is given by
$\phi(x)=\sum_{k=0}^{\infty}\mu_{k}(\phi)h_{k}(x)$, where
$\mu_{k}(\phi)=\mathbb{E}_{X\sim\mathcal{N}(0,1)}[\phi(X)h_{k}(X)]$ is the
$k$th normalized probabilist’s Hermite coefficient of $\phi$.

###  2.2 NTK Parametrization

In what follows, for $n,d\in\mathbb{N}$ let $\mathbf{X}\in\mathbb{R}^{n\times
d}$ denote a matrix which stores $n$ points in $\mathbb{R}^{d}$ row-wise.
Unless otherwise stated, we assume $d\leq n$ and denote the $i$th row of
$\mathbf{X}_{n}$ as $\mathbf{x}_{i}$. In this work we consider fully-connected
neural networks of the form
$f^{(L+1)}\colon\mathbb{R}^{d}\rightarrow\mathbb{R}$ with $L\in\mathbb{N}$
hidden layers and a linear output layer. For a given input vector
$\mathbf{x}\in\mathbb{R}^{d}$, the activation $f^{(l)}$ and preactivation
$g^{(l)}$ at each layer $l\in[L+1]$ are defined via the following recurrence
relations,

$\displaystyle
g^{(1)}(\mathbf{x})=\gamma_{w}\mathbf{W}^{(1)}\mathbf{x}+\gamma_{b}\mathbf{b}^{(1)},\;f^{(1)}(\mathbf{x})=\phi\left(g^{(1)}(\mathbf{x})\right),$
(1) $\displaystyle
g^{(l)}(\mathbf{x})=\frac{\sigma_{w}}{\sqrt{m_{l-1}}}\mathbf{W}^{(l)}f^{(l-1)}(\mathbf{x})+\sigma_{b}\mathbf{b}^{(l)},\;f^{(l)}(\mathbf{x})=\phi\left(g^{(l)}(\mathbf{x})\right),\;\forall
l\in[2,L],$ $\displaystyle
g^{(L+1)}(\mathbf{x})=\frac{\sigma_{w}}{\sqrt{m_{L}}}\mathbf{W}^{(L+1)}f^{(L)}(\mathbf{x}),\;f^{(L+1)}(\mathbf{x})=g^{(L+1)}(\mathbf{x}).$

The parameters $\mathbf{W}^{(l)}\in\mathbb{R}^{m_{l}\times m_{l-1}}$ and
$\mathbf{b}^{(l)}\in\mathbb{R}^{m_{l}}$ are the weight matrix and bias vector
at the $l$th layer respectively, $m_{0}=d$, $m_{L+1}=1$, and
$\phi\colon\mathbb{R}\rightarrow\mathbb{R}$ is the activation function applied
elementwise. The variables $\gamma_{w},\sigma_{w}\in\mathbb{R}_{>0}$ and
$\gamma_{b},\sigma_{b}\in\mathbb{R}_{\geq 0}$ correspond to weight and bias
hyperparameters respectively. Let $\theta_{l}\in\mathbb{R}^{p}$ denote a
vector storing the network parameters
$(\mathbf{W}^{(h)},\mathbf{b}^{(h)})_{h=1}^{l}$ up to and including the $l$th
layer. The Neural Tangent Kernel (Jacot et al., 2018)
$\tilde{\Theta}^{(l)}\colon\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$
associated with $f^{(l)}$ at layer $l\in[L+1]$ is defined as

$\tilde{\Theta}^{(l)}(\mathbf{x},\mathbf{y}):=\langle\nabla_{\theta_{l}}f^{(l)}(\mathbf{x}),\nabla_{\theta_{l}}f^{(l)}(\mathbf{y})\rangle.$
(2)

We will mostly study the NTK under the following standard assumptions.

######  Assumption 1.

NTK initialization.

  1. 1.

At initialization all network parameters are distributed as $\mathcal{N}(0,1)$
and are mutually independent.

  2. 2.

The activation function satisfies $\phi\in L^{2}(\mathbb{R},\gamma)$, is
differentiable almost everywhere and its derivative, which we denote
$\phi^{\prime}$, also satisfies $\phi^{\prime}\in L^{2}(\mathbb{R},\gamma)$.

  3. 3.

The widths are sent to infinity in sequence,
$m_{1}\rightarrow\infty,m_{2}\rightarrow\infty,\ldots,m_{L}\rightarrow\infty$.
We refer to this regime as the sequential infinite width limit.

Under Assumption 1, for any $l\in[L+1]$,
$\tilde{\Theta}^{(l)}(\mathbf{x},\mathbf{y})$ converges in probability to a
deterministic limit
$\Theta^{(l)}\colon\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$
(Jacot et al., 2018) and the network behaves like a kernelized linear
predictor during training; see, e.g., Arora et al. (2019b); Lee et al. (2019);
Woodworth et al. (2020). Given access to the rows $(\mathbf{x}_{i})_{i=1}^{n}$
of $\mathbf{X}$ the NTK matrix at layer $l\in[L+1]$, which we denote
$\mathbf{K}_{l}$, is the $n\times n$ matrix with entries defined as

$[\mathbf{K}_{l}]_{ij}=\frac{1}{n}\Theta^{(l)}(\mathbf{x}_{i},\mathbf{x}_{j}),\;\forall(i,j)\in[n]\times[n].$
(3)

##  3 Expressing the NTK as a power series

We derive a power series for the NTK under the following assumptions on the
network initialization hyperparameters.

######  Assumption 2.

The hyperparameters of the network satisfy $\gamma_{w}^{2}+\gamma_{b}^{2}=1$,
$\sigma_{w}^{2}\mathbb{E}_{Z\sim\mathcal{N}(0,1)}[\phi(Z)^{2}]\leq 1$ and
$\sigma_{b}^{2}=1-\sigma_{w}^{2}\mathbb{E}_{Z\sim\mathcal{N}(0,1)}[\phi(Z)^{2}]$.
The data is normalized so that $\left\lVert\mathbf{x}_{i}\right\rVert=1$ for
all $i\in[n]$.

Recall under Assumption 1 that the preactivations of the network are centered
Gaussian processes (Neal, 1996; Lee et al., 2018). Assumption 2 ensures the
preactivation of each neuron has unit variance and thus is reminiscent of the
LeCun et al. (2012), Glorot & Bengio (2010) and He et al. (2015)
initializations, which are designed to avoid vanishing and exploding
gradients. We refer the reader to Appendix A.3 for a thorough discussion.
Under Assumption 2 we will also show it is possible to write the NTK not only
as a dot-product kernel, but also as an analytic power series on $[-1,1]$. In
order to state this result recall, given a function $f\in
L^{2}(\mathbb{R},\gamma)$, that we denote the $p$th normalized probabilist’s
Hermite coefficient of $f$ as $\mu_{p}(f)$, we refer the reader to Appendix
A.4 for an overview of the Hermite polynomials and their properties.
Furthermore, letting $\bar{a}=(a_{j})_{j=0}^{\infty}$ denote a sequence of
real numbers, then for any $p,k\in\mathbb{Z}_{\geq 0}$ we define

$F(p,k,\bar{a})=\begin{cases}1,\;&k=0\text{ and }p=0,\\\ 0,\;&k=0\text{ and
}p\geq 1,\\\
\sum_{(j_{i})\in\mathcal{J}(p,k)}\prod_{i=1}^{k}a_{j_{i}},\;&k\geq 1\text{ and
}p\geq 0,\end{cases}$ (4)

where

$\mathcal{J}(p,k)\vcentcolon=\big{\\{}(j_{i})_{i\in[k]}\;:\;j_{i}\geq
0\;\forall i\in[k],\;\sum_{i=1}^{k}j_{i}=p\big{\\}}\quad\text{for all
$p\in\mathbb{Z}_{\geq 0}$, $k\in\mathbb{N}$}.$

Here $\mathcal{J}(p,k)$ is the set of all $k$-tuples of nonnegative integers
which sum to $p$ and $F(p,k,\bar{a})$ is therefore the sum of all ordered
products of $k$ elements of $\bar{a}$ whose indices sum to $p$. We are now
ready to state the key result of this section, Theorem 3.1, whose proof is
provided in Appendix B.1.

######  Theorem 3.1.

Under Assumptions 1 and 2, for all $l\in[L+1]$

$n\mathbf{K}_{l}=\sum_{p=0}^{\infty}\kappa_{p,l}\left(\mathbf{X}\mathbf{X}^{T}\right)^{\odot
p}.$ (5)

The series for each entry $n[\mathbf{K}_{l}]_{ij}$ converges absolutely and
the coefficients $\kappa_{p,l}$ are nonnegative and can be evaluated using the
recurrence relationships

$\kappa_{p,l}=\begin{cases}\delta_{p=0}\gamma_{b}^{2}+\delta_{p=1}\gamma_{w}^{2},&l=1,\\\
\alpha_{p,l}+\sum_{q=0}^{p}\kappa_{q,l-1}\upsilon_{p-q,l},&l\in[2,L+1],\end{cases}$
(6)

where

$\alpha_{p,l}=\begin{cases}\sigma_{w}^{2}\mu_{p}^{2}(\phi)+\delta_{p=0}\sigma_{b}^{2},&l=2,\\\
\sum_{k=0}^{\infty}\alpha_{k,2}F(p,k,\bar{\alpha}_{l-1}),&l\geq 3,\end{cases}$
(7)

and

$\upsilon_{p,l}=\begin{cases}\sigma_{w}^{2}\mu_{p}^{2}(\phi^{\prime}),&l=2,\\\
\sum_{k=0}^{\infty}\upsilon_{k,2}F(p,k,\bar{\alpha}_{l-1}),&l\geq
3,\end{cases}$ (8)

are likewise nonnegative for all $p\in\mathbb{Z}_{\geq 0}$ and $l\in[2,L+1]$.

To compute the coefficients of the NTK as per Theorem 3.1, the Hermite
coefficients of both $\phi$ and $\phi^{\prime}$ are required. Under Assumption
3 below, which has minimal impact on the generality of our results, this
calculation can be simplified. In short, under Assumption 3
$\upsilon_{p,2}=(p+1)\alpha_{p+1,2}$ and therefore only the Hermite
coefficients of $\phi$ are required. We refer the reader to Lemma B.3 in
Appendix B.2 for further details.

######  Assumption 3.

The activation function $\phi\colon\mathbb{R}\rightarrow\mathbb{R}$ is
absolutely continuous on $[-a,a]$ for all $a>0$, differentiable almost
everywhere, and is polynomially bounded, i.e.,
$|\phi(x)|=\mathcal{O}(|x|^{\beta})$ for some $\beta>0$. Further, the
derivative $\phi^{\prime}\colon\mathbb{R}\rightarrow\mathbb{R}$ satisfies
$\phi^{\prime}\in L^{2}(\mathbb{R},\gamma)$.

We remark that ReLU, Tanh, Sigmoid, Softplus and many other commonly used
activation functions satisfy Assumption 3. In order to understand the
relationship between the Hermite coefficients of the activation function and
the coefficients of the NTK, we first consider the simple two-layer case with
$L=1$ hidden layers. From Theorem 3.1

$\kappa_{p,2}=\sigma_{w}^{2}(1+\gamma_{w}^{2}p)\mu_{p}^{2}(\phi)+\sigma_{w}^{2}\gamma_{b}^{2}(1+p)\mu_{p+1}^{2}(\phi)+\delta_{p=0}\sigma_{b}^{2}.$
(9)

As per Table 1, a general trend we observe across all activation functions is
that the first few coefficients account for the large majority of the total
NTK coefficient series.

Table 1: Percentage of $\sum_{p=0}^{\infty}\kappa_{p,2}$ accounted for by the first $T+1$ NTK coefficients assuming $\gamma_{w}^{2}=1$, $\gamma_{b}^{2}=0$, $\sigma_{w}^{2}=1$ and $\sigma_{b}^{2}=1-\mathbb{E}[\phi(Z)^{2}]$. $T=$ |  0 |  1 |  2 |  3 |  4 |  5
---|---|---|---|---|---|---
ReLU |  43.944 |  77.277 |  93.192 |  93.192 |  95.403 |  95.403
Tanh |  41.362 |  91.468 |  91.468 |  97.487 |  97.487 |  99.090
Sigmoid |  91.557 |  99.729 |  99.729 |  99.977 |  99.977 |  99.997
Gaussian |  95.834 |  95.834 |  98.729 |  98.729 |  99.634 |  99.634

However, the asymptotic rate of decay of the NTK coefficients varies
significantly by activation function, due to the varying behavior of their
tails. In Lemma 3.2 we choose ReLU, Tanh and Gaussian as prototypical examples
of activations functions with growing, constant, and decaying tails
respectively, and analyze the corresponding NTK coefficients in the two layer
setting. For typographical ease we denote the zero mean Gaussian density
function with variance $\sigma^{2}$ as
$\omega_{\sigma}(z)\vcentcolon=(1/\sqrt{2\pi\sigma^{2}})\exp\left(-z^{2}/(2\sigma^{2})\right)$.

######  Lemma 3.2.

Under Assumptions 1 and 2,

  1. 1.

if $\phi(z)=ReLU(z)$, then $\kappa_{p,2}=\delta_{(\gamma_{b}>0)\cup(p\text{
even})}\Theta(p^{-3/2})$,

  2. 2.

if $\phi(z)=Tanh(z)$, then
$\kappa_{p,2}=\mathcal{O}\left(\exp\left(-\frac{\pi\sqrt{p-1}}{2}\right)\right)$,

  3. 3.

if $\phi(z)=\omega_{\sigma}(z)$, then
$\kappa_{p,2}=\delta_{(\gamma_{b}>0)\cup(p\text{
even})}\Theta(p^{1/2}(\sigma^{2}+1)^{-p})$.

The trend we observe from Lemma 3.2 is that activation functions whose Hermite
coefficients decay quickly, such as $\omega_{\sigma}$, result in a faster
decay of the NTK coefficients. We remark that analyzing the rates of decay in
the deep setting is challenging due to the calculation of
$F(p,k,\bar{\alpha}_{l-1})$ (4) and therefore leave this study to future work.

Finally, we briefly pause here to highlight the potential for using a
truncation of (5) in order to perform efficient numerical approximation of the
infinite width NTK. We remark that this idea is also addressed in a concurrent
work by Han et al. (2022), albeit under a somewhat different set of
assumptions 111In particular, in Han et al. (2022) the authors focus on
homogeneous activation functions and allow the data to lie off the sphere. By
contrast, we require the data to lie on the sphere but can handle non-
homogeneous activation functions in the deep setting.. As per our observations
thus far that the coefficients of the NTK power series (5) typically decay
quite rapidly, one might consider approximating $\Theta^{(l)}$ by computing
just the first few terms in each series of (5). Furthermore Figure 2 in
Appendix B.3 shows the absolute error between the truncated ReLU NTK and the
analytical expression for the ReLU NTK, which is also defined in Appendix B.3.
Let $\rho$ denote the input correlation. The key takeaway is that while for
$\left\lvert\rho\right\rvert$ close to one the approximation is poor, for
$\left\lvert\rho\right\rvert<0.5$, which is arguably more realistic for real-
world data, with just $50$ coefficients machine level precision can be
achieved. We refer the interested reader to Appendix B.3 for a proper
discussion.

##  4 Analyzing the spectrum of the NTK via its power series

In this section, we consider a general kernel matrix power series of the form
$n\mathbf{K}=\sum_{p=0}^{\infty}c_{p}(\mathbf{X}\mathbf{X}^{T})^{\odot p}$
where $\\{c_{p}\\}_{p=0}^{\infty}$ are coefficients and $\mathbf{X}$ is the
data matrix. According to Theorem 3.1, the coefficients of the NTK power
series (5) are always nonnegative, thus we only consider the case where
$c_{p}$ are nonnegative. We will also consider the kernel function power
series, which we denote as $K(x_{1},x_{2})=\sum_{p=0}^{\infty}c_{p}\langle
x_{1},x_{2}\rangle^{p}$. Later on we will analyze the spectrum of kernel
matrix $\mathbf{K}$ and kernel function $K$.

###  4.1 Analysis of the upper spectrum and effective rank

In this section we analyze the upper part of the spectrum of the NTK,
corresponding to the large eigenvalues, using the power series given in
Theorem 3.1. Our first result concerns the effective rank (Huang et al., 2022)
of the NTK. Given a positive semidefinite matrix
$\mathbf{A}\in\mathbb{R}^{n\times n}$ we define the effective rank of
$\mathbf{A}$ to be

$\mathrm{eff}(\mathbf{A})=\frac{Tr(\mathbf{A})}{\lambda_{1}(\mathbf{A})}.$

The effective rank quantifies how many eigenvalues are on the order of the
largest eigenvalue. This follows from the Markov-like inequality

$\left\lvert\\{p:\lambda_{p}(\mathbf{A})\geq
c\lambda_{1}(\mathbf{A})\\}\right\rvert\leq c^{-1}\mathrm{eff}(\mathbf{A})$
(10)

and the eigenvalue bound

$\frac{\lambda_{p}(\mathbf{A})}{\lambda_{1}(\mathbf{A})}\leq\frac{\mathrm{eff}(\mathbf{A})}{p}.$

Our first result is that the effective rank of the NTK can be bounded in terms
of a ratio involving the power series coefficients. As we are assuming the
data is normalized so that $\left\lVert\mathbf{x}_{i}\right\rVert=1$ for all
$i\in[n]$, then observe by the linearity of the trace

$Tr(n\mathbf{K})=\sum_{p=0}^{\infty}c_{p}Tr((\mathbf{X}\mathbf{X}^{T})^{\odot
p})=n\sum_{p=0}^{\infty}c_{p},$

where we have used the fact that $Tr((\mathbf{X}\mathbf{X}^{T})^{\odot p})=n$
for all $p\in\mathbb{N}$. On the other hand,

$\lambda_{1}(n\mathbf{K})\geq\lambda_{1}(c_{0}(\mathbf{X}\mathbf{X}^{T})^{0})=\lambda_{1}(c_{0}\mathbf{1}_{n\times
n})=nc_{0}.$

Combining these two results we get the following theorem.

######  Theorem 4.1.

Assume that we have a kernel Gram matrix $\mathbf{K}$ of the form
$n\mathbf{K}=\sum_{p=0}^{\infty}c_{p}(\mathbf{X}\mathbf{X}^{T})^{\odot p}$
where $c_{0}\neq 0$. Furthermore, assume the input data $\mathbf{x}_{i}$ are
normalized so that $\left\lVert\mathbf{x}_{i}\right\rVert=1$ for all
$i\in[n]$. Then

$\mathrm{eff}(\mathbf{K})\leq\frac{\sum_{p=0}^{\infty}c_{p}}{c_{0}}.$

By Theorem 3.1 $c_{0}\neq 0$ provided the network has biases or the activation
function has nonzero Gaussian expectation (i.e., $\mu_{0}(\phi)\neq 0$). Thus
we have that the effective rank of $\mathbf{K}$ is bounded by an $O(1)$
quantity. In the case of ReLU for example, as evidenced by Table 1, the
effective rank will be roughly $2.3$ for a shallow network. By contrast, a
well-conditioned matrix would have an effective rank that is $\Omega(n)$.
Combining Theorem 4.1 and the Markov-type bound (10) we make the following
important observation.

######  Observation 4.2.

The largest eigenvalue $\lambda_{1}(\mathbf{K})$ of the NTK takes up an
$\Omega(1)$ fraction of the entire trace and there are $O(1)$ eigenvalues on
the same order of magnitude as $\lambda_{1}(\mathbf{K})$, where the $O(1)$ and
$\Omega(1)$ notation are with respect to the parameter $n$.

While the constant term $c_{0}\mathbf{1}_{n\times n}$ in the kernel leads to a
significant outlier in the spectrum of $\mathbf{K}$, it is rather
uninformative beyond this. What interests us is how the structure of the data
$\mathbf{X}$ manifests in the spectrum of the kernel matrix $\mathbf{K}$. For
this reason we will examine the centered kernel matrix
$\widetilde{\mathbf{K}}:=\mathbf{K}-\frac{c_{0}}{n}\mathbf{1}_{n\times n}$. By
a very similar argument as before we get the following result.

######  Theorem 4.3.

Assume that we have a kernel Gram matrix $\mathbf{K}$ of the form
$n\mathbf{K}=\sum_{p=0}^{\infty}c_{p}(\mathbf{X}\mathbf{X}^{T})^{\odot p}$
where $c_{1}\neq 0$. Furthermore, assume the input data $\mathbf{x}_{i}$ are
normalized so that $\left\lVert\mathbf{x}_{i}\right\rVert=1$ for all
$i\in[n]$. Then the centered kernel
$\widetilde{\mathbf{K}}:=\mathbf{K}-\frac{c_{0}}{n}\mathbf{1}_{n\times n}$
satisfies

$\mathrm{eff}(\widetilde{\mathbf{K}})\leq\mathrm{eff}(\mathbf{X}\mathbf{X}^{T})\frac{\sum_{p=1}^{\infty}c_{p}}{c_{1}}.$

Thus we have that the effective rank of the centered kernel
$\widetilde{\mathbf{K}}$ is upper bounded by a constant multiple of the
effective rank of the input data Gram $\mathbf{X}\mathbf{X}^{T}$. Furthermore,
we can take the ratio $\frac{\sum_{p=1}^{\infty}c_{p}}{c_{1}}$ as a measure of
how much the NTK inherits the behavior of the linear kernel
$\mathbf{X}\mathbf{X}^{T}$: in particular, if the input data gram has low
effective rank and this ratio is moderate then we may conclude that the
centered NTK must also have low effective rank. Again from Table 1, in the
shallow setting we see that this ratio tends to be small for many of the
common activations, for example, for ReLU it is roughly 1.3. To summarize then
from Theorem 4.3 we make the important observation.

######  Observation 4.4.

Whenever the input data are approximately low rank, the centered kernel matrix
$\widetilde{\mathbf{K}}=\mathbf{K}-\frac{c_{0}}{n}\mathbf{1}_{n\times n}$ is
also approximately low rank.

It turns out that this phenomenon also holds for finite-width networks at
initialization. Consider the shallow model

$\sum_{\ell=1}^{m}a_{\ell}\phi(\langle\mathbf{w}_{\ell},\mathbf{x}\rangle),$

where $\mathbf{x}\in\mathbb{R}^{d}$ and $\mathbf{w}_{\ell}\in\mathbb{R}^{d}$,
$a_{\ell}\in\mathbb{R}$ for all $\ell\in[m]$. The following theorem
demonstrates that when the width $m$ is linear in the number of samples $n$
then $\mathrm{eff}(\mathbf{K})$ is upper bounded by a constant multiple of
$\mathrm{eff}(\mathbf{X}\mathbf{X}^{T})$.

######  Theorem 4.5.

Assume $\phi(x)=ReLU(x)$ and $n\geq d$. Fix $\epsilon>0$ small. Suppose that
$\mathbf{w}_{1},\ldots,\mathbf{w}_{m}\sim N(0,\nu_{1}^{2}I_{d})$ i.i.d. and
$a_{1},\ldots,a_{m}\sim N(0,\nu_{2}^{2})$. Set
$M=\max_{i\in[n]}\left\lVert\mathbf{x}_{i}\right\rVert_{2}$, and let

$\Sigma:=\mathbb{E}_{\mathbf{w}\sim
N(0,\nu_{1}^{2}I)}[\phi(\mathbf{X}\mathbf{w})\phi(\mathbf{w}^{T}\mathbf{X}^{T})].$

Then

$m=\Omega\left(\max(\lambda_{1}(\Sigma)^{-2},1)\max(n,\log(1/\epsilon))\right),\quad\nu_{1}=O(1/M\sqrt{m})$

suffices to ensure that, with probability at least $1-\epsilon$ over the
sampling of the parameter initialization,

$\mathrm{eff}(\mathbf{K})\leq C\cdot\mathrm{eff}(\mathbf{X}\mathbf{X}^{T}),$

where $C>0$ is an absolute constant.

Many works consider the model where the outer layer weights are fixed and have
constant magnitude and only the inner layer weights are trained. This is the
setting considered by Xie et al. (2017), Arora et al. (2019a), Du et al.
(2019b), Oymak et al. (2019), Li et al. (2020), and Oymak & Soltanolkotabi
(2020). In this setting we can reduce the dependence on the width $m$ to only
be logarithmic in the number of samples $n$, and we have an accompanying lower
bound. See Theorem C.5 in the Appendix C.2.3 for details.

In Figure 1 we empirically validate our theory by computing the spectrum of
the NTK on both Caltech101 (Li et al., 2022) and isotropic Gaussian data for
feedforward networks. We use the
functorch222https://pytorch.org/functorch/stable/notebooks/neural_tangent_kernels.html
module in PyTorch (Paszke et al., 2019) using an algorithmic approach inspired
by Novak et al. (2022). As per Theorem 4.1 and Observation 4.2, we observe all
network architectures exhibit a dominant outlier eigenvalue due to the nonzero
constant coefficient in the power series. Furthermore, this dominant outlier
becomes more pronounced with depth, as can be observed if one carries out the
calculations described in Theorem 3.1. Additionally, this outlier is most
pronounced for ReLU, as the combination of its Gaussian mean plus bias term is
the largest out of the activations considered here. As predicted by Theorem
4.3, Observation 4.4 and Theorem 4.5, we observe real-world data, which has a
skewed spectrum and hence a low effective rank, results in the spectrum of the
NTK being skewed. By contrast, isotropic Gaussian data has a flat spectrum,
and as a result beyond the outlier the decay of eigenvalues of the NTK is more
gradual. These observations support the claim that the NTK inherits its
spectral structure from the data. We also observe that the spectrum for Tanh
is closer to the linear activation relative to ReLU: intuitively this should
not be surprising as close to the origin Tanh is well approximated by the
identity. Our theory provides a formal explanation for this observation,
indeed, the power series coefficients for Tanh networks decay quickly relative
to ReLU. We provide further experimental results in Appendix C.3, including
for CNNs where we observe the same trends. We note that the effective rank has
implications for the generalization error. The Rademacher complexity of a
kernel method (and hence the NTK model) within a parameter ball is determined
by its its trace (Bartlett & Mendelson, 2002). Since for the NTK
$\lambda_{1}(\mathbf{K})=O(1)$, lower effective rank implies smaller trace and
hence limited complexity.

Figure 1:  (Feedforward NTK Spectrum)  We plot the normalized eigenvalues
$\lambda_{p}/\lambda_{1}$ of the NTK Gram matrix $\mathbf{K}$ and the data
Gram matrix $\mathbf{X}\mathbf{X}^{T}$ for Caltech101 and isotropic Gaussian
datasets. To compute the NTK we randomly initialize feedforward networks of
depths $2$ and $5$ with width $500$. We use the standard parameterization and
Pytorch’s default Kaiming uniform initialization in order to better connect
our results with what is used in practice. We consider a batch size of $n=200$
and plot the first $100$ eigenvalues. The thick part of each curve corresponds
to the mean across 10 trials, while the transparent part corresponds to the
95% confidence interval

###  4.2 Analysis of the lower spectrum

In this section, we analyze the lower part of the spectrum using the power
series. We first analyze the kernel function $K$ which we recall is a dot-
product kernel of the form $K(x_{1},x_{2})=\sum_{p=0}^{\infty}c_{p}\langle
x_{1},x_{2}\rangle^{p}$. Assuming the training data is uniformly distributed
on a hypersphere it was shown by Basri et al. (2019); Bietti & Mairal (2019)
that the eigenfunctions of $K$ are the spherical harmonics. The following
theorem gives the eigenvalues of the kernel $K$ in this setting.

######  Theorem 4.6.

Suppose that the training data are uniformly sampled from the unit hypersphere
$\mathbb{S}^{d}$, $d\geq 2$. If the dot-product kernel function has the
expansion $K(x_{1},x_{2})=\sum_{p=0}^{\infty}c_{p}\langle
x_{1},x_{2}\rangle^{p}$ where $c_{p}\geq 0$, then the eigenvalue of every
spherical harmonic of frequency $k$ is given by

$\overline{\lambda_{k}}=\frac{\pi^{d/2}}{2^{k-1}}\sum_{\begin{subarray}{c}p\geq
k\\\ p-k\text{ is
even}\end{subarray}}c_{p}\frac{\Gamma(p+1)\Gamma(\frac{p-k+1}{2})}{\Gamma(p-k+1)\Gamma(\frac{p-k+1}{2}+k+d/2)},$

where $\Gamma$ is the gamma function.

A proof of Theorem 4.6 is provided in Appendix C.4. This theorem connects the
coefficients $c_{p}$ of the kernel power series with the eigenvalues
$\overline{\lambda_{k}}$ of the kernel. In particular, given a specific decay
rate for the coefficients $c_{p}$ one may derive the decay rate of
$\overline{\lambda_{k}}$ as illustrated in the following Corollary.

######  Corollary 4.7.

Under the same setting as in Theorem 4.6,

  1. 1.

if $c_{p}=\Theta(p^{-a})$ where $a\geq 1$, then
$\overline{\lambda_{k}}=\Theta(k^{-d-2a+2})$,

  2. 2.

if $c_{p}=\delta_{(p\text{ even})}\Theta(p^{-a})$, then
$\overline{\lambda_{k}}=\delta_{(k\text{ even})}\Theta(k^{-d-2a+2})$,

  3. 3.

if $c_{p}=\mathcal{O}\left(\exp\left(-a\sqrt{p}\right)\right)$, then
$\overline{\lambda_{k}}=\mathcal{O}\left(k^{-d+1/2}\exp\left(-a\sqrt{k}\right)\right)$,

  4. 4.

if $c_{p}=\Theta(p^{1/2}a^{-p})$, then
$\overline{\lambda_{k}}=\mathcal{O}\left(k^{-d+1}a^{-k}\right)$ and
$\overline{\lambda_{k}}=\Omega\left(k^{-d/2+1}2^{-k}a^{-k}\right)$.

For the NTK of a two-layer ReLU network with $\gamma_{b}>0$, then according to
Lemma 3.2 we have $c_{p}=\kappa_{p,2}=\Theta(p^{-3/2})$ . Therefore using
Corollary 4.7 $\overline{\lambda_{k}}=\Theta(k^{-d-1})$. Notice here that $k$
refers to the frequency, and the number of spherical harmonics of frequency at
most $k$ is $\Theta(k^{d})$. Therefore, for the $\ell$th largest eigenvalue
$\lambda_{\ell}$ we have $\lambda_{\ell}=\Theta(\ell^{-(d+1)/d})$. This rate
agrees with Basri et al. (2019) and Velikanov & Yarotsky (2021). For the NTK
of a two-layer ReLU network with $\gamma_{b}=0$, the eigenvalues corresponding
to the even frequencies are $0$, which also agrees with Basri et al. (2019).
Corollary 4.7 also shows the decay rates of eigenvalues for the NTK of two-
layer networks with Tanh activation and Gaussian activation. We observe that
when the coefficients of the kernel power series decay quickly then the
eigenvalues of the kernel also decay quickly. As faster decay of the
eigenvalues of the kernel implies a smaller RKHS (Geifman et al., 2020),
Corollary 4.7 demonstrates that using ReLU results in a larger RKHS relative
to using either Tanh or Gaussian activations. We numerically illustrate
Corollary 4.7 in Figure 4, Appendix C.3,

We now briefly touch on how one can relate the coefficients of a power series
kernel to its spectrum without making any assumptions on the data
distribution.

######  Theorem 4.8 (Informal).

Let the rows of $\mathbf{X}\in\mathbb{R}^{n\times d}$ be arbitrary points on
the unit sphere. Consider the kernel matrix
$n\mathbf{K}=\sum_{p=0}^{\infty}c_{p}\left(\mathbf{X}\mathbf{X}^{T}\right)^{\odot
p}$ and let $r(n)\leq d$ denote the rank of $\mathbf{X}\mathbf{X}^{T}$. Then

  1. 1.

if $c_{p}=\mathcal{O}(p^{-\alpha})$ with $\alpha>r(n)+1$ for all
$n\in\mathbb{Z}_{\geq 0}$ then
$\lambda_{n}(\mathbf{K})=\mathcal{O}\left(n^{-\frac{\alpha-1}{r(n)}}\right)$,

  2. 2.

if $c_{p}=\mathcal{O}(e^{-\alpha\sqrt{p}})$ then
$\lambda_{n}(\mathbf{K})=\mathcal{O}\left(n^{\frac{1}{2r(n)}}\exp\left(-\alpha^{\prime}n^{\frac{1}{2r(n)}}\right)\right)$
for any $\alpha^{\prime}<\alpha 2^{-1/2r(n)}$,

  3. 3.

if $c_{p}=\mathcal{O}(e^{-\alpha p})$ then
$\lambda_{n}(\mathbf{K})=\mathcal{O}\left(\exp\left(-\alpha^{\prime}n^{\frac{1}{r(n)}}\right)\right)$
for any $\alpha^{\prime}<\alpha 2^{-1/2r(n)}$.

Although the presence of the factor $1/r(n)$ in the exponents of $n$ in these
bounds is a weakness, Theorem 4.8 still illustrates how, in a highly general
setting, the asymptotic decay of the coefficients of the power series ensures
a certain asymptotic decay in the eigenvalues of the kernel matrix. A formal
version of this result is provided in Appendix C.5 along with further
discussion.

##  5 Conclusion

Using a power series expansion we derived a number of insights into both the
outliers as well as the asymptotic decay of the spectrum of the NTK. We are
able to perform our analysis without recourse to a high dimensional limit or
the use of random matrix theory. Interesting avenues for future work include
better characterizing the role of depth and performing the same analysis on
networks with convolutional or residual layers.

##### Reproducibility Statement

To ensure reproducibility, we make the code public at
https://github.com/bbowman223/data_ntk.

## Acknowledgements and Disclosure of Funding

This project has been supported by ERC Grant 757983 and NSF CAREER Grant
DMS-2145630.

## References

  * Allen-Zhu et al. (2019) Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pp. 242–252. PMLR, 2019.  URL https://proceedings.mlr.press/v97/allen-zhu19a.html.
  * Anthony & Bartlett (2002) Martin Anthony and Peter L. Bartlett.  _Neural Network Learning - Theoretical Foundations_.  Cambridge University Press, 2002.  URL http://www.cambridge.org/gb/knowledge/isbn/item1154061/?site_locale=en_GB.
  * Arora et al. (2019a) Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pp. 322–332. PMLR, 2019a.  URL https://proceedings.mlr.press/v97/arora19a.html.
  * Arora et al. (2019b) Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang.  On exact computation with an infinitely wide neural net.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019b.  URL https://proceedings.neurips.cc/paper/2019/file/dbc4d84bfcfe2284ba11beffb853a8c4-Paper.pdf.
  * Bartlett & Mendelson (2002) Peter L. Bartlett and Shahar Mendelson.  Rademacher and gaussian complexities: Risk bounds and structural results.  _J. Mach. Learn. Res._ , 3:463–482, 2002.  URL http://dblp.uni-trier.de/db/journals/jmlr/jmlr3.html#BartlettM02.
  * Basri et al. (2019) Ronen Basri, David W. Jacobs, Yoni Kasten, and Shira Kritchman.  The convergence rate of neural networks for learned functions of different frequencies.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett (eds.), _Advances in Neural Information Processing Systems 32_ , pp. 4763–4772, 2019.  URL https://proceedings.neurips.cc/paper/2019/hash/5ac8bb8a7d745102a978c5f8ccdb61b8-Abstract.html.
  * Basri et al. (2020) Ronen Basri, Meirav Galun, Amnon Geifman, David Jacobs, Yoni Kasten, and Shira Kritchman.  Frequency bias in neural networks for input of non-uniform density.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pp. 685–694. PMLR, 2020.  URL https://proceedings.mlr.press/v119/basri20a.html.
  * Bietti & Bach (2021) Alberto Bietti and Francis Bach.  Deep equals shallow for ReLU networks in kernel regimes.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=aDjoksTpXOP.
  * Bietti & Mairal (2019) Alberto Bietti and Julien Mairal.  On the inductive bias of neural tangent kernels.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/c4ef9c39b300931b69a36fb3dbb8d60e-Paper.pdf.
  * Bowman & Montúfar (2022a) Benjamin Bowman and Guido Montúfar.  Spectral bias outside the training set for deep networks in the kernel regime.  _CoRR_ , abs/2206.02927, 2022a.  URL https://doi.org/10.48550/arXiv.2206.02927.
  * Bowman & Montúfar (2022b) Benjamin Bowman and Guido Montúfar.  Implicit bias of MSE gradient optimization in underparameterized neural networks.  In _International Conference on Learning Representations_ , 2022b.  URL https://openreview.net/forum?id=VLgmhQDVBV.
  * Caponnetto & De Vito (2007) Andrea Caponnetto and Ernesto De Vito.  Optimal rates for the regularized least-squares algorithm.  _Foundations of Computational Mathematics_ , 7(3):331–368, 2007.
  * Cui et al. (2021) Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová.  Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime.  In _Advances in Neural Information Processing Systems_ , 2021.  URL https://openreview.net/forum?id=Da_EHrAcfwd.
  * Daniely et al. (2016) Amit Daniely, Roy Frostig, and Yoram Singer.  Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity.  In _Advances in Neural Information Processing Systems_ , volume 29. Curran Associates, Inc., 2016.  URL https://proceedings.neurips.cc/paper/2016/file/abea47ba24142ed16b7d8fbf2c740e0d-Paper.pdf.
  * Davis (2021) Tom Davis.  A general expression for Hermite expansions with applications.  2021\.  doi: 10.13140/RG.2.2.30843.44325.  URL https://www.researchgate.net/profile/Tom-Davis-2/publication/352374514_A_GENERAL_EXPRESSION_FOR_HERMITE_EXPANSIONS_WITH_APPLICATIONS/links/60c873c5a6fdcc8267cf74d4/A-GENERAL-EXPRESSION-FOR-HERMITE-EXPANSIONS-WITH-APPLICATIONS.pdf.
  * de G. Matthews et al. (2018) Alexander G. de G. Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahramani.  Gaussian process behaviour in wide deep neural networks.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=H1-nGgWC-.
  * Du et al. (2019a) Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai.  Gradient descent finds global minima of deep neural networks.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pp. 1675–1685. PMLR, 2019a.  URL https://proceedings.mlr.press/v97/du19c.html.
  * Du et al. (2019b) Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh.  Gradient descent provably optimizes over-parameterized neural networks.  In _International Conference on Learning Representations_ , 2019b.  URL https://openreview.net/forum?id=S1eK3i09YQ.
  * Engel et al. (2022) Andrew Engel, Zhichao Wang, Anand Sarwate, Sutanay Choudhury, and Tony Chiang.  TorchNTK: A library for calculation of neural tangent kernels of PyTorch models.  2022\.
  * Fan & Wang (2020) Zhou Fan and Zhichao Wang.  Spectra of the conjugate kernel and neural tangent kernel for linear-width neural networks.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 7710–7721. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/572201a4497b0b9f02d4f279b09ec30d-Paper.pdf.
  * Folland (1999) G. B. Folland.  _Real analysis: Modern techniques and their applications_.  Wiley, New York, 1999.
  * Geifman et al. (2020) Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Basri Ronen.  On the similarity between the Laplace and neural tangent kernels.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 1451–1461. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/1006ff12c465532f8c574aeaa4461b16-Paper.pdf.
  * Glorot & Bengio (2010) Xavier Glorot and Yoshua Bengio.  Understanding the difficulty of training deep feedforward neural networks.  In _Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics_ , volume 9 of _Proceedings of Machine Learning Research_ , pp. 249–256. PMLR, 2010.  URL https://proceedings.mlr.press/v9/glorot10a.html.
  * Han et al. (2022) Insu Han, Amir Zandieh, Jaehoon Lee, Roman Novak, Lechao Xiao, and Amin Karbasi.  Fast neural kernel embeddings for general activations.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=yLilJ1vZgMe.
  * He et al. (2015) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In _2015 IEEE International Conference on Computer Vision (ICCV)_ , pp. 1026–1034, 2015.
  * Huang et al. (2022) Ningyuan Teresa Huang, David W. Hogg, and Soledad Villar.  Dimensionality reduction, regularization, and generalization in overparameterized regressions.  _SIAM J. Math. Data Sci._ , 4(1):126–152, 2022\.  URL https://doi.org/10.1137/20m1387821.
  * Jacot et al. (2018) Arthur Jacot, Franck Gabriel, and Clement Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  In _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper/2018/file/5a4be1fa34e62bb8a6ec6b91d2462f5a-Paper.pdf.
  * Jin et al. (2022) Hui Jin, Pradeep Kr. Banerjee, and Guido Montúfar.  Learning curves for gaussian process regression with power-law priors and targets.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=KeI9E-gsoB.
  * Karakida et al. (2020) Ryo Karakida, Shotaro Akaho, and Shun ichi Amari.  Universal statistics of Fisher information in deep neural networks: mean field approach.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2020(12):124005, 2020.  URL https://doi.org/10.1088/1742-5468/abc62e.
  * Kazarinoff (1956) Donat K. Kazarinoff.  On Wallis’ formula.  _Edinburgh Mathematical Notes_ , 40:19–21, 1956.
  * LeCun et al. (2012) Yann A. LeCun, Léon Bottou, Genevieve B. Orr, and Klaus-Robert Müller.  _Efficient BackProp_ , pp. 9–48.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2012.  URL https://doi.org/10.1007/978-3-642-35289-8_3.
  * Lee et al. (2018) Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S. Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein.  Deep neural networks as Gaussian processes.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=B1EA-M-0Z.
  * Lee et al. (2019) Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington.  Wide neural networks of any depth evolve as linear models under gradient descent.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/0d1a9651497a38d8b1c3871c84528bd4-Paper.pdf.
  * Lee et al. (2020) Jaehoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein.  Finite versus infinite neural networks: an empirical study.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 15156–15172. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/ad086f59924fffe0773f8d0ca22ea712-Paper.pdf.
  * Li et al. (2022) Li, Andreeto, Ranzato, and Perona.  Caltech 101, Apr 2022.
  * Li et al. (2020) Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak.  Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks.  In _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , volume 108 of _Proceedings of Machine Learning Research_ , pp. 4313–4324. PMLR, 2020.  URL https://proceedings.mlr.press/v108/li20j.html.
  * Louart et al. (2018) Cosme Louart, Zhenyu Liao, and Romain Couillet.  A random matrix approach to neural networks.  _The Annals of Applied Probability_ , 28(2):1190–1248, 2018.  URL https://www.jstor.org/stable/26542333.
  * Mishkin & Matas (2016) Dmytro Mishkin and Jiri Matas.  All you need is a good init.  In Yoshua Bengio and Yann LeCun (eds.), _4th International Conference on Learning Representations, Conference Track Proceedings_ , 2016.  URL http://arxiv.org/abs/1511.06422.
  * Murray et al. (2022) M. Murray, V. Abrol, and J. Tanner.  Activation function design for deep networks: linearity and effective initialisation.  _Applied and Computational Harmonic Analysis_ , 59:117–154, 2022.  URL https://www.sciencedirect.com/science/article/pii/S1063520321001111.  Special Issue on Harmonic Analysis and Machine Learning.
  * Neal (1996) Radford M. Neal.  _Bayesian Learning for Neural Networks_.  Springer-Verlag, Berlin, Heidelberg, 1996.
  * Nguyen (2021) Quynh Nguyen.  On the proof of global convergence of gradient descent for deep relu networks with linear widths.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 8056–8062. PMLR, 2021.  URL https://proceedings.mlr.press/v139/nguyen21a.html.
  * Nguyen & Mondelli (2020) Quynh Nguyen and Marco Mondelli.  Global convergence of deep networks with one wide layer followed by pyramidal topology.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 11961–11972. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/8abfe8ac9ec214d68541fcb888c0b4c3-Paper.pdf.
  * Nguyen et al. (2021) Quynh Nguyen, Marco Mondelli, and Guido Montúfar.  Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep ReLU networks.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 8119–8129. PMLR, 2021.  URL https://proceedings.mlr.press/v139/nguyen21g.html.
  * Novak et al. (2019) Roman Novak, Lechao Xiao, Yasaman Bahri, Jaehoon Lee, Greg Yang, Jiri Hron, Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein.  Bayesian deep convolutional networks with many channels are Gaussian processes.  In _7th International Conference on Learning Representations_. OpenReview.net, 2019.  URL https://openreview.net/forum?id=B1g30j0qF7.
  * Novak et al. (2022) Roman Novak, Jascha Sohl-Dickstein, and Samuel Stern Schoenholz.  Fast finite width neural tangent kernel, 2022.  URL https://openreview.net/forum?id=zLb9oSWy933.
  * O’Donnell (2014) Ryan O’Donnell.  _Analysis of Boolean functions_.  Cambridge University Press, 2014.
  * Oymak & Soltanolkotabi (2020) Samet Oymak and Mahdi Soltanolkotabi.  Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks.  _IEEE Journal on Selected Areas in Information Theory_ , 1(1), 2020.  URL https://par.nsf.gov/biblio/10200049.
  * Oymak et al. (2019) Samet Oymak, Zalan Fabian, Mingchen Li, and Mahdi Soltanolkotabi.  Generalization guarantees for neural networks via harnessing the low-rank structure of the Jacobian.  _CoRR_ , abs/1906.05392, 2019.  URL http://arxiv.org/abs/1906.05392.
  * Panigrahi et al. (2020) Abhishek Panigrahi, Abhishek Shetty, and Navin Goyal.  Effect of activation functions on the training of overparametrized neural nets.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=rkgfdeBYvH.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems 32_ , pp. 8024–8035. Curran Associates, Inc., 2019.  URL http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf.
  * Pennington & Worah (2017) Jeffrey Pennington and Pratik Worah.  Nonlinear random matrix theory for deep learning.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper/2017/file/0f3d014eead934bbdbacb62a01dc4831-Paper.pdf.
  * Pennington & Worah (2018) Jeffrey Pennington and Pratik Worah.  The spectrum of the Fisher information matrix of a single-hidden-layer neural network.  In _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper/2018/file/18bb68e2b38e4a8ce7cf4f6b2625768c-Paper.pdf.
  * Poole et al. (2016a) Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli.  Exponential expressivity in deep neural networks through transient chaos.  In _Advances in Neural Information Processing Systems_ , volume 29. Curran Associates, Inc., 2016a.  URL https://proceedings.neurips.cc/paper/2016/file/148510031349642de5ca0c544f31b2ef-Paper.pdf.
  * Poole et al. (2016b) Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli.  Exponential expressivity in deep neural networks through transient chaos.  In _Advances in Neural Information Processing Systems_ , volume 29. Curran Associates, Inc., 2016b.  URL https://proceedings.neurips.cc/paper/2016/file/148510031349642de5ca0c544f31b2ef-Paper.pdf.
  * Schoenholz et al. (2017) Samuel S. Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein.  Deep information propagation.  In _International Conference on Learning Representations (ICLR)_ , 2017.  URL https://openreview.net/pdf?id=H1W1UN9gg.
  * Schur (1911) J. Schur.  Bemerkungen zur Theorie der beschränkten Bilinearformen mit unendlich vielen Veränderlichen.  _Journal für die reine und angewandte Mathematik_ , 140:1–28, 1911.  URL http://eudml.org/doc/149352.
  * Simon et al. (2022) James Benjamin Simon, Sajant Anand, and Mike Deweese.  Reverse engineering the neural tangent kernel.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 20215–20231. PMLR, 17–23 Jul 2022.  URL https://proceedings.mlr.press/v162/simon22a.html.
  * Sontag & Sussmann (1989) Eduardo D. Sontag and Héctor J. Sussmann.  Backpropagation can give rise to spurious local minima even for networks without hidden layers.  _Complex Systems_ , 3:91–106, 1989.
  * Velikanov & Yarotsky (2021) Maksim Velikanov and Dmitry Yarotsky.  Explicit loss asymptotics in the gradient descent training of neural networks.  In _Advances in Neural Information Processing Systems_ , volume 34, pp. 2570–2582. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper/2021/file/14faf969228fc18fcd4fcf59437b0c97-Paper.pdf.
  * Vershynin (2012) Roman Vershynin.  _Introduction to the non-asymptotic analysis of random matrices_ , pp. 210–268.  Cambridge University Press, 2012.
  * Weyl (1912) Hermann Weyl.  Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung).  _Mathematische Annalen_ , 71(4):441–479, 1912\.  URL https://doi.org/10.1007/BF01456804.
  * Woodworth et al. (2020) Blake Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro.  Kernel and rich regimes in overparametrized models.  In _Proceedings of Thirty Third Conference on Learning Theory_ , volume 125 of _Proceedings of Machine Learning Research_ , pp. 3635–3673. PMLR, 2020.  URL https://proceedings.mlr.press/v125/woodworth20a.html.
  * Xie et al. (2017) Bo Xie, Yingyu Liang, and Le Song.  Diverse Neural Network Learns True Target Functions.  In _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , volume 54 of _Proceedings of Machine Learning Research_ , pp. 1216–1224. PMLR, 2017.  URL https://proceedings.mlr.press/v54/xie17a.html.
  * Yang & Salman (2019) Greg Yang and Hadi Salman.  A fine-grained spectral perspective on neural networks, 2019.  URL https://arxiv.org/abs/1907.10599.
  * Zou & Gu (2019) Difan Zou and Quanquan Gu.  An improved analysis of training over-parameterized deep neural networks.  In _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/6a61d423d02a1c56250dc23ae7ff12f3-Paper.pdf.
  * Zou et al. (2020) Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu.  Gradient descent optimizes over-parameterized deep ReLU networks.  _Machine learning_ , 109:467–492, 2020.

## Appendix

The appendix is organized as follows.

  * •

Appendix A gives background material on Gaussan kernels, NTK, unit variance
intitialization, and Hermite polynomial expansions.

  * •

Appendix B provides details for Section 3.

  * •

Appendix C provides details for Section 4.

##  Appendix A Background material

###  A.1 Gaussian kernel

Observe by construction that the flattened collection of preactivations at the
first layer $(g^{(1)}(\mathbf{x}_{i}))_{i=1}^{n}$ form a centered Gaussian
process, with the covariance between the $\alpha$th and $\beta$th neuron being
described by

$\Sigma_{\alpha_{\beta}}^{(1)}(\mathbf{x}_{i},\mathbf{x}_{j})\vcentcolon=\mathbb{E}[g^{(1)}_{\alpha}(\mathbf{x}_{i})g^{(1)}_{\beta}(\mathbf{x}_{j})]=\delta_{\alpha=\beta}\left(\gamma_{w}^{2}\mathbf{x}_{i}^{T}\mathbf{x}_{j}+\gamma_{b}^{2}\right).$

Under the Assumption 1, the preactivations at each layer $l\in[L+1]$ converge
also in distribution to centered Gaussian processes (Neal, 1996; Lee et al.,
2018). We remark that the sequential width limit condition of Assumption 1 is
not necessary for this behavior, for example the same result can be derived in
the setting where the widths of the network are sent to infinity
simultaneously under certain conditions on the activation function (de G.
Matthews et al., 2018). However, as our interests lie in analyzing the limit
rather than the conditions for convergence to said limit, for simplicity we
consider only the sequential width limit. As per Lee et al. (2018, Eq. 4), the
covariance between the preactivations of the $\alpha$th and $\beta$th neurons
at layer $l\geq 2$ for any input pair $\mathbf{x},\mathbf{y}\in\mathbb{R}$ are
described by the following kernel,

$\displaystyle\Sigma_{\alpha_{\beta}}^{(l)}(\mathbf{x},\mathbf{y})$
$\displaystyle\vcentcolon=\mathbb{E}[g^{(l)}_{\alpha}(\mathbf{x})g^{(l)}_{\beta}(\mathbf{y})]$
$\displaystyle=\delta_{\alpha=\beta}\left(\sigma_{w}^{2}\mathbb{E}_{g^{(l-1)}\sim\mathcal{G}\mathcal{P}(0,\Sigma^{l-1})}[\phi(g^{(l-1)}_{\alpha}(\mathbf{x}))\phi(g^{(l-1)}_{\beta}(\mathbf{y}))]+\sigma_{b}^{2}\right).$

We refer to this kernel as the Gaussian kernel. As each neuron is identically
distributed and the covariance between pairs of neurons is 0 unless
$\alpha=\beta$, moving forward we drop the subscript and discuss only the
covariance between the preactivations of an arbitrary neuron given two inputs.
As per the discussion by Lee et al. (2018, Section 2.3), the expectations
involved in the computation of these Gaussian kernels can be computed with
respect to a bivariate Gaussian distribution, whose covariance matrix has
three distinct entries: the variance of a preactivation of $\mathbf{x}$ at the
previous layer, $\Sigma^{(l-1)}(\mathbf{x},\mathbf{x})$, the variance of a
preactivation of $\mathbf{y}$ at the previous layer,
$\Sigma^{(l)}(\mathbf{y},\mathbf{y})$, and the covariance between
preactivations of $\mathbf{x}$ and $\mathbf{y}$,
$\Sigma^{(l-1)}(\mathbf{x},\mathbf{y})$. Therefore the Gaussian kernel, or
covariance function, and its derivative, which we will require later for our
analysis of the NTK, can be computed via the the following recurrence
relations, see for instance (Lee et al., 2018; Jacot et al., 2018; Arora et
al., 2019b; Nguyen et al., 2021),

$\displaystyle\Sigma^{(1)}(\mathbf{x},\mathbf{y})=\gamma_{w}^{2}\mathbf{x}^{T}\mathbf{x}+\gamma_{b}^{2},$
(11)
$\displaystyle\mathbf{A}^{(l)}(\mathbf{x},\mathbf{y})=\begin{bmatrix}\Sigma^{(l-1)}(\mathbf{x},\mathbf{x})&\Sigma^{(l-1)}(\mathbf{x},\mathbf{y})\\\
\Sigma^{(l-1)}(\mathbf{y},\mathbf{x})&\Sigma^{(l-1)}(\mathbf{x},\mathbf{x})\end{bmatrix}$
$\displaystyle\Sigma^{(l)}(\mathbf{x},\mathbf{y})=\sigma_{w}^{2}\mathbb{E}_{(B_{1},B_{2})\sim\mathcal{N}(0,\mathbf{A}^{(l)}(\mathbf{x},\mathbf{y}))}[\phi(B_{1})\phi(B_{2})]+\sigma_{b}^{2},$
$\displaystyle\dot{\Sigma}^{(l)}(\mathbf{x},\mathbf{y})=\sigma_{w}^{2}\mathbb{E}_{(B_{1},B_{2})\sim\mathcal{N}(0,\mathbf{A}^{(l)}(\mathbf{x},\mathbf{y}))}\left[\phi^{\prime}(B_{1})\phi^{\prime}(B_{2})\right].$

###  A.2 Neural Tangent Kernel (NTK)

As discussed in the Section 1, under Assumption 1 $\tilde{\Theta}^{(l)}$
converges in probability to a deterministic limit, which we denote
$\Theta^{(l)}$. This deterministic limit kernel can be expressed in terms of
the Gaussian kernels and their derivatives from Section A.1 via the following
recurrence relationships (Jacot et al., 2018, Theorem 1),

$\displaystyle\Theta^{(1)}(\mathbf{x},\mathbf{y})$
$\displaystyle=\Sigma^{(1)}(\mathbf{x},\mathbf{y}),$ (12)
$\displaystyle\Theta^{(l)}(\mathbf{x},\mathbf{y})$
$\displaystyle=\Theta^{(l-1)}(\mathbf{x},\mathbf{y})\dot{\Sigma}^{(l)}(\mathbf{x},\mathbf{y})+\Sigma^{(l)}(\mathbf{x},\mathbf{y})$
$\displaystyle=\Sigma^{(l)}(\mathbf{x},\mathbf{y})+\sum_{h=1}^{l-1}\Sigma^{(h)}(\mathbf{x},\mathbf{y})\left(\prod_{h^{\prime}=h+1}^{l}\dot{\Sigma}^{(h^{\prime})}(\mathbf{x},\mathbf{y})\right)\;\forall
l\in[2,L+1].$

A useful expression for the NTK matrix, which is a straightforward extension
and generalization of Nguyen et al. (2021, Lemma 3.1), is provided in Lemma
A.1 below.

######  Lemma A.1.

(Based on Nguyen et al. 2021, Lemma 3.1) Under Assumption 1, a sequence of
positive semidefinite matrices $(\mathbf{G}_{l})_{l=1}^{L+1}$ in
$\mathbb{R}^{n\times n}$, and the related sequence
$(\dot{\mathbf{G}}_{l})_{l=2}^{L+1}$ also in $\mathbb{R}^{n\times n}$, can be
constructed via the following recurrence relationships,

$\displaystyle\mathbf{G}_{1}$
$\displaystyle=\gamma_{w}^{2}\mathbf{X}\mathbf{X}^{T}+\gamma_{b}^{2}\textbf{1}_{n\times
n},$ (13) $\displaystyle\mathbf{G}_{2}$
$\displaystyle=\sigma_{w}^{2}\mathbb{E}_{\mathbf{w}\sim\mathcal{N}(\textbf{0},\textbf{I}_{d})}[\phi(\mathbf{X}\mathbf{w})\phi(\mathbf{X}\mathbf{w})^{T}]+\sigma_{b}^{2}\textbf{1}_{n\times
n},$ $\displaystyle\dot{\mathbf{G}}_{2}$
$\displaystyle=\sigma_{w}^{2}\mathbb{E}_{\mathbf{w}\sim\mathcal{N}(\textbf{0},\textbf{I}_{n})}[\phi^{\prime}(\mathbf{X}\mathbf{w})\phi^{\prime}(\mathbf{X}\mathbf{w})^{T}],$
$\displaystyle\mathbf{G}_{l}$
$\displaystyle=\sigma_{w}^{2}\mathbb{E}_{\mathbf{w}\sim\mathcal{N}(\textbf{0},\textbf{I}_{n})}[\phi(\sqrt{\mathbf{G}_{l-1}}\mathbf{w})\phi(\sqrt{\mathbf{G}_{l-1}}\mathbf{w})^{T}]+\sigma_{b}^{2}\textbf{1}_{n\times
n},\;l\in[3,L+1],$ $\displaystyle\dot{\mathbf{G}}_{l}$
$\displaystyle=\sigma_{w}^{2}\mathbb{E}_{\mathbf{w}\sim\mathcal{N}(\textbf{0},\textbf{I}_{n})}[\phi^{\prime}(\sqrt{\mathbf{G}_{l-1}}\mathbf{w})\phi^{\prime}(\sqrt{\mathbf{G}_{l-1}}\mathbf{w})^{T}],\;l\in[3,L+1].$

The sequence of NTK matrices $(\mathbf{K}_{l})_{l=1}^{L+1}$ can in turn be
written using the following recurrence relationship,

$\displaystyle n\mathbf{K}_{1}$ $\displaystyle=\mathbf{G}_{1},$ (14)
$\displaystyle n\mathbf{K}_{l}$
$\displaystyle=\mathbf{G}_{l}+n\mathbf{K}_{l-1}\odot\dot{\mathbf{G}}_{l}$
$\displaystyle=\mathbf{G}_{l}+\sum_{i=1}^{l-1}\left(\mathbf{G}_{i}\odot\left(\odot_{j=i+1}^{l}\dot{\mathbf{G}}_{j}\right)\right).$

###### Proof.

For the sequence $(\mathbf{G}_{l})_{l=1}^{L+1}$ it suffices to prove for any
$i,j\in[n]$ and $l\in[L+1]$ that

$[\mathbf{G}_{l}]_{i,j}=\Sigma^{(l)}(\mathbf{x}_{i},\mathbf{x}_{j})$

and $\mathbf{G}_{l}$ is positive semi-definite. We proceed by induction,
considering the base case $l=1$ and comparing (13) with (11) then it is
evident that

$[\mathbf{G}_{1}]_{i,j}=\Sigma^{(1)}(\mathbf{x}_{i},\mathbf{x}_{j}).$

In addition, $\mathbf{G}_{1}$ is also clearly positive semi-definite as for
any $\mathbf{u}\in\mathbb{R}^{n}$

$\mathbf{u}^{T}\mathbf{G}_{1}\mathbf{u}=\gamma_{w}^{2}\left\lVert\mathbf{X}^{T}\mathbf{u}\right\rVert^{2}+\gamma_{b}^{2}\left\lVert\textbf{1}_{n}^{T}\mathbf{u}\right\rVert^{2}\geq
0.$

We now assume the induction hypothesis is true for $\mathbf{G}_{l-1}$. We will
need to distinguish slightly between two cases, $l=2$ and $l\in[3,L+1]$. The
proof of the induction step in either case is identical. To this end, and for
notational ease, let $\mathbf{V}=\mathbf{X}$,
$\mathbf{w}\sim\mathcal{N}(0,\textbf{I}_{d})$ when $l=2$, and
$\mathbf{V}=\sqrt{\mathbf{G}_{l-1}}$,
$\mathbf{w}\sim\mathcal{N}(0,\textbf{I}_{n})$ for $l\in[3,L+1]$. In either
case we let $\mathbf{v}_{i}$ denote the $i$th row of $\mathbf{V}$. For any
$i,j\in[n]$

$[\mathbf{G}_{l}]_{ij}=\sigma_{w}^{2}\mathbb{E}_{\mathbf{w}}[\phi(\mathbf{v}_{i}^{T}\mathbf{w})\phi(\mathbf{v}_{j}^{T}\mathbf{w})]+\sigma_{b}^{2}.$

Now let $B_{1}=\mathbf{v}_{i}^{T}\mathbf{w}$,
$B_{2}=\mathbf{v}_{j}^{T}\mathbf{w}$ and observe for any
$\alpha_{1},\alpha_{2}\in\mathbb{R}$ that
$\alpha_{1}B_{1}+\alpha_{2}B_{2}=\sum_{k}^{n}(\alpha_{1}v_{ik}+\alpha_{2}v_{jk})w_{k}\sim\mathcal{N}(0,\left\lVert\alpha_{1}\mathbf{v}_{i}+\alpha_{2}\mathbf{v}_{j}\right\rVert^{2})$.
Therefore the joint distribution of $(B_{1},B_{2})$ is a mean 0 bivariate
normal distribution. Denoting the covariance matrix of this distribution as
$\tilde{\mathbf{A}}\in\mathbb{R}^{2\times 2}$, then $[\mathbf{G}_{l}]_{ij}$
can be expressed as

$[\mathbf{G}_{l}]_{ij}=\sigma_{w}^{2}\mathbb{E}_{(B_{1},B_{2})\sim\tilde{\mathbf{A}}}[\phi(B_{1})\phi(B_{2})]+\sigma_{b}^{2}.$

To prove $[\mathbf{G}_{l}]_{i,j}=\Sigma^{(l)}$ it therefore suffices to show
that $\tilde{\mathbf{A}}=\mathbf{A}^{(l)}$ as per (11). This follows by the
induction hypothesis as

$\displaystyle\mathbb{E}[B_{1}^{2}]$
$\displaystyle=\mathbf{v}_{i}^{T}\mathbf{v}_{i}=[\mathbf{G}_{l-1}]_{ii}=\Sigma^{(l-1)}(\mathbf{x}_{i},\mathbf{x}_{i}),$
$\displaystyle\mathbb{E}[B_{2}^{2}]$
$\displaystyle=\mathbf{v}_{j}^{T}\mathbf{v}_{j}=[\mathbf{G}_{l-1}]_{jj}=\Sigma^{(l-1)}(\mathbf{x}_{j},\mathbf{x}_{j}),$
$\displaystyle\mathbb{E}[B_{1}B_{2}]$
$\displaystyle=\mathbf{v}_{i}^{T}\mathbf{v}_{j}=[\mathbf{G}_{l-1}]_{ij}=\Sigma^{(l-1)}(\mathbf{x}_{i},\mathbf{x}_{j}).$

Finally, $\mathbf{G}_{l}$ is positive semi-definite as long as
$\mathbb{E}_{\mathbf{w}}[\phi(\mathbf{V}\mathbf{w})\phi(\mathbf{V}\mathbf{w})^{T}]$
is positive semi-definite. Let
$M(\mathbf{w})=\phi(\mathbf{V}\mathbf{w})\in\mathbb{R}^{n\times n}$ and
observe for any $\mathbf{w}$ that $M(\mathbf{w})M(\mathbf{w})^{T}$ is positive
semi-definite. Therefore
$\mathbb{E}_{\mathbf{w}}[M(\mathbf{w})M(\mathbf{w})^{T}]$ must also be
positive semi-definite. Thus the inductive step is complete and we may
conclude for $l\in[L+1]$ that

$[\mathbf{G}_{l}]_{i,j}=\Sigma^{(l)}(\mathbf{x}_{i},\mathbf{x}_{j}).$ (15)

For the proof of the expression for the sequence
$(\dot{\mathbf{G}}_{l})_{l=2}^{L+1}$ it suffices to prove for any $i,j\in[n]$
and $l\in[L+1]$ that

$[\dot{\mathbf{G}}_{l}]_{i,j}=\dot{\Sigma}^{(l)}(\mathbf{x}_{i},\mathbf{x}_{j}).$

By comparing (13) with (11) this follows immediately from (15). Therefore with
(13) proven (14) follows from (12). ∎

###  A.3 Unit variance initialization

The initialization scheme for a neural network, particularly a deep neural
network, needs to be designed with some care in order to avoid either
vanishing or exploding gradients during training Glorot & Bengio (2010); He et
al. (2015); Mishkin & Matas (2016); LeCun et al. (2012). Some of the most
popular initialization strategies used in practice today, in particular LeCun
et al. (2012) and Glorot & Bengio (2010) initialization, first model the
preactivations of the network as Gaussian random variables and then select the
network hyperparameters in order that the variance of these idealized
preactivations is fixed at one. Under Assumption 1 this idealized model on the
preactivations is actually realized and if we additionally assume the
conditions of Assumption 2 hold then likewise the variance of the
preactivations at every layer will be fixed at one. To this end, and as in
Poole et al. (2016b); Murray et al. (2022), consider the function
$V\colon\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$ defined as

$V(q)=\sigma_{w}^{2}\mathbb{E}_{Z\sim\mathcal{N}(0,1)}\left[\phi\left(\sqrt{q}Z\right)^{2}\right]+\sigma_{b}^{2}.$
(16)

Noting that $V$ is another expression for
$\Sigma^{(l)}(\mathbf{x},\mathbf{x})$, derived via a change of variables as
per Poole et al. (2016b), the sequence of variances
$(\Sigma^{(l)}(\mathbf{x},\mathbf{x}))_{l=2}^{L}$ can therefore be generated
as follows,

$\Sigma^{(l)}(\mathbf{x},\mathbf{x})=V(\Sigma^{(l-1)}(\mathbf{x},\mathbf{x})).$
(17)

The linear correlation
$\rho^{(l)}:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow[-1,1]$ between the
preactivations of two inputs $\mathbf{x},\mathbf{y}\in\mathbb{R}^{d}$ we
define as

$\displaystyle\rho^{(l)}(\mathbf{x},\mathbf{y})=\frac{\Sigma^{(l)}(\mathbf{x},\mathbf{y})}{\sqrt{\Sigma^{(l)}(\mathbf{x},\mathbf{x})\Sigma^{(l)}(\mathbf{y},\mathbf{y})}}.$
(18)

Assuming
$\Sigma^{(l)}(\mathbf{x},\mathbf{x})=\Sigma^{(l)}(\mathbf{y},\mathbf{y})=1$
for all $l\in[L+1]$, then
$\rho^{(l)}(\mathbf{x},\mathbf{y})=\Sigma^{(l)}(\mathbf{x},\mathbf{y})$. Again
as in Murray et al. (2022) and analogous to (16), with
$Z_{1},Z_{2}\sim\mathcal{N}(0,1)$ independent, $U_{1}\vcentcolon=Z_{1}$,
$U_{2}(\rho)\vcentcolon=(\rho Z_{1}+\sqrt{1-\rho^{2}}Z_{2})$ 333We remark that
$U_{1},U_{2}$ are dependent and identically distributed as
$U_{1},U_{2}\sim\mathcal{N}(0,1)$. we define the correlation function
$R:[-1,1]\rightarrow[-1,1]$ as

$\displaystyle
R(\rho)=\sigma_{w}^{2}\mathbb{E}[\phi(U_{1})\phi(U_{2}(\rho))]+\sigma_{b}^{2}.$
(19)

Noting under these assumptions that $R$ is equivalent to
$\Sigma^{(l)}(\mathbf{x},\mathbf{y})$, the sequence of correlations
$(\rho^{(l)}(\mathbf{x},\mathbf{y}))_{l=2}^{L}$ can thus be generated as

$\rho^{(l)}(\mathbf{x},\mathbf{y})=R(\rho^{(l-1)}(\mathbf{x},\mathbf{y})).$

As observed in Poole et al. (2016b); Schoenholz et al. (2017), $R(1)=V(1)=1$,
hence $\rho=1$ is a fixed point of $R$. We remark that as all preactivations
are distributed as $\mathcal{N}(0,1)$, then a correlation of one between
preactivations implies they are equal. The stability of the fixed point
$\rho=1$ is of particular significance in the context of initializing deep
neural networks successfully. Under mild conditions on the activation function
one can compute the derivative of $R$, see e.g., Poole et al. (2016b);
Schoenholz et al. (2017); Murray et al. (2022), as follows,

$\displaystyle
R^{\prime}(\rho)=\sigma_{w}^{2}\mathbb{E}[\phi^{\prime}(U_{1})\phi^{\prime}(U_{2}(\rho))].$
(20)

Observe that the expression for $\dot{\Sigma}^{(l)}$ and $R^{\prime}$ are
equivalent via a change of variables (Poole et al., 2016b), and therefore the
sequence of correlation derivatives may be computed as

$\dot{\Sigma}^{(l)}(\mathbf{x},\mathbf{y})=R^{\prime}(\rho^{(l)}(\mathbf{x},\mathbf{y})).$

With the relevant background material now in place we are in a position to
prove Lemma A.2.

######  Lemma A.2.

Under Assumptions 1 and 2 and defining
$\chi=\sigma_{w}^{2}\mathbb{E}_{Z\sim\mathcal{N}(0,1)}[\phi^{\prime}(Z)^{2}]\in\mathbb{R}_{>0}$,
then for all $i,j\in[n]$, $l\in[L+1]$

  * •

$[\mathbf{G}_{n,l}]_{ij}\in[-1,1]$ and $[\mathbf{G}_{n,l}]_{ii}=1$,

  * •

$[\dot{\mathbf{G}}_{n,l}]_{ij}\in[-\chi,\chi]$ and
$[\dot{\mathbf{G}}_{n,l}]_{ii}=\chi$.

Furthermore, the NTK is a dot product kernel, meaning
$\Theta(\mathbf{x}_{i},\mathbf{x}_{j})$ can be written as a function of the
inner product between the two inputs,
$\Theta(\mathbf{x}_{i}^{T}\mathbf{x}_{j})$.

###### Proof.

Recall from Lemma A.1 and its proof that for any $l\in[L+1]$, $i,j\in[n]$
$[\mathbf{G}_{n,l}]_{ij}=\Sigma^{(l)}(\mathbf{x}_{i},\mathbf{x}_{j})$ and
$[\dot{\mathbf{G}}_{n,l}]_{ij}=\dot{\Sigma}^{(l)}(\mathbf{x}_{i},\mathbf{x}_{j})$.
We first prove by induction $\Sigma^{(l)}(\mathbf{x}_{i},\mathbf{x}_{i})=1$
for all $l\in[L+1]$. The base case $l=1$ follows as

$\Sigma^{(1)}(\mathbf{x},\mathbf{x})=\gamma_{w}^{2}\mathbf{x}^{T}\mathbf{x}+\gamma_{b}^{2}=\gamma_{w}^{2}+\gamma_{b}^{2}=1.$

Assume the induction hypothesis is true for layer $l-1$. With
$Z\sim\mathcal{N}(0,1)$, then from (16) and (17)

$\displaystyle\Sigma^{(l)}(\mathbf{x},\mathbf{x})$
$\displaystyle=V(\Sigma^{(l-1)}(\mathbf{x},\mathbf{x}))$
$\displaystyle=\sigma_{w}^{2}\mathbb{E}\left[\phi^{2}\left(\sqrt{\Sigma^{(l-1)}(\mathbf{x},\mathbf{x})}Z\right)\right]+\sigma_{b}^{2}$
$\displaystyle=\sigma_{w}^{2}\mathbb{E}\left[\phi^{2}\left(Z\right)\right]+\sigma_{b}^{2}$
$\displaystyle=1,$

thus the inductive step is complete. As an immediate consequence it follows
that $[\mathbf{G}_{l}]_{ii}=1$. Also, for any $i,j\in[n]$ and $l\in[L+1]$,

$\displaystyle\Sigma^{(l)}(\mathbf{x}_{i},\mathbf{x}_{j})$
$\displaystyle=\rho^{(l)}(\mathbf{x}_{i},\mathbf{x}_{j})=R(\rho^{(l-1)}(\mathbf{x}_{i},\mathbf{x}_{j}))=R(...R(R(\mathbf{x}_{i}^{T}\mathbf{x}_{j}))).$

Thus we can consider $\Sigma^{(l)}$ as a univariate function of the input
correlation $\Sigma:[-1,1]\rightarrow[-1,1]$ and also conclude that
$[\mathbf{G}_{l}]_{ij}\in[-1,1]$. Furthermore,

$\displaystyle\dot{\Sigma}^{(l)}(\mathbf{x}_{i},\mathbf{x}_{j})=R^{\prime}(\rho^{(l)}(\mathbf{x}_{i},\mathbf{x}_{j}))=R^{\prime}(R(...R(R(\mathbf{x}_{i}^{T}\mathbf{x}_{j})))),$

which likewise implies $\dot{\Sigma}$ is a dot product kernel. Recall now the
random variables introduced to define $R$: $Z_{1},Z_{2}\sim\mathcal{N}(0,1)$
are independent and $U_{1}=Z_{1}$, $U_{2}=(\rho
Z_{1}+\sqrt{1-\rho^{2}}Z_{2})$. Observe $U_{1},U_{2}$ are dependent but
identically distributed as $U_{1},U_{2}\sim\mathcal{N}(0,1)$. For any
$\rho\in[-1,1]$ then applying the Cauchy-Schwarz inequality gives

$\displaystyle|R^{\prime}(\rho)|^{2}=\sigma_{w}^{4}\left|\mathbb{E}[\phi^{\prime}(U_{1})\phi^{\prime}(U_{2})]\right|^{2}\leq\sigma_{w}^{4}\mathbb{E}[\phi^{\prime}(U_{1})^{2}]\mathbb{E}[\phi^{\prime}(U_{2})^{2}]=\sigma_{w}^{4}\mathbb{E}[\phi^{\prime}(U_{1})^{2}]^{2}=|R^{\prime}(1)|^{2}.$

As a result, under the assumptions of the lemma
$\dot{\Sigma}^{(l)}:[-1,1]\rightarrow[-\chi,\chi]$ and
$\dot{\Sigma}^{(l)}(\mathbf{x}_{i},\mathbf{x}_{i})=\chi$. From this it
immediately follows that $[\dot{\mathbf{G}}_{l}]_{ij}\in[-\chi,\chi]$ and
$[\dot{\mathbf{G}}_{l}]_{ii}=\chi$ as claimed. Finally, as
$\Sigma:[-1,1]\rightarrow[-1,1]$ and
$\dot{\Sigma}:[-1,1]\rightarrow[-\chi,\chi]$ are dot product kernels, then
from (12) the NTK must also be a dot product kernel and furthermore a
univariate function of the pairwise correlation of its input arguments. ∎

The following corollary, which follows immediately from Lemma A.2 and (14),
characterizes the trace of the NTK matrix in terms of the trace of the input
gram.

######  Corollary A.3.

Under the same conditions as Lemma A.2, suppose $\phi$ and $\sigma_{w}^{2}$
are chosen such that $\chi=1$. Then

$Tr(\mathbf{K}_{n,l})=l.$ (21)

###  A.4 Hermite Expansions

We say that a function $f:\mathbb{R}\rightarrow\mathbb{R}$ is square
integrable w.r.t. the standard Gaussian measure
$\gamma=e^{-x^{2}/2}/\sqrt{2\pi}$ if
$\mathbb{E}_{x\sim\mathcal{N}(0,1)}[f(x)^{2}]<\infty$. We denote by
$L^{2}(\mathbb{R},\gamma)$ the space of all such functions. The probabilist’s
Hermite polynomials are given by

$\displaystyle
H_{k}(x)={(-1)}^{k}e^{x^{2}/2}\frac{d^{k}}{dx^{k}}e^{-x^{2}/2},\quad
k=0,1,\ldots.$

The first three Hermite polynomials are $H_{0}(x)=1$, $H_{1}(x)=x$,
$H_{2}(x)=(x^{2}-1)$. Let $h_{k}(x)=\tfrac{H_{k}(x)}{\sqrt{k!}}$ denote the
normalized probabilist’s Hermite polynomials. The normalized Hermite
polynomials form a complete orthonormal basis in $L^{2}(\mathbb{R},\gamma)$
(O’Donnell, 2014, §11): in all that follows, whenever we reference the Hermite
polynomials, we will be referring to the normalized Hermite polynomials. The
Hermite expansion of a function $\phi\in L^{2}(\mathbb{R},\gamma)$ is given by

$\displaystyle\phi(x)=\sum_{k=0}^{\infty}\mu_{k}(\phi)h_{k}(x),$ (22)

where

$\mu_{k}(\phi)=\mathbb{E}_{X\sim\mathcal{N}(0,1)}[\phi(X)h_{k}(X)]$ (23)

is the $k$th normalized probabilist’s Hermite coefficient of $\phi$. In what
follows we shall make use of the following identities.

$\displaystyle\forall k\geq 1,\,h_{k}^{\prime}(x)$
$\displaystyle=\sqrt{k}h_{k-1}(x),$ (24) $\displaystyle\forall k\geq
1,\,xh_{k}(x)$ $\displaystyle=\sqrt{k+1}h_{k+1}(x)+\sqrt{k}h_{k-1}(x).$ (25)
$\displaystyle\begin{array}[]{c}h_{k}(0)=\left\\{\begin{array}[]{ll}0,&\text{
if }k\text{ is odd }\\\ \frac{1}{\sqrt{k!}}(-1)^{\frac{k}{2}}(k-1)!!&\text{ if
}k\text{ is even }\end{array}\right.,\\\ \text{ where
}k!!=\left\\{\begin{array}[]{ll}1,&k\leq 0\\\ k\cdot(k-2)\cdots 5\cdot 3\cdot
1,&k>0\text{ odd }\\\ k\cdot(k-2)\cdots 6\cdot 4\cdot 2,&k>0\text{ even
}.\end{array}\right.\end{array}$ (33)

We also remark that the more commonly encountered physicist’s Hermite
polynomials, which we denote $\tilde{H}_{k}$, are related to the normalized
probablist’s polynomials as follows,

$h_{k}(z)=\frac{2^{-k/2}\tilde{H}_{k}(z/\sqrt{2})}{\sqrt{k!}}.$

The Hermite expansion of the activation function deployed will play a key role
in determining the coefficients of the NTK power series. In particular, the
Hermite coefficients of ReLU are as follows.

######  Lemma A.4.

Daniely et al. (2016) For $\phi(z)=\max\\{0,z\\}$ the Hermite coefficients are
given by

$\mu_{k}(\phi)=\begin{cases}1/\sqrt{2\pi},&\text{$k=0$},\\\
1/2,&\text{$k=1$},\\\ (k-3)!!/\sqrt{2\pi k!},&\text{$k$ even and $k\geq
2$},\\\ 0,&\text{$k$ odd and $k>3$}.\end{cases}$ (34)

##  Appendix B Expressing the NTK as a power series

###  B.1 Deriving a power series for the NTK

We will require the following minor adaptation of Nguyen & Mondelli (2020,
Lemma D.2). We remark this result was first stated for ReLU and Softplus
activations in the work of Oymak & Soltanolkotabi (2020, Lemma H.2).

######  Lemma B.1.

For arbitrary $n,d\in\mathbb{N}$, let $\mathbf{A}\in\mathbb{R}^{n\times d}$.
For $i\in[n]$, we denote the $i$th row of $\mathbf{A}$ as $\mathbf{a}_{i}$,
and further assume that $\left\lVert\mathbf{a}_{i}\right\rVert=1$. Let
$\phi:\mathbb{R}\rightarrow\mathbb{R}$ satisfy $\phi\in
L^{2}(\mathbb{R},\gamma)$ and define

$\mathbf{M}=\mathbb{E}_{\mathbf{w}\sim\mathcal{N}(0,\textbf{I}_{n})}[\phi(\mathbf{A}\mathbf{w})\phi(\mathbf{A}\mathbf{w})^{T}]\in\mathbb{R}^{n\times
n}.$

Then the matrix series

$\mathbf{S}_{K}=\sum_{k=0}^{K}\mu_{k}^{2}(\phi)\left(\mathbf{A}\mathbf{A}^{T}\right)^{\odot
k}$

converges uniformly to $\mathbf{M}$ as $K\rightarrow\infty$.

The proof of Lemma B.1 follows exactly as in (Nguyen & Mondelli, 2020, Lemma
D.2), and is in fact slightly simpler due to the fact we assume the rows of
$\mathbf{A}$ are unit length and $\mathbf{w}\sim\mathcal{N}(0,\textbf{I}_{d})$
instead of $\sqrt{d}$ and
$\mathbf{w}\sim\mathcal{N}(0,\frac{1}{d}\textbf{I}_{d})$ respectively. For the
ease of the reader, we now recall the following definitions, which are also
stated in Section 3. Letting
$\bar{\alpha}_{l}\vcentcolon=(\alpha_{p,l})_{p=0}^{\infty}$ denote a sequence
of real coefficients, then

$F(p,k,\bar{\alpha}_{l})\vcentcolon=\begin{cases}1\;&k=0\text{ and }p=0,\\\
0\;&k=0\text{ and }p\geq 1,\\\
\sum_{(j_{i})\in\mathcal{J}(p,k)}\prod_{i=1}^{k}\alpha_{j_{i},l}\;&k\geq
1\text{ and }p\geq 0,\end{cases}$ (35)

where

$\mathcal{J}(p,k)\vcentcolon=\\{(j_{i})_{i\in[k]}\;:\;j_{i}\geq 0\;\forall
i\in[k],\;\sum_{i=1}^{k}j_{i}=p\\}$

for all $p\in\mathbb{Z}_{\geq 0}$, $k\in\mathbb{Z}_{\geq 1}$.

We are now ready to derive power series for elements of
$(\mathbf{G}_{l}))_{l=1}^{L+1}$ and $(\dot{\mathbf{G}}_{l}))_{l=2}^{L+1}$.

######  Lemma B.2.

Under Assumptions 1 and 2, for all $l\in[2,L+1]$

$\displaystyle\mathbf{G}_{l}=\sum_{k=0}^{\infty}\alpha_{k,l}(\mathbf{X}\mathbf{X}^{T})^{\odot
k},$ (36)

where the series for each element $[\mathbf{G}_{l}]_{ij}$ converges absolutely
and the coefficients $\alpha_{p,l}$ are nonnegative. The coefficients of the
series (36) for all $p\in\mathbb{Z}_{\geq 0}$ can be expressed via the
following recurrence relationship,

$\alpha_{p,l}=\begin{cases}\sigma_{w}^{2}\mu_{p}^{2}(\phi)+\delta_{p=0}\sigma_{b}^{2},&l=2,\\\
\sum_{k=0}^{\infty}\alpha_{k,2}F(p,k,\bar{\alpha}_{l-1}),&l\geq 3.\end{cases}$
(37)

Furthermore,

$\displaystyle\dot{\mathbf{G}}_{l}=\sum_{k=0}^{\infty}\upsilon_{k,l}(\mathbf{X}\mathbf{X}^{T})^{\odot
k},$ (38)

where likewise the series for each entry $[\dot{\mathbf{G}}_{l}]_{ij}$
converges absolutely and the coefficients $\upsilon_{p,l}$ for all
$p\in\mathbb{Z}_{\geq 0}$ are nonnegative and can be expressed via the
following recurrence relationship,

$\upsilon_{p,l}=\begin{cases}\sigma_{w}^{2}\mu_{p}^{2}(\phi^{\prime}),&l=2,\\\
\sum_{k=0}^{\infty}\upsilon_{k,2}F(p,k,\bar{\alpha}_{l-1}),&l\geq
3.\end{cases}$ (39)

###### Proof.

We start by proving (36) and (37). Proceeding by induction, consider the base
case $l=2$. From Lemma A.1

$\mathbf{G}_{2}=\sigma_{w}^{2}\mathbb{E}_{\mathbf{w}\sim\mathcal{N}(\textbf{0},\textbf{I}_{d})}[\phi(\mathbf{X}\mathbf{w})\phi(\mathbf{X}\mathbf{w})^{T}]+\sigma_{b}^{2}\textbf{1}_{n\times
n}.$

By the assumptions of the lemma, the conditions of Lemma B.1 are satisfied and
therefore

$\displaystyle\mathbf{G}_{2}$
$\displaystyle=\sigma_{w}^{2}\sum_{k=0}^{\infty}\mu_{k}^{2}(\phi)\left(\mathbf{X}\mathbf{X}^{T}\right)^{\odot
k}+\sigma_{b}^{2}\textbf{1}_{n\times n}$
$\displaystyle=\alpha_{0,2}\textbf{1}_{n\times
n}+\sum_{k=1}^{\infty}\alpha_{k,2}\left(\mathbf{X}\mathbf{X}^{T}\right)^{\odot
k}.$

Observe the coefficients $(\alpha_{k,2})_{k\in\mathbb{Z}_{\geq 0}}$ are
nonnegative. Therefore, for any $i,j\in[n]$ using Lemma A.2 the series for
$[\mathbf{G}_{l}]_{ij}$ satisfies

$\displaystyle\sum_{k=0}^{\infty}\left\lvert\alpha_{k,2}\right\rvert\left\lvert\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{k}\right\rvert$
$\displaystyle\leq\sum_{k=0}^{\infty}\alpha_{k,2}\langle\mathbf{x}_{i},\mathbf{x}_{i}\rangle^{k}$
$\displaystyle=[\mathbf{G}_{l}]_{ii}$ $\displaystyle=1$ (40)

and so must be absolutely convergent. With the base case proved we proceed to
assume the inductive hypothesis holds for arbitrary $\mathbf{G}_{l}$ with
$l\in[2,L]$. Observe

$\displaystyle\mathbf{G}_{l+1}$
$\displaystyle=\sigma_{w}^{2}\mathbb{E}_{\mathbf{w}\sim\mathcal{N}(\textbf{0},\textbf{I}_{n})}[\phi(\mathbf{A}\mathbf{w})\phi(\mathbf{A}\mathbf{w})^{T}]+\sigma_{b}^{2}\textbf{1}_{n\times
n},$

where $\mathbf{A}$ is a matrix square root of $\mathbf{G}_{l}$, meaning
$\mathbf{G}_{l}=\mathbf{A}\mathbf{A}$. Recall from Lemma A.1 that
$\mathbf{G}_{l}$ is also symmetric and positive semi-definite, therefore we
may additionally assume, without loss of generality, that
$\mathbf{A}\in\mathbb{R}^{n\times n}$ is symmetric, which conveniently implies
$\mathbf{G}_{n,l}=\mathbf{A}\mathbf{A}^{T}$. Under the assumptions of the
lemma the conditions for Lemma A.2 are satisfied and as a result
$[\mathbf{G}_{n,l}]_{ii}=\left\lVert\mathbf{a}_{i}\right\rVert=1$ for all
$i\in[n]$, where we recall $\mathbf{a}_{i}$ denotes the $i$th row of
$\mathbf{A}$. Therefore we may again apply Lemma A.1,

$\displaystyle\mathbf{G}_{l+1}$
$\displaystyle=\sigma_{w}^{2}\sum_{k=0}^{\infty}\mu_{k}^{2}(\phi)\left(\mathbf{A}\mathbf{A}^{T}\right)^{\odot
k}+\sigma_{b}^{2}\textbf{1}_{n\times n}$
$\displaystyle=(\sigma_{w}^{2}\mu_{0}^{2}(\phi)+\sigma_{b}^{2})\textbf{1}_{n\times
n}+\sigma_{w}^{2}\sum_{k=1}^{\infty}\mu_{k}^{2}(\phi)\left(\mathbf{G}_{n,l}\right)^{\odot
k}$
$\displaystyle=(\sigma_{w}^{2}\mu_{0}^{2}(\phi)+\sigma_{b}^{2})\textbf{1}_{n\times
n}+\sigma_{w}^{2}\sum_{k=1}^{\infty}\mu_{k}^{2}(\phi)\left(\sum_{m=0}^{\infty}\alpha_{m,l}(\mathbf{X}\mathbf{X}^{T})^{\odot
m}\right)^{\odot k},$

where the final equality follows from the inductive hypothesis. For any pair
of indices $i,j\in[n]$

$[\mathbf{G}_{l+1}]_{ij}=(\sigma_{w}^{2}\mu_{0}^{2}(\phi)+\sigma_{b}^{2})+\sigma_{w}^{2}\sum_{k=1}^{\infty}\mu_{k}^{2}(\phi)\left(\sum_{m=0}^{\infty}\alpha_{m,l}\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{m}\right)^{k}.$

By the induction hypothesis, for any $i,j\in[n]$ the series
$\sum_{m=0}^{\infty}\alpha_{m,l}\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{m}$
is absolutely convergent. Therefore, from the Cauchy product of power series
and for any $k\in\mathbb{Z}_{\geq 0}$ we have

$\left(\sum_{m=0}^{\infty}\alpha_{m,l}\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{m}\right)^{k}=\sum_{p=0}^{\infty}F(p,k,\bar{\alpha}_{l})\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p},$
(41)

where $F(p,k,\bar{\alpha}_{l})$ is defined in (4). By definition,
$F(p,k,\bar{\alpha}_{l})$ is a sum of products of positive coefficients, and
therefore $\left\lvert
F(p,k,\bar{\alpha}_{l})\right\rvert=F(p,k,\bar{\alpha}_{l})$. In addition,
recall again by Assumption 2 and Lemma A.2 that $[\mathbf{G}_{l}]_{ii}=1$. As
a result, for any $k\in\mathbb{Z}_{\geq 0}$, as
$\left\lvert\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle\right\rvert\leq 1$

$\sum_{p=0}^{\infty}\left\lvert
F(p,k,\bar{\alpha}_{l})\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}\right\rvert\leq\left(\sum_{m=0}^{\infty}\alpha_{m,l}\right)^{k}=[\mathbf{G}_{n,l}]_{ii}=1$
(42)

and therefore the series
$\sum_{p=0}^{\infty}F(p,k,\bar{\alpha}_{l})\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}$
converges absolutely. Recalling from the proof of the base case that the
series $\sum_{p=1}^{\infty}\alpha_{p,2}$ is absolutely convergent and has only
nonnegative elements, we may therefore interchange the order of summation in
the following,

ij
$\displaystyle=(\sigma_{w}^{2}\mu_{0}^{2}(\phi)+\sigma_{b}^{2})+\sigma_{w}^{2}\sum_{k=1}^{\infty}\mu_{k}^{2}(\phi)\left(\sum_{p=0}^{\infty}F(p,k,\bar{\alpha}_{l})\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}\right)$
$\displaystyle=\alpha_{0,2}+\sum_{k=1}^{\infty}\alpha_{k,2}\left(\sum_{p=0}^{\infty}F(p,k,\bar{\alpha}_{l})\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}\right)$
$\displaystyle=\alpha_{0,2}+\sum_{p=0}^{\infty}\left(\sum_{k=1}^{\infty}\alpha_{k,2}F(p,k,\bar{\alpha}_{l})\right)\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}.$

Recalling the definition of $F(p,k,l)$ in (4), in particular
$F(0,0,\bar{\alpha}_{l})=1$ and $F(p,0,\bar{\alpha}_{l})=0$ for
$p\in\mathbb{Z}_{\geq 1}$, then

ij
$\displaystyle=\left(\alpha_{0,2}+\sum_{k=1}^{\infty}\alpha_{k,2}F(0,k,\bar{\alpha}_{l})\right)\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{0}+\sum_{p=1}^{\infty}\left(\sum_{k=1}^{\infty}\alpha_{k,2}F(p,k,\bar{\alpha}_{l})\right)\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}$
$\displaystyle=\left(\sum_{k=0}^{\infty}\alpha_{k,2}F(0,k,\bar{\alpha}_{l})\right)\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{0}+\sum_{p=1}^{\infty}\left(\sum_{k=0}^{\infty}\alpha_{k,2}F(p,k,\bar{\alpha}_{l})\right)\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}$
$\displaystyle=\sum_{p=0}^{\infty}\left(\sum_{k=0}^{\infty}\alpha_{k,2}F(p,k,\bar{\alpha}_{l})\right)\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}$
$\displaystyle=\sum_{p=0}^{\infty}\alpha_{p,l+1}\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}.$

As the indices $i,j\in[n]$ were arbitrary we conclude that

$\mathbf{G}_{l+1}=\sum_{p=0}^{\infty}\alpha_{p,l+1}\left(\mathbf{X}\mathbf{X}^{T}\right)^{\odot
p}$

as claimed. In addition, by inspection and using the induction hypothesis it
is clear that the coefficients $(\alpha_{p,l+1})_{p=0}^{\infty}$ are
nonnegative. Therefore, by an argument identical to (40), the series for each
entry of $[\mathbf{G}_{l+1}]_{ij}$ is absolutely convergent. This concludes
the proof of (36) and (37).

We now turn our attention to proving the (38) and (39). Under the assumptions
of the lemma the conditions for Lemmas A.1 and B.1 are satisfied and therefore
for the base case $l=2$

$\displaystyle\dot{\mathbf{G}}_{2}$
$\displaystyle=\sigma_{w}^{2}\mathbb{E}_{\mathbf{w}\sim\mathcal{N}(\textbf{0},\textbf{I}_{n})}[\phi^{\prime}(\mathbf{X}\mathbf{w})\phi^{\prime}(\mathbf{X}\mathbf{w})^{T}]$
$\displaystyle=\sigma_{w}^{2}\sum_{k=0}^{\infty}\mu_{k}^{2}(\phi^{\prime})\left(\mathbf{X}\mathbf{X}^{T}\right)^{\odot
k}$
$\displaystyle=\sum_{k=0}^{\infty}\upsilon_{k,2}\left(\mathbf{X}\mathbf{X}^{T}\right)^{\odot
k}.$

By inspection the coefficients $(\upsilon_{p,2})_{p=0}^{\infty}$ are
nonnegative and as a result by an argument again identical to (40) the series
for each entry of $[\dot{\mathbf{G}}_{2}]_{ij}$ is absolutely convergent. For
$l\in[2,L]$, from (36) and its proof there is a matrix
$\mathbf{A}\in\mathbb{R}^{n\times n}$ such that
$\mathbf{G}_{l}=\mathbf{A}\mathbf{A}^{T}$. Again applying Lemma B.1

$\displaystyle\dot{\mathbf{G}}_{n,l+1}$
$\displaystyle=\sigma_{w}^{2}\mathbb{E}_{\mathbf{w}\sim\mathcal{N}(\textbf{0},\textbf{I}_{n})}[\phi^{\prime}(\mathbf{A}\mathbf{w})\phi^{\prime}(\mathbf{A}\mathbf{w})^{T}]$
$\displaystyle=\sigma_{w}^{2}\sum_{k=0}^{\infty}\mu_{k}^{2}(\phi^{\prime})\left(\mathbf{A}\mathbf{A}^{T}\right)^{\odot
k}$
$\displaystyle=\sum_{k=0}^{\infty}\upsilon_{k,2}\left(\mathbf{G}_{n,l}\right)^{\odot
k}$
$\displaystyle=\sum_{k=0}^{\infty}\upsilon_{k,2}\left(\sum_{p=0}^{\infty}\alpha_{p,l}\left(\mathbf{X}\mathbf{X}^{T}\right)^{\odot
p}\right)^{\odot k}$

Analyzing now an arbitrary entry $[\dot{\mathbf{G}}_{l+1}]_{ij}$, by
substituting in the power series expression for $\mathbf{G}_{l}$ from (36) and
using (41) we have

ij
$\displaystyle=\sum_{k=0}^{\infty}\upsilon_{k,2}\left(\sum_{p=0}^{\infty}\alpha_{p,l}\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}\right)^{k}$
$\displaystyle=\sum_{k=0}^{\infty}\upsilon_{k,2}\left(\sum_{p=0}^{\infty}F(p,k,\bar{\alpha}_{l})\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}\right)$
$\displaystyle=\sum_{p=0}^{\infty}\left(\sum_{k=0}^{\infty}\upsilon_{k,2}F(p,k,\bar{\alpha}_{l})\right)\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}$
$\displaystyle=\sum_{p=0}^{\infty}\upsilon_{p,l+1}\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}.$

Note that exchanging the order of summation in the third equality above is
justified as for any $k\in\mathbb{Z}_{\geq 0}$ by (42) we have
$\sum_{p=0}^{\infty}F(p,k,\bar{\alpha}_{l})|\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle|^{p}\leq
1$ and therefore
$\sum_{k=0}^{\infty}\sum_{p=0}^{\infty}\upsilon_{k,2}F(p,k,\bar{\alpha}_{l})\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}$
converges absolutely. As the indices $i,j\in[n]$ were arbitrary we conclude
that

$\dot{\mathbf{G}}_{l+1}=\sum_{p=0}^{\infty}\upsilon_{p,l+1}\left(\mathbf{X}\mathbf{X}^{T}\right)^{\odot
p}$

as claimed. Finally, by inspection the coefficients
$(\upsilon_{p,l+1})_{p=0}^{\infty}$ are nonnegative, therefore, and again by
an argument identical to (40), the series for each entry of
$[\dot{\mathbf{G}}_{n,l+1}]_{ij}$ is absolutely convergent. This concludes the
proof. ∎

We are now prove the key result of Section 3.

See 3.1

###### Proof.

We proceed by induction. The base case $l=1$ follows trivially from Lemma A.1.
We therefore assume the induction hypothesis holds for an arbitrary
$l-1\in[1,L]$. From (14) and Lemma B.2

$\displaystyle n\mathbf{K}_{l}$
$\displaystyle=\mathbf{G}_{l}+n\mathbf{K}_{l-1}\odot\dot{\mathbf{G}}_{l}$
$\displaystyle=\left(\sum_{p=0}^{\infty}\alpha_{p,l}\left(\mathbf{X}\mathbf{X}^{T}\right)^{\odot
p}\right)+\left(n\sum_{q=0}^{\infty}\kappa_{q,l-1}\left(\mathbf{X}\mathbf{X}^{T}\right)^{\odot
q}\right)\odot\left(\sum_{w=0}^{\infty}\upsilon_{w,l}\left(\mathbf{X}\mathbf{X}^{T}\right)^{\odot
w}\right).$

Therefore, for arbitrary $i,j\in[n]$

ij
$\displaystyle=\sum_{p=0}^{\infty}\alpha_{p,l}\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}+\left(n\sum_{q=0}^{\infty}\kappa_{q,l-1}\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{q}\right)\left(\sum_{w=0}^{\infty}\upsilon_{w,l}\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{w}\right).$

Observe
$n\sum_{q=0}^{\infty}\kappa_{q,l-1}\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{q}=\Theta^{(l-1)}(\mathbf{x}_{i},\mathbf{x}_{j})$
and therefore the series must converge due to the convergence of the NTK.
Furthermore,
$\sum_{w=0}^{\infty}\upsilon_{w,l}\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{w}=[\dot{\mathbf{G}}_{n,l}]_{ij}$
and therefore is absolutely convergent by Lemma B.2. As a result, by Merten’s
Theorem the product of these two series is equal to their Cauchy product.
Therefore

ij
$\displaystyle=\sum_{p=0}^{\infty}\alpha_{p,l}\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}+\sum_{p=0}^{\infty}\left(\sum_{q=0}^{p}\kappa_{q,l-1}\upsilon_{p-q,l}\right)\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}$
$\displaystyle=\sum_{p=0}^{\infty}\left(\alpha_{p,l}+\sum_{q=0}^{p}\kappa_{q,l-1}\upsilon_{p-q,l}\right)\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p}$
$\displaystyle=\sum_{p=0}^{\infty}\kappa_{p,l}\langle\mathbf{x}_{i},\mathbf{x}_{j}\rangle^{p},$

from which the (5) immediately follows. ∎

###  B.2 Analyzing the coefficients of the NTK power series

In this section we study the coefficients of the NTK power series stated in
Theorem 3.1. Our first observation is that, under additional assumptions on
the activation function $\phi$, the recurrence relationship (6) can be
simplified in order to depend only on the Hermite expansion of $\phi$.

######  Lemma B.3.

Under Assumption 3 the Hermite coefficients of $\phi^{\prime}$ satisfy

$\mu_{k}(\phi^{\prime})=\sqrt{k+1}\mu_{k+1}(\phi)$

for all $k\in\mathbb{Z}_{\geq 0}$.

###### Proof.

Note for each $n\in\mathbb{N}$ as $\phi$ is absolutely continuous on $[-n,n]$
it is differentiable a.e. on $[-n,n]$. It follows by the countable additivity
of the Lebesgue measure that $\phi$ is differentiable a.e. on $\mathbb{R}$.
Furthermore, as $\phi$ is polynomially bounded we have $\phi\in
L^{2}(\mathbb{R},e^{-x^{2}/2}/\sqrt{2\pi})$. Fix $a>0$. Since $\phi$ is
absolutely continuous on $[-a,a]$ it is of bounded variation on $[-a,a]$. Also
note that $h_{k}(x)e^{-x^{2}/2}$ is of bounded variation on $[-a,a]$ due to
having a bounded derivative. Thus we have by Lebesgue-Stieltjes integration-
by-parts (see e.g. Folland 1999, Chapter 3)

$\displaystyle\int_{-a}^{a}\phi^{\prime}(x)h_{k}(x)e^{-x^{2}/2}dx$
$\displaystyle=\phi(a)h_{k}(a)e^{-a^{2}/2}-\phi(-a)h_{k}(-a)e^{-a^{2}/2}+\int_{-a}^{a}\phi(x)[xh_{k}(x)-h_{k}^{\prime}(x)]e^{-x^{2}/2}dx$
$\displaystyle=\phi(a)h_{k}(a)e^{-a^{2}/2}-\phi(-a)h_{k}(-a)e^{-a^{2}/2}+\int_{-a}^{a}\phi(x)\sqrt{k+1}h_{k+1}(x)e^{-x^{2}/2}dx,$

where in the last line above we have used the fact that (24) and (25) imply
that $xh_{k}(x)-h_{k}^{\prime}(x)=\sqrt{k+1}h_{k+1}(x)$. Thus we have shown

$\displaystyle\int_{-a}^{a}\phi^{\prime}(x)h_{k}(x)e^{-x^{2}/2}dx$
$\displaystyle=\phi(a)h_{k}(a)e^{-a^{2}/2}-\phi(-a)h_{k}(-a)e^{-a^{2}/2}+\int_{-a}^{a}\phi(x)\sqrt{k+1}h_{k+1}(x)e^{-x^{2}/2}dx.$

We note that since $|\phi(x)h_{k}(x)|=\mathcal{O}(|x|^{\beta+k})$ we have that
as $a\rightarrow\infty$ the first two terms above vanish. Thus by sending
$a\rightarrow\infty$ we have

$\int_{-\infty}^{\infty}\phi^{\prime}(x)h_{k}(x)e^{-x^{2}/2}dx=\int_{-\infty}^{\infty}\sqrt{k+1}\phi(x)h_{k+1}(x)e^{-x^{2}/2}dx.$

After dividing by $\sqrt{2\pi}$ we get the desired result. ∎

In particular, under Assumption 3, and as highlighted by Corollary B.4, which
follows directly from Lemmas B.2 and B.3, the NTK coefficients can be computed
only using the Hermite coefficients of $\phi$.

######  Corollary B.4.

Under Assumptions 1, 2 and 3, for all $p\in\mathbb{Z}_{\geq 0}$

$\upsilon_{p,l}=\begin{cases}(p+1)\alpha_{p+1,2},&l=2,\\\
\sum_{k=0}^{\infty}\upsilon_{k,2}F(p,k,\bar{\alpha}_{l-1}),&l\geq
3.\end{cases}$ (43)

With these results in place we proceed to analyze the decay of the
coefficients of the NTK for depth two networks. As stated in the main text,
the decay of the NTK coefficients depends on the decay of the Hermite
coefficients of the activation function deployed. This in turn is strongly
influenced by the behavior of the tails of the activation function. To this
end we roughly group activation functions into three categories: growing
tails, flat or constant tails and finally decaying tails. Analyzing each of
these groups in full generality is beyond the scope of this paper, we
therefore instead study the behavior of ReLU, Tanh and Gaussian activation
functions, being prototypical and practically used examples of each of these
three groups respectively. We remark that these three activation functions
satisfy Assumption 3. For typographical ease we let
$\omega_{\sigma}(z)\vcentcolon=(1/\sqrt{2\pi\sigma^{2}})\exp\left(-z^{2}/(2\sigma^{2})\right)$
denote the Gaussian activation function with variance $\sigma^{2}$.

See 3.2

###### Proof.

Recall (9),

$\kappa_{p,2}=\sigma_{w}^{2}(1+\gamma_{w}^{2}p)\mu_{p}^{2}(\phi)+\sigma_{w}^{2}\gamma_{b}^{2}(1+p)\mu_{p+1}^{2}(\phi)+\delta_{p=0}\sigma_{b}^{2}.$

In order to bound $\kappa_{p,2}$ we proceed by using Lemma A.4 to bound the
square of the Hermite coefficients. We start with ReLU. Note Lemma A.4
actually provides precise expressions for the Hermite coefficients of ReLU,
however, these are not immediately easy to interpret. Observe from Lemma A.4
that above index $p=2$ all odd indexed Hermite coefficients are $0$. It
therefore suffices to bound the even indexed terms, given by

$\mu_{p}(ReLU)=\frac{1}{\sqrt{2\pi}}\frac{(p-3)!!}{\sqrt{p!}}.$

Observe from (33) that for $p$ even

$h_{p}(0)=(-1)^{p/2}\frac{(p-1)!!}{\sqrt{p!}},$

therefore

$\mu_{p}(ReLU)=\frac{1}{\sqrt{2\pi}}\frac{(p-3)!!}{\sqrt{p!}}=\frac{1}{\sqrt{2\pi}}\frac{\left\lvert
h_{p}(0)\right\rvert}{p-1}.$

Analyzing now $\left\lvert h_{p}(0)\right\rvert$,

$\frac{(p-1)!!}{\sqrt{p!}}=\frac{\prod_{i=1}^{p/2}(2i-1)}{\sqrt{\prod_{i=1}^{p/2}(2i-1)2i}}=\sqrt{\frac{\prod_{i=1}^{p/2}(2i-1)}{\prod_{i=1}^{p/2}2i}}=\sqrt{\frac{(p-1)!!}{p!!}}.$

Here, the expression inside the square root is referred to in the literature
as the Wallis ratio, for which the following lower and upper bounds are
available Kazarinoff (1956),

$\sqrt{\frac{1}{\pi(p+0.5)}}<\frac{(p-1)!!}{p!!}<\sqrt{\frac{1}{\pi(p+0.25)}}.$
(44)

As a result

$\left\lvert h_{p}(0)\right\rvert=\Theta(p^{-1/4})$

and therefore

$\mu_{p}(ReLU)=\begin{cases}\Theta(p^{-5/4}),\;&p\text{ even},\\\ 0,\;&p\text{
odd}.\end{cases}$

As $(p+1)^{-3/2}=\Theta(p^{-3/2})$, then from (9)

$\displaystyle\kappa_{p,2}$
$\displaystyle=\Theta((p\mu_{p}^{2}(ReLU)+\delta_{\gamma_{b}>0}(p+1)\mu_{p+1}^{2}(ReLU)))$
$\displaystyle=\Theta((\delta_{p\text{ even}}p^{-3/2}+\delta_{(p\text{
odd})\cap(\gamma_{b}>0)}(p+1)^{-3/2}))$
$\displaystyle=\Theta\left(\delta_{(p\text{ even})\cup\left((p\text{
odd})\cap(\gamma_{b}>0)\right)}p^{-3/2}\right)$
$\displaystyle=\delta_{(p\text{
even})\cup(\gamma_{b}>0)}\Theta\left(p^{-3/2}\right)$

as claimed in item _1._

We now proceed to analyze $\phi(z)=Tanh(z)$. From Panigrahi et al. (2020,
Corollary F.7.1)

$\mu_{p}(Tanh^{\prime})=\mathcal{O}\left(\exp\left(-\frac{\pi\sqrt{p}}{4}\right)\right).$

As Tanh satisfies the conditions of Lemma B.3

$\mu_{p}(Tanh)=p^{-1/2}\mu_{p-1}(Tanh^{\prime})=\mathcal{O}\left(p^{-1/2}\exp\left(-\frac{\pi\sqrt{p-1}}{4}\right)\right).$

Therefore the result claimed in item _2._ follows as

$\displaystyle\kappa_{p,2}$
$\displaystyle=\mathcal{O}((p\mu_{p}^{2}(Tanh)+(p+1)\mu_{p+1}^{2}(Tanh)))$
$\displaystyle=\mathcal{O}\left(\exp\left(-\frac{\pi\sqrt{p-1}}{2}\right)+\exp\left(-\frac{\pi\sqrt{p}}{2}\right)\right)$
$\displaystyle=\mathcal{O}\left(\exp\left(-\frac{\pi\sqrt{p-1}}{2}\right)\right).$

Finally, we now consider $\phi(z)=\omega_{\sigma}(z)$ where
$\omega_{\sigma}(z)$ is the density function of $\mathcal{N}(0,\sigma^{2})$.
Similar to ReLU, analytic expressions for the Hermite coefficients of
$\omega_{\sigma}(z)$ are known (see e.g., Davis, 2021, Theorem 2.9),

$\mu_{p}^{2}(\omega_{\sigma})=\begin{cases}\frac{p!}{(\left(p/2\right)!)^{2}2^{p}2\pi(\sigma^{2}+1)^{p+1}},\;&\text{p
even},\\\ 0,\;&\text{p odd}.\\\ \end{cases}$

For $p$ even

$(p/2)!=p!!2^{-p/2}.$

Therefore

$\displaystyle\frac{p!}{(p/2)!(p/2)!}=2^{p}\frac{p!}{p!!p!!}=2^{p}\frac{(p-1)!!}{p!!}.$

As a result, for $p$ even and using (44), it follows that

$\displaystyle\mu_{p}^{2}(\omega_{\sigma})$
$\displaystyle=\frac{(\sigma^{2}+1)^{-(p+1)}}{2\pi}\frac{(p-1)!!}{p!!}$
$\displaystyle=\Theta(p^{-1/2}(\sigma^{2}+1)^{-p}).$

Finally, since
$(p+1)^{1/2}(\sigma^{2}+1)^{-p-1}=\Theta(p^{1/2}(\sigma^{2}+1)^{-p})$, then
from (9)

$\displaystyle\kappa_{p,2}$
$\displaystyle=\Theta((p\mu_{p}^{2}(\omega_{\sigma})+\delta_{\gamma_{b}>0}(p+1)\mu_{p+1}^{2}(\omega_{\sigma})))$
$\displaystyle=\Theta\left(\delta_{(p\text{ even})\cup\left((p\text{
odd})\cap(\gamma_{b}>0)\right)}p^{1/2}(\sigma^{2}+1)^{-p}\right)$
$\displaystyle=\delta_{(p\text{
even})\cup(\gamma_{b}>0)}\Theta\left(p^{1/2}(\sigma^{2}+1)^{-p}\right)$

as claimed in item _3._ ∎

###  B.3 Numerical approximation via a truncated NTK power series and
interpretation of 2

Currently, computing the infinite width NTK requires either a) explicit
evaluation of the Gaussian integrals highlighted in (13), b) numerical
approximation of these same integrals such as in Lee et al. (2018), or c)
approximation via a sufficiently wide yet still finite width network, see for
instance Engel et al. (2022); Novak et al. (2022). These Gaussian integrals
(13) can be solved solved analytically only for a minority of activation
functions, notably ReLU as discussed for example by Arora et al. (2019b),
while the numerical integration and finite width approximation approaches are
relatively computationally expensive. The truncated NTK power series we define
as analogous to (5) but with the series involved being computed only up to the
$T$th element. Once the top $T$ coefficients are computed, then for any input
correlation the NTK can be approximated by evaluating the corresponding finite
degree $T$ polynomial.

######  Definition B.5.

For an arbitrary pair $\mathbf{x},\mathbf{y}\in\mathbb{S}^{d-1}$ let
$\rho=\mathbf{x}^{T}\mathbf{y}$ denote their linear correlation. Under
Assumptions 1, 2 and 3, for all $l\in[2,L+1]$ the $T$-truncated NTK power
series $\hat{\Theta}_{T}^{(l)}:[-1,1]\rightarrow\mathbb{R}$ is defined as

$\Theta_{T}^{(l)}(\rho)=\sum_{p=0}^{T}\hat{\kappa}_{p,l}\rho^{p}.$ (45)

and whose coefficients are defined via the following recurrence relation,

$\hat{\kappa}_{p,l}=\begin{cases}\delta_{p=0}\gamma_{b}^{2}+\delta_{p=1}\gamma_{w}^{2},&l=1,\\\
\hat{\alpha}_{p,l}+\sum_{q=0}^{p}\hat{\kappa}_{q,l-1}\hat{\upsilon}_{p-q,l},&l\in[2,L+1].\end{cases}$
(46)

Here, with $\bar{\hat{\alpha}}_{l-1}=(\hat{\alpha}_{p,l-1})_{p=0}^{T}$,

$\hat{\alpha}_{p,l}\vcentcolon=\begin{cases}\sigma_{w}^{2}\mu_{p}^{2}(\phi)+\delta_{p=0}\sigma_{b}^{2},&l=2,\\\
\sum_{k=0}^{T}\hat{\alpha}_{k,2}F(p,k,\bar{\hat{\alpha}}_{l-1}),&l\geq
3\end{cases}$ (47)

and

$\hat{\upsilon}_{p,l}\vcentcolon=\begin{cases}\sqrt{p+1}\hat{\alpha}_{p+1,2},&l=2,\\\
\sum_{k=0}^{T}\sqrt{k+1}\hat{\alpha}_{p+1,2}F(p,k,\bar{\hat{\alpha}}_{l}),&l\geq
3.\end{cases}$ (48)

In order to analyze the performance and potential of the truncated NTK for
numerical approximation, we compute it for ReLU and compare it with its
analytical expression Arora et al. (2019b). To recall this result, let

$\displaystyle R(\rho)$
$\displaystyle\vcentcolon=\frac{\sqrt{1-\rho^{2}}+\rho\cdot\arcsin(\rho)}{\pi}+\frac{\rho}{2},$
$\displaystyle R^{\prime}(\rho)$
$\displaystyle\vcentcolon=\frac{\arcsin(\rho)}{\pi}+\frac{1}{2}.$

Under Assumptions 1 and 2, with $\phi(z)=ReLU(z)$, $\gamma_{w}^{2}=1$,
$\sigma_{w}^{2}=2$, $\sigma_{b}^{2}=\gamma_{b}^{2}=0$,
$\mathbf{x},\mathbf{y}\in\mathbb{S}^{d}$ and
$\rho_{1}\vcentcolon=\mathbf{x}^{T}\mathbf{y}$, then
$\Theta_{1}(\mathbf{x},\mathbf{y})=\rho$ and for all $l\in[2,L+1]$

$\displaystyle\rho_{l}=R(\rho_{l-1}),$ (49)
$\displaystyle\Theta_{l}(\mathbf{x},\mathbf{y})=\rho_{l}+\rho_{l-1}R^{\prime}(\rho_{l-1}).$

Turning our attention to Figure 2, we observe particularly for input
correlations $\left\lvert\rho\right\rvert\approx 0.5$ and below then the
truncated ReLU NTK power series achieves machine level precision. For
$\left\lvert\rho\right\rvert\approx 1$ higher order coefficients play a more
significant role. As the truncated ReLU NTK power series approximates these
coefficients less well the overall approximation of the ReLU NTK is worse. We
remark also that negative correlations have a smaller absolute error as odd
indexed terms cancel with even index terms: we emphasize again that in Figure
2 we plot the absolute not relative error. In addition, for $L=1$ there is
symmetry in the absolute error for positive and negative correlations as
$\alpha_{p,2}=0$ for all odd $p$. One also observes that approximation
accuracy goes down with depth, which is due to the error in the coefficients
at the previous layer contributing to the error in the coefficients at the
next, thereby resulting in an accumulation of error with depth. Also, and
certainly as one might expect, a larger truncation point $T$ results in
overall better approximation. Finally, as the decay in the Hermite
coefficients for ReLU is relatively slow, see e.g., Table 1 and Lemma 3.2, we
expect the truncated ReLU NTK power series to perform worse relative to the
truncated NTK’s for other activation functions.

Figure 2: (NTK Approximation via Truncation) Absolute error between the
analytical ReLU NTK and the truncated ReLU NTK power series as a function of
the input correlation $\rho$ for two different values of the truncation point
$T$ and three different values for the depth $L$ of the network. Although the
truncated NTK achieves a uniform approximation error of only $10^{-1}$ on
$[-1,1]$, for $\left\lvert\rho\right\rvert\leq 0.5$, which we remark is more
typical for real world data, $T=50$ suffices for the truncated NTK to achieve
machine level precision.

##  Appendix C Analyzing the spectrum of the NTK via its power series

###  C.1 Effective rank of power series kernels

Recall that for a positive semidefinite matrix $\mathbf{A}$ we define the
effective rank Huang et al. (2022) via the following ratio

$\mathrm{eff}(\mathbf{A}):=\frac{Tr(\mathbf{A})}{\lambda_{1}(\mathbf{A})}.$

We consider a kernel Gram matrix $\mathbf{K}\in\mathbb{R}^{n\times n}$ that
has the following power series representation in terms of an input gram matrix
$\mathbf{X}\mathbf{X}^{T}$

$n\mathbf{K}=\sum_{i=0}^{\infty}c_{i}(\mathbf{X}\mathbf{X}^{T})^{\odot i}.$

Whenever $c_{0}\neq 0$ the effective rank of $\mathbf{K}$ is $O(1)$, as
displayed in the following theorem. See 4.1

###### Proof.

By linearity of trace we have that

$Tr(n\mathbf{K})=\sum_{i=0}^{\infty}c_{i}Tr((\mathbf{X}\mathbf{X}^{T})^{\odot
i})=n\sum_{i=0}^{\infty}c_{i}$

where we have used the fact that $Tr((\mathbf{X}\mathbf{X}^{T})^{\odot i})=n$
for all $i\in\mathbb{N}$. On the other hand

$\lambda_{1}(n\mathbf{K})\geq\lambda_{1}(c_{0}(\mathbf{X}\mathbf{X}^{T})^{0})=\lambda_{1}(c_{0}\mathbf{1}_{n\times
n})=nc_{0}.$

Thus we have that

$\mathrm{eff}(\mathbf{K})=\frac{Tr(\mathbf{K})}{\lambda_{1}(\mathbf{K})}=\frac{Tr(n\mathbf{K})}{\lambda_{1}(n\mathbf{K})}\leq\frac{\sum_{i=0}^{\infty}c_{i}}{c_{0}}.$

∎

The above theorem demonstrates that the constant term
$c_{0}\mathbf{1}_{n\times n}$ in the kernel leads to a significant outlier in
the spectrum of $\mathbf{K}$. However this fails to capture how the structure
of the input data $\mathbf{X}$ manifests in the spectrum of $\mathbf{K}$. For
this we will examine the centered kernel matrix
$\widetilde{\mathbf{K}}:=\mathbf{K}-\frac{c_{0}}{n}\mathbf{1}\mathbf{1}^{T}$.
Using a very similar argument as before we can demonstrate that the effective
rank of $\widetilde{\mathbf{K}}$ is controlled by the effective rank of the
input data gram $\mathbf{X}\mathbf{X}^{T}$. This is formalized in the
following theorem. See 4.3

###### Proof.

By the linearity of the trace we have that

$Tr(n\widetilde{\mathbf{K}})=\sum_{i=1}^{\infty}c_{i}Tr((\mathbf{X}\mathbf{X}^{T})^{\odot
i})=Tr(\mathbf{X}\mathbf{X}^{T})\sum_{i=1}^{\infty}c_{i}$

where we have used the fact that $Tr((\mathbf{X}\mathbf{X}^{T})^{\odot
i})=Tr(\mathbf{X}\mathbf{X}^{T})=n$ for all $i\in[n]$. On the other hand we
have that

$\lambda_{1}(n\widetilde{\mathbf{K}})\geq\lambda_{1}(c_{1}\mathbf{X}\mathbf{X}^{T})=c_{1}\lambda_{1}(\mathbf{X}\mathbf{X}^{T}).$

Thus we conclude

$\mathrm{eff}(\widetilde{\mathbf{K}})=\frac{Tr(\widetilde{\mathbf{K}})}{\lambda_{1}(\widetilde{\mathbf{K}})}=\frac{Tr(n\widetilde{\mathbf{K}})}{\lambda_{1}(n\widetilde{\mathbf{K}})}\leq\frac{Tr(\mathbf{X}\mathbf{X}^{T})}{\lambda_{1}(\mathbf{X}\mathbf{X}^{T})}\frac{\sum_{i=1}^{\infty}c_{i}}{c_{1}}.$

∎

###  C.2 Effective rank of the NTK for finite width networks

####  C.2.1 Notation and definitions

We will let $[k]:=\\{1,2,\ldots,k\\}$. We consider a neural network

$\sum_{\ell=1}^{m}a_{\ell}\phi(\langle\mathbf{w}_{\ell},\mathbf{x}\rangle)$

where $\mathbf{x}\in\mathbb{R}^{d}$ and $\mathbf{w}_{\ell}\in\mathbb{R}^{d}$,
$a_{\ell}\in\mathbb{R}$ for all $\ell\in[m]$ and $\phi$ is a scalar valued
activation function. The network we present here does not have any bias values
in the inner-layer, however the results we will prove later apply to the
nonzero bias case by replacing $\mathbf{x}$ with $[\mathbf{x}^{T},1]^{T}$. We
let $\mathbf{W}\in\mathbb{R}^{m\times d}$ be the matrix whose $\ell$-th row is
equal to $\mathbf{w}_{\ell}$ and $\mathbf{a}\in\mathbb{R}^{m}$ be the vector
whose $\ell$-th entry is equal to $a_{\ell}$. We can then write the neural
network in vector form

$f(\mathbf{x};\mathbf{W},\mathbf{a})=\mathbf{a}^{T}\phi(\mathbf{W}\mathbf{x})$

where $\phi$ is understood to be applied entry-wise.

Suppose we have $n$ training data inputs
$\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\in\mathbb{R}^{d}$. We will let
$\mathbf{X}\in\mathbb{R}^{n\times d}$ be the matrix whose $i$-th row is equal
to $\mathbf{x}_{i}$. Let $\mathbf{\theta}_{inner}=vec(\mathbf{W})$ denote the
row-wise vectorization of the inner-layer weights. We consider the Jacobian of
the neural networks predictions on the training data with respect to the inner
layer weights:

$\mathbf{J}_{inner}^{T}=\left[\frac{\partial
f(\mathbf{x}_{1})}{\partial\mathbf{\theta}_{inner}},\frac{\partial
f(\mathbf{x}_{2})}{\partial\mathbf{\theta}_{inner}},\ldots,\frac{\partial
f(\mathbf{x}_{n})}{\partial\mathbf{\theta}_{inner}}\right]$

Similarly we can look at the analagous quantity for the outer layer weights

$\mathbf{J}_{outer}^{T}=\left[\frac{\partial
f(\mathbf{x}_{1})}{\partial\mathbf{a}},\frac{\partial
f(\mathbf{x}_{2})}{\partial\mathbf{a}},\ldots,\frac{\partial
f(\mathbf{x}_{n})}{\partial\mathbf{a}}\right]=\phi\left(\mathbf{W}\mathbf{X}^{T}\right).$

Our first observation is that the per-example gradients for the inner layer
weights have a nice Kronecker product representation

$\frac{\partial
f(\mathbf{x})}{\partial\mathbf{\theta}_{inner}}=\begin{bmatrix}a_{1}\phi^{\prime}(\langle\mathbf{w}_{1},\mathbf{x}\rangle)\\\
a_{2}\phi^{\prime}(\langle\mathbf{w}_{2},\mathbf{x}\rangle)\\\ \cdots\\\
a_{m}\phi^{\prime}(\langle\mathbf{w}_{m},\mathbf{x}\rangle)\end{bmatrix}\otimes\mathbf{x}.$

For convenience we will let

$\mathbf{Y}_{i}:=\begin{bmatrix}a_{1}\phi^{\prime}(\langle\mathbf{w}_{1},\mathbf{x}_{i}\rangle)\\\
a_{2}\phi^{\prime}(\langle\mathbf{w}_{2},\mathbf{x}_{i}\rangle)\\\ \cdots\\\
a_{m}\phi^{\prime}(\langle\mathbf{w}_{m},\mathbf{x}_{i}\rangle)\end{bmatrix}.$

where the dependence of $\mathbf{Y}_{i}$ on the parameters $\mathbf{W}$ and
$\mathbf{a}$ is suppressed (formally
$\mathbf{Y}_{i}=\mathbf{Y}_{i}(\mathbf{W},\mathbf{a})$). This way we may write

$\frac{\partial
f(\mathbf{x}_{i})}{\partial\mathbf{\theta}_{inner}}=\mathbf{Y}_{i}\otimes\mathbf{x}_{i}.$

We will study the NTK with respect to the inner-layer weights

$\mathbf{K}_{inner}=\mathbf{J}_{inner}\mathbf{J}_{inner}^{T}$

and the same quantity for the outer-layer weights

$\mathbf{K}_{outer}=\mathbf{J}_{outer}\mathbf{J}_{outer}^{T}.$

For a hermitian matrix $\mathbf{A}$ we will let $\lambda_{i}(\mathbf{A})$
denote the $i$th largest eigenvalue of $\mathbf{A}$ so that
$\lambda_{1}(\mathbf{A})\geq\lambda_{2}(\mathbf{A})\geq\cdots\geq\lambda_{n}(\mathbf{A})$.
Similarly for an arbitrary matrix $\mathbf{A}$ we will let
$\sigma_{i}(\mathbf{A})$ to the $i$th largest singular value of $\mathbf{A}$.
For a matrix $\mathbf{A}\in\mathbb{R}^{r\times k}$ we will let
$\sigma_{min}(\mathbf{A})=\sigma_{\min(r,k)}$.

####  C.2.2 Effective rank

For a positive semidefinite matrix $\mathbf{A}$ we define the effective rank
(Huang et al., 2022) of $\mathbf{A}$ to be the quantity

$\mathrm{eff}(\mathbf{A}):=\frac{Tr(\mathbf{A})}{\lambda_{1}(\mathbf{A})}.$

The effective rank quantifies how many eigenvalues are on the order of the
largest eigenvalue. We have the Markov-like inequality

$\left\lvert\\{i:\lambda_{i}(\mathbf{A})\geq
c\lambda_{1}(\mathbf{A})\\}\right\rvert\leq
c^{-1}\frac{Tr(\mathbf{A})}{\lambda_{1}(\mathbf{A})}$

and the eigenvalue bound

$\frac{\lambda_{i}(\mathbf{A})}{\lambda_{1}(\mathbf{A})}\leq\frac{1}{i}\frac{Tr(\mathbf{A})}{\lambda_{1}(\mathbf{A})}.$

Let $\mathbf{A}$ and $\mathbf{B}$ be positive semidefinite matrices. Then we
have

$\displaystyle\frac{Tr(\mathbf{A}+\mathbf{B})}{\lambda_{1}(\mathbf{A}+\mathbf{B})}\leq\frac{Tr(\mathbf{A})+Tr(\mathbf{B})}{\max\left(\lambda_{1}(\mathbf{A}),\lambda_{1}(\mathbf{B})\right)}\leq\frac{Tr(\mathbf{A})}{\lambda_{1}(\mathbf{A})}+\frac{Tr(\mathbf{B})}{\lambda_{1}(\mathbf{B})}.$

Thus the effective rank is subadditive for positive semidefinite matrices.

We will be interested in bounding the effective rank of the NTK. Let
$\mathbf{K}=\mathbf{J}\mathbf{J}^{T}=\mathbf{J}_{outer}\mathbf{J}_{outer}^{T}+\mathbf{J}_{inner}\mathbf{J}_{inner}^{T}=\mathbf{K}_{outer}+\mathbf{K}_{inner}$
be the NTK matrix with respect to all the network parameters. Note that by
subadditivity

$\frac{Tr(\mathbf{K})}{\lambda_{1}(\mathbf{K})}\leq\frac{Tr(\mathbf{K}_{outer})}{\lambda_{1}(\mathbf{K}_{outer})}+\frac{Tr(\mathbf{K}_{inner})}{\lambda_{1}(\mathbf{K}_{inner})}.$

In this vein we will control the effective rank of $\mathbf{K}_{inner}$ and
$\mathbf{K}_{outer}$ separately.

####  C.2.3 Effective rank of inner-layer NTK

We will show that the effective rank of inner-layer NTK is bounded by a
multiple of the effective rank of the data input gram
$\mathbf{X}\mathbf{X}^{T}$. We introduce the following meta-theorem that we
will use to prove various corollaries later

######  Theorem C.1.

Set
$\alpha:=\sup_{\left\lVert\mathbf{b}\right\rVert=1}\left[\min_{j\in[n]}|\langle\mathbf{Y}_{j},\mathbf{b}\rangle|\right]$.
Assume $\alpha>0$. Then

$\frac{\min_{i\in[n]}\left\lVert\mathbf{Y}_{i}\right\rVert_{2}^{2}Tr(\mathbf{X}\mathbf{X}^{T})}{\max_{i\in[n]}\left\lVert\mathbf{Y}_{i}\right\rVert_{2}^{2}\lambda_{1}(\mathbf{X}\mathbf{X}^{T})}\leq\frac{Tr(\mathbf{K}_{inner})}{\lambda_{1}\left(\mathbf{K}_{inner}\right)}\leq\frac{\max_{i\in[n]}\left\lVert\mathbf{Y}_{i}\right\rVert_{2}^{2}}{\alpha^{2}}\frac{Tr(\mathbf{X}\mathbf{X}^{T})}{\lambda_{1}(\mathbf{X}\mathbf{X}^{T})}$

###### Proof.

We will first prove the upper bound. We first observe that

$\displaystyle Tr(\mathbf{K}_{inner})=\sum_{i=1}^{n}\left\lVert\frac{\partial
f(\mathbf{x}_{i})}{\partial\mathbf{\theta}_{inner}}\right\rVert_{2}^{2}=\sum_{i=1}^{n}\left\lVert\mathbf{Y}_{i}\otimes\mathbf{x}_{i}\right\rVert_{2}^{2}=\sum_{i=1}^{n}\left\lVert\mathbf{Y}_{i}\right\rVert_{2}^{2}\left\lVert\mathbf{x}_{i}\right\rVert_{2}^{2}$
$\displaystyle\leq\max_{j\in[n]}\left\lVert\mathbf{Y}_{j}\right\rVert_{2}^{2}\sum_{i=1}^{n}\left\lVert\mathbf{x}_{i}\right\rVert_{2}^{2}=\max_{j\in[n]}\left\lVert\mathbf{Y}_{j}\right\rVert_{2}^{2}Tr(\mathbf{X}\mathbf{X}^{T})$

Recall that

$\lambda_{1}\left(\mathbf{K}_{inner}\right)=\lambda_{1}\left(\mathbf{J}_{inner}\mathbf{J}_{inner}^{T}\right)=\lambda_{1}\left(\mathbf{J}_{inner}^{T}\mathbf{J}_{inner}\right).$

Well

$\displaystyle\mathbf{J}_{inner}^{T}\mathbf{J}_{inner}=\sum_{i=1}^{n}\frac{\partial
f(\mathbf{x}_{i})}{\partial\mathbf{\theta}_{inner}}\frac{\partial
f(\mathbf{x}_{i})}{\partial\mathbf{\theta}_{inner}}^{T}=\sum_{i=1}^{n}\left[\mathbf{Y}_{i}\otimes\mathbf{x}_{i}\right]\left[\mathbf{Y}_{i}\otimes\mathbf{x}_{i}\right]^{T}$
$\displaystyle=\sum_{i=1}^{n}\left[\mathbf{Y}_{i}\mathbf{Y}_{i}^{T}\right]\otimes\left[\mathbf{x}_{i}\mathbf{x}_{i}^{T}\right]$

Well then we may use the fact that

$\lambda_{1}(\mathbf{J}_{inner}^{T}\mathbf{J}_{inner})=\max_{\left\lVert\mathbf{b}\right\rVert_{2}=1}\mathbf{b}^{T}\mathbf{J}_{inner}^{T}\mathbf{J}_{inner}\mathbf{b}$

Let $\mathbf{b}_{1}\in\mathbb{R}^{m}$ and $\mathbf{b}_{2}\in\mathbb{R}^{d}$ be
vectors that we will optimize later satisfying
$\left\lVert\mathbf{b}_{1}\right\rVert_{2}\left\lVert\mathbf{b}_{2}\right\rVert_{2}=1$.
Then we have that
$\left\lVert\mathbf{b}_{1}\otimes\mathbf{b}_{2}\right\rVert=1$ and

$\displaystyle(\mathbf{b}_{1}\otimes\mathbf{b}_{2})^{T}\mathbf{J}_{inner}^{T}\mathbf{J}_{inner}(\mathbf{b}_{1}\otimes\mathbf{b}_{2})=\sum_{i=1}^{n}(\mathbf{b}_{1}\otimes\mathbf{b}_{2})^{T}\left(\left[\mathbf{Y}_{i}\mathbf{Y}_{i}^{T}\right]\otimes\left[\mathbf{x}_{i}\mathbf{x}_{i}^{T}\right]\right)(\mathbf{b}_{1}\otimes\mathbf{b}_{2})$
$\displaystyle=\sum_{i=1}^{n}\left[\mathbf{b}_{1}^{T}\mathbf{Y}_{i}\mathbf{Y}_{i}^{T}\mathbf{b}_{1}\right]\left[\mathbf{b}_{2}^{T}\mathbf{x}_{i}\mathbf{x}_{i}^{T}\mathbf{b}_{2}\right]\geq\left[\min_{j\in[n]}\mathbf{b}_{1}^{T}\mathbf{Y}_{j}\mathbf{Y}_{j}^{T}\mathbf{b}_{1}\right]\sum_{i=1}^{n}\mathbf{b}_{2}^{T}\mathbf{x}_{i}\mathbf{x}_{i}^{T}\mathbf{b}_{2}$
$\displaystyle=\left[\min_{j\in[n]}\mathbf{b}_{1}^{T}\mathbf{Y}_{j}\mathbf{Y}_{j}^{T}\mathbf{b}_{1}\right]\mathbf{b}_{2}^{T}\left[\sum_{i=1}^{n}\mathbf{x}_{i}\mathbf{x}_{i}^{T}\right]\mathbf{b}_{2}=\left[\min_{j\in[n]}\mathbf{b}_{1}^{T}\mathbf{Y}_{j}\mathbf{Y}_{j}^{T}\mathbf{b}_{1}\right]\mathbf{b}_{2}\mathbf{X}^{T}\mathbf{X}\mathbf{b}_{2}$

Pick $\mathbf{b}_{2}$ so that $\left\lVert\mathbf{b}_{2}\right\rVert=1$ and

$\mathbf{b}_{2}\mathbf{X}^{T}\mathbf{X}\mathbf{b}_{2}=\lambda_{1}(\mathbf{X}^{T}\mathbf{X})=\lambda_{1}(\mathbf{X}\mathbf{X}^{T}).$

Thus for this choice of $\mathbf{b}_{2}$ we have

$\displaystyle\lambda_{1}(\mathbf{J}_{inner}^{T}\mathbf{J}_{inner})\geq(\mathbf{b}_{1}\otimes\mathbf{b}_{2})^{T}\mathbf{J}_{inner}^{T}\mathbf{J}_{inner}(\mathbf{b}_{1}\otimes\mathbf{b}_{2})\geq$
$\displaystyle\left[\min_{j\in[n]}\mathbf{b}_{1}^{T}\mathbf{Y}_{j}\mathbf{Y}_{j}^{T}\mathbf{b}_{1}\right]\mathbf{b}_{2}\mathbf{X}^{T}\mathbf{X}\mathbf{b}_{2}=\left[\min_{j\in[n]}\mathbf{b}_{1}^{T}\mathbf{Y}_{j}\mathbf{Y}_{j}^{T}\mathbf{b}_{1}\right]\lambda_{1}(\mathbf{X}\mathbf{X}^{T})$

Now note that
$\alpha^{2}=\sup_{\left\lVert\mathbf{b}_{1}\right\rVert=1}\left[\min_{j\in[n]}\mathbf{b}_{1}^{T}\mathbf{Y}_{j}\mathbf{Y}_{j}^{T}\mathbf{b}_{1}\right]$.
Thus by taking the sup over $\mathbf{b}_{1}$ in our previous bound we have

$\lambda_{1}(\mathbf{K}_{inner})=\lambda_{1}(\mathbf{J}_{inner}^{T}\mathbf{J}_{inner})\geq\alpha^{2}\lambda_{1}(\mathbf{X}\mathbf{X}^{T}).$

Thus combined with our previous result we have

$\frac{Tr(\mathbf{K}_{inner})}{\lambda_{1}\left(\mathbf{K}_{inner}\right)}\leq\frac{\max_{i\in[n]}\left\lVert\mathbf{Y}_{i}\right\rVert_{2}^{2}}{\alpha^{2}}\frac{Tr(\mathbf{X}\mathbf{X}^{T})}{\lambda_{1}(\mathbf{X}\mathbf{X}^{T})}.$

We now prove the lower bound.

$\displaystyle Tr(\mathbf{K}_{inner})=\sum_{i=1}^{n}\left\lVert\frac{\partial
f(\mathbf{x}_{i})}{\partial\mathbf{\theta}_{inner}}\right\rVert_{2}^{2}=\sum_{i=1}^{n}\left\lVert\mathbf{Y}_{i}\otimes\mathbf{x}_{i}\right\rVert_{2}^{2}=\sum_{i=1}^{n}\left\lVert\mathbf{Y}_{i}\right\rVert_{2}^{2}\left\lVert\mathbf{x}_{i}\right\rVert_{2}^{2}$
$\displaystyle\geq\min_{j\in[n]}\left\lVert\mathbf{Y}_{j}\right\rVert_{2}^{2}\sum_{i=1}^{n}\left\lVert\mathbf{x}_{i}\right\rVert_{2}^{2}=\min_{j\in[n]}\left\lVert\mathbf{Y}_{j}\right\rVert_{2}^{2}Tr(\mathbf{X}\mathbf{X}^{T})$

Let $\mathbf{Y}\in\mathbb{R}^{n\times m}$ be the matrix whose $i$th row is
equal to $\mathbf{Y}_{i}$. Then observe that

$\mathbf{K}_{inner}=[\mathbf{Y}\mathbf{Y}^{T}]\odot[\mathbf{X}\mathbf{X}^{T}]$

where $\odot$ denotes the entry-wise Hadamard product of two matrices. We now
recall that if $\mathbf{A}$ and $\mathbf{B}$ are two positive semidefinite
matrices we have (Oymak & Soltanolkotabi, 2020, Lemma 2)

$\lambda_{1}(\mathbf{A}\odot\mathbf{B})\leq\max_{i\in[n]}\mathbf{A}_{i,i}\lambda_{1}(\mathbf{B}).$

Applying this to $\mathbf{K}_{inner}$ we get that

$\lambda_{1}(\mathbf{K}_{inner})\leq\max_{i\in[n]}\left\lVert\mathbf{Y}_{i}\right\rVert_{2}^{2}\lambda_{1}(\mathbf{X}\mathbf{X}^{T})$

Combining this with our previous result we get

$\frac{\min_{i\in[n]}\left\lVert\mathbf{Y}_{i}\right\rVert_{2}^{2}Tr(\mathbf{X}\mathbf{X}^{T})}{\max_{i\in[n]}\left\lVert\mathbf{Y}_{i}\right\rVert_{2}^{2}\lambda_{1}(\mathbf{X}\mathbf{X}^{T})}\leq\frac{Tr(\mathbf{K}_{inner})}{\lambda_{1}(\mathbf{K}_{inner})}$

∎

We can immediately get a useful corollary that applies to the ReLU activation
function

######  Corollary C.2.

Set
$\alpha:=\sup_{\left\lVert\mathbf{b}\right\rVert=1}\left[\min_{j\in[n]}|\langle\mathbf{Y}_{j},\mathbf{b}\rangle|\right]$
and $\gamma_{max}:=\sup_{x\in\mathbb{R}}|\phi^{\prime}(x)|$. Assume $\alpha>0$
and $\gamma_{max}<\infty$. Then

$\frac{\alpha^{2}}{\gamma_{max}^{2}\left\lVert\mathbf{a}\right\rVert_{2}^{2}}\frac{Tr(\mathbf{X}\mathbf{X}^{T})}{\lambda_{1}(\mathbf{X}\mathbf{X}^{T})}\leq\frac{Tr(\mathbf{K}_{inner})}{\lambda_{1}\left(\mathbf{K}_{inner}\right)}\leq\frac{\gamma_{max}^{2}\left\lVert\mathbf{a}\right\rVert_{2}^{2}}{\alpha^{2}}\frac{Tr(\mathbf{X}\mathbf{X}^{T})}{\lambda_{1}(\mathbf{X}\mathbf{X}^{T})}$

###### Proof.

Note that the hypothesis on $|\phi^{\prime}|$ gives
$\left\lVert\mathbf{Y}_{i}\right\rVert_{2}^{2}\leq\gamma_{max}^{2}\left\lVert\mathbf{a}\right\rVert_{2}^{2}$
for all $i\in[n]$. Moreover by Cauchy-Schwarz we have that
$\min_{i\in[n]}\left\lVert\mathbf{Y}_{i}\right\rVert_{2}\geq\alpha$. Thus by
theorem C.1 we get the desired result. ∎

If $\phi$ is a leaky ReLU type activation (say like those used in Nguyen &
Mondelli (2020)) Theorem C.1 translates into an even simpler bound

######  Corollary C.3.

Suppose $\phi^{\prime}(x)\in[\gamma_{min},\gamma_{max}]$ for all
$x\in\mathbb{R}$ where $\gamma_{min}>0$. Then

$\frac{\gamma_{min}^{2}Tr(\mathbf{X}\mathbf{X}^{T})}{\gamma_{max}^{2}\lambda_{1}(\mathbf{X}\mathbf{X}^{T})}\leq\frac{Tr(\mathbf{K}_{inner})}{\lambda_{1}\left(\mathbf{K}_{inner}\right)}\leq\frac{\gamma_{max}^{2}}{\gamma_{min}^{2}}\frac{Tr(\mathbf{X}\mathbf{X}^{T})}{\lambda_{1}(\mathbf{X}\mathbf{X}^{T})}$

###### Proof.

We will lower bound

$\alpha:=\sup_{\left\lVert\mathbf{b}\right\rVert=1}\left[\min_{j\in[n]}|\langle\mathbf{Y}_{j},\mathbf{b}\rangle|\right]$

so that we can apply Corollary C.2. Set
$\mathbf{b}=\mathbf{a}/\left\lVert\mathbf{a}\right\rVert_{2}$. Then we have
that

$\langle\mathbf{Y}_{j},\mathbf{b}\rangle=\sum_{\ell=1}^{m}a_{\ell}\phi^{\prime}(\langle\mathbf{w}_{\ell},\mathbf{x}_{j}\rangle)a_{\ell}/\left\lVert\mathbf{a}\right\rVert_{2}\geq\frac{\gamma_{min}}{\left\lVert\mathbf{a}\right\rVert_{2}}\sum_{\ell=1}^{m}a_{\ell}^{2}=\gamma_{min}\left\lVert\mathbf{a}\right\rVert_{2}$

Thus $\alpha\geq\gamma_{min}\left\lVert\mathbf{a}\right\rVert_{2}$. The result
then follows from Corollary C.2 ∎

To control $\alpha$ in Theorem C.1 when $\phi$ is the ReLU activation function
requires a bit more work. To this end we introduce the following lemma.

######  Lemma C.4.

Assume $\phi(x)=ReLU(x)$. Let $R_{min},R_{max}>0$ and define
$\tau=\\{\ell\in[m]:|a_{\ell}|\in[R_{min},R_{max}]\\}$. Set
$T=\min_{i\in[n]}\sum_{\ell\in\tau}\mathbb{I}\left[\langle\mathbf{x}_{i},\mathbf{w}_{\ell}\rangle\geq
0\right]$. Then

$\alpha:=\sup_{\left\lVert\mathbf{b}\right\rVert=1}\left[\min_{i\in[n]}|\langle\mathbf{Y}_{i},\mathbf{b}\rangle|\right]\geq\frac{R_{min}^{2}}{R_{max}}\frac{T}{|\tau|^{1/2}}$

###### Proof.

Let $\mathbf{a}_{\tau}$ be the vector such that
$(\mathbf{a}_{\tau})_{\ell}=a_{\ell}\mathbb{I}[\ell\in\tau]$. Then note that

$\displaystyle\langle\mathbf{Y}_{j},\mathbf{a}_{\tau}/\left\lVert\mathbf{a}_{\tau}\right\rVert_{2}\rangle=\frac{1}{\left\lVert\mathbf{a}_{\tau}\right\rVert}\sum_{\ell\in\tau}a_{\ell}^{2}\mathbb{I}[\langle\mathbf{w}_{\ell},\mathbf{x}_{j}\rangle\geq
0]\geq$
$\displaystyle\frac{R_{min}^{2}}{\left\lVert\mathbf{a}_{\tau}\right\rVert}\sum_{\ell\in\tau}\mathbb{I}[\langle\mathbf{w}_{\ell},\mathbf{x}_{j}\rangle\geq
0]\geq\frac{R_{min}^{2}}{\left\lVert\mathbf{a}_{\tau}\right\rVert_{2}}T\geq\frac{R_{min}^{2}}{R_{max}|\tau|^{1/2}}T.$

∎

Roughly what Lemma C.4 says is that $\alpha$ is controlled when there is a set
of inner-layer neurons that are active for each data point whose outer layer
weights are similar in magnitude. Note that in Du et al. (2019b), Arora et al.
(2019a), Oymak et al. (2019), Li et al. (2020), Xie et al. (2017) and Oymak &
Soltanolkotabi (2020) the outer layer weights all have fixed constant
magnitude. Thus in that case we can set $R_{min}=R_{max}$ in Lemma C.4 so that
$\tau=[m]$. In this setting we have the following result.

######  Theorem C.5.

Assume $\phi(x)=ReLU(x)$. Suppose $|a_{\ell}|=R>0$ for all $\ell\in[m]$.
Furthermore suppose $\mathbf{w}_{1},\ldots,\mathbf{w}_{m}$ are independent
random vectors such that
$\mathbf{w}_{\ell}/\left\lVert\mathbf{w}_{\ell}\right\rVert$ has the uniform
distribution on the sphere for each $\ell\in[m]$. Also assume
$m\geq\frac{4\log(n/\epsilon)}{\delta^{2}}$ for some
$\delta,\epsilon\in(0,1)$. Then with probability at least $1-\epsilon$ we have
that

$\frac{(1-\delta)^{2}}{4}\mathrm{eff}(\mathbf{X}\mathbf{X}^{T})\leq\mathrm{eff}(\mathbf{K}_{inner})\leq\frac{4}{(1-\delta)^{2}}\mathrm{eff}(\mathbf{X}\mathbf{X}^{T}).$

###### Proof.

Fix $j\in[n]$. Note by the assumption on the $\mathbf{w}_{\ell}$’s we have
that $\mathbb{I}[\langle\mathbf{w}_{1},\mathbf{x}_{j}\rangle\geq
0],\ldots,\mathbb{I}[\langle\mathbf{w}_{m},\mathbf{x}_{j}\rangle\geq 0]$ are
i.i.d. Bernouilli random variables taking the values $0$ and $1$ with
probability $1/2$. Thus by the Chernoff bound for Binomial random variables we
have that

$\mathbb{P}\left(\sum_{\ell=1}^{m}\mathbb{I}[\langle\mathbf{w}_{\ell},\mathbf{x}_{j}\rangle\geq
0]\leq\frac{m}{2}(1-\delta)\right)\leq\exp\left(-\delta^{2}\frac{m}{4}\right).$