Characterizing the spectrum of the NTK via a power series expansion
Authors: Michael Murray
Hui Jin
Benjamin Bowman
Guido Montufar
Venue: ICLR 2023 poster (2023)
Keywords: neural tangent kernel
power series
Hermite coefficient
activation function
spectrum
input Gram matrix

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 and explore the role of depth. 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 study the eigenvalues of the NTK, analyzing the impact of the choice of activation function. 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.

Published as a conference paper at ICLR 2023
CHARACTERIZING THE SPECTRUM OF THE NTK VIA A POWER SERIES EXPANSION
Michael Murray, 1 Hui Jin, 1- Benjamin Bowman, ti$ Guido Montufar
f Department of Mathematics, UCLA, CA, USA
Department of Statistics, UCLA, CA, USA
$ Max Planck Institute for Mathematics the Sciences, Leipzig, Germany
mmuurray, huijin, benbowwan montufar) @math. ucla. edu
Equal contribution
ABSTRACT
Under mild conditions on the network initialization we derive a power series ex- pansion for the Neural Tangent Kernel (NTK) of arbitrarily deep feedforward net- works 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 Her- mite coefficients leads to faster decay in the NTK coefficients and explore the role of depth. Using this series, first relate the effective rank of the NTK to the effective rank of the input-data Gram. Second, for data drawn uniformly on the sphere study the eigenvalues of the NTK, analyzing the impact of the choice of activation function. Finally, for generic data and activation functions with suf- ficiently fast Hermite coefficient decay, we derive an asymptotic upper bound on the spectrum of the NTK.
INTRODUCTION
Neural networks currently dominate modern artificial intelligence, however, despite their empiri- cal success establishing 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 overparameterized regime which precludes classical statistical learning theory (Anthony & Bartleti 2002). The persistent success of overparameteriized models tuned via non-convex optimization suggests that the relationship between the parameteriza- tion, 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 al. 2018). In the infinite width limit the opti- mization dynamics are described entirely by the NTK and the parameterization behaves like a linear model (Lee al. (2019). In this regime explicit guarantees for the optimization and generalization can be obtained (Du et al. 2019a by Arora et al. 2019a: Allen-Zhu et al., 2019: Zou et al.) 2020). 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 principled basis.
The spectrum of the NTK is fundamental to both the optimization and generalization of wide net- works. In particular, bounding the smallest eigenvalue of the NTK Gram matrix is staple tech- nique for establishing convergence guarantees for the optimization (Du et al.) [019a] b) Oymak & Soltanolkotabi 2020). Furthermore, the full spectrum the NTK Gram matrix governs the dynam- ics 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 & Montu- far 2022; Bowman & Montúfar 2022). 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 al. 2022

---

Published as a conference paper at ICLR 2023
The importance of the spectrum of the NTK has led to 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. 2016; Pennington & Worah 2017 2018 Louart et al. 2018 Karakida et al.) 2020). These results often require complex random matrix theory operate in regime where the input dimension is sent to infinity. By contrast, using just a power series expansion we are able to characterize variety of attributes of the spectrum for fixed input dimension and recover key results from prior work.
1.1 CONTRIBUTIONS
In Theorem
we derive coefficients for the power series expansion of the NTK under unit variance initialization, see Assumption Consequently we able to derive insights into the NTK spectrum, notably concerning the outlier eigenvalues as well as the asymptotic decay.
3.1
In Theorem 4.1 and Observation 4.2
we demonstrate that the largest eigenvalue λ1 (K) of the NTK proportion of the trace and that there are O(1) outlier eigenvalues of the same
takes up 22))
order as A K).
In Theorem 4.3 and Theorem 4.5
we show that the effective rank Tr(K)/Aj) (K) of the NTK is upper bounded by constant multiple of the effective rank Tr(XX") (Xx((xX)) of the input data Gram matrix for both infinite and finite width networks.
In Corollary 4.7 and Theorem 4.8 we characterize the asymptotic behavior of the NTK spectrum for both uniform and nonuniform data distributions 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 consequence, when the network is polynomially wide in the number of samples, global conver-
gence 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). (021). Furthermore, the connection between infinite width networks and
Gaussian processes, which traces back Neal (199)). has been reinvigorated in light of the NTK.
Recent investigations include [Lee et al. 201 8): 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 (0020) in the high dimensional limit. Ve- [ikanov & Yarotsky (2021) demonstrated that for ReLU networks the spectrum of the NTK integral operator asymptotically follows 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 un- der the uniform distribution, which then expanded to the nonuniform case by Basri et al.) (2020). Geifman et al. (2022) analyzed the spectrum of the conjugate kernel and NTK for convolutional net- works with ReI.U activations whose pixels are uniformly distributed on the sphere. Geifman et al. (2020) Bietti & Bach (202T); [Chn & Xul (202T) 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 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 demonstrate that any dot product kernel can be realized by the NTK or Conjugate Kernel of 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 un- der various activations. Finally, in 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 employ the Hermite expansion to charac-
2

---

Published as a conference paper at ICLR 2023
terize both the outlier and asymptotic portions of the spectrum for both shallow and deep networks under general activations.
PRELIMINARIES
For our notation, lower case letters, e.g., 2, y, denote scalars, lower bold characters, e.g., y, are for vectors, and upper case bold characters, e.g., X, Y, are for matrices. For natural numbers k1, k2 N we let [K1] (1....:Ak }1 and [K2, knj (k,,..., k1). If k2 > k1 then [k2, ki] is the empty set. We use Il-llp to denote the p-norm of the matrix or vector in question and as default use ||-I1 as the operator 2-norm respectively. We use 1mxn E Rm to denote the matrix with all entries equal to one. We define ōp=e to take the value if p c and be zero otherwise. We will frequently overload scalar functions o R + R by applying them elementwise vectors and matrices. The entry in the ith row and jth column of a matrix we access using the notation [X] The Hadamard entrywise product of two matrices X, Y R denote X Y as is standard. The pth Hadamard power we denote X and define it as the Hadamard product of X with itself times,
X O .....
XOXO...ox O.
Given a Hermitian or symmetric matrix X E Ruxn we adopt the convention that Xx(X) denotes the ith largest eigenvalue,
(X) (X)
An (X).
Finally, for square matrix X E R we let (X) Σ X is denote the trace.
2.1 HERMITE EXPANSION
We say that function : R - R is square integrable with respect to the standard Gaussian measure 722) = _ /2 if Ex~N((.1) (x < co. We denote by (?, 7) the space of all such functions. The normalized probabilist's Hermite polynomials are defined as
V2r
hu (x) (-1)* x=²2==221 d²
dak d 12
4 0, l,...
VK! and form a complete orthonormal basis in (TR, O'DDnelll 2014 $11). The Hermite ex-
pansion of function L2, 7) is given by ((z) k= My (o) (x))) where (x(Ø)
Xx=.xr..)//XXX//uxXx is the kth normalized probabilist's Hermite coefficient d.
2.2 NTK PARAMETRIZATION
In what follows, for d E N let X E Raxd denote matrix which stores n points in IR row-wise. Unless otherwise stated, we assume < n and denote the ith row X,, as x,, In this work we consider fully-connected neural networks of the form (L+1); Rd R with L. N hidden layers and linear output layer. For given input vector E Rd, the activation f(l) and preactivation g()) at each layer / [L + 1] are defined via the following recurrence relations,
g (x) = The w + mb) (x) = = (x))
g (x) ow
will ( + (0, (x) = (x)( VI [2,
(1)
Vmi-i
(x)
Ow w((+) (() (x)+1)(x)) = =g (x+
mmg
The parameters ( mm and (1) R Th are the weight matrix and bias vector at the Ith
layer respectively, mo = d, m141 = 1, and Φb R - I is the activation function applied element- wise. The variables 7wu, Twe E R20 7n, 0b E IRz0 correspond to weight and bias hyperparameters respectively. Let 0, IR denote a vector storing the network parameters (W(h), b())) )/m up to
and including the Ith layer. The Neural Tangent Kernel (Jacot al. 2018 (0) Rd Rdd + R
associated with (() at layer E [T. + 1] defined as
(x, y) == (Vo, (x),, (y)). We will mostly study the NTK under the following standard assumptions.
(2)
3

---

Published as a conference paper at ICLR 2023
Assumption 1. NTK initialization.
At initialization all network parameters are distributed as (0, 1) and are mutually independent.
The activation function satisfies (IR, 7). is differentiable almost everywhere and its deriva- tive, which we denote 6', also satisfies ø' E (R.
3. The widths are sent to infinity in sequence, m1 7 DC, m2 + OC.... mL - DC.
Under Assumption 1 for any 1 [++1 1. 60
y) converges probability to a deterministic limit (Jacot et al., 2018 and the network behaves like a kernelized linear predictor
( TR x Rd during training; see, e.g., Arooa et al. (2019b); [Lee et al.] (2019); Woodworth et al. (2020). Given access to the rows (x,)ī=1 of X the NTK matrix at layer E [ + IJ, which we denote K,, is the matrix with entries defined as
Kilas = (x),),) v(i,)) E [n] x [n].
(3)
EXPRESSING THE NTK AS A POWER SERIES
The following assumption allows us to study power series for the NTK of deep networks and with general activation functions. We remark that power series for the NTK of deep networks with positive homogeneous activation functions, namely ReLU, have been studied in prior works Han et al. 2022); Chen & Xu (2021); Bietti & Bach (021); ; Geifman et al. (2022). We further remark that while these works focus the asymptoties of the NTK spectrum also study the large eigenvalues.
Assumption 2. The hyperparameters the network satisfy nu +2 L, BzwNoo ())(()))))))))))))))))))))) S and of 1 - o(]Ez-Nro.,]002))) The data is normalized so that |xx for all [n].
Recall under Assumption 1 that the preactivations of the network are centered Gaussian processes [Nea] 1996; Lee et al., 2018). Assumption [2] ensures the preactivation of each neuron has unit variance and thus is reminiscent of the [LeCun 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 show it is possible to write the NTK not only
dot-product kernel but also [-1, and derive expressions for the coefficients. In order to state this result recall, given a function f (R, 7), that the pth normalized probabilist's Hermite coefficient of f is denoted Up((), refer the reader to Appendix [A.4 for an overview of the Hermite polynomials and their properties.
analytic power series
Furthermore, letting
(az [a denote sequence of real numbers, then for any p, k E 220
define
k 0 and p 0,
F(g,k, k,) = 0,
k = 0 and p 2 1,
(4)
Σ (GDET(A
I 4s.
A 2 1 and 2 0,
where
kp, (U:)vE) : J. 2 Ovi [k]. J: -= for all p E Zzo, k E
Here [p, k) is the set of all k-tuples of nonnegative integers which sum to p and F(p, ki a) is therefore the of all ordered products of elements of à whose indices sum p. We are now ready to state the key result of this section, Theorem 3.1 whose proof is provided in Appendix B.T
Theorem 3.1. Under Assumptions 7 and 2 for all I [ [[++1]
k Σ Kp. (XXT) OP
(S)
The series for each entry n (i]js converges absolutely and the coefficients Kp, are nonnegative and can be evaluated using the recurrence relationships
8p=00 + 6p=
1= 1,
Kp.1
ap.l + Σg 1
LE [2, L+
(6)
4

---

Published as a conference paper at ICLR 2023
where
o (u + 60-00%
1= 2,
Opp
Ek=o k= ak F(, a1-))
123,
and
o Qullige')
1= 2,
Up.1 Ek=o Uk F k 01-1),
(8)
1 2
are likewise nonnegative for all p E Z20 and [2. L +
As already remarked, power series for the NTK have been studied in previous works, however, the best of our knowledge Theorem 3.1 i. the first to explicitly express the coefficients at layer in terms of the coefficients of previous layers. To compute the coefficients of the NTK as per Theorem 3.1 the Hermite coefficients of both ø and o' are required. Under Assumption 3 below, which has minimal impact the generality of results, this calculation can be simpliñed. In short, under Assumption Pp. = (p + p and therefore only the Hermite coefficients of á are required. We refer the reader to Lemma B.3 Appendix B.2 for further details.
Assumption 3. The activation function o: IR - R is absolutely continuous on [-a, a) for all O. differentiable almost everywhere, and is polynomially bounded, i.e, (Ø(x) O(xx])) for some B > 0. Further, the derivative d': R + R satisfies ø' E LL., 7).
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 hidden layers. From Theorem 3.1
Kp. = oe PD) (1
(1 60=00
(9)
As per Table [. general trend we observe across all activation functions is that the first few coeffi- cients account for the large majority of the total NTK coefficient series.
Table 1: Percentage of Ep=o k accounted for by the first T NTK coefficients assuming
7/ 1, 2 = of and of = [[)(
T=
0
ReLU
43.944
77.277
99.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 ReLÚ, Tanh and Gaussian 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 o² as wa (2) == (1/V2ma²²) exp (-=²/(2o²)) Lemma 3.2. Under Assumptions
[and
1. if ((z)= = (2), then Kp.2 = (()))))U(ppa) Opp -3/2),
2. ((2) = Tanh(z), then Kp,2 = O (exp I x/p-11
3. (2) Wa (2),, then Kp.2 O( even) Opp 12 1)-
The trend we observe from Lemma 3.2 is that activation functions whose Hermite coefficients decay quickly, such as W. result in faster decay of the NTK coefficients. We remark that analyzing the rates of decay for > 3 is challenging due the calculation of F(p, k. āI-1) (4). In Appendix B.4 we provide preliminary results this direction, upper bounding, in a very specific setting, the decay of the NTK coefficients for depths > 2. Finally, we briefly pause here highlight the potential for
5

---

Published as a conference paper at ICLR 2023
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 somewhat different set of assumptions[] As per our observations thus far that the coefficients of the NTK power series 55) typically decay quite rapidly,
might consider approximating + by computing just the first few terms in each series of (5). Figure 2 Appendix B.3 displays the absolute error between the truncated ReLU NTK and the analytical expression for the ReLU NTK, which is also defined Appendix [B.3 Letting denote the input correlation then the key takeaway that while for |pl close one the approximation is poor, for le| 0.5, which arguably more realistic for real-world data, with just 50 coefficients machine level precision can be achieved. We refer the interested reader Appendix [3. for proper discussion.
ANALYZING THE SPECTRUM OF THE NTK VIA ITS POWER SERIES
In this section, we consider a general kernel matrix power series of the form nk E Go (XX+) where {cp]p=u coefficients and X is the data matrix. According to Theo- rem 3.1 the coefficients of the NTK power series (5) are always nonnegative, thus we only consider case where Ep are nonnegative. We will also consider the kernel function power series, which we denote as K (2) = Ep=0 Cp (21, Later on we will analyze the spectrum of kernel matrix 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 A Raxx we define the effective rank of to be
Tr(A)
cff(A)
(A)
The effective rank quantifies how many eigenvalues are on the order of the largest eigenvalue. This follows from the Markov-like inequality
Kp: Ap 2 cA)( Scfef(A)
(10)
and the eigenvalue bound
(A) S eff(A)
(A)
Our first result is that the effective rank of the NTK can be bounded in terms of ratio involving the power series coefficients. As are assuming the data normalized that ||,||| for all i [n),, then observe by the linearity of the trace
Tr(nK) = Σ CTTrr((XX (XX =n
Cp
p=0
p=0
where we have used the fact that (eT((XXX))XX
all E N. On the other hand,
X1 (n (c (xx = (c nCg-
Combining these two results we get the following theorem.
Theorem 4.1. Assume that we have a kernel Gram matrix K of the form n. = Ep-o c (XX² where * O. Furthermore, assume the input data x; are normalized so that ||x:|| = 1 for all i [n]. Then
Eg-
eff(K) <
'In particular, in Han et al. 2222)) 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 con-homogeneous activation functions in the deep setting.

---

Published as a conference paper at ICLR 2023
By Theorem 3.1 Co f provided the network has biases the activation function has nonzero Gaussian expectation (i.e., (0) * 0). Thus we have that the effective rank of K bounded by an O(1) quantity. In the case of ReLU for example, evidenced by Table [ 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 (n)). Combining Theorem 4.1 and the Markov-type bound (T0) we make the following important observation.
Observation 4.2. The largest eigenvalue X (K) of the NTK takes up an (1(1) fraction of the entire trace and there are (11) eigenvalues on the same order of magnitude as X (K), where the O(1) and S2(1) notation are with respect to the parameter n.
While the constant term colnxn in the kernel leads to significant outlier in the spectrum of K, it rather uninformative beyond this. What interests us is how the structure of the data X manifests in the spectrum of the kernel matrix K. For this reason will examine the centered kernel matrix K =
Eo Lnxn. By a very similar argument as before we get the following result.
n
Theorem 4.3. Assume that we have a kernel Gram matrix K of the form nK = Ep=o Cp (xX"))OOp
where + O. Furthermore, assume the input data X; are normalized so that |Xxi|| = 1 for all i e [n]. Then the centered kernel K == K 50 Inxn satisfies
2p=1 Cp
eff eff(K) S efx
Thus we have that the effective rank of the centered kernel K is upper bounded by a constant multiple of the effective rank of the input data Gram XXT. Furthermore, we can take the ratio 2p=1 9 as a measure of how much the NTK inherits the behavior of the linear kernel XX*; in particular, 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 I 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.3we we make the important observation.
Observation 4.4. Whenever the input data are approximately low rank, the centered kernel matrix K- K Go nxn is also approximately low rank.
turns that this phenomenon also holds for finite-width networks at initialization. Consider the shallow model
m Σ
aao((Wws, x));
where x E Rdd and wy E Rd, E IR for all l E [m]. The following theorem demonstrates that when the width is linear in the number of samples then eff(K) is upper bounded by a constant multiple of eff (XXT).
Theorem 4.S. Assume ((x) = (x) and n 2 Fix e > 0 small. Suppose that Wi,...y Wm N (0, vî La) i..dd and ......, am v2). Set M maxie[m] [x and let
Σ N (XW)) (Xw) x²)
Then
m Ω (max(A) (2)
= O(1/M)m
suffices to ensure that, with probability least 1 1-c over the sampling of the parameter initialization,
eff < eff((x"")
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. (2019)). Du et al. (2019b). Oymak et al. (2019). Li et al. (2020), Oymak reduce the dependence the number of samples n. and we have an accompanying lower bound. See Theorem C.5 in the Appendix C.2.3 details.
Soltanolkotabi only be logarithmic in
(2020). In this setting
the width

---

Published as a conference paper at ICLR 2023
In Figure 1 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 functorch 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 dominant outlier eigenvalue due 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.I Additionally, this outlier is most pronounced for ReLU, as the combination of its Gaussian mean plus bias term is the largest out of the activa- tions 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 spec- trum of the NTK being skewed. By contrast, isotropic Gaussian data has 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 well approximated by the identity. Our theory provides 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 kernel method (and hence the NTK model) within parameter ball is determined by its its trace (Bartlett & Mendelson 2002). Since for the NTK A (K) = (11), lower effective rank implies smaller trace and hence limited complexity.
NTK Spectrum: Caltech101. Depth-2
NTK Spectrum: Gaussian Data, Depthr2
Activation
Normatzed Magritude
tart
107
10
NTK Caltech101. Depthe5
NTK Depthen
10
Normaized Magnitude
10"
10
20
80
80 100
0
20
60 Eigenvalue Index
40
80
100
Eigenvalue Index
Figure 1: (Feedforward NTK Spectrum) We plot the normalized eigenvalues Ap/Ar of the NTK Gram matrix K and the data Gram matrix XX" for Caltech101 and isotropic Gaussian datasets. To compute the NTK randomly initialize feedforward networks of depths 2 and 5 with width 500. We use the standard parameterization and Pytorch's hss default Kaiming uniform initialization order to better connect our results with what is used in practice. We consider batch size of 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 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 an- alyze the kernel function K which we recall is dot-product kernel of the form K(x1, x2) Ep (11, P. Assuming the training data is uniformly distributed on hypersphere it was shown by Basri et al. (2019) Bietti & Mairal (0199 that the cigenfunctions of K are the spherical
hhtp:///woocaaannnncccocclleeeeo tangent kernels.hml
8

---

Published as a conference paper at ICLR 2023
harmonics. Azevedo & Menegatto (2015) gave the eigenvalues of the kernel K in terms of the power series coefficients.
Theorem 4.6. [Azevedo Menegatto (2015) Let I denote the gamma function. Suppose that the training data are uniformly sampled from the unil hypersphere St d 2 2. If the dot-product kernel function has the expansion K (21, x2) =p= Cplr1, x2) where cp 0, then the eigenvalue of every spherical harmonic of frequency k given by
4//2
T(p + 1 2
A
Cp T(p - k+ - s+1 +k +k+
P2R
p- iie
A proof of Theorem 4.6 is provided in Appendix C.4 for the reader's convenience. This theorem connects the coefficients Cp of the kernel power series with the eigenvalues Åu the kernel. In particular, given a specific decay rate for the coefficients Cp one may derive the decay rate of Λg: for example. Scetbon & Harchaoui (2021) examined the decay rate of d if cp admits a polynomial de- cay or exponential decay. The following Corollary summarizes the decay rates of Å corresponding to two layer networks with different activations.
Corollary 4.7. Under the same setting as in Theorem 4.6
1. if cp Opp where 2 then d 0(k-d-200 20+2)
2. if = 6ip mun) Opp ") then TE = 5(k eve) dd 2ka2)22)+2)
3. cp O (exp (-ayp)), then To O (K-d+1122 exp (-avk)
4. c, 0(p2/2a then Ave O -Ok (k-d+1a-t and No Ω 1/-d/2+12222 -k.)
In addition to recovering existing results for ReLU networks Basri et al. 2019); Velikanov & Yarot-
sky (202I): Geifman et al. (2020); Bietti & Bach (202I). Corollary /4. also provides the decay rates for two-layer networks with Tanh and Gaussian activations. As faster eigenvalue decay implies a smaller RKHS Corollary 4.7 shows using ReLU results in a larger RKHS relative to Tanh or Gaus- sian activations. Numerics for Corollary 4.7 4 are provided in Figure g in Appendix C.3 Finally, in
Theorem 4.8 we relate a kernel's power series to its spectral decay for arbitrary data distributions. Theorem 4.8 (Informal). Let the rows of X Raxd be arbitrary points the unit sphere. Consider the kernel matrix nK Epro Cp (XX²)
&o and r(n) S d denote the runk of XXT. Then
1. c = O(p ") with > r(n) + for all n E Zzo then (K)] =0 0
P(m)
a-1
2. cf = -vV) then X, (K) = On कगंा exp (-a'n )) for any a' < a2 (22-1/2(())
(K)= = O (exp (-o'nrrrs) for any a' a2-1/2r10
3. cp (pp then (K)
Although the presence of the factor 1/r(n) in the exponents of in these bounds is weakness, T. illustrates how, in a highly general setting, the asymptotic decay of the coefficients of the power series ensures certain asymptotic decay in the eigenvalues of the kernel matrix. A formal version this result is provided Appendix C.5 along with further discussion.
5 CONCLUSION
Using a power series expansion we derived number of insights into both the outliers as well as the asymptotic decay of the spectrum of the NTK, in particular highlighting the role of the activation function. We performed our analysis without recourse to a high dimensional limit or the use of random matrix theory. Interesting avenues for future work include better analyzing the role of depth as well as characterizing the outlier eigenvalues and spectrum as a whole for networks with convolutional, residual or transformer layers.
9

---

Published as a conference paper at ICLR 2023
Acknowledgements and Disclosure of Funding: 757983 and NSF CAREER Grant DMS- MM5-21
This project has been supported by ERC Grant
Reproducibility Statement: To ensure reproducibility, we make the code public at https:// github. cwt.bbowwann233// data battkttkkk
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. 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
pettss:/prroest ingeeediigg.. ngs. ml www.lr.ress//ee v97 /7/9////22 aelnn z zhul
19.mtml
Martin Anthony and Peter L. Bartlett. Neural Network Learning Theoretical Foundations. Cam- bridge University Press, 2002. URL http::/t//// /ttp::///wwww./ www. cambridge. wtt/ hebb/kowwleder
locale=en GB
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Ma- chine Learning Research, pp. 322-332. PMLR, 2019a. httpt::tp///ptee
ngs. mllr.
press/v97 aroral html
Sanjeev Arora. Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ru- osong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019b. URL bttpp:://proceediogs... neurips occppaper/211//EIee htt.c//eeeeebbebeeeeooeeeaeeeeee
pdf
Douglas Azevedo and Valdir A Menegatto. Higenvalues of dot-product kernels the sphere. Pro- ceeding Series of the Brazilian Society of Commutationall and Applied Mathematics, 3(1), 2015.
Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3:463 2002. URL httt::/: wirietrrrr.uiiiteerrr....
de/ de/db/journal
/mlr/ jml r html #Bart1ettM02
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-4773 2019. URL
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 htttt:::/pppceeeeeeeeeeee wig. ngs mll. wtt.sss....ppp..l111.. press/v119/ basri20a. html
Alberto Bietti and Francis Bach. Deep equals shallow for ReLU networks in kernel regimes. In International Conference on Learning Representations, 2021. URL /ttp::ttt/:/ooeeeeiiee
net/ Fodd joksTpXOP
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. In Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates. Inc., 2019. URL https::/proccediaggs... www.eeuwiiss..ppappee//o... cctppapper/211///ileee
Benjamin Bowman and Guido Montúfar. Implicit bias of MSE gradient optimization in underpa- rameterized neural networks. In International Conference on Learning Representations, 2022.
10

---

Published as a conference paper at ICLR 2023
Benjamin Bowman and Guido Montufar. Spectral bias outside the training set for deep networks in the kernel regime. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https: hattps://ppereeviee /openrevie...
net/forum? i a= P1.2gb775
Andrea Caponnetto and Emesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
Lin Chen and Sheng Xu. Deep neural tangent kernel and laplace kernel have the same RKHS. In International Conference on Learning Representations, 2021. URL /R//ttsss//opeereeeeee
net/ ttr:://rummuii//e www.ruumidwwkww22eee
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kemel regression: The crossover from the noiseless to noisy regime. In Advances Neural In- formation Processing Systems, 2021. (tI.ht/ts:// bttt:s:///ppereeee /wtp///eeeeeeeeeeeeee ew. net. forum? d=Da
EHrActwd
Amit Daniely, Roy Frostig, and Yoram Singer.
Toward deeper understanding of neu- ral networks: The power of initialization and dual view on expressivity. In Ad- vances Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
URL /ttpsss/prroeeddnng....ee new.iipgss..e..ss...e...... cc/papper/216//ilee abead (et.12222ee166ddff22224444244400 Paper.
Tom Davis. A
general
expression for Hermite expansions with applica- doi: 00133440RG.222238444442222.
tions. 2021.
URL https://
www. www.ereeeeaaaaaee hww.
ication/
352374514
WITH
GENERAL SEEERAL-EXPRESEEEE EXPRESS FOR HERESSIIOOOOORRRMMITEITT HERMITE-EXPASIIOO WITH
-IP.AAPLIAATTOOOOOO APPLICATIONS.
pdf
Alexander G. de Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahra- mani. Gaussian process behaviour in wide deep neural networks. In International Confer- ence on Leurning Representations, 2018. URL http:s://openreviii net/ forum?ide
H1 11-nGgWC--
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 1675-1685. PMLR, 2019a. URL /
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes wwer-parameterized neural networks. In International Conference on Learning Representations, 2019b. URL htttts:://ppereeiieeeee wwt.:neeeooommmmmmmmemmmee...
Andrew Engel, Zhichao Wang, Anand Sarwate, Sutanay Choudhury, and Tony Chiang. TorchNTK: A library for calculation of neural tangent kernels of Py models. 2022.
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: //tpee/iinoo/o/ooo///ooo. itw.:eeeeddiiig...eeeeeeee.eeeee wnwurips........ cc/ Papo://00//ELee/5222244444
G. B. Folland. Real analysis: Modern techniques and their applications. Wiley, New York, 1999.
Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Basri Ro- nen. On the similarity between the Laplace and neural tangent kernels. In Ad- vances in Neural Information Processing Systems, volume 33, pp. 1451-1461. Curran Asso- ciates, Inc., 2020. URL httpppsss//ppcccciissss.... newripss...s...............iii.. httpprxwpps..ccppppp///////////e 1006ff1 100
8

---

Published as a conference paper at ICLR 2023
Amnon Geifman, Meirav Galun, David Jacobs, and Ronen Basri. On the spectral bias of convo- lutional neural tangent and gaussian process kernels. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
URL wtt.tttpps:.. htttps://oppnrevieeee
net foor/ www.rooormmnnnnonooeeeooooeee dwgthhhzymmmyyy.
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. Bttppttps///rrrcedding mll: www.s//ssssp..... pppess/vv/cee http://///llllroo glorot 1 10a Da. html
Insu Han, Amir Zandich, Jachoon 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: /ttps///eeeeeeeeeeeeeeee net. http://wwwweeee/onttteet.e forum SosorrumiidyyyylIIli
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.
Ningyuan Teresa Huang, David W. Hogg, and Soledad Villar. Dimensionality reduction, regular- ization, and generalization in overparameterized regressions. SIAM J. Math. Data Sci., 4(1): 126-152, 2022. htttts:tt::///t
100 1137/20m 1378821111111
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: http::s:s///cceeeedeee ngs neurips....... cc/
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 URL httpttts///peeeeeiiiss/ htt.pp/www....a...ee.oooooooaaaa
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:: /tt:://ooi..o oec.h.org/11.. 10..0..108111110 142 5468/ abc62e
Donat K. Kazarinoff. On Wallis' formula. Edinburgh Mathematical Notes, 40:19-21, 1956.
Yann A. LeCun, Léon Bottou, Genevieve B. Orr, and Klaus-Robert Müller. Efficient BackProp, pp. 48. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. URL 10C7/978 3- 002---42222------ 35289-8
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S. Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as Gaussian processes. In International Confer- ence on Learning Representations, 2018. URL
net/ forum?id
BlEA M- 02
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. In Advances in Neural Information Processing Systems, volume 32, Cur- ran Associates, Inc., 2019. URL https: httt::::/pppccceinnnstt
Jaehoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: empirical study, In Ad- vances Neural Information Processing Systems, volume 33, pp. 15156-15172. Curran Asso- ciates, Inc., 2020. URL /ttppppse/ppppeeias......oooss.. 2a0GF999EEeee11100022222222222:0
Li, Andreeto, Ranzato, and Perona. Caltech 101, Apr 2022.
12

---

Published as a conference paper at ICLR 2023
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 Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 4313-4324. PMLR, 2020. URL https://
proceedi ngg ml wrwss/esssvvv..... w0///vv0////// 1120j html]
Cosme Louart, Zhenyu Liao, and Romain Couillet. A random matrix approach to neural networks.
The Annals of Applied Probability, 28(2):1190-1244 2018. URL https::///// www jstor.
org/stab stabbe//6b642333
Dmytro Mishkin and Jiri Matas, All you need a good init. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, Conference Truck Proceedings, 2016. http:
org/abs/ 1111106422
M. Murray, Abrol, and J. Tanner. Activation function design for deep networks: lin- earity and effective initialisation. Applied and Computational Harmonic Analysis, 59:117- 154. 2022. URL https::/wwe
reiencedirret. com/ science/article/pa S1 0163520322001111 Special Issue on Harmonic Analysis and Machine Learning.
Radford M. Neal. Bayesian Learning for Neural Networks. Springer-Verlag. Berlin, Heidelberg. 1996.
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. https::/proceedding hww.p/nss............e...e..eeee
PMLR, 2021. URL
mlr ppwss//seeee..........c
htmll
Quynh Nguyen and Marco Mondelli. Global convergence deep networks with one wide layer fol- lowed by pyramidal topology. In Advances in Neural Information Processing Systems, volume 33, pp. 11961-11972. Curran Associates, Inc., 2020. URL htttttss:/ppocceediiinn wtw.:eeeeeeeinn....ii....e. neurips. pdf
Quynh Nguyen, Marco Mondelli, and Guido Montúfar. Tight bounds the smallest eigenvalue of the neural tangent kernel for deep ReLU networks. In Proceedings of the 38th Interna- tional Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Re- search, pp. 8119-8129. PMLR, 2021. URL WtRLhttps:// http://ooooeenngg......l o wtt..ngss........s1/1113..3 nguyen21g. html
Roman Novak, Lechao Xiao, Yasaman Bahri, Jaehoon Lee, Greg Yang, Jiri Hron, Daniel A. Abo- lafia, 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: http///ppneei....eeo/eeeeeeoe.ep net wwwp://eefffrmmioooommo
/
B1 B1g30j0qF7
Roman Novak, Jascha Sohl-Dickstein, and Samuel Schoenholz. Fast finite width 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. 17018-17044 PMLR, 17-23 Jul 2022. URL htttps://procett ngs. wwg..m.......................mm. wwppssss/vvr wtt../eprssss//eeeeeeaeeeee w2wl////oooa22.aaammmmmmm
Ryan O' D'Donelll. Analysis of Boolean
Boolean,functions functions. Cambridge University Press, 2014.
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameterizaatoo:: Global con- vergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1), 2020. URL httpt::t:////...t htt.tppss/.pr......ooo////////// /t4e.ogo///bbl11100200099
Samet Oymak, Zalan Fabian, Mingchen Li, and Mahdi Soltanolkotabi. Generalization guarantees for neural networks via hamnessing the low-rank structure of the Jacobian. CoRR, abs/1906.05392, 2019. htRLttt:://aee
abs 1906 0000../9921332322922
Abhishek Panigrahi, Abhishek Shetty, and Navin Goyal. Effect of activation functions on the train- ing of overparametrized neural nets. In International Conference on Learning Representations, 2020. URL URL htt.httsss///oeeeiiieeee net. wwwpeeeeeweeeeeeeeeeeeeeeeeeeeee httt://orrumm.okkkkkffeoeoeee
13

---

Published as a conference paper at ICLR 2023
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.
Jeffrey Pennington and Pratik Worah. Nonlinear random matrix theory for deep learn- ing. In Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL hot.ol/eeeedddbbbbbbbeceeeeeeed
Paper.
Jeffrey Pennington and Pratik Worah. The spectrum of the Fisher information matrix of single- hidden-layer neural network. In Advances in Neural Information Processing Systems, vol- ume 31. Curran Associates, Inc., 2018. URL httpp:://pppcceeeeeeteec ngs. neurips cc/
Ben Poole. Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Gan- guli. Exponential expressivity in deep neural networks through transient chaos. In Advances in Neural Information Processing Systems, volume 29. Curran Asso- ciates, Inc., 2016. URL
neurpp.p....g................... httpps.cc/ppe wttps/.appppe///1////1.. 145100811456726eeccc554555521352 Paper.. pdf
Meyer Scetbon and Zaid Harchaoui. A spectral analysis of dot-product kernels. In International conference on artificial intelligence and statistics, pp. 3394-349000 3402. PMLR, 2021.
Samuel S. Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein. Deep informa- tion propagation. International Conference on Learning Representations (ICLR), 2017. URL https://openreviin net pttp
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://euddm. or..
James Benjamin Simon, Sajant Anand, and Mike Deweese. Reverse engineering the neural tangent kernel. In Kamalika Chaudhuri, Stefanie Jegelka, Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 2020111222222 PMIR, 17-23 Jul http://oooeeeein..........eeeeee
2022. URL https/////p.ceeesg..o.... mlr www. wwt.:r/essseeeeeeeeeeeeeeeeeeeee wwwp://t......a.....m html
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.
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 httpppp::/p/cceeaaaaaaaee www..iin...........o............ ce/ 22ap:///D0///L1/224466622222B2.B
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices, pp- 210-268.
Cambridge University Press, 2012.
Hermann Weyl. Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differen- tialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumsttahlungg) Mathematische Annalen, 44(4):441-479 1912. httptt /tw////oiiiii wwwp:...o....................... 1007/B1 000000///E00446660 01456804
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.
PMLR, 2020. URL https: /tL/httpp:///rcceddnnss http:///eocceenn.... mlr. A.r.peessvll2//ee httpssss/ww///oooooorrtt/00 html
14

---

Published as a conference paper at ICLR 2023
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, vol- ume 54 of Proceedings Machine Learning Research, pp. 1216-1224. PMLR, 2017. URL ngs. m wrw.sssss.....rsse.m.m. press /
html
Greg Yang and Hadi Salman. A fine-grained spectral perspective on neural networks, 2019. URL
attps://arxian org/ abs/ 1907 10599
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 Asso- ciates, Inc., 2019, URL /ttpp::/pproceeddngg.....
pdf
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over-
parameterized deep ReLU networks. Machine learning, 109(3)467--922, 2020.
15

---

Published as a conference paper at ICLR 2023
APPENDIX
The appendix is organized as follows.
Appendix A gives background material on Gaussan kernels, NTK, unit variance intitialization, and Hermite polynomial expansions.
Appendix provides details for Section
Appendix provides details for Section
A BACKGROUND MATERIAL
A.1 GAUSSIAN KERNEL
Observe by construction that the flattened collection of preactivations the first layer (g (x:)) form a centered Gaussian process, with the covariance between the ath and 9th neuron being de- scribed by E
(xi, x,) Bigh" (x: )93 (1) (x,)] - m ( xj + +88
Under the Assumption the preactivations at each layer / 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 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 Matthews 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 ath and 8th neurons at layer / 2 2 for any mput pair x, IR are described by the following kernel,
[ aas
y) = Elga ( (x)gg (1) (y))
= = (02_ (x)))() (t- ">))) +
(x)))(
We refer this kernel as the Gaussian kernel. As each neuron is identically distributed and the covariance between pairs of neurons is 0 unless a 8, 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 bivariate Gaussian distribution, whose covariance matrix has three distinct entries: the variance of a preactivation of x at the previous layer, ()- (x,x), x), the variance of preactivation of at the previous layer, E covariance between preactivations of x and y, ((-1)) (x,y). Therefore the Gaussian kernel, or covariance function, and its derivative, which we will require later for our analysis of the NTK, can
(y, y), and the
be computed via the the following recurrence relations, see for instance (L.ee et al. 2018 2018 AAroa et al. 2019h Nguyen al.) 2021).
Jacot et al.,
(x,)) 1xx + 73. [2)11)((xx))
-1-1)
A 10 (x.y)) E (y,x)
1) (x,x)
(1I)
(00 (x,,) y)
(o(
+
(xx (B.
16' (B (B2))
A.2 NEURAL TANGENT KERNEL (NTK)
As discussed in the Section under Assumption converges in probability to a deterministic limit, which we denote ( This deterministic limit kernel can be expressed in terms of the Gaus- sian kemels and their derivatives from Section A.1 via the following recurrence relationships (Jacot
16

---

Published as a conference paper at ICLR 2023
al.
2018
Theorem 1),
e (xxy) (x,)) = (x.)), y),
1 (x, 0 (x, (x,,) + (x,))
(12)
=I Σ (x,))
II W=++1
(x))(x))) We 2,
A useful expression for the NTK matrix, which is a straightforward extension and generalization of Nguyen al. (2021 Lemma 3.1), is provided in Lemma below.
Lemma A.1. (Based on Nguyen al. 2027 Lemma 3.1) Under Assumption ] sequence positive
semidefinite matrices (Gi) in R=x", and the related sequence (Gt) also in R=*x" can be constructed via the following recurrence relationships,
G T XXx" IbInn
22 = a² = w. (oW. (x(w) 7 + of Ixni
G2 = Ew (''))''
(13)
G: = 2 Ew GG///GGWWWW/ /G--w aaxn E [3, L + 1],
G o "w (0 (d G G E [3, T. +1.
The sequence of NTK matrices tionship,
(K [ can in turn be written using the following recurrence rela-
n G1:
mK; G. + nKK @ Gr
(14)
G Σ G
Go)=+))))
Proof. For the sequence (=) it suffices to prove for any i,j [ri] and / E [L that
[Glli = ( (x,
and G is positive semi-definite. We proceed by induction, considering the base case / 1 and comparing 13 with I1) then it is evident that
[Giba (x)(,,)))))))))) xj).
In addition, G, also clearly positive semi-definite for any u E R.
n n = |XT 1
1
2
2 0.
We now assume the induction hypothesis is true for G We will need to distinguish slightly between two cases, - and ( E L 1]. The proof of the induction step in either case is identical. To this end, and for notational ease, let V X, ~ N00 Ia) when = 2, and 1]. In either case we let v, denote the ith row of V.
V = G ~ \0 I,) for E [3, L +
For any i.j E [m]
Giiy = E ( ( w )o( w)] t.
Now let Bj v.T. B2 = v/ w and observe for any 01 02 R that o1 Bi +az Car +
a2Ugk)Wu ~ \O0,, + 11)) Therefore the joint distribution of (B1, B2) is mean bivariate normal distribution. Denoting the covariance matrix of this distribution as A E R22x2 then [Gily can be expressed as
[iiyy o 2 L.B. (o (B)) +o
17

---

Published as a conference paper at ICLR 2023
To prove [Gr]a, Σ it therefore suffices to show that À = A as per (11). This follows by the induction hypothesis as
E[B = v? v; = GG = -0 (x,, xz):
E[B vI v [G-ilgs = E1111)
11 (xj, xj),
E B2] vTv, = =G = E(111) (x,: x,).
Finally, G2 is positive semi-definite as long as (ol Vw) is positive semi-definite. Let M(w) ((Vw) E Rax" and observe for any that M(w) (w) is positive semi-definite Therefore Ew [M (W)MM()) must also be positive semi-definite. Thus the inductive step is com- plete and we may conclude for / E [L. + 1] that
[Gilas 0 (xi, Xj).
(15)
For the proof of the expression for the sequence (2) it suffices prove for any i, E [n]] and
I E [L
that
[Gila] Σ (x)
By comparing
13 with IT] this follows immediately from (55) Therefore with
1
proven (4)
follows from
A.3 UNIT VARIANCE INITIALIZATION
The initialization scheme for a neural network, particularly deep neural network, needs to be designed with some care in order to avoid either vanishing or exploding gradients during training Glorot & Bengio (010);; He al. (2015); Mishkin & Matas (2016); LeCun al. (2012). Some of the most popular initialization strategies used in practice today, in particular LeCun et al. (2012) and Glorot & Bengio (010) initialization, first model the preactivations of the network Gaussian random variables and then select the network hyperparameters in order that the variance of these idealized preactivations is fixed at one. Under Assumption this idealized model the preactiva- tions is actually realized and if we additionally assume the conditions of Assumption 2 hold then likewise the variance of the preactivations every layer will be fixed at one. To this end, and in Poole et al. (2016); Murray et al. 2022). consider the function V: Rzu - R>0 defined as
V(4) E2~N( ④ (v92)²
+ o
(16)
Noting that V is another expression for x (x, x). derived via change of variables per Poole et al. 2016), the sequence of variances (Σ (x, x) 2 can therefore be generated as follows,
Σ00 (x,x) x) (x,)))
(17)
The linear correlation (()) Rd x d |-, 1] between the preactivations of two inputs x, Rd we define as
(0 (x.
1 (x, (x. = VEO (x, x) x))(0)y))))))
(18)
Assuming (x, x) 500 (y, y) = for all E [L + 1). then p 00 (x,y) (x((xx))))))) (x, Again as in Murray et al. (2022) and analogous to (6)), with Z1, Zz ~V 1) independent, U1 = Z,,
U2(p) == (pZz + 1 11-p²Zg) we define the correlation function R: [-1, 1] + [-1, as
R(p)
+
(19)
Noting under these assumptions that R is equivalent to (x,,), the sequence of correlations (x() x)) can thus be generated as
(x,y) = R(p ().
As observed in Poole et al. 2016); Schoenholz et al. 2017). R(1) = V(1) = 1, hence p = 1 is a fixed point of R. We remark that all preactivations are distributed (0 1). then correlation
We remark that U1, U2 dependent and identically distributed as U2 N/(0, 1).
18

---

Published as a conference paper at ICLR 2023
of one between preactivations implies they equal. The stability of the fixed point p is of particular significance in the context of initializing deep neural networks successfully. Under mild conditions the activation function
compute the derivative of R, see e.g., Poole et al.
2022), as follows, (016); Schoenholz et al. (2017): Murray et al.
R'(p) の E (U1) (U2()))
(20)
Observe that the expression for ( and R' are equivalent via change of variables (Poole et al. 2016), and therefore the sequence of correlation derivatives may be computed as
500 (x, = (e(p (),
With the relevant background material now in place we are in position to prove Lemma A.2 Lemma A.2. Under Assumptions and and defining X = Ni (()) E Eso, then for
all i.j [n]. [L 1]
[Gn,lly [-1,1] and iGn, = 1,
. [Gr,l E [-xx and [Gn,tjis X-
Furthermore, the NTK is dot product kernel, meaning ( (x) can be written as function of the inner product between the two imputs, O(x) xz)-
Proof. Recall from Lemma A. and its proof that for any E + + 11. i,j E [n]] [Gn,les g0 X;, X5) and [Gn,lli = 50 x)). We first prove by induction E (x;,x,) 1 for all
E [L + 1]. The base case / follows as
E x) = 7 xxxxxxxxxxx + 78 = Ter + g
Assume the induction hypothesis is true for layer 1 1. With Z ~ NO, 1), then from 16 and 17
x xx = V(Σ (x,x)
= = 6²
(V20-11 (x, x)2
+ +o²
= L [o² (Z)] + o
1,
thus the inductive step complete. As an immediate consequence it follows that [Gi]a: 1. Also, for any i,j [n] and ( E [L 1].
(x,, x,) (x,,,
= R(...
Thus consider (0)) and also conclude that [Grly E [-1, Furthermore,
univariate function of the input correlation Σ [-1,1] + [-11]]
50" (x,, x,) = R²' (2 (x,, x,)) = R((((..
which likewise implies is dot product kernel. Recall now the random variables introduced to
define R: Z1, 7/2 ~ (0, 1) are independent and U1 Z1. U2 (p71 + v1 p² 72). Observe
U1. U2 are dependent but identically distributed as U1, U2 (). For any p E [-1, 1] then applying the Cauchy-Schwarz Schwarz inequality gives
(R(()) of (U:)) (U2))) Eld' (EE))(U,)) (U)))) (U)))
- (1) (1)
As result, under the assumptions of the lemma 100 [-1,1] + [-x.x] and 1000 (x, x,) = X- From this immediately follows that [Gr]ey E [-x,x] and [Gr]a = x as claimed. Finally, as : + [- and E [- > [-x: are dot product kernels, then from 12 the NTK must also be dot product kernel and furthermore univariate function of the pairwise correlation of its input arguments.
The following corollary, which follows immediately from Lemma A.2 and 14 trace of the NTK matrix in terms of the trace of the input gram.
characterizes the Corollary A.3. Under the same conditions Lemma A.2 suppose o and o are chosen such that = 1. Then
(r(Kn.)) -.
(21)
19

---

Published as a conference paper at ICLR 2023
A.4 HERMITE EXPANSIONS
We say that function f R + R is square integrable w.r.t the standard Gaussian measure
e-x² 2v22 if Ez=NN(,,))f(zz < We denote by L L2,,,, 7) the space of all such functions. The probabilist's Hermite polynomials are given by
de dz d
=x(=)((11)) o=
-0 0212 k- k= 0,1
The first three Hermite polynomials are Ho(x) 1, H1(x) = H2(2) (x² 1). Let
hx(2)) Hx(x) denote the normalized probabilist's ' Hermite polynomials. The normalized Hermite
vk!
polynomials form complete orthonormal basis in (2, 7) (ODDnneell 2014 $11): in all that follows, whenever we reference the Hermite polynomials. we will be referring to the normalized
Henmite polynomials. The Hermite expansion of function ø L L2, 7) is given by
<(x) Σ mm(o))(())
(22)
where
(x) = Ex~N((o (o.
(23)
the kith normalized probabilist's Hermite coefficient of Φb In what follows we shall make of the following identities.
Vk 2 1, Mx(x)) = Vkha-1(z))
(24)
Vk > 1, xhh(z)= vk + 1h)+1(x) + (k).
(25)
if is odd if is even
h0) =
(-1) 1)!!
vkl
1,
k < 0
(26)
where k!!!
k. (k 2.... 1,
k > 0 odd
k: (k
- 2...-....442
k > 0 even
We also remark that the more commonly encountered physicist's Hermite polynomials, which we denote HE, are related to the normalized probablist's polynomials as follows.
k/2 2/ (2/V22)
hx(z)
Vk!
The Hermite expansion of the activation function deployed will play key role in determining the coefficients of the NTK power series. particular, the Hermite coefficients of ReLU are as follows.
Lemma A.4. Daniely et al. (0066) For ((2) max(0, 2} the Hermite coefficients are given by
1/V2iT
k 0. h: =
1/2,
(x(
(27)
(I: - (k33)!!/mmm 2TTk
1: even and k 2 2, k odd and k > 3.
0,
B EXPRESSING THE NTK AS POWER SERIES
B. DERIVING POWER SERIES FOR 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 Oymak & Soltanolkotabi 2020 Lemma H.2).
20

---

Published as a conference paper at ICLR 2023
Lemma B.1. For arbitrary n, d N. ler A Raxd For E [n]. denote the ith row of A a. and further assume that ||as] = Ler R satisfy & (R, 7) and define
M = E (O..)
Then the matrix series
K SK = Σ k=
(2( (AA7) OF
converges uniformly to M as K + cc.
The proof of Lemma B.1 follows exactly as (Nguyen & Mondelli, 2020 Lemma D.2), and is in fact slightly simpler due to the fact we assume the rows of A are unit length and No,,, La) instead of vd and following definitions, which are also stated in Section 3 Letting dy == ((p.)) denote a sequence of real coefficients, then
(0, ( respectively. For the ease of the reader, now recall the
and p
F(p, k.) =
and p 2 1,
(28)
Enwert I Ojan k 2 and 2 0,
where
k) = (61)EM : 200e [k], Σ j: = p}
for all p E Zoo. Z21-
We are now ready to derive power series for elements of (GI) and (G))
Lemma B.2. Under Assumptions and for all E [2, L +1] 1]
G
aka (XX
(29)
where the series for each element tive. The coefficients of the series relationship,
G ij converges absolutely and the coefficients atp.1 nonnega- for all p E Zzo can be expressed via the following recurrence
29
oz (2))( + 5p-n0t
1= 2,
Olp,1
(30)
Ek-o ag Pp, k a1-1);
I 12 3.
Furthermore
G Ukl OO
(31)
where likewise the series for each entry [Golis converges absolutely and the coefficients vp.1 for all E Zzu are nonnegative and can be expressed via the following recurrence relationship.
0 (g0))))) Eh Uk Fl k,
1= 2,
Up.1
(32)
12
Proof. We start by proving From Lemma A.
29 and 330. Proceeding by induction, consider the base case 2.
G2 = o E Ew- (. (X + +o 1nnn
By the assumptions of the lemma. the conditions Lemma B. are satisfied and therefore
(0) [xx" Ok + of
G2 2
k=0
0k (XXT)oc of
00, Inx
+
Am
21

---

Published as a conference paper at ICLR 2023
Observe the coefficients (0 Lemma A.2 the series for [Gily satisfies
nonnegative.
Therefore, for any i,j [n]]
using
Ja X,,,,))
0n xx,,
[Gr]a =
(33)
k=0
and so must be absolutely convergent. With the base case proved we proceed to assume the inductive hypothesis holds for arbitrary G. with I [2, LJ. Observe
G -
of 1nnx
where A is matrix square root of G2, meaning G AA. Recall from Lemma A.I that Gj is also symmetric and positive semi-definite, therefore we may additionally assume, without loss of generality, that A TR=x is symmetric, which conveniently implies G,.,' A AAT Under the assumptions of the lemma the conditions for Lemma A.2 are satisfied and as a result [G,, =
||a.|| 1 for all i [n], where we recall a; denotes the æth row of A. Therefore we may again apply Lemma A.
G Te
Σ (0) (AAT) OF + tof1nxn
k=0
= (60)) + o3 nxn + o
(d) (G,,.) Sk
k=1
= (ow + oz) Inxn + o
(O)
Σ
am, [XX fm
m==
where the final equality follows from the inductive hypothesis. For any pair of indices i,j E [n]
G = (6 + of) + o Σ (2) k=1
Σ m
am, (x,, x,)
m is absolutely conver- gent. Therefore, from the Cauchy product of power series and for any & E Aoo we have
By the induction hypothesis, for any i,j E [n]] the series Em= am, x))
Σ am,, I x²)
Σ a(), p=0
(34)
where F(p, k. ār) is defined in 44. By definition, F(p, k, ār) is sum of products of positive coefficients, and therefore [F(p, at) F(p, ki az). In addition, recall again by Assumption and Lemma A.2 that [Gi]s = 1. As result, for any k E Zzo. as (xx, x,y, <
Σ F(p. k (x),, S
Σ am,i = IGn,
(35)
and therefore the series Ep- F'P, ki (x, x²) converges absolutely. Recalling from the proof of the base case that the series Ep= ap,2 is absolutely convergent and has only nonnegative ele- ments, we may therefore interchange the order of summation in the following.
sc
|G = (o()) + +0t) +
Σ
F(p. k. (x),
= 00,2 +
0k
F(p, ān) (x,,
k=1
p=0
00
O4 (p, k an)
x)).
00,2
p=0
22

---

Published as a conference paper at ICLR 2023
Recalling the definition of kl in 4). in particular 0,),0,ā;) 1 and F(p,0,ā 0 for p E Z21, then
0 (0, (1)) (x,, (x,
[G41lk = 00,2 +
ak (p, k. (xe,
(xx,))) x3)
p=1
a (0, k,)))) (xx,
Σ k=
2 (p, (x))
0n F (v, k, (xx,x/)
= (x;
D=U
As the indices i.j [n] were arbitrary we conclude that
G = Σ aptlt (xx")* Cp
p=0
as claimed. In addition, by inspection and using the induction hypothesis is clear that the coeffi-
cients (0p.41)p==0 are nonnegative. Therefore, by argument identical to (33) the series for each
entry of [Guilja absolutely convergent. This concludes the proof of 29 and (30).
We now turn our attention to proving the (31) and (32). Under the assumptions the lemma the conditions for Lemmas A. lnd B.I are satisfied and therefore for the base case | 2
G2 = 2 ww 16' (Xw))"(X)""
2 x
1 (o)) (XX*) Ok
uk (XXT)
By inspection the coefficients (0 are nonnegative and as result by an argument again iden- tical to 333 the series for each entry of [G2ly is absolutely convergent. For / E [2, L]. from 29
and its proof there is matrix A E Ruxa such that G = AAT", Again applying Lemma B.
G = o o. (Aw)o
mE(D') (AAT) ok
m
kmm0
Uk.2 (Gn,.) ok
k=0
Ok
xc
Σ Uk.2
Σ
apdl (XXT) op
23

---

Published as a conference paper at ICLR 2023
Analyzing an arbitrary entry [Gı-llký, by substituting in the power series expression for G: from (29) and using (34) we have
[Gt+ly
Σ apd (x,,
Uk
k=0
Fla,k: (n), (xi (x)xx
Uk
k=0
U/ F (p, (p) ai) (x,:
p=0
k==0
(X,, p=0
Note that exchanging the order of summation in the third equality above is justified as I and therefore
for any k E Z20 by (35) we have Ep= F, (x),, (x)
Ex=o Ep 2p k an) (x;, x converges absolutely, As the indices i,j E [n]] were arbitrary we conclude that
G Upd++ (XXT) or
as claimed. Finally, by inspection the coefficients (Vp are nonnegative, therefore, and again by an argument identical to (33). the series for each entry of [Gn,4talis is absolutely convergent. This concludes the proof.
We are now prove the key result of Section
Theorem 3.1. Under Assumptions and for all I E [I+ 1]
[
nK Σ Kp, (Xx7) 2xx))rr
(5)
The series each entry n niKily converges absolutely and the coefficients Kp, are nonnegative and can be evaluated using the recurrence relationships
8p=ur% + Th ap.l + Σ 11
1=
Kp.1
LE [2, L 1].
(6)
where
(o + Sp=uos O'p.1
1 1= 2, 12 3,
Eh az (p. ko a1-1);
and
Upd = oupp(o')
1 2, 12 3,
(8)
k= Uk F F(p, k on-1);
are likewise nonnegative for all E Zzu and E [2, +
Proof. We proceed by induction. The base case 1 follows trivially from Lemma A.1
We
therefore assume the induction hypothesis holds for an arbitrary - [1, LJ.
From 14
and
Lemma B.2
ki G: + nKKi1 Gi
8 Σ
Σ apd (XXT)or)
1 (Xx?)
on
Unal (XXT)
n
24

---

Published as a conference paper at ICLR 2023
Therefore, for arbitrary i,j E [n]]
[nKilij- = Σ pp (x: x))
Σ 9=
Rg. (x;, x,)
Σ Vial (x, xz)
0l1-1) Observe ni Eq=0 Kig.-1 (Xi, Xj - Xx, Xj) and therefore the series must converge due to the
convergence of the NTK. Furthermore, Σw= Uw., i x [Gn,lig and therefore is absolutely
convergent by Lemma B.2 As a result, by Merten's 's Theorem the product of these two series is equal to their Cauchy product. Therefore
Op xx,
(x,, x2)
p=0
Σ Opp11 +
Rig.t-1 1p--a
(xi, Xii
9=
Σ Kip (x,, xy)²
from which the (5) immediately follows.
B.2 ANALYZING THE COEIFICIENTS 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 é. the recurrence rela- tionship (6) can be simplified in order to depend only on the Hermite expansion of Lemma B.3. Under Assumption 3 the Hermite coefficients of ø' satisfy
(==(d') Vk + (())+((0)
for all & E Zzo-
Proof. Note for each N as is absolutely continuous on [-n, n) it is differentiable a.e. [-n, n). It follows by the countable additivity of the Lebesgue measure that ø is differentiable a.e. on R. Furthermore, ø is polynomially bounded we have E LR, -/ /mm Fix > 0. Since Φ is absolutely continuous on [-a.a] it is bounded variation on [-a, a). Also note that h (=)))==²²/2 =2 is of bounded variation on [-a, a] due to having bounded derivative. Thus we have by Sabesgue-Stieltjje integration-by- by-nartsssss (see e.g. Folland 1999 Chapter 3)
[
('())h(()e--
-2
=a)) 02/2 -2-2200-0)a-alll ((-a))a(-aaa 12/2 f d(x))zha(=) (x)]e x² 12
(aa)ha((a) 02/12 b(-a) (-a)e 22/2
(()) That (z)e x² 12
where in the last line above have used the fact that 24 and
25 imply that sha(x) M,(x)
Vk + (hx+1(x). Thus have shown
[ ('())h((t)e- - 12
= o(-a)ha(--aa - S ((z)V/++ 1h (x)e 12
We note that since (0(x))) (x)) (+1x)++)) we have that as - oc the first two terms above vanish. Thus by sending + 00 we have
I o' (z)))a(z)) 12 f.o. 16(z)(2)/a-111 -122 212
After dividing by 2m get the desired result.
25

---

Published as a conference paper at ICLR 2023
In particular, under Assumption 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 d.
Corollary B.4. Under Assumptions
2 andd 3
for all p Zz0
(p 1) k=u Fl., k 01-1);
1= 2,
Up.1 =
(36)
2 3.
With these results in place 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 the activation function. To this end we roughly group activation functions into three categories: growing tails, flat 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 ReL.U, 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 (2) = (1/ 2 exp (-22/(200) denote the Gaussian activation function with variance o².
Lemma B.5. Under Assumptions 7 and
1. (() = (eLU(22), then Kp.2 = (1 (0) even) (pp ((pp)
2. (f) = Tanh(z), then Kp,2 = (exp xv/p-1
3. (f) = (2)),, then Kp,2 8(no20)U(p Opp (o² 1)-")
Proof. Recall 9
Kp. = 2o (mP))
+ + (1+ +2)
+ 60=007
In order to bound Kp.2 we proceed by using Lemma A.4 to bound the square of the Hermite co- efficients. We start with ReLU. Note Lemma A.4 actually provides precise expressions for the Henmite coefficients of ReLU, however, these are not immediately easy to interpret. Observe from Lemma A..4 that above index p all odd indexed Hermite coefficients are 0. It therefore suffices to bound the even indexed terms, given by
(p - 33)!!
(reRL) = V2T
Vpl
Observe from
26 that for p even
hp(0) = (-1)p/2 (p 1)!!
vp!
therefore
(p 3)!!
(0)
P' (ReTU)
22 Vp!
2nT p
Analyzing now (0)),
pp 1)1! vp!
1T/2 (2i 1)
TT'/2 (2i
1)
(p 1)!!
/I (2i 1)2i
11./2
p!!
Here, the expression inside the square root is referred to in the literature the Wallis ratio, for which the following lower and upper bounds are available Kazarinoff (1956).
< (p
(p-1)) 1-1!!! V
1
(37)
<(p + 0.5)
p!!
T(p + 0.25)
26

---

Published as a conference paper at ICLR 2023
As result
[0) = (pp-1111 =(pp1)))
and therefore
even, odd.
Upl (Re)L 0,
As +p+11 1) 0(p-3/2) then from 9
((pp)) (ReUU (U) + & 1 (ReLU)))
k
((S5peven) 3/2 + 6 (odd) (P + 1) 8/2))
θ (11p (f 3/2
o( 0 -/2) 3/2
as claimed in item I.
We now proceed to analyze ((z) Tann((z). From Panigrahi et al. 2020 Corollary F.7.1)
Mp(Tanlly = exp
As Tanh satisfies the conditions of Lemma
Hp (Tanh) = 1p11112/pp20 Mp-1 (Tanh')anhh))) =0 (0p1-1/ee
1/2 exp
Tvp-
4
Therefore the result claimed in item follows as
O( ( (Tanh) + (p+ 1) (Tann)))
Kp.
TVP-1 -1
+ cxp (- /VP
exp
2
i TVP
I
O exp
2
Finally, we now consider d(2) Wa (2) where Wa (2) is the density function of A0, g3). Similar to ReLU, analytic expressions for the Hermite coefficients of wa (z) are known (see e.g., Davis 2021 Theorem 2.9),
k2(wo)
(p/2)))
p even,
0.
p odd.
For p even
(p/2)! p!/2-p/2.
Therefore
p!
2D p!
2D (p 1)!!
(p/2) 22)
p!p!!
p!!
As result, for p even and using (37 it follows that
( (02 1)-(++) (p+1) (p-1)) 1)!!
(022222 + P)
2x
p!!
Finally, since (p + (0² + 11)---1 12 + 1) then from 9
kpp2 ((pu((ww)) + 8 (p + 1) 1 (W,)))
θ (lppeee) odd (7. (())0)))))) 20² + 1)-
oln 12 +1) (0)++
claimed in item 3.
27

---

Published as a conference paper at ICLR 2023
B.3 NUMERICAL APPROXIMATION VIA 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 (3), b) numerical approximation of these same integrals such as in Lee) al. (2018), or c) approximation via a sufficiently wide yet still finite width network, see for in- stance Engel ct al. y; Novak et al. (2022). These Gaussian integrals (T3) can be solved solved analytically only for 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 7th element. Once the top 7 coeffi- cients are computed, then for any input correlation the NTK can be approximated by evaluating the corresponding finite degree T polynomial.
Definition B.6. For an arbitrary pair x,y E &dd-1 let P == x denote their linear correlation.
Under Assumptions / and for all E [2, I. 1] the T-rruncated NTK power series 6 T [-1,1] + defined as
0% (p) Σ kp,ipp
(38)
and whose coefficients are defined via the following recurrence relation,
6p=078 + Pw: Ep.t + 2 R
1=
Rp,1
(39)
lE [2, L+ 1I.
Here, with 8 (dp..- 1- Tm-
uipe Sp-uog
1=
áp, ==
(40)
Σ K= 2 a1-1),
123
and
vp -1p+12212 Elzo vk 12 k, āt),
1=
0p.1
(41)
[ 12 3.
In order to analyze the performance and potential of the truncated NTK for numerical approximation, we compute for ReLU and compare with its analytical expression Arora et al. (2019b). To recall this result, let
R(p) V1 p2 + p arosin(p)
+P
π
2
(p(p) arcsin(p)
Under Assumptions I and
2 with ((z) = Re n/=
= 1, 0²
=2 o = = =,, E Sd and
2,
P1 := xx'y, then (x and for all / E [2, [.+
Pr = R(pt-1); 1),
(42)
(x Pt P(
Turning our attention to Figure 2 observe particularly for input correlations |p| 0.5 and
below then the truncated ReLU NTK power series achieves machine level precision. For [p] x 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 smaller absolute error 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. as Op.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, e.g.. Table I 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.
there is symmetry the absolute error for positive and negative correlations
28

---

Published as a conference paper at ICLR 2023
Error truncated NTK
10a
10
10"31
10a11
Le1
T-50, L-1
10"31
1-5,
T-50,
-1.00
-0.75
-0.50 -0.25
0.00 025
0.50 0.75
1.0
Figure 2: (NTK Approximation via Truncation) Absolute error between the analytical ReLU NTK and the truncated ReLU NTK power series as funetion of the input correlation for two different values of the truncation point 7 and three different values for the depth L of the network. Although the truncated NTK achieves uniform approximation error of only 10-1 [-1, for lo| < 0.5, which we remark is more typical for real world data, = 50 suffices for the truncated NTK to achieve machine level precision.
B.4 CHARACTERIZING NTK POWER SERIES COEFFICIENT DECAY RATES FOR DEEP NETWORKS
In general, Theorem 3.1 does not provide a straightforward path to analyzing the decay of the NTK power series coefficients for depths greater than two. This is at least in part due to the difficulty of analyzing (p, k, a;-1). which recall is the sum of all ordered products of k elements of ã whose indices sum p, defined in 4 However, in the setting where the squares of the Hermite coefficients, and therefore the series (Qg.2)p=0 decay at an exponential rate, this quantity can be characterized and therefore an analysis, least to certain degree, of the impact of depth con- ducted. Although admittedly limited in scope, we highlight that this setting is relevant for the study of Gaussian activation functions and radial basis function (RBF) networks. We will also make the additional simplifying assumption that the activation function has zero Gaussian mean (which can be obtained by centering). Unfortunately this further reduces the applicability of the following results to activation functions commonly used in practice. We leave the study of relaxing this zero bias as- sumption, perhaps only enforcing exponential decay asymptotically, as well as a proper exploration of other decay patterns, to future work.
The following lemma precisely describes, the specific setting considered here, the evolution of the coefficients of the Gaussian Process kernel with depth.
Lemma B.7. Let 0g,, = O and ap = C2T for Zzi, where C2 and 1p2 are constants such that Ep= 0p.2 1. Then for all 1 2 and p E Zzo
0,
p p=0 0,
ap1++1
CH+
p
p p21 1
(43)
where the constants 7141 and C1+1 are defined as
C₁2
C41
(44)
1/2 + C²'
7/2 + Ci
Proof. Observe for 1 = 2, we have that 0o.1 = 0 and ap,1 = Cm, P hold by assumption. Thus
by induction it suffices show that 0n,1 and 0pp.1 Cm, P implies (43) and 44 hold. Thus
29

---

Published as a conference paper at ICLR 2023
assume for some / 2 2 have that dug, 0 and Op.
Cm -. Recall the definition of F from
as Cru, = then with p 2 1 and I k S p
F(p,k,āi)=
Σ (A)ET)
II
agd Σ
II a
(p.8)
where
((N)EE) : J. 1221111 12IEE
ビ== for all p E Z2 k E [p],
which is the set all k-tuples of positive (instead non-negative) integers which sum to p. Substi-
tuting Cpp,1 = Cmn P then
k() = E
Ch Cf "I (p, = cf ( -
where the final equality follows from stars and bars argument. Now observe for > p that at least one of the indices in (f must be and therefore I[ 03,,2 0. As a result under the assumptions of the lemma
1. F(p,k, k. ai) = Ch (K=)),
k = 0 and p = 0,
k E [p] and 2 1. otherwise.
(45)
0.
Substituting 45 into it follows that
00,1+1
0 F(0, āi) 00,22 0
k=0
and for p 2
0p1++1
0k Fa (p,ki ki)
km0
C1 k
1
C2m
7/2
1-1
= = "Cm² C2
p-1
Σ
C
(2 h
P
122
1=0
Ci
p-1
m "Cme C22
1
C₁C₂
11112
-P
1/2 + Ct
1/2 +
C₁
C1417777
as claimed.
We now analyze the coefficients of the derivative of the Gaussian Process kernel.
Lemma B.8. In addition to the assumptions of Lemma B.7 assume also that é satisfies Assumption
Then Up.2
C2 (1 + p) Furthermore, for all 2 2 and E Zzo
(C2Tp² Up141 (11441 + V1+1P)
p 0,
(46)
p N 1,
where the constants V/41 and V44 are defined as
2C2C1
C2C²
C2C² 72(Ci + 712)
ViL
V4+1
(47)
T2 + T1))
(2(Cis + 72)22*
and Ct and mp defined in 44
30

---

Published as a conference paper at ICLR 2023
Proof. Under Assumption then for all Zz0 have
C2 (1 + p)m p.
Up,2 = " = (p 1) (p + 1)0p+122
1/2
For 1 2 2 and p 0 it therefore follows that
20 (ks + 22 =1,2 C2n
00,++
A=0
For 1 2 2 and p then
Up
Uk F (p,
k=0
Σ
(k: 1)ax+112(Pppkk
Σ h=1
hC2n2 h F(p, h a,
C2 /
p+1
h p 1)
1/2
h -
C2
Ci
P (
G tht
Σ
+ 2)
172
C2 11
Σ
(
P
(
p
72
122
C2C1 11 -D
1+ 11
Ci
C (p 1)
(1+
(1
p-2
1/2
72
1/2
2C2CI
11/12
C2C
1111/2
-p
(p 10
m (Ct + +12
1/2 + Ci
(C + 1222
112 + Ci
2020r
C2O2
C2O7
1141 +
-P
pMi+1
(Ci + 1/22
1/2 (a 12)22
(12(Ci 122)²
(V/41 + V(+1P)i+1
as claimed.
With the coefficients of both the Gaussian Process kernel and its derivative characterized, we proceed upper bound the decay of the NTK coefficients in the specific setting outlined Lemma B.7 and B.8
Lemma B.9. Let the data, hyperparameters and activation function & be such that Assumptions
2 and are satisfied along with the conditions of of Lemma B.7. Then for any 2 2 there exist
positive constants Mi and K2 such that for all E Zz1
Kpd S (M) + Kip 21 )m
(48)
where qn defined in Lemma B.7
Proof. We proceed by induction starting with the base case = Applying the results of Lemmas B.7 and
B.8 to (6) then for p E Zz1
Kp. = ((C2 + C2 + (2) + 7 "²
(49)
If we define M₁ = C2 + C2 and K₁- : -2 + 7 C2, which are clearly positive constants, then Kp,2 (M₂ K3y)n and so for 2 the induction hypothesis clearly holds.
31

---

Published as a conference paper at ICLR 2023
We now assume the inductive hypothesis holds for some / 2 2. Observe from (46). with / 2 2 and p E 220 that
4p141 S (A/+1 + V4+1P)
(50)
where 1/+1 = max(C27z V441.. Substituting 50 and the inductive hypothesis inequality into 66) it follows for 2 that
Kp,++1 I C4+17441 + 1141
(M/ + K(/9t- " + (
9=0
p
(M + 3)/2t-3)(44 + V4+1(p 9)) (
122
=C417144 + 1111
112 + Ci
4=0
P
S C4417441 M111
(Mi + Kiq 2 (A/4) + V1+1(D-00 9))
9=0
P $ C4+ + M111
(Mi + 3// + V4t1))
4=0
$ (C1+1 M/A(+1)mm + MMVV+iPP+ + Σ(M] K(921-3) + VV+1p) Mitt
< (C1+1 + MM 1 + (M/VV41P + p(Mj + 3) 1 + V(+1P)) Miti
< (C1+1 A/A44+100 M + (Mi 2M V + Ki KiA1410 21-3 KiV4112 21-)) 7
- ((C1+1 + MM/ 1114 + (M/44/+1 + 2M, V4+ + K/4/+1 + K/V1+1) 1 M141
Therefore there exist positive constants Mi_ C++++M,4
and Ki+1 + V
Kj + K/Vi=1 such that Kp.4+1 I (M + K24 (0(+1)))))))))) 3) as claimed. This completes the inductive step and therefore also the proof of the lemma.
C ANALYZING THE SPECTRUM OF THE NTK VIA ITS POWER SERIES
C.1 EFFECTIVE RANK OF POWER SERIES KERNELS
Recall that for positive semidefinite matrix A we define the effective rank Huang et al. (0022 via the following ratio
(A) = Tr(A)
{A
We consider a kernel Gram matrix K Rnxn that has the following power series representation in terms of an input gram matrix XX"
K Σ c (X
Whenever co * the effective rank of K is O(), as displayed in the following theorem. the Theorem 4.1. Assume that we have a kernel Gram matrix K of the form n. = Ep Cp (XXT)0 Op
where 6o + 0. Furthermore, assume the input data x, are normalized so that |Xx || = for all i [n]. Then
Ep=o
eff( S
Co
Proof. By linearity of trace we have that
Tr(nK) - TTrr(XX'*
(01)
Σe G
1=0
32

---

Published as a conference paper at ICLR 2023
where we have used the fact that Tr( Tr((XX7)0) for all i N. On the other hand
(nK) (x (1 noo.
Thus have that
(r(K) Tr(nK) (1( (1(KK
2i
elT(K)
S
Co
The above theorem demonstrates that the constant term colaxn in the kernel leads significant outlier in the spectrum of K. However this fails to capture how the structure of the input data X manifests in the spectrum of K. For this we will examine the centered kernel matrix K ==
K co 112". Using very similar argument as before we can demonstrate that the effective rank of K is controlled by the effective rank of the input data gram XX". This is formalized in the following theorem.
Theorem 4.3. Assume that we have kernel Gram matrix K of the form nK = Ep=o Cp (XXX) JOP where + O. Furthermore, assume the input data x; are normalized so that xx&|| for all i [n]. Then the centered kernel K == = 02 laxn satisfies
Ep=1
eff (K) < efx
Proof. By the linearity of the trace we have that
20
Tr(nk) Σ (Tx(((x)))))== Tr(XX" Σ
C4
where we have used the fact that Tr Tr((XXT) Tr(XXT) n for all i E [n]. On the other hand we have that
(1(nK) A1((IXX))) (XX)).
Thus we conclude
Tr(K) Tr(nk)
Tr(XX EE
eff(K) (K) A1(nK) Xx(XXT)
C1
C.2 EFFECTIVE RANK OF THE NTK FOR FINITE WIDTH NETWORKS
C.2.1 NOTATION AND DEFINITIONS
We will let [k] (1,2, k). We consider a neural network
Σ agol (We, x))
where x IRd and W. E Rd, E E for all E E [m] and ó is scalar valued activation function. The network we present here does have any bias values in the inner-layer, however the results we will prove later apply to the nonzero bias case by replacing x with xx" _1"" We let W E mxx be the matrix whose l-th row is equal to We and ag. We can then write the neural network in vector form
R. be the vector whose k-th entry is equal to
f(x; W, a) = a (WWx)
where @ is understood to be applied ensr.
Suppose have training data inputs Xi...., Xn Rd. We will let X E Raxd be the matrix whose i-th row is equal to X,. Let owner = uec( W) denote the row-wise vectorization of the inner- layer weights. We consider the Jacobian of the neural networks predictions the training data with respect to the inner layer weights:
Of(x))
0f(x))
0 (xx)
JT inner
30 Hmnner
00 00mner
06 2i.ner
33

---

Published as a conference paper at ICLR 2023
Similarly we can look at the analagous quantity for the outer layer weights
[x(())
(x(x2)
0s(x,)
J
Φ (Wx*).
outer
da
da
da
Our first observation is that the per-example gradients for the inner layer weights have a nice Kro- necker product representation
aid'((w1,
(x(x) a inner
a20' ((22(
@ x.
Om (Wwm, x))
For convenience will let
a1 ((W1,
a2 ((w2, x,))
Y,
am &' ((Wm xx))
where the dependence of Y; on the parameters W and is suppressed (formally Y, (WW,,)) This way we may write
0f(x:) = Y; x, 00 Hnnne
We will study the NTK with respect to the inner-layer weights
K Kinner Jinnerd inner
and the same quantity for the outer-layer weights
K ooter Jouter outer.
JT
For hermitian matrix A will let (AA denote the ith largest eigenvalue of A that X1 (A) 2 (A) 2 ... 2 (A). Similarly for an arbitrary matrix A we will let (((A) to the ith largest singular value of A. For matrix E rg we will let Tmin (A) miin(r,k)
C.2.2 EFFECTIVE RANK
For positive semidefinite matrix A we define the effective rank (Huang al. 2022) of A to be the quantity
Tr(A)
eff
(A)
The effective rank quantifies how many eigenvalues are on the order of the largest eigenvalue. We have the Markov-like inequality
Tr(A)
Ki: (1:A(A)) (A)(
AA
and the eigenvalue bound
A(A) 1Tr(A)
(A) (A)
Let A and B be positive semidefinite matrices. Then we have
Tr(A + B)
Tr(B) A max (A), (A) (B)
Tr(A)
X, A B
Thus the effective rank is subadditive for positive semidefinite matrices.
We will be interested in bounding the effective rank of the NTK. Let K = JJJ Jo J +
Jinner JT anner Kouter + Kinner be the NTK matrix with respect to all the network parameters. Note that by subadditivity
Tr(K) Tr(Kouter (K)
Tr(K Tr(Kinner
(1(Kouter)
A (K (inne))
In this vein will control the effective rank of K Kinner and Kauter separately.
34

---

Published as a conference paper at ICLR 2023
C.2.3 EFFECTIVE RANK OF INNER-LAYER NTK
We will show that the effective rank of inner-layer NTK is bounded by multiple of the effective rank of the data input gram XX". We introduce the following meta-theorem that we will use to prove various corollaries later Theorem C.1. Set = siplibl=1 [minseta] KY b)ll. Assume a > Then
[in Y | (xXx+
Tr(K Kinnr)
ma 1 Tr(XX")
ma |Y A1 (XXT)
(Kinner)
a²
XXX")
Proof. We will first prove the upper bound. We first observe that
(f(x),) 80inee
n Y 2 x1
n Σ
Tr Tr(Kinner)
Σ
Y 11x1112
12
1=1
max Y jE(m]
|xxI|2
max JE(n)
Y , Tr=
Recall that
A1 (Kinner) d1 (J (Jinnerd Jnner) x1 (J Unnner (Jinerranner)
Well
0s(x;) 05(xi) T
J
inner inner
20 inner 30 Winner
Y.Y @ x
Well then we may use the fact that
A1 (J inner (nner)
max [|bl|==1
bJr
Jnner Jinner inner
Let b1 E Rm and by E Rd be vectors that we will optimize later satisfying [b1ll2 |ball2 = 1. Then we have that [bb @ b2ll = and
(b, b²) J T J inner (b, 3 b2)
= (b, b²)² ((YY?) s [xxx]]) (b, @ b2)
[b Y.
bi] x00"" ba]
>
min by Y, Y b jj(nl
by x bz
min jE(N]
by v Y bj
by'
Σ xxxx
T
b2
min by Y Y bj jE(x
Xb2 "xb2
1=1
Pick b2 so that ||bl| and
b x = = xx (Xx")
=
Thus for this choice of b2 we have
X (J Inne J inner)
2 (b. & b2) "J" J' Jineer (b, 8 b2) 2
min by DT YJb by jE(n)
bax T =
min b YY (xx))
JE(n
Now note that a² bup || mmnnee[n) b Y b.]. Thus by taking the sup over b in our previous bound we have
X1 K Kinner)
>1 (Jnner J Jinner) 2 a2 (Xx²)
35

---

Published as a conference paper at ICLR 2023
Thus combined with our previous result have
Tr TrKinnee))
maXiE[n] IY,1 Tr(Xx*)
A (nnn)))
A1(XX=)
We now prove the lower bound.
af(x;; 30mner
n Σ Y x1112 Σ
n
Tr(K Fr(Kinner)
Σ
Y 11
min jE(m
|x min
Y Y Tr
JE
Let Y E Ruxm be the matrix whose ith row is equal to Y. Then observe that
K Kinner
YY [Xx]
where @ denotes the entry-wise Hadamard product two matrices. We now recall that if A and B two positive semidefinite matrices have (Oymak & Soltanolkotabi 2020 Lemma 2)
A1 B)
max (B))
:E|n]
Applying this to Kinner we get that
KK inner)
max
|Y, (XX7)
sE(n]
Combining this with our previous result we get
min Y 11 Tr(x"")
Tr Tr(Kinner)
max4e[1]
Y, Y1 A1 (XXT)
A1 >1(Kinerr
We can immediately get a useful corollary that applies the ReLU activation function
Corollary C.2. Set suppib|=1 [mingejm] ((Y,, b)[] and "/max suPaeR (0'(z), > 0 and Pimax < cc. Then
Assume
Tr (XX
Tr( Tr(Kenner) A K (Kinee))
Tmaz ||a|| Tr(XX
la
XI XXX
a
(XXTT)
Tmme
Proof. Note that the hypothesis on |o'| gives ||,1 <
22 mma
||a|| for all i E [n]. Moreover by
Cauchy-Schwarz we have that minfe[a) | 2 a. Thus by thcorem C.1 we get the desired result.
If à is a leaky ReLU type activation (say like those used in Nguyen & Mondelli 2020 Theorem
C.1 translates into simpler bound
Corollary C.3. Suppose d'(x)) Timin: Ymar for all
RR where Train > 0. Then
2n Tr(XX")
Tr TriKinner)
Maa Tr(XX")
2 maa (XXT)
d (Kinner)
Pim X (XXT)
Proof. We will lower bound
KY b)|
a: sup
min jeIn|
bb|==
so that we can apply Corollary
C.2 Set b a/ |a|]
Then we have that
m
YY b) =
aro' ((w, /ee/ ||a]| 2
Umin
az = Ymnn ||al|
|a||
1=1
Thus 2 Tmin ||a|| The result then follows from Corollary
C.2
36

---

Published as a conference paper at ICLR 2023
To control in Theorem C.I when ó is the ReLU activation function requires a bit more work. To this end we introduce the following lemma.
Lemma C.A. Assume ((x) = (x). Let Rmins Rymas: > O and define T = {e E [m]] : |axl E
[Rminy Rmaz]] }. Set T min4e(n) Eter [(x;; We) 2 0J. Then
R
miin
T
sup |b]|=1
min iE|n]
(Y b)| 2
Raar
[ |
Proof. Let a, be the vector such that (ar)e aelle E 7]. Then note that
, ||-|122
1
Σ
afT(( xy)
||a-||
FET
Rmin
Rmiin T
R2
Σ
I[(we,
20
Rmax 1/2/22 T.
ar ll
FET
Roughly what Lemma C.4 says is that a is controlled when there is a set of inner-layer neurons that are active for each data point whose outer layer weights similar in magnitude. Note that in Du et al. (201bb), Arora et al. (2019)), Oyymk 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 Rmin Rmaw in Lemma C.4 so that T = [m]] In this setting we have the following result.
Theorem C.5. Assume 6(z) (e)U(z). Suppose lael R 0 for all l E [m]. Furthermore suppose Wi...., are independent random vectors such that We/ Well has the uniform distri- bution on the sphere for each E [m]]. Also assume 4log(n/c) probability at least - we have that
for some 8, (0, 1). Then with
8a
(1 2)
4
eff(XXx] S eff (Kinne)) S
eff (Xx").
(1 8)2
Proof. Fix j E [n]. Note by the assumption on the wy's we have that [[(W1,y)) 2
0) ...... 1[( X²) 2 0] are i.i.d. Bernouilli random variables taking the values 0 and 1 with proba- bility 1/2. Thus by the Chernoff bound for Binomial random variables we have that
0 S (1 (1-6) 6))
exp (-82
P
W X2)
Thus taking the union bound over every j E [n]] we get that if m >
llg(n/c) de then
min jE(n]
Σ [(w,, x,)
(1-5)
holds with probability at least e. Now note that we set Rman = Rmar = we have that [m] where is defined as it is in Lemma C.4 In this case by previous bound we have that T as defined in Lemma C.4 satisfies T 2 8) with probability at least - e. In this case the conclusion of Lemma gives
a 2 Rm 1/2 8)
(1-8)
||l||
2
Thus by Corollary C.2 and the above bound for we get the desired result.
We will now Lemma C.4 to prove bound in the case of Gaussian initialization.
37

---

Published as a conference paper at ICLR 2023
Lemma C.6. Assume ((x)
(x) Suppose that de N(0.²2) for each é [m]
i.d. Furthermore suppose Wi...., Wm are random vectors independent of each other and such that Wz/ |well has the uniform distribution the sphere for each [m]] Set p P Pz~N(01) (12 E (1/2,1) 2 0.3. Assume
4 4log(n/c)
m
82 - 8)p
for some c, E (0, 1). Then with probability at least (1 - c)² we have that
= sup blj=1
min sE|n
YY b)
2 (1-6)8/2 p22
Proof. Set Rmiin 2 and Rmaz = v. Now set
Rmin Rynax
p P. P0. (lal E [Rmins Rmarl) 2IP N(0,1.
2IP (0. (z E [1/2, 11) ~ 0.3.
Now define т = {E [m]] lazl E [Rminn Rmaz]] We have by the Chernoff bound for binomial random variables
IP ((T] (1 8)mp) S exp (-62 (-82)
Thus m 2 log (t)
2 (a weaker condition than the hypothesis on m) then we have that |r| 2 (1 - 8)mp with probability at least 1 From now on assume such T has been ob- served and view as fixed so that the only remaining randomness is over the we's. Now set T = minie(n) Eter [[x, we) 2 0j. By the Chernoff bound again we get that for fixed i E [n]]
pe
0 (1 (1-8) [T]
S exp (-BelT)
P
Σ
I w
2
E
Thus by taking the union bound over E [n]] we get
- 0) |r| S n nxx
P
T
2
4
(1 8)mp
-82
S n exxp
4
Thus if we consider 7 fixed and sampling of the we's we have that
4log(n/c) then with probability at least 1 the 82(1-b1p
8)
T2 |T|
2
In this case by lemma C.4 we have that
= sup [b||=1
min
(Y b)| >
R2
Main
T [7|1/2
[E(m]
Rmax
8)3/2mm 1221122
Thus the above holds with probability least (1 e)2
This lemma now allows us to bound the effective rank of K Kinner in the case of Gaussian initializa- tion.
Theorem C.7. Assume d(x) ReLU(x). Suppose that
(0, for each & [m]] i..dd Furthermore suppose Wi...., Wm are random vectors independent of each other and a
such that we/ [well has the uniform distribution the sphere for each & [m]. Set p
P.- P=~N(0.1) [|2] E [1/ z 0.3. Let e, E (0, 1). Then there exists absolute constants c, K > such that if
(noe
m 2
82 8)p
38

---

Published as a conference paper at ICLR 2023
then with probability least 1
3E we have that
TT XX")
TrnKenner
Tr(XX")
C A X
A K Kinner)
(XXx²)
where
64 C' (1 8)
maxfc KK (og((o/)),mml mk]
Proof. By Bermstein's inequality
12 mk? K
[1a/v12 - m 2 < exp -c min
where e an absolute constant. Set max K log(1/c), /c), mk) so that the right hand side of the above inequality is bounded by Thus by Lemma C.6 and the union bound we can ensure that with probability at least
-1 3c 2² 2 -c
that ||a/v||2 1 m + and the conclusion of Lemma C.6 hold simultaneously. In that case
|all
2 m +
64 (1
1
1 +
= C.
a
8mp
8)3p
m
Thus by Corollary C.2
we get the desired result.
By fixing 5 > 0 in the previous theorem get the immediate corollary Corollary C.8. Assume (bx) (eLU(x).. Suppose that at N(, v²) for each [m] ii.d Furthermore suppose Wi..... Wm. are random vectors independent of each other and a such that we/ [|we| has the uniform distribution on the sphere for each E [m]. Then there exists an absolute constant C >> O such that m = (llog(n/E)) ensures that with probability at least 1
TxXXX C (XXT)
Tr(Kinner)
Tr(XX*
S
A1 (K (nner))
Ax(XXT)
C.2.4 EFFECTIVE RANK OF OUTER-LAYER NTK
Throughout this section ((x) (x) Our goal of this section, similar to before, is to bound the effective rank of Koater by the effective rank of the input data gram XXT. In this section we will often make of the basic identities
||B|| = || |BI|
|AB|| < |||| |BI|
Tr(AAT) ) = Tr(A A) |
|| ||A
A(AAA) = (AA") |
To begin bounding the effective rank of Kouter, we prove the following lemma.
Lemma C.9. Assume 6(x) ReLU(x) (x) and W full rank with d. Then
1 WXXX 11 112
W Tr(XX
[ I11 + || WX
m (W)2 (XX"))
39

---

Published as a conference paper at ICLR 2023
Proof. First note that
| || - |xx| 1 - [ x = TxITT((""))
Pick Rd such that |bll = 1 and X |
Since w is full rank we may set where mmin ( (W?) is the smallest
u u= (WT)bb so that W W b where ||ln| S Omin (W
nonzero singular value of W Well then
X = |bbl2 = X u||2 & X Iuulla - |X min (WT)-1
|X || min (W)
Now using the fact that x ((x) 66-2) we have that
[x 112 = | wx") - ~ wx 112 - | )|12 + (o(--x")ll
Thus combined with our previous results gives
X I min (W) [|( 1llrr- 112]
Therefore
1o(WX M12
|Ø(Wx))
mmin (W) [1] W ll1 + (op--xX)J1 122
|X 1
W Tr(X"")
| Tr(XX") (XX")
|X|
which gives us the desired result.
Corollary C.10. Assume 6(x) = (x) and W is full rank with m 2 d. Then
max (Io((WT)) - )1
WW Tr(XX")
<
max 116(- (1o(Wx7)1331l(((
Mmin (W)2 (XX*)
Proof. Using the fact that
[@Wx") Il1 + (|x(- S 2 max (|o( |6
and lemma C.9 we have that
| 1o(xx")
W Tr(XX")
max (1 11122.11(--w0 (
Gmin (W2 (XX")
Note that the right hand side and the denominator of the left hand side do not change when you replace W with WW. Therefore by using the above bound for both W and -W as the weight matrix separately
conclude
max (10(WXT) 1|= 11=- (1666-x])]
IWI Tr(XX")
4 max (10(WXT) 1o(o-oo
Omin W)2 (XX")
Corollary C.11. Assume d(x) = (z) and m 2 d. Suppose W and W have the same distribution. Then conditioned on W being full rank we have that with probability least 1/2
Tr(Kouter)
|W (r
<
\ (Kouter)
Omin W)² A (XX
40

---

Published as a conference paper at ICLR 2023
Proof. Fix W where W is full rank. We have by corollary C.10 that either
Tx(XX")
I
(x(WX
min W X (XX*)
holds or
(6(-wx"))
IW Tr(XX")
11 WX
Mmin (W) A (XX²)
(the first holds in the case where | )|2 < ((@(w>))
1 112 and the second in the case
Since W and - W have the same distribution, it follows that the first inequality must hold at least 1/2 of the time. From
Tr(Kouter A [K outer))
J J
outer 1|
outer 12
| 1@(WX
get the desired result.
We now note that when W is rectangular shaped and the entries of W are i.d. Gaussians that W full rank with high probability and mmi (m)) | is well behaved. We recall the result from Vershynin (2012)
Theorem C.12. Let A be N x n matrix whose entries are independent standard normal random variables. Then for every 2 O, with probability at least 2 2exp(-1* /2) one has
v S Jmin (A) S Sa
vn+1
Corollary C.11
gives us a bound that works at least half the time. However, we would like to derive a bound that holds with high probability. We will have that when m 2 n we have sufficient concentration of the largest singular value of ((WX") to prove such a bound. We recall the result from Vershynin (2012) (Remark 5.40)
Theorem C.13. Assume that is an x n matrix whose rows A, are independent sub- tob--gausiann random vectors in IR" with second moment matrix L. Then for every t 2 O. the following inequality holds with probability at least 2 exp((cct2)
|
A'A Σ
mmax(6,82) where 8 6=C
VN
where C = CK, c= cK > 0 depend only on K = max; ||Aillga
We will use theorem C.13 in the following lemma.
Lemma C.14. Assume (xx) (e) Let A di 6(WXT) and M max4elm |xxl|z Suppose that W Wi...ry
Wm Wm
(0, 22 Ia) i...d. Set K Mvv/n and define
Σ = Bw- Buw (ow xx")
Then for every 2 0 the following inequality holds with probability at least 2 2expp (exp(-cxtt)
LA-A-E)
1
S max(6. 82) where C=CK]
Ck V
+
m
2
m
m
where сx. Cg > 0 are absolute constants that depend only on K.
Proof.
We will let Ag, denote the 9th row of A (considered as column vector). Note that
A di ((We))
41

---

Published as a conference paper at ICLR 2023
We immediately get that the rows of A are ii.d. We will now bound ||Ae: 1l Let b R" such that |lb||| 1. Then
(I(((X,)),))) b)llg
Σ (xx; wi))ba
bu (xx, wo)
lbil |1 woll
1=1
by ||llliill2 S CMp ||b|l & CMuVa
where C > 0 is absolute constant. Set K Muyn. Well then by theorem C.13 have the following. For every / 2 0 the following inequality holds with probability at least 2 exxp(ccxl*
AATA- m
max(6, 83) where 8 Ck v
n m
m
We now ready prove high probability bound for the effective rank of Kouter. Theorem C.15. Assume d(x)) (x) and d. Let M max4e[m] ||x||12-
Suppose that
Wa Wm (0, La) i.i.d. Set K Mvvn
= Bww Bow.Noournlo//wwod )
log(2/c)
d= CK Ck
n
V
where E 0 is small. Now assume
Vm Vdl + 2og((//
and
1
max (axx) マ 5)1(E)
Then with probability at least 1 3c
2 Tx(X-x) ) /m Vd vd- t1 (XTX
Tr(Kouter)
Vm v vd 1
12
\1 oouter)
Proof. By theorem C.12 with t /2log(2/c) we have that with probability at least 1 that
mm Vd - t S Jmin (W/v) S 01 (W /v) S /m +d+ti
(51)
The above inequalities and the hypothesis on imply that W is full rank.
Let A = of WXT) and À = o(- Wx ). Set to
(og(2/e) where is defined as in theorem
ex
C.14 Note that A and À are identical in distribution. Thus by theorem C.14 and the union bound we get that with probability at least 2c
1 ATA-D Σ
A
Σ
< max(o, 82) =:p
(52)
where
n
t2
8 = C
+
v m
42

---

Published as a conference paper at ICLR 2023
By previous results and the union bound ensure with probability at least 1 - 3c that the bounds (51) and (52 all hold simultaneously. In this case we have
1
A
A
<
A T
A
+
2p
1 m
2p
1 ATA
2p
A
A
A
1 1+
ATA
m
X1
p.
Assuming p S 21 we have by the above bound
1
A
A
3
A
T
A
Now note that so that our previous bound implies
| = [|(((WX'
)12
|AA|| = -
| wX s 3l
then we have by corollary C.10 that
Tr Tr(Kouter)
1 Tr(XX")
< 12
(Kouter)
16(( )12
Tmin
(ninnW] (W)² (XX"))
Vm+ vd vd+4 Vm vd -1
Tr(XX]
S 12
AxXX"
From the above theorem get the following corollary.
Corollary C.16. Assume o(x) = ReLU(x) and n 2 d. Suppose that Wi,... N(0, v²1a) i..dd Fix small. Set M max4e(n] ||x; l2- Then
m Ω (max(A) (A1 (E)-2, 1) max(n, log()/e)))
and
== O(1/M/m
suffices to ensure that with probability at least -
Tr(Kouter)
< 0 Tr(XX")
A1 (Kuter)))
(XXTX
where C O is absolute constant.
C.2.5 BOUND FOR THE COMBINED NTK
Based on the results in the previous two sections, we can now bound the effective rank of the com- bined NTK gram matrix K Kinner + Kouter-
Theorem 4.5. Assume ((x) ReLU (x) and n 2 d. Fix > 0 small. Suppose that Wiy Wm. (O, v Ia) Li.d. and dj,..... am ~ N ((, v2) Set M = maxie[n] |xsll and let
Σ = E N (Xw x
Then
m Ω (max (
Vi = O(1
suffices ensure that, with probability least 1 1-c over the sampling of the parameter initialization,
eff eff(K) < C eff efx(Xx)),
where is an absolute constant.
Proof. This follows from the union bound and Corollaries C.8 and C.16
43

---

Published as a conference paper at ICLR 2023
C.2.6 MAGNITUDE OF THE SPECTRUM
By our results in sections C.2.3 and C.2.4 we have that m 2 n suffices ensure that
Tr(K)
Tr(XX²)
X (XX) Sd
(K)
Well note that
(
Tr(K)
dd
(K)
(K)
if > then X₂ ( A1 (K) is small. Thus the NTK only has (d) large eigenvalues. The smallest
eigenvalue A. (K) of the NTK has been of interest in proving convergence guaranteess (Du et al.
2019a b: Oymak & Soltanolkotabi 2020). By our previous inequality
(K)) d (K)
<
Thus in the setting where m 2 n >> d we have that the smallest eigenvalue will be driven to zero relative to the largest eigenvalue. Alternatively we can view the above inequality lower bound on the condition number
A1 (K) A, K
n 2
d
We will first bound the analytical NTK in the setting when the outer layer weights have fixed constant magnitude. This is the setting considered by Xie et al. (201)) Oymak et al. (2019), Li et al. (2020), Oymak & Soltanolkotabi (2020).
(2017),(Aoraa AArora et al. al. (2019a), Du et al. (2019)),
Theorem C.17. Let ((x) ReLU(() (x) and assume X O. Let K inner E Rax be the analytical NTK, i.e.
(K (iner = (x,, (w ((x;,, ()),'((X, w))].
Then
1 1Tr(XX")
Tr(Ko (nnee)
Tr(Xx")
4 A (XXT)
A (Ko
(XX))
inner
Proof. We consider the setting where lael
= 1/ym for all E E [m]] and we ~ N(0, I2) i.i.d.. As
was shown by Jacot et al.) (2018). Du et al. (2019b) in this setting we have that if we fix the training data X and send m + Do we have that
Knner Kinnelly l2
in probability. Therefore by continuity of the effective rank we have that
Tr Tr(Kinner)
Tr(K 90 inner
A1(Kinne
X1 (K
po inner)
in probability, Let 17 0. Then there exists an M E NN such that m > M implies that
Pr(Kinne
Tr(K3 (nner)
<n
(53)
(IKKinerr)
X1 (o (nner)
with probability greater than 1/2. Now fix d E (0, 1). On the other hand by Theorem C.5 with
1/4 have that if m 2 A llog(nn then with probability at least 3/4 that
5)2 TxXXXT)
Tr(Kinner)
Tr(XX=) 1- (XX")
(54)
4
(XX
A1 (Kinner)
Thus if we set m = max( 4
g2 log(4n), M) we have with probability at least 3/4 - 1/2 = 1/4 that 53 and (54) hold simultaneously. In this case we have that
(1 5)2 (xXX
Tr(K
4 Tr(XX")
(XX)) 7
inner
<
(1-8) 8)2 X1 (XXT) +
d1 (K
DC
Note that the above argument runs through for any 17 andd (0, 1). Thus may send n) + 0+ and 8 - 0+ in the above inequality to get
1 (XX")
(r DO
)
Tr(XX")
<
4 A (XT)
\ (K
XxXXTT)
innrr
44

---

Published as a conference paper at ICLR 2023
We thus have the following corollary about the conditioning of the analytical NTK. Corollary C.18. Let ((x) = (RLUUx) and assume X o O. Ler K E uxx be the analytical NTK, i.e.
( = X X ((x;, w))d' w))l.
Then
An K Koo
inner
4
x1 K
innnrr
71
C.3 EXPERIMENTAL VALIDATION OF RESULTS ON THE NTK SPECTRUM
NTK Spedtrmm Caltech111 Depth-2
Spectrum: Gaussion data, Depthr2
Activation
Normazzed Maghitule
tatt Inear
10
NTK Spectrum: Caltech101 Depth-5
NTK Spectrum: Gaussian data, Depthr5
10
Nomalzed Magnitude
10"
10
10
100
100
Eigenwatue Index
Eigenvatue Index
Figure (NTK Spectrum for CNNs) We plot the normalized eigenvalues >p/A1 of the NTK Gram matrix K and the data Gram matrix XX" for Caltech101 and isotropic Gaussian datasets. To compute the NTK, we randomly initialize convolutional neural networks of depth 2 and with 100 channels per layer. We use the standard parameterization and Pytorch's '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 the mean across 10 trials while the transparent part corresponds to the 95% confidence interval.
NTK Spectrum: ReLU
NTK Spectrum: Tanh
NTK Spectrum: Gaussian
0.0375/ 0.0375/-14891 144891
109
1.755.30 -3M
10
05.466 t1 Gaussian
Eigenvalue
ReLU
Elgenvalue
Tanh
Eigevvalue
10
10:
10
30-10
10-11
5.
10-18
10-16
1000 Eigenvalue Index I
200
600
Eigenvalue Index
Eigenvalue Index
Figure 4: (Asymptotic NTK Spectrum) NTK spectrum of two-layer fully connected networks with ReLU, Tanh and Gaussian activations under the NTK parameterization. The orange curve the experimental eigenvalue. The blue curves in the left shows the regression fit for the experimental cigenvalues as a function eigenvalue index in the form of X = at-b where a and are unknown parameters determined by regression. The blue curves in the middle shows the regression fit for the experimental eigenvalues in the form of A = at -.75, The blue curves in the right shows the regression fit for the experimental eigenvalues in the form of X = at50055
We experimentally test the theory developed in Section and its implications by analyzing the spectrum the NTK for both fully connected neural network architectures (FCNNs), the results of which are displayed in Figure and also convolutional neural network architectures (CNNs), shown
45

---

Published as a conference paper at ICLR 2023
in Figure For the feedforward architectures consider networks of depth and 5 with the width of all layers being set at 500. With regard to the activation function we test linear, ReLU and Tanh, and in terms of initialization practice and is the default in PyTorcc (Paszke et al. 2019). For the convolutional architectures we again consider depths 2 and 5, with each layer consisting of 100 channels with the filter size set to 5x5. In terms of data, we consider 40x40 patches from both real world images, generated by applying Pytorch's ss RandomRes sizedCrop transform a random batch of Caltech101 images (Li et al. 2022). as well as synthetic images corresponding to isotropic Gaussian vectors. The batch sized is fixed at 200 and we plot only the first 100 normalized eigenvalues. Each experiment was repeated 10 times. Finally, compute the NTK we use the functorch module in PyTorch using an algorithmic approach inspired by Novak et al. (2022).
Kaiming uniform (He et al., 2013), which is very common in
The results for convolutional neural networks show the same trends as observed in feedforward neu- ral networks, which we discussed in Section[4.1] In particular, we again observe the dominant outlier eigenvalue, which increases with both depth and the size of the Gaussian mean of the activation. We also again see that the NTK spectrum inherits its structure from the data, i.c., is skewed for skewed data or relatively flat for isotropic Gaussian data. Finally, also see that the spectrum for Tanh is closer to the spectrum for the linear activation when compared with the ReLU spectrum. In terms of differences between the CNN and FCNN experiments, we observe that the spread of the 95% con- fidence interval is slightly larger for convolutional nets, implying a slightly larger variance between trials. We remark that this is likely attributable to the fact that there are only 100 channels in each layer and by increasing this quantity we would expect the variance to reduce. In summary, despite the fact that our analysis concerned with FCNNs, it appears that the broad implications and trends also hold for CNNs. We leave a thorough study of the NTK spectrum for CNNs and other network architectures to future work.
To test our theory in Section 4.2 we numerically plot the spectrum of NTK of two-layer feedforward
networks with Rel.U, Tanh, and Gaussian activations Figure 4 The input data are uniformly drawn from S Notice that when d 2, @(e2/2). Then Corollary 4.7 shows that for the
ReLU activation A - (((-3/2), for the Tanh activation de- O (E-3/4 exp( (xpp--5e/44) ())))) and for the
Gaussian activation A 0(E-1/22 /²/3, These theoretical decay rates for the NTK spectrum
verified by the experimental results in Figure
C.4 ANALYSIS OF THE LOWER SPECTRUM: UNIFORM DATA
Theorem 4.6. (Azevedo Menegatto 2013)) Let F denote the gamma function. Suppose that the
training data are uniformly sampled from the unit hypersphere Sr. d 2 2. If the dot-product kernel
function has the expansion K K(#1, x22 = Ep cp(x1, x2), where cp 2 0, then the eigenvalue of every spherical harmonic of frequency k given by
4/2 b
T(p + 1))())((++))
2
Cp T(p k 1) k+1 + k + d/2)
p2k p k even
Proof. Let O(t)
Ep=0 cp then K ((x),x2)= = (((x1,)2)) According to Funk Hecke theorem
00
Basri et al. 2019
Section 4.2), we have
A = vol(gd- S" 0(t))..(t)(11 d=2 dt,
(55)
where Vol(S polynomial, given by
4/2 T(d/2)
is the volume of the hypersphere gd-1 and Pa.a(t) is the Gegenbauer
(-1)& T(d/2)
1
d 20/2 dik (1 8 P)
(t)
2 T(k + d/2) (1 12 21/2
and I' is the gamma function.
http:///woochannyyccceeeeeeeooor tangent kernels.hml
46

---

Published as a conference paper at ICLR 2023
From 55
have
[" P(t)Pk,((t(11 - -1)² dt
A Vol(B"
T(d/2) 0(1) ((1) (-1)* T(d/2) di
2m2
Tik: + dd/2) dlk (1 (3)
2
2T///2 (-1) T(d/2)
06
to dt
Σ cp
dth (1 ())t(a-2)/2ddt
(56)
r(d/2) 2 I(k + d/2)
p=0
-1
Using integration by parts, we have
dt [ 1 dik (1 - (3)
dth-1 (1 - (1-t2) -2) (2)2222
dh-1
-1 {"
-P _
to d
dtk (1 - 2))0t(d-2)/22
-P S- 10-1 d=
dth-1 (2)kt(d-2)/22))
(57)
where the last line in (57) holds because
dh-1 (1 f2)kt(d (d-))(2-2)/2 21/2 0 when
de
When < k. repeat the above procedure 57 times, we get
[" t de
d dtk (1 (1- 22)
dth (1 22)
(-1)pp
dk---1 d (1 - (2)
(-1)pp! 0.
(58)
When 2 ki repeat the above procedure 57 k times, we get
[r E0 dl
dth (1-8))-(d-)))22t- = (-11-()-1)--66-k-11) J" tp - -
1). -o-
(59)
When p k odd, t0- f0- 82 (2)++(1 is an odd function, then
[r t + (d)42d)2)/2 O.
(60)
When p is even,
| 1 (1 (2) dt 2 k0 -
(12) (12)60--11)/2 1)/2 +
p k+
B
2 k d/2
r( k+1 [ + d/2)
(61)
r (P-k+1 k+1
+ k: + +
where the beta function.
Plugging 61
58 and (60) into 59
get
1 dk
dth (1 12) (d) (d-2)/2
T( 41 (1)(((///2))))))))
(-1) - 1)...
... (p + 1)
rr - +k+d/2)
p is even and p 2 k. otherwise.
(62)
0.
47

---

Published as a conference paper at ICLR 2023
Plugging 62
into (56). get
2T
(-1)²
T(d/2)
Σ 1x ... (v- k+ 1) T( T d/2)
λR T(d/2)
2
r(k: + d/2)
T( + k + d/2)
p2k
p-k iven
7d/2
p(p 1) 1)...
1)1 (
2k-1
r( (( k+1 k + d/2)
p2k l p k even
2
T//2
T(p 1)T( () k+1)
2k-1
T(p k 1)r P k+1 + k d/2)
p2k p- issevv
Corollary C.19. Under the same setting in Theorem 4.6
1. cp = O(p ") where a 2 1. then X O O(k-d-200 22222+)).
2. cp = (veeve)) (pp==)), then A = (ven) O(k ((k-a-20t2)
3. cp O (exp (-avF)), ), then dv =0 01--411/2 exp (-avk))
4. cp 0pp (P), then Av O (k--dtlahh) and Av 52 (k 22122212-2 b)).
Proof of Corvllary C.4 part 1. We first prove d = O(k Suppose that op S Cy for
some constant C, then according to Theorem 4.6 we have
T d/2
T(p - 1)T((=
As S
Cp
2
T(p - k + + p k+1
+ k +
2
p- is even
According to Stirling's 's formula, have
2T
1 1+0 ())
T(2)
(63)
Then for any = 2 1. we can find constants C₁ and C2 such that
2x
2x
CiV
[(2)
S C21
(64)
z
Then
p-k+1
2x
p+1
p+1
2x
x 4/2 C2
p+1
1
A <
Cp
2 C2
p
2x
[p-++1
p-k+1
2x
p +k-d/2
p- +k+d/2
p-
p-k+I
+k+d/2
p-6+1
π 1/2 CCC
c²
p+1 (p + +1)
(p-b++
2h-1 C7
p
2 k1d +k+d/2
p2k
(p- (p-k k- 1o-k+1)0-ke
p-k+1 2
- k + =k+d/2)
p-k is even
+x+d/2
1/2 C2C
e 2 (p 1 1)
2 O7
1p-k+ 1)
p-b+1
p k+1 + ke + kd22)
P2 +k=d/2
i-kiseee even
4/2 2 C3C
p (p + 1jp+
(65)
C7
1p+k+1+d)+ 2tgtd
(p-k+1)
p2k
p- k is even
48

---

Published as a conference paper at ICLR 2023
We define
(p + 1)p
fa(p) (p-k+1) + 1) (p 1 d)
(66)
p+h+d
By applying the chain rule elug fa(P), we have that the derivative of fo is
(p + 1) y0+2p=
(p) = 2(p - k + 1)
p-k+1
(p + k - d 1) ptked
2a
++d
h2 d(p - k +
+ +log(1 + (p- k + 1)(p + k +
(67)
(p + 1)(p + k + 1) k+d
Let (p(p)
2a
(p+IKet&to+t) + Logg(1 + (p-RtD/etktdtT] Then ga (p) and (p( have the
k2a 40-d(p-k-t
P
same sign. Next we will show that (p(p) 2 0 for k < 2+24a
x² when is large enough.
First when p 2 k: and 8² =1-d ( (-k-1]oth+d+t)
2 1, we have
k k+d d (p) 2 k [k+1)(k++ k +d+1)
2a
log(2) 2 0,
(68)
when k is sufficiently large.
Second when p 2 k and 0 S (p- (p-x+1((tt++44)
d(pppkk11 S 1, since log (1+ 2 2 for 0 S x S 1, we have
2a
h: +
k2 - d(p k: 1)
(p)) 2
p
(p 1) + k + d + 1)
2(p k + 1)(p + k + 1)
2a
k: +d d
k² -p dp
p
(p + (p k + d d+
2p(p + k: + +
When p S "421
2²
we have k2 - dp d 24ap. Then
2-2 - dp
24ap
Gap
k+d
4p(p + +
4p(p + k 1)
k +
when k is sufficiently large. Also we have
k2 dp
24ap
60
2a
Ar(p + k +
4r(p+k+d+1)
p p
d 11
p
when & is sufficiently large.
Combining all the arguments above, we conclude that (p) 2 and (x) 2 0 when k ppp S
1.2
Then when k S x S 2424a we have
d424a
1.2
fa(p) S fa
(69)
d 24a
When p 2 2424a
12
we have
p a (p 1) 1
fa(
P-
(p 1p-k+ *+11 1)
(p + 1 + 1 + d)
p a (p + 1)
24
(0p + 1)2 222 + d(p k + 1))
k 11+++00 d)
(p + +1 &/2
k2 x2-dlp-k-1 k-p
1 +
kid p+i
(x+1)²
p a-a-
F-
22 d(p-pp-k- b-1)) 1)
1)+
49

---

Published as a conference paper at ICLR 2023
2x1l
If ddp < 0, (1 k-d(ppbbbtt
2 1f. ddp-k-ppp- k+ 2 0, i.e., p S dd
(p+1)²
for sufficiently large ki, we have
2 dk -d -++1
1 k² d(p k 1) 11+
R 2
h2 d(
A.a
h + 1)
1
2424a
A2
+ 1)2
24244
48a(d d + 24a)
2d
k-2
42
48ald424u)
(8-(4-) 2d
2
27
which is constant independent of k. Then for p 2
we have
2+24a
48ald+246) 2d
fa(p) S e
p
pa-z
(70)
Finally we have
A = 2n 2/2
Σ
Sa(p)
C7
p2k
k is even
0
Σ
+ + Σ
fa(p)
kSPS
p2 I=246
p-
p-k even
0
1.2
+++1 ++11 fa
122
(d424c)
p
d 24a
d + 24a
P2 74216
p- is even
0
k.2
+ 1
(8add+25a)
k-2
-a-
+
18a(4436a)
a - 1 d + 24a -1)
122
1-a- y
+ 24a
d 24a
= 0 (d-2++-))2)
Next prove Tu
22 d220+2). Since co nonnegative and cp O(p have that
Cp 2 C'p-a for some constant C² Then we have
d/2
r(p () k+1
x 2
C'p
(71)
l(p k+ + 1)r( + +k+d/2)
P2 is
According to Stirling's formula
and
64
using the similar argument as
65
we have
2x
p+l
p+1
2
d 2 Σ Cp
4/2 C2
p+1
2 C2
p k+1
kil +k+d/2
p-k+1 +
4k-4/2
D2k p- k even
2x p-k++
2x
p-
+ d/4
(72)
2/ 25 C7C CCC
p (p + 1) 10+
Σ
(73)
C
p ktl
(p + 1e + + d) 1tk
(p-k
p>k
p- R is even
> 2x d/2 $0eECfC
Σ
fa(p),
(74)
C2
P2k²
p- is even
50

---

Published as a conference paper at ICLR 2023
where fp( is defined in 666)
When p 2 k2, we have
p a (p 1)8+3
fa(D)
(p + k + 1 + d) P-k+d
(p 1p-k+ k+1 1)
p a (p 1)
(p+h+1+d) 24
((D + 1)2 122 + d(p - k + 1))
(p 1p+1) -
2k+d-1
(1 x2 12-d(p-h-1) (p+1)3
(1+
k+d p+1
For sufficiently large k, k2 - d(p - k + 1) < O. Then we have
p=++1
11)1
1 Lal 6:14), p-k+1
(1 k.2 -_-2pppp- dpp-k+ x+11
k22 d(p- - k k 1)
2 k41)
(p4
(p 1)2
(p+1)
2+dpp-ht1) p-k-1
5 e
112
dp S e
c
which is a constant independent of ks Also, for sufficiently large k we have
2k+d-1
2
(I ++
1: + d
k +
1
p p+1 1
p+1
kld 2 1 epll
422 2
=
Then for p 2 k2, we have fp) 2e e (p+ 4.
Finally we have
d 2 27 27d/22 27 C9C
Σ fa(p)
(75)
C₃
p2
p- is even
> 6/2 6/2 2f0
Σ
(p--(p+1)-er
(76)
C2
p2ka
p- even
CfC 2n
(1:2 + 22) 2
(77)
C2
2(a + 1)
Q(k 2kkk-d22-2 2-20
(78)
Overall, we have d = O(k ((k-
Proof of Corollary C.4 part 2. It is easy to verify that X = when is even because Cp = 0 when p 2 l and p- k is even. When l is odd, the proof of Theorem stil applies.
Proof of Corollary C.4 part 3. Since Cp = O (exp (-a/p)), we have that Cp S Cv for some
constant C. Similar to 65 we have
b 2 4/2 C 4/2
RVP (p + 1)
Σ
(79)
C2
(p (p-k 1)) (p+ ks + 1+ d) 24
p k is even
51

---

Published as a conference paper at ICLR 2023
Use the definition in 666 and let O, we have
(p + 1)
fo(p)
(80)
E+
(p- k +
(p+k+++d) d)
Then according to (69) and (7).. for sufficiently large k we have fo(p) - fo
k2
when k S p -
ka T and fo(p) X Cap for some constant C3 when p 2 k2 Then when k S S
we have
fo(p) S fo d S C3 (()
When p 4.2 we have fo(p) s Csp $ 03 1
Overall,
for all p 2 h; we have
122 fo(D) S C3
(81)
Then we have
S 2nT 0/2 220303C
Ae
e fo(p)
(82)
C7
p2kk
is oven
< 2nT 0/2 3
12
e e-op
(83)
07
p2k
p p-k even
2/2 2 2
C2C3
122)
-
2e ao-aak---
(av - 11
S
6/2
(84)
C9
d
a²
o 1-2 cxp (-avk))
(85)
Proof of Corollary C.4, part 4. Since ep 0pp2/2a-P), we have that co S Cp for some
constant C. Similar to 665) we have
pl/2a a P (p + 1)p+
du < 2n
2/2/22 4/2
(86)
C7
(p-k +1)
(p+ k: +1 1+d)
k
Use the definition in 66 and let a 0. we have
(p 1)
fo(p)
(87)
(p - k 1) (p+++1+d)) d)
422 Then according to (69) and 70 for sufficiently large k. we have folD) S fo d p S 12 & and fo(p) < Cap # for some constant C3 when p 2 2a
when S
J. Then when h S p S 1a we
1/2
&
have 1/2 fo()) 2 p2 1/ fo
S C3
When p 2 12 we have 1/2 fo( s
k2 d 12 s CCss
Overall, for all p 2 k. we have
1.2
(2(()) S SC3
(88)
d
52

---

Published as a conference paper at ICLR 2023
Then we have
2t
Ta v 2nh 1/2
2m
plaa--fll
(89)
C9
p2k k p- oven
28 C
122
$ 2/2
a
(90)
09
p- even
S 2/2 2
$ C3O3C
1:2
-
1
(k-1)
(91)
C2
log a
o (h d+1 a +).
(92)
On the other hand, since cp = 0 a P), we have that cp 2 C'p212a for some constant C². Similar to (3). we have
2 2n 1/2 2 d C/C"
pl p (p + 1)
2/2
Σ
(93)
C
FINTE
(p-k+1)
(p + + 1 d)
p2k
p- is even
d C²C"
11/2a (k + 1) x+
2x 4/2
(94)
C
(k (k-Ki k +
(k k + 1
k 2-4/2+1a-* (k 1)*
=Q
(95)
+++++++++ d)*
Since (k: + 1)ah = k* +1 = Ok**). Similarly, (k + k + 1 d). (((2k)*). Then we have
k- k-d/2-1 a x: (k 1)²²
A+ = Ω
(96)
(k+ k + 1 + d)*
h- -kk
Ω
(97)
(2k)²
Ω
k 6-d/2+12-- k
(98)
For the NTK of a two-layer ReLU network with % > 0, then according to Lemma 3.2 we have
Cp = Kp.2 = Op -32) Therefore using Corollary 4.7 Ax O(k -()= Notice here that refers to the frequency, and the number of spherical harmonics of frequency at most k is ((dd). Therefore, for the fth largest eigenvalue >o we have A = ((g-(d+1)/d) This rate agrees with Basri et al. (2019) and Velikanov & Yarotsky (202I). For the NTK of two-layer ReLU network with No 0. the eigenvalues corresponding to the even frequencies are O, which also agrees with Basri 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 smaller RKHS, Corollary 4.7 demonstrates that using ReLU results in a larger RKHS relative to using either Tanh Gaussian activations, We numerically illustrate Corollary 4.7 in Figure 4 Appendix
C.5 ANALYSIS OF THE LOWER SPECTRUM: NON-UNIFORM DATA
The purpose of this section is to prove a formal version of Theorem 4.8 In order to prove this result first need the following lemma.
Lemma C.20. Let the coefficients (c,)g0, with Cj E Rzz for all j E Zzo be such that the series
ES= Gpp converges for all p E 11,, Given data matrix X E RRud with ||x=|| for all
53

---

Published as a conference paper at ICLR 2023
i [n]. define rank(X) 2 2 and the gram matrix G == XX". Consider the kernel matrix
nk
cG
5=0
For arbitrary mn E 221, let the eigenvalue index satisfy n 2 > rank (Hm), where Hmm 2i=0 og G. Then
| mm
(
Σ
(99)
Proof. We start our analysis by considering A (nK) for some arbitrary k E Ngn. Let
H ==
Σ oj
G
f=0
T Σ c2
be the m-head and m-tail the Hermite expansion of nl: clearly nK = H. + Tm for any E N. Recall that a constant matrix is symmetric and positive semi-definite, furthermore, by the Schur product theorem, the Hadamard product two positive semi-definite matrices is positive semi-definiee As a result, G is symmetric and positive semi-definite for all j E Zzo and therefore
Hm and Tm are also symmetric positive semi-definite matrices. From Weyl's inequality (Weyl 1912
Satz 1) it follows that
mA (K) S (H.)) (Tm)
(100)
In order to upper bound A (T observe, as Tm is square, symmetric and positive semi-definite, that (Tm) = m/ Using the non-negativity of the coefficients (c,), and the triangle inequal- ity we have
A1 (Tm)=
=
Σ G
<
Σ j=m
cj
|oy
j=m
By the assumptions of the lemma [G] and therefore [G] 1 for all j E Zzo. Furthermore, for any pair of positive semi-definite matrices A, B E Rax= and A: [n]
A1 + B) < max max (B)
(101)
*E(n]
Schur (111)). Therefore, as maxie[m] G 1,
|
o (o
GoU-1))
for all j N. As result
A (T
< Co Σ
j=m
Finally, we now turn our attention to the analysis of X (H.). Upper bounding a small eigenvalue is typically challenging, however, the problem simplifies when and & exceeds the rank of H,, as is assumed here, as this trivially implies Au (H.m) = 0. Therefore, for (ann(Hm)))
Ak(K)=
Cj
Y
j=m
as claimed.
In order to use Lemma C.20 we require an upper bound on the rank of H To this end we provide
Lemma C.21
54

---

Published as a conference paper at ICLR 2023
Lemma C.21. Let G R=x" be symmetric, positive semi semi- definite matrix of rank 2 $ Define Hm E Raxx as
d.
H
(102)
1=
where (c)) is sequence of real coefficients. Then
rank (Hm) $1 + min(r 1, 1 (2e))
2e
(103)
ma - r}
- (m-1)--1
Proof. As G is a symmetric and positive semi-definite matrix, its eigenvalues are real and non- negative and eigenvectors are orthogonal. Let (v:)==1 be set of orthogonal eigenvectors for G and the eigenvalue associated with v, E R". Then G may be written as sum of rank one matrices as follows,
G= Σ xMV.
As the Hadamard product is commutative, associative and distributive over addition, for any j Zzo G can also be expressed of rank matrices,
Oj
G
Σ
nvv!
Σ Enava
r
Th V.vi
Σ no VEN
Ti Tia "r (vi, 4 (vi, の (vi,v?)
Toe The ' (Vi1
By
① Vi2 1... (v, 3 vi2 o ....0vv.'''
Note the fourth equality in the above follows from v.v.' = V @ V, and an application of the mixed- product property the Hadamard product. matrix rank is sub-additive, the rank of GoI less than or equal to the number of distinct rank-one matrix summands. This quantity in turn is equal to the number vectors of the form (v,, @ Vi, O ... O Vi,), where i1, .2, i [r]. This in turn is equivalent to computing the number of j-combinations with repetition from objects. Via a stars and bars argument this is equal to (r+j-1) (+ It therefore follows that
+ - r-
rank 03
c(r + - 1)
r-1
r-1
j
5 r-
1+ r-1
5 m1
8jgh-1 + 8p2n-1
j
r-
55

---

Published as a conference paper at ICLR 2023
The rank of H., therefore be bounded via subadditivity of the rank
m
rank(Hm)) rank
Og
Σ
Ø=1
m=1
S1+
rank (GO))
/=1
(104)
( r- (1=1)²²
r-1
$1 (2e)"-1
<1 + min 1, m 12)
2e
r-1 (m 1)r-1
+ max m r}
r-
As our goal here to characterize the small eigenvalues, then as n grows we need both and therefore m to grow well. As result we will therefore be operating in the regime where m > r. To this end we provide the following corollary.
Corollary C.22. Under the conditions and setup Lemma C.21 with 2 2 7 then rank(Hm)) < 2mn"
Proof. I 2 >>> 2e + then -1 >>> 2e. As a result from Lemma
C.21
rank (m)) < + (r 1)(2))) r-1 + (m -r) (
(
2e
(m 1)r-1
<r(2e)=-1 (m 1)"
2m
as claimed.
Corollary C.22 implies for any l: 2 2m", ,, le I n that we can apply Lemma C.20 to upper bound the size of the kth eigenvalue. Our goal is to upper bound the decay of the smallest eigenvalue. To this end, and in order to make our bounds as tight as possible, we therefore choose the truncation point
m(n) = (n/2)1/r], note this is the largest truncation which still satisfies 2m(n)" I n. In order to state the next lemma, we introduce the following pieces of notation: with = {e: Rgo Rg0)
1/r
define U L x Zz1 + R2o as
U m) = I
Sm ((x)dr.
Lemma C.23. Given a sequence of data points (Xi)kEzz, with x, E Sd for all E Zzi, construct sequence of row-wise data matrices (Xn)neZsu Xn E Raxd with x; corresponding to the ith of X,- The corresponding sequence of gram matrices m(n) : [n/22//r(m) where r(n) := rank(X (x)) and suppose for all sufficiently large n that m(n) 2 r(n) 2 7. Let the coefficients (cg)3= with Cj E Rz0 for all j E Zoo be such that 1) the series ΣØ= cip' converges for all E [-1, and 2) (c))²= O((()), where L satisfies (L, m(n)) co for all n and is monotonically decreasing. Consider the sequence of
denote Gn
XTT Let
kernel matrices indexed by and defined as
nK,, = Σ G
1=0
With v Zz1 - Zz1 suppose G @m(())
On then
(kn) O(n -1n) m(()))
(105)
56

---

Published as a conference paper at ICLR 2023
Proof. By the assumptions of the Lemma we may apply Lemma C.20 and Corollary C.22 results in
which
Gn
@m(())
An (k
Σ
Cj
Onn u(())
Cj.
/=m(n)
z=m(n)
Additionally, as (cy), = O({()) then
9
An (Kn)
n [(n) Σ E(i)
j=m(n)
n v(x)
((x)dx)
m(n)-1
O (n (n-r(m) U m()))
as claimed.
Based on Lemma C.20 we provide Theorem C.24 which considers three specific scenarios for the decay of the power series coefficients inspired by Lemmal 3.2
Theorem C.24. In the same setting, and also under the same assumptions as in Lemma
C.23 then
1. cp 0pp ") with r(n) + for all n E Zzo then Xn (K,,) O (n 7m)
2. if cp Ole-avP), then Xn \n(Kn) o (n exp (-a'n )) for any d' <
a2 0222/2((m)
3. cp ape-ap), then An(K,, O (expp (-a'nrèu)) for any d < <02-1/2r(1)
Proof. First, as [rnli $ 1 then
G (o)()))]
Trace Gmm(n)
=
n
n
Therefore, to recover the three results listed now apply Lemma C.23 with v(n) 0. First, to prove 1., under the assumption {(x) = x with a > 0 then
do (m(n) 1) +++1
ml
a
As result
(K,,) = 0 Pim
To prove ii), under the assumption ((x) e: avv with > then
f mm(m)-1
eav== 2exp(-a( (aaaammmmm (m(m) 1) ()aammm)) 1 1+11
a²
As result
An (K,.) O (0
nt exp (-a' (-a'nzrix) n
for any a' < a2 1/2r(n,, Finally, to prove iii), under the assumption ((x) = e -a with a > 0 then
f c az dx===== exp( exp(-a(m(n)) -
m(n)-1
a
Therefore
Xa (K,,) 0 (oxp (-o'nrd))
again for any a' <2211/2(())
57

---

Published as a conference paper at ICLR 2023
Unfortunately, the curse of dimensionality is clearly present in these results due to the 1/r(n) factor in the exponents of n. However, although perhaps somewhat loose we emphasize that these results certainly far from trivial. In particular, while trivially we know that A, (K,) Tr(KK,)/n O(--1), in contrast, even the weakest result concerning the power law decay our result clear improvement long
r(n) + 1. For the other settings, i.e., those specified in 2. and 3., results are significantly stronger.
58


Reviews:
[{"review_id": "HY29zqaxBW", "reviewer": "Reviewer_rRGi", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the infinite-width NTK in the setting of general activation functions and datasets. It is shown that, under the standard Gaussian initialization, the NTK can be expressed as a power series in the data Gram matrix elements. The paper then discusses the coefficients of this series and its convergence for a few common activations. After that the authors discuss spectral properties of kernels that can be represented by such series. In particular, the paper give bounds on the efficient rank of the NTK and the convergence rates of its eigenvalues in several scenarios.", "summary_of_the_review": "An interesting work developing a new and potentially important analytic method. However, the experimental part is weak, and there are some issues with the exposition.", "strength_and_weaknesses": "Strengths\n-------------\nI think that the paper develops a new and interesting general analytic approach to the study of NTK. The idea of a power expansion of the NTK appearing in main theorem 3.1 seems new and important to me. Importantly, this approach is applicable to a very large class of activations and generic data sets. As the authors show, the coefficients of this power expansion can be explicitly computed to some extent, and can be related to the spectral properties of the NTK, in particular the eigenvalue convergence rate. The obtained spectral results agree with some earlier results and provide a different perspective on them. All this opens up potential new ways for NTK analysis. \n\nWeaknesses\n-----------------\n1. The experimental part of the paper seems very weak to me. There are only a few experiments with real data in section 4.1, and I don't quite see what these experiments are supposed to demonstrate. The authors observe that there is a long tail of small eigenvalues, but such long tails are common, and it is not clear how this observation confirms the developed theoretical picture. On the other hand, there are some obvious interesting features in Figure 2 that the authors don't comment on, despite there apparent relevance to the theoretical results. In particular, the curves for the activation Tanh almost match the curves for Data - is it because Tanh has a very fast decaying power expansion? Would this also be so if Tanh was replaced by the trivial linear activation? Why is there a constant difference between the Tanh and Data curves in the case of Depth-5 MNIST? Is the slope of the ReLU curve smaller than the slope of Data/Tanh because the coefficient decay of ReLU dominates the data eigenvalue decay? I think that the experimental part and its discussion could have been much more prominent. \n\n2. I didn't understand some statements. In particular, it's not clear to me under which conditions Observation 4.2 holds and why. The notation \\Omega(1) and O(1) here is confusing (what is the respective parameter?); I would suggest to write this in a more explicit form. I also don't understand the statement of Theorem 4.8. Is r(n) here an arbitrary function?  Is K_n some n x n submatrix of K and \\lambda_n(K_n) its lowest eigenvalue?       ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "5_m3qU6Dx8a", "reviewer": "Reviewer_VHSv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies a power series of the neural tangent kernel (NTK) for an infinitely wide fully-connected neural network when inputs are on the unit sphere. Using the power series, the authors analyze the spectrum of the NTK. In particular, they focus on the effective rank of the NTK matrix, defined as the ratio of the trace to the leading eigenvalue, and compare it to that of the data Gram matrix. For shallow ReLU network, the effective rank of the NTK is a constant multiple of that of the data Gram matrix. Finally, they provide the lower part of the eigenvalues using the spherical harmonic analysis.", "summary_of_the_review": "The results of this paper are incremental and the motivation of the effective rank ratio of the NTK is unclear.", "strength_and_weaknesses": "Strength:\n- This paper provides a power series of fully-connected NTK (Theorem 3.1) when inputs are normalized. This can be obtained by Hermite expansion of the activation and polynomial composition. Hence, once the coefficients of the series of NTK is computed (which is data-independent), then the NTK is computed by applying some polynomial to each entry of the data Gram matrix. \n\n- The authors make use of the power series of the NTK to analyze its effective rank. They particularly compute the ratio of effective ranks between the NTK and the data Gram matrix, and show that this can be small for common activations (e.g., ReLU).\n\nWeakness:\n- The main focus of the spectrum analysis part is the effective rank. The authors mention that it can quantify some counts of eigenvalues of the NTK. But, it needs more comprehensive motivation why the effective rank analysis is meaningful. And what is expected when the effective rank of the NTK is close to that of the data Gram matrix?\n\n  One question is that Figure 2 looks that the spectrum of the NTK with ``tanh’’ activation matches the data Gram matrix more than that of the ReLU. However, in practice, it is well-known that the ReLU activation performs better than the tanh in terms of training and test (for both CIFAR-10 and MNIST). It is uncertain that such spectrum is meaningful to analyze the NTK. \n\n- The paper should add/edit more related works. The relationship to the Hermite expansion was originally studied by [1], which actually characterizes the NTK for shallow networks. There is also rich literature studying the Hermite polynomials for the NTK, e.g., [2,3,4].\n\n- The paper entirely assumes that inputs are normalized, which can be fairly unrealistic because practical datasets are not. Under this assumption, I think the contributions are quite incremental, which can be derived from the simple composition of power series (coefficients are obtained from the Hermite expansion). For homogeneous activation (e.g., ReLU), the results can be easily extended to the entire R^d (also studied in [3]). But, generally, it seems that the results can be more complicated and different.\n\n- Moreover, the results of this paper are limited only to the ``fully-connected’’ neural network. Practical usage of the NTK is also related to the convolutional neural networks or more results on modern architectures would improve the results. \n\n[1] Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity. In NeurIPS, 2016.\n\n[2] James B Simon, Sajant Anand, and Michael R DeWeese. Reverse Engineering the Neural Tangent Kernel. In ICML, 2022.\n\n[3] Insu Han, Amir Zandieh, Jaehoon Lee, Roman Novak, Lechao Xiao and Amin Karbasi.Fast Neural Kernel Embeddings for General Activations. In NeurIPS, 2022.\n\n[4] Lokhande, Vishnu Suresh, Songwong Tasneeyapant, Abhay Venkatesh, Sathya N. Ravi, and Vikas Singh. Generating accurate pseudo-labels in semi-supervised learning and avoiding overconfident predictions via Hermite polynomial activations. In CVPR, 2020.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "0wCAYkscYg6", "reviewer": "Reviewer_jD66", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents theoretical results on the eigenvalue spectrum of the neural tangent kernel (NTK) based on Hermite polynomial expansions. The results enable expressing the NTK matrices for neural networks of arbitrary depth via power series expansions based on the data points matrix. Bounds on the eigenvalues of the NTK for popular activation functions are also provided.", "summary_of_the_review": "The paper presents an interesting theoretical analysis deriving bounds for the NTK spectrum decay and relating it to the data eigenspectrum. The results practical interpretation is provided and empirical results to demonstrate theoretical insights in practice are also presented. The approach is novel compared to previous work, and the results are more broadly applicable.", "strength_and_weaknesses": "### Strengths\n* The analysis is mathematically rigorous.\n* A discussion on their practical interpretation follows each of the main results.\n* The approach taken in the analysis is relatively simpler than pre-existing attempts on deriving general results for the NTK spectrum.\n* The power series formulation (Thr. 3.1) and in special the eigenvalue results (Lem. 3.2, Cor. 4.7, Thr. 4.8) have the potential to impact many applications of NTK-based convergence analysis of deep learning frameworks.\n* Empirical results practically validating theoretical insights are also presented (Fig. 1 & 2)\n\n### Weaknesses\n* In Assumption 2, \"The hyperparameters of the network satisfy $\\gamma_w^2 + \\gamma_b^2 = 1$ ... and $\\sigma_b^2 = 1 - \\sigma_w^2 \\mathbb{E}_{Z\\sim\\mathcal{N}(0,1)}[\\phi(Z)]$\" seems somewhat restrictive to me, and this part of the assumption hasn't been discussed in the paragraph following it.\n* Some notation definitions are missing in the main text, e.g.: $r(n)$, $h_k$", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster