Controlling the Inductive Bias of Wide Neural Networks by Modifying the
  Kernel's Spectrum
Wide neural networks are biased towards learning certain functions,
influencing both the rate of convergence of gradient descent (GD) and the
functions that are reachable with GD in finite training time. As such, there is
a great need for methods that can modify this bias according to the task at
hand. To that end, we introduce Modified Spectrum Kernels (MSKs), a novel
family of constructed kernels that can be used to approximate kernels with
desired eigenvalues for which no closed form is known. We leverage the duality
between wide neural networks and Neural Tangent Kernels and propose a
preconditioned gradient descent method, which alters the trajectory of GD. As a
result, this allows for a polynomial and, in some cases, exponential training
speedup without changing the final solution. Our method is both computationally
efficient and simple to implement.
Amnon Geifman, Daniel Barzilai, Ronen Basri, Meirav Galun
# Controlling the Inductive Bias of Wide Neural Networks by Modifying the Kernel's Spectrum

###### Abstract

Wide neural networks are _biased_ towards learning certain functions, influencing both the rate of convergence of gradient descent (GD) and the functions that are reachable with GD in finite training time. As such, there is a great need for methods that can modify this _bias_ according to the task at hand. To that end, we introduce Modified Spectrum Kernels (MSKs), a novel family of constructed kernels that can be used to approximate kernels with desired eigenvalues for which no closed form is known. We leverage the duality between wide neural networks and Neural Tangent Kernels and propose a preconditioned gradient descent method, which alters the trajectory of GD. As a result, this allows for a polynomial and, in some cases, exponential training speedup without changing the final solution. Our method is both computationally efficient and simple to implement.

Machine Learning, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent, Gradient Descent Descent Descent, Gradient Descent Descent Descent, Gradient Descent Descent, Gradient Descent Descent Descent, Gradient Descent Descent, Gradient Descent Descent Descent, Gradient Descent Descent, Gradient Descent Descent Descent, Gradient Descent Descent Descent, Gradient Descent Descent Descent, Gradient Descent Descent, Gradient Descent Descent Descent Descent, Gradient Descent Descent Descent, Gradient Descent Descent Descent Descent, Gradient Descent Descent Descent Descent Descent, Gradient Descent
kernels for which a closed form is unknown (Section 3).
2. We introduce preconditioned gradient descent and prove its convergence for wide neural networks (Section 4.1).
3. We prove that our method is consistent, meaning that the preconditioning does not change the final network prediction on test points (Section 4.2).
4. We provide an algorithm that enables a wide range of spectral bias manipulations, yielding a significant convergence speedup for training wide neural networks. We finally demonstrate this acceleration on synthetic data (Section 4.3).

## 2 Preliminaries and Background

We consider positive definite kernels \(\mathbf{k}:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}\) defined over a compact metric space \(\mathcal{X}\) endowed with a finite Borel measure \(\mu\). Given such \(\mathbf{k}\), its corresponding (linear) integral operator \(L_{\mathbf{k}}:L_{\mu}^{2}(\mathcal{X})\to L_{\mu}^{2}(\mathcal{X})\) is defined as

\[L_{\mathbf{k}}(f)(\mathbf{x})=\int_{\mathbf{\mathbf{z}}\in\mathcal{X}} \mathbf{k}(\mathbf{x},\mathbf{z})f(\mathbf{z})d\mu(\mathbf{z}).\]

This is a compact, positive self-adjoint operator that therefore has an eigen-decomposition of the form

\[L_{\mathbf{k}}(f)=\sum_{i\geq 0}\lambda_{i}\langle f,\Phi_{i} \rangle_{\mu}\Phi_{i},\]

where the inner product \(\langle,\rangle_{\mu}\) is with respect to \(L_{\mu}^{2}(\mathcal{X})\), and \(\lambda_{i},\Phi_{i}\) are the eigenvalues and eigenfunctions of the integral operator satisfying

\[L_{\mathbf{k}}(\Phi_{i})=\lambda_{i}\Phi_{i}.\]

According to Mercer's Theorem, \(\mathbf{k}\) can be written using the eigen-decomposition of the integral operator as

\[\mathbf{k}(\mathbf{x},\mathbf{z})=\sum_{i\in I}\lambda_{i}\Phi_{i}( \mathbf{x})\Phi_{i}(\mathbf{z}),\ \ \ \mathbf{x},\mathbf{z}\in\mathcal{X}. \tag{1}\]

Furthermore, each such kernel is associated with a unique Reproducing Kernel Hilbert Space (RKHS) \(\mathcal{H}_{\mathbf{k}}\subseteq L_{\mu}^{2}(\mathcal{X})\) (which we denote by \(\mathcal{H}\) when the kernel is clear by context), consisting of functions of the form \(f(\mathbf{x})=\sum_{i\in I}\alpha_{i}\Phi_{i}(\mathbf{x})\) whose RKHS norm is finite, i.e., \(\|f\|_{\mathcal{H}}:=\sum_{i\in I}\frac{\alpha_{i}^{2}}{\lambda_{i}}<\infty\). The latter condition restricts the set of functions in an RKHS, allowing only functions that are sufficiently smooth in accordance to the asymptotic decay of \(\lambda_{k}\). For any positive definite kernel there exists a feature map \(\phi:\mathcal{X}\rightarrow\mathcal{H}\) s.t \(\mathbf{k}(\mathbf{x},\mathbf{z})=\langle\phi(\mathbf{x}),\phi(\mathbf{z})\rangle_ {\mathcal{H}}\). As such, we may occasionally call the RKHS \(\mathcal{H}\) the _feature space_ of \(\mathbf{k}\).

Given training data \(X=\{\mathbf{x}_{1},...,\mathbf{x}_{n}\}\), \(\mathbf{x}_{i}\in\mathcal{X}\), corresponding labels \(\{y_{i}\}_{i=1}^{n}\), \(y_{i}\in\mathbb{R}\), and a regularization parameter \(\gamma>0\), the problem of _Kernel Ridge Regression (KRR)_ is formulated as

\[\min_{f\in\mathcal{H}}\sum_{i=1}^{n}(f(\mathbf{x}_{i})-y_{i})^{2} +\gamma\|f\|_{\mathcal{H}}. \tag{2}\]

The solution satisfies \(f(\mathbf{x})=\mathbf{k}_{\mathbf{x}}^{T}(K+\gamma I)^{-1}\mathbf{y}\), where the entries of \(\mathbf{k}_{\mathbf{x}}\in\mathbb{R}^{n}\) are \(\frac{1}{n}\mathbf{k}(\mathbf{x},\mathbf{x}_{i})\), \(K\) is the \(n\times n\) kernel matrix with \(K_{ij}=\frac{1}{n}\mathbf{k}(\mathbf{x}_{i},\mathbf{x}_{j})\), and \(\mathbf{y}=(y_{1},...,y_{n})^{T}\).

## 3 Modified Spectrum Kernels

Our aim in this section is to describe and analyze the construction of novel kernels for which no closed form is known. We do so by manipulating the spectrum of existing kernels whose matrix is easy to compute. Since a constructed kernel may not have a closed form, we directly manipulate the kernel matrix of an existing kernel to fit our desired spectrum. The theory in this section refers to arbitrary kernels, and the connection to NTK and wide neural networks is deferred to Sec. 4.

**Definition 3.1**.: **Modified Spectrum Kernel (MSK).** Let \(\mathbf{k}(\mathbf{x},\mathbf{z}):=\sum_{k=1}^{\infty}\lambda_{k}\Phi_{k}(\mathbf{ x})\Phi_{k}(\mathbf{z})\) be a Mercer kernel with eigenvalues \(\lambda_{i}\) and eigenfunction \(\Phi_{i}(\cdot)\) and \(g:\mathbb{R}\rightarrow\mathbb{R}\) a function which is non-negative and \(L\)-Lipschitz. The Modified Spectrum Kernel (w.r.t. \(\mathbf{k}\)) is defined as \(\mathbf{k}_{g}(\mathbf{x},\mathbf{z}):=\sum_{k=1}^{\infty}g(\lambda_{k})\Phi_{k}( \mathbf{x})\Phi_{k}(\mathbf{z})\).

The MSK has the same eigenfunctions as the source kernel \(\mathbf{k}\), while its eigenvalues are modified by \(g\). Clearly, constructing a closed-form solution to the modified kernel is rarely possible. However, it is possible to approximate the modified kernel efficiently under certain conditions, given the values of the original kernel \(\mathbf{k}\), as proved in Theorem 3.2.

**Theorem 3.2**.: _Let \(g,\mathbf{k},\mathbf{k}_{g}\) be as in (3.1) and assume that \(\forall\mathbf{x}\in\mathcal{X},|\Phi_{i}(\mathbf{x})|\leq M\). Let \(K,K_{g}\) be the corresponding kernel matrices on i.i.d samples \(\mathbf{x}_{1},...,\mathbf{x}_{n}\in\mathcal{X}\). Define the kernel matrix \(\tilde{K}_{g}=VDV^{T}\) where \(V=(\mathbf{v}_{1},..,\mathbf{v}_{n})\) with \(\mathbf{v}_{i}\) the 'th eigenvector of \(K\) and \(D\) is a diagonal matrix with \(D_{ii}=g(\hat{\lambda}_{i})\) where \(\hat{\lambda}_{i}\) is the 'th eigenvalue of \(K\). Then, for \(n\rightarrow\infty\)_

\[\left\|\tilde{K}_{g}-K_{g}\right\|_{F}\overset{a.s.}{\rightarrow }0,\]

_where a.s. stands for almost surely._

We next provide a proof sketch. The full proof is given in Appendix C. For an eigenfunction \(\Phi\) of \(\mathbf{k}(\mathbf{x},\mathbf{z})\), we let \(\Phi(X):=(\Phi(\mathbf{x}_{1}),\dots,\Phi(\mathbf{x}_{n}))^{T}\in\mathbb{R}^ {n}\) be the evaluation of the eigenfunctions on the data. By the definition of the kernels, \(K=\sum_{k=1}^{\infty}\lambda_{k}\Phi_{k}(X)\Phi_{k}(X)^{T}\), and similarly, \(K_{g}\) can
be written as \(K_{g}=\sum_{k=1}^{\infty}g(\lambda_{k})\Phi_{k}(X)\Phi_{k}(X)^{T}\). Since \(\tilde{K}_{g}\) has the eigenvectors of \(K\) with the eigenvalues \(g(\lambda_{k})\), we would like to say that the eigenvalues of \(K_{g}\) are close to \(g(\lambda_{k})\) and that the eigenvectors of \(K\) are close to those of \(K_{g}\). It is already known that the eigenvalues of a kernel matrix converge to those of its integral operator (with the suitable normalization) (Rosasco et al., 2010), and as such, we know that the eigenvalues of \(\tilde{K}_{g}\) should be close to those of \(K_{g}\). The challenge is that the eigenvectors \(\mathbf{v}_{k}\) do not have to be close to \(\Phi_{k}(X)\), the evaluations of the eigenfunctions on the data (for example when there is an eigenvalue of multiplicity greater than 1). This means that the eigenvectors of \(\tilde{K}_{g}\) can be very different from those of \(K_{g}\). We work around this by showing that for large \(n\), if \(\mathbf{v}_{l},..,\mathbf{v}_{d}\) are the eigenvectors of \(K\) corresponding to eigenvalue \(\lambda_{k}\) and \(\Phi\) is some eigenfunction, then

\[\sum_{i=l}^{d}(\mathbf{v}_{i}^{T}\Phi(X))^{2}\rightarrow\begin{cases}1\ \ \text{if}\ \Phi\ \text{is an eigenfunction of}\ \lambda_{k}\\ 0\ \ \text{else},\end{cases}\]

allowing us to show that the norm between the eigenspaces of \(\tilde{K}_{g}\) and \(K_{g}\) tends to 0.

Kernel Construction with MSKs.Generating new kernels from existing ones is a long-standing problem in kernel theory (Saitoh & Sawano, 2016). The classical kernel theory uses arithmetic operations such as addition and multiplication of kernels to generate new kernels with unique RKHSs. Recent papers provided tools to building data dependent kernels based on training points (Simon, 2022; Sindhwani et al., 2005; Ionescu et al., 2017). Nevertheless, there are still many kernels for which a closed form is unknown.

MSKs allow extending existing RKHS theory by computing new kernels with predetermined Mercer decomposition even when a closed form is unknown and, specifically, solve KRR with these new kernels. Suppose we would like to solve the problem of KRR as defined in (2). Let \(\mathbf{k}(\mathbf{x},\mathbf{z})=\sum_{k=1}^{\infty}\lambda_{k}\Phi_{k}(\mathbf{ x})\Phi_{k}(\mathbf{z})\) and \(\mathbf{k}_{g}(\mathbf{x},\mathbf{z})=\sum_{k=1}^{\infty}g(\lambda_{k})\Phi_{k}( \mathbf{x})\Phi_{k}(\mathbf{z})\) be two Mercer kernels where \(\mathbf{k}(\mathbf{x},\mathbf{z})\) has a known closed form, whereas \(\mathbf{k}_{g}(\mathbf{x},\mathbf{z})\) does not. Assuming we obtain i.i.d. samples of training points \(\mathbf{x}_{1},..,\mathbf{x}_{n}\) and a test point \(\mathbf{x}\), we can build \(\tilde{K}_{g}\) (as in Theorem 3.2) using the \(n+1\) points \(\mathbf{x}_{1},..,\mathbf{x}_{n},\mathbf{x}\). Then, by a continuity argument, Theorem 3.2 guarantees that the predictor \(f^{*}(\mathbf{x})=[\tilde{K}_{g}]_{n+1,1:n}([\tilde{K}_{g}]_{1:n,1:n}+\gamma I )^{-1}\mathbf{y}\) converges to the KRR prediction with the kernel \(\mathbf{k}_{g}\), where \([\ \cdot\ ]_{,:}\) corresponds to the sub-matrix induced by the specified indices.

## 4 Provable NTK Based Preconditioning for Neural Networks

In this section, we develop and analyze a preconditioning scheme for accelerating the convergence rate of gradient descent in the training phase of neural networks while minimizing the Mean Squares Error (MSE) loss. The acceleration is achieved by manipulating the spectrum of the NTK, overcoming the spectral bias of neural networks. We begin by explaining how the convergence rate of neural networks is related to the spectrum of the NTK. Then, we introduce a preconditioning scheme for wide neural networks and prove that it attains a global optimum. We further prove that in the infinite width limit and when training the network to completion, preconditioned and standard gradient descent converge to the same global minimum.

We consider a fully connected neural network parameterized as follows:

\[\mathbf{g}^{(0)}(\mathbf{x}) =\mathbf{x}\] \[\mathbf{f}^{(l)}(\mathbf{x}) =W^{(l)}\mathbf{g}^{(l-1)}(\mathbf{x})+\mathbf{b}^{(l)}\in\mathbb{ R}^{d_{l}},\ \ \ \ l=1,\ldots L\] \[\mathbf{g}^{(l)}(\mathbf{x}) =\rho\left(\mathbf{f}^{(l)}(\mathbf{x})\right)\in\mathbb{R}^{d_{l }},\ \ \ \ l=1,\ldots L\] \[f(\mathbf{x},\mathbf{w}) =f^{(L+1)}(\mathbf{x})=W^{(L+1)}\cdot\mathbf{g}^{(L)}(\mathbf{x} )+b^{(L+1)}.\]

where \(\mathbf{w}\in\mathbb{R}^{p}\) is the set of all the network parameters. We select a simple architecture and note that our results can easily extend to many other architectures. We denote by \(m\) the width of the network and assume that \(d_{1}=d_{2}=..=d_{L}=m\). The activation function is denoted by \(\rho\) and the following quantities \(|\rho(0)|\), \(\left\|\rho^{\prime}\right\|_{\infty}\), and \(\sup_{x\neq x^{\prime}}|\rho^{\prime}(x)-\rho^{\prime}(x^{\prime})|/|x-x^{ \prime}|\) should be finite. We use standard initialization that assures that the network is trained in the NTK regime (see more details in Appendix A).

We denote the vector of labels for all the data points \((y_{1},\ldots,y_{n})\) by \(\mathbf{y}\in\mathbb{R}^{n}\) and the vector of network predictions \(f(\mathbf{x}_{i},\mathbf{w})\) by \(f(X,\mathbf{w})\in\mathbb{R}^{n}\). The residual at time \(t\) is \(\mathbf{r}_{t}:=f(X,\mathbf{w}_{t})-\mathbf{y}\). Letting \(\mathcal{L}\) be the squared error loss, \(\mathcal{L}(\mathbf{w}_{t})=\frac{1}{2}\left\|\mathbf{r}_{t}\right\|^{2}\), a gradient descent iteration for optimizing \(\mathbf{w}\in\mathbb{R}^{p}\) is given by

\[\mathbf{w}_{t+1}-\mathbf{w}_{t}=-\eta\nabla_{\mathbf{w}}\mathcal{L}(\mathbf{w} _{t})=-\eta\nabla_{\mathbf{w}}f(X,\mathbf{w}_{t})^{T}\mathbf{r}_{t}, \tag{3}\]

where \(\eta\) is the learning rate, and \(\nabla_{\mathbf{w}}f(X,\mathbf{w}_{t})\in\mathbb{R}^{n\times p}\) is the Jacobian of the network.

The empirical NTK matrix at time \(t\), \(K_{t}\in\mathbb{R}^{n\times n}\), and the NTK matrix, \(K\in\mathbb{R}^{n\times n}\), are defined as

\[K_{t}= \frac{1}{m}\nabla_{\mathbf{w}}f(X,\mathbf{w}_{t})\nabla_{\mathbf{ w}}f(X,\mathbf{w}_{t})^{T} \tag{4}\] \[K= \text{lim}_{m\rightarrow\infty}K_{0}. \tag{5}\]

(Arora et al., 2019) showed that for a wide neural network with ReLU activation, small initialization, and a small learning rate, it holds that for every \(\epsilon>0\), the residual at time
evolves with the following linear dynamics

\[\left\|\mathbf{r}_{t}\right\|=\left\|(I-\eta K)^{t}\mathbf{y}\right\| \pm\epsilon=\sqrt{\sum_{i=1}^{n}(1-\eta\lambda_{i})^{2t}(\mathbf{v}_{i}^{T} \mathbf{y})^{2}}\pm\epsilon, \tag{6}\]

where \(\{\lambda_{i}\}_{i=1}^{n}\) and \(\{\mathbf{v}_{i}\}_{i=1}^{n}\) respectively are the eigenvalues and eigenvectors of the NTK matrix \(K\).

Eq. (6) reveals the relation between the inductive bias of neural networks and the spectrum of the NTK matrix (Basri et al., 2020). Specifically, to learn an eigen-direction \(\mathbf{v}_{i}\) of a target function within accuracy \(\delta>0\), it is required that \((1-\eta\lambda_{i})^{t}<\delta+\epsilon\). When the learning rate is sufficiently small to imply convergence, \(0<\eta<\frac{2}{\lambda_{i}}\), the number of iterations needed is

\[t>-\log(\delta+\epsilon)/\eta\lambda_{i}=O\left(\frac{\lambda_{1}}{\lambda_{ i}}\right).\]

The eigenvalues and eigenvectors of \(K\) depend on the data distribution and are not yet fully characterized for arbitrary distributions (e.g., (Basri et al., 2020)). In the case of a fully connected network with ReLU activation and with data points distributed uniformly on the sphere \(\mathbb{S}^{d-1}\), the eigenvectors are discretizations of the spherical harmonics and the eigenvalues asymptotically decay as \(\lambda_{k}\approx k^{-d}\), where \(k\) is the frequency (Basri et al., 2020; Bietti and Bach, 2020). In this scenario, learning a high-frequency eigenvector with gradient descent is computationally prohibitive, even for a low-dimension sphere. With other activation functions, the asymptotic decay of the eigenvalues might be even exponential (Murray et al., 2022), yielding an infeasible computational learning cost for learning high frequency target functions.

### Preconditioned Gradient Descent

To accelerate the convergence of standard gradient descent (3), we propose a _preconditioned gradient descent_ (PGD). The update rule of our PGD is given by

\[\mathbf{w}_{t+1}=\mathbf{w}_{t}-\eta\nabla_{\mathbf{w}}f(X,\mathbf{w}_{t})^{T }S\mathbf{r}_{t}, \tag{7}\]

where \(S\in\mathbb{R}^{n\times n}\) is a preconditioning matrix that satisfies \(S\succ 0\).

In contrast to standard preconditioning techniques, which multiply the complete gradient with a preconditioning matrix, we manipulate only the network's gradient, hence reducing the cost per iteration for a generic preconditioner from \(p^{2}\) (where \(p\), the number of parameters in the network, is usually huge) to \(n^{2}\), where in the over-parameterized case \(n\ll p\).

We next show an analogous result to the linear dynamics of the form of (6) for PGD. The key difference, is that carefully choosing \(S\) enables to manipulate the dynamics of gradient descent almost arbitrarily.

**Theorem 4.1**.: _Let \(\eta_{0},\delta_{0},\epsilon>0\), \(S\in\mathbb{R}^{n\times n}\) such that \(S\succ 0\) and \(\eta_{0}<\frac{2}{\lambda_{min}(KS)+\lambda_{max}(KS)}\). Then, there exists \(N\in\mathbb{N}\) such that for every \(m\geq N\), the following holds with probability at least \(1-\delta_{0}\) over random initialization when applying preconditioned GD with learning rate \(\eta=\eta_{0}/m\)_

\[\mathbf{r}_{t}=(I-\eta_{0}KS)^{t}\mathbf{y}\pm\xi(t),\]

_where \(\left\|\xi\right\|_{2}\leq\epsilon\)._

Recall that we assume \(K\succ 0\) and \(S\succ 0\), so while \(KS\) is not necessarily positive definite or symmetric, it has positive real eigenvalues. As such, the term \(\frac{2}{\lambda_{min}(KS)+\lambda_{max}(KS)}\) is positive and defines the maximal feasible learning rate. The formal proof of Theorem 4.1 is given in Appendix A, and here we give some key points of the proof. The proof relies on Lemma 4.2, which shows that PGD finds a global minimum in which the weights are close to their initial values. In particular, for any iteration \(t\), \(K_{t}S\approx K_{0}S\approx KS\). Based on the results of Lemma 4.2, Theorem 4.1 carefully bounds the distance \(\xi(t)\) between \(\mathbf{r}_{t}\) and the linear dynamics \((I-\eta_{0}KS)^{t}\mathbf{y}\).

**Lemma 4.2**.: _For \(\delta_{0}>0\), \(\frac{2}{\lambda_{min}(KS)+\lambda_{max}(KS)}>\eta_{0}\) and \(S\) such that \(S\succ 0\), there exist \(C>0\), \(N\in\mathbb{N}\) and \(\kappa>1\), such that for every \(m\geq N\), the following holds with probability at least \(1-\delta_{0}\) over random initialization. When applying preconditioned gradient descent as in (7) with learning rate \(\eta=\eta_{0}/m\)_

1. \(\left\|\mathbf{r}_{t}\right\|_{2}\leq\left(1-\frac{\eta\lambda_{min}}{3} \right)^{t}C\)__
2. \(\sum_{j=1}^{t}\left\|\mathbf{w}_{j}-\mathbf{w}_{j-1}\right\|_{2}\leq\frac{3 \kappa C}{\lambda_{min}}m^{-1/2}\)__
3. \(\sup_{t}\left\|(K_{0}-K_{t})S\right\|_{F}\leq\frac{6\kappa^{3}C}{\lambda_{min }}m^{-1/2}\)_,_

_where \(\lambda_{min}\) is the minimal eigenvalue of \(KS\)._

The full proof of Lemma 4.2 is given in Appendix A.

Theorem 4.1 implies that the dynamics of preconditioned gradient descent are characterized by \(KS\) instead of \(K\). In particular, if \(KS\) is symmetric, PGD follows the dynamics

\[\left\|\mathbf{r}_{t}\right\|=\left\|(I-\eta KS)^{t}\mathbf{y}\right\|\pm \epsilon=\sqrt{\sum_{i=1}^{n}(1-\eta\hat{\lambda}_{i})^{2t}(\hat{\mathbf{v}}_{ i}^{T}\mathbf{y})^{2}}\pm\epsilon, \tag{8}\]

where now, in contrast to (6), \(\hat{\lambda}_{i},\hat{\mathbf{v}}_{i}\) are the eigenvalues and eigenvectors of \(KS\). This enables to manipulate the convergence behaviour in two ways. The first is to reduce the condition number of \(K\) and therefore achieve a significant improvement in the convergence rate. The second is
to change certain eigenvalues and therefore manipulate the relative convergence of each eigenfunction of the NTK.

where now, in contrast to (6), \(\hat{\lambda}_{i},\hat{\mathbf{v}}_{i}\) are the eigenvalues and eigenvectors of \(KS\). As such, the choice of \(S\) determines the rate at which the network converges to any specific target function.

The results of Zhang et al. (2019) and Cai et al. (2019) can be viewed as a special case of (8). Specifically, these works characterize the convergence of an approximate second-order method (Gauss-Newton) when applied to a wide, two-layer network. In this case, the update rule is of the form

\[\mathbf{w}_{t+1}-\mathbf{w}_{t}=-\eta F(\mathbf{w}_{t})^{-1}\nabla_{\mathbf{w }}\mathcal{L}(\mathbf{w}_{t}),\]

with \(F\) being the Fisher information matrix associated with the network's predictive distribution. Their derivation leads to similar convergence results as shown in (8) but is limited to the case of \(S=K_{t}^{-1}\).

We show in Sec. 4.3 how \(S\) can be chosen to reduce by a polynomial (or even exponential) factor the number of iterations required to converge in the directions corresponding to small eigenvalues of \(K\). This is highly beneficial when the projections of the target function on the eigenvectors of \(K\), \((\hat{\mathbf{v}}_{i}^{T}\mathbf{y})\) are relatively large in directions corresponding to small eigenvalues. For example, for image reconstruction or rendering, this equates to learning more efficiently the fine details, which correspond to high frequencies in the image (Tancik et al., 2020). Another example arises in Physics Informed Neural Networks (PINN), which were shown to suffer significantly from the slow convergence rate in the directions corresponding to small eigenvalues (Wang et al., 2022).

### Convergence Analysis

In this section, we characterize the resulting prediction function of the network on unseen test points and show that PGD generates a consistent prediction function in the following sense. At convergence, the prediction function of a network trained with PGD is close to the prediction function of a network trained with standard GD.

We start by defining a preconditioned loss, \(\mathcal{L}_{S}(f,\mathbf{w})\), which modifies the standard MSE loss

\[\mathcal{L}_{S}(f,\mathbf{w})=\frac{1}{2}\left\|\hat{S}^{1/2}(f(X,\mathbf{w})- \mathbf{y})\right\|_{2}^{2}, \tag{9}\]

where \(S\succ 0\) is the preconditioning matrix. An iteration of standard GD w.r.t \(\mathcal{L}_{S}(f,\mathbf{w})\) yields

\[\mathbf{w}_{t+1}-\mathbf{w}_{t}=-\eta\nabla_{\mathbf{w}}\mathcal{L}_{S}(f, \mathbf{w}_{t})=-\eta\nabla_{\mathbf{w}}f(X,\mathbf{w}_{t})^{T}S\mathbf{r}_{ t}, \tag{10}\]

which is equivalent to a PGD iteration (7) with the standard MSE loss. This has two implications. First, it implies that PGD can easily be implemented by simply modifying the loss function. Second, it enables us to analyze the prediction function generated by PGD.

Specifically, given an initialization \(\mathbf{w}_{0}\in\mathbb{R}^{p}\), let \(\phi(\mathbf{x}):=\nabla f(\mathbf{x},\mathbf{w}_{0})\) and \(h(\mathbf{x},\mathbf{w}^{\prime}):=\langle\mathbf{w}^{\prime},\phi(\mathbf{x })\rangle\). For simplicity, we denote \(h(X,\mathbf{w}^{\prime}):=(h(\mathbf{x}_{1},\mathbf{w}^{\prime}),\ldots,h( \mathbf{x}_{n},\mathbf{w}^{\prime}))^{T}\in\mathbb{R}^{n}\).

The minimizer of the kernel ridge regression objective with respect to the preconditioned loss is defined as

\[\mathbf{w}_{\gamma}^{*}:=\operatorname*{arg\,min}_{\mathbf{w}^{\prime}\in \mathbb{R}^{p}}\frac{1}{2}\left\|S^{1/2}(h(X,\mathbf{w}^{\prime})-\mathbf{y} )\right\|_{2}^{2}+\frac{1}{2}\gamma\left\|\mathbf{w}^{\prime}\right\|_{2}^{2}, \tag{11}\]

and the minimizer of a kernel ridge regression with respect to the standard MSE loss is defined as

\[\mathbf{w}_{\gamma}^{**}:=\operatorname*{arg\,min}_{\mathbf{w}^{\prime}\in \mathbb{R}^{p}}\frac{1}{2}\left\|(h(X,\mathbf{w}^{\prime})-\mathbf{y})\right\| _{2}^{2}+\frac{1}{2}\gamma\left\|\mathbf{w}^{\prime}\right\|_{2}^{2}. \tag{12}\]

We denote by \(\mathbf{w}^{*}\) and \(\mathbf{w}^{**}\) the limits of \(\mathbf{w}_{\gamma}^{*}\) and \(\mathbf{w}_{\gamma}^{**}\), respectively, when \(\gamma\to 0\). In Lemma 4.3 we show that the two minimizers are equal, which means that the preconditioned loss does not change the prediction function in kernel regression.

For a given learning rate \(\eta\) and loss \(\mathcal{L}_{S}\), \(h\) can be optimized through gradient descent with respect to the loss \(\mathcal{L}_{S}\) via the iterations

\[\mathbf{w}_{0}^{\prime}=0\quad;\quad\mathbf{w}_{t+1}^{\prime}=\mathbf{w}_{t}^ {\prime}-\eta\nabla\mathcal{L}_{S}(h,\mathbf{w}_{t}^{\prime}). \tag{13}\]

We show in Lemma 4.3 that this iterative procedure yields a prediction function that remains close to the neural network prediction throughout PGD.

**Lemma 4.3**.:
1. _Let_ \(\mathbf{w}_{0}\in\mathbb{R}^{p}\) _and_ \(\phi(\mathbf{x}):=\nabla f(\mathbf{x},\mathbf{w}_{0})\)_, it holds that_ \(\mathbf{w}^{*}=\mathbf{w}^{**}\)_._
2. _Let_ \(\delta_{0}>0\)_,_ \(\epsilon>0\)_, a test point_ \(\mathbf{x}\in\mathbb{R}^{d}\) _and_ \(T>0\) _number of iteration. Under the conditions of Theorem_ 4.1_,_ \(\exists N\in\mathbb{N}\) _s.t_ \(\forall m>N\)_, it holds with probability at least_ \(1-\delta_{0}\) _that_ \[|h(\mathbf{x},\mathbf{w}_{T}^{\prime})-f(\mathbf{x},\mathbf{w}_{T})|\leq\epsilon,\] _where_ \(\mathbf{w}^{\prime}\) _is as in (_13_) and_ \(f\) _is optimized with PGD._

The full proof of Lemma 4.3 can be found in Appendix B. Point (1) is proved by deriving \(\mathbf{w}_{\gamma}^{*}\) in closed form, i.e., \(\mathbf{w}_{\gamma}^{*}=\sum_{i=1}^{n}\alpha_{i}^{*}\phi(\mathbf{x}_{i})\), with

\[\alpha^{*}=(K_{0}+\gamma S^{-1})^{-1}\mathbf{y}.\]

This serves as a generalization of the standard kernel ridge regression solution, which is obtained by substituting \(S=I\). Therefore, using the preconditioned loss yields a corresponding change of the regularization. When taking \(\gamma\to 0\), the
solution becomes equivalent to that of the standard kernel ridge regression problem.

Point (2) states that in the limit of infinite width, the value of \(f(\cdot,\mathbf{w}_{T})\) at a test point is very close to \(h(\cdot,\mathbf{w}_{T}^{\prime})\). We note that as \(\mathcal{L}_{S}\) is convex, \(h(\mathbf{x},\mathbf{w}_{T}^{\prime})\) approaches \(h(\mathbf{x},\mathbf{w}^{*})\) for sufficiently large \(T\).

By combining these two points we obtain that, with sufficiently many iterations and large width, \(f\) well approximates the solution of the standard kernel ridge regression problem, and thus of the standard non-preconditioned gradient descent on the network itself (Lee et al., 2019).

### An Algorithm for Modifying the Spectral Bias

In light of Theorem 4.1, \(S\) can be chosen to mitigate any negative effect arising from NTK. Specifically, we can modify the spectral bias of neural networks in a way that enables them to efficiently learn the eigen-directions of the NTK that correspond to small eigenvalues. To this end, we use a MSK based precondition, as outlined in the PGD algorithm 1.

First, given the NTK matrix \(K\) of size \(n\times n\), we construct a pre-conditioner from \(K\) by applying a spectral decomposition, obtaining the top \(k+1\) eigenvalues and eigenvectors. We denote the top \(k+1\) eigenvalues by \(\lambda_{1}\geq\ldots\geq\lambda_{k}\geq\lambda_{k+1}>0\), and their corresponding eigenvectors by \(\mathbf{v}_{1},\ldots,\mathbf{v}_{k},\mathbf{v}_{k+1}\). The proposed pre-conditioner is of the form

\[S=I-\sum_{i=1}^{k}\left(1-\frac{g(\lambda_{i})}{\lambda_{i}}\right)\mathbf{v} _{i}\mathbf{v}_{i}^{T}. \tag{14}\]

It can be readily observed that \(S\) and \(K\) share the same eigenvectors, and as long as \(g(\lambda_{i})>0\) then \(S\succ 0\) and its eigenvalues given in descending order are:

\[\left[1,\ldots,1,\frac{g(\lambda_{k})}{\lambda_{k}},\ldots,\frac{g(\lambda_{ 1})}{\lambda_{1}}\right].\]

Since \(S\) and \(K\) share the same eigenvectors, it holds that the eigenvalues of \(KS\) are

\[[g(\lambda_{1}),\ldots,g(\lambda_{k}),\lambda_{k+1},\lambda_{k+2},..,\lambda_{ n}].\]

The connection with Theorem 3.2 can now be clearly seen, as the product \(KS\) yields a MSK matrix, and therefore approximates a kernel that shares the same eigenfunctions of \(\mathbf{k}\) and its eigenvalues are modified by \(g\) (where for \(\lambda\geq\lambda_{k+1}\) we let \(g(\lambda)=\lambda\)). Together with Theorem 4.1, the dynamics of the neural network are controlled by this modified kernel, and as such we obtain a way to alter the spectral bias of neural networks.

As an example, we may set \(g(\lambda_{i})=\lambda_{k+1}\), \(1\leq i\leq k\), making the top \(k+1\) eigenvalues equal to each other. Then, due to (8), by picking the learning rate \(\eta=\frac{2}{\lambda_{k+1}+\lambda_{n}}\), we get that for every \(i\leq k+1\), \(\mathbf{v}_{i}\) can be learnt in \(O(1)\) time (number of iterations). This starkly contrasts the typical spectral bias of neural networks, under which for large \(i\), learning \(\mathbf{v}_{i}\) may be infeasible in polynomial time. For example, when the activation function \(\rho\) is tanh, Murray et al. (2022) showed that \(\lambda_{k}=O\left(k^{-d+1/2}e^{-\sqrt{k}}\right)\). Applying (6), vanilla GD requires \(O\left(k^{d+1/2}e^{\sqrt{k}}\right)\) iterations to converge, exponentially slower in \(k\) compared to PGD.

We leave the choice of \(k\), the number of modified eigenvalues, to the practitioners. Typically, the NTK matrix will be ill-conditioned with the smallest eigenvalues very close to 0. Thus, \(k\) may be chosen in a way that helps avoid these numeric instabilities. Furthermore, since only the top \(k\) eigenvalues and eigenvectors need to be calculated, choosing a small \(k\) allows for a very efficient calculation of \(S\). By contrast, choosing \(k=n\) implies that \(S=K^{-1}\).

Previous work showed that the networks' width in the NTK regime should generally exceed \(m\sim n^{4}\)(Song and Yang, 2019). Therefore, in this regime inverting \(K\) or calculating its eigenvalues (\(O(n^{3})\) operations) is cheaper than computing the gradient (\(O(n^{4})\) operations). Our method is also significantly more efficient than a standard preconditioner matrix whose size is \(\sim L^{2}m^{2}\sim L^{2}n^{8}\). Furthermore, in practice, one may choose \(k\), the number of eigenvalues to modify, to be small, leading to further speedups.

**Experiments**. We validated our results numerically by tracking the speed of convergence for a neural network both with and without a preconditioner. We generated inputs from a uniform distribution on the circle, \(\mathbf{x}_{i}\sim U(\mathbb{S}^{1})\). With each input we associated a target value \(y_{i}\) by taking a Fourier component of frequency \(k\) (we repeated this experiment with different values of \(k\)), i.e., if \(\mathbf{x}_{i}=(\cos(\theta),\sin(\theta))^{T}\) then \(y_{i}=\sin(k\theta)\). Note that under the uniform distribution on the circle, the Fourier components are the eigenfunctions of the integral operator of NTK for fully connected networks (Basri et al., 2019). We then trained a fully connected network to regress the target function. For efficiency, we trained the network with stochastic gradient descent (SGD). The preconditioner \(S\) is chosen to be either \(I_{n}\) (no precon
ditioning), \(K^{-1}\) (inverse NTK matrix), or \(K_{t}^{-1}\) (inverse empirical NTK matrix). Figure 1 shows that without preconditioning, the number of standard GD iterations is roughly quadratic in the frequency of the target function and quickly reaches the iteration limit. In contrast, using preconditioners based on either \(K\) or \(K_{t}\) boosts the convergence, yielding a near-constant number of iterations, irrespective of the frequency of the target function. It can be seen that without preconditioning, the number of standard GD iterations is roughly quadratic in the frequency of the target function and quickly reaches the iteration limit. In contrast, using preconditioners based on either \(K\) or \(K_{t}\) boosts the convergence, yielding a near constant number of iterations, irrespective of the frequency of the target function. The lower panel in Figure 1 also shows a convergence plot for a few different functions.

## 5 Related Works

A long string of works established the connection between kernel regression and neural networks. Early works considered a Bayesian inference setting for neural networks, showing that randomly initialized networks are equivalent to Gaussian processes (Williams, 1997; Neal, 2012). In this direction, Cho and Saul (2009) introduced the Arc-cosine kernel, while Daniely et al. (2016) studied general compositional kernels and its relation to neural networks. Recently, a family of kernels called the Neural Tangent Kernels (NTK) was introduced (Jacot et al., 2018; Allen-Zhu et al., 2019; Arora et al., 2019). These papers proved that training an over-paramterized neural network is equivalent to using gradient decent to solve kernel regression with NTK. Follow-up works defined analogous kernels for residual networks (Huang et al., 2020), convolutional networks (Arora et al., 2019; Li et al., 2019), and other standard architectures (Yang, 2020).

Subsequent work used the NTK theory to characterize the spectral bias of neural networks. Bach (2017); Basri et al. (2019); Cao et al. (2019); Bietti and Bach (2020); Xu et al. (2019) have studied the eigenfunctions and eigenvalues of NTK under the uniform distribution and further showed that fully connected neural networks learn low-frequency functions faster than higher-frequency ones. Basri et al. (2020) further derived the eigenfunctions of NTK with non-uniform data distribution. Yang and Salman (2019); Misiakiewicz and Mei (2021) analyzed the eigenvalues of NTK over the Boolean cube. More recent studies investigated this bias with other network architectures, including fully-connected ResNets (Belfer et al., 2021; Tirer et al., 2022), convolutional networks (Geifman et al., 2022; Cagnetta et al., 2022; Xiao, 2022), and convolutional ResNets (Barzilai et al., 2022). (Murray et al., 2022) characterized the spectrum of NTK using its power series expansion.

Preconditioning is a widely used approach to accelerating convex optimization problems. A preconditioner is typically constructed using the inverse of the Hessian or its approximation (Nocedal and Wright, 1999) to improve the condition number of the problem. Recent works tried to improve the condition number of kernel ridge regression. Ma and Belkin (2017); Ma et al. (2018) suggested using a left preconditioner in conjunction with Richardson iterations. Another line of work analyzed the speed of convergence of an approximate second order method for two-layer neural networks (Zhang et al., 2019; Cai et al., 2019). They showed that natural gradient descent improves convergence in a factor proportional to the condition number of the NTK Gram matrix.

Figure 1: Numerical validation. Top: The number of iterations required to learn different Fourier components as a function of frequency. Standard SGD is shown in blue, and (stochastic) PGD with a preconditioner derived from the NTK matrix \(K\) and the empirical NTK \(K_{t}\) respectively are shown in green and orange. Bottom: Training curves with four different frequencies (\(k=5,7,10,12\)). The graphs show the MSE loss as a function of iteration number with stochastic GD and PGD.
Several studies aim to construct preconditioners for neural networks. Carlson et al. (2015) built a diagonal preconditioner based on Adagrad and RMSProp updates. Other heuristic preconditoiners use layer-wise adaptive learning rates (You et al., 2017, 2019). In this line of work, it is worth mentioning (Lee et al., 2020), who used the convergence results of (Arora et al., 2019) to incorporate leverage score sampling into training neural networks. Amari et al. (2020) studied the generalization of overparameterized ridgeless regression under a general class of preconditioners via the bias-variance trade-off.

Past studies explored the concept of data-dependent kernels. Simon (2022) suggested using the posterior of the target function to produce a new type of data-dependent kernel. Sindhwani et al. (2005) studied a wide class of kernel modifications conditioned on the training data and explored their RKHS. Ionescu et al. (2017) extended this method to build a new class of kernels defined by multiplying the random feature approximation with a weighted covariance matrix. Kennedy et al. (2013) constructed a new family of kernels for a variety of data distributions using the Spherical Harmonic functions on the 2-Sphere.

## 6 Conclusion

In this work we addressed the problem of manipulating the spectral bias of neural networks. We formulated a unique preconditioning scheme which enables manipulating the speed of convergence of gradient descent in each eigen-direction of the NTK. This preconditioning scheme can be efficiently implemented by a slight modification to the loss function. Furthermore, for sufficient training time and width, we showed that the predictor obtained by standard GD is approximately the same as that of PGD. We also showed how to construct novel kernels with nearly arbitrary eigenvalues through the use of kernel spectrum manipulations. Our theory is supported by experiments on synthetic data. In future work we plan to explore other forms of spectral manipulations and apply our method in real-world scenarios.

## Acknowledgements

Research at the Weizmann Institute was partially supported by the Israel Science Foundation, grant No. 1639/19, by the Israeli Council for Higher Education (CHE) via the Weizmann Data Science Research Center and by research grants from the Estate of Tully and Michele Plesser and the Anita James Rosen Foundation.
