Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networks

Introduction

Recent progress in our theoretical understanding of neural networks has connected their training and generalization to two associated kernel matrices. The first is the Conjugate Kernel (CK) or the equivalent Gaussian process kernel . This is the gram matrix of the derived features produced by the final hidden layer of the network. The network predictions are linear in these derived features, and the CK governs training and generalization in this linear model.

The second is the Neural Tangent Kernel (NTK) . This is the gram matrix of the Jacobian of in-sample predictions with respect to the network weights, and was introduced to study full network training. Under gradient-flow training dynamics, the in-sample predictions follow a differential equation governed by the NTK. We provide a brief review of these matrices in Section 2.1.

The spectral decompositions of these kernel matrices are related to training and generalization properties of the underlying network. Training occurs most rapidly along the eigenvectors of the largest eigenvalues , and the eigenvalue distribution may determine the trainability of the model and the extent of implicit bias towards simpler functions . It is thus of interest to understand the spectral properties of these matrices, both at random initialization and over the course of training.

In this work, we apply techniques of random matrix theory to derive an exact asymptotic characterization of the eigenvalue distributions of the CK and NTK at random initialization, in a multi-layer feedforward network architecture. We study a “linear-width” asymptotic regime, where each hidden layer has width proportional to the training sample size. We impose an assumption of approximate pairwise orthogonality for the training samples, which encompasses general settings of independent samples that need not have independent entries.

We show that the eigenvalue distributions for both the CK and the NTK converge to deterministic limits, depending on the limiting eigenvalue distribution of the training data. The limit distribution for the CK at each intermediate hidden layer is a Marcenko-Pastur map of a linear transformation of that of the previous layer. The NTK can be approximated by a linear combination of CK matrices, and its limiting eigenvalue distribution can be described by a recursively defined sequence of fixed-point equations that extend this Marcenko-Pastur map. We demonstrate the agreement of these asymptotic limits with the observed spectra on both synthetic and CIFAR-10 training data of moderate size.

In this linear-width asymptotic regime, feature learning occurs, and both the CK and NTK evolve over training. Although our theory pertains only to their spectra at random initialization of the weights, we conclude with an empirical examination of their spectral evolutions during training, on simple examples of learning a single neuron and learning a binary classifier for two classes in CIFAR-10. In these examples, the bulk eigenvalue distributions of the CK and NTK undergo elongations, and isolated principal components emerge that are highly predictive of the training labels. Recent theoretical work has studied the evolution of the NTK in an entrywise sense , and we believe it is an interesting open question to translate this understanding to a more spectral perspective.

2 Related literature

Many properties of the CK and NTK have been established in the limit of infinite width and fixed sample size $n$. In this limit, both the CK and the NTK at random initialization converge to fixed $n\times n$ kernel matrices. The associated random features regression models converge to kernel linear regression in the RKHS of these limit kernels. Furthermore, network training occurs in a “lazy” regime , where the NTK remains constant throughout training . Spectral properties of the CK, NTK, and Hessian of the training loss have been previously studied in this infinite-width limit in . Limitations of lazy training and these equivalent kernel regression models have been studied theoretically and empirically in , suggesting that trained neural networks of practical width are not fully described by this type of infinite-width kernel equivalence. The asymptotic behavior is different in the linear-width regime of this work: For example, for a linear activation $\sigma(x)=x$, the infinite-width limit of the CK for random weights is the input Gram matrix $X^{\top}X$, whereas its limit spectrum under linear-width asymptotics has an additional noise component from iterating the Marcenko-Pastur map.

The limit NTK spectrum for a one-hidden-layer network with i.i.d. Gaussian inputs was recently characterized in parallel work of . In particular, applied the same idea as in Lemma 3.5 below to study the Hadamard product arising in the NTK. previously studied the equivalent spectrum of a sample covariance matrix derived from the network Jacobian, which is one of two components of the Hessian of the training loss, in a slightly different setting and also for one hidden layer.

The spectra of the kernel matrices $X^{\top}X$ that we study are equivalent (up to the addition/removal of 0’s) to the spectra of the sample covariance matrices in linear regression using the features $X$. As developed in a line of recent literature including , this spectrum and the associated Stieltjes transform and resolvent are closely related to the training and generalization errors in this linear regression model. These works have collectively provided an asymptotic understanding of training and generalization error for random features regression models derived from the CK and NTK of one-hidden-layer neural networks, and related qualitative phenomena of double and multiple descent in the generalization error curves.

Background

We denote the Jacobian matrix of the network predictions with respect to the weights $\theta$ as

The Neural Tangent Kernel (NTK) is the matrix

Under gradient-flow training of the network weights $\theta$ with training loss $\|\mathbf{y}-f_{\theta}(X)\|^{2}/2$, the time evolutions of residual errors and in-sample predictions are given by

where $\theta(t)$ and $K^{\text{NTK}}(t)$ are the parameters and NTK at training time $t$ . Denoting the eigenvalues and eigenvectors of $K^{\text{NTK}}(t)$ by $(\lambda_{\alpha}(t),\mathbf{v}_{\alpha}(t))_{\alpha=1}^{n}$, and the spectral components of the residual error by $r_{\alpha}(t)=\mathbf{v}_{\alpha}(t)^{\top}(\mathbf{y}-f_{\theta(t)}(X))$, these training dynamics are expressed spectrally as

Note that these relations hold instantaneously at each training time $t$, regardless of whether $K^{\text{NTK}}(t)$ evolves or remains approximately constant over training. Hence, $\lambda_{\alpha}(t)$ controls the instantaneous rate of decay of the residual error in the direction of $\mathbf{v}_{\alpha}(t)$.

For very wide networks, $K^{\text{NTK}}$, $\lambda_{\alpha}$, and $\mathbf{v}_{\alpha}$ are all approximately constant over the entirety of training . This yields the closed-form solution $r_{\alpha}(t)\approx r_{\alpha}(0)e^{-t\lambda_{\alpha}}$, so that the in-sample predictions $f_{\theta(t)}(X)$ converge exponentially fast to the observed training labels $\mathbf{y}$, with a different exponential rate $\lambda_{\alpha}$ along each eigenvector $\mathbf{v}_{\alpha}$ of $K^{\text{NTK}}$.

2 Eigenvalue distributions, Stieltjes transforms, and the Marcenko-Pastur map

We will call this limit $\rho^{\text{MP}}_{\gamma}\boxtimes\mu$ the Marcenko-Pastur map of $\mu$ with aspect ratio $\gamma$. This distribution $\rho^{\text{MP}}_{\gamma}\boxtimes\mu$ may be defined by its Stieltjes transform $m(z)$, which solves the Marcenko-Pastur fixed point equation

Main results

The number of layers $L\geq 1$ is fixed, and $n,d_{0},d_{1},\ldots,d_{L}\to\infty$, such that

The weights $\theta=(\operatorname{vec}(W_{1}),\ldots,\operatorname{vec}(W_{L}),\mathbf{w})$ are i.i.d. and distributed as $\mathcal{N}(0,1)$.

Part (c) quantifies our assumption of approximate pairwise orthogonality of the training samples. Although not completely general, it encompasses many settings of independent samples with input dimension $d_{0}\asymp n$, including:

Non-white Gaussian inputs $\mathbf{x}_{\alpha}\sim\mathcal{N}(0,\Sigma)$, for any $\Sigma$ satisfying $\operatorname{Tr}\Sigma=1$ and $\|\Sigma\|\lesssim 1/n$.

Inputs $\mathbf{x}_{\alpha}$ drawn from certain multi-class Gaussian mixture models, in the high-dimensional asymptotic regimes that were studied in .

In particular, the limit spectral law $\mu_{0}$ in Assumption 3.2(d) can be very different from the Marcenko-Pastur spectrum that would correspond to $X$ having i.i.d. entries. This approximate orthogonality is implied by the following more technical convex concentration property, which is discussed further in . We prove this result in Appendix B.

2 Spectrum of the Conjugate Kernel

Recall the Marcenko-Pastur map (5). Let $\mu_{1},\mu_{2},\mu_{3},\ldots$ be the sequence of probability distributions on $[0,\infty)$ defined recursively by

Here, $\mu_{0}$ is the input limit spectrum in Assumption 3.2(d), $b_{\sigma}$ is defined in (7), and $(1-b_{\sigma}^{2})+b_{\sigma}^{2}\cdot\mu$ denotes the translation and rescaling of $\mu$ that is the distribution of $(1-b_{\sigma}^{2})+b_{\sigma}^{2}\lambda$ when $\lambda\sim\mu$.

Furthermore, $\|K^{\text{CK}}\|\leq C$ a.s. for a constant $C>0$ and all large $n$.

3 Spectrum of the Neural Tangent Kernel

In the neural network model (1), an application of the chain rule yields an explicit form

By this lemma, if $b_{\sigma}=0$, then $q_{0}=\ldots=q_{L-1}=0$ and the limit spectrum of $K^{\text{NTK}}$ reduces to the limit spectrum of $r_{+}\operatorname{Id}+X_{L}^{\top}X_{L}$ which is a translation of $\rho_{\gamma_{L}}^{\text{MP}}$ described in Theorem 3.4. Thus we assume in the following that $b_{\sigma}\neq 0$. Our next result provides an analytic description of the limit spectrum of $K^{\text{NTK}}$, by extending (9,10) to characterize the trace of rational functions of $X_{0}^{\top}X_{0},\ldots,X_{L}^{\top}X_{L}$ and $\operatorname{Id}$.

Specializing the function $t_{L}$ for the last layer $L$ to the values $(z_{-1},z_{0},\ldots,z_{L-1},z_{L})=(r_{+},q_{0},\ldots,q_{L-1},1)$ and $(w_{-1},w_{0},\ldots,w_{L})=(1,0,\ldots,0)$, we obtain an analytic description for the limit spectrum of $K^{\text{NTK}}$ via its Stieltjes transform.

In particular, $\operatorname{lim\;spec}K^{\text{NTK}}$ is the probability distribution with Stieltjes transform

Furthermore, $\|K^{\text{NTK}}\|\leq C$ a.s. for a constant $C>0$ and all large $n$.

4 Extension to multi-dimensional outputs and rescaled parametrizations

Theorem 3.7 pertains to a network with scalar outputs, under the “NTK-parametrization” of network weights in (1). As neural network models used in practice often have multi-dimensional outputs and may be parametrized differently for backpropagation, we state here the extension of the preceding result to a network with $k$-dimensional output and a general scaling of the weights.

Fix any $k\geq 1$. Suppose Assumption 3.2 holds, and $b_{\sigma}\neq 0$. Then $\|K^{\text{NTK}}\|\leq C$ a.s. for a constant $C>0$ and all large $n$, and $\operatorname{lim\;spec}K^{\text{NTK}}$ is the probability distribution with Stieltjes transform

Experiments

We describe in Appendix A an algorithm to numerically compute the limit spectral densities of Theorem 3.7. The computational cost is independent of the dimensions $(n,d_{0},\ldots,d_{L})$, and each limit density below was computed within a few seconds on our laptop computer. Using this procedure, we investigate the accuracy of the theoretical predictions of Theorems 3.4 and 3.7. Finally, we conclude by examining the spectra of $K^{\text{CK}}$ and $K^{\text{NTK}}$ after network training.

2 CIFAR-10 training data

We consider $n=5000$ samples randomly selected from the CIFAR-10 training set , with input dimension $d_{0}=3072$, and $L=5$ hidden layers of dimensions $d_{1}=\ldots=d_{5}=10000$. Strong principal component structure may cause the training samples to have large pairwise inner-products, which is shown in Appendix J.1. Thus, we pre-process the training samples by removing the leading 10 PCs—a few example images before and after this removal are depicted in Appendix J.3. A close agreement between the observed and limit spectra is displayed in Figure 2, for both $K^{\text{CK}}$ and $K^{\text{NTK}}$. Results without removing these leading 10 PCs are presented in Appendix J.2, where there is close agreement for $K^{\text{CK}}$ but a deviation from the theoretical prediction for $K^{\text{NTK}}$. This suggests that the approximation in Lemma 3.5 is sensitive to large but low-rank perturbations of $X$.

3 CK and NTK spectra after training

Figure 3 depicts the spectra of $K^{\text{CK}}$ and $K^{\text{NTK}}$ for the trained weights $\theta$. Intermediate layers are shown in Appendix J.4. We observe that the bulk spectra of $K^{\text{CK}}$ and $K^{\text{NTK}}$ are elongated from their random initializations. Furthermore, large outlier eigenvalues emerge in both $K^{\text{CK}}$ and $K^{\text{NTK}}$ over training. The corresponding eigenvectors are highly predictive of the training labels $\mathbf{y}$, suggesting the emergence of these eigenvectors as the primary mechanism of training in this example.

We describe in Appendix J.5 a second training example for a binary classification task on CIFAR-10, where similar qualitative phenomena are observed for the trained $K^{\text{CK}}$. This may suggest a path to understanding the learning process of deep neural networks, for future study.

Conclusion

We have provided analytic descriptions of the empirical eigenvalue distributions of the Conjugate Kernel (CK) and Neural Tangent Kernel (NTK) of large feedforward neural networks at random initialization, under a general condition for the input samples. Our work uses techniques of random matrix theory to provide an asymptotic analysis in a limiting regime where network width grows linearly with sample size. The resulting limit spectra exhibit “high-dimensional noise” that is not present in analyses of the infinite-width limit alone. This type of high-dimensional limit has been previously studied for networks with a single hidden layer, and our work develops new proof techniques to extend these characterizations to multi-layer networks, in a systematic and recursive form.

Our results contribute to the theoretical understanding of neural networks in two ways: First, an increasingly large body of literature studies the training and generalization errors of linear regression models using random features derived from the neural network CK and NTK. In the linear-width setting of our current paper, such results are typically based on asymptotic approximations for the Stieltjes transforms and resolvents of the associated kernel and covariance matrices. Our work develops theoretical tools that may enable the extension of these studies to random features regression models that are derived from deep networks with possibly many layers.

Second, the linear-width asymptotic regime may provide a simple setting for studying feature learning and neural network training outside of the “lazy” regime, and which is arguably closer to the operating regimes of neural network models in some practical applications. Our experimental results suggest interesting phenomena in the spectral evolutions of the CK and NTK that may potentially arise during training in this regime, and our theoretical characterizations of their spectra for random weights may provide a first step towards the analysis of these phenomena.

Broader Impact

This work performs theoretical analysis that aims to extend our understanding of training and generalization in multi-layer neural networks. A better theoretical understanding of training and generalization in these models may ultimately help us to (1) understand the mechanisms by which social biases may be propagated by artificial systems, and prevent this from occurring, and (2) increase the robustness and fault-tolerance of artificial systems built on such models.

Acknowledgments and Disclosure of Funding

This research is supported in part by NSF Grant DMS-1916198. We would like to thank John Lafferty and Ganlin Song for helpful discussions regarding the Neural Tangent Kernel.

References

Appendix A Numerical solution of the fixed-point equations

Set $\mathbf{z}_{L}^{(t)}=\mathbf{z}_{L}$, and compute $\mathbf{z}_{L-1}^{(t)}=\mathbf{z}_{\text{prev}}(s_{L}^{(t)},\mathbf{z}_{L}^{(t)})$, $\mathbf{z}_{L-2}^{(t)}=\mathbf{z}_{\text{prev}}(s_{L-1}^{(t)},\mathbf{z}_{L-1}^{(t)})$, etc.

Appendix B Proof of (ε,B)𝜀𝐵(\varepsilon,B)-orthonormality for independent input training samples

for a constant $c$ depending only on $c_{0}$. Applying this for $t=\sqrt{Kd\log n}$ and a union bound, with probability $1-2ne^{-cK\log n}$,

Rescaling, this shows $|\|\mathbf{x}_{\alpha}\|^{2}-1|\leq\sqrt{(K\log n)/d}$.

On the event (21), applying this for $t=\sqrt{Kd\log n}$, this probability is at most $2e^{-cK\log n}$. Taking a union bound, with probability $1-2n^{2}e^{-cK\log n}$,

Rescaling, this shows $|\mathbf{x}_{\alpha}^{\top}\mathbf{x}_{\beta}|\leq\sqrt{(K\log n)/d}$.

we have $\|\widetilde{X}\|\leq B\sqrt{d}$ on this event. Rescaling, this shows $\|X\|\leq B$.

which has mean 0. Note that integrating the tail bound (20) yields the sub-exponential condition

For any $t>0$, applying this with $\lambda=\min(t/(2Cd),c^{\prime})$ yields the sub-exponential tail bound

Now applying this for $t=(B/2)d$, and again taking a union bound over a $1/2$-net $\mathcal{N}$ of the unit ball, we have with probability $1-5^{n}\cdot e^{-cBd}$ that

Applying all of the above bounds for sufficiently large constants $K,B>0$, we obtain that these bounds hold with probability at least $1-n^{-k}$, which yields Proposition 3.3.

Appendix C Overview of proofs and preliminary lemmas

The proofs of Theorems 3.4, 3.7, and 3.8 are contained in the subsequent Appendices D–H. We provide here an outline of the argument.

conditional on the previous layers. For the Neural Tangent Kernel, given the approximation in Lemma 3.5, this will entail analyzing the Stieltjes transform

conditional on the previous layers, where $A$ is a linear combination of $X_{0}^{\top}X_{0},\ldots,X_{L-1}^{\top}X_{L-1}$, and $\operatorname{Id}$. Note that this matrix $A$ is deterministic conditional on the previous layers.

In Appendix D, we carry out a non-asymptotic analysis of $(\varepsilon,B)$-orthonormality. In particular, we show that if the deterministic input $X\equiv X_{0}$ is $(\varepsilon,B)$-orthonormal, then $X_{1}$ is $(C\varepsilon,CB)$-orthonormal with high probability, for a constant $C>0$ depending only on $\lambda_{\sigma}$. Note that we require the fourth technical condition

In Appendix E, we carry out the analysis of the trace

In Appendix G, we prove Theorem 3.7 on the NTK. Our analysis reduces the trace of any linear combination of $X_{0}^{\top}X_{0},\ldots,X_{L}^{\top}X_{L}$ and $\operatorname{Id}$ to the trace of a more general rational function of $X_{0}^{\top}X_{0},\ldots,X_{L-1}^{\top}X_{L-1}$ and $\operatorname{Id}$ in the previous layer. In order to close the inductive loop, we analyze the trace of such a rational function across layers, and show that it may be characterized by the recursive fixed-point equations (12) and (13). In Appendix G, we also establish the approximation in Lemma 3.5 and the existence and uniqueness of the fixed point to (12).

Finally, in Appendix H, we prove Theorem 3.8, which is a minor extension of Theorem 3.7.

Let us collect here a few basic results, which we will use in the subsequent sections.

Under Assumption 3.2(b), the constants $a_{\sigma}$ and $b_{\sigma}$ in (7) satisfy

For a universal constant $C>0$, the activation function $\sigma$ satisfies

It is clear from definition that $a_{\sigma}\leq\lambda_{\sigma}^{2}$. By the Gaussian Poincaré inequality,

By Gaussian integration-by-parts and Cauchy-Schwarz,

(the last inequality applying $\lambda_{\sigma}\geq 1$). Then $|\sigma(x)|\leq|\sigma(0)|+\lambda_{\sigma}|x|\leq\lambda_{\sigma}(|x|+C)$. ∎

Appendix D Propagation of approximate pairwise orthogonality

Note that $\widecheck{X}$ has i.i.d. rows with distribution $\sigma(\mathbf{w}^{\top}X)/\sqrt{\check{d}}$, where $\mathbf{w}\sim\mathcal{N}(0,\operatorname{Id})$. Define the second-moment matrix of $\widecheck{X}$ by

where the expectations are over the standard Gaussian matrix $W$ and standard Gaussian vector $\mathbf{w}$. Let $\Phi_{\alpha\beta}$ denote the $(\alpha,\beta)$ entry of $\Phi$ for any $\alpha,\beta\in[n]$. We show in this section the following result.

Suppose $X$ is $(\varepsilon,B)$-orthonormal where $\varepsilon<1/\lambda_{\sigma}$. Then for universal constants $C,c>0$, with probability at least $1-2n^{2}e^{-c\check{d}\varepsilon^{2}}-3e^{-cn}$, the matrix $\widecheck{X}$ remains $(\widecheck{\varepsilon},\widecheck{B})$-orthonormal with

In the remainder of this section, we prove Lemma D.1. We divide the proof into Lemmas D.3, D.4, and D.5 below, which check the individual requirements for $(\widecheck{\varepsilon},\widecheck{B})$-orthonormality of $\widecheck{X}$. We denote by $C,C^{\prime},c,c^{\prime}>0$ universal constants that may change from instance to instance.

If $X$ is $(\varepsilon,B)$-orthonormal where $\varepsilon<1/\lambda_{\sigma}$, then for universal constants $C,c>0$:

With probability at least $1-2n^{2}e^{-c\check{d}\varepsilon^{2}}$, simultaneously for all $\alpha\neq\beta\in[n]$, the columns of $\widecheck{X}$ satisfy

Note that (26) establishes an approximation which is second-order in $\varepsilon$—this will be important in our later arguments which approximate $\Phi$ in Frobenius norm.

For part (a), observe that $(\zeta_{\alpha},\zeta_{\beta})\equiv(\mathbf{w}^{\top}\mathbf{x}_{\alpha},\mathbf{w}^{\top}\mathbf{x}_{\beta})$ is bivariate Gaussian, with mean 0 and covariance

where $\Delta$ is entrywise bounded by $\varepsilon$. Then performing a Gram-Schmidt orthogonalization procedure, for some independent standard Gaussian variables $\xi_{\alpha},\xi_{\beta}\sim\mathcal{N}(0,1)$, we have

By a Taylor expansion of $\sigma(\zeta)$ around $\zeta=\xi$, there exists a random variable $\eta$ between $\zeta$ and $\xi$ such that

where this remainder has magnitude at most $C\lambda_{\sigma}^{2}\varepsilon^{2}$. For the first term, substituting (29) and applying independence of $\xi_{\alpha}$ and $\xi_{\beta}$, we have

For part (b), let $\mathbf{w}_{k}^{\top}$ be the $k^{\text{th}}$ row of $W$. Then by definition of $\widecheck{X}$, for any $\alpha,\beta\in[n]$ (including $\alpha=\beta$),

Applying Bernstein’s inequality (see [53, Theorem 2.8.1]), for a universal constant $c>0$ and any $t>0$,

Applying this for $t=\lambda_{\sigma}^{2}\varepsilon$ and taking a union bound over all $\alpha,\beta\in[n]$, we get

If $X$ is $(\varepsilon,B)$-orthonormal where $\varepsilon<1/\lambda_{\sigma}$, then for universal constants $C,c>0$:

$\|\Phi\|\leq C\lambda_{\sigma}^{2}B^{2}$.

With probability at least $1-2e^{-cn}$, \|\widecheck{X}\|\leq C\Big{(}1+\sqrt{n/\check{d}}\Big{)}\lambda_{\sigma}B.

where the first term on the right is $\Phi$. Then

the last inequality using the final condition of $(\varepsilon,B)$-orthonormality in Definition 3.1. This establishes part (a).

Note that the complementary event $\|\widecheck{X}^{\top}\widecheck{X}-\Phi\|\leq\max(\delta,\delta^{2})\|\Phi\|$ implies

for a constant $C^{\prime}>0$. Then choosing $t=\sqrt{n}$ and applying part (a) yields part (b). ∎

If $X$ is $(\varepsilon,B)$-orthonormal where $\varepsilon<1/\lambda_{\sigma}$, then for universal constants $C,c>0$, with probability at least $1-e^{-cn}$, the columns of $\widecheck{X}$ satisfy

Let us remark that in settings where $\varepsilon\gg 1/\sqrt{n}$, applying Lemma D.3(b) to bound each term $(\|\widecheck{\mathbf{x}}_{\alpha}\|^{2}-1)^{2}$ separately would not yield a constant-order bound for this sum. The proof below performs a more careful analysis of the combined fluctuations of $(\|\widecheck{\mathbf{x}}_{\alpha}\|^{2}-1)^{2}$.

The quantity to be bounded is $\|\mathbf{z}+\mathbf{r}\|^{2}$. Note that $\|\mathbf{z}+\mathbf{r}\|^{2}\leq 2\|\mathbf{z}\|^{2}+2\|\mathbf{r}\|^{2}$. We have

Thus it remains to bound $\|\mathbf{z}\|^{2}$.

so $\|\mathbf{z}\|\leq 2\sup_{\mathbf{v}\in\mathcal{N}}\mathbf{v}^{\top}\mathbf{z}$. For each fixed vector $\mathbf{v}=(v_{1},\ldots,v_{n})\in\mathcal{N}$, we have

We will bound the sub-exponential norm of each summand $i=1,\ldots,\check{d}$ and apply Bernstein’s inequality.

For $\mathbf{w}\sim\mathcal{N}(0,\operatorname{Id})$, denote

Observe that $\mathbf{q}(\mathbf{w})=X^{\top}\mathbf{w}$. Thus we wish to bound the sub-exponential norm of $F(\mathbf{q}(\mathbf{w}))$ when $\mathbf{w}\sim\mathcal{N}(0,\operatorname{Id})$. By the Gaussian Sobolev inequality (see [2, Eq. (3)]), for any $p\geq 2$,

We have $(\partial/\partial q_{\alpha})F(\mathbf{q})=2\sigma(q_{\alpha})\sigma^{\prime}(q_{\alpha})v_{\alpha}$, so

Recalling (31), we have $\|\sigma(q_{\alpha})^{2}\|_{\psi_{1}}=\|\sigma(\mathbf{w}^{\top}\mathbf{x}_{\alpha})^{2}\|_{\psi_{1}}\leq C\lambda_{\sigma}^{2}$. Then

This implies the bound (see [53, Proposition 2.7.1]), for any $p\geq 1$,

for a universal constant $C^{\prime}>0$. Thus, applying this to (38), we obtain for any $p\geq 2$

Finally, this implies (see again [53, Proposition 2.7.1]) $\|F(\mathbf{q}(\mathbf{w}))\|_{\psi_{1}}\leq C^{\prime}\lambda_{\sigma}^{2}B$ for a universal constant $C^{\prime}>0$, which is our desired bound on the sub-exponential norm of $F(\mathbf{q}(\mathbf{w}))$.

Applying this and Bernstein’s inequality to (37), for any $t>0$,

for a large enough constant $C_{0}>0$, and taking the union bound over all $5^{n}$ vectors $\mathbf{v}\in\mathcal{N}$, we get

for a constant $c>0$. Combining with the bound on $\|\mathbf{r}\|^{2}$ in (36), we obtain the lemma. ∎

Appendix E Resolvent analysis for a single layer

We collect here the set of assumptions that we will use in this section.

There are constants $B,C_{0},c_{0}>0$ such that

$X$ is $(\varepsilon_{n},B)$-orthonormal, where $\varepsilon_{n}<n^{-0.01}$.

$W$ has i.i.d. $\mathcal{N}(0,1)$ entries, and $\sigma(x)$ satisfies Assumption 3.2(b).

Throughout this section, $C,C^{\prime},c,c^{\prime},n_{0}>0$ denote constants changing from instance to instance that may depend on $\lambda_{\sigma}$ and the above values $B,C_{0},c_{0}$.

Proposition C.2 ensures that $A+\alpha\widecheck{X}^{\top}\widecheck{X}-z\operatorname{Id}$ is invertible. Define the resolvent

and the deterministic ($n$-dependent) parameter

The goal of this section is to prove the following result, which approximates this resolvent $R$ by replacing the random matrix $\alpha\widecheck{X}^{\top}\widecheck{X}$ with a deterministic matrix $\bar{s}^{-1}\Phi$, and provides an approximate fixed-point equation that defines this parameter $\bar{s}$.

For $A=0$ and $\alpha=1$, we will verify in Appendix F that this result reduces to the Marcenko-Pastur equation (6).

Under Assumption E.1, deterministically for some constants $C,c,n_{0}>0$ and all $n\geq n_{0}$,

Furthermore, with probability at least $1-2e^{-c^{\prime}n}$ for a constant $c^{\prime}>0$,

We may write $A+\alpha\widecheck{X}^{\top}\widecheck{X}-z\operatorname{Id}=U+iV$ where $U=A+(\operatorname{Re}\alpha)\widecheck{X}^{\top}\widecheck{X}-(\operatorname{Re}z)\operatorname{Id}$ and $V=(\operatorname{Im}\alpha)\widecheck{X}^{\top}\widecheck{X}^{\top}-(\operatorname{Im}z)\operatorname{Id}$. Both $U$ and $V$ are symmetric, and $V\preceq(-\operatorname{Im}z)\operatorname{Id}$ because $\operatorname{Im}\alpha\leq 0$ and $\operatorname{Im}z>0$. Then $\|R\|\leq 1/\operatorname{Im}z\leq C$ by Proposition C.2.

The bound $\|\Phi\|\leq C$ comes from Lemma D.4(a) and the $(\varepsilon_{n},B)$-orthonormality assumption for $X$. Then from the definition of $\bar{s}$ in (40) and the bounds $\|R\|,\|\Phi\|\leq C$, we have also $|\bar{s}|\leq C$. For the lower bound for $\operatorname{Im}\bar{s}$ and $\operatorname{Im}\operatorname{tr}R\Phi$, let us write

The first trace is real because $R+R^{*}$ is Hermitian, so

Denoting $Y=A+\alpha\widecheck{X}^{\top}\widecheck{X}-z\operatorname{Id}$ and applying the identity $A^{-1}-B^{-1}=A^{-1}(B-A)B^{-1}$, we have

Then, writing $Y=U+iV$ as above and applying $Y^{*}-Y=-2iV$, we get

Since $\operatorname{tr}R\widecheck{X}^{\top}\widecheck{X}R^{*}\Phi=\operatorname{tr}\Phi^{1/2}R\widecheck{X}^{\top}\widecheck{X}R^{*}\Phi^{1/2}$, where this matrix is positive semi-definite, this trace is real and non-negative. Similarly, $\operatorname{tr}RR^{*}\Phi$ is real and non-negative. Then the above yields the lower bound

where $\lambda_{\min}(RR^{*})$ is the smallest eigenvalue of $RR^{*}$. By (28) and the condition $\varepsilon_{n}<n^{-0.01}$, we have $\operatorname{tr}\Phi\geq c$ for a constant $c>0$ and large enough $n_{0}$. Observe that $\lambda_{\min}(RR^{*})=1/\|Y\|^{2}$, and $\|Y\|\leq\|A\|+|\alpha|\cdot\|\widecheck{X}\|^{2}+|z|$. By Lemma D.4(b), with probability $1-2e^{-c^{\prime}n}$, we have $\|\widecheck{X}\|\leq C$, so putting this together yields $\operatorname{Im}\operatorname{tr}R\Phi\geq c$ with this probability. Finally, for the deterministic bound $\operatorname{Im}\bar{s}\geq c$, we may apply $\operatorname{Im}\operatorname{tr}R\Phi\geq c$ on the event where $\|\widecheck{X}\|\leq C$ holds, and $\operatorname{Im}\operatorname{tr}R\Phi\geq 0$ on the complementary event. Taking an expectation and applying the definition (40) yields $\operatorname{Im}\bar{s}\geq c$. ∎

E.2 Resolvent approximation

We recall the result of [39, Lemma 1], which establishes concentration of quadratic forms in the rows of $\widecheck{X}$. The following is its specialization to standard Gaussian matrices $W$, and stated in our notation.

where $t_{0}=|\sigma(0)|+\lambda_{\sigma}\|X\|\sqrt{1/\gamma}$.

Using this result, we establish the following approximation for the resolvent $R$ in (39).

Under Assumption E.1, there exist constants $C,c,c^{\prime},n_{0}>0$ such that for all $n\geq n_{0}$ and $t\in(n^{-1},c^{\prime})$,

By rescaling $M$, we may assume that $\|M\|\leq 1$. We have $\operatorname{Id}=R(A+\alpha\widecheck{X}^{\top}\widecheck{X}-z\operatorname{Id})=RA+\alpha R\widecheck{X}^{\top}\widecheck{X}-zR$. Writing $\widecheck{X}^{\top}\widecheck{X}=\sum_{i}\widecheck{\mathbf{x}}_{i}\widecheck{\mathbf{x}}_{i}^{\top}$ (where $\widecheck{\mathbf{x}}_{i}^{\top}$ is the $i^{\text{th}}$ row of $\widecheck{X}$), multiplying by $M$, and taking the normalized trace $\operatorname{tr}=n^{-1}\operatorname{Tr}$,

Let us define the leave-one-out resolvent, for each $1\leq i\leq\check{d}$,

We may then decompose $\delta_{n}$ as $\delta_{n}=J_{1}+\gamma J_{2}$ where (recalling $\gamma=n/\check{d}$)

Bound for $J_{1}$. Momentarily fix the index $i\in\{1,\ldots,\check{d}\}$. Applying the Sherman-Morrison identity, we have

Then, introducing $A_{1}=\widecheck{\mathbf{x}}_{i}^{\top}MR^{(i)}\widecheck{\mathbf{x}}_{i}$ and $A_{2}=\widecheck{\mathbf{x}}_{i}^{\top}R^{(i)}\widecheck{\mathbf{x}}_{i}$,

Applying Proposition E.3, we have for some constants $C,c,c^{\prime}>0$, on an event $\mathcal{E}(\widecheck{X}^{(i)})$ of probability $1-2e^{-c^{\prime}n}$, that

Bound for $J_{2}$. Applying the identity $A^{-1}-B^{-1}=A^{-1}(B-A)B^{-1}$,

Then, applying also the bounds $\|R\|,\|R^{(i)}\|\leq C$ from Proposition E.3,

E.3 Proof of Lemma E.2

We now prove Lemma E.2 using Lemma E.5. Define the random $n$-dependent parameter

Under Assumption E.1, for some constants $c,n_{0}>0$, all $n\geq n_{0}$, and any $t>0$,

where $\odot$ is the Hadamard product, and $\sigma^{\prime}$ is applied entrywise. Applying Proposition E.3,

Thus $|\operatorname{vec}(\Delta)^{\top}(\nabla F(W))|\leq C/\sqrt{n}$. This holds for every $\Delta$ such that $\|\Delta\|_{F}=1$, so $F(W)$ is $C/\sqrt{n}$-Lipschitz in $W$ with respect to the Frobenius norm. Then the result follows from Gaussian concentration of measure. ∎

To conclude the proof of Lemma E.2, we may again assume $\|M\|\leq 1$ by rescaling $M$. Set

for all $t\in(n^{-1},c^{\prime})$. Furthermore, applying the definition of $\widetilde{M}$,

Recall that $|\bar{s}|\geq\operatorname{Im}\bar{s}\geq c$. Then, on the event where $|s-\bar{s}|\leq t$ and $t<c/2$, we have $|s^{-1}-\bar{s}^{-1}|\leq Ct$. Then applying Lemma E.6, for some constants $c,c^{\prime}>0$ and all $t\in(0,c^{\prime})$,

Combining this with (44) yields Lemma E.2(a). Specializing Lemma E.2(a) to $M=\Phi$, we obtain

Applying again Lemma E.6 to bound $|s-\bar{s}|$, we obtain Lemma E.2(b).

Appendix F Analysis for the Conjugate Kernel

Theorem 3.4 is a special case of Theorem 3.7, but let us provide here a simpler argument. Define, for each layer, the $n\times n$ matrices

and the result follows from the condition $\varepsilon_{n}n^{1/4}\to 0$. ∎

Proposition C.3 and Lemma F.1 together show that

Thus, along the sub-subsequence where $\bar{s}\to s_{0}$, we get

Now applying Lemma E.2(a) with $M=\operatorname{Id}$, and taking the limit along this sub-subsequence, by a similar argument we obtain that

Appendix G Analysis for the Neural Tangent Kernel

where we define diagonal matrices indexed by $\alpha\in[n]$ and $k\in[L]$ as

Applying the chain rule, we may verify for each input sample $\mathbf{x}_{\alpha}$ that

where $\odot$ is the Hadamard product. Thus, the NTK is given by

With probability at least $1-2e^{-c\check{d}t^{2}}$,

With probability at least $1-(2\check{d}+2)e^{-c\min(t^{2}\check{d},t\sqrt{\check{d}})}$,

Furthermore, both (a) and (b) hold with $(\mathbf{x}_{\alpha},\mathbf{x}_{\alpha})$ in place of $(\mathbf{x}_{\alpha},\mathbf{x}_{\beta})$, upon replacing $b_{\sigma}^{2}$ by $a_{\sigma}$.

Applying $\sigma^{\prime}(\mathbf{w}_{k}^{\top}\mathbf{x}_{\alpha})\sigma^{\prime}(\mathbf{w}_{k}^{\top}\mathbf{x}_{\beta})\in[-\lambda_{\sigma}^{2},\lambda_{\sigma}^{2}]$ and Hoeffding’s inequality,

To bound the mean, recall that $(\zeta_{\alpha},\zeta_{\beta})\equiv(\mathbf{w}_{k}^{\top}\mathbf{x}_{\alpha},\mathbf{w}_{k}^{\top}\mathbf{x}_{\beta})$ is bivariate Gaussian, which we may write as

By the Hanson-Wright inequality (see [50, Theorem 1.1]),

for a constant $c>0$. Then, applying $|\sigma^{\prime}(x)|\leq\lambda_{\sigma}$ and a union bound over $k=1,\ldots,\check{d}$, with probability at least $1-2\check{d}e^{-c\min(t^{2}\check{d},t\sqrt{\check{d}})}$,

Then part (b) follows from combining with part (a), and applying $\operatorname{Tr}M\leq\sqrt{d}\|M\|_{F}$. ∎

By Corollary D.2, we may assume that each matrix $X_{0},\ldots,X_{L}$ is $(\varepsilon_{n},B)$-orthonormal. Since a larger value of $\varepsilon_{n}$ corresponds to a weaker assumption, we may assume without loss of generality that $\varepsilon_{n}\geq n^{-0.48}$.

Recalling the definition (53) and applying the Hanson-Wright inequality conditional on $W_{1},\ldots,W_{L}$,

with probability $1-e^{-n^{0.01}}$. Combining these bounds, with probability $1-C^{\prime}e^{-n^{0.01}}$,

We also have $\|W_{k}/\sqrt{d_{k}}\|\leq C$ for each $k=2,\ldots,L$ with probability $1-C^{\prime}e^{-cn}$, see e.g. [53, Theorem 4.4.5]. Then, applying $\|D_{k}\|\leq\lambda_{\sigma}$, we have $\|M_{k}\|_{F}\leq C\sqrt{n}\|M_{k}\|\leq C^{\prime}\sqrt{n}$ for every $k=1,\ldots,L$. Then the first bound of (55) follows. The second bound of (55) is the same, applying Lemma G.1 for $(\mathbf{x}_{\alpha},\mathbf{x}_{\alpha})$ instead of $(\mathbf{x}_{\alpha},\mathbf{x}_{\beta})$. The almost sure statement follows from the Borel-Cantelli Lemma. ∎

Under Assumption 3.2, almost surely as $n\to\infty$,

Furthermore, for a constant $C>0$, almost surely for all large $n$, $\|K^{\text{NTK}}\|\leq C$.

By Corollary D.2, we may assume that each matrix $X_{0},\ldots,X_{L}$ is $(\varepsilon_{n},B)$-orthonormal. Then

Increasing $\varepsilon_{n}$ if necessary, we may assume $\varepsilon_{n}\geq n^{-0.48}$. Combining with (55), we have for the off-diagonal entries of the Hadamard product that

The first statement of the lemma then follows from the assumption $\varepsilon_{n}n^{1/4}\to 0$.

For the second statement on the operator norm, we have

Combining Lemma G.3 and Proposition C.3, this proves Lemma 3.5.

G.2 Unique solution of the fixed-point equation

Since $S\Phi S^{*}$ is Hermitian and positive semi-definite, the quantities $\operatorname{tr}S\Phi S^{*}A$, $\operatorname{tr}S\Phi S^{*}\Phi$, and $\operatorname{tr}S\Phi S^{*}$ are all real, and the latter two are nonnegative. Then

Each term on the right side of (58) is nonnegative, and dropping the first two of these terms yields (a).

For part (b), applying the identity $A^{-1}-B^{-1}=A^{-1}(B-A)B^{-1}$, we have

Applying Cauchy-Schwarz to the inner-product $\langle S_{1},S_{2}\rangle_{\Phi}=\operatorname{tr}S_{1}\Phi S_{2}^{*}\Phi$,

Dropping $\operatorname{Im}\alpha^{-1}$ in (58) and applying this to upper-bound $\gamma\operatorname{tr}S\Phi S^{*}\Phi/|s|^{2}$, part (b) follows. ∎

Denoting $S\equiv S(s)$ and applying the von Neumann trace inequality,

where $\lambda_{1}(\cdot)\geq\ldots\geq\lambda_{n}(\cdot)$ denote the sorted eigenvalues. Since $\Phi$ has a non-degenerate limit spectrum, there is a constant $\varepsilon>0$ for which $\lambda_{\varepsilon n}(\Phi)>\varepsilon$ for all large $n$. (Throughout the proof, $\varepsilon n$, $\varepsilon n/2$, etc. should be understood as their roundings to the nearest integer.) Then

Denoting by $\sigma_{\alpha}(\cdot)$ the $\alpha^{\text{th}}$ largest singular value, observe that

Applying $\sigma_{\alpha+\beta-1}(A+B)\leq\sigma_{\alpha}(A)+\sigma_{\beta}(B)$, we have

Since the spectra of $A$ and $\Phi$ converge to deterministic limits, this implies that there is a constant $C(s)>0$ (also depending on $z$ and $\varepsilon$) such that $\sigma_{\alpha}(A+s^{-1}\Phi-z\operatorname{Id})\leq C(s)$ for every $\alpha\in[\varepsilon n/2,\varepsilon n]$ and all large $n$. Thus

for all large $n$, and this shows the claim (59).

Then, taking the limit $n\to\infty$ in Lemma G.4(b), we get

G.3 Proof of Proposition 3.6 and Theorem 3.7

provided that this limit exists and defines the Stieltjes transform of a probability measure. For

defined recursively by (12) and (13). Proposition 3.6 and Theorem 3.7 are immediate consequences of the following extended result.

By Corollary D.2, we may assume that each matrix $X_{0},\ldots,X_{L}$ is $(\varepsilon_{n},B)$-orthonormal.

by the same argument as (49). Then, we have

where the convergence to 0 follows from Lemma G.3. Finally, we have

Applying these approximations to (62), we have almost surely along this sub-subsequence that

the same arguments as above establish that

where $\mathbf{w}_{\text{prev}}$ is as defined in (15). Then

Appendix H Multi-dimensional outputs and rescaled parametrizations

In this section, we provide some motivation for the form of the NTK in (17) for networks with a $k$-dimensional output, and we prove Theorem 3.8 regarding its spectrum.

Then the time evolution of in-sample predictions is given by

where $K^{\text{NTK}}$ is the matrix defined in (17). For $\tau_{1}=\ldots=\tau_{L+1}=1$, this matrix is simply

H.2 Proof of Theorem 3.8

The matrix $K^{\text{NTK}}$ in (17) admits a $k\times k$ block decomposition

a computation using the chain rule similar to (54) verifies that

Under the assumptions of Theorem 3.8, for any indices $i\neq j\in[k]$, almost surely as $n\to\infty$,

Furthermore, for a constant $C>0$, almost surely for all large $n$, $\|K_{ij}^{\text{NTK}}\|\leq C$.

By Corollary D.2, we may assume that each $X_{0},\ldots,X_{L}$ is $(\varepsilon_{n},B)$-orthonormal.

for both $\alpha=\beta$ and $\alpha\neq\beta$ with probability $1-e^{-n^{0.01}}$, where $M_{L}$ is the same matrix as defined in (56). Applying the bound $\|M_{L}\|_{F}\leq C\sqrt{n}$ as in the proof of Corollary G.2, this yields

and the first statement follows from the assumption $\varepsilon_{n}n^{1/4}\to 0$. The second statement on the operator norm follows from the bound

Applying this lemma together with Proposition C.3, we obtain

where the off-diagonal blocks $K_{ij}^{\text{NTK}}$ may be replaced by 0. Then the limit spectral distribution of $K^{\text{NTK}}$ is an equally weighted mixture of those of $K_{11}^{\text{NTK}},\ldots,K_{kk}^{\text{NTK}}$. For each diagonal block $K_{ii}^{\text{NTK}}$, the argument of Lemma G.3 shows that

Then by Theorem 3.7, each diagonal block $K_{ii}^{\text{NTK}}$ has the same limit spectral distribution, whose Stieltjes transform is given by the function $m_{\text{NTK}}(z)$ in Theorem 3.8. Furthermore, since $\|K_{ii}^{\text{NTK}}\|\leq C$ by Lemma G.3 and $\|K_{ij}^{\text{NTK}}\|\leq C$ for $i\neq j$ by Lemma H.1, this shows $\|K^{\text{NTK}}\|\leq C$. This establishes Theorem 3.8.

Again, when $b_{\sigma}=0$, the limit spectrum of each $K_{ii}^{\text{NTK}}$ reduces to $\operatorname{lim\;spec}(\tau\cdot r_{+}\operatorname{Id}+\tau_{L+1}X_{L}^{\top}X_{L})$, which can be computed via the Stieltjes transform of $\rho^{\text{MP}}_{\gamma_{L}}$.

Appendix I Reduction to result of Pennington and Worah [46] for one hidden layer

Consider the one-hidden-layer conjugate kernel

and observe that the eigenvalues of $K^{\text{CK}}$ are those of $M$ multiplied by $n/d_{1}$ and padded by $n-d_{1}$ additional zeros (or with $d_{1}-n$ zeros removed, if $n-d_{1}<0$). [46, Theorem 1] characterizes the limit spectral distribution of $M$ in terms of a quartic equation in its Stieltjes transform, under the additional assumptions that $X$ has i.i.d. $\mathcal{N}(0,1/d_{0})$ entries and $n/d_{0}\to\gamma_{0}\in(0,\infty)$.In , the $1/\sqrt{d_{0}}$ scaling is in $W_{1}$ rather than $X$, but these are clearly the same. We consider $\sigma_{w}=\sigma_{x}=1$ and $\eta=1$ in the results of . By Theorem 3.4, this should be equivalent to the description

for the limit spectrum of $K^{\text{CK}}$, if we specialize to $\mu_{0}=\rho_{\gamma_{0}}^{\text{MP}}$ being the Marcenko-Pastur limit of the input gram matrix $X^{\top}X$. We derive this equivalence in this section.

Taking the limit on both sides, we obtain the relation between $m_{K}(z)$ and $m_{M}(z)$, which is

[46, Theorem 1] characterizes $G(z)\equiv-m_{M}(z)$ as the root of a quartic equation. Defining three $z$-dependent quantities $P,P_{\phi},P_{\psi}$ by

To verify that (66) is equivalent to this equation (70), note that (66) means the Stieltjes transform $m_{K}(z)$ is defined by the Marcenko-Pastur equation (6) as

Applying the identity $1-\gamma_{1}-\gamma_{1}^{2}zm_{K}(\gamma_{1}z)=-zm_{M}(z)$ from rearranging (67), and applying also $\zeta=b_{\sigma}^{2}$ in (68),

When $X$ has i.i.d. $\mathcal{N}(0,1/d_{0})$ entries, the limit spectral distribution of $X^{\top}X$ is the Marcenko-Pastur law $\mu_{0}=\rho_{\gamma_{0}}^{\text{MP}}$. The Stieltjes transform $m(z)$ of this law $\mu_{0}=\rho_{\gamma_{0}}^{\text{MP}}$ is characterized by the quadratic equation

(which is the specialization of (6) when $\mu$ is the point distribution at 1). Defining

we obtain then that $g(a,b)$ satisfies the quadratic equation

Applying this with $a=-\zeta zm_{M}(z)$ and $b=(1-\zeta)zm_{M}(z)+\gamma_{1}z$, the quantity (72) is exactly $g(a,b)$. Thus this equation holds for $g(a,b)=m_{K}(\gamma_{1}z)$ and these settings of $(a,b)$, i.e.

From the relation (67), we see that this is a quartic equation in $m_{M}(z)$. Note that the definitions of $P_{\psi}$ and $P_{\phi}$ in (69) may be equivalently written as

where we have used $G(z)=-m_{M}(z)$, $\psi/\phi=\gamma_{1}$ from (68), and the relation (67). Applying now $\gamma_{1}z=(\psi/\phi)z=1/(\phi t)$ and $\gamma_{0}=1/\phi$, the equation (73) becomes

and dividing both sides by $-\phi(1-\zeta tP_{\phi}P_{\psi})$ yields

Identifying the left side as $P$ by (69), we obtain (70) as desired.

Appendix J Additional simulation results

All pairwise inner-products $\{\mathbf{x}_{\alpha}^{\top}\mathbf{x}_{\beta}:1\leq\alpha<\beta\leq n\}$, for (a) 5000 CIFAR-10 training samples, (b) 5000 CIFAR-10 training samples with the first 10 PCs removed, and (c) i.i.d. Gaussian training data of the same dimensions. Results for (b) were reported in Section 4.2, and results for (a) are reported below in Appendix J.2. CIFAR-10 training samples were mean-centered and normalized to satisfy $\mathbf{x}_{\alpha}^{\top}1=0$ and $\|\mathbf{x}_{\alpha}\|^{2}=1$ in (a) and (b).

The pairwise inner-products in (a) span a typical range of $[-0.5,0.5]$. Those in (b) span a range of about $[-0.2,0.2]$, and those in (c) about $[-0.02,0.02]$. Thus, with 10 PCs removed, these inner-products for CIFAR-10 are larger than for i.i.d. Gaussian inputs by a factor of 10. We found in Section 4.2 that the inner-products of (b) are sufficiently small for the observed spectra to match the theoretical limits of Theorems 3.4 and 3.7.

J.2 CK and NTK spectra for CIFAR-10 without removal of leading PCs

Same plots as Figure 2 for CIFAR-10 training samples, without the removal of the 10 leading PCs. We observe a close agreement of the observed CK spectrum with the limit spectrum of Theorem 3.4. However, there is a greater discrepancy of the NTK spectrum with the limit spectrum of Theorem 3.7 in this setting.

J.3 Example images of CIFAR-10 with/without leading PCs

Example CIFAR-10 training samples for each class. For each training sample, we compare the original image (above) and the corresponding normalized image upon removing the top 10 PCs (below). Most of the image details are preserved upon removing these 10 PCs.

J.4 Observed and limit CK spectra for all layers

The same as above, corresponding to the CIFAR-10 training samples in Appendix J.2. (Results with 10 PCs removed look the same.) A close agreement with the limit spectrum described by Theorem 3.4 is observed at each layer.

Spectra of the CK matrices at all three layers, corresponding to the trained 3-layer network of Section 4.3. The limit spectra at random initialization of weights are depicted in red, and the two largest eigenvalues of each matrix are depicted by blue arrows.

J.5 CK spectrum after training on a CIFAR-10 example

We train a binary classifier on $n=10000$ training samples from CIFAR-10, corresponding to classes 0 (airplane) and 1 (automobile). The classifier is a fully-connected network with $L=4$ hidden layers of dimensions $d_{1}=\ldots=d_{4}=1000$, with bias terms and a normalized sigmoid activation at each hidden layer and also at the output layer. This network is given by

We train the weights and biases using the Adam optimizer in Keras, with learning rate 0.01, batch size 128, and 60 training epochs. To ensure that the leading PCs of the untrained kernel matrix $K^{\text{CK}}$ are not too predictive of the training labels, and to better separate the original PCs from those that emerge after training, we remove the leading 5 PCs of the input data before training. The resulting 0–1 classification accuracy on the CIFAR-10 test set is $85.3\%$. (Training without removing these 5 PCs yields a slightly higher test accuracy of $90.7\%$, using the same network architecture.)

Panel (a) above shows the eigenvalue distribution of $K^{\text{CK}}$ at random initialization, with the largest eigenvalue being approximately 500. We observe a close agreement with the limit spectrum of Theorem 3.4. Panel (b) shows the eigenvalues of $K^{\text{CK}}$ after training. We observe an elongation of the bulk spectral support and the emergence of large outlier eigenvalues, analogous to the synthetic example of Section 4.3.

The above figure depicts the information about the training labels that is contained in the top 2 PCs of $K^{\text{CK}}$, (a) before training and (b) after training. Denoting by $\hat{X}_{L}$ the rank-2 approximation of $X_{L}$, with columns $\hat{\mathbf{x}}_{1}^{L},\ldots,\hat{\mathbf{x}}_{n}^{L}$ (both before and after training), we re-fit a linear binary classifier $y_{\alpha}=\sigma(\mathbf{w}^{\top}\hat{\mathbf{x}}_{\alpha}^{L}+b)$ of the training labels to these columns. The in-sample 0–1 training accuracy of this classifier is 51.4% pre-training and 96.8% post-training, and the figure shows the linear predictions $\mathbf{w}^{\top}\hat{\mathbf{x}}_{\alpha}^{L}+b$ against the training labels $y_{\alpha}$. We observe that the leading principal components of $K^{\text{CK}}$ are not predictive of the training labels before training, but become highly predictive after training.